What Do Agents Think One Another Want? Level-2 Inverse Games for Inferring Agents' Estimates of Others' Objectives

This paper proposes a novel level-2 inverse game framework that infers agents' estimates of each other's objectives to address the limitations of traditional level-1 methods in decentralized scenarios, demonstrating through theory and experiments that accounting for these mutual misalignments is crucial for accurately predicting strategic interactions.

The Gist

Imagine you are watching a dance floor where two people are trying to move around each other without bumping.

The Old Way (Level-1 Inference): The "Mind-Reader" Mistake
Traditionally, if you wanted to understand why these dancers were moving the way they were, you would assume they both knew exactly what the other person wanted. You'd think, "Okay, Dancer A wants to go left, and Dancer B knows Dancer A wants to go left, so they coordinate perfectly."

This is what the paper calls Level-1 Inference. It assumes everyone is on the same page, sharing a secret mental map of each other's goals.

The Problem: The "Misunderstanding" Dance
But in real life, people aren't mind-readers. Sometimes, Dancer A thinks Dancer B wants to go right, while Dancer B actually wants to go left. Because of this mix-up, they might both freeze in the middle of the floor, or worse, crash into each other.

If you use the old "Level-1" method to watch this, you would be confused. You'd see them freezing and think, "Oh, they must both want to stay still!" You would miss the real reason: they are paralyzed because they are misunderstanding each other.

The New Way (Level-2 Inference): The "Theory of Mind" Detective
This paper introduces a smarter way to watch the dance, called Level-2 Inference.

Instead of just guessing what the dancers want, this method guesses what the dancers think the other person wants. It asks:

1. What does Dancer A actually want?
2. What does Dancer A think Dancer B wants?
3. What does Dancer B actually want?
4. What does Dancer B think Dancer A wants?

By solving this "guessing game about guesses," the observer can finally explain why the dancers froze. They realize, "Ah! They aren't stuck because they want to stop; they are stuck because they are both trying to be polite to a goal the other person doesn't even have!"

The Real-World Example: The Lane Change

The authors test this with a classic driving scenario: Two cars trying to change lanes.

• The Scene: A blue car wants to move into the right lane. A red car is already there.
• The Mix-up: The blue car thinks the red car wants to stay in the right lane. The red car thinks the blue car wants to stay in the left lane.
• The Result: Both cars hesitate. They both think, "If I move, I'll hit them!" So, they both stay put, creating a traffic jam (a deadlock).

What the Old Method Sees:
It looks at the frozen cars and says, "Both drivers must want to stay in their current lanes." This is wrong. If a self-driving car used this logic, it would never try to change lanes because it thinks the other car is stubborn.

What the New Method Sees:
It looks at the frozen cars and says, "Wait, the blue car is hesitating because it thinks the red car is blocking it. But the red car is actually willing to move! The blue car is just operating on a false belief."

Why This Matters

The paper proves that figuring out these "false beliefs" is incredibly hard mathematically (it's "non-convex," which is a fancy way of saying the math landscape is full of tricky hills and valleys where it's easy to get lost).

However, the authors built a new "GPS" (an algorithm) that can navigate these tricky hills. They showed that by using this new method, we can:

1. Predict behavior better: We can see why a driver is being "weird" or "cautious" when they are actually just confused.
2. Prevent accidents: If a self-driving car realizes the human driver is hesitating because of a misunderstanding rather than a refusal, the self-driving car can take the lead and move first, breaking the deadlock.

The Big Picture

Think of this like a relationship counselor.

• Level-1 says: "You two are fighting because you both want different things."
• Level-2 says: "You two are fighting because you think the other person wants something they don't actually want. Let's fix the misunderstanding, not just the goals."

This paper gives computers the ability to be that counselor, helping them understand the messy, misunderstood world of human interaction.

Technical Summary

Here is a detailed technical summary of the paper "Level-2 Inverse Games for Inferring Agents' Estimates of Others' Objectives."

1. Problem Statement

The paper addresses a fundamental limitation in Inverse Game Theory, specifically within multi-agent interactive settings (e.g., autonomous driving, bargaining).

• The Gap: Existing "Level-1" inverse game approaches assume that while an external observer does not know the agents' objectives, the agents themselves possess complete and accurate knowledge of each other's objectives.
• The Reality: In decentralized real-world scenarios, agents often act based on misaligned or incorrect beliefs about what others want. For example, in a lane-change scenario, two cars may deadlock because each incorrectly believes the other intends to stay in its current lane, even though both actually want to change lanes.
• The Challenge: A Level-1 observer, assuming mutual knowledge, would incorrectly infer that both agents simply prefer their current lanes, leading to significant prediction errors. The paper proposes solving a Level-2 Inverse Game: inferring not only each agent's true objective ($\theta_{i,i}$) but also their estimates of other agents' objectives ($\theta_{i,-i}$).

2. Methodology

