2009/08/31 by Vijay V. Vazirani
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Algorithm #Computer science #Economic theories and models #Function (biology) #Game Theory and Applications #Game Theory and Voting Systems #Mathematical analysis #Mathematical optimization #Mathematics #Nash equilibrium #Polynomial #Regular polygon #Solver #Time complexity #cs.DS #cs.GT
paper · pdf · doi:10.1007/978-3-642-16170-4_28
arxiv created 2009/09/24 · openalex publication_date 2010/01/01 · arxiv updated 2015/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The solution to a Nash or a nonsymmetric bargaining game is obtained by maximizing a concave function over a convex set, i.e., it is the solution to a convex program. We show that each 2-player game whose convex program has linear constraints, admits a rational solution and such a solution can be found in polynomial time using only an LP solver. If in addition, the game is succinct, i.e., the coefficients in its convex program are ``small'', then its solution can be found in strongly polynomial time. We also give a non-succinct linear game whose solution can be found in strongly polynomial time.