Inverse Game Theory: An Incenter-Based Approach

The strongest honest case is a finite-type nonatomic inverse-equilibrium problem. I would not claim that this paper contains a formal \(P\), NP-hardness, W[1]-hardness, or FPT theorem: it does not. Its strongest named computational result is Theorem 1, “Incenter Computation,” proved by the authors, with the proof placed in the supplement. The theorem shows that finding the incenter of the consistent-parameter cone is equivalent to a convex optimization problem with one constraint for every possible deviation.

My lead mirror is Continuum Incenter Inverse-VI.

Let \(T=\{1,\ldots,\tau\}\) be finitely many agent types and let \(\mu_t\) be the mass of type \(t\), with \(\sum_t\mu_t=1\). Think of millions of charging agents, producers, or traffic users grouped into a small number of exact technology, location, demand, and preference classes. Agents of the same type have the same feasible action interval \(X_t=[\ell_t,u_t]\), utility features, costs, and parameters. Thus \(n\gg\tau\), and the population is represented by \(\mu\), not by \(n\) named players.

In context \(s^j\), a type-\(t\) agent chooses a scalar action \(a_t\in X_t\). Its utility is \(U_t(a_t,z,s^j;\theta_t)=\langle\theta_t,\phi_t(a_t,z,s^j)\rangle\), where \(z=\sum_t\mu_ta_t\) is the population aggregate and the utility is concave in \(a_t\). The observations are type-level equilibrium actions \(\hat a_t^j\), rather than the actions of every individual agent. Let \(\hat z^j=\sum_t\mu_t\hat a_t^j\).

The instance consists of \(T\), rational masses \(\mu\), the action intervals, the contexts \(s^1,\ldots,s^N\), the observed profiles \(\hat a^1,\ldots,\hat a^N\), and the feature maps \(\phi_t\). Define the consistent parameter set by

\[ \mathcal C_\mu= \left\{ \vartheta=(\theta_t)_{t\in T}: \sum_{t\in T}\mu_t \left\langle \theta_t, \partial_a\phi_t(\hat a_t^j,\hat z^j,s^j) \right\rangle (a_t-\hat a_t^j)\le 0 \ \text{for every }a\in\prod_tX_t,\ j\in[N] \right\}. \]

The continuous problem is to output an \(\varepsilon\)-optimal angular incenter of \(\mathcal C_\mu\): a parameter direction \(\vartheta\) that maximizes its minimum angle from the boundary of the consistent set, exactly in the sense of Definition 2 and Theorem 1 of the paper. The instance carries the promise that \(\mathcal C_\mu\) has nonempty interior. If the data are inconsistent, the corresponding loss-minimization version from equation (8) is the natural extension.

This is genuinely a population continuization. The mass vector \(\mu\) determines the aggregate state and the equilibrium constraints; the individual identities disappear because agents of one type are interchangeable. A finite \(n\)-agent instance with \(n_t\) copies of type \(t\) maps downward to \(\mu_t=n_t/n\), while the continuum problem is the high-multiplicity limit of that family. It is not merely continuous because actions are real-valued: the population itself is the continuous object.

The mirror is plausible because it preserves the paper’s central question. The authors observe equilibrium behavior under contexts and infer utility parameters that rationalize it. The only substantive change is replacing a long list of named but interchangeable players by masses of player types. The scalar-action restriction is also not artificial: their own aggregative-game and Cournot examples use scalar decisions. A large fleet, producer population, or traffic-user population with repeated type classes is a natural regime in which the authors would likely recognize the model as their inverse variational-inequality problem.

I would expect this finite-type scalar-action version to be Class A. At each observation, the derivative is linear in \(\vartheta\). Since each \(X_t\) is an interval, the universal deviation condition reduces to endpoint deviations, producing only \(O(N\tau)\) linear constraints. The incenter can therefore be computed by the corresponding finite convex or second-order-cone formulation. The relevant complexity would be polynomial in \(\tau\), the parameter dimension, the number of contexts, and the input encoding length, rather than in the number \(n\) of agents.

The main questions this generates are whether the discrete-to-continuum approximation admits additive parameter or equilibrium guarantees; whether noisy and \(\varepsilon\)-equilibrium observations have sample-complexity bounds; how to handle multiple equilibria within a type; and whether the result survives when \(T\) itself is continuous. Vector-valued actions and unrestricted network-routing deviations would also expose a pricing problem analogous to the paper’s infinite-constraint difficulty.

I would not use Lemma 1 or Proposition 1 as additional anchors. They are useful SDP and KKT specializations, but neither gives a complexity classification, and adding them would mostly repeat the same mirror. Strictly speaking, therefore, the paper has no named result of the form “this problem is in \(P\)” or “this problem is NP-hard.” The positive case rests on Theorem 1’s named convex reformulation, not on a theorem proving polynomial-time solvability.

The weakest point is that a nonatomic inverse-VI model is not literally the same strategic environment as the paper’s finite-player Nash game: an individual’s effect on the aggregate vanishes, and type-level equilibrium observations discard within-type heterogeneity. If the authors regard player-specific strategic externalities as essential, they may reject the mirror as a mean-field reformulation rather than their problem. The answer is that the paper already works through variational inequalities and aggregative and traffic games, and the proposed regime preserves their inverse-equilibrium object while making the high-multiplicity assumption explicit. Still, that modelling transition—not computational tractability—is the mirror’s real vulnerability.