Title: Game Efficiency through Linear Programming Duality,
Abstract: The efficiency of a game is typically quantified by the price of anarchy
(PoA), defined as the worst ratio of the objective function value of an
equilibrium --- solution of the game --- and that of an optimal outcome. Given
the tremendous impact of tools from mathematical programming in the design of
algorithms and the similarity of the price of anarchy and different measures
such as the approximation and competitive ratios, it is intriguing to develop a
duality-based method to characterize the efficiency of games.
In the paper, we present an approach based on linear programming duality to
study the efficiency of games. We show that the approach provides a general
recipe to analyze the efficiency of games and also to derive concepts leading
to improvements. The approach is particularly appropriate to bound the PoA.
Specifically, in our approach the dual programs naturally lead to competitive
PoA bounds that are (almost) optimal for several classes of games. The approach
indeed captures the smoothness framework and also some current non-smooth
techniques/concepts. We show the applicability to the wide variety of games and
environments, from congestion games to Bayesian welfare, from full-information
settings to incomplete-information ones.