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

ArXiv/SSRN - December 28, 2020

Social Distancing During a Pandemic: The Role of Friends

Michael Bailey, Drew Johnston, Martin Koenen, Theresa Kuchler, Dominic Russel, Johannes Stroebel

AISTATS - April 13, 2021

Multi-armed Bandits with Cost Subsidy

Deeksha Sinha, Karthik Abinav Sankararaman, Abbas Kazerouni, Vashist Avadhanula

The Web Conference - April 21, 2021

Stochastic bandits for multi-platform budget optimization in online advertising

Vashist Avadhanula, Riccardo Colini Baldeschi, Stefano Leonardi, Karthik Abinav Sankararaman, Okke Schrijvers

Innovative Technology at the Interface of Finance and Operations - March 31, 2021

Market Equilibrium Models in Large-Scale Internet Markets

Christian Kroer, Nicolas E. Stier-Moses

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