Research map / Learning theory and algorithms / Submodular and game algorithms
On the Proximity of Markets with Integral Equilibria
Siddharth Barman, Sanath Kumar Krishnamurthy
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Round a Fisher-market equilibrium to an integral allocation while keeping prices fixed and adjusting budgets | Fisher markets with additive valuations · Random Fisher markets, n=2, m=10 through n=64, m=320 | Mean run-time: 1.104 sec -> 0.0002 sec; 1.621 sec -> 0.0005 sec; 2.067 sec -> 0.0007 sec; 2.869 sec -> 0.002 sec; 5.593 sec -> 0.007 se | Improved |
| Round the equilibrium allocation using the proposed algorithm | Equal-income random Fisher markets · Random instances across the reported agent counts | Number of envy-free allocations: 99, 86, 95, 99, 98, 100 out of 100 | Mixed |
| Use equilibrium rounding to produce an integral allocation | Additive fair-division instances · Indivisible goods; general theorem | Proportionality up to one good and fractional Pareto efficiency | Improved |
| Use equilibrium rounding to produce an integral allocation | Additive fair-division instances · Indivisible goods; general theorem | EF_1^1 and fractional Pareto efficiency | Improved |
Closest papers by meaning
- Fair Division with Market Values (AAAI 2025 · similarity 0.90)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.89)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.89)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.88)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.88)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.88)
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.
