Core-selecting auction mechanisms are auctions that select player utilities which satisfy certain stability properties. They are currently of theoretical and practical interest in mechanism design, having already been used to conduct multi-billion dollar auctions. We generalize the concept of a Core-selecting auction mechanism to a large class of complete information games and demonstrate that several well-known games can be described by these Core-selecting mechanisms. Our main result is a bound on the Price of Anarchy of Core-selecting mechanisms. Provided some simple conditions are met, there are Core-selecting mechanisms with Price of Anarchy at most 1 + 1/D^2, where D in [0,1] is a measure of the degree of submodularity of the game's social welfare function, expressed as a set function. In addition to this result, we show that there exist special Core-selecting mechanisms which have two additional properties: they are player-Pareto optimal and they provide a local, individual utility guarantee. / Les mécanismes d'enchères de Coeur-sélection (Core-selecting auction mechanisms) sont des enchères qui sélectionnent les utilités des joueurs qui satisfont certains propriétés de stabilité. Ils occupent présentement une place d'intérêt théorique et pratique dans la théorie de la conception des mécanismes, ayant été utilisés pour effectuer des enchères avec des recettes en milliards de dollars. Nous généralisons la notion d'un mécanisme d'enchères de Coeur-sélection pour les appliquer à des jeux des informations complètes. Nous démontrons que ces mécanismes décrivent plusieurs jeux bien connus. Notre résultat principal est un majorant pour le Prix de l'Anarchie (Price of Anarchy) des mécanismes de Coeur-sélection. Nous démontrons que, si certaines conditions simples sont atteintes, il existe des mécanismes de Coeur-sélection avec un Prix de l'Anarchie d'au plus que 1+1/D^2, où D, entre 0 et 1, est une measure du degré du Sous-modularité (Submodularity) de la fonction du Bien-être du jeu, encodée sous forme de fonction d'ensemble. En plus de cette garantie, nous démontrons qu'il éxiste des mécanismes de Coeur-sélection qui ont aussi deux autres caractéristiques: ils sont Joueur-Optimales (Player Optimal), et ils garantissent un minimum pour le bien-être individuel.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.121179 |
| Date | January 2014 |
| Creators | Sloan, Peter |
| Contributors | Adrian Roshan Vetta (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Arts (Department of Mathematics and Statistics) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses |
Page generated in 0.012 seconds