The Power of Media Agencies in Ad Auctions: Improving Utility through Coordinated Bidding

1 Introduction

Over the last years, digital advertising has been one of the main drivers of the growth of world market. Remarkably, the vast majority of the companies employ digital tools to advertise their products or services, and the worldwide annual spent in digital advertising reached about 150 billion USD in 2020 [IAB, 2021]. Furthermore, most of the economic reports forecast that artificial intelligence (AI) will fuel an increase of market value by almost 100% over the next decade [Chui et al., 2018]. Indeed, AI tools have become widespread throughout digital advertising, enabling new opportunities that were not available before. Notable examples are in, e.g., auction design [Bachrach et al., 2014; Castiglioni et al., 2022a], budget allocation [Nuara et al., 2018], bidding opimization [He et al., 2013; Castiglioni et al., 2022b], and multi-channel advertising [Nuara et al., 2019].

Recent years have witnessed a proliferation of media agencies, which claim to play the role of intermediaries between advertisers and platforms selling ad slots. This has been driven by the increasing complexity of digital advertisingdue to, e.g., a huge amount of available data and of parameters to be set on advertising platforms-and the rising competition among a growing number of advertisers. When a group of competing advertisers is managed by a common agency, it frequently happens that the agency has to place bids on behalf of different advertisers participating in the same ad auction. This dramatically changes the strategic interaction underlying ad auctions, since agencies can coordinate advertisers' bidding strategies by implementing many forms of collusionsuch as, e.g., bid rigging-, increasing advertisers' value. In particular, simple examples show that colluding in ad auctions can reward the colluders with a utility that is arbitrarily larger than what they would get without doing that. Moreover, a recent empirical study on real-world data by one of the major US agencies (Aegis-Dentsu-Merkle) shows that collusion is pervasive and leads to a significant reduction in the average cost-per-click [Decarolis and Rovigatti, 2017].

Original Contributions. We study the computational problem faced by a media agency that has to coordinate the bidding strategies of a group of colluders, under GSP and VCG mechanisms (details on the adoption of such mechanisms in ad auctions are provided in [Varian and Harris, 2014]). We assume that the media agency knows the private valuations of the colluders (i.e., how much they value a click on their ad), and that it decides colluders' bids on their behalf. Moreover, the media agency is in charge of paying the auction mechanism for a click on an allocated ad, and at the same time it requires monetary transfers to and from the colluders.

These are necessary to enforce some individual rationality constraints ensuring that the colluders do not leave the agency and participate in the ad auction individually. In this paper, we study two settings that differ for the kind of monetary transfers that they allow for: the arbitrary transfers setting, where any kind of monetary transfer to and from the advertisers is allowed, and the more realistic limited liability setting, in which no advertiser can be paid by the media agency. Finally, we assume that the bids of the advertisers external to the media agency are drawn according to some probability distribution. As a first result, we introduce an abstract bid optimization problem, called weighted utility problem (WUP), which works for any finite set of possible bid values and is useful in proving our main results in the rest of the paper. In order to solve such a problem, we first show that the utilities of bidding strategies are related to the length of paths in a directed acyclic weighted graph, whose structure and weights depend on the mechanism under study (either GSP or VCG mechanism). This allows us to solve WUP instances in polynomial time by finding a shortest path of the graph. Next, we switch the attention to the original media agency problem, starting from the arbitrary transfers setting. A major challenge is dealing with a potentially continuous set of possible bids. Notably, we show that it is possible to reduce the attention to a finite set of bidding strategies, only incurring in a small additive loss in the value of the obtained solution and relaxing the incentive constraints by a small additive amount. The set is built by recursively splitting the interval of possible bid values, until one gets sub-intervals such that the probability that an external bid is in a given sub-interval is sufficiently small. Then, the resulting sub-intervals are used to define the desired finite set of bids. In conclusion, we cast the problem as a WUP instance and solve it by our graph-based algorithm in polynomial time. This gives a bi-criteria additive FPTAS for the original problem, since the (additive) approximation is in terms of both objective value and incentive constraints. Finally, we study the limited liability setting. In this case, we leverage the same finite set of bidding strategies defined for the arbitrary transfers setting in order to formulate the problem as a linear program (LP) with exponentially-many variables and polynomially-many constraints. Since we use only a finite set of bids, we need to relax the individual rationality constraints by an arbitrary small amount to guarantee the existence of a feasible solution. We solve such an LP in polynomial time by applying the ellipsoid algorithm [Gr¨otschel et al., 1981] to its dual, which features polynomially-many variables and exponentially-many constraints. This requires solving a suitable separation problem in polynomial time, which can be done by reducing it to a WUP instance. As in the arbitrary transfer setting, the resulting algorithm is a bi-criteria additive FPTAS.

