The Price of Mediation

Abstract : We study the relationship between correlated equilibria and Nash equilibria. In contrast to previous work focusing on the possible benefits of a benevolent mediator, we define and bound the Price of Mediation (PoM): the ratio of the social cost (or utility) of the worst correlated equilibrium to the social cost (or utility) of the worst Nash. We observe that in practice, the heuristics used for mediation are frequently non-optimal, and from an economic perspective mediators may be inept or self-interested. Recent results on computation of equilibria also motivate our work. We consider the Price of Mediation for general games with small numbers of players and pure strategies. For two player, two strategy games we give tight bounds in the non-negative cost model and the non-negative utility model. For larger games (either more players, or more pure strategies per player, or both) we show that the PoM can be arbitrary. We also have many results on symmetric congestion games (also known as load balancing games). We show that for general convex cost functions, the PoM can grow exponentially in the number of players. We prove that the PoM is one for linear costs and at most a small constant (but can be larger than one) for concave costs. For polynomial cost functions, we prove bounds on the PoM which are exponential in the degree.
Keywords : Discrete Algorithms
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.31--60
Liste complète des métadonnées

https://hal.inria.fr/hal-01179210
Contributeur : Hélène Lowinger <>
Soumis le : mercredi 22 juillet 2015 - 09:14:47
Dernière modification le : jeudi 7 septembre 2017 - 01:03:41
Document(s) archivé(s) le : vendredi 23 octobre 2015 - 10:23:41

Fichier

dmtcs-16-1-3.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01179210, version 1

Collections

Citation

Milan Bradonjic, Gunes Ercal, Adam Meyerson, Alan Roytman. The Price of Mediation. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.31--60. 〈hal-01179210〉

Partager

Métriques

Consultations de la notice

85

Téléchargements de fichiers

147