PaperlayerView exact revision on arXiv

Source-linked AI summary

Data-Driven Estimation in Equilibrium Using Inverse Optimization

Dimitris Bertsimas, Vishal Gupta, Ioannis Ch. Paschalidis

arXiv:1308.3397v2math.OC

TL;DR

Equilibrium primitives are often difficult to observe or estimate, even though equilibria themselves may be observable. The paper uses inverse variational inequalities to estimate these primitives from observed equilibria, proving generalization and predictive properties and illustrating the approach in demand and congestion estimation.

  • Problem

    Equilibrium-model inputs can be difficult to estimate despite directly observable equilibria, and small estimation errors can substantially affect resulting equilibria and system design.

  • Method

    The paper formulates inverse variational inequality problems and uses observed equilibria to estimate model primitives with tractable parametric and nonparametric methods.

  • Results

    The approach recovers reasonable demand and congestion functions with good generalization properties and predictive power in Nash and traffic-equilibrium applications.

  • Takeaways & Limitations

    Observed equilibria can support computationally tractable estimation of unobservable equilibrium-model primitives and meaningful predictive claims.

  • Takeaways & Limitations

    Equilibrium conditions may provide only local information about a function, leaving its global behavior unidentified even as the sample size grows.

Abstract

from arXiv · show

Equilibrium modeling is common in a variety of fields such as game theory and transportation science. The inputs for these models, however, are often difficult to estimate, while their outputs, i.e., the equilibria they are meant to describe, are often directly observable. By combining ideas from inverse optimization with the theory of variational inequalities, we develop an efficient, data-driven technique for estimating the parameters of these models from observed equilibria. We use this technique to estimate the utility functions of players in a game from their observed actions and to estimate the congestion function on a road network from traffic count data. A distinguishing feature of our approach is that it supports both parametric and \emph{nonparametric} estimation by leveraging ideas from statistical learning (kernel methods and regularization operators). In computational experiments involving Nash and Wardrop equilibria in a nonparametric setting, we find that a) we effectively estimate the unknown demand or congestion function, respectively, and b) our proposed regularization technique substantially improves the out-of-sample performance of our estimators.

1 Introduction

The paper estimates unobservable primitives of equilibrium systems from observed equilibria using an inverse variational inequality framework. It supports parametric and nonparametric estimation, with tractable optimization formulations and computational evidence of useful predictive performance.

  • Motivation: Observed equilibria provide data for estimating otherwise unobservable model primitives in games and transportation systems.The paper illustrates this idea with player utilities inferred from actions and road costs inferred from traffic counts.
  • Method: The inverse variational inequality formulation seeks a common function making observed data approximate equilibria.This extends inverse optimization from observed optimal solutions to observed equilibria.
  • Nonparametric estimation: Kernel methods convert the infinite-dimensional nonparametric inverse problem into a finite-dimensional convex quadratic optimization problem.The optimization size scales linearly with the number of observations rather than the dimension of the potentially infinite-dimensional function space.
  • Positioning: The approach is presented as complementary to structural estimation, offering fewer modeling assumptions and computational tractability for continuous problems.Structural methods may yield stronger claims when their underlying assumptions are valid.
  • Parametric estimation: Parametric formulations can be reformulated as conic optimization problems for several useful function classes.The resulting formulations are described as theoretically and numerically tractable, including for large-scale instances.
  • Results: Under mild assumptions, the estimators have generalization guarantees, and experiments recover reasonable demand and congestion functions with predictive power.The applications use Nash equilibrium demand estimation and traffic user-equilibrium congestion estimation.

2 Variational Inequalities: Background

Variational inequalities provide a common formulation for constrained optimization, Nash equilibrium, and traffic equilibrium. The paper also defines approximate VI solutions and characterizes them over conic-representable feasible sets.

  • Definitions and examples: A variational inequality VI(f, F) seeks x* in F satisfying the VI condition for a function f and feasible set F.The paper uses this framework to represent several equilibrium and optimization problems.
  • Existence and uniqueness: VI solutions need not exist or be unique without suitable assumptions on f or F.Continuity of f and convexity and compactness of F are given as sufficient conditions for existence and uniqueness.
  • Nash equilibrium: Nash equilibrium can be represented as a variational inequality over the Cartesian product of players’ strategy sets.The VI characterization accommodates constrained strategy sets, whereas a gradient-zero condition assumes interior best responses.
  • Wardrop equilibrium: Wardrop equilibrium is a solution to VI(c, F), where used paths have no greater cost than alternative paths for the same origin-destination pair.Arc costs may depend on flows across the network because of interdependencies among arcs.
  • Approximate equilibria: An ε-approximate VI solution generalizes ε-optimality in constrained convex optimization through a bounded primal-gap condition.The paper also relates ε-approximate and δ-near solutions under strong monotonicity.
  • Conic representability: The paper assumes feasible sets can be represented by conic inequalities and satisfy a Slater condition to characterize approximate solutions.Polyhedra arise with the nonnegative orthant, while other cones can represent more complex sets such as intersections of ellipsoids.

