Paper Info
Title
The price of optimum in a matching game
Abstract
Due to the lack of coordination, it is unlikely that the selfish players of a strategic game reach a socially good state. Using Stackelberg strategies is a popular way to improve the system's performance. Stackelberg strategies consist of controlling the action of a fraction a of the players. However compelling an agent can be costly, unpopular or just hard to implement. It is then natural to ask for the least costly way to reach a desired state. This paper deals with a simple strategic game which has a high price of anarchy: the nodes of a simple graph are independent agents who try to form pairs. We analyse the optimization problem where the action of a minimum number of players shall be fixed and any possible equilibrium of the modified game must be a social optimum (a maximum matching). For this problem, deciding whether a solution is feasible or not is not straitforward, but we prove that it can be done in polynomial time. In addition the problem is shown to be APX-hard, since its restriction to graphs admitting a vertex cover is equivalent, from the approximability point of view, to VERTEX COVER in general graphs
Year
Venue
Keywords
2011
SAGT
general graph,matching game,good state,simple strategic game,vertex cover,optimization problem,simple graph,strategic game,modified game,approximability point,stackelberg strategy
Field
DocType
Volume
Simultaneous game,Mathematical economics,Mathematical optimization,Computer science,Repeated game,Price of anarchy,Normal-form game,Screening game,Sequential game,Game tree,Non-cooperative game
Conference
6982
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
17
3
Name
Order
Citations
PageRank
Bruno Escoffier143037.32
Laurent Gourvès224130.97
Jérôme Monnot351255.74