Tesi di LAUREA SPECIALISTICA Titolo An Automated Mechanism Design Approach for Federated Search Engines Data 2011-12-20 Autore/i Trovò, Francesco Relatore Gatti, N. Relatore Ceppi, S. Full text non disponibile Abstract Today one of the most interesting scientific problems, is the handling of environments where multiple intelligent agents interact. If we are holding an auction or if we arbiter a divorce goods division, we need a tool which is able to find a proper solution in order to satisfy all the involved people. While game theory is useful to find equilibria in predetermined games, mechanism design is the technique able to create new algorithms for multiple agents interactions. It was initially developed in economics, but nowadays it has applications in many different fields. This theory allows to find new mechanism satisfying some wanted properties. Some of the usual requirements are that the agents involved should be incentivated to report truthfully their preferences (Incentive Compatibility) and they should also be stimulated to participate (Individual Rationality). At last, we also would like that the mechanism is valuable for the arbiter of the contention (Weakly Budget Balance). Unfortunately, it is not always possible to find a solution with classic mechanism design. Various impossibility results were shown, excluding the possibility to design an appropriate mechanism for all the settings. In such a case, we can exploit the possibility to convert our problem into a linear programming one and solve it with operation research. This method is known as Automated Mechanism Design, because it is able to construct the mechanism without any help from the human component, while the classical version of this method has to construct analytically the mechanism. The online advertisement auctions present an interesting application field for mechanism design techniques. In this setting, multiple agents compete in order to get their advertisements impressed in a search engine web page. Among the possible auction of this kind, the one named federated search engine auctions are challenging respect to the mechanism design point of view. In fact, it is possible to show impossibility results regarding this setting, which suggest finding a solution applying the automated mechanism design technique. In this master thesis, we want to study the possibility to apply automated mechanism design to federated search engine online advertisement auction. We will first describe the theory in order to understand the tools we will use and then we will present the setting we are considering. After a formal description of the model, we will perform some simulation in order to understand the eective power of the automated mechanism design techniques.