Related Works. While a longstanding literature investigates the role of mediators in ad auctions-see, e.g., the seminal works by Vorobeychik and Reeves [2008] and Ashlagi et al. [2009]-, collusion is currently emerging as one of the central problems in advertising, as the adoption of AI algorithms can concretely support an agency to find the best collusive behaviors [OECD, 2017]. Motivated by the recent study by Decarolis and Rovigatti [2017], some works provide theoretical contributions to assess how collusion can be conducted by an agency. Decarolis et al. [2020] study a setting in which there is no monetary transfer between the agency and bidders by providing equilibrium conditions. They show that, in simple settings, GSP is more inefficient than VCG, both in terms of efficiency and revenue. Lorenzon [2018] studies a setting with two slots and three bidders that are all controlled by an agency in a GSP auction. Furthermore, a monetary transfer is possible. The author shows collusive stable behaviors in which the redistribution is uniform over the three bidders.

2 Preliminaries

We study the problem of coordinated bidding faced by a media agency in ad auctions, with both GSP and VCG payments. In this setting, the set N := {1, . . . , n} of bidders (or agents) is partitioned as N := Nc∪Ne, where: Nc is a set of advertisers whose advertising campaigns are managed by a common media agency, while Ne is a set of advertisers that are not part of the agency, but participate in the ad auction individually. In this work, we refer to the former as colluders, while we call the latter external agents. Moreover, we let nc := |Nc| and ne := |Ne| be the numbers of colluders and external agents, respectively. The advertisers compete for displaying their ads on a set M := {1, ...,m} of slots, with m ≤ n. Each agent i ∈ N has a private valuation vi ∈ [0, 1] for an advertising slot, which reflects how much they value a click on their ad. Furthermore, each slot j ∈ M is associated with a click through rate parameter λj ∈ [0, 1], encoding the probability with which the slot is clicked by a user. 1 Each agent i ∈ N participates in the ad auction with a bid bi ∈ [0, 1], representing how much they are willing to pay for a click on their ad. We denote by b = (bi)i∈N the bid profile made by all the agents' bids. We also let bc = (bi)i∈Nc be the profile of colluders' bids (also called bidding strategy), while be = (bi)i∈Ne is the profile of external agents' bids. For the ease of notation, we sometimes write b = (bc , be ) to denote the profile made by all the bids in bc and be .

The media agency knows the valuations vi of all the colluders i ∈ Nc, and it decides the bid profile bc on their behalf. Additionally, the media agency defines a monetary transfer qi ∈ [-1, 1] for each colluder i ∈ Nc. We adopt the convention that, if qi > 0, then the transfer is from the agent to the agency, while, if qi < 0, then it is the other way around. 2

W.l.o.g., we assume that the slots are ordered in decreasing value of click through rate, so that λ1 ≥ . . . ≥ λm. Moreover, for the ease of presentation, we let λm+1 = . . . = λn+1 = 0.

The auction goes on as follows. First, the media agency selects a bidding strategy bc = (bi)i∈Nc and requires a transfer qi from each colluder i ∈ Nc. Then, external agents individually report their bids to the auction mechanism, resulting in a profile be = (bi)i∈Ne , while the media agency reports bids bc on behalf of the colluders. Finally, given all the agents' bids b = (bc , be ), the mechanism allocates an ad to each slot and defines an expected payment πi(b) ∈ [0, 1] for each agent i ∈ N, where the expectation is with respect to the clicks. The media agency is responsible of paying the auction mechanism on behalf of the colluders.

1 For the ease of presentation, we assume that the click through rate only depends on the slot and not on the ad being displayed. This dependence can be easily captured by interpreting vi as an expected value w.r.t. clicks once the user observed the slot.

2 Notice that there are some scenarios in which it is in the interest of the media agency to pay a colluder in order to ensure that they stay in the agency; see Example 2 in [Romano et al., 2022].

