The Price of Optimum: Complexity and Approximation for a Matching Game - Sorbonne Université Accéder directement au contenu
Article Dans Une Revue Algorithmica Année : 2017

The Price of Optimum: Complexity and Approximation for a Matching Game

Résumé

This paper deals with a matching game in which the nodes of a simple graph are independent agents who try to form pairs. If we let the agents make their decision without any central control then a possible outcome is a Nash equilibrium, that is a situation in which no unmatched player can change his strategy and find a partner. However, there can be a big difference between two possible outcomes of the same instance, in terms of number of matched nodes. A possible solution is to force all the nodes to follow a centrally computed maximum matching but it can be difficult to implement this approach. This article proposes a tradeoff between the total absence and the full presence of a central control. Concretely, we study the optimization problem where the action of a minimum number of agents is centrally fixed and any possible equilibrium of the modified game must be a maximum matching. In algorithmic game theory, this approach is known as the price of optimum of a game. For the price of optimum of the matching game, deciding whether a solution is feasible is not straightforward, but we prove that it can be done in polynomial time. In addition, the problem is shown APX-hard, since its restriction to graphs admitting a perfect matching is equivalent, from the approximability point of view, to vertex cover. Finally we prove that this problem admits a polynomial 6-approximation algorithm in general graphs.
Fichier non déposé

Dates et versions

hal-01483682 , version 1 (06-03-2017)

Identifiants

Citer

Bruno Escoffier, Laurent Gourvès, Jérôme Monnot. The Price of Optimum: Complexity and Approximation for a Matching Game. Algorithmica, 2017, 77 (3), pp.836-866. ⟨10.1007/s00453-015-0108-5⟩. ⟨hal-01483682⟩
197 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More