arxiv: 2605.12040 · v1 · submitted 2026-05-12 · 💻 cs.GT

Recognition: no theorem link

Position Auctions with a Capacity Constraint

Eleni Batziou , Georgios Birmpas , Georgios Chionas , Piotr Krysta

Authors on Pith no claims yet

Pith reviewed 2026-05-13 03:47 UTC · model grok-4.3

classification 💻 cs.GT

keywords position auctionscapacity constrainttruthful mechanismapproximation algorithmsponsored searchmatching with constraintsmechanism designlocal improvements

0 comments

The pith

A mechanism for capacity-constrained position auctions combines density ordering with local improvements to achieve the first truthful constant-factor approximation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies sponsored search where ads come in different sizes and the total space available is limited. It formulates the problem as a matching task with a global capacity constraint and designs an allocation rule that begins with a density-based ranking of ads then performs targeted swaps to improve total welfare without breaking the space limit. A small randomization step turns the rule into a universally truthful mechanism that still guarantees constant-factor approximation to the best possible welfare. This matters for modern ad platforms because ignoring ad length leads to either wasted space or poor value extraction from advertisers. If the analysis holds, auction designers gain a practical way to run truthful auctions over variable-size inventory while losing only a bounded amount of efficiency.

Core claim

We formulate position auctions with heterogeneous ad sizes as a matching problem subject to a global capacity constraint. Our allocation rule augments a density-based ordering of advertisers with capacity-aware local improvements that reassign ads to raise welfare while respecting the space limit. When applied to single-parameter agents with position-dependent click-through rates, a minor modification produces a universally truthful randomized mechanism that retains the constant-factor approximation guarantee. This constitutes the first truthful constant-approximation mechanism for this variant of capacity-constrained matching.

What carries the argument

An allocation rule that starts from a density-based ordering and then applies capacity-aware local improvements (re-allocations that increase welfare without violating the global space constraint).

If this is right

Welfare is guaranteed to be within a constant factor of the optimum even when ads occupy different amounts of space.
The same rule, with one randomization step, becomes universally truthful while preserving the approximation guarantee.
The approach directly applies to sponsored search formats that allow variable-length creative units.
Local re-allocations can be performed efficiently enough to respect real-time bidding constraints.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Platforms could deploy the rule to manage mixed text, image, and video ads without manual size filtering.
The local-improvement idea may transfer to other online matching problems that combine value maximization with packing constraints.
Testing the realized approximation ratio on historical auction logs would reveal how tight the constant is in practice.
Extending the model to multi-parameter settings would require new techniques to maintain truthfulness.

Load-bearing premise

The guarantees assume single-parameter agents whose values depend only on which position they receive and click-through rates that depend only on position.

What would settle it

An explicit instance of advertisers, ad sizes, values, and positions where the mechanism's welfare is less than 1/4 of the optimal welfare under the capacity constraint.

Figures

Figures reproduced from arXiv: 2605.12040 by Eleni Batziou, Georgios Birmpas, Georgios Chionas, Piotr Krysta.