Given a bid profile b = (bi)i∈N, assuming w.l.o.g. that each bidder i ∈ [m] is assigned to slot i (by re-labeling bidders accordingly), we denote bidder i's expected revenue as ri(b) := λivi, while bidder i's expected utility is ui(b) := ri(b) - qi. 3 Instead, the expected utility of the agency is ∑i∈Nc (qi-πi(b)). We also denote with U the cumulative expected utility of all the colluders and the media agency. Formally, it holds U := ∑i∈Nc (ri(b) -πi(b)).

Next, we review GSP and VCG mechanisms in ad auctions (see the book by Nisan and Ronen [2001] for their general description). Given a bid profile b = (bi)i∈N , assuming w.l.o.g. that b1 ≥ . . . ≥ bn (by re-labeling bidders accordingly), both mechanisms orderly assign the first m agents, who are those with the highest bids, to the first m slots, which are those with the highest click through rates. Moreover, the mechanisms assign the following expected payments.

• GSP mechanism: πGSP i (b) := λibi+1 for each agent i ∈ [m], and πGSP i (b) = 0 for all the other agents.
• VCG mechanism: πVCG i (b) := ∑m+1 j=i+1 bj(λj-1 - λj) for each agent i ∈ [m], and πVCG i (b) = 0 for the others.

The VCG payments are such that each agent is charged a payment that is equal to the externalities that they impose on other agents. This makes the VCG mechanism truthful, which means that it is a dominant strategy for each agent to report their true valuation to the mechanism, namely bi = vi for every i ∈ N. This is not the case for the GSP mechanism.

3 ProblemFormulation

In this section, we introduce the optimization problem faced by the media agency. In words, the goal of the media agency is to find a bidding strategy bc = (bi)i∈Nc that coordinates colluders' bids in a way that maximizes the cumulative expected utility U, while at the same time guaranteeing that they are incentivized to be part of the media agency. The rest of the section is devoted to formally defining such a problem.

Before introducing the optimization problem, let us notice that knowing the valuations of all the colluders allows the media agency to improve the cumulative expected utility U with respect to the case in which all the bidders act individually. This is formalized by the following proposition, whose proof readily follows from Example 1 in [Romano et al., 2022].

Proposition 1. The cumulative expected utility U may be arbitrarily larger than the sum of the colluders' expected utilities when they participate in the ad auction individually.

In general, the media agency may adopt a randomized bidding strategy in order to maximize U. By letting Bc be the set of all the possible colluders' bid profiles bc = (bi)i∈Nc , we denote by γ ∈ Γ any randomized bidding strategy, where Γ is the set of all the probability distributions over Bc . Moreover, whenever γ ∈ Γ has a finite support, we denote with γbc the probability of choosing a bidding strategy bc ∈ Bc .

3 We denote with [m] the set {1, . . . ,m}.

In this work, unless stated otherwise, we consider the case in which the bid profile be = (bi)i∈Ne of the external agents is drawn from a probability distribution γ e . Then, we define the expected revenue of bidder i ∈ Nc for any bidding strategy bc ∈ Bc as ˜ ri(bc ) := Ebe∼γ eri(bc , be ), while their expected payment is as ˜πi(bc ) := Ebe∼γ eπi(bc , be ). In the rest of the paper, we assume that all algorithms have access to an oracle that returns the value of the expectations ˜ ri(bc ) and ˜πi(bc ), for a bidding strategy bc ∈ Bc given as input. 4

The following Problem (1) encodes the maximization problem faced by the media agency, where the meaning of IR and AIR constraints is described in the following.

The elements of Problem (1) are defined as follows.

Objective (1a) encodes the cumulative expected utility U of the colluders and the media agency, in expectation with respect to the randomized bidding strategy γ.

Constraints (1b), which are called individual rationality (IR) constraints, ensure that the colluders are incentivized to be part of the media agency, rather than leaving it and participating in the ad auction as external agents. In particular, they guarantee that each colluder i ∈ Nc achieves at least a minimum expected utility ti, where the values ti ∈ [0, 1] for i ∈ Nc are given as input. 5

Constraint (1c) is an agency individual rationality (AIR) constraint which provides guarantees over the utility of the media agency. Since the agency corresponds to the mechanism a payment ∑i∈Nc Ebc∼γ[˜πi(bc )] in expectation over the clicks, the constraint requires that the sum of transfers ∑i∈Nc qi covers the payment, so that the expected utility attained by the agency is non-negative.

