Mediators in Position Auctions  Itai Ashlagi, Dov Monderer, and Moshe Tennenholtz  Faculty of Industrial Engineering and Management  Haifa, Israel  ashlagii@.tx.technion.ac.il, dov@ie.technion.ac.il, moshet@ie.technion.ac.il  ABSTRACT  A mediator is a reliable entity, which can play on behalf of  agents in a given game. A mediator however can not enforce  the use of its services, and each agent is free to participate  in the game directly. In this paper we introduce a study of  mediators for games with incomplete information, and   apply it to the context of position auctions, a central topic  in electronic commerce. VCG position auctions, which are  currently not used in practice, possess some nice   theoretical properties, such as the optimization of social surplus  and having dominant strategies. These properties may not  be satisfied by current position auctions and their variants.  We therefore concentrate on the search for mediators that  will allow to transform current position auctions into VCG  position auctions. We require that accepting the   mediator services, and reporting honestly to the mediator, will  form an ex post equilibrium, which satisfies the following  rationality condition: an agent"s payoff can not be negative  regardless of the actions taken by the agents who did not  choose the mediator"s services, or by the agents who report  false types to the mediator. We prove the existence of such  desired mediators for the next-price (Google-like) position  auctions, as well as for a richer class of position auctions,  including all k-price position auctions, k > 1. For k=1, the  self-price position auction, we show that the existence of  such mediator depends on the tie breaking rule used in the  auction.  Categories and Subject Descriptors  J.4 [Social and Behavioral Sciences]: [Economics]; I.2  [Artificial Intelligence]: Distributed Artificial   IntelligenceMultiagent systems    1. INTRODUCTION  Consider an interaction in a multi-agent system, in which  every player holds some private information, which is called  the player"s type. For example, in an auction interaction  the type of a player is its valuation, or, in more complex  auctions, its valuation function. Every player has a set of  actions, and a strategy of a player is a function that maps  each of its possible types to an action. This interaction  is modeled as a game with incomplete information. This  game is called a Bayesian game, when a commonly known  probability measure on the profiles of types is added to the  system. Otherwise it is called a pre-Bayesian game. In this  paper we deal only with pre-Bayesian games. The leading  solution concept for pre-Bayesian games is the ex post   equilibrium: A profile of strategies, one for each player, such  that no player has a profitable deviation independently of  the types of the other players. Consider the following simple  example of a pre-Bayesian game, which possesses an ex post  equilibrium. The game is denoted by H.  a b  a 5, 2 3, 0  b 0, 0 4, 2  A  a b  a 2, 2 0, 0  b 3, 3 5, 2  B  At the game H there are two players. Both players can  choose among two actions: a and b. The column player,  player 2, has a private type, A or B (player 1 has only one  possible type). A strategy of player 1 is g1,where g1 = a or  g1 = b. A strategy of player 2 is a function g2 : {A, B} →  {a, b}.That is, player 2 has 4 strategies. In this game the  strategy profile (g1, g2) is an ex post equilibrium, where g1 =  b and g2(A) = b, g2(B) = a.  Unfortunately, pre-Bayesian games do not, in general,   possess ex post equilibria, even if we allow mixed strategies. In  order to address this problem we suggest in this paper the  use of mediators. A mediator is a reliable entity that can  interact with the players and perform on their behalf actions  in a given game. However, a mediator can not enforce   behavior. Indeed, an agent is free to participate in the game  without the help of the mediator. The mediator"s   behavior on behalf of the agents that give it the right of play is  pre-specified, and is conditioned on information the agents  would provide to the mediator. This notion is highly   natural; in many systems there is some form of reliable party or  279  administrator that can be used as a mediator. The simplest  form of a mediator discussed in the game theory literature  is captured by the notion of correlated equilibrium [1]. This  notion was generalized to communication equilibrium by [5,  15]. Another type of mediators is discussed in [13]. However,  in all these settings the mediator can not perform actions  on behalf of the agents that allow it to do so. Mediators  that can obtain the right of play but can not enforce the  use of their services have been already defined and discussed  for games with complete information in [14].1  The topic of  mediators for games with complete information has been  further generalized and analyzed in [16]. In this paper we  introduce another use of mediators, in establishing   behaviors which are stable against unilateral deviations in games  with incomplete information. Notice that we assume that  the multi-agent interaction (formalized as a game) is given,  and all the mediator can do is to perform actions on behalf  of the agents that explicitly allow it to do so.2  In order to illustrate the power of mediators for games  with incomplete information consider the following pre-Bayesian  game G that does not possess an ex post equilibrium. In G,  the column player has two possible types: A and B.  a b  a 5, 2 3, 0  b 0, 0 2, 2  A  a b  a 2, 2 0, 0  b 3, 0 5, 2  B  A mediator for G should specify the actions it will choose  on behalf of the players that give it the right to play. If  player 2 wants to give the mediator the right to play it should  also report a type. Consider the following mediator:  If both players give the mediator the right of play, then the  mediator will play on their behalf (a, a) if player 2 reports  A and (b, b) if player 2 reports B. If only player 1 gives the  mediator the right of play then the mediator will choose a  on his behalf. If only player 2 gives the mediator the right  of play, the mediator will choose action a (resp. b) on its  behalf, if B (resp. A) has been reported.  The mediator generates a new pre-Bayesian game,which  is called the mediated game. In the mediated game player  1 has three actions: Give the mediator the right of play,  denoted by m, or play directly a or b. Player 2 has four  actions: m − A, m − B,a,b, where m − A (m − B) means  reporting A (B) to the mediator and give it the right of play.  The mediated game is described in the following figure:  m − A m − B a b  m 5, 2 2, 2 5, 2 3, 0  a 3, 0 5, 2 5, 2 3, 0  b 2, 2 0, 0 0, 0 2, 2  A  1  For games with complete information the main interest is  in leading agents to behaviors, which are stable against   deviations by coalitions. A special case of mediators was already  discussed in [8]. In this paper the authors discussed   mediators for a two-person game, which is known to the players  but not to the mediators, and they looked for Nash   equilibrium in the new game generated by the mediator.  2  This natural setting is different from the one discussed in  the classical theories of implementation and mechanism   design, where a designer designs a new game from scratch in  order to yield some desired behavior.  m − A m − B a b  m 2, 2 5, 2 2, 2 0, 0  a 0, 0 2, 2 2, 2 0, 0  b 5, 2 3, 0 3, 0 5, 2  B  It is now easy to verify that giving the mediator the right  of play, and reporting truthfully, is an ex-post equilibrium  at the mediated game. That is, (f1, f2) is an ex post   equilibrium, where f1 = m, and f2(A) = m−A, f2(B) = m−B.  The aim of this paper is twofold. We introduce mediators  for games with incomplete information, and apply them in  the context of position auctions. Our choice of positions   auctions as the domain of application is not an accident; indeed,  positions auctions have become a central issue in   advertisement and the selection of appropriate position auctions for  that task is a subject of considerable amount of study [17,  3, 9, 4].3  Current position auctions however do not possess  ex-post equilibrium, i.e. solutions which are stable against  unilateral deviations regardless of the agents" private   information, nor guarantee optimal social surplus. In contrast,  in the VCG position auction, which is currently not used  in practice, there is a truth-revealing ex post equilibrium,  which yields optimal surplus. We therefore suggest the use  of mediators in order to attempt and implement the output  of the VCG position auction, by transforming other (and in  particular current) position auctions into a VCG position  auction.4  More specifically, the mediated game will have  an ex post equilibrium, which generates the outcome of the  VCG position auction. One such mediator has already been  discussed for other purposes in the literature: An English  auction type of algorithm was constructed in [3] that takes  as an input the valuations of the players and outputs bids for  the next-price position auction. It was proved there that   reporting the true type to this algorithm by each player forms  an ex post equilibrium, which generates the VCG outcome.  In our language this algorithm can be almost considered as a  mediator for the next-price position auction that implement  the VCG outcome function. What is missing, is a   component that punishes players who send their bids directly to  the auctioneer, and a proof that using the mediator services  and reporting the true type by each player is an ex post  equilibrium in the mediated game defined by the algorithm  and by the additional component. A mediator may generate  a desired outcome by punishing the players who do not use  its services with very high bids by the players that use its  services. We believe that such mediators are not realistic,  and therefore we concentrate on the search for valid   mediators that generate an ex post equilibrium and satisfy the  additional rationality condition: an agent"s payoff can not  be negative regardless of the actions taken by the agents  who did not choose the mediator"s services, or agents who  report false types to the mediator. We prove the existence  of such desired mediators for the next-price (Google-like)  position auctions5  , as well as for a richer class of position  auctions, including all k-price position auctions, k > 1. For  k=1, the self-price position auction, we show that the   ex3  See also [12], where position auctions are titled ad auctions.  4  In general, except for the VCG position auction we do not  expect position auctions to possess an ex post equilibrium  (see Footnote 7).  5  Our proof uses an algorithm, which is different from the  algorithm in [3] discussed earlier.  280  istence of such mediator depends on the tie breaking rule  used in the auction.  Mediators in one-item auctions (in particular first price  and second price auctions) have been already discussed in  [6, 11, 2]; however they all used a Bayesian model.   Position auctions are a restricted type of general pre-Bayesian  games. In this conference version we make the formal   definition of mediators and implementing by mediation for the  special case of position auctions, and only in the full version  we present the general theory of mediators for pre-Bayesian  games. Most of the proofs are omitted from this conference  version.  2. POSITION AUCTIONS  In a position auction there is a seller who sells a finite  number of positions j ∈ K = {1, ..., m}. There is a finite  number of (potential) bidders i ∈ N = {1, ..., n}. We assume  that there are more bidders than positions, i.e. n > m.  The positions are sold for a fixed period of time. For each  position j there is a commonly-known number αj > 0, which  is interpreted as the expected number of visitors at that  position. αj is called the click-through rate of position j.  We assume that α1 > α2 > αm > 0. If i holds a position  then every visitor to this position gives i a revenue of vi > 0,  where vi is called the valuation of i. The set of possible  valuations of i is Vi = (0, ∞).  We assume that the players" utility functions are   quasilinear. That is, if player i is assigned to position j and pays  pi per click then his utility is αj(vi − pi).  Every player is required to submit a bid, bi ∈ Bi = [0, ∞).  We assume that bidding 0 is a symbol for non-participation.  Therefore, a player with a bid 0 is not assigned to any   position, and it pays 0.  In all position auctions we consider, the player with the  highest positive bid receives the first position, the player  with the second highest positive bid receives the second   position, and so on. It is useful to define for every position  auction two dummy positions m + 1 and −1, which more  than one player may be assigned to. All players, who   participate in the auction but do not get a position in K are  assigned to position m + 1 and all players who choose not  to participate are assigned to position −1. We also define  αm+1 = α−1 = 0.  An assignment of players to positions is called an   allocation. Hence, an allocation is a vector s = (s1, s2, · · · , sn)  with si ∈ K ∪ {−1, m + 1} such that if si ∈ K then si = sl  for every l = i; si is the position of player i. Given the  above, a position auction is defined by its tie breaking rule,  which determines the allocation in case of ties, and by its  payment scheme. These are discussed below.  2.1 Tie breaking rules  In practice, the most commonly used tie breaking rule  is the First-Arrival rule: if a set of players submit the same  bid, their priority in receiving the positions is determined by  the times their bids were recorded; An earlier bid receives  a higher priority. In auction theory this tie breaking rule is  typically modelled by assuming that the auctioneer is using  a random priority rule. More specifically, let Γ be the set of  all permutations, γ = (γ1, ..., γn) of N. Every such γ defines  a priority rule as follows: i has a higher priority than k if and  only if γi < γk. Every vector of bids b and a permutation  γ uniquely determine an allocation. An auctioneer who is  using the random priority rule chooses a fixed priority rule  γ by randomizing uniformly over Γ. However, the resulting  priority rule is not told to the players before they make their  bids. When the priority rule γ is told to the players before  they make their bids, the tie breaking rule is called a fixed  priority rule. Dealing with a fixed priority rule simplifies  notations and proofs, and in most cases, and in particular  in this paper, results that are obtained with this tie breaking  rule are identical to the results obtained with the random  priority rule. Therefore we will assume this tie breaking  rule. In contrast, in Section 7 we discuss a non-standard  approach for analyzing directly the first-arrival tie breaking  rule.  Unless we say specifically otherwise we assume in this   paper a fixed priority rule.  Without loss of generality we assume that the fixed   priority rule is defined by the natural order, ˜γ = (1, 2, ..., n).  That is, bidder i has a higher priority than bidder k if and  only if i < k. Given this fixed priority rule we can make the  following definitions, which apply to all position auctions:  We denote by s(b, i) the position player i is assigned to  when the bid profile is b. The allocation determined by b is  denoted by  s(b) = (s(b, 1), s(b, 2), · · · , s(b, n)).  For every j ∈ K ∪ {−1, m + 1} we denote by δ(b, j) the  set of players assigned to position j. Note that for j ∈ K,  δ(b, j) contains at most one player.  2.2 The payment schemes  Let α be a click-trough rate vector. Each position j ∈  K ∪ {−1, m + 1} is associated with a payment function,  pα  j : B → R+, where pα  j (b) is the payment for position j  when the bid profile is b. Naturally we assume that pα  −1  is identically zero. However, we also assume that pα  m+1 is  identically zero. Hence, a participant who is not assigned a  real position pays nothing.  We call the vector of payment functions pα  = (pα  j )j∈K the  position payment scheme.  Remark: Whenever α is fixed or its value is clear from the  context we will allow ourselves to omit the superscript α  from the payment and other functions.  We deal with anonymous position payment schemes, i.e.  the players" payments to the auctioneer are not influenced  by their identities. This is modeled as follows: Let b ∈ B =  B1 × B2 × · · · × Bn be a bid profile. We denote by b(j) the  jth  highest bid in b. For j > n we let b(j) = 0. For example  if b = (3, 7, 3, 0, 2) then b(1) = 7, b(2) = 3, b(3) = 3, b(4) =  2, b(5) = 0. We denote b∗  = (b(1), · · · , b(n)). Anonymity is  modeled by the requirement that for every two bid profiles  b, d ∈ B, p(b) = p(d) whenever b∗  = d∗  . That is, for  every position j there exists a real-valued function ˜pj defined  over all ordered vectors of bids such that for every b ∈ B  pj(b) = ˜pj(b∗  ).  We further assume that a player never pays more than  his bid. That is pj(b) ≤ b(j) for every b ∈ B and for every  j ∈ K.  It is convenient in certain cases to describe the payment  functions indexed by the players. Let G be a position   auction with a position payment scheme p.  For every player i we denote  qi(b) = ps(b,i)(b),  281  and  q(b) = (q1(b), q2(b), · · · qn(b)).  Note that the correspondence p → q is one-to-one. We call q  the player payment scheme. All our assumptions about the  position payment schemes can be transformed to analogous  assumptions about the player payment schemes. For   convenience, a position auction will be described either by its  position payment scheme or by its player payment scheme.  The utility function for player i, wi : Vi × B → R+ is  defined as follows:  wi(vi, b) = αs(b,i)(vi − qi(b)) = αs(b,i)(vi − ps(b,i)(b)).  2.3 Central position auctions  We next describe the payment schemes of three central  position auctions.  Self-price position auctions: Each player who is assigned  to a position with a positive click-through rate pays his own  bid. That is, for every j ∈ K and every b ∈ B  pj(b) = b(j) (1)  Next-price position auctions: In this auction (run with  a slight variation by Google), every player who is assigned  to a position with a positive click-through rate pays the bid  of the player assigned to the position right after him if there  is such a player, and zero otherwise. That is for every j ∈ K  and for every b ∈ B  pj(b) = b(j+1) (2)  VCG position auctions: In a Vickrey-Clarke-Groves (VCG)  position auction the payment function for position j ∈ K is  defined as follows.6  For every b ∈ B  pvcg  j (b) =  Pm+1  k=j+1 b(k)(αk−1 − αk)  αj  (3)  Note that the VCG position auction is not the next-price  position auction unless there is only one position and α1 = 1.  2.4 Mediators for position auctions  We denote by G = G(α, p) the position auction with  the click-through rate vector α and the payment scheme  p. Recall that the set of types of i is Vi = (0, ∞). Let  V = V1 × V2 × · · · × Vn be the set of profile of types, and for  every S ⊆ N let VS = ×i∈SVi.  A mediator for G is a vector of functions m = (mS)S⊆N ,  where mS : VS → BS. The mediator m generates a   preBayesian game Gm, which is called the mediated game. In  this game every player i receives his type vi and can either  send a type, ˆvi (not necessarily the true type) to the   mediator, or send a bid directly to the auction. If S is the set of  players that send a type to the mediator, the mediator bids  on their behalf mS(ˆvS). Hence, the action set of player i in  the mediated game is Bi ∪Vi, where conveniently Vi denotes  both, (0, ∞) , and a copy of (0, ∞), which is disjoint from  6  We use the standard payment function of the VCG   mechanism. A general VCG mechanism may be obtained from  the standard one by adding an additional payment function  to each player, which depends only on the types of the other  players. Some authors (see e.g., [7]) call the standard VCG  mechanism, the VC mechanism. According to this   terminology we actually deal with VC position auctions. However,  we decided to use the more common terminology.  Bi. We introduce the following terminology: The T-strategy  for a player in the mediated game is the strategy, in which  this player uses the mediator"s services and reports his true  value to the mediator. The T-strategy profile is the profile of  strategies in which every player is using the T-strategy. The  T-strategy profile is an ex post equilibrium in the mediated  game if for every player i and type vi, and for every vector of  types of the other players, v−i, the following two conditions  hold:  E1: i is not better off when he gives the mediator the right  of play and report a false type. That is, for every ˆvi ∈ Vi  wi(vi, mN (vi, v−i)) ≥ wi(vi, mN (ˆvi, v−i)).  E2: i is not better off when he bids directly. That is for  every bi ∈ Bi,  wi(vi, mN (vi, v−i)) ≥ wi(vi, (bi, mN\i(v−i))).  Whenever the T-strategy profile is an ex post equilibrium  in Gm, the mediator m implements an outcome function  in G. This outcome function is denoted by ϕm  , and it is  defined as follows:  ϕm  (v) = (s(mN (v)), q(mN (v)).  Hence, the range of the function ϕm  is the Cartesian product  of the set of allocations with Rn  +.  3. IMPLEMENTING THE VCG OUTCOME  FUNCTION BY MEDIATION  In general, except for the VCG position auction we do not  expect position auctions to possess an ex post equilibrium.7  Therefore, the behavior of the participants in most position  auctions cannot be analytically predicted, and in practice it  can form a non-efficient allocation: an allocation that does  not maximize social surplus. In contrast, in the VCG   position auction the truth-reporting strategy is a dominant  strategy for every player, and the resulting allocation is   efficient. Given a position auction G our goal is to construct a  mediator that would implement the outcome function of the  VCG position auction. This outcome function is defined as  follows:  ϕvcg  (v) = (s(v), qvcg  (v)).  Definition: Let G be a position auction . Let m be a  mediator for G. We say the m implements the VCG outcome  function in G, or that it implements ϕvcg  in G if the   Tstrategy profile is an ex post equilibrium in Gm, and ϕm  =  ϕvcg  .  We demonstrate our definitions so far by a simple   example:  Example 1. Consider a self-price auction G = G(α, p)  with 2 players and one position, with α1 = 1. That is, G is  a standard two-person first-price auction. The   corresponding VCG position auction is a standard second-price   auction. We define a family of mediators mc  , c ≥ 1, each of  them implements the VCG position auction. Assume both  7  Actually, it can be shown that if a strategy profile b in  a position auction is an ex post equilibrium then for every  player i bi is a dominant strategy. It is commonly   conjectured that except for some extremely artificial combinatorial  auctions , the VCG combinatorial auctions are the only ones  with dominant strategies (see [10]).  282  players use the mediator"s services and send him the types  ˆv = (ˆv1, ˆv2), then all mediators act similarly and as follows:  If ˆv1 ≥ ˆv2 the mediator makes the following bids on behalf  of the players: b1 = ˆv2, and b2 = 0. If ˆv2 > ˆv1, the mediator  makes the bids b1 = 0, b2 = ˆv1. If only one player uses  the mediator services, say player i, then mediator mc  bids  bi = cˆvi on behalf of i. We claim that for every c > 1, the  T-strategy profile is an ex post equilibrium in the mediated  game generated by mc  . Indeed, assume player 2 reports his  type v2 to the mediator, and consider player 1.  If v1 ≥ v2 then by using the T-strategy player 1 receives the  position and pays v2. Hence, 1"s utility is v1 −v2. If player 1  deviates by using the mediator"s services and reporting ˆv1 ≥  v2 his utility is still v1 − v2. If he reports ˆv1 < v2 his utility  will be 0. If player 1 does not use the mediator, he should  bid at least cv2 in order to get the positions, and therefore  his utility cannot exceed v1 − v2.  If v1 < v2, then the T-strategy yields 0 to player 1, and  any other strategy yields a non-positive utility.  Obviously each of the mediators mc  implements the VCG  outcome function. Note however, that the T-strategy is not  a dominant strategy when c > 1; e.g. if v1 > v2 and player  2 bids directly v2 (without using the mediator services), then  bidding directly v1 is better for player 1 than using the   Tstrategy: in the former case player 1"s utility is 0 and in the  latter case her utility is negative.  It is interesting to note that this simple example can not  be extended to general self-price position auctions, as will  be discussed in section 4.  While each of the mediators mc  in Example 1 implements  the VCG outcome function, the mediator with c = 1 has  a distinct characteristic: a player who uses the T-strategy  cannot get a negative utility. In contrast, for every c > 1, if  say player 2 does not use the mediator services, participates  directly and bids less than cv1, then the T-strategy yields a  negative utility of (1 − c)v1 to player 1. This motivates our  definition of valid mediators:  Let G be a position auction. A mediator for G is valid,  if for every player, using the T-strategy guarantees a   nonnegative level of utility.  Formally, a mediator m for G, is valid if for every subset  S ⊆ N and every player i ∈ S wi(vi, mS(vS), b−S) ≥ 0 for  every b−S ∈ B−S and every vs ∈ VS.  4. MEDIATORS IN NEXT-PRICE POSITION  AUCTIONS  We now show that there exists a valid mediator, which   implements the VCG outcome function in next-price position  auctions. Although in the following section we prove a more  general result, we present this result first, given the   importance of next-price position auctions in the literature and  in practice. Our proof makes use of the following technical  lemma.  Lemma 1. Let pvcg  be the VCG payment scheme.  1. pvcg  j (b) ≤ b(j+1) for every j ∈ K.  2. pvcg  j (b) ≥ pvcg  j+1(b) for every j = 1, ..., m − 1 and for  every b ∈ B, where for every j, equality holds if and  only if b(j+1) = b(j+2) = · · · = b(m+1).  The proof of Lemma 1 is given in the full version. We can  now show:  Theorem 2. Let G be a next-price position auction. There  exists a valid mediator that implements ϕvcg  in G.  Theorem 2 follows from a more general theorem given in the  next section. However, we still provide a proof since a more  simple and intuitive mediator is constructed for this case.  Proof of Theorem 2. We define a mediator m, which will  implement the VCG outcome function in G: For every v ∈  V let mN (v) = b(v), where b(v) is defined as follows:  For every player i such that 2 ≤ s(v, i) ≤ m let bi(v) =  pvcg  s(v,i)−1(v).8  For every i ∈ δ(v, m + 1), bi(v) = pvcg  m (v).  Let bδ(v,1)(v) = 1 + max{i:s(v,i)≥2}bi(v).  For every S ⊆ N such that S = N and for every vS ∈ VS  let mS(v) = vS. This completes the description of the  mediator m.  We show that ϕm  (v) = ϕvcg  (v) for every v ∈ V . Let  v ∈ V be an arbitrary valuation vector.  We have to show that s(b(v)) = s(v) and that q(b(v)) =  qvcg  (v):  We begin by showing that s(b(v)) = s(v). It is sufficient  to show that whenever 1 ≤ s(v, i) < s(v, l) ≤ m + 1 for  some i = l, then s(b(v), i) < s(b(v), l).  We first show it for s(v, i) = 1, that is δ(v, 1) = i. In  this case bδ(v,1)(v) > bj(v) for every j = i, s(b(v), i) = 1.  Therefore s(b(v), i) < s(b(v), l). If s(v, i) > 1, we   distinguish between two cases.  1. vi = vl. Since s(v, i) < s(v, l), the fixed priority rule  implies that i < l. By the second part of Lemma 1,  pvcg  s(v,i)−1(v) ≥ pvcg  s(v,l)−1(v). Therefore bi(v) ≥ bl(v),  which yields s(b(v), i) < s(b(v), l).  2. vi > vl. Let j + 1 = s(v, i). That is v(j+1) = vi, and  therefore by the second part of Lemma 1, pvcg  s(v,i)−1(v) >  pvcg  s(v,i)(v). Since s(v, i) ≤ s(v, l) − 1, by the second  part of Lemma 1, pvcg  s(v,i)(v) ≥ pvcg  s(v,l)−1(v).   Therefore pvcg  s(v,i)−1(v) > pvcg  s(v,l)−1(v), which yields bi(v) >  bl(v). Therefore s(b(v), i) < s(b(v), l).  This completes the proof that s(b(v)) = s(v) for all v ∈ V .  Observe that for every player i such that s(b(v), i) ∈ K  ps(b(v),i)(b(v)) = pvcg  s(v,i)(v).  Therefore qi(b(v)) = qvcg  i (v) for every i ∈ N. This shows  that q(b(v)) = qvcg  (v) for all v ∈ V . Hence, ϕm  = ϕvcg  .  We proceed to prove that the T-strategy is an ex-post  equilibrium. Note that by the truthfulness of VCG, it is not  beneficial for any player i to miss report her value to the  mediator, given that all other players use the T-strategy.  Next we show that it is not beneficial for a single player i ∈  N to participate in the auction directly if all other players  use the T-strategy. Fix some v ∈ V . Assume that player i  is the only player that participates directly in the auction.  Hence, v−i is the vector of bids submitted by the mediator.  Let bi be player i"s bid. Let k = s(v, i). Therefore, since  ϕm  = ϕvcg  , s(b(v), i) = k. Let j be player i"s position in the  deviation. Hence j = s((v−i, bi), i). If j /∈ K then player i"s  8  Recall that s(b, i) denotes the position of player i under the  bid profile b, and δ(b, j) denotes the set of players assigned  to position j. Whenever j ∈ K, we slightly abuse notations,  and also refer to δ(b, j) as the player that is assigned to  position j.  283  utility is zero and therefore deviating is not worthwhile for  i. Suppose j ∈ K. Then  αk(vi − pk(b(v))) = αk(vi − pvcg  k (v)) ≥  αj(vi − pvcg  j (v−i, bi)) ≥ αj(vi − v(j+1)),  where the first equality follows from ϕm  = ϕvcg  , the first  inequality follows since VCG is truthful, and the second   inequality follows from the first part of Lemma 1. Since pj  is position j"s payment function in the next-price position  auction, αj(vi − v(j+1)) = αj(vi − pj(v−i, bi)). Therefore  αk(vi − pk(b(v))) ≥ αj(vi − pj(v−i, bi)).  Hence, player i does not gain from participating directly in  the auction.  Finally we show that m is valid. If all players choose  the mediator then by the first part of Lemma 1 each player  which uses the T-strategy will not pay more than his value.  Consider the situation in which a subset of players, S,   participate directly in the auction. Since the mediator submits  the reported values on behalf of the other players, these  other players will not pay more than their reported values.  Hence a player which used the T-strategy will not pay more  than his value. 2  5. MEDIATORS IN GENERALIZED   NEXTPRICE POSITION AUCTIONS  In the previous section we discussed the implementation  of the VCG outcome function in the next price position   auction. In this section we deal with a more general family of  position auctions, in which the payment of each player who  has been assigned a position, is a function of the bids of  players assigned to lower positions than his own. The  payment scheme p of such a position auction satisfies the  following condition:  N1: For every j ∈ K and every b1  , b2  ∈ B such that b1  (l) =  b2  (l) for every l > j, we have that pj(b1  ) = pj(b2  ).  We next provide sufficient conditions for implementing the  VCG outcome function by a valid mediator in position   auctions whose payment schemes satisfy N1.  We need the following notation and definition. For every  position auction G and every b ∈ B let ϕG  (b) = (s(b), q(b)).  We say that G is a V CG cover if for every v ∈ V there  exists b ∈ B such that ϕG  (b) = ϕvcg  (v).  We say that G is monotone if pj(b) ≥ pj(b ) for every  j ∈ K and for every b ≥ b , where b ≥ b if and only if  bi ≥ bi for every i ∈ N.  We are now able to show:  Theorem 3. Let G = G(α, p) be a position auction such  that p satisfies N1. If the following conditions hold then  there exists a valid mediator that implements ϕvcg  in G:  1. G is a V CG cover  2. G is monotone.  The proof of Theorem 3 is given in the full version. We  next provide the construction of the valid mediator, which  will implement the VCG outcome function in a position   auction G, which satisfies the conditions of Theorem 3:  Algorithm for building m for G:  • For every v ∈ V let mN (v) = b(v), where b(v) is  some bid profile such that ϕG  (b(v)) = ϕvcg  (v)  • For every i and for every v−i ∈ V−i, let  vi  = (v−i, M(v−i)), where M(v−i) = 1 + maxj=ivj.  • For every i ∈ N and every v−i ∈ V−i, let mN\{i}(v−i) =  b−i(vi  ), where b(vi  ) is some bid profile such that  ϕG  (b(vi  )) = ϕvcg  (vi  ).  • For every S ⊆ N, such that 1 ≤ |S| ≤ n − 2, let  mS(vS) = vS.  Remark: As we wrote, Theorem 3 applies in particular  to next-price position auctions discussed in Section 4.   However, this Theorem applies to many other interesting   position auctions as will be shown later. Moreover, the mediator  constructed for this general case is different from the one in  the proof of Theorem 2.  We now show that condition N1 as well as the   requirement that G is a V CG cover, and the requirement that G  is monotone are all necessary for establishing our result. It  is easy to see that if G is not a V CG cover then Theorem  3 does not hold. The following example shows the necessity  of the monotonicity condition.  Example 4. Let G = G(α, p) be the following position  auction. Let n = 4, m = 3, α = (100, 10, 1), p1(b) = b(2) −  b(3) and p2(b) =  b(3)+b(4)  2  , and p3(b) = b(4). Notice that G  is not monotone. Observe that condition N1 is satisfied. In  the full version we show that G is a V CG cover, and it is  not possible to implement the VCG outcome function in G  with a valid mediator.  The next example shows that Theorem 3 does not hold,  when condition N1 is not satisfied.  Example 5. Let G = G(α, p) be the following position  auction. Let N = {1, 2, 3}, K = {1, 2} and α = (2, 1). Let  p1(b) =  b(1)  4  and p2(b) = b(2). It is immediate to see that the  monotonicity condition is satisfied. We next show that G is  a V CG cover. Let v ∈ V be an arbitrary valuation vector.  We need to find a bid profile b(v) such that ϕG  (b(v)) =  ϕvcg  (v). Note that pvcg  1 (v) =  v(2)+v(3)  2  and pvcg  2 (v) = v(3).  We define the bid profile b(v) as follows.  Let bδ(v,3)(v) =  v(3)  2  , bδ(v,2)(v) = v(3) and bδ(v,1)(v) =  2v2 + 2v(3).  By the construction of b(v), s(b(v), i) = s(v, i) for i =  1, 2, 3 . In addition observe that pj(b(v)) = pvcg  j (v) for  j = 1, 2, 3, 4. Therefore ϕG  (b(v)) = ϕvcg(v). Since v is  arbitrary, G is a V CG cover.  Naturally N1 is not satisfied. Suppose in negation that  there exists a valid mediator m, which implements the VCG  outcome function in G. Consider the following vector of  valuations v = (12, 10, 8). If all players use the mediator  then player 2 (with valuation 10) gets position 2, pays 8, and  therefore her utility is 1(10−8) = 2. Player 2 can always bid  more than the other players, and by that cause some other  player to be positioned second; Since the mediator is required  to be valid it must be that the mediator submits not more  than 12 on behalf of both players 1 and 3. But then player  2 can bid 13, and win the first position; therefore, player 2"s  utility will be 2(10 − 13  4  ) > 8. This contradicts that m is a  valid mediator that implements the VCG outcome function  in G.  To summarize, we have shown sufficient conditions for  transforming a large class of position auctions to the V CG  284  position auction by mediation. Moreover by dropping any  of our conditions we get that such transformation might not  be feasible.  In the next subsections we provide classes of interesting  position auctions which can be transformed to the VCG   position auction by mediation. These auctions satisfy the   conditions of Theorem 3. However, in order to use Theorem 3  one has to check that a certain position auction, G is a VCG  cover. In the full version paper, before we apply this   theorem we present another useful theorem that gives sufficient  conditions guaranteeing that G is a VCG cover.  5.1 Generalized next-price position auctions  In a generalized next-price auction the payment scheme is  of the following form. For every j ∈ K and for every b ∈ B  pj(b) = b(l(j)) where l(j) is an integer such that l(j) > j.9  .  We show:  Proposition 1. Let G be a generalized next-price   position auction. There exists a valid mediator that implements  ϕvcg  in G if and only if the following two conditions hold:  (i) l(j + 1) > l(j) for j = 1, ..., m − 1, and (ii) l(m) ≤ n.  5.2 K-next-price position auctions  In k-next-price position auctions the payment scheme is  defined as follows: For every j ∈ K and for every b pj(b) =  b(j+k). K-next-price position auctions are, in particular   generalized next-price position auctions. Therefore Proposition  1 yields as a corollary:  Proposition 2. Let k ≥ 1. Let G be a k-next-price   position auction. There exists a valid mediator that implements  ϕvcg  in G if and only if n ≥ m + k − 1.  5.3 Weighted next-price position auctions  In weighted next-price position auctions the payment schemes  are of the following form. For every j ∈ K and for every  b ∈ B, pj(b) =  b(j+1)  cj  , where cj ≥ 1.  Proposition 3. Let G be a weighted next-price position  auction with the weights c1, c2, ..., cm. There exists a valid  mediator that implements ϕvcg  in G if and only if c1 ≥ · · · ≥  cm.  5.4 Google-like position auctions  Google-like ad auctions are slightly different from   nextprice auction. In these auctions the click-trough rate of an  ad i in position j is the product of the quality of ad i,  βi > 0, and the position click-trough rate αj > 0.10  Players  are ranked in the positions by biβi.  Let b ∈ B. Let ˜δ(b, j) be defined as follows. For every  j ∈ K, let ˜δ(b, j) be the player i that obtains position j,  and for j = m let ˜δ(b, j) = i, where i obtained position m  in case there is more than one player i such that bi = b(m),  then i is chosen between them via the breaking rule ˜γ.  If player i obtains position j ∈ K then she pays pj(b) =  β˜δ(b,j+1)  b˜δ(b,j+1)  βi  . Therefore player i"s utility will be  αjβi(vi −  b˜δ(b,j+1)  βi  β˜δ(b,j+1)) = αj(viβi − b˜δ(b,j+1)β˜δ(b,j+1)).  9  Recall that b(j) = 0 for every j > n  10  See e.g. [17].  Hence by denoting ˜vi = viβi for every i ∈ N, and by   applying Theorem 2 we obtain:  Proposition 4. There exists a valid mediator which   implements the VCG outcome function in the Google-like   position auction.  6. SELF-PRICE POSITION AUCTIONS  Let G be a self-price position auction as described at   section 2. At example 1 we showed that when there is one  position and two players, the VCG outcome function is   implemented by a valid mediator in this auction. The proof  in this example can be easily generalized to show that the  VCG outcome function can be implemented by a valid   mediator in a self-price position auction, in which there is one  position and an arbitrary number of players, n ≥ 2.  Next we show that it is impossible to implement the VCG  outcome function, even by a non-valid mediator, in a   selfprice position auction which has more than one position  (m > 1).  Theorem 6. Let G be a self-price position auction with  more than one position. There is no mediator that   implements the VCG outcome function in G.  Proof. Let v ∈ V be the following valuation profile. vn = 10  and v1 = v2 = · · · = vn−1 = 5. The VCG outcome function  assigns to this v an allocation, in which player n receives  position 1 and player 1 receives position 2. The payments of  players n and 1 are both equal to 5. In order to implement  such an outcome, a mediator must bid 5 on behalf of player  n (so that this player pays 5), and it must bid less than 5 on  behalf of any other player, because otherwise another player  receives position 1. Note that the bid of any other player  cannot equal 5 because every other player has an higher  priority than n. In particular, even if player 1 gets indeed  position 2 he will pay less than 5. Hence, no mediator can  implement the VCG outcome function in G.2  The proof of Theorem 6 heavily uses the fixed priority  rule assumption. However, as we have already said, all our  results including this theorem hold also for the tie breaking  rule defined by the random priority rule. The proof of the  impossibility theorem for the random priority rule uses the  fact that the particular bad priority rule used in the proof  of Theorem 6, has a positive probability.  As we previously discussed, the fixed and random   priority rules are just convenient ways to model the first-arrival  rule, which is common in practice. When one attempts to  directly model position auctions that use the first-arrival  rule without these modeling choices he tackles a lot of   modeling problems. In particular, it is not clear how to model a  position auction with the first-arrival rule as a game with   incomplete information. To do this, one has to allow a player  not only to submit a bid but also to decide about the time  of the bid. This raises a lot of additional modeling   problems, such as determining the relationship between the time  a player decides to submit a bid and the time in which this  bid is actually recorded. Hence, efficient modeling as a game  may be untractable. Nevertheless, in the next section we  will analyze mediators in position auctions, which use the  first-arrival rule. We will define ex post equilibrium and the  notion of implementation by mediation without explicitly  modeling well-defined games. We will show that in this case  285  there is a way to implement the VCG outcome function in  a self-price position auction. Moreover, we will find a valid  mediator that does the job.  7. POSITION AUCTIONS WITH THE FIRST  ARRIVAL RULE  Let G be a position auction with the first-arrival rule.  Every mediator for G has the ability to determine the order  in which the bids he submits on behalf of the players are  recorded; He can just submit the bids sequentially, waiting  for a confirmation before submitting the next bid. We need  the following notations.  Every order of bidding can be described by some γ ∈ Γ; i  bids before k if and only if γi < γk. Hence, an order of bids  can serve as a priority rule. For every order of bids γ and a  vector of bids b we define s(b, γ, i) as the position assigned  to i. We denote the payment of i when the vector of bids  is b and the order of bidding is γ by qi(b, γ) = ps(b,γ,i)(b),  and we denote wi(vi, b, γ) the utility of i.  A mediator for G should determine the bids of the players  who use its services and also the order of bids as a function  of the reported types. However, all mediators discussed in  this paper will use the same rule to determine the order of  bids: If all players report the vector of types ˆv, the   mediator uses the order of bids γˆv  , which is defined as follows:  γˆv  i < γˆv  k if and only if ˆvi > ˆvk, or ˆvi = ˆvk and i < k. For  example, if n = 3 and the reported types are ˆv = (6, 7, 6),  then γˆv  = (2, 1, 3). If only a strict subset of the players  use the mediator"s services, the mediator applies the same  order of bids rule to this subset. A mediator for a position  auction with the first arrival rule is therefore defined by a  vector m = (mS)S⊆N . However, such a mediator is called  a directed mediator in order to stress the fact that it   determines not only the bids but also the order of bids. To  summarize: If all players use the directed mediator m, and  the reported bids are ˆv, then the directed mediator bids  mN (ˆv)i on behalf of i, i receives the position s(ˆv, γˆv  , i),  and pays qi(mN (ˆv), γˆv  ). If only the subset S uses the   mediator"s services, the reported types are ˆvS, and the other  players bid directly b−S then the actual order of bids is not  uniquely determined. If this order is γ then the position  of i ∈ N is s(b, γ, i), and its payment is qi(b, γ), where  b = (mS(ˆvS), b−S). In particular, if every player is using  the T-strategy and the players" profile of types is v, then  the outcome generated by the directed mediator is  ψm  (v) = (s(v, γv  ), q(mN (v), γv  ).  But why should the players use the T strategy? Assume all  players but i use the T strategy. If player i deviates from the  T strategy by reporting a false type to the directed mediator,  the resulting outcome is well-defined. On the other hand,  when this player sends a bid directly to the auctioneer, the  resulting outcome is not clear, because the order of bids is  not clear.11  A good desired directed mediator would be one that no  player would want to deviate from the T strategy   independently of the order in which the bids are recorded because  of his deviation. More specifically:  Definition: Let G be a position auction with the   firstarrival rule, and let m be a directed mediator for G. The  11  It is clear however, that the resulting order γ is consistent  with the well-defined order of bids of N \ i.  T-strategy profile is an ex post equilibrium with respect to  m if for every player i and type vi, and for every vector of  types of the other players, v−i, the following two conditions  hold:  F1: i is not better off when he gives the directed mediator  the right of play and reports a false type. That is, for every  ˆvi ∈ Vi  wi(vi, mN (vi, v−i), γ(vi,v−i)  ) ≥ wi(vi, mN (ˆvi, v−i), γ(ˆvi,v−i)  ).  F2: i is not better off when he bids directly independently  of the resulting order of recorded bids. That is for every  bi ∈ Bi, and for every γ ∈ Γ, which is consistent with the  order of bids of members of N \ i resulting from the vector  of types v−i,  wi(vi, mN (vi, v−i), γ(vi,v−i)  ) ≥ wi(vi, (bi, mN\i(v−i)), γ).  The notion of valid directed mediators is analogously   defined:  Definition: Let G be a position auction with the   firstarrival rule. A directed mediator for G is valid, if for every  player, using the T-strategy guarantees a non-negative level  of utility.  Formally, a directed mediator m for G is valid, if for every  player i with type vi, for every subset S ⊆ N such that i ∈ S,  for every vS\i, and for every b−S, wi(vi, mS(vS), b−S, γ) ≥  0 for every γ ∈ Γ, which is consistent with the standard  order of bids of S determined by the mediator when the  reported types are vS.  The notion of implementation by mediation remains as  before: The directed mediator m implements the VCG   outcome function in G if ψm  = ϕvcg  .  Our previous results remain true for directed mediators for  position auctions with the first arrival rule. Next we show  that in contrast to Theorem 6, it is possible to implement the  VCG outcome function in every self-price position auction  with the first-arrival rule.  Theorem 7. Let G = G(α, p) be the self-price position  auction with the first arrival rule. There exists a valid   directed mediator that implements the VCG outcome function  in G.  In the following theorem we provide sufficient conditions  for implementing that the VCG outcome function in a   position auction with the first-arrival rule. A special   characteristic of auctions satisfying these sufficient conditions is  that players" payments may depend also on their own bid,  in contrast to the auctions discussed in Theorem 3. The long  proof of this theorem is in the spirit of all previous proofs,  and therefore it is omitted.  Theorem 8. Let G = G(α, p) be a position auction with  the first-arrival rule. If the following conditions hold then  there exists a valid directed mediator for G that implements  the VCG outcome function in G.  1. For every v ∈ V there exists b ∈ B such that pj(b) =  v(j) for every j ∈ K.  2. G is monotone.  3. pj(b) ≥ pj+1(b) for every j ∈ K and every b ∈ B.  4. For every j ∈ K and every b1  , b2  ∈ B such that b1  (l) =  b2  (l) for every l ≥ j, pj(b1  ) = pj(b2  ).  286  8. REFERENCES  [1] R.J. Aumann. Subjectivity and correlation in  randomized strategies. Journal of Mathematical  Economics, 1:67-96, 1974.  [2] N.A.R. Bhat, K. Leyton-Brown, Y. Shoham, and  M. Tennenholtz. Bidding Rings Revisited. Working  Paper, 2005.  [3] B. Edelman, M. Ostrovsky, and M. Schwarz. Internet  advertising and the generalized second price auction:  Selling billions of dollars worth of keywords. NBER  working paper 11765, Novenmber 2005.  [4] J. Feng, H.K. Bhargava, and D.M. Pennock.  Implementing sponsored search in web search engines:  Computational evaluation of alternative mechanisms.  INFORMS Journal on Computing, 2006.  [5] F. M. Forges. An approach to communication  equilibria. Econometrica, 54(6):1375-85, 1986.  [6] D. Graham and R. Marshall. Collusive Bidder  Behavior at Single-Object Second-Price and English  Auctions. Journal of Political Economy, 95:1217-1239,  1987.  [7] R. Holzman, N. Kfir-Dahav, D. Monderer, and  M. Tennenholtz. Bundling equilibrium in  combinatorial auctions. Games and Economic  Behavior, 47:104-123, 2004.  [8] E. Kalai and R.W. Rosenthal. Arbitration of  Two-Party Disputes under Ignorance. International  Journal of Game Theory, 7:65-72, 1976.  [9] S. Lahaie. An analysis of alternative slot auction  designs for sponsored search. In Proceedings of the 7th  ACM conference on Electronic commerce, pages  218-227, 2006.  [10] R. Lavi, A. Mu"alem, and N. Nisan. Towards a  characterization of truthful combinatorial auctions. In  Proceedings of the 44th Annual IEEE Symposium on  Foundations of Computer Science (FOCS)., 2003.  [11] R. McAfee and J. McMillan. Bidding Rings. American  Economic Review, 82:579-599, 1992.  [12] A. Mehta, A. Saberi, , V. Vazirani, and U. Vazirani.  Adwords and Generalized Online Matching. In  Twentieth International joint conference on Artificial  Intelligence (FOCS 05) , 2005.  [13] D. Monderer and M. Tennenholtz. K-Implementation.  Journal of Artificial Intelligence Research (JAIR),  21:37-62, 2004.  [14] D. Monderer and M. Tennenholtz. Strong mediated  equilibrium. In Proceedings of the AAAI, 2006.  [15] R. B. Myerson. Multistage games with  communication. Econometrica, 54(2):323-58, 1986.  [16] O. Rozenfeld and M. Tennenholtz. Routing mediators.  In Proceedings of the 23rd International Joint  Conferences on Artificial Intelligence(IJCAI-07),  pages 1488-1493, 2007.  [17] H. Varian. Position auctions. Technical report, UC  Berkeley, 2006.  287