Ad Exchange: Envy-Free Auctions with Mediators

Abstract

Ad exchanges are an emerging platform for trading advertisement slots on the web with billions of dollars revenue per year. Every time a user visits a web page, the publisher of that web page can ask an ad exchange to auction off the ad slots on this page to determine which advertisements are shown at which price. Due to the high volume of traffic, ad networks typically act as mediators for individual advertisers at ad exchanges. If multiple advertisers in an ad network are interested in the ad slots of the same auction, the ad network might use a “local” auction to resell the obtained ad slots among its advertisers.

In this work we want to deepen the theoretical understanding of these new markets by analyzing them from the viewpoint of combinatorial auctions. Prior work studied mostly single-item auctions, while we allow the advertisers to express richer preferences over multiple items. We develop a game-theoretic model for the entanglement of the central auction at the ad exchange with the local auctions at the ad networks. We consider the incentives of all three involved parties and suggest a three-party competitive equilibrium, an extension of the Walrasian equilibrium that ensures envy-freeness for all participants. We show the existence of a three-party competitive equilibrium and a polynomial-time algorithm to find one for gross-substitute bidder valuations.

This work was funded by the Vienna Science and Technology Fund (WWTF) through project ICT10-002. Additionally the research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement no. 340506. A full version of the paper is available at https://eprints.cs.univie.ac.at/4456/.

O. Ben-Zwi—Work done while at the University of Vienna.

1 Introduction

As advertising on the web becomes more mature, ad exchanges (AdX) play a growing role as a platform for selling advertisement slots from publishers to advertisers. Following the Yahoo! acquisition of Right Media in 2007, all major web companies, such as Google, Facebook, and Amazon, have created or acquired their own ad exchanges. Other major ad exchanges are provided by the Rubicon Project, OpenX, and AppNexus. In 2012 the total revenue at ad exchanges was estimated to be around two billion dollars [4]. Every time a user visits a web page, the publisher of that web page can ask an ad exchange to auction off the ad slots on this page. Thus, the goods traded at an ad exchange are ad impressions. This process is also known as real-time bidding (RTB). A web page might contain multiple ad slots, which are currently modeled to be sold separately in individual auctions. Individual advertisers typically do not directly participate in these auctions but entrust some ad network to bid on their behalf. When a publisher sends an ad impression to an exchange, the exchange usually contacts several ad networks and runs a (variant of a) second-price auction [13] between them, potentially with a reserve price under which the impression is not sold. An ad network (e.g. Google’s Display Network [6]) might then run a second, “local” auction to determine the allocation of the ad slot among its advertisers. We study this interaction of a central auction at the exchange and local auctions at the ad networks.¹

We develop a game-theoretic model that considers the incentives of the following three parties: (1) the ad exchange, (2) the ad networks, and (3) the advertisers. As the ad exchange usually charges a fixed percentage of the revenue and hands the rest to the publishers, the ad exchange and the publishers have the same objective and can be modeled as one entity. We then study equilibrium concepts of this new model of a three-party exchange. Our model is described as an ad exchange, but it may also model other scenarios with mediators that act between bidders and sellers, as noted already by Feldman et al. [5]. The main differences between our model and earlier models (discussed in detail at the end of this section) are the following: (a) We consider the incentives of all three parties simultaneously. (b) While most approaches in prior work use Bayesian assumptions, we apply worst-case analysis. (c) We allow auctions with multiple heterogeneous items, namely combinatorial auctions, in contrast to the single-item auctions studied so far. Multiple items arise naturally when selling ad slots on a per-impression basis, since there are usually multiple advertisement slots on a web page.

To motivate the incentives of ad networks and exchanges, we compare next their short and long-term revenue considerations, following Mansour et al. [13] and Muthukrishnan [14]. Ad exchanges and ad networks generate revenue as follows: (1) An ad exchange usually receives some percentage of the price paid by the winner(s) of the central auction. (2) An ad network can charge a higher price to its advertisers than it paid to the exchange or it can be paid via direct contracts with its advertisers. Thus both the ad exchange and the ad networks (might) profit from higher prices in their auctions. However, they also have a motivation not to charge too high prices as (a) the advertisers could stick to alternative advertising channels such as long-term contracts with publishers, and (b) there is a significant competition between the various ad exchanges and ad networks, as advertisers can easily switch to a competitor. Thus, lower prices (might) increase advertiser participation and, hence, the long-term revenue of ad exchanges and ad networks. We only consider a single auction (of multiple items) and leave it as an open question to study changes over time. We still take the long-term considerations outlined above into account by assuming that the ad exchange aligns its strategic behavior with its long-term revenue considerations and only desires for each central auction to sell all items.² In our model the incentive of an ad network to participate in the exchange comes from the opportunity to purchase some items at a low price and then resell them at a higher price. However, due to long-term considerations, our model additionally requires the ad networks to “satisfy their advertisers” by faithfully representing the advertisers’ preferences towards the exchange, while still allowing the ad networks to extract revenue from the competition between the advertisers in their network. An example for this kind of restriction for an ad network is Google’s Display Network [6] that guarantees its advertisers that each ad impression is sold via a second-price auction, independent of whether an ad exchange is involved in the transaction or not [13].

To model a stable outcome in a three-party exchange, we use the equilibrium concept of envy-freeness for all three types of participants. A participant is envy-free if he receives his most preferred set of items under the current prices. Envy-freeness for all participants is a natural notion to express stability in a market, as it implies that no coalition of participants would strictly profit from deviating from the current allocation and prices (assuming truthfully reported preferences). Thus an envy-free equilibrium supports stability in the market prices, which in turn facilitates, for example, revenue prediction for prospective participants and hence might increase participation and long-term revenue. For only two parties, i.e., sellers and buyers, where the sellers have no intrinsic value for the items they sell, envy-freeness for all participants is equal to a competitive or Walrasian equilibrium [20], a well established notion in economics to characterize an equilibrium in a market where demand equals supply. We provide a generalization of this equilibrium concept to three parties.

Our Contribution. We introduce the following model for ad exchanges. A central seller wants to sell k items. There are m mediators $\mathcal {M}_i$, each with her own $n_i$ bidders. Each bidder has a valuation function over the items. In the ad exchange setting, the central seller is the ad exchange, the items are the ad slots shown to a visitor of a web page, the mediators are the ad networks, and the bidders are the advertisers. A bidder does not have any direct “connection” to the central seller. Instead, all communication is done through the mediators. A mechanism for allocating the items to the bidders is composed of a central auction with mediators acting as bidders, and then local auctions, one per mediator, in which every mediator allocates the set of items she bought in the central auction; that is, an auction where the bidders of that mediator are the only participating bidders and the items that the mediator received in the central auction are the sole items. The prices of the items obtained in the central auction provide a lower bound for the prices in the local auctions, i.e., they act as reserve prices in the local auctions. We assume that the central seller and the bidders have quasi-linear utilities, i.e., utility functions that are linear in the price, and that their incentive is to maximize their utility. For the central seller this means that his utility from selling a set of slots is just the sum of prices of the items in the set. The utility of a bidder on receiving a set of items S is his value for S minus the sum of the prices of the items in S.

The incentive of a mediator, however, is not so straightforward and needs to be defined carefully. In our model, to “satisfy” her bidders, each mediator guarantees her bidders that the outcome of the local auction will be minimal envy free, that is, for the final local price vector, the item set that is allocated to any bidder is one of his most desirable sets over all possible item sets (even sets that contain items that were not allocated to his mediator, i.e., each bidder is not only locally, but globally envy-free) and there is no (item-wise) smaller price vector that fulfills this requirement. We assume that each mediator wants to maximize her revenue³ and define the revenue of a mediator for a set of items S as the difference between her earnings when selling S with this restriction and the price she has to pay for S at the central auction.

For this model we define a new equilibrium concept, namely the three-party competitive equilibrium. At this equilibrium all three types of participants are envy-free. Envy-free solutions for the bidders always exist, as one can set the prices of all items high enough so that no bidder will demand any item. Additionally, we require that there is no envy for the central seller, meaning that all items are sold. If there were no mediators, then a two-party envy-free solution would be exactly a Walrasian equilibrium, which for certain scenarios can be guaranteed [11]. However, with mediators it is not a-priori clear that a three-party competitive equilibrium exists as, additionally, the mediators have to be envy-free. We show that for our definition of a mediator’s revenue (a) the above requirements are fulfilled and (b) a three-party competitive equilibrium exists whenever a Walrasian equilibrium for the central auction exists or whenever a two-party equilibrium exists for the bidders and the central seller without mediators. Interestingly, we show that for gross-substitute bidder valuations the incentives of this kind of mediator can be represented with an or-valuation over the valuations of her bidders. This then leads to the following result: For gross-substitute bidder valuations a three-party competitive equilibrium can be computed in polynomial time. In particular, we will show how to compute the three-party competitive equilibrium with minimum prices.

