The Ad Types Problem

Conference on Web and Internet Economics (WINE)


In this paper we introduce the Ad Types Problem, a generalization of the traditional positional auction model for ad allocation that better captures some of the challenges that arise when ads of different types need to be interspersed within a user feed of organic content. 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 θ to slot j is vi · αθj where vi is an advertiser-specific value and each ad type θ has a discount curve α1(θ)α 2(θ) ≥ … ≥ 0 over the slots that is common for ads of type θ. We present two contributions for this problem: 1) we give an algorithm that finds the maximum weight matching that runs in O(n2(k + log n)) time for n slots and n ads of each type—cf. O(kn3) when using the Hungarian algorithm—, and 2) we show how to apply reserve prices in total time O(n3 (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 Gij slots cannot show an ad of type θj. We show that the problem is hard to approximate within k1− 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 (including discount curves) optimally and runs in O(k · n2k+1) time.

Related Publications

All Publications

EC - December 23, 2020

Matching Algorithms for Blood Donation

Duncan C. McElfresh, Christian Kroer, Sergey Pupyrev, Eric Sodomka, Karthik Abinav Sankararaman, Zack Chauvin, Neil Dexter, John P. Dickerson

NeurIPS - December 16, 2020

Online Bayesian Persuasion

Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Nicola Gatti

NBER - September 30, 2020

The Effects of COVID-19 on U.S. Small Businesses: Evidence from Owners, Managers, and Employees

Georgij Alekseev, Safaa Amer, Manasa Gopal, Theresa Kuchler, JW Schneider, Johannes Stroebel, Nils Wernerfelt

The Web Conference - April 30, 2020

Envy, Regret, and Social Welfare Loss

Riccardo Colini Baldeschi, Stefano Leonardi, Okke Schrijvers, Eric Sodomka

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy