REVIEW 3 major objections 4 minor 33 references
Position Auctions in AI-Generated Content
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Under the MNL user model the paper obtains computationally efficient welfare-optimal auctions and revenue-optimal auctions, and under the cascade model it obtains $O(\log m)$-approximate auctions, all with truthfulness guarantees suitable…
desk verdict Timely mechanism-design paper with a real MNL LP trick and a useful cascade approximation, but the revenue theorems need a regularity assumption and one proof misuses convexity. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The winner determination problem (WDP) is the engine of the paper: a single optimization over augmented allocations whose exact or approximate, monotone solutions plug into VCG payments for welfare maximization and into the envelope-theorem integral for revenue maximization. For MNL, the WDP objective is linear-fractional, and the paper transforms it into a linear program by changing variables to $y_{ij} = x_{ij}/(1+\sum_{i',j'} x_{i'j'} e^{\rho_{i'j'}})$ and $z = 1/(1+\sum_{i',j'} x_{i'j'} e^{\rho_{i'j'}})$; since the relaxed objective is convex over the matching polytope, a maximum occurs at an integral extreme point, so the relaxation yields an integral matching without loss. For the cascade model, the paper introduces a restricted welfare problem that removes the cascading discount, proves it 4-approximates the original WDP, gives a PTAS for it via budgeted matching, and then converts the approach into a monotone $O(\log m)$-approximation by bucketing advertiser-position pairs by their click-through rates and running greedy maximal matching inside each bucket.
What would settle it
Run a controlled experiment on an AI chat or search surface: estimate the standalone position-ad click rates $p_{ij}$, choose allocations by the paper's mechanisms, and compare the model-predicted joint click probabilities under MNL and cascade with observed user clicks. If users click more than one sponsored creative, continue scanning after a click, or choose in a way that fits neither the simultaneous-choice nor the sequential-stopping rule, then the predicted welfare and revenue guarantees for the corresponding model would not hold on that surface.
Extended reading notes
Core claim
The paper's central claim is that dropping the separability assumption — the classic assumption that an ad's click rate factors into an ad effect times a position effect — changes the allocation problem from ranking to general matching, but the change does not break mechanism design. The key reduction is to the winner determination problem (WDP): choose an augmented allocation (a matching of advertisers to positions together with a rendering order) that maximizes the total bidder weight. The paper proves that any exact solution of the WDP is monotone in each bidder's bid (Lemma 3.1), so VCG payments give a truthful welfare-maximizing auction and envelope-theorem payments give a revenue-maximizing auction. The paper then shows the WDP is tractable: under MNL it is solved exactly by a linear-programming relaxation that recovers an integral matching (Theorem 4.1), and under the cascade model it is solved within an $O(\log m)$ factor by a monotone algorithm (Corollary 5.1).
Load-bearing premise
The welfare and revenue guarantees hold only if real user behavior in AI-generated content matches the multinomial logit or cascade model, including the assumptions that a user clicks at most one ad and, in the cascade model, stops immediately after clicking; the paper takes these models and the standalone click-through-rate matrix as given rather than empirically validated.
Editorial extensions
If this is right
- A platform can run a VCG-style auction for in-content ads and rely on truthful reporting rather than bid shading, achieving optimal welfare under the MNL model.
- Under MNL, the exact optimal allocation is computable in polynomial time even though each position-ad pair has its own click-through rate.
- Under the cascade model, a truthful auction loses only a logarithmic factor in the number of positions, so near-optimal welfare or revenue remains achievable in polynomial time.
- The greedy matching construction is monotone, which is what lets the envelope theorem produce payments; the resulting auction is $\epsilon$-incentive-compatible and individually rational.
- Substitution effects are modeled explicitly: the allocation problem is a matching, not a ranking, so the chosen set of ads matters, not just their order.
Reading between the lines
- The practical bottleneck is measurement, not computation: if large language models cannot estimate standalone position-ad click-through rates accurately enough, the theoretical guarantees have no real-world hook.
- The $O(\log m)$ gap in the cascade model is likely not intrinsic; the paper leaves open whether a constant-factor monotone approximation exists, and closing that gap would make cascade auctions directly deployable.
- The same LP-transformation trick may extend to other choice models whose objective is linear-fractional with a totally unimodular feasible region, a direction the paper does not pursue.
- A behavioral hybrid — say, cascade scanning with occasional returns or multi-click users — would require new models; testing those empirically is a natural next step.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper extends classical position auctions to placements embedded in AI-generated content, where the click-through rate of each advertiser-position pair is pair-specific and user substitution matters. The authors formulate a winner determination problem (WDP) and show how exact or approximate WDP solvers with monotone allocation rules yield IC/IR welfare- and revenue-maximizing mechanisms via VCG, Myerson, and the envelope theorem. For the MNL user model, they propose an LP-based exact WDP algorithm and claim optimal welfare and ε-IC revenue auctions. For the cascade model, they give a 4-approximation via a restricted welfare problem, a PTAS, and an O(log m)-approximation with a monotone allocation rule, yielding approximately optimal auctions. The paper has several load-bearing technical gaps: the proof of Lemma 4.2 is invalid and its statement is false, the revenue theorems omit a regularity assumption, and the cascade revenue results do not address negative virtual values.
Significance. The topic is timely, and the reduction framework is standard and clearly presented: the paper correctly observes that an exact WDP oracle yields VCG for welfare and, under monotonicity, an envelope-based optimal auction, and that approximate solvers can be plugged in if monotonicity is separately proven. The cascade-model contribution—a monotone O(log m)-approximate WDP via bucketing and greedy matching—appears to be a genuine algorithmic result, and the 4-approximation and PTAS for the restricted welfare problem are interesting. If the identified gaps are fixed, the paper would provide a useful foundation for ad allocation in generative-AI content. The current version, however, cannot be accepted because the main MNL algorithm and the revenue theorems are not correct as stated.
major comments (3)
- [Section 4, Lemma 4.2] Lemma 4.2 is incorrect as stated and its proof rests on a false premise. The proof claims that the WDP objective is convex in x because 'linear-fractional functions are convex on its domain' and then invokes the Bauer maximum principle. Linear-fractional functions are not convex; they are quasilinear (both quasiconvex and quasiconcave), and the cited Boyd reference does not support convexity. More seriously, the conclusion that setting x = y/z from any optimal solution (y,z) of LP (5) yields an integral matching is false. For a concrete counterexample, take n=m=2, K=2, rho_ij=0 for all i,j, and b_i=1. The point y_ij=1/6 for all i,j and z=1/3 is feasible and optimal for (5), but x_ij = y_ij/z = 1/2 for all i,j is not an integral matching, while both the integral perfect matchings achieve the same objective value 2/3. Thus the proposed LP algorithm does not, as written, output a feasible integral allocation. The theorem that the MNL WDP is polynomial may still be true (for example through parametric search on the ratio objective), but the proof and algorithm provided need substantial correction.
- [Section 3.2, Theorem 4.1, Corollary 5.1] The revenue-maximization theorems are stated for arbitrary absolutely continuous independent value distributions, but the construction in Section 3.2 requires the virtual-value allocation rule to be monotone. The paper itself notes in Section 3.2 that a sufficient condition is that the virtual values phi_i(v_i) = v_i - (1-F_i(v_i))/f_i(v_i) are non-decreasing, yet no regularity assumption or ironing procedure is introduced in Section 2 or in the theorem statements. For a non-regular distribution, the rule 'solve the WDP with b_i = phi_i(v_i)' need not be monotone. In the minimal MNL case n=m=1, the allocation is y(v)=1{phi(v)>0}; if phi crosses zero twice, y(v) is 1, then 0, then 1 as v increases. Such a rule cannot be implemented with the envelope payment (4), and Myerson's lemma gives a strict IC violation, not an epsilon-level one. The epsilon in Theorem 4.1 is described only as coming from discretizing the payment integral, not from handling non-monotone allocations. The theorems should be restricted to regular distributions or should incorporate ironed virtual values.
- [Sections 5.3-5.4, Corollary 5.1] The cascade WDP algorithms (Algorithm 1, Algorithm 2, and the analyses in Section 5.3, Section 5.4, and Appendix A) are developed for nonnegative values/bids, but the revenue reduction in Section 3.2 uses bids that are virtual values, which can be negative. The approximation proofs rely on weights w_ij = v_i p_ij and on arguments involving 'the minimum value' and token contributions that fail or become vacuous when weights are negative. For instance, if every virtual value is negative, the optimal WDP value is 0 (no allocation), whereas Algorithm 2 would still match edges of negative weight, yielding a negative welfare and violating the claimed O(log m) approximation ratio. The paper needs to specify how the cascade WDP solver treats negative bids (for example, by discarding advertisers with negative virtual values) and to reprove the approximation and monotonicity guarantees in that regime. As stated, the revenue part of Corollary 5.1 is not supported.
minor comments (4)
- [Theorem 4.1 and Corollary 5.1] The parameter epsilon is used without a formal definition of epsilon-IC and without a statement of the running-time dependence on epsilon; please add formal definitions and state the computational complexity as a function of epsilon and the input size.
- [Appendix A, Lemma 5.16] The proof of monotonicity for the greedy matching algorithm is only a sketch. In particular, the case where an advertiser's value increase changes the identity of the matched position is not handled rigorously; please expand the argument with a detailed case analysis.
- [Section 4, Lemma 4.2 citation] The paper cites Boyd et al. Chapter 2.3.3 for the claim that linear-fractional functions are convex; this is incorrect, as Boyd et al. discuss quasiconvexity of linear-fractional functions. The citation should be corrected together with the proof of Lemma 4.2.
- [Author block] The author names in the running header contain spacing artifacts (e.g., 'BHA W ALKAR', 'V AHAB MIRROKNI'); the final version should use the correct names.
Circularity Check
No significant circularity: the central derivations reduce to standard external results (VCG, Myerson, Milgrom–Segal, Berger et al.) and are not fitted to the quantities they predict.
full rationale
The paper's derivation chain is self-contained and non-circular. The central results are obtained by reducing mechanism design to a winner determination problem (WDP), then solving the WDP. The welfare-maximization auction uses the standard VCG construction with payments given by Eq. (3) and the optimal WDP allocation; no fitted parameter or target quantity is presupposed. The revenue-maximization auction follows the standard Myerson/envelope reduction: optimality is characterized via virtual values phi_i(v_i) and the envelope payment rule (4), with Lemma 3.1 establishing monotonicity of the exact WDP solution. The approximation results in the cascade model rest on external, independently verified results: the PTAS of Berger et al. (2008) for budgeted matching, cited as Theorem 5.6, and classical facts on greedy matchings. The MNL LP transformation (Lemma 4.2) invokes convexity and extreme-point properties from Boyd et al., not any conclusion of this paper. The related-work section contains self-citations by the same Google authors, but none of these citations is used to justify the model, the reductions, or the approximation guarantees; all load-bearing external assumptions are standard (Myerson 1981; Milgrom and Segal 2002; Berger et al. 2008) and are cited as external theorems. There is therefore no step in which a prediction is equivalent by construction to a fitted input or to a self-citation. A separate concern, the absent regularity/ironing assumption in the revenue theorems, is a correctness risk rather than circularity.
Assumptions & free parameters
assumptions (5)
- domain assumption Standalone click-through rates p_ij are known common knowledge for every position-creative pair and correctly capture context-dependent CTRs.
- domain assumption User behavior follows the multinomial logit model or the cascade model as specified in Section 2.1.
- domain assumption Advertiser values are independently distributed with absolutely continuous distributions and, for revenue optimality, regular virtual values that are non-decreasing.
- standard math Berger et al. 2008 provide a PTAS for the budgeted matching problem.
- standard math The Charnes-Cooper transformation and basic properties of linear-fractional programs are valid.
Cite this review
Pith. "Pith review of Position Auctions in AI-Generated Content." pith.science (2026). https://pith.science/paper/DTSZIZBB
@misc{pith2026250603309,
author = {Pith},
title = {Pith review of: Position Auctions in AI-Generated Content},
year = {2026},
howpublished = {\url{https://pith.science/paper/DTSZIZBB}},
note = {Machine review of arXiv:2506.03309}
}
read the original abstract
We consider an extension to the classic position auctions in which sponsored creatives can be added within AI generated content rather than shown in predefined slots. New challenges arise from the natural requirement that sponsored creatives should smoothly fit into the context. With the help of advanced LLM technologies, it becomes viable to accurately estimate the benefits of adding each individual sponsored creatives into each potential positions within the AI generated content by properly taking the context into account. Therefore, we assume one click-through rate estimation for each position-creative pair, rather than one uniform estimation for each sponsored creative across all positions in classic settings. As a result, the underlying optimization becomes a general matching problem, thus the substitution effects should be treated more carefully compared to standard position auction settings, where the slots are independent with each other. In this work, we formalize a concrete mathematical model of the extended position auction problem and study the welfare-maximization and revenue-maximization mechanism design problem. Formally, we consider two different user behavior models and solve the mechanism design problems therein respectively. For the Multinomial Logit (MNL) model, which is order-insensitive, we can efficiently implement the optimal mechanisms. For the cascade model, which is order-sensitive, we provide approximately optimal solutions.
Figures
Reference graph
Works this paper leans on
-
[9]
In Proceedings of the 2008 international conference on web search and data mining
An experimental comparison of click position-bias models. In Proceedings of the 2008 international conference on web search and data mining . 87–94. Yuan Deng, Vahab Mirrokni, Renato Paes Leme, Hanrui Zhang, and Song Zuo
work page 2008
-
[12]
arXiv preprint arXiv:2402.01704 (2024)
States as Strings as Strategies: Steering Language Models with Game-Theoretic Solvers. arXiv preprint arXiv:2402.01704 (2024). Arpita Ghosh and Mohammad Mahdian
arXiv 2024
-
[13]
Externalities in online advertising. In Proceedings of the 17th International Conference on World Wide Web, WWW 2008, Beijing, China, April 21-25, 2008 , Jinpeng Huai, Robin Chen, Hsiao-Wuen Hon, Yunhao Liu, Wei-Ying Ma, Andrew Tomkins, and Xiaodong Zhang (Eds.). ACM, 161–168. https://doi.org/10.1145/ 1367497.1367520 Renato Gomes, Nicole Immorlica, and Ev...
arXiv 2008
-
[16]
In Proceedings of the ACM on Web Conference 2024
Bidder Selection Problem in Position Auctions: A Fast and Simple Algorithm via Poisson Approximation. In Proceedings of the ACM on Web Conference 2024 . 89–98. MohammadTaghi Hajiaghayi, Sébastien Lahaie, Keivan Rezaei, and Suho Shin
work page 2024
-
[17]
arXiv preprint arXiv:2406.09459 (2024)
Ad Auctions for LLMs via Retrieval Augmented Generation. arXiv preprint arXiv:2406.09459 (2024). Przemyslaw Jeziorski and Ilya Segal
arXiv 2024
-
[19]
A Cascade Model for Externalities in Sponsored Search. In Internet and Network Economics, 4th International Workshop, WINE 2008, Shanghai, China, December 17-20,
work page 2008
-
[20]
Papadimitriou and Shuzhong Zhang (Eds.)
, Christos H. Papadimitriou and Shuzhong Zhang (Eds.). Springer, 585–596. https: //doi.org/10.1007/978-3-540-92185-1_65 Nunzio Lorè and Babak Heydari
-
[21]
Strategic behavior of large language models: Game structure vs. contextual framing. arXiv preprint arXiv:2309.05898 (2023). Yuxuan Lu, Shengwei Xu, Yichi Zhang, Yuqing Kong, and Grant Schoenebeck
arXiv 2023
Show all 33 references
-
[22]
arXiv preprint arXiv:2311.03220 (2023)
Alympics: Language agents meet game theory. arXiv preprint arXiv:2311.03220 (2023). Daniel McFadden
2023 arXiv
-
[26]
arXiv preprint arXiv:2402.09552 (2024)
Rationality Report Cards: Assessing the Economic Rationality of Large Language Models. arXiv preprint arXiv:2402.09552 (2024). Eric Hal Schwartz
2024 arXiv
-
[27]
Eric Hal Schwartz
Microsoft Bing Generative AI Chatbot Experiments With Ads.https://voicebot.ai/2023/04/03/microsoft- bing-generative-ai-chatbot-experiments-with-ads/ (2023). Eric Hal Schwartz
2023
-
[28]
https://voicebot.ai/2024/04/02/perplexity-will-embed-ads-in-generative-ai-search-engine/ (2024)
Perplexity Will Embed Ads in Generative AI Search Engine: Report. https://voicebot.ai/2024/04/02/perplexity-will-embed-ads-in-generative-ai-search-engine/ (2024). Ermis Soumalias, Michael J Curry, and Sven Seuken
2024
-
[29]
arXiv preprint arXiv:2405.05905 (2024)
Truthful Aggregation of LLMs with an Application to Online Advertising. arXiv preprint arXiv:2405.05905 (2024). Haoran Sun, Yurong Chen, Siwei Wang, Wei Chen, and Xiaotie Deng
2024 arXiv
-
[30]
arXiv preprint arXiv:2405.16276 (2024)
Mechanism Design for LLM Fine-tuning with Multiple Reward Models. arXiv preprint arXiv:2405.16276 (2024). David Robert Martin Thompson and Kevin Leyton-Brown
2024
-
[31]
International Journal of Industrial Organization 25, 6 (2007), 1163–1178
Position auctions. International Journal of Industrial Organization 25, 6 (2007), 1163–1178. William Vickrey
2007
-
[33]
arXiv preprint arXiv:2406.09363 (2024)
ElicitationGPT: Text Elicitation Mechanisms via Language Models. arXiv preprint arXiv:2406.09363 (2024). 20 Santiago Balseiro, Kshipra Bhawalkar, Yuan Deng, Zhe Feng, Jieming Mao, Aranyak Mehta, Vahab Mirrokni, Renato Paes Leme, Di Wang, and Song Zuo A Missing proofs of Sectio...
2024
-
[1961]
The Journal of Finance 16, 1 (1961), 8–37
Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance 16, 1 (1961), 8–37. Yifan Wu and Jason Hartline
1961
-
[1971]
Public choice 11, 1 (1971), 17–33
Multipart pricing of public goods. Public choice 11, 1 (1971), 17–33. Nick Craswell, Onno Zoeter, Michael Taylor, and Bill Ramsey
1971
-
[1975]
Journal of the Royal Statistical Society Series C: Applied Statistics 24, 2 (1975), 193–202
The analysis of permutations. Journal of the Royal Statistical Society Series C: Applied Statistics 24, 2 (1975), 193–202. Narun Raman, Taylor Lundy, Samuel Amouyal, Yoav Levine, Kevin Leyton-Brown, and Moshe Tennenholtz
1975
-
[1981]
Mathematics of operations research 6, 1 (1981), 58–73
Optimal auction design. Mathematics of operations research 6, 1 (1981), 58–73. Robin L Plackett
1981
-
[2002]
Econometrica 70, 2 (2002), 583–601
Envelope theorems for arbitrary choice sets. Econometrica 70, 2 (2002), 583–601. Roger B Myerson
2002
-
[2007]
American Economic Review 97, 1 (2007), 242–259
Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American Economic Review 97, 1 (2007), 242–259. Position Auctions in AI-Generated Content 19 Caoyun Fan, Jindou Chen, Yaohui Jin, and Hao He
2007
-
[2008]
In Internet and Network Economics, 4th International Workshop, WINE 2008, Shanghai, China, December 17-20,
Sponsored Search Auctions with Markovian Users. In Internet and Network Economics, 4th International Workshop, WINE 2008, Shanghai, China, December 17-20,
2008
-
[2009]
In Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18,
Externalities in Keyword Auctions: An Empirical and Theoretical Assessment. In Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18,
2009
-
[2011]
The Quarterly Journal of Economics 126, 3 (2011), 1213–1270
Position auctions with consumer search. The Quarterly Journal of Economics 126, 3 (2011), 1213–1270. Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, et al
2011
-
[2014]
arXiv preprint arXiv:1411.0279 (2014)
Optimizing Expected Utility in a Multinomial Logit Model with Position Bias and Social Influence. arXiv preprint arXiv:1411.0279 (2014). Gagan Aggarwal, Jon Feldman, S. Muthukrishnan, and Martin Pál
2014 arXiv
-
[2015]
American Economic Journal: Microeconomics 7, 3 (August 2015), 24–53
What Makes Them Click: Empirical Analysis of Consumer Demand for Search Advertising. American Economic Journal: Microeconomics 7, 3 (August 2015), 24–53. https://doi.org/10.1257/mic.20100119 David Kempe and Mohammad Mahdian
2015 doi
-
[2020]
Position Ranking and Auctions for Online Marketplaces.Manag. Sci. 66, 8 (2020), 3617–3634. https://doi.org/10.1287/MNSC.2019.3372 Edward H Clarke
2020
-
[2022]
Science 378, 6624 (2022), 1067–1074
Human-level play in the game of Diplomacy by combining language models with strategic reasoning. Science 378, 6624 (2022), 1067–1074. André Berger, Vincenzo Bonifaci, Fabrizio Grandoni, and Guido Schäfer
2022
-
[2023]
arXiv preprint arXiv:2310.05746 (2023)
Put your money where your mouth is: Evaluating strategic planning and execution of LLM agents in an auction arena. arXiv preprint arXiv:2310.05746 (2023). Leon Yang Chu, Hamid Nazerzadeh, and Heng Zhang
2023 arXiv
-
[2024]
In Proceedings of the ACM on Web Conference 2024
Mechanism design for large language models. In Proceedings of the ACM on Web Conference 2024 . 144–155. Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz
2024
-
[5385]
Papadimitriou and Shuzhong Zhang (Eds.)
, Christos H. Papadimitriou and Shuzhong Zhang (Eds.). Springer, 621–628. https://doi.org/10.1007/978-3-540-92185-1_68 Susan Athey and Glenn Ellison
-
[5929]
Springer, 172–183
, Stefano Leonardi (Ed.). Springer, 172–183. https://doi.org/10.1007/978-3-642-10841-9_17 Nikolai Gravin, Yixuan Even Xu, and Renfei Zhou
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.