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

Journal of Big Data - November 6, 2021

A graphical method of cumulative differences between two subpopulations

Mark Tygert

The Quarterly Journal of Economics - October 25, 2021

Peer Effects in Product Adoption

Michael Bailey, Drew Johnston, Theresa Kuchler, Johannes Stroebel, Arlene Wong

Conference on Neural Information Processing Systems (NeurIPS) - December 1, 2021

Bandits with Knapsacks beyond the Worst Case

Karthik Abinav Sankararaman, Aleksandrs Slivkins

POPL - January 22, 2022

Profile Inference Revisited

Wenlei He, Julián Mestre, Sergey Pupyrev, Lei Wang, Hongtao Yu

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: Cookie Policy