In the following, we sometimes relax IR constraints by using δ-IR constraints, for δ > 0, which are defined as follows:

In the following, we call the scenario described so far, in which transfers qi could be negative, the arbitrary transfers

4 Our results can be easily extended-only incurring in a small additive loss in cumulative expected utility-to the case in which the distribution γ e is unknown, but the algorithms have access to a black-box oracle that returns i.i.d. samples drawn according to γ e (rather than returning expected values).

5 To the best of our knowledge, in the literature there is only one work by Bachrach [2010] that formalizes IR constraints for a setting that is similar to ours. Bachrach [2010] takes inspiration from the concept of core [Peleg and Sudh¨olter, 2007] in cooperative games in order to define suitable IR constraints. However, this approach has many downsides. The most relevant issue of such an approach is that it is not computationally viable, since computing the core would require exponential time in the number of colluders.

setting. Monetary transfers from the media agency to the agents are not always feasible in practice. Indeed, in some real-world scenarios a media agency could potentially lose customers by adopting a strategy for which some agents pay and some others are paid for participating in the same auction. For these reasons, we introduce and study a second scenario, which we call transfers with limited liability setting, where no agent is paid by the agency. In such setting, Problem (1) is augmented with the following additional limited liability (LL) constraints on the monetary transfers qi:

As we show in Section 5, there always exists an optimal solution to Problem (1) without LL constraints that is not randomized. The same does not hold for the problem with LL constraints, in which an optimal bidding strategy may be randomized, as in Example 3 in [Romano et al., 2022].

We conclude by introducing the following assumption on the values ti, guaranteeing that Problem (1) is feasible. 6

Assumption 1. There always exists a bidding strategy bc ∈ Bc such that ˜ ri(bc ) - ˜πi(bc ) ≥ ti for all i ∈ Nc.

Proposition 2. With Assumption 1, Problem (1) with LL constraints admits a non-randomized feasible solution.

4 Weighted Utility Problem

In this section, we provide a polynomial-time algorithm for an abstract bid optimization problem, called weighted utility problem (WUP). This will be crucial in the following sections

in order to solve Problem (1) with or without LL constraints. Let ∆ := {δ1, . . . , δd} be a discrete set of d different bid values, with δ1 ≥ . . . ≥ δd. Moreover, given a bidding strategy bc = (bi)i∈Nc ∈ Bc such that bi ∈ ∆ for all i ∈ Nc, we write bc ∈ Bc∆ to denote that each bi belongs to ∆.

Then, WUP reads as follows:

where ˆ yi ≥ 0 for i ∈ Nc and ˆx ≥ 0 are give problem parameters. A solution to Problem (4) is a bidding strategy bc ∈ Bc∆ that maximizes the sum of suitable weighted utilities of the colluders, which are defined so that colluder i's expected revenue ˜ ri(b) is weighted by coefficient ˆ yi, while their expected payment ˜πi(b) is weighted by coefficient ˆx. Notice that, when ˆ yi = 1 for all i ∈ Nc and ˆx = 1, then the objective of Problem (4) coincides with the cumulative expected utility U.

6 All the omitted proofs can be found in [Romano et al., 2022].

As a first step, we consider Problem (4) in which the profile of external agents' bids be is fixed, which reads as follows:

For the sake of presentation, we first provide our results for Problem (5), and, then, we show how they can be extended to Problem (4), where the bids of external agents are stochastic. Thus, in the rest of the section, we always assume that a profile of external agent's bids be = (bi)i∈Ne is given.

The main idea underpinning our results is to map Problem (4) into a shortest path problem [Dijkstra, 1959]. Specifically, we show that the weighted utilities of bidding strategies are related to the length of paths in a particular directed acyclic weighted graph, whose structure and weights derive from the considered auction mechanism. The following lemma is crucial for the construction of the graph.

Lemma 1. Given any bidding strategy bc = (bi)i∈Nc ∈ Bc∆ that is optimal for Problem (5), it holds bi ≥ bj for every pair of colluders i, j ∈ Nc such that ˆ yivi ≥ ˆ yj vj .

In the rest of this section, for the ease of notation and w.l.o.g. thanks to Lemma 1, we re-label bidders in N so that Nc := {1, . . . , nc} and ˆ yivi ≥ ˆ yjvj for any i, j ∈ Nc : i < j. Moreover, w.l.o.g., we also re-label external agents so that Ne := {nc + 1, . . . , n} and bi ≥ bj for any i, j ∈ Ne : i < j. We build the graph as follows (see Figure 1).

• The set of vertices V contains dnc nodes, plus a source node s and a sink node s′ . In particular, there are d nodes for each colluder, one for each possible bid value. For every i ∈ Nc and δj ∈ ∆, we let (i, δj) be the node corresponding to colluder i and bid value δj. Intuitively, selecting a path passing through such a node encodes the fact that the bid bi of colluder i is set to value δj.
• The set of arcs A has cardinality O(d2nc). In particular, the source node s is connected to all the nodes (1, δj) (for δj ∈ ∆), while all nodes (nc, δj) (for δj ∈ ∆) are connected to the sink node s′ . Moreover, for every i ∈ Nc \ {nc} and δj ∈ ∆, node (i, δj) is connected to all nodes (i +1, δj ′ ) such that δj ′ ∈ ∆ and j ′ ≥ j. Intuitively, each path in the graph going from s to s′ defines a bidding strategy bc = (bi)i∈Nc ∈ Bc∆ such that bi ≥ bj for every i, j ∈ Nc with ˆ yivi ≥ ˆ yjvj. Notice that focusing on such bidding strategies is w.l.o.g. by Lemma 1. In the following, we denote the arc going from (i, δj) to (i + 1, δj ′ ) with the tuple (i, δj , δj ′ ).
• Each arc (i, δj , δj ′ ) has a weight wi,j,j ′ . For i ∈ Nc\{n} and δj, δj ′ ∈ ∆, the weight wi,j,j ′ encodes the fraction of cumulative weighted utility obtained by setting bi = δj and bi+1 = δj ′ , once all the (higher) bids bi′ with i′ ∈ Nc : i′ < i are assigned to a value given the preceding nodes in the selected path. The weights wnc,j,s′ on arcs going from nodes (nc, δj) (for δj ∈ ∆) to the sink s′ are defined analogously, while those on arcs exiting from the source s are denied as ws,j = 0 for all δj ∈ ∆.

A directed path σ ∈ Σ is a sequence of arcs connecting the source node s to the sink node s′ . The length Wσ of path σ is the sum of the weights of the arcs in the path:

Then, the shortest path problem on the weighted graph is

In conclusion, we define the weights of all arcs (i, δj , δj ′ ), which depend on the considered auction mechanism, either GSP or VCG. The weights wnc,j,s′ of arcs entering the sink s′ are defined analogously, by letting δj ′ = 0. For the ease of notation, given δj ∈ ∆, we let τ(δj) := ∑i∈Ne 1{bi>δj} be the number of external agents with a bid larger than δj .

For the GSP mechanism, the weight of arc (i, δj , δj ′ ) is

Intuitively, for the GSP mechanism, the weight wi,j,j ′ is exactly equal to the weighted utility of colluder i when they bid value δj and the colluder i + 1 bids value δj ′ .

For the VCG mechanism, the weight of arc (i, δj , δj ′ ) is

where we let

For the VCG mechanism, wi,j,j ′ has a less intuitive interpretation than for the GSP mechanism. In particular, wi,j,j ′ is composed of a revenue term, which is agent i's expected revenue λi+τ(δj)vi, weighted by ˆ yi, and two payment terms, gi(δj) and ℓi(δj , δj ′ ), weighted by ˆx. The latter are two parts of the cumulative payment from the agency to the mechanism, which are related to the externalities of colluders i′ ∈ Nc with i′ < i, when colluders i and i + 1 bid δj and δj ′ , respectively. In particular, the fraction of the expected payment related to some colluder i′ ∈ Nc with i′ < i, due to the presence of colluder i bidding δj, is δj(λi+τ(δj)-1 - λi+τ(δj)). The term gi(δj ) defines the summation of such payments over all agents i′ ∈ Nc : i′ < i. Moreover, the fraction of expected payment related to i′ , due to the presence of an external agent k ∈ Ne bidding bk, is bk(λk-nc+i-1 - λk-nc+i). The term ℓi(δj, δj ′) is the summation of such expected payments due to external agents with bids bk ∈ (δj ′ , δj ].

