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.