The authors propose a framework that models agents as rational actors operating within a "Theory of Mind" hierarchy (Level-2 reasoning), where each agent $i$ solves a hypothesized Nash game based on their own objective and their belief about others' objectives.

A. Mathematical Formulation

• Level-2 Parameters: For each agent $i$, the parameter set is $\Theta_i = \{\theta_{i,i}, \theta_{i,-i}\}$, where $\theta_{i,i}$ is the true objective and $\theta_{i,-i}$ represents agent $i$'s estimate of all other agents' objectives.
• Hypothesized Equilibrium: Each agent $i$ independently computes a hypothesized Local Generalized Nash Equilibrium (LGNE), denoted $(\hat{x}_i, \hat{u}_i)$, based on their parameter set $\Theta_i$.
• Inverse Problem: The observer aims to find the set of parameters $\hat{\Theta}$ that maximizes the likelihood of observed trajectories $y$. The optimization problem is:
  $$\max_{\hat{\Theta}} p(y | x, u)$$
  Subject to the constraint that the observed actions $u$ are the diagonal elements of the hypothesized LGNEs derived from $\hat{\Theta}$.

B. Theoretical Characterization

• Non-Convexity: The authors prove (Proposition 1) that the Level-2 inference problem is non-convex, even in benign Linear-Quadratic (LQ) settings. This implies that finding the global optimum is difficult, and local minima exist.
• Prediction Error Bounds: They derive upper and lower bounds on the prediction error of Level-1 inference when applied to data generated by Level-2 agents (Proposition 2). The bounds demonstrate that as the heterogeneity (mismatch) in agents' beliefs increases, the error of Level-1 inference grows significantly.

C. Algorithmic Approach

To solve the non-convex inverse problem efficiently, the authors employ a gradient-based approach:

1. MCP Transcription: They transcribe the KKT conditions of the hypothesized Nash games into a Mixed Complementarity Problem (MCP).
2. Differentiability: Using the Implicit Function Theorem, they derive the gradients of the MCP solution (the equilibrium strategies) with respect to the Level-2 parameters.
3. Optimization: They utilize a differentiable MCP solver (specifically ParametricMCPs.jl) to compute gradients and perform gradient descent to minimize the loss function $L(\hat{\Theta})$. This allows for both offline (historical data) and online (receding horizon) inference.

3. Key Contributions

1. Formal Framework: Introduced a formal mathematical model for Level-2 Inverse Dynamic Games, extending classical inverse game theory to account for agents' misaligned beliefs about one another.
2. Theoretical Proof: Proved the non-convexity of the Level-2 inference problem and established theoretical bounds showing why Level-1 methods fail when agents hold heterogeneous estimates.
3. Efficient Algorithm: Developed a gradient-based algorithm using differentiable MCPs to identify local solutions for Level-2 inverse games, enabling the recovery of complex belief structures.

4. Experimental Results

The method was evaluated on two primary scenarios:

A. Synthetic Linear-Quadratic (LQ) Games

• Setup: Agents interacted with varying degrees of belief mismatch.
• Finding: Level-2 inference successfully recovered the true parameters and belief estimates, achieving significantly lower loss values than Level-1 inference. As the heterogeneity of agents' beliefs increased, Level-1 performance degraded rapidly, while Level-2 remained robust.

B. Urban Driving (Lane Change) Scenario

• Setup: A two-vehicle lane-change scenario where agents have double-integrator dynamics and collision constraints.
• Fictitious Play: Simulations showed that mismatched beliefs (e.g., both cars thinking the other won't move) lead to deadlocks or unsafe maneuvers, whereas aligned beliefs lead to successful lane changes.
• Inference Performance:
  • Level-1: Incorrectly inferred that both agents wanted to stay in their lanes (or converged to a single shared objective), failing to explain the deadlock.
  • Level-2: Successfully inferred that Agent 1 believed Agent 2 wanted the bottom lane, and vice versa. This explained the observed deadlock behavior. The algorithm recovered the "mismatched belief" parameters ($\hat{\theta}_{i,j}$) that drove the agents' cautious behavior.

5. Significance and Impact

• Explaining "Irrational" Behavior: The framework provides a mechanism to explain observed behaviors that appear irrational or inefficient under standard game-theoretic assumptions (e.g., deadlocks, aggressive driving) by attributing them to misunderstandings rather than conflicting goals.
• Safety in Autonomous Systems: For autonomous vehicles and regulators, accurately inferring an agent's belief about others is crucial for predicting future behavior. A car that thinks another car is stationary will act differently than one that thinks the car is moving; Level-2 inference captures this nuance.
• Scalability: By leveraging differentiable MCPs and gradient descent, the approach offers a computationally feasible path to solving complex, non-convex inverse problems in continuous spaces, moving beyond discrete approximations used in previous "Level-k" reasoning literature.

In conclusion, this paper bridges the gap between theoretical game theory and real-world multi-agent interactions by acknowledging that agents often operate on flawed models of their peers, and provides the mathematical tools to infer those flawed models from data.