3 The Inverse Variational Inequality Problem

The paper formulates inverse equilibrium estimation through variational inequalities, using observed approximate equilibria to estimate a common function or its parametric representation. The framework accommodates multiple equilibria and boundary observations, while parametric tractability depends on the function parameterization.

  • 3.1 Problem Formulation: The inverse VI problem estimates a common function f so observed x_j are approximate solutions across constrained equilibrium problems.The feasible sets are defined by linear equalities and convex constraints, with a Slater condition assumed for each observation.
  • 3.2 Parametric Estimation: Parametric estimation restricts f to a family f(x; θ) indexed by θ in a compact parameter set and reformulates the inverse problem as an optimization problem.The reformulation follows from the VI characterization and introduces auxiliary variables for the observed equilibria.
  • 3.2 Parametric Estimation: The framework remains valid when the model generates multiple distinct equilibria or when observed and induced equilibria lie on the feasible-set boundary.These properties distinguish the approach from methods requiring equilibrium uniqueness or relative-interior solutions.
  • 3.2 Parametric Estimation: When f depends linearly on parameters through arbitrary nonlinear basis functions, the parametric formulation becomes a conic optimization problem.With the nonnegative orthant it becomes linear optimization; with the second-order cone it becomes a second-order cone problem.
  • 3.3 Application: Demand Estimation under Bertrand-Nash Competition: The Bertrand–Nash application estimates demand functions so observed prices approximately satisfy Nash equilibrium conditions under bounded price constraints.The formulation can use linear or multinomial-logit demand specifications, although the latter produces a non-convex optimization problem.
  • 3.3 Application: Demand Estimation under Bertrand-Nash Competition: The paper notes that non-convex formulations can be numerically challenging and may scale poorly.This limitation arises for the multinomial-logit specification rather than from the general inverse VI formulation.

4 Kernel Methods: Background

The paper uses reproducing kernel Hilbert spaces to represent broad classes of functions and to encode kernel-dependent notions of smoothness. Kernel evaluation and norm structure make nonparametric estimation computationally workable.

  • Kernel Methods in the Paper: The nonparametric inverse VI method uses kernels to seek the smoothest function reconciling observed data approximately with equilibrium conditions.The paper relates this use to spline interpolation and regularization rather than primarily to feature extraction.
  • Kernel Definitions and Examples: A kernel is a symmetric positive-semidefinite function, with linear, polynomial, and Gaussian kernels providing common examples.These kernels induce different function spaces, including finite-dimensional linear or polynomial spaces and an infinite-dimensional Gaussian-kernel space.
  • RKHS Construction: The RKHS construction begins with finite linear combinations of kernel sections k_x and extends them by completion.The resulting space H is obtained from H_0 by extending the scalar product and norm by continuity.
  • RKHS Construction: The reproducing property connects the inner product to function evaluation, making H a Reproducing Kernel Hilbert Space.The property holds throughout H and is the central structural feature used by kernel methods.
  • Smoothness and Norms: The RKHS norm encodes smoothness, with small norm penalizing rapid variation according to the selected kernel.For linear kernels it corresponds to a small coefficient norm and gradient; for Gaussian kernels it suppresses high-frequency behavior.

5 The Inverse Variational Inequality Problem: A Nonparametric Approach

The nonparametric inverse VI approach selects a minimum-norm RKHS function that approximately reconciles observed equilibria, then reduces the infinite-dimensional problem to finite-dimensional convex optimization. The same framework estimates congestion functions from traffic counts under a structured network cost model.

  • 5.1 Kernel Based Formulation: Nonparametric inverse VI estimation is ill-posed because many functions may exactly reconcile a limited set of equilibrium observations.The method therefore needs a principled criterion for choosing among multiple compatible functions.
  • 5.1 Kernel Based Formulation: The method selects the minimum H-norm function among those that approximately reconcile the data.The H-norm imposes kernel-dependent smoothness and supports generalization, while the approximation requirement allows controlled equilibrium error.
  • 5.1 Kernel Based Formulation: The RKHS optimization has an optimal finite kernel expansion whose evaluation points are exactly the observed data points.This representation converts optimization over an infinite-dimensional function space into a finite-dimensional optimization problem.
  • 5.1 Kernel Based Formulation: The resulting finite-dimensional problem is a convex quadratic optimization problem with tractable numerical structure.The kernel matrix is positive semidefinite, and block structure can further simplify computation.
  • 5.1 Kernel Based Formulation: Compared with the parametric approach, the nonparametric formulation is always convex but offers less control over the specific form of f.The tradeoff is between parametric form control and nonparametric tractability.
  • 5.2 Application: Traffic Equilibrium: For traffic estimation, the paper estimates a nondecreasing congestion function g from observed flows while using known arc characteristics in the cost model.The cost is assumed to have the form c_a(x_a)=c^0_a g(x_a/m_a), and monotonicity is enforced on observed arcs.
  • 5.2 Application: Traffic Equilibrium: The traffic formulation exploits low-rank kernel matrices and decomposition into shortest-path subproblems to solve large network instances efficiently.The optimization decouples by origin-destination pair and observation network for fixed kernel coefficients.