Related Work. The theoretical research on ad exchanges was initialized by a survey of Muthukrishnan [14] that lists several interesting research directions. Our approach specifically addresses his 9th problem, namely to enable the advertisers to express more complex preferences that arise when multiple advertisement slots are auctioned off at once as well as to design suitable auctions for the exchange and the ad networks to determine allocation and prices given these preferences.

The most closely related work with respect to the model of the ad exchange is Feldman et al. [5]. It is similar to our work in two aspects: (1) The mediator bids on behalf of her bidders in a central auction and the demand of the mediator as well as the tentative allocation and prices for reselling to her bidders are determined via a local auction. (2) The revenue of the mediator is the price she can obtain from reselling minus the price she paid in the central auction. The main differences are: (a) Only one item is auctioned at a time and thus the mediator can determine her valuation with a single local auction. (b) Their work does not consider the incentives of the bidders, only of the mediators and the central seller. (c) A Bayesian setting is used where the mediators and the exchange know the probability distributions of the bidders’ valuations. Based on this information, the mediators and the exchange choose reserve prices for their second-price auctions to maximize their revenue. The work characterizes the equilibrium strategies for the selection of the reserve prices.

Mansour et al. [13] (mainly) describe the auction at the DoubleClick exchange. Similar to our work advertisers use ad networks as mediators for the central auction. They observe that if mediators that participate in a single-item, second-price central auction are only allowed to submit a single bid, then it is not possible for the central auction to correctly implement a second-price auction over all bidders as the bidders with the highest and the second highest value might use the same mediator. Thus they introduce the Optional Second Price auction, where every mediator is allowed to optionally submit the second highest bid with the highest bid. In such an auction each mediator can guarantee to her bidders that if one of them is allocated the item, then he pays the (global) second-price for it. For the single-item setting, the bidders in their auction and in our auction pay the same price. If the mediator of the winning bidder did not specify an optional second price, then her revenue will equal the revenue of our mediator. If she did, her revenue will be zero and the central seller will receive the gain between the prices in the local and the central auction.

Stavrogiannis et al. [18] consider a game between bidders and mediators, where the bidders can select mediators (based on Bayesian assumptions of each other’s valuations) and the mediators can set the reserve prices in the second-price local auction. The work presents mixed Nash equilibrium strategies for the bidders to select their mediator. In [19] the same authors compare different single-item local auctions with respect to the achieved social welfare and the revenue of the mediators and the exchange.

Balseiro et al. (2013) introduced a setting that does not include mediators [1]. Instead, they see the ad exchange as a game between publishers, who select parameters such as reserve prices for second-price auctions, and advertisers, whose budget constraints link different auctions over time. They introduced a new equilibrium concept for this game and used this to analyze the impact of auction design questions such as the selection of a reserve price. Balseiro et al. (2014) studied a publisher’s trade-off between using an ad exchange versus fulfilling long-term contracts with advertisers [2].

Equilibria in trading networks (such as ad exchanges) are also addressed in the “matching with contracts” literature. Hatfield and Milgrom [10] presented a new model where instead of bidders and items there are agents and trades between pairs of agents. The potential trades are modeled as edges in a graph where the agents are represented by the nodes. Agent valuations are then defined over the potential trades and assumed to be monotone substitute. They proved the existence of an (envy-free) equilibrium when the agent-trades graph is bipartite. Later this was improved to directed acyclic graphs by Ostrovsky [16] and to arbitrary graphs by Hatfield et al. [9]. They did not show (polynomial-time) algorithms to reach equilibria. Our model can be reduced to this model, hence a three-party equilibrium exists when all bidders are monotone gross substitute. The result of this reduction (not stated here) is not polynomial in the number of bidders and items.

2 Preliminaries

Let $\varOmega$ denote a set of k items. A price vector is an assignment of a non-negative price to every element of $\varOmega$. For a price vector $p = (p_1, ..., p_k)$ and a set $S \subseteq \varOmega$ we use $p(S) = \sum _{j \in S} p_j$. For any two price vectors p, r an inequality such as $p \ge r$ as well as the operations $\min (p,r)$ and $\max (p,r)$ are meant item-wise.

We denote with $\langle \varOmega _b\rangle = \langle \varOmega _b\rangle _{b\in \mathcal {B}}$ an allocation of the items in $\varOmega$ such that for all bidders $b \in \mathcal {B}$ the set of items allocated to b is given by $\varOmega _b$ and we have $\varOmega _b \subseteq \varOmega$ and $\varOmega _b \cap \varOmega _{b'} = \emptyset$ for $b' \ne b$, $b' \in \mathcal {B}$. Note that some items might not be allocated to any bidder.

A valuation function $v_b$ of a bidder b is a function from $2^{\varOmega }$ to $\mathbb {R}$, where $2^{\varOmega }$ denotes the set of all subsets of $\varOmega$. We assume throughout the paper $v_b(\emptyset ) = 0$. Unless specified otherwise, for this work we assume monotone valuations, that is, for $S\subseteq T$ we have $v_b(S)\le v_b(T)$. This assumption is made for ease of presentation. We use $\{v_b\}$ to denote a collection of valuation functions. The (quasi-linear) utility of a bidder b from a set $S \subseteq \varOmega$ at prices $p \ge 0$ is defined as $u_{b,p}(S) = v_b(S) - p(S)$. The demand $D_b(p)$ of a bidder b for prices $p \ge 0$ is the set of subsets of items $S \subseteq \varOmega$ that maximize the bidder’s utility at prices p. We call a set in the demand a demand representative. Throughout the paper we omit subscripts if they are clear from the context.

Definition 1

(Envy Free). An allocation $\langle \varOmega _b\rangle$ of items $\varOmega$ to bidders $\mathcal {B}$ is envy free (on $\varOmega$) for some prices p if for all bidders $b \in \mathcal {B}$, $\varOmega _b\in D_b(p)$. We say that prices p are envy free (on $\varOmega$) if there exists an envy-free allocation (on $\varOmega$) for these prices.

There exist envy-free prices for any valuation functions of the bidders, e.g., set all prices to $\max _{b, S} v_b(S)$. For these prices the allocation which does not allocate any item is envy free. Thus also minimal envy-free prices always exist, but are in general not unique.

Definition 2

(Walrasian Equilibrium (WE)). A Walrasian equilibrium (on $\varOmega$) is an envy-free allocation $\langle \varOmega _b\rangle$ (on $\varOmega$) with prices p such that all prices are non-negative and the price of unallocated items is zero. We call the allocation $\langle \varOmega _b\rangle$ a Walrasian allocation (on $\varOmega$) and the prices p Walrasian prices (on $\varOmega$).

We assume that the central seller has a value of zero for every subset of the items; thus (with quasi-linear utility functions) selling all items makes the seller envy free. In this case a Walrasian equilibrium can be seen as an envy-free two-party equilibrium, i.e., envy free for the buyers and the seller. Note that for a Walrasian price vector there might exist multiple envy-free allocations.

2.1 Valuation Classes

A unit demand valuation assigns a value to every item and defines the value of a set as the maximum value of an item in it. An additive valuation also assigns a value to every item but defines the value of a set as the sum of the values of the items in the set. Non-negative unit demand and non-negative additive valuations both have the gross-substitute property (defined below) and are by definition monotone.

Definition 3

(Gross Substitute (GS)). A valuation function is gross substitute if for every two price vectors $p^{(2)} \ge p^{(1)} \ge 0$ and every set $D^{(1)} \in D(p^{(1)})$, there exists a set $D^{(2)} \in D(p^{(2)})$ with $j \in D^{(2)}$ for every $j \in D^{(1)}$ with $p^{(1)}_j = p^{(2)}_j$.

For gross-substitute valuations of the bidders a Walrasian equilibrium is guaranteed to exist in a two-sided market [11] and can be computed in polynomial time [15, 17]. Further, gross substitute is the maximal valuation class containing the unit demand class for which the former holds [7]. Several equivalent definitions are known for this class [7, 17]. We will further use that for gross-substitute valuations the Walrasian prices form a complete lattice [7].

We define next an $\textsc {or}$-valuation. Lehmann et al. [12] showed that the $\textsc {or}$ of gross-substitute valuations is gross substitute.

Definition 4

(OR-player). The $\textsc {or}$ of two valuations v and w is defined as $(v\;\textsc {or}\; w)(S) = \max _{R, T \subseteq S, R \cap T = \emptyset }(v(R) + w(T))$. Given a set of valuations $\{v_b\}$ for bidders $b \in \mathcal {B}$ we say that the $\textsc {or}$-player is a player with valuation $v_{\textsc {or}}(S) = \max _{\langle S_b\rangle } \sum _{b \in \mathcal {B}} v_b(S_b)\,.$

3 Model and Equilibrium

There are k items to be allocated to m mediators. Each mediator $\mathcal {M}_i$ represents a set $\mathcal {B}_i$ of bidders, where $|\mathcal {B}_i|=n_i$. Each bidder is connected to a unique mediator. Each bidder has a valuation function over the set of items and a quasi-linear utility function. A central auction is an auction run on all items with mediators as bidders. After an allocation $\langle \varOmega _i\rangle$ and prices r at the central auction are set, another m local auctions are conducted, one by each mediator. In the local auction for mediator $\mathcal {M}_i$ the items $\varOmega _i$ that were allocated to her in the central auction are the sole items and the bidders $\mathcal {B}_i$ are the sole bidders. A solution is an assignment of central-auction and local-auction prices to items and an allocation of items to bidders and hence, by uniqueness, also to mediators. We define next a three-party equilibrium based on envy-freeness.

Definition 5

(Equilibrium). A three-party competitive equilibrium is an allocation of items to bidders and a set of $m+1$ price vectors $r,p^1,p^2,\ldots ,p^m$ such that the following requirements hold. For $1 \le i \le m$

• 1. every mediator⁴ $\mathcal {M}_i$ is allocated a set $\varOmega _i$ in her demand at price r,

• 2. every item j with non-zero price r is allocated to a mediator,

• 3. the price $p^i$ coincides with r for all items not in $\varOmega _i$,

• 4. and every bidder $b\in \mathcal {B}_i$ is allocated a subset of $\varOmega _i$ that is in his demand at price $p^i$.

In other words, the allocation to the bidders in $\mathcal {B}_i$ with prices $p^i$ must be envy-free for the bidders, the allocation to the mediators with prices r must be envy free for the mediators and for the central seller, i.e., must be a Walrasian equilibrium; and the prices $p^i$ must be equal to the prices r for all items not assigned to mediator $\mathcal {M}_i$.

Note that the allocation of the items to the mediators and prices r are the outcome of a central auction run by the central seller, while the allocation to the bidders in $\mathcal {B}_i$ and prices $p^i$ correspond to the outcome of a local auction run by mediator $\mathcal {M}_i$. These auctions are connected by the demands of the mediators and Requirement 3.

We next present our mediator model. The definition of an Envy-Free Mediator, or $\textsc {ef}$-mediator for short, reflects the following idea: To determine her revenue for a set of items S at central auction prices r, the mediator simulates the local auction she would run if she would obtain the set S at prices r. Given the outcome of this “virtual auction”, she can compute her potential revenue for S and r as the difference between the virtual auction prices of the items sold in the virtual auction and the central auction prices for the items in S. However, as motivated in the introduction, the mediator is required to represent the preferences of her bidders and therefore not every set S is “allowed” for the mediator, that is, for some sets the revenue of the mediator is set to $-1$. The sets that maximize the revenue are then in the demand of the mediator at central auction prices r. To make the revenue of a mediator well-defined and to follow our motivation that a mediator should satisfy her bidders, the virtual auctions specifically compute minimal envy-free price vectors.

Definition 6

(Envy-Free Mediator). An $\textsc {ef}$-mediator $\mathcal {M}_i$ determines her demand for a price vector $r \ge 0$ as follows. For each subset of items $S \subseteq \varOmega$ she runs a virtual auction with items S, her bidders $\mathcal {B}_i$, and reserve prices r. We assume that the virtual auction computes minimal envy-free prices $p^S \ge r$ and a corresponding envy-free allocation $\langle S_b\rangle$.⁵ We extend the prices $p^S$ to all items in $\varOmega$ by setting $p^S_j = r_j$ for $j \in \varOmega \setminus S$, and define the revenue $R_{i,r}(S)$ of the mediator for a set S as follows. If the allocation $\langle S_b\rangle$ is envy free for the bidders $\mathcal {B}_i$ and prices $p^S$ on $\varOmega$, then $R_{i,r}(S) = \sum _{b \in \mathcal {B}_i} p^S(S_b) - r(S)$; otherwise, we set $R_{i,r}(S) = -1$. The demand $D_{i}(r)$ of $\mathcal {M}_i$ is the set of all sets S that maximize the revenue of the mediator for the reserve prices r. The local auction of $\mathcal {M}_i$ for a set $\varOmega _i$ allocated to her in the central auction at prices r is equal to her virtual auction for $\varOmega _i$ and r.

Following the above definition, we say that a price vector is locally envy free if it is envy free for the bidders $\mathcal {B}_i$ on the subset $\varOmega _i \subseteq \varOmega$ assigned to mediator $\mathcal {M}_i$ and globally envy free if it is envy free for the bidders $\mathcal {B}_i$ on $\varOmega$. Note that if $p^S$ is envy free on $\varOmega$, then it is minimal envy free $\ge r$ on $\varOmega$ for the bidders $\mathcal {B}_i$.

An interesting property of $\textsc {ef}$-mediators is that every Walrasian equilibrium in the central auction can be combined with the outcome of the local auctions of $\textsc {ef}$-mediators to form a three-party competitive equilibrium.

Theorem 1

Assume all mediators are $\textsc {ef}$-mediators. Then a Walrasian equilibrium in the central auction with allocation $\langle \varOmega _i \rangle$ together with the allocation and prices computed in the local auctions of the mediators $\mathcal {M}_i$ on their sets $\varOmega _i$ (not necessarily Walrasian) form a three-party competitive equilibrium.

Further, with $\textsc {ef}$-mediators a three-party competitive equilibrium exists whenever a Walrasian eq. exists for the bidders and items without the mediators.

Theorem 2

Assume all mediators are $\textsc {ef}$-mediators and a Walrasian equilibrium exists for the set of bidders and items (without mediators). Then there exists a three-party competitive equilibrium.

The proof of Theorem 2 only shows the existence of trivial three-party equilibria that basically ignores the presence of mediators. However, three-party equilibria and $\textsc {ef}$-mediators allow for richer outcomes that permit the mediators to gain revenue from the competition between their bidders while still representing the preferences of their bidders towards the central seller. In the next section we show how to find such an equilibrium provided that the valuations of all bidders are gross substitute. Recall that gross-substitute valuations are the most general valuations that include unit demand valuations for which a Walrasian equilibrium exists [7]; and that efficient algorithms for finding a Walrasian equilibrium are only known for this valuation class.

4 An Efficient Algorithm for Gross-substitute Bidders

In this section we will show how to find, in polynomial time, a three-party competitive equilibrium if the valuations of all bidders are gross substitute. The prices the bidders have to pay at equilibrium, and thus the utilities they achieve, will be the same as in a Walrasian equilibrium (between bidders and items) with minimum prices (see full version). The price the bidders pay is split between the mediators and the exchange. We show how to compute an equilibrium where this split is best for the mediators and worst for the exchange. In turn the computational load can be split between the mediators and the exchange as well. The algorithm will be based on existing algorithms to compute Walrasian equilibria for gross-substitute bidders.

The classical (two-party) allocation problem is the following: We are given k items and n valuation functions and we should find an equilibrium allocation (with or without equilibrium prices) if one exists. Recall that in general a valuation function has a description of size exponential in k. Therefore, the input valuation functions can only be accessed via an oracle, defined below. An efficient algorithm runs in time polynomial in n and k (where the oracle access is assumed to take constant time).

Given an algorithm that computes a Walrasian allocation for gross-substitute bidders, by a result of Gul and Stacchetti [7] minimum Walrasian prices can be computed by solving the allocation problem $k+1$ times. A Walrasian allocation can be combined with any Walrasian prices to form a Walrasian equilibrium [7]. Thus we can assume for gross-substitute valuations that a polynomial-time algorithm for the allocation problem also returns a vector of minimum prices that support the allocation.

Two main oracle definitions that were considered in the literature are the valuation oracle, where a query is a set of items S and the oracle replies with the exact value of S; and the demand oracle, where a query is a price vector p and the oracle replies with a demand representative D [3].

It is known that a demand oracle is strictly stronger than a valuation oracle, i.e., a valuation query can be simulated by a polynomial number of demand queries but not vice versa. For gross-substitute valuations, however, these two query models are polynomial-time equivalent, see Paes Leme [17]. The two-party allocation problem is efficiently solvable for gross-substitute valuations [15, 17].

We define the three-party allocation problem in the same manner. We are given k items, n valuation functions over the items and m mediators, each associated with a set of unique bidders. We are looking for a three-party equilibrium allocation (and equilibrium prices) if one exists. We will assume that the input valuations are given through a valuation oracle.

The algorithm will be based on the following central result: For gross substitute valuations of the bidders an $\textsc {ef}$-mediator and an $\textsc {or}$-player over the valuations of the same bidders are equivalent with respect to their demand and their allocation of items to bidders. Thus in this case $\textsc {ef}$-mediators can be considered as if they have a gross-substitute valuation. Note that for general valuations this equivalence does not hold.

Theorem 3

If the valuation functions of a set of bidders $\mathcal {B}_i$ are gross substitute, then the demand of an $\textsc {ef}$-mediator for $\mathcal {B}_i$ is equal to the demand of an $\textsc {or}$-player for $\mathcal {B}_i$. Moreover, the allocation in a virtual auction of the $\textsc {ef}$-mediator for reserve prices r and a set of items S in the demand is an optimal allocation for the $\textsc {or}$-player for S and r and vice versa.

To this end, we will first show for the virtual (and local) auctions that a modified Walrasian equilibrium, the reserve-we(r), exists for gross-substitute valuations with reserve prices. For this we will use yet another reduction to a (standard) Walrasian equilibrium without reserve prices but with an additional additive player⁶.

Definition 7

(Walrasian Equilibrium with Reserve Prices r (RESERVE-WE(r)) [8]). A Walrasian equilibrium with reserve prices $r \ge 0$ (on $\varOmega$) is an envy-free allocation $\langle \varOmega _b\rangle$ (on $\varOmega$) with prices p such that $p\ge r$, and the price of every unallocated item is equal to its reserve price, i.e., $p_j = r_j$ for $j \not \in \cup _b \varOmega _b$. We say that $\langle \varOmega _b\rangle$ is a reserve-we(r) allocation (on $\varOmega$) and p are reserve-we(r) prices (on $\varOmega$).

4.1 Properties of Walrasian Equilibria with Reserve Prices

In this section we generalize several results about Walrasian equilibria to Walrasian equilibria with reserve prices. Similar extensions were shown for unit demand valuations in [8].

We first define a suitable linear program. The reserve-lp(r) is a linear program obtained from a reformulation of the dual of the LP-relaxation of the welfare maximization integer program after adding reserve prices $r \ge 0$. More details on this reformulation are given in the full version of the paper.

For an integral solution to the reserve-lp(r) we can interpret this reformulation as a solution to a welfare-lp with an additional additive player whose value for an item is equal to that item’s reserve price. We will use this interpretation to extend known results for Walrasian equilibria to Walrasian equilibria with reserve prices. The results are summarized in Theorem 4 below. We use the following definition.

Definition 8

(Additional Additive Player). Let $\{v_b\}$ be a set of valuation functions over $\varOmega$ for bidders $b \in \mathcal {B}$, and let $r \ge 0$ be reserve prices for the items in $\varOmega$. Let $\{v'_{b'}\}$ be the set of valuation functions when an additive bidder a is added, i.e., for the bidders $b' \in \mathcal {B}' = \mathcal {B}\cup \{a\}$ with $v'_{b'}(S) = v_{b'}(S)$ for ${b'} \ne a$ and $v'_a(S) = \sum _{j \in S} r_j$ for all sets $S \subseteq \varOmega$. For an allocation $\langle \varOmega _b \rangle _{b \in \mathcal {B}}$ we define $\langle \varOmega '_{b'} \rangle _{b' \in \mathcal {B}'}$ with $\varOmega '_{b'} = \varOmega _{b'}$ for ${b'} \ne a$ and $\varOmega '_a = \varOmega \setminus \cup _b \varOmega _b$.

Theorem 4

(a) The allocation $\langle \varOmega _b \rangle$ and the prices p are a reserve-we(r) for $r \ge 0$ and bidders $\mathcal {B}$ if and only if the allocation $\langle \varOmega '_{b'} \rangle$ and prices $p'$ are a we for the bidders $\mathcal {B}'$, where we have $p_j = p'_j$ for $j \in \cup _{b \in \mathcal {B}} \varOmega _b$ and $p_{j'} = r_{j'}$ for ${j'} \in \varOmega \setminus \cup _{b \in \mathcal {B}} \varOmega _b$ (a1). The allocation $\langle \varOmega _b \rangle$ is a reserve-we(r) allocation if and only if $\langle \varOmega _b \rangle$ is an integral solution to the reserve-lp(r) (a2).

