Abstract
Inverse Game Theory aims to recover the underlying utility functions of players from observed equilibrium behaviors. This task is traditionally hindered by issues of identifiability—where multiple utility functions explain the same data—and computational scalability in multi-player settings. This paper presents a novel framework that reformulates the problem as a Variational Inequality (VI) and identifies the "incenter" of the consistent parameter set as the most robust estimate. By converting the problem into an unconstrained loss minimization solvable via Mirror Descent, the authors achieve state-of-the-art accuracy and scalability across diverse economic and traffic models.
Introduction: The Challenge of Inverse Modeling
In standard game theory, researchers predict outcomes (equilibria) based on known player preferences. Inverse Game Theory reverses this logic: given observations of how agents interact in various contexts, can we deduce what they value? This is critical for applications ranging from optimizing market mechanisms to designing efficient urban transportation policies.
Two primary obstacles exist:
- Identifiability: Observed behaviors often lack a unique "best-fit" utility function.
- Scalability: Traditional constrained optimization approaches suffer from a combinatorial explosion of constraints as the number of players or observations grows, often leading to computational intractability.
Methodology: Geometry and Variational Inequalities
The core innovation of this work is the Incenter-Based Approach, which treats parameter estimation as a geometric search for robustness.
The Incenter Concept
Instead of selecting any arbitrary parameter vector $\vartheta$ that satisfies the equilibrium conditions, the authors seek the incenter. Geometrically, the incenter is the point furthest from the boundaries of the set of consistent parameters. This point represents the most robust estimate, as it is least susceptible to noise or minor deviations in player behavior (e.g., bounded rationality).
Variational Inequality Reformulation
To make this search mathematically tractable, the authors reformulate Nash Equilibrium conditions into a Variational Inequality (VI). This allows them to define a "consistent set" of parameters rigorously.
Scalable Optimization
To handle large-scale data, the authors transform the hard constraints of the incenter problem into an unconstrained loss minimization problem. This enables the use of Mirror Descent (I-MD), a first-order optimization algorithm that scales efficiently with the number of players and observations. For scenarios with known structural priors (e.g., monotonicity), they further extend the framework using Semidefinite Programming (I-SDP).
Experimental Evaluation
The framework was tested on three distinct environments:
- Bertrand-Nash Price Competition: Firms competing on price.
- Aggregative Games (Cournot Competition): Firms competing on production quantity.
- Network Traffic Games: Estimating travel latency costs on the Sioux Falls network (24 nodes, 76 links).
Key Results and Insights
The proposed methods, I-MD and I-SDP, consistently outperformed previous state-of-the-art approaches in both accuracy and computational efficiency.
- Robustness and Accuracy: The incenter-based approach achieved significantly lower estimation errors for utility parameters. By focusing on the geometric center of the feasible region, the model remains valid even when players exhibit "noisy" or near-equilibrium behavior.
- Computational Scalability: On the Sioux Falls dataset, where previous methods became intractable due to the infinite action space, the I-MD algorithm converged rapidly.
- Effectiveness of Priors: The inclusion of structural priors through I-SDP led to faster convergence and even lower error rates, demonstrating the value of incorporating domain knowledge into the inverse modeling process.
Conclusion and Future Directions
By moving from constrained optimization to a geometric loss-function-based approach, this paper makes inverse game theory viable for high-dimensional, real-world problems. Future work will focus on establishing formal sample complexity bounds and extending the framework to handle highly non-linear utility functions, such as those represented by deep neural networks. Integrating these estimated utilities directly into predictive models for unseen contexts remains a promising next step.
Summary updated