Winning Without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every Round

Avrim Blum, Melissa Dutz

Introduction

In classical game theory, agents are typically modeled as perfectly rational entities that always select mathematically optimal strategies. However, human behavior is frequently governed by cognitive shortcuts and biases, such as the gambler’s fallacy or loss aversion. This paper explores a challenging "blind" competitive environment: a symmetric, zero-sum game where a player can observe their opponent’s actions but receives no feedback regarding the payoffs or the current score.

While previous research established that a player could guarantee a tie in this low-information setting by simply mimicking the opponent (the "Copycat" algorithm), this work investigates whether a player can go further. Specifically, it asks: if an opponent follows predictable behavioral biases, can a player reverse-engineer the hidden game structure and eventually win nearly every round?

The Problem Setting: Permissible Games

The authors focus on "Permissible Games," defined as symmetric, zero-sum games where every possible action can be defeated by at least one other action. The primary hurdle in this environment is the lack of payoff visibility. Even if a player can perfectly predict that an opponent will play "Action A," they do not know which of their own actions beats "Action A" because the game matrix is hidden. To win, the player must simultaneously learn the opponent's behavioral patterns and the underlying rules of the game.

Methodology: Prediction and Probing

The authors propose a two-step framework to overcome the lack of information:

1. Predicting the Opponent

To anticipate the opponent's next move, the player employs a "halving algorithm." The player maintains a set of all possible hypotheses regarding the game matrix and the opponent's tie-breaking rules. By taking a majority vote of these hypotheses and immediately discarding any that fail to predict the opponent's actual move, the player rapidly narrows down the possible strategies the opponent might be using.

2. Learning Best Responses

Predicting a move is insufficient if the player does not know the payoff matrix. To bridge this gap, the player must "probe" the opponent. By playing specific sequences of actions, the player forces the biased opponent into states where their subsequent responses reveal the hidden payoffs. For example, if an opponent reacts to losses by shifting actions, their shift reveals which of the player's previous moves was the "winner."

For more complex behavioral models, the authors utilize the Ellipsoid Algorithm. This method treats the unknown game matrix as a point within a high-dimensional space. Each move made by the opponent provides a mathematical constraint (an inequality) that shrinks the volume of the space where the true matrix could reside, eventually isolating the correct payoffs.

Exploiting Specific Behavioral Biases

The paper demonstrates that several common behavioral strategies are highly vulnerable to exploitation:

  • Myopic Best Responder: An opponent who simply responds to the player's last move. The proposed algorithm learns to win every round after a maximum of $n+1$ rounds (where $n$ is the number of possible actions).
  • Gambler’s Fallacy: An opponent who believes a certain outcome is "due" and responds to the player's least-played move. The algorithm guarantees a consistent win from round $3n$ onwards.
  • Win-Stay, Lose-Shift (WSLS): A strategy where the opponent repeats successful moves and changes unsuccessful ones. The player can learn to win all but $O(n^2)$ rounds.
  • Follow the Leader (FTL): An opponent who plays the best action in retrospect against the player's entire history. This is the most complex bias to exploit; using the Ellipsoid method, the authors prove the player can win all but a number of rounds that is exponential in the number of actions but polynomial in the total rounds played.

Key Insights

A central takeaway of the research is that behavioral biases act as an information "side channel." Because a biased opponent reacts to the history of play in a structured, non-random way, their actions inadvertently leak information about the underlying payoff matrix. However, the player must often be willing to play sub-optimally in the short term—effectively sacrificing rounds to "force" information out of the opponent—before they can achieve a dominant winning streak.

Limitations and Future Work

The current findings are limited to deterministic behavioral strategies. If an opponent introduces randomness or follows a probabilistic strategy, the halving and ellipsoid methods become significantly more difficult to apply, as a single observation can no longer definitively rule out a hypothesis.

Future research directions include extending these techniques to probabilistic strategies, exploring extensive-form games like Poker where information is partially hidden, and determining if these methods can achieve positive average payoffs even when the specific nature of the opponent's bias is unknown at the start of the game.

Summary updated

BibTeX
@inproceedings{blum2024winning,
  author = {Avrim Blum and Melissa Dutz},
  title = {{Winning Without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every Round}},
  booktitle = {ITCS},
  year = {2024},
  doi = {10.4230/lipics.itcs.2024.18},
}
Figure