The following lemma establishes the relation between the length of the paths in the weighted graph defined above and the objective of Problem (5).

Lemma 2. Given any path σ ∈ Σ composed by the sequence of nodes {(1, δj1 ), . . . , (nc, δjnc )}, it holds

where bc = (δj1 , . . . , δjnc ). Moreover, for any bidding strategy bc = (bi)i∈Nc ∈ Bc∆, there exists a corresponding path composed by the sequence of nodes {(1, b1), . . . , (nc, bnc )}.

Algorithm 1 REC((α, β], p, η)

• 1: if P be∼γ e {∃j ∈ Ne : bj ∈ (α, β]} ≤ p ∨ β - α ≤ η then
• 2: return {(α, β]}
• 3: else

• 5: IR ← REC (( α+β 2 , β] , p, η)
• 6: return IL ∪ IR
• 7: end if

The following theorem provides the polynomial-time algorithm for solving Problem (5), which works by simply finding a shortest path of the graph defined above.

Theorem 1. Problem (5) can be solved in polynomial time.

Finally, by substituting the quantities involved in Problem (5) with their expectations, thanks to the linearity of the objective, we get the following result:

Theorem 2. Problem (4) can be solved in polynomial time.

5 Arbitrary Transfers Setting

In this section, we provide an approximate solution to the media agency problem with arbitrary transfers. In particular, we design a bi-criteria additive FPTAS that returns solutions providing an arbitrary small loss ε > 0 with respect to the optimal value of the problem, by relaxing the IR constraints by the additive factor ε. As a first step, we show that there always exists a non-randomized solution to Problem (1).

Lemma 3. In the arbitrary transfers setting, there always exists an optimal non-randomized solution to Problem (1).

Then, we show how to reduce the problem to a new one working with a finite (discretized) set of bids, in order to apply the results provided in Section 4. As a first result, given a probability value p ∈ [0, 1] and a minimum discretization step η ∈ [0, 1], we show how to split the space of bids [0, 1] into a suitably-defined set of intervals using the recursive algorithm whose pseudo-code is provided in Algorithm 1.

We prove the following:

Lemma 4. Given p ∈ [0, 1] and η ∈ [0, 1], REC((0, 1], p, η) returns a set {(αj, βj]}j∈[k∗ ] composed of k∗ ≤ 2ne p log 1 η intervals such that, for every interval (αj, βj], it holds either Pbe∼γ e {∃i ∈ Ne : bi ∈ (αj , βj ]} ≤ p or βj -αj ≤ η. Moreover, it holds that ⋃j∈[k∗ ] (αj, βj] = (0, 1] and the procedure runs in time polynomial in ne, 1p , and log 1 η .

Let I p,η := {(αj, βj]}j∈[k∗ ] be the set of intervals returned by REC((0, 1], p, η). The next step is to show that, for η small enough, Pbe∼γ e {∃i ∈ Ne : bi ∈ (αj, βj)} ≤ p for every interval (αj , βj ]. This holds by definition for each interval (αj, βj] with βj - αj > η. Thus, let us consider the intervals (αj , βj ] such that βj - αj ≤ η. Let M be the maximum number of bits needed to represent the bids in the support of probability distribution γ e . By setting η = 2-M , we have that all the bids bi in the interval (αj, βj] are equal to βj. 7 Hence, it holds Pbe∼γ e {∃i ∈ Ne : bi ∈ (αj, βj)} = 0.

Letting Bcp := ⋃(α,β]∈I p,η ⋃i∈Nc {α+τ i} be a suitable set of discretized bidding strategies for τ > 0 and η = 2-M , we show that we can restrict the attention to bid profiles in Bcp with a small loss in utility and by relaxing IR constraints. 8

First, we provide the following auxiliary result.

Lemma 5. Given p ∈ [0, 1], for any bidding strategy bc ∈ Bc , there exists a discretized bidding strategy ˆbc ∈ Bcp :

• ˜πi(ˆbc ) ≤ ˜πi(bc ) for all i ∈ Nc; and
• ˜ ri(ˆbc ) ≥ ˜ ri(bc ) - p for all i ∈ Nc.

Then, by exploiting Lemma 5 we can prove the following Lemma 6. Intuitively, the lemma shows that, given a probability p ∈ [0, 1] and an optimal discretized bidding strategy, one can find an approximate solution to Problem (1) in polynomial time.