6 Extensions

The section extends the estimation framework with finite representations, priors, semi-parametric models, ambiguity sets, and analysis of model multiplicity. It also identifies cases involving partial derivatives where the main finite-representation result does not apply.

  • Theorem 4 extends to optimization problems depending on component norms and function evaluations at finitely many points, with objectives nondecreasing in those norms.
  • The resulting finite representation supports additional estimation problems and facilitates inference.
  • Prior information can be incorporated by decomposing the VI function as f = f0 + g, where g is believed to be small.
  • Semi-parametric estimation represents the VI function as a parametric component plus a nonparametric RKHS component.
  • Partial-derivative dependence makes Theorem 4 inapplicable, and extending the techniques to this case remains open.
  • Ambiguity sets characterize functions that reconcile observed equilibria, enabling upper and lower envelopes and comparisons with parametric alternatives.

7 Generalization Guarantees

The section establishes generalization guarantees for parametric and nonparametric estimators under sampling and regularity assumptions. These guarantees relate empirical approximation error to performance on new equilibrium data, while their usefulness depends on model fit and may require cross-validation in small samples.

  • The analysis proves generalization guarantees intended to make performance on future data similar to observed performance.
  • The guarantees assume i.i.d. data, feasible sets satisfying a Slater condition, observed equilibria lying in those sets, and bounded feasible regions.
  • Theorem 6 provides a high-probability bound for the convex parametric problem with the infinity norm, using the tail probability β(α).
  • β(α) converges exponentially fast in N, but depends strongly on the dimension of θ; ℓ1 regularization can improve the bound by reducing effective dimension.
  • The guarantees do not ensure small training error, which occurs only when a VI adequately models the system.
  • The prediction guarantee in Theorem 8 requires strong monotonicity and states that solutions using the fitted function predict future system behavior when training error is small.
  • Because complexity-based bounds may be loose in small samples, cross-validation or bootstrapping is recommended when computationally feasible.

8 Computational Experiments

Computational experiments apply the proposed estimators to Bertrand–Nash demand and Wardrop congestion functions. The results show useful generalization, while ambiguity sets reveal when equilibrium data do not identify a unique function.

  • Experimental scope: The experiments cover Bertrand–Nash demand estimation and Wardrop congestion-function estimation.The study includes full-information and unobserved-effects Bertrand–Nash settings, plus a Wardrop-equilibrium traffic example.
  • Bertrand–Nash equilibrium: Under full information and a correctly specified parametric form, the optimization uniquely recovers the true marginal revenue functions with residual ε = 0.The experiment assumes the demand-function form is known while estimating its parameters.
  • Bertrand–Nash equilibrium: Nonparametric fits can exactly reconcile equilibrium data while differing from the true function, because equilibrium conditions provide only local information near the revenue minimum.The ambiguity set contains multiple functions consistent with the observations, even when the fitted function is not the true one.
  • Bertrand–Nash equilibrium: The ambiguity-set analysis warns that a unique parametric fit can support unwarranted claims about marginal-revenue slopes or demand functional form.Any function in the ambiguity set may have generated the data, so those additional claims are not supported by the observations alone.
  • Bertrand–Nash equilibrium: The unobserved-effects Bertrand–Nash estimator has mean out-of-sample prediction error (−.002, 0.02) with standard deviation (.048, .047).Its estimated probability of exceeding the training residual threshold was .025, below the theorem-based .21 bound.
  • Wardrop equilibrium: For Wardrop estimation, the mean relative approximation error is 6.5% and the mean relative predictive error is about 5.5%.The evaluation uses an out-of-sample test set of Nout = 500 and normalized approximation and flow-prediction errors.

9 Conclusion

The paper presents a computationally tractable inverse-variational-inequality framework for estimating equilibrium model primitives. It proves generalization and predictive properties and illustrates them through Nash-demand and user-equilibrium congestion applications.

  • Conclusion: The paper proposes a computationally tractable estimation technique based on an inverse variational inequality formulation.The framework targets estimation from systems presumed to be in equilibrium.
  • Conclusion: The estimators are designed to provide good generalization guarantees and predictive power.These properties are stated as theoretical results of the proposed approach.
  • Conclusion: Two applications illustrate the framework: demand estimation under Nash equilibrium and congestion-function estimation under user equilibrium.The applications demonstrate the method in game-theoretic and transportation settings.
  • Conclusion: The results suggest that the technique can model systems presumed to be in equilibrium and make meaningful predictive claims about them.This is the paper’s stated overall conclusion.