(b) If the valuations $\{v\}$ are gross substitute, then (b1) there exists a reserve-we(r) for $\{v\}$ and (b2) the reserve-we(r) price vectors form a complete lattice.

Theorem 4 will be used in the next section to characterize the outcome of the virtual auctions of an $\textsc {ef}$-mediator. It also provides a polynomial-time algorithm to compute a reserve-we(r) when the bidders in $\mathcal {B}$ have gross-substitute valuations, given a polynomial-time algorithm for a we for gross-substitute bidders.

4.2 The Equivalence of the EF-mediator and the OR-player for Gross-substitute Valuations—Proof Outline

In this section we outline the proof of Theorem 3, the complete proof can be found in the full version of the paper. The proof proceeds as follows. We first characterize the demand of an $\textsc {ef}$-mediator for bidders with gross-substitute valuations. As a first step we show that for such bidders an $\textsc {ef}$-mediator actually computes a reserve-we(r) with minimum prices in each of her virtual auctions. The minimality of the prices implies that whenever the virtual auction prices for an item set S are globally envy-free, they are also minimum reserve-we(r) prices for the set of all items $\varOmega$ and the bidders in $\mathcal {B}_i$. Thus, given reserve prices r, all virtual auctions of an $\textsc {ef}$-mediator result in the same price vector p as long as they are run on a set S with non-negative revenue. With the help of some technical lemmata we then completely characterize the demand of an $\textsc {ef}$-mediator and show that the mediator does not have to run multiple virtual auctions to determine her demand; it suffices to run one virtual auction on $\varOmega$ where the set of allocated items is a set in the demand of the $\textsc {ef}$-mediator. Thus for gross-substitute bidders the mediator can efficiently answer demand queries and compute the outcome of her local auction.