**Figure 1.** Figure 1: An instance where max(G(rv), G(rd)) results in a linear approximation. For any sufficiently small parameter ϵ ≤ 1/k, the total welfare of max(G(rd), G(rv)) is O(k). Hence max(G(rd), G(rv)) = Θ(k) and the approximation ratio is Θ(k 2 )/Θ(k) = Θ(k), matching the upper bound asymptotically. See also [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗

read the original abstract

Sponsored search auctions are commonly modeled as an assignment of a fixed set of slots (positions) to a set of advertisers, with welfare maximization being reducible to a standard matching problem. Motivated by modern ad formats, we study a richer variant of the classical position auctions model, in which ads have heterogeneous sizes and the platform must jointly select and assign a subset of ads to positions subject to a global space constraint. We formulate this as a matching problem with a capacity constraint, and propose an algorithmic technique that goes beyond simple greedy methods while achieving constant factor approximation guarantees. Our allocation rule augments density-based ordering with capacity-aware local improvements, which allow for re-allocations that improve welfare, while respecting the capacity constraint. Applied in the context of position auctions, we analyze this mechanism under the assumption of single-parameter agents and position-dependent click-through-rates (CTRs). We show that a minor modification to our approach yields a universally truthful randomized mechanism with a constant factor approximation guarantee. To the best of our knowledge, this is the first truthful constant-approximation mechanism for this variant of capacity-constrained matching.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a plausible first constant-approx truthful mechanism for position auctions with heterogeneous ad sizes under capacity, but the local-improvement step's monotonicity after the minor randomized tweak is the part that still needs verification.

read the letter

The main point is that the authors give what they claim is the first constant-approximation truthful mechanism for position auctions with heterogeneous ad sizes and a global capacity constraint. They do this by combining density ordering with local improvements that reallocate to respect the space limit. The approach works by first ordering ads by density, then applying capacity-aware swaps or reassignments to improve welfare without violating the total size. This goes beyond simple greedy and handles the richer model motivated by modern ad formats. When ad sizes are the same it falls back to standard matching, which checks out. They then apply a minor randomized modification to get a universally truthful mechanism while keeping the constant factor. This is useful because it addresses a practical issue in sponsored search where ads take different amounts of space. The technique is new enough in this context and the claims are self-contained without relying on fitted parameters. The potential issue is whether the local improvements preserve the monotonicity needed for truthfulness. As the stress test notes, a bid increase might change which improvements are applied, breaking the non-decreasing allocation probability. The paper says the minor modification fixes this, but the abstract does not spell out the argument or show that the approximation ratio holds after randomization. If the full version has a detailed proof that the modification works, the result is fine; if not, that step needs more work. The math and citations look standard for the area, with no red flags in the abstract. This paper is for people working on mechanism design for combinatorial auctions and ad allocation. A reader who knows the classic position auction results will see the extension clearly. It deserves a serious referee because the problem is relevant and the local improvement idea could be of broader interest, though the editor should flag the truthfulness details for close checking. I would bring this to a reading group to go over the proof of the randomized mechanism.

Referee Report

1 major / 1 minor

Summary. The paper studies position auctions with heterogeneous ad sizes subject to a global capacity constraint, formulating it as a matching problem. It proposes an allocation rule that augments density-based ordering with capacity-aware local improvements to obtain constant-factor welfare approximation. For single-parameter agents with position-dependent CTRs, a minor modification is claimed to produce a universally truthful randomized mechanism with the same guarantee, asserted to be the first such result.

Significance. If the constant-factor guarantee and the truthfulness of the modified mechanism both hold, this would be a meaningful extension of position-auction mechanism design to more realistic ad formats that incorporate size heterogeneity and space limits. The algorithmic idea of combining density ordering with targeted local re-allocations could prove useful for other constrained assignment settings in algorithmic mechanism design.

major comments (1)

[Abstract and mechanism description] The central claim requires a universally truthful mechanism. The allocation augments density ordering with capacity-aware local improvements; the skeptic correctly notes that such re-allocations can violate monotonicity of allocation probabilities in an agent's bid. The abstract states only that a 'minor modification' restores universal truthfulness, but no explicit argument is supplied showing that the modification (e.g., randomization over improvement orders) preserves monotonicity while retaining the constant welfare ratio. This step is load-bearing for the mechanism guarantee and must be verified with a concrete proof or counterexample check.

minor comments (1)

[Abstract] The abstract asserts constant-factor guarantees without stating the specific ratio or sketching the proof; adding a one-sentence outline would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the thorough review and for identifying the need for a more explicit treatment of universal truthfulness. We address the major comment below and will strengthen the manuscript accordingly.

read point-by-point responses

Referee: [Abstract and mechanism description] The central claim requires a universally truthful mechanism. The allocation augments density ordering with capacity-aware local improvements; the skeptic correctly notes that such re-allocations can violate monotonicity of allocation probabilities in an agent's bid. The abstract states only that a 'minor modification' restores universal truthfulness, but no explicit argument is supplied showing that the modification (e.g., randomization over improvement orders) preserves monotonicity while retaining the constant welfare ratio. This step is load-bearing for the mechanism guarantee and must be verified with a concrete proof or counterexample check.

Authors: We agree that the current version supplies only a high-level statement that a minor modification yields universal truthfulness and does not contain a self-contained proof that randomization over improvement orders preserves monotonicity. In the revision we will add a dedicated subsection that (i) formally defines the randomized procedure (sampling a random order of candidate local swaps), (ii) proves that each agent's allocation probability is non-decreasing in its bid by showing that any bid increase can only add feasible improving swaps without removing previously feasible ones, and (iii) verifies that the same constant-factor welfare guarantee is retained because every realized allocation remains a feasible capacity-respecting matching whose welfare is at least as high as the density-ordered baseline. We will also include a short counter-example illustrating why the deterministic local-improvement rule alone can violate monotonicity, thereby motivating the randomization. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algorithmic construction is self-contained

full rationale

The paper proposes a density-ordering allocation augmented by capacity-aware local improvements for constant-factor welfare approximation in capacity-constrained position auctions. It then claims a minor modification produces a universally truthful randomized mechanism. No load-bearing step reduces by construction to a fitted parameter, self-referential definition, or prior self-citation chain. The derivation of the approximation ratio and the truthfulness modification are presented as independent algorithmic arguments rather than renamings or ansatzes imported from the authors' own prior work. This matches the default case of a self-contained mechanism-design paper with no detectable circular reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard single-parameter domain assumptions and position-dependent CTRs common in the literature; no new free parameters, invented entities, or ad-hoc axioms are introduced beyond the capacity constraint itself.

axioms (2)

domain assumption Single-parameter agents
Standard assumption for designing truthful mechanisms in auction settings; invoked when analyzing the randomized mechanism.
domain assumption Position-dependent click-through rates
Common modeling choice in position auction literature; used to define welfare.

pith-pipeline@v0.9.0 · 5498 in / 1276 out tokens · 86554 ms · 2026-05-13T03:47:43.258859+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

Hal R. Varian. Position auctions.International Journal of Industrial Organization, 25(6):1163–1178, 2007

work page 2007
[2]

Internet advertising and the generalized second- price auction: Selling billions of dollars worth of keywords.American Economic Review, 97(1):242–259, March 2007

Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second- price auction: Selling billions of dollars worth of keywords.American Economic Review, 97(1):242–259, March 2007

work page 2007
[3]

College admissions and the stability of marriage.The American Mathematical Monthly, 69(1):9–15, 1962

David Gale and Lloyd S Shapley. College admissions and the stability of marriage.The American Mathematical Monthly, 69(1):9–15, 1962

work page 1962
[4]

Shapley and M

L. Shapley and M. Shubik. The assignment game I: The core.International Journal of Game Theory, 1(1):111–130, 1971

work page 1971
[5]

Ruggiero Cavallo, Prabhakar Krishnamurthy, Maxim Sviridenko, and Christopher A. Wilkens. Sponsored search auctions with rich ads. In Rick Barrett, Rick Cummings, Eugene Agichtein, and Evgeniy Gabrilovich, editors, Proceedings of the 26th International Conference on World Wide Web (WWW 2017), pages 43–51, Perth, Australia,

work page 2017
[6]

Hartline, Nicole Immorlica, Mohammad Reza Khani, Brendan Lucier, and Rad Niazadeh

Jason D. Hartline, Nicole Immorlica, Mohammad Reza Khani, Brendan Lucier, and Rad Niazadeh. Fast core pricing for rich advertising auctions. In Eva Tardos, Edith Elkind, and Rakesh V ohra, editors,Proceedings of the 2018 ACM Conference on Economics and Computation (EC), pages 111–112, Ithaca, NY , USA, 2018. ACM

work page 2018
[7]

On the efficiency and equilibria of rich ads

Mohammad Amin Ghiasi, MohammadTaghi Hajiaghayi, Sébastien Lahaie, and Hadi Yami. On the efficiency and equilibria of rich ads. In Sarit Kraus, editor,Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI 2019), pages 301–307, Macao, China, 2019. ijcai.org

