Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00453-015-0108-5 | Algorithmica |
Keywords | Field | DocType |
Approximation algorithm,Srategic game,Complexity,Price of Anarchy,Price of optimum,Stackelberg strategy | Minimax,Combinatorics,Mathematical optimization,Strategy,Algorithmic game theory,Repeated game,Normal-form game,Sequential game,Game tree,Mathematics,Extensive-form game | Journal |
Volume | Issue | ISSN |
77 | 3 | 0178-4617 |
Citations | PageRank | References |
1 | 0.35 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bruno Escoffier | 1 | 430 | 37.32 |
| Laurent Gourvès | 2 | 241 | 30.97 |
| Jérôme Monnot | 3 | 512 | 55.74 |