2007/03/27 by Edith Elkind, Leslie Ann Goldberg, Elkind, Edith +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Artificial Intelligence in Games #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Multiagent Systems (cs.MA) #cs.DS #cs.GT #cs.MA
paper · pdf · doi:10.48550/arxiv.cs/0703133
25 pages. Short version appears in ACM EC'07
arxiv created 2007/03/27 · openalex publication_date 2007/03/27 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper addresses the problem of fair equilibrium selection in graphical games. Our approach is based on the data structure called the \em best response policy, which was proposed by Kearns et al. \citekls as a way to represent all Nash equilibria of a graphical game. In \citeegg, it was shown that the best response policy has polynomial size as long as the underlying graph is a path. In this paper, we show that if the underlying graph is a bounded-degree tree and the best response policy has polynomial size then there is an efficient algorithm which constructs a Nash equilibrium that guarantees certain payoffs to all participants. Another attractive solution concept is a Nash equilibrium that maximizes the social welfare. We show that, while exactly computing the latter is infeasible (we prove that solving this problem may involve algebraic numbers of an arbitrarily high degree), there exists an FPTAS for finding such an equilibrium as long as the best response policy has polynomial size. These two algorithms can be combined to produce Nash equilibria that satisfy various fairness criteria.