A Omitted Proofs

The omitted proofs establish finite kernel representations, optimization equivalences, and statistical guarantees for the inverse-variational-inequality estimators.

  • Theorem 4: The proof of Theorem 4 uses a finite-dimensional span of kernel evaluations to represent an optimal estimator.The relevant function components lie in the span of kernel functions evaluated at observed samples.
  • Theorem 5: Theorem 5’s proof shows feasibility and objective-value equivalence between the function-space problem and its finite representation.A feasible coefficient vector constructs a feasible function, and conversely an optimal function yields feasible coefficients.
  • Theorem 6: Theorem 6 derives out-of-sample approximate-equilibrium guarantees by relating the estimator to a randomized uncertain convex program.The proof interprets violation probability as the probability that a new observation is not a zN-approximate equilibrium.
  • Theorem 7: Theorem 7 bounds expected approximation error using uniform concentration through Rademacher complexity.The proof applies a uniform empirical-to-true-expectation bound to the class of equilibrium residual functions.
  • Technical remark: The proof appendix notes that the constants in one concentration lemma are not tight, but retains them for simplicity.The stated constant can be reduced from 8 to 2 by modifying the proof.
  • Theorem 8: Theorem 8 converts residual bounds into guarantees that a new point lies near a solution of the fitted variational inequality.The argument uses Theorem 6 or Theorem 7 to bound the probability of a residual exceeding the training threshold.

B Casting Structural Estimation as an Inverse Variational Inequality

The paper recasts structural estimation as an inverse variational inequality by finding de-noised data and parameters that satisfy equilibrium conditions. This formulation accommodates noisy and partially unobserved inputs but can be computationally difficult.

  • Problem formulation: The structural-estimation formulation assumes a true parameter θ* generates equilibrium solutions, while observed inputs are noisy versions of the true parameters.The noise is modeled through i.i.d. perturbations of the observed equilibrium data.
  • Problem formulation: The estimator minimizes a norm of perturbations subject to de-noised data constituting perfect equilibria for the fitted θ.The formulation can treat some components of x as unobserved by making them optimization variables.
  • Relation to structural estimation: When equilibria lie in the strict interior of the feasible region, the formulation is equivalent to a weighted least-squares problem for f(x*) = 0.Interior variational-inequality conditions reduce to the equilibrium equations used in the structural formulation.
  • Relation to structural estimation: The formulation connects to structural-estimation methods that minimize perturbations needed to satisfy structural equations and additional orthogonality or GMM constraints.The equivalence extends when corresponding preprocessing, instrument constraints, and norm choices are incorporated.
  • Computational comparison: Compared with the paper’s inverse-VI formulation, the structural-estimation problem contains non-convex bilinear terms and is expected to be significantly harder numerically.Its complexity depends on how f depends jointly on x and θ, rather than only on θ.
  • Computational comparison: The paper’s inverse-VI framework naturally generalizes to nonparametric estimation, unlike the restricted structural formulation described here.This distinction is presented as a central computational and modeling advantage of the proposed approach.

C Omitted Formulations

The omitted formulations specify parametric and nonparametric estimation variants, including regularized objectives, functional definitions, monotonicity constraints, and normalization conditions.

  • Parametric formulation details: The Section 8.1 parametric formulation uses median observations to fix other variables, minimum observed prices, and constraints on fitted functions.The supplied formulation states that the optimization is linear and that additional equations enforce price monotonicity and normalization.
  • Parametric formulation details: The fitted functions are constrained to be non-decreasing in each firm’s own price and normalized to equal the true functions at one point for visual comparison.Any suitable normalization can be used in principle.
  • C.1 Formulation from Section 8.1: The nonparametric formulation replaces parametric functions M1(·, θ1) and M2(·, θ2) with functions in H and adds Hilbert-space regularization.Its objective is ||ϵ||1 + λ(||M1||H + ||M2||H).
  • C.1 Formulation from Section 8.1: The nonparametric optimization can be rewritten as a convex quadratic program using Theorem 4 and the discussion in Section 6.
  • C.2 Formulation from Section 8.2: The parametric formulation replaces the objective with ||ϵ||∞ + λ(||θ1||1 + ||θ2||1) and defines M1 and M2 using Eq. (33).
  • C.2 Formulation from Section 8.2: The nonparametric formulation in Section 8.2 is identical to the nonparametric formulation of the previous section.
Loading 1308.3397v2…