Cycle patterns reveal player behavior in random two player games
Cycle structure of best-response dynamics in random bimatrix games
Computer Science and Game Theory
Summary
Some games are made by two players taking turns to pick their best move based on what the other player did. The authors studied many random versions of these games to see how players might end up repeating the same moves over and over in cycles. They found that the type of game changes how long these repeating loops are and how many different loops show up. To do this, they represented the back-and-forth moves as arrows linking choices, then looked for cycles in those arrows.
What this means in practice
- •For game developers: Analyze and predict repeating strategy patterns in multiplayer games with complex payoffs.
- •For economic modelers: Better understand cycle lengths in competitive scenarios modeled as bimatrix games with random outcomes.
Tested on simulated data.
Authors
Georgios Nikolaos Karelas, Gábor Lugosi, Rui-Ray Zhang
Abstract
We study the best-response dynamics in games with random payoffs. We consider two-player bimatrix games, with $n$ strategies each. We assume that payoffs come from a continuous distribution, and study the best-response dynamics of these games, after imposing some structure on their payoff matrices. In particular, we focus on symmetric games, antisymmetric games, common-interest games, zero-sum games, and games with independent payoffs. When two players take turns in playing the best response to the opponent's action, they eventually end up cycling through the same sequence of actions. The main focus of the paper is the cycle structure of large random games. In particular, we study the number of cycles, the number of cycles of a certain length, the length of the longest cycle, and related quantities. We show that the structure of the game has an important impact on the typical cycle structure. Our arguments are based on a representation of the best-response dynamics of these games as directed bipartite graphs, and on the cycle structure that arises in them.