pith. sign in

arxiv: 1907.04400 · v1 · pith:SCJUMDAInew · submitted 2019-07-09 · 💻 cs.GT

The Ad Types Problem

Riccardo Colini-Baldeschi , Juli\'an Mestre , Okke Schrijvers , Christopher A. Wilkens This is my paper

Pith reviewed 2026-05-24 23:45 UTC · model grok-4.3

classification 💻 cs.GT
keywords ad types problemmaximum weight matchingassignment problemVCG pricinggap rulesdynamic programmingapproximation hardnessonline advertising
0
0 comments X

The pith

The ad types problem admits a maximum-weight matching algorithm running in O(n²(k + log n)) time.

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

The Ad Types Problem is a structured assignment problem with k ad types sharing discount curves over ordered slots. The paper gives an algorithm to solve the maximum weight matching in O(n²(k + log n)) time, compared to O(kn³) for general methods. It also computes VCG prices in the same time and handles reserve prices in O(n³(k + log n)). For the version with gap rules between ad types, the problem is hard to approximate but can be solved exactly with a dynamic program in O(k n^{2k+1}) time.

Core claim

We present an algorithm that finds the maximum weight matching that runs in O(n^2(k + log n)) time for n slots and n ads of each type—cf. O(kn^3) when using the Hungarian algorithm—and show to do VCG pricing in asymptotically the same time, namely O(n^2(k + log n)), and apply reserve prices in O(n^3(k + log n)). The Ad Types Problem (with gap rules) includes a matrix G such that after we show an ad of type θ_i, the next G_ij slots cannot show an ad of type θ_j. We show that the problem is hard to approximate within k^{1-ε} for any ε > 0 (even without discount curves) by reduction from Maximum Independent Set. On the positive side, we show a Dynamic Program formulation that solves the problem

What carries the argument

The non-increasing discount curves α^θ common to all ads of each type θ, which factor edge weights as v_i · α^θ_j and let the ordered slots be exploited by a specialized matching procedure.

If this is right

  • The maximum weight assignment can be computed without resorting to the general cubic-time Hungarian algorithm when the number of types is small.
  • VCG payments for the optimal assignment can be found in the same near-quadratic time.
  • Reserve prices can be incorporated while keeping the running time polynomial.
  • The gap-rules variant is NP-hard to approximate but admits an exact solution via dynamic programming when k is constant.

Where Pith is reading between the lines

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

  • If discount curves differ within a type the claimed speedup no longer holds and general-purpose solvers become necessary.
  • The same factored-weight structure may yield speedups in other ordered assignment settings outside advertising.
  • Real-time ad auctions with moderate k could scale to larger n using this method rather than cubic solvers.

Load-bearing premise

Each ad type has a fixed, publicly known, non-increasing discount curve that is identical for all ads of that type.

What would settle it

Run the algorithm and the Hungarian algorithm on an instance with n=4 and k=2; if the returned matchings differ in total weight, the claim is false.

read the original abstract

The Ad Types Problem (without gap rules) is a special case of the assignment problem in which there are $k$ types of nodes on one side (the ads), and an ordered set of nodes on the other side (the slots). The edge weight of an ad $i$ of type $\theta$ to slot $j$ is $v_i\cdot \alpha^{\theta}_j$ where $v_i$ is an advertiser-specific value and each ad type $\theta$ has a discount curve $\alpha^{(\theta)}_{1} \ge \alpha^{(\theta)}_{2} \ge ... \ge 0$ over the slots that is common for ads of type $\theta$. We present two contributions for this problem: 1) we give an algorithm that finds the maximum weight matching that runs in $O(n^2(k + \log n))$ time for $n$ slots and $n$ ads of each type---cf. $O(kn^3)$ when using the Hungarian algorithm---, and 2) we show to do VCG pricing in asymptotically the same time, namely $O(n^2(k + \log n))$, and apply reserve prices in $O(n^3(k + \log n))$. The Ad Types Problem (with gap rules) includes a matrix $G$ such that after we show an ad of type $\theta_i$, the next $G_{ij}$ slots cannot show an ad of type $\theta_j$. We show that the problem is hard to approximate within $k^{1- \epsilon}$ for any $\epsilon > 0$ (even without discount curves) by reduction from Maximum Independent Set. On the positive side, we show a Dynamic Program formulation that solves the problem (including discount curves) optimally and runs in $O(k\cdot n^{2k + 1})$ time.

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.