Finally we compare the utility function of the $\textsc {or}$-player to the optimal value of the reserve-lp(r) to observe that they have to be equal (up to an additive constant) for item sets that are in the demand of the $\textsc {or}$-player. Combined with the above characterization of the demand of the mediator, we can then relate both demands at central auction prices r to optimal solutions of the reserve-lp(r) for r and $\varOmega$ and hence show the equality of the demands for these two mediator definitions for gross-substitute valuations of the bidders. Recall that an $\textsc {or}$-player over gross-substitute valuations has a gross-substitute valuation [12]. Thus in this case we can regard the $\textsc {ef}$-mediator as having a gross-substitute valuation. This implies that a Walrasian equilibrium for the central auction exists and, with the efficient demand oracle defined above, can be computed efficiently when all bidders have gross-substitute valuations and all mediators are $\textsc {ef}$-mediators.

4.3 Computing an Equilibrium

The basic three-party auction is simple: First run the central auction at the exchange, then the local auctions at the mediators. In this section we summarize the details and analyze the time needed to compute a three-party competitive equilibrium. We assume that all bidders have gross-substitute valuations and that their valuations can be accessed via a demand oracle. We assume, for simplicity, that there are m $\textsc {ef}$-mediators, each with n/m distinct bidders. We will use known polynomial-time auctions for the two-party allocation problem, see [17] for a recent survey. Theorem 4 shows how such an auction can be modified to yield a reserve-we(r) instead of a Walrasian equilibrium.

Let A be a polynomial-time algorithm that can access n gross-substitute valuations over k items $\varOmega$ via a demand oracle and outputs a Walrasian price vector $p\in \mathbb {R}^k$ and a Walrasian allocation $\langle \varOmega _i \rangle _{i\in [n]}$. Let the runtime of A be $T(n,k) = O(n^{\alpha }k^{\beta })$ for constants $\alpha$, $\beta$.

Although we can assume oracle access to the bidders’ valuations, we cannot assume it for the mediators’ (gross-substitute) valuations, as they are not part of the input. However, as outlined in the previous section, a mediator can determine a set in her demand by running a single virtual auction to compute a reserve-we(r), i.e., there is an efficient demand oracle for the mediators. Hence, solving the allocation problem for the central auction can be done in time $T(m,k) \cdot T(n/m,k) = O(n^{\alpha }k^{2\beta })$. Further, the local auctions for all mediators take time $O(m \cdot T(n/m,k))$ and thus the total time to compute a three-party competitive equilibrium is $O(n^{\alpha }k^{2\beta })$.⁷

5 Short Discussion

We proposed a new model for auctions at ad exchanges. Our model is more general than previous models in the sense that it takes the incentives of all three types of participants into account and that it allows to express preferences over multiple items. Interestingly, at least when gross-substitute valuations are considered, this generality does not come at the cost of tractability, as shown by our polynomial-time algorithm. Note that this is the most general result we could expect in light of the classical (two-sided) literature on combinatorial auctions.⁸