License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.66
URN: urn:nbn:de:0030-drops-101597
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10159/
Go to the corresponding LIPIcs Volume Portal

Kim Thang, Nguyen

Game Efficiency Through Linear Programming Duality

pdf-format:
LIPIcs-ITCS-2019-66.pdf (0.5 MB)

Abstract

The efficiency of a game is typically quantified by the price of anarchy (PoA), defined as the worst ratio of the 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.

BibTeX - Entry

@InProceedings{kimthang:LIPIcs:2018:10159,
  author =	{Nguyen Kim Thang},
  title =	{{Game Efficiency Through Linear Programming Duality}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{66:1--66:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10159},
  URN =		{urn:nbn:de:0030-drops-101597},
  doi =		{10.4230/LIPIcs.ITCS.2019.66},
  annote =	{Keywords: Price of Anarchy, Primal-Dual}
}

Keywords: Price of Anarchy, Primal-Dual
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI