TY - GEN
T1 - Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming
AU - Caragiannis, Ioannis
AU - Jiang, Zhile
N1 - Publisher Copyright:
© 2023 ACM.
PY - 2023/6/2
Y1 - 2023/6/2
N2 - Cut games are among the most fundamental strategic games in algorithmic game theory. It is well-known that computing an exact pure Nash equilibrium in these games is PLS-hard, so research has focused on computing approximate equilibria. We present a polynomial-time algorithm that computes 2.7371-approximate pure Nash equilibria in cut games. This is the first improvement to the previously best-known bound of 3, due to the work of Bhalgat, Chakraborty, and Khanna from EC 2010. Our algorithm is based on a general recipe proposed by Caragiannis, Fanelli, Gravin, and Skopalik from FOCS 2011 and applied on several potential games since then. The first novelty of our work is the introduction of a phase that can identify subsets of players who can simultaneously improve their utilities considerably. This is done via semidefinite programming and randomized rounding. In particular, a negative objective value to the semidefinite program guarantees that no such considerable improvement is possible for a given set of players. Otherwise, randomized rounding of the SDP solution is used to identify a set of players who can simultaneously improve their strategies considerably and allows the algorithm to make progress. The way rounding is performed is another important novelty of our work. Here, we exploit an idea that dates back to a paper by Feige and Goemans from 1995, but we take it to an extreme that has not been analyzed before.
AB - Cut games are among the most fundamental strategic games in algorithmic game theory. It is well-known that computing an exact pure Nash equilibrium in these games is PLS-hard, so research has focused on computing approximate equilibria. We present a polynomial-time algorithm that computes 2.7371-approximate pure Nash equilibria in cut games. This is the first improvement to the previously best-known bound of 3, due to the work of Bhalgat, Chakraborty, and Khanna from EC 2010. Our algorithm is based on a general recipe proposed by Caragiannis, Fanelli, Gravin, and Skopalik from FOCS 2011 and applied on several potential games since then. The first novelty of our work is the introduction of a phase that can identify subsets of players who can simultaneously improve their utilities considerably. This is done via semidefinite programming and randomized rounding. In particular, a negative objective value to the semidefinite program guarantees that no such considerable improvement is possible for a given set of players. Otherwise, randomized rounding of the SDP solution is used to identify a set of players who can simultaneously improve their strategies considerably and allows the algorithm to make progress. The way rounding is performed is another important novelty of our work. Here, we exploit an idea that dates back to a paper by Feige and Goemans from 1995, but we take it to an extreme that has not been analyzed before.
KW - Approximate pure Nash equilibrium
KW - cut games
KW - randomized rounding
KW - semidefinite programming
UR - https://www.scopus.com/pages/publications/85163129294
U2 - 10.1145/3564246.3585236
DO - 10.1145/3564246.3585236
M3 - Article in proceedings
AN - SCOPUS:85163129294
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 710
EP - 722
BT - STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
A2 - Saha, Barna
A2 - Servedio, Rocco A.
PB - Association for Computing Machinery
T2 - 55th Annual ACM Symposium on Theory of Computing, STOC 2023
Y2 - 20 June 2023 through 23 June 2023
ER -