TY - GEN

T1 - Approximate Equilibrium Computation for Discrete-Time Linear-Quadratic Mean-Field Games

AU - Uz Zaman, Muhammad Aneeq

AU - Zhang, Kaiqing

AU - Miehling, Erik

AU - Basar, Tamer

N1 - Funding Information:
The authors are affiliated with the Coordinated Science Laboratory, University of Illinois at Urbana–Champaign Urbana, IL 61801. Research supported in part by AFOSR (FA9550-19-1-0353), in part by ARL (W911NF-17-2-0196),and in part by ARO (W911NF-16-1-0485).

PY - 2020/7

Y1 - 2020/7

N2 - While the topic of mean-field games (MFGs) has a relatively long history, heretofore there has been limited work concerning algorithms for the computation of equilibrium control policies. In this paper, we develop a computable policy iteration algorithm for approximating the mean-field equilibrium in linear-quadratic MFGs with discounted cost. Given the mean-field, each agent faces a linear-quadratic tracking problem, the solution of which involves a dynamical system evolving in retrograde time. This makes the development of forward-in-time algorithm updates challenging. By identifying a structural property of the mean-field update operator, namely that it preserves sequences of a particular form, we develop a forward-in-time equilibrium computation algorithm. Bounds that quantify the accuracy of the computed mean-field equilibrium as a function of the algorithm's stopping condition are provided. The optimality of the computed equilibrium is validated numerically. In contrast to the most recent/concurrent results, our algorithm appears to be the first to study infinite-horizon MFGs with non-stationary mean-field equilibria, though with focus on the linear quadratic setting.

AB - While the topic of mean-field games (MFGs) has a relatively long history, heretofore there has been limited work concerning algorithms for the computation of equilibrium control policies. In this paper, we develop a computable policy iteration algorithm for approximating the mean-field equilibrium in linear-quadratic MFGs with discounted cost. Given the mean-field, each agent faces a linear-quadratic tracking problem, the solution of which involves a dynamical system evolving in retrograde time. This makes the development of forward-in-time algorithm updates challenging. By identifying a structural property of the mean-field update operator, namely that it preserves sequences of a particular form, we develop a forward-in-time equilibrium computation algorithm. Bounds that quantify the accuracy of the computed mean-field equilibrium as a function of the algorithm's stopping condition are provided. The optimality of the computed equilibrium is validated numerically. In contrast to the most recent/concurrent results, our algorithm appears to be the first to study infinite-horizon MFGs with non-stationary mean-field equilibria, though with focus on the linear quadratic setting.

UR - http://www.scopus.com/inward/record.url?scp=85089564380&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85089564380&partnerID=8YFLogxK

U2 - 10.23919/ACC45564.2020.9147474

DO - 10.23919/ACC45564.2020.9147474

M3 - Conference contribution

AN - SCOPUS:85089564380

T3 - Proceedings of the American Control Conference

SP - 333

EP - 339

BT - 2020 American Control Conference, ACC 2020

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2020 American Control Conference, ACC 2020

Y2 - 1 July 2020 through 3 July 2020

ER -