Scalable Equilibrium Computation in Multi-agent Influence Games on Networks
Fotini Christia, Michael Curry, Constantinos Daskalakis, Erik Demaine, John P. Dickerson, MohammadTaghi Hajiaghayi, Adam Hesterberg, Marina Knittel
Abstract
We provide a polynomial-time, scalable algorithm for equilibrium computation in multi-agent influence games on networks, extending work of Bindel, Kleinberg, and Oren (2015) from the single-agent to the multi-agent setting. In games of influence, agents have limited advertising budget to influence the initial predisposition of nodes in some network towards their products, but the eventual decisions of the nodes are determined by the stationary state of DeGroot opinion dynamics on the network, which takes over after the seeding (Ahmadinejad et al. 2014, 2015). In multi-agent systems, how should agents spend their budgets to seed the network to maximize their utility in anticipation of other advertising agents and the network dynamics? We show that Nash equilibria of this game are pure and (under weak assumptions) unique, and can be computed in polynomial time; we test our model by computing equilibria using mirror descent for the two-agent case on random graphs.
BibTeX
@inproceedings{aaai2021_scalableequilibr,
title = {Scalable Equilibrium Computation in Multi-agent Influence Games on Networks},
author = {Fotini Christia and Michael Curry and Constantinos Daskalakis and Erik Demaine and John P. Dickerson and MohammadTaghi Hajiaghayi and Adam Hesterberg and Marina Knittel and Aidan Milliff},
booktitle = {AAAI 2021},
year = {2021}
}