Referee Report

0 major / 2 minor

Summary. The paper defines the Ad Types Problem (without gap rules) as a structured assignment problem with k ad types on one side and n ordered slots on the other; each ad i of type θ has value v_i and edges to slots weighted by v_i · α^θ_j where α^θ is a type-specific non-increasing discount curve. It claims an O(n²(k + log n)) algorithm for maximum-weight perfect matching (n slots, n ads per type) improving on the O(kn³) Hungarian algorithm, shows VCG payments can be computed in the same bound, and reserve prices in O(n³(k + log n)). For the gap-rules variant (with matrix G forbidding certain type sequences), it proves inapproximability within k^{1-ε} via reduction from Maximum Independent Set (even without discounts) and gives an O(k n^{2k+1}) dynamic program that solves the problem optimally including discounts.

Significance. If the stated running times and reduction hold, the work gives a practically relevant speedup for a structured assignment problem arising in ad allocation, together with matching VCG pricing. The clean separation between the gap-rules and non-gap-rules cases, the explicit time bounds, and the reduction from Maximum Independent Set are strengths that make the contribution self-contained and falsifiable.

minor comments (2)
  1. [Abstract] Abstract, paragraph 1: the statement 'n slots and n ads of each type' should be clarified to indicate that there are kn total ads and the matching selects exactly n of them; the current phrasing risks confusion about the input size.
  2. [Abstract] Abstract: the notation α^θ_j (with superscript θ and subscript j) is used without an explicit definition of the index ranges; a single sentence defining the domain of θ and j would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the paper, accurate summary of the contributions, and recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; algorithmic claims are self-contained

full rationale

The paper states an explicit model (identical non-increasing α^θ per type, perfect matching) upfront and derives a specialized O(n²(k + log n)) algorithm plus VCG pricing from first-principles combinatorial arguments on that model. No parameters are fitted then renamed as predictions, no self-citation chains justify core claims, no ansatz is smuggled, and no result is defined in terms of itself. The gap-rules hardness and DP are separate and explicitly bounded. This matches the default expectation of a non-circular algorithmic paper.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, invented entities, or non-standard axioms are introduced; the work relies on standard properties of the assignment problem and non-increasing sequences.

