Designing budget-balanced best-response mechanisms for network coordination games. (English) Zbl 1319.91054

Escoffier, Bruno; Ferraioli, Diodato; Gourvès, Laurent; Moretti, Stefano

Vöcking, Berthold (ed.), Algorithmic game theory. 6th international symposium, SAGT 2013, Aachen, Germany, October 21–23, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-41391-9/pbk). Lecture Notes in Computer Science 8146, 207-218 (2013).

Summary: Network coordination games (NCGs) have recently received a lot of attention since they model several kinds of interaction problems in social networks. However, the performance of these games at equilibrium may be very bad. This motivates the adoption of mechanisms for inducing a socially optimal state. Many settings are naturally dynamical and thus we believe it is worth to consider the design of incentive compatible best-response mechanisms [N. Nisan et al., “Best-response mechanisms”, in: Innovations in computer science (ICS). 155–165 (2011)] for NCGs. Specifically, we would like to assign to players special fees in order to induce the optimum profile of an NCG. Moreover, we would like the mechanism to be budget-balanced, i.e., implementable with no cost.
We show that a budget-balanced and incentive compatible best-response mechanism for inducing the optimal profile of a two-strategy NCG always exists. Moreover, for such a mechanism, we investigate other properties inspired by envy-freeness, collusion-resistance and fairness.
For the entire collection see [Zbl 1273.91018].

MSC:

91A80	Applications of game theory
91A43	Games involving graphs
91B26	Auctions, bargaining, bidding and selling, and other market models
91B32	Resource and cost allocation (including fair division, apportionment, etc.)
91D30	Social networks; opinion dynamics