Lemma 6. Given p ∈ [0, 1] and an optimal discretized bidding strategy ˆbc ∈ argmaxbc∈Bcp ∑i∈Nc ˜ ri(bc ) - ˜πi(bc ), we can find in polynomial time a p-IR (see Equation (2)) and AIR solution to Problem (1) with value at least OPT -pnc, where OPT is the optimal value of Problem (1).

By Theorem 2, for any p ∈ [0, 1], it is possible to find an optimal discretized bidding strategy ˆbc in time polynomial in the instance size and in 1p , since, as it is easy to check, the number of possible discretized bids in Bcp is polynomial in 1p . Moreover, by employing Lemma 6, we can use the bidding strategy ˆbc to find an approximated solution to Problem (1) in polynomial time. Hence, given any ε > 0, it is sufficient to choose p ∈ [0, 1] so that 1p ∈ poly( 1ε , n) in order to obtain an ε-IR (see Equation (2)) and AIR approximate solution to Problem (1), as stated by the following theorem.

Theorem 3. Given ε > 0, there exists an algorithm that runs in time polynomial in the instance size and 1ε , which returns an ε-IR and AIR solution to Problem (1) with value at least OPT - ε, where OPT is the optimal value of Problem (1).

6 Transfers with Limited Liability Setting

In this section, we provide an approximate solution to the media agency problem with limited liability constraints. In particular, similarly to the arbitrary transfers setting, we design a bi-criteria additive FPTAS that returns solutions providing an arbitrary small loss ε > 0 with respect to the optimal value of the problem, by relaxing the IR constraints by ε.

As a first step, we show that we can restrict Problem (1) with LL constraints to work with the set Bcp by only incurring in a small loss in the objective function value and IR

7 Our algorithm runs in time logarithmic in 1 η and hence polynomial in the size of the binary representation of bids in be .

8 In the following, we ignore the loss in cumulative expected utility that results from the introduction of τ > 0. Notice that this parameter is only necessary to induce specific tie-breaking rules and our results can be easily extended to consider the loss in utility due to τ. Moreover, τ can be taken to be exponentially small in the size of the problem instance, and hence negligible.

constraints satisfaction. Notice that, Problem (1) with LL constraints restricted to discretized bids does not only have a smaller optimal value than Problem (1) with LL constraints, but it can also result in an infeasible problem, since Assumption 1 is not necessarily satisfied for a discretized bidding strategies. However, we can prove that, given a probability p ∈ [0, 1], the following LP (7) that uses only bids in Bcp and relaxes the IR constraints of quantity p is feasible and has value at least OPT - pnc, where OPT is the optimal value of Problem (1) with LL constraints.

Formally, we prove the following:

Lemma 7. LP (7) is feasible. Moreover, the optimal value of LP (7) is at least OPT - pnc, where OPT is the optimal value of Problem (1) with LL constraints.

Next, we provide an algorithm to solve LP (7) by using the ellipsoid method. To do that, we use the dual LP (8), in which variables y = {y1, . . . , ync }, x, and z are related to Constraints (7b), (7c), and γ ∈ ∆Bcp , respectively.

By Lemma 7, the primal LP (7) is feasible (and bounded), and, thus, it holds strong duality. As a consequence, in order to provide a polynomial-time algorithm to solve LP (7), it is enough to apply the ellipsoid method to the dual LP (8), which can be done in polynomial time since the latter has polynomially-many variables and exponentially-many constraints. This is possible by providing a polynomial-time separation oracle that, given an assignment of values to the variables as input, returns a violated constraint (if any). Since there are only polynomially-many Constraints (8c), we can check if one of them is violated in polynomial time. Moreover, in order to find whether there exists a violated Constraint (8b), it is sufficient to solve the weighted utility problem in Equation (4) by setting ˆ yi = (1 - yi) for each i ∈ Nc and ˆx = x-1. By Theorem 2, this can be done in polynomial time by computing a shortest path of a suitable graph. Hence, we can prove the following theorem.

Theorem 4. Given ε > 0, there exists an algorithm that runs in time polynomial in the instance size and 1ε and returns an ε-IR (see Equation (2)) and AIR solution to Problem (1) with LL constraints having value at least OPT - ε, where OPT is the optimal value of Problem (1) with LL constraints.