Learning a Game by Paying the Agents
For game theory and multi-agent systems, this provides a method to learn and influence no-regret learning agents, addressing the practical problem of steering agents without knowing their preferences.
The paper introduces a principal who can observe, signal, and pay agents in a repeated normal-form game, and shows that the principal can learn the agents' utility functions to any desired precision using a polynomial number of rounds, for any no-regret learning algorithms. This is then used to steer agents to a desired equilibrium without prior knowledge of their utilities.
We study the problem of learning the utility functions of no-regret learning agents in a repeated normal-form game. Differing from most prior literature, we introduce a principal with the power to observe the agents playing the game, send agents signals, and give agents payments as a function of their actions. We show that the principal can, using a number of rounds polynomial in the size of the game, learn the utility functions of all agents to any desired precision $ε> 0$, for any no-regret learning algorithms of the agents. Our main technique is to formulate a zero-sum game between the principal and the agents, where the principal chooses strategies among the set of all payment functions to minimize the agent's payoff. Finally, we discuss implications for the problem of steering agents. We introduce, using our utility-learning algorithm as a subroutine, the first algorithm for steering arbitrary no-regret learning agents to a desired equilibrium without prior knowledge of their utility functions.