When Should a Leader Act Suboptimally? The Role of Inferability in Repeated Stackelberg Games
This addresses the challenge of autonomous agents conveying intentions in non-adversarial interactions, though it appears incremental as it builds on existing game theory models.
The paper tackles the problem of inferable behavior in repeated Stackelberg games, showing that the performance gap due to a follower's incomplete information is bounded by the number of interactions and the leader's strategy stochasticity, with results encouraging less stochastic strategies.
When interacting with other decision-making agents in non-adversarial scenarios, it is critical for an autonomous agent to have inferable behavior: The agent's actions must convey their intention and strategy. We model the inferability problem using Stackelberg games with observations where a leader and a follower repeatedly interact. During the interactions, the leader uses a fixed mixed strategy. The follower does not know the leader's strategy and dynamically reacts to the statistically inferred strategy based on the leader's previous actions. In the inference setting, the leader may have a lower performance compared to the setting where the follower has full information on the leader's strategy. We refer to the performance gap between these settings as the inferability gap. For a variety of game settings, we show that the inferability gap is upper-bounded by a function of the number of interactions and the stochasticity level of the leader's strategy, encouraging the use of inferable strategies with lower stochasticity levels. We also analyze bimatrix Stackelberg games and identify a set of games where the leader's near-optimal strategy may potentially suffer from a large inferability gap.