Bifurcation analysis of auction mechanisms

This thesis focuses on the field of algorithmic applied to problems of decision with opponents, commonly called algorithmic game theory. This field combines mathematical models, which describe situations of strategic interaction, with algorithmic tools, which allow to find solutions that prescribe to each player the best strategies to be implemented. Within this framework, a topic currently studied by the scientific community is the development of economic mechanisms when the players, who will take part in the mechanism, use adaptive strategies, commonly called learning strategies. For example, a typically used algorithm is Q-Learning. To design the best economic mechanism it is necessary to model the learning dynamics of the players and study the calibration of the parameters of the mechanism using system theory tools, such as bifurcation studies. The objective of this project is to study this type of problem in the context of the auction scenarios. In particular, online advertising auctions (used, for example, by Google, Microsoft, Amazon) have been analyzed.

Quello dei meccanismi economici è uno dei campi attualmente studiati della comunità scientifica. Abbiamo applicato strumenti della teoria dei giochi algoritmica a problemi d'asta con l'obiettivo di progettare un meccanismo in grado di guidare il sistema verso uno stato con un Social Welfare migliore rispetto a quello dell'equilibrio di Nash. Abbiamo studiato ed analizzato i meccanismi della First Price, Generalized Second Price e della GSP ripetuta con budget fissato. Ogni giocatore che prende parte al meccanismo utilizza strategie adattive, comunemente dette di learning. Oggetto di studio sono state le dinamiche evolutive del Q-Learning, FAQ e Gradient Ascent. Per modellare le dinamiche di apprendimento e studiare la calibrazione dei parametri abbiamo utilizzato strumenti di teoria dei sistemi, mentre, per lo studio di biforcazione, abbiamo utilizzato MATCONT un tool di Matlab in grado di analizzare sistemi di equazioni dinamiche. Infine è stato progettato un meccanismo in grado di guidare il sistema verso uno stato con Social Welfare migliore rispetto a quello del Nash che non è raggiungibile nel caso di giocatori razionali.