Research map / Learning theory and algorithms / Submodular and game algorithms
Bootstrapping Fisher Market Equilibrium and First-Price Pacing Equilibrium
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Develops statistically valid bootstrap procedures for linear Fisher market equilibria and first-price pacing equilibria, including a new characterization of FPPE asymptotics without strict complementarity and a bootstrap for FPPE without degenerate buyers.
Problem
Statistical inference (confidence intervals) for equilibrium quantities in linear Fisher markets and first-price pacing equilibria from a single observed market, where standard bootstrap can fail due to equilibrium constraints.
Approach
Bootstrap the Eisenberg-Gale convex program (or its quadratic approximation) using exchangeable, numerical, and proximal bootstrap weights; for FPPE with constraints, propose a projected quadratic-program bootstrap that removes strict complementarity by restricting to estimated unpaced buyers, justified via epi-convergence and weak convergence theory.
Key results
- Finite-sample FPPE distribution is well approximated by the bootstrap distribution from a single FPPE instance when the bootstrap stepsize is chosen appropriately (synthetic 8-buyer, 100-item experiment).
- For the iPinYou semi-real experiment, with d in [0.2, 0.3] the 95% bootstrap confidence interval for the sum of pacing multipliers achieves near-nominal finite-sample coverage.
- The standard multinomial bootstrap is shown theoretically to fail to consistently estimate the FPPE limit distribution in a one-buyer example.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the proposed bootstrap with an appropriate stepsize | FPPE with no degenerate buyers · Synthetic FPPE experiments | distributional approximation | Helped |
| increase the bootstrap stepsize too much (d too small) (ablation) | Proposed FPPE bootstrap · Synthetic FPPE experiments | distributional approximation | Hurt |
| use the proposed bootstrap with d in [0.2, 0.3] | FPPE confidence intervals · iPinYou-based semi-real experiments | coverage rate | Helped |
| use a too-small bootstrap stepsize (d = 0.10 or 0.05) (ablation) | Proposed FPPE bootstrap · iPinYou-based semi-real experiments | coverage rate | Mixed |
| use a large bootstrap stepsize (d) (ablation) | Proposed FPPE bootstrap · iPinYou-based semi-real experiments | coverage rate | Hurt |
| use the standard multinomial bootstrap | FPPE · One-buyer FPPE | bootstrap consistency | Hurt |
Surprising findings
- The standard multinomial bootstrap fails for FPPE in a one-buyer example, with the bootstrap limit differing from the true limit distribution.
- Too small a bootstrap stepsize exponent (d=0.10 or 0.05) causes over-coverage, while too large a value causes under-coverage.
Limitations
- Bootstrap for general FPPE with degenerate buyers is only given as a confidence region via test inversion, which is computationally costly.
- Requires twice differentiability of the population EG objective and a smoothing/stepsize choice; Hessian estimation via finite differences is sensitive to stepsize.
- Assumes stationary i.i.d. input data.
Experimental setup
Datasets: iPinYou
Benchmarks: iPinYou semi-real auction data
Metrics: bootstrap distribution vs. finite-sample distribution confidence interval coverage rate interval width
Baselines: multinomial bootstrap
Builds on: Eisenberg-Gale convex program proximal bootstrap numerical bootstrap exchangeable bootstrap
Closest papers by meaning
- Statistical Inference and A/B Testing for First-Price Pacing Equilibria (ICML 2023 · similarity 0.89)
- Fast and Interpretable Dynamics for Fisher Markets via Block-Coordinate Updates (AAAI 2023 · similarity 0.88)
- On the Convergence of Tâtonnement for Linear Fisher Markets (AAAI 2025 · similarity 0.86)
- Interference Among First-Price Pacing Equilibria: A Bias and Variance Analysis (ICLR 2025 · similarity 0.83)
- Beyond Monotonicity: On the Convergence of Learning Algorithms in Standard Auction Games (AAAI 2025 · similarity 0.83)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.