Computing Constrained Approximate Equilibria in Polymatrix Games

Deligkas, Fearnley and Savani, RSJ ORCID: 0000-0003-1262-7831 (2017) Computing Constrained Approximate Equilibria in Polymatrix Games In: Symposium on Algorithmic Game Theory (SAGT).

Text note.pdf - Author Accepted Manuscript Download (343kB)

Abstract

This paper studies constrained approximate Nash equilibria in polymatrix games. We show that is NP-hard to decide if a polymatrix game has a constrained approximate equilibrium for 9 natural constraints and any non-trivial ∈. We then provide a QPTAS for polymatrix games with bounded treewidth and logarithmically many actions per player that finds constrained approximate equilibria for a wide family of constraints.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	cs.GT, cs.GT
Depositing User:	Symplectic Admin
Date Deposited:	25 Jul 2017 08:40
Last Modified:	22 May 2026 21:00
DOI:	10.1007/978-3-319-66700-3_8
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3008589
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.