Approximating Equilibria in Restricted Games

Authors

Jack W. Doyle, Phillips Academy AndoverFollow

Abstract

We consider optimal play in restricted games with linear constraints, and use ϵ-equilibria to find near-equilibrium states in these games. We present three mathematical optimization formulations -- a mixed-integer linear program (MILP), a quadratic program with linear constraints (QP), and a quadratically constrained program (QCP) -- to both approximate and identify these states. The MILP has a short runtime relative to the QP and QCP for large games (a factor 100 faster for |S|=9) and exhibits linear growth in run time, but provides only relatively weak upper bound. The QP and QCP provide a tight bound and the precise value respectively, and outperform the LP for small games (|S| ≤ 5), but they exhibit an exponential growth of the required runtime.

Author Bio

Jack is a junior at Philips Academy Andover. He is interested in computational approaches towards problems in discrete math, specifically graph theory and game theory. In his free time he plays the violin, and tries to create new cryptosystems.

Faculty Sponsor

Benoît Legat

Recommended Citation

Doyle, Jack W. (2024) "Approximating Equilibria in Restricted Games," Rose-Hulman Undergraduate Mathematics Journal: Vol. 25: Iss. 1, Article 7.
Available at: https://scholar.rose-hulman.edu/rhumj/vol25/iss1/7