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.

Featured Publications