pith-pipeline@v0.9.0 · 5882 in / 1175 out tokens · 20751 ms · 2026-05-24T23:45:19.764426+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Envy, Regret, and Social Welfare Loss

    cs.GT 2019-07 unverdicted novelty 6.0

    Introduces IC-Envy metric for auction incentive compatibility that satisfies IC-Envy ≥ IC-Regret in position auctions and ad types, bounds social welfare loss from misreports, and improves ML prediction of regret over...

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Cost of conciseness in s ponsored search auctions

    Zoe Abrams, Arpita Ghosh, and Erik Vee. Cost of conciseness in s ponsored search auctions. In Proceedings of the 3rd International Conference on Interne t and Network Economics, pages 326–334, 2007

    work page 2007

  2. [2]

    Muthukrishnan, and Martin Pal

    Gagan Aggarwal, Jon Feldman, S. Muthukrishnan, and Martin Pal. Sponsored search auctions with markovian users. In Proceedings of the Workshop on Internet and Network Economics (WINE), pages 621–628, 2008

    work page 2008

  3. [3]

    Position auctions with consumer sea rch

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

    work page 2011

  4. [4]

    Sponsored search auctions with rich ads

    Ruggiero Cavallo, Prabhakar Krishnamurthy, Maxim Sviridenko, a nd Christopher A Wilkens. Sponsored search auctions with rich ads. In Proceedings of the 26th Interna- tional Conference on World Wide Web , pages 43–51. International World Wide Web Conferences Steering Committee, 2017

    work page 2017

  5. [5]

    Mat ching auctions for search and native ads

    Ruggiero Cavallo, Maxim Sviridenko, and Christopher A Wilkens. Mat ching auctions for search and native ads. In Proceedings of the 2018 ACM Conference on Economics and Computation , pages 663–680. ACM, 2018

    work page 2018

  6. [6]

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

    work page 2014

  7. [7]

    Multipart pricing of public goods

    Edward H Clarke. Multipart pricing of public goods. Public choice , 11(1):17–33, 1971

    work page 1971

  8. [8]

    Mechanism de sign for multi-slot ads auction in sponsored search markets

    Xiaotie Deng, Yang Sun, Ming Yin, and Yunhong Zhou. Mechanism de sign for multi-slot ads auction in sponsored search markets. In Proc of the 4th Frontiers in Algorithmics International Workshop , pages 11–22, 08 2010

    work page 2010

  9. [9]

    Sponsore d search, market equi- libria, and the hungarian method

    Paul D¨ utting, Monika Henzinger, and Ingmar Weber. Sponsore d search, market equi- libria, and the hungarian method. Information Processing Letters, 113(3):67–73, 2013

    work page 2013

  10. [10]

    Networks, crowds, and markets , volume 8

    David Easley, Jon Kleinberg, et al. Networks, crowds, and markets , volume 8. Cam- bridge university press Cambridge, 2010

    work page 2010

  11. [11]

    I nternet advertising and the generalized second-price auction: Selling billions of dollars worth o f keywords

    Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. I nternet advertising and the generalized second-price auction: Selling billions of dollars worth o f keywords. Amer- ican economic review , 97(1):242–259, 2007

    work page 2007

  12. [12]

    Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM , 19(2):248–264, 1972

    work page 1972

  13. [13]

    Ad auctions and cascade model: G sp inefficiency and algorithms

    Gabriele Farina and Nicola Gatti. Ad auctions and cascade model: G sp inefficiency and algorithms. In Proceedings of the Thirtieth AAAI Conference on Artificial I ntelligence, AAAI’16, pages 489–495. AAAI Press, 2016

    work page 2016

  14. [14]

    Fibonacci heaps and their uses in im- proved network optimization algorithms

    Michael L Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in im- proved network optimization algorithms. Journal of the ACM (JACM) , 34(3):596–615, 1987

    work page 1987

  15. [15]

    A linear-time algorithm for a special case of disjoint set union

    Harold N Gabow and Robert Endre Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of computer and system sciences , 30(2):209–221, 1985

    work page 1985

  16. [16]

    Externalities in online adver tising

    Arpita Ghosh and Mohammad Mahdian. Externalities in online adver tising. In Pro- ceedings of the 17th International World Wide Web Conferenc e, pages 161–168, 2008

    work page 2008

  17. [17]

    Expressive auctions for externa lities in online adver- tising

    Arpita Ghosh and Amin Sayedi. Expressive auctions for externa lities in online adver- tising. In Proceedings of the 19th International Conference on World W ide Web , pages 371–380, 2010. 19

    work page 2010

  18. [18]

    Ioannis Giotis and Anna R. Karlin. On the equilibria and efficiency of t he gsp mechanism in keyword auctions with externalities. In Proceedings of the 4th International Workshop on Internet and Network Economics (WINE) , pages 629–638, 2008

    work page 2008

  19. [19]

    Maximum matching in a convex bipartite graph

    Fred Glover. Maximum matching in a convex bipartite graph. Naval research logistics quarterly, 14(3):313–316, 1967

    work page 1967

  20. [20]

    Exter nalities in keyword auctions: An empirical and theoretical assessment

    Renato Gomes, Nicole Immorlica, and Evangelos Markakis. Exter nalities in keyword auctions: An empirical and theoretical assessment. In Proceedings of the Workshop on Internet and Network Economics (WINE) , pages 172–183, 2009

    work page 2009

  21. [21]

    Incentives in teams

    Theodore Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617–631, 1973

    work page 1973

  22. [22]

    Fast core pricing for rich advertising auctions

    Jason Hartline, Nicole Immorlica, Mohammad Reza Khani, Brendan Lucier, and Rad Niazadeh. Fast core pricing for rich advertising auctions. In Proceedings of the 2018 ACM Conference on Economics and Computation , pages 111–112. ACM, 2018

    work page 2018

  23. [23]

    Position auctions with dynamic resizing

    Patrick Hummel. Position auctions with dynamic resizing. International Journal of Industrial Organization , 45:38–46, 2016

    work page 2016

  24. [24]

    Clique is hard to approximate within n(1− ǫ)

    Johan Hstad. Clique is hard to approximate within n(1− ǫ). In Acta Mathematica , pages 627–636, 1996

    work page 1996

  25. [25]

    Matchings in node-weighted convex bipartite graph s

    Irit Katriel. Matchings in node-weighted convex bipartite graph s. INFORMS Journal on Computing , 20(2):205–211, 2008

    work page 2008

  26. [26]

    A cascade model for exter nalities in sponsored search

    David Kempe and Mohammad Mahdian. A cascade model for exter nalities in sponsored search. In Proceedings of the 4th International Workshop on Internet a nd Network Economics, pages 585–596, 2008

    work page 2008

  27. [27]

    Note on VCG vs. Price Raising for Matching Markets

    Walter Kern, Bodo Manthey, and Marc Uetz. Note on vcg vs. pr ice raising for matching markets. arXiv preprint arXiv:1604.04157 , 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  28. [28]

    The hungarian method for the assignment proble m

    Harold W Kuhn. The hungarian method for the assignment proble m. Naval research logistics quarterly, 2(1-2):83–97, 1955

    work page 1955

  29. [29]

    Sponsored search auctions

    S´ ebastien Lahaie, David M Pennock, Amin Saberi, and Rakesh V V ohra. Sponsored search auctions. Algorithmic game theory , pages 699–716, 2007

    work page 2007

  30. [30]

    Efficient algorithms for fin ding maximum match- ings in convex bipartite graphs and related problems

    Witold Lipski and Franco P Preparata. Efficient algorithms for fin ding maximum match- ings in convex bipartite graphs and related problems. Acta Informatica, 15(4):329–346, 1981

    work page 1981

  31. [31]

    A lgorithmic cartog- raphy: Placing points of interest and ads on maps

    Mohammad Mahdian, Okke Schrijvers, and Sergei Vassilvitskii. A lgorithmic cartog- raphy: Placing points of interest and ads on maps. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery an d Data Mining , pages 755–764. ACM, 2015. 20

    work page 2015

  32. [32]

    Algorithms for the assignment and transport ation problems

    James Munkres. Algorithms for the assignment and transport ation problems. Journal of the society for industrial and applied mathematics , 5(1):32–38, 1957

    work page 1957

  33. [33]

    Muthukrishnan

    S. Muthukrishnan. Bidding on configurations in internet ad auct ions. In Hung Q. Ngo, editor, Computing and Combinatorics , pages 1–6, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg

    work page 2009

  34. [34]

    Optimal auction design

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

    work page 1981

  35. [35]

    Fast scheduling of weighted unit jobs with releas e times and deadlines

    C Greg Plaxton. Fast scheduling of weighted unit jobs with releas e times and deadlines. In International Colloquium on Automata, Languages, and Prog ramming, pages 222–

    work page

  36. [36]

    Vertex-weighted matching in two-direction al orthogonal ray graphs

    C Gregory Plaxton. Vertex-weighted matching in two-direction al orthogonal ray graphs. In International Symposium on Algorithms and Computation , pages 524–534. Springer, 2013

    work page 2013

  37. [37]

    On minimum-cost assignment s in unbalanced bipartite graphs

    Lyle Ramshaw and Robert E Tarjan. On minimum-cost assignment s in unbalanced bipartite graphs. HP Labs, Palo Alto, CA, USA, Tech. Rep. HPL-2012-40R1 , 2012

    work page 2012

  38. [38]

    Revenue-maximizing auctions

    Tim Roughgarden. Revenue-maximizing auctions. Twenty lectures on algorithmic game theory, 2016

    work page 2016

  39. [39]

    Ironing in the dark

    Tim Roughgarden and Okke Schrijvers. Ironing in the dark. In Proceedings of the 2016 ACM Conference on Economics and Computation , pages 1–18. ACM, 2016

    work page 2016

  40. [40]

    Algorithms for the tran sportation problem in geometric settings

    R Sharathkumar and Pankaj K Agarwal. Algorithms for the tran sportation problem in geometric settings. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages 306–317. Society for Industrial and Applied Mathematics, 2012

    work page 2012

  41. [41]

    Position auctions

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

    work page 2007

  42. [42]

    Counterspeculation, auctions, and competitive s ealed tenders

    William Vickrey. Counterspeculation, auctions, and competitive s ealed tenders. The Journal of finance , 16(1):8–37, 1961

    work page 1961

  43. [43]

    Linear degree extractors and the inapprox imability of max clique and chromatic number

    David Zuckerman. Linear degree extractors and the inapprox imability of max clique and chromatic number. Theory of Computing , 3(1):103–128, 2007. 21

    work page 2007