work page 2019
[8]

Simple mechanisms for welfare maximization in rich advertising auctions

Gagan Aggarwal, Kshipra Bhawalkar, Aranyak Mehta, Divyarthi Mohan, and Alexandros Psomas. Simple mechanisms for welfare maximization in rich advertising auctions. InAdvances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022

work page 2022
[9]

Position auctions in ai-generated content, 2025

Santiago Balseiro, Kshipra Bhawalkar, Yuan Deng, Zhe Feng, Jieming Mao, Aranyak Mehta, Vahab Mirrokni, Renato Paes Leme, Di Wang, and Song Zuo. Position auctions in ai-generated content, 2025

work page 2025
[10]

Auctions with llm summaries

Avinava Dubey, Zhe Feng, Rahul Kidambi, Aranyak Mehta, and Di Wang. Auctions with llm summaries. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’24, page 713–722, New York, NY , USA, 2024. Association for Computing Machinery

work page 2024
[11]

Budgeted matching and budgeted matroid intersection via the gasoline puzzle.Mathematical Programming, 128:355–372, 2011

Andreas Berger, Vincenzo Bonifaci, Fabrizio Grandoni, Thomas Rothvoß, and Guido Schäfer. Budgeted matching and budgeted matroid intersection via the gasoline puzzle.Mathematical Programming, 128:355–372, 2011

work page 2011
[12]

Roger B. Myerson. Optimal auction design.Mathematics of Operations Research, 6(1):58–73, 1981

work page 1981
[13]

Position auctions with consumer search.The Quarterly Journal of Economics, 126(3):1213–1270, None 2011

Susan Athey and Glenn Ellison. Position auctions with consumer search.The Quarterly Journal of Economics, 126(3):1213–1270, None 2011

work page 2011
[14]

Cost of conciseness in sponsored search auctions

Zoë Abrams, Arpita Ghosh, and Erik Vee. Cost of conciseness in sponsored search auctions. In Xiaotie Deng and Fan Chung Graham, editors,Internet and Network Economics, pages 326–334, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg

work page 2007
[15]

Ruggiero Cavallo and Christopher A. Wilkens. Gsp with general independent click-through-rates. In Tie-Yan Liu, Qi Qi, and Yinyu Ye, editors,Web and Internet Economics, pages 400–416, Cham, 2014. Springer International Publishing. 13

work page 2014
[16]

Mechanism design for multi-slot ads auction in sponsored search markets

Xiaotie Deng, Yang Sun, Ming Yin, and Yunhong Zhou. Mechanism design for multi-slot ads auction in sponsored search markets. In Der-Tsai Lee, Danny Z. Chen, and Shi Ying, editors,Frontiers in Algorithmics, pages 11–22. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010

work page 2010
[17]

Position auctions with budget constraints: Implications for advertisers and publishers.Marketing Science, 34(6):897–905, 2015

Shijie Lu, Yi Zhu, and Anthony Dukes. Position auctions with budget constraints: Implications for advertisers and publishers.Marketing Science, 34(6):897–905, 2015

work page 2015
[18]

Position auctions with budgets: Existence and uniqueness

Itai Ashlagi, Mark Braverman, Avinatan Hassidim, Ron Lavi, and Moshe Tennenholtz. Position auctions with budgets: Existence and uniqueness. 2010

work page 2010
[19]

Hartline

Gagan Aggarwal and Jason D. Hartline. Knapsack auctions. InProceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 1083–1092. ACM Press, 2006

work page 2006
[20]

Approximation techniques for utilitarian mechanism design

Patrick Briest, Piotr Krysta, and Berthold Vöcking. Approximation techniques for utilitarian mechanism design. SIAM J. Comput., 40(6):1587–1622, 2011

work page 2011
[21]

Utilitarian mechanism design for multiobjective optimization.SIAM Journal on Computing, 43(4):1263–1290, 2014

Fabrizio Grandoni, Piotr Krysta, Stefano Leonardi, and Carmine Ventre. Utilitarian mechanism design for multiobjective optimization.SIAM Journal on Computing, 43(4):1263–1290, 2014

work page 2014
[22]

The performance of deferred-acceptance auctions.Math

Paul Dütting, Vasilis Gkatzelis, and Tim Roughgarden. The performance of deferred-acceptance auctions.Math. Oper. Res., 42(4):897–914, 2017

work page 2017
[23]

G. H. Hardy, J. E. Littlewood, and G. Pólya.Inequalities. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 2nd edition, 1952. Section 10.2, Theorem 368. 14 Appendix A Limitations of Existing Techniques We specify the standard greedy algorithms and their composition and subsequently show why they fail to achieve a constant approximati...

work page 1952