23rd Conference of the International Federation of Operational Research Societies
Abstract Submission

1054. The optimal play against the fictitious play learning algorithm in infinitely repeated games

Invited abstract in session HE-22: Combinatorial Optimization & Game Theory , cluster Game Theory and Operations Management.

Thursday, 16:15-17:45
Room: FENH202

Authors (first author is the speaker)

1. YIFEN MU
Academy of Mathematics and Systems Science, Chinese Academy of Sciences
2. Hongcheng Dong
Academy of Mathematics and System Sciences, Chinese Academy of Sciences
3. Xiaoguang Yang
Institute of Systems Science, Academy of Mathematics and Systems Science, Chinese Academy of Sciences

Abstract

With the rapid development of artificial intelligence in recent years, games between the human(or a perfect player) and machine/AI would become more common and the related problems would be more important. In this work, we will investigate the infinitely repeated games between the human and machine/AI, where the machine/AI adopts the classical learning algorithm, Fictitious Play(FP), to update its action each time. We will study the globally optimal strategy of the human over the infinite time. This problem involves evolution analysis and optimal control for the dynamical game systems driven by the learning algorithm and a perfect opponent, insufficiently studied in the literature, especially from the point of theoretical analysis. For all the two-player-two-action games, we will prove and construct the optimal strategy of the human, turning out to be dependent on the order relations between the human’s payoff values. Furthermore, under the optimal strategy, the outcome of the game system will enter a cycle if the machine’s payoff parameter is rational, while the cyclic behavior would be broken if the machine’s payoff parameter is irrational. Moreover, the period of the cycle or the limiting proportion of outcomes depends on the machine’s payoff parameter, too. In all the games with different payoff structures, the Fictitious Play algorithm can be exploited to the utmost extent, implying the intrinsic drawbacks of the algorithm from this point. Results in this work are rigorous and might shed some light on the analysis for more general game models and more advanced learning algorithms.

Keywords

Status: accepted

Back to the list of papers