Worst-Case Optimal Redistribution of VCG Payments  Mingyu Guo  Duke University  Department of Computer Science  Durham, NC, USA  mingyu@cs.duke.edu  Vincent Conitzer  Duke University  Department of Computer Science  Durham, NC, USA  conitzer@cs.duke.edu  ABSTRACT  For allocation problems with one or more items, the   wellknown Vickrey-Clarke-Groves (VCG) mechanism is efficient,  strategy-proof, individually rational, and does not incur a  deficit. However, the VCG mechanism is not (strongly)  budget balanced: generally, the agents" payments will sum  to more than 0. If there is an auctioneer who is selling  the items, this may be desirable, because the surplus   payment corresponds to revenue for the auctioneer. However, if  the items do not have an owner and the agents are merely  interested in allocating the items efficiently among   themselves, any surplus payment is undesirable, because it will  have to flow out of the system of agents. In 2006,   Cavallo [3] proposed a mechanism that redistributes some of  the VCG payment back to the agents, while maintaining  efficiency, strategy-proofness, individual rationality, and the  non-deficit property. In this paper, we extend this result in a  restricted setting. We study allocation settings where there  are multiple indistinguishable units of a single good, and  agents have unit demand. (For this specific setting,   Cavallo"s mechanism coincides with a mechanism proposed by  Bailey in 1997 [2].) Here we propose a family of mechanisms  that redistribute some of the VCG payment back to the  agents. All mechanisms in the family are efficient,   strategyproof, individually rational, and never incur a deficit. The  family includes the Bailey-Cavallo mechanism as a special  case. We then provide an optimization model for finding the  optimal mechanism-that is, the mechanism that maximizes  redistribution in the worst case-inside the family, and show  how to cast this model as a linear program. We give both  numerical and analytical solutions of this linear program,  and the (unique) resulting mechanism shows significant   improvement over the Bailey-Cavallo mechanism (in the worst  case). Finally, we prove that the obtained mechanism is   optimal among all anonymous deterministic mechanisms that  satisfy the above properties.  Categories and Subject Descriptors  J.4 [Computer Applications]: Social and Behavioral   Sciences-Economics; I.2.11 [Distributed Artificial   Intelligence]: Multiagent Systems    1. INTRODUCTION  Many important problems in computer science and   electronic commerce can be modeled as resource allocation   problems. In such problems, we want to allocate the resources  (or items) to the agents that value them the most.   Unfortunately, agents" valuations are private knowledge, and  self-interested agents will lie about their valuations if this  is to their benefit. One solution is to auction off the items,  possibly in a combinatorial auction where agents can bid  on bundles of items. There exist ways of determining the  payments that the agents make in such an auction that   incentivizes the agents to report their true valuations-that  is, the payments make the auction strategy-proof. One very  general way of doing so is to use the VCG mechanism [23,  4, 12]. (The VCG mechanism is also known as the Clarke  mechanism or, in the specific context of auctions, the   Generalized Vickrey Auction.)  Besides strategy-proofness, the VCG mechanism has   several other nice properties in the context of resource   allocation problems. It is efficient: the chosen allocation always  maximizes the sum of the agents" valuations. It is also   (expost) individually rational: participating in the mechanism  never makes an agent worse off than not participating.   Finally, it has a no-deficit property: the sum of the agents"  payments is always nonnegative.  In many settings, another property that would be   desirable is (strong) budget balance, meaning that the payments  sum to exactly 0. Suppose the agents are trying to   distribute some resources among themselves that do not have  a previous owner. For example, the agents may be trying  to allocate the right to use a shared good on a given day.  Or, the agents may be trying to allocate a resource that  they have collectively constructed, discovered, or otherwise  obtained. If the agents use an auction to allocate these   resources, and the sum of the agents" payments in the auction  is positive, then this surplus payment must leave the system  30  of the agents (for example, the agents must give the money  to an outside party, or burn it). Na¨ıve redistribution of the  surplus payment (e.g. each of the n agents receives 1/n of  the surplus) will generally result in a mechanism that is not  strategy-proof (e.g. in a Vickrey auction, the second-highest  bidder would want to increase her bid to obtain a larger   redistribution payment). Unfortunately, the VCG mechanism  is not budget balanced: typically, there is surplus payment.  Unfortunately, in general settings, it is in fact impossible to  design mechanisms that satisfy budget balance in addition  to the other desirable properties [16, 11, 21].  In light of this impossibility result, several authors have  obtained budget balance by sacrificing some of the other  desirable properties [2, 6, 22, 5]. Another approach that  is perhaps preferable is to use a mechanism that is more  budget balanced than the VCG mechanism, and maintains  all the other desirable properties. One way of trying to   design such a mechanism is to redistribute some of the VCG  payment back to the agents in a way that will not affect the  agents" incentives (so that strategy-proofness is maintained),  and that will maintain the other properties. In 2006,   Cavallo [3] pursued exactly this idea, and designed a mechanism  that redistributes a large amount of the total VCG payment  while maintaining all of the other desirable properties of  the VCG mechanism. For example, in a single-item auction  (where the VCG mechanism coincides with the second-price  sealed-bid auction), the amount redistributed to bidder i  by Cavallo"s mechanism is 1/n times the second-highest bid  among bids other than i"s bid. The total redistributed is at  most the second-highest bid overall, and the redistribution  to agent i does not affect i"s incentives because it does not  depend on i"s own bid.  In this paper, we restrict our attention to a limited   setting, and in this setting we extend Cavallo"s result. We  study allocation settings where there are multiple   indistinguishable units of a single good, and all agents have unit  demand, i.e. they want only a single unit. For this specific  setting, Cavallo"s mechanism coincides with a mechanism  proposed by Bailey in 1997 [2]. Here we propose the family  of linear VCG redistribution mechanisms. All mechanisms  in this family are efficient, strategy-proof, individually   rational, and never incur a deficit. The family includes the  Bailey-Cavallo mechanism as a special case (with the caveat  that we only study allocation settings with multiple   indistinguishable units of a single good and unit demand, while  Bailey"s and Cavallo"s mechanisms can be applied outside  these settings as well). We then provide an optimization  model for finding the optimal mechanism inside the family,  based on worst-case analysis. Both numerical and   analytical solutions of this model are provided, and the resulting  mechanism shows significant improvement over the   BaileyCavallo mechanism (in the worst case). For example, for  the problem of allocating a single unit, when the number  of agents is 10, our mechanism always redistributes more  than 98% of the total VCG payment back to the agents  (whereas the Bailey-Cavallo mechanism redistributes only  80% in the worst case). Finally, we prove that our   mechanism is in fact optimal among all anonymous deterministic  mechanisms (even nonlinear ones) that satisfy the desirable  properties.  Around the same time, the same mechanism has been   independently derived by Moulin [19].1  Moulin actually   pursues a different objective (also based on worst-case analysis):  whereas our objective is to maximize the percentage of VCG  payments that are redistributed, Moulin tries to minimize  the overall payments from agents as a percentage of   efficiency. It turns out that the resulting mechanisms are the  same. Towards the end of this paper, we consider dropping  the individual rationality requirement, and show that this  does not change the optimal mechanism for our objective.  For Moulin"s objective, dropping individual rationality does  change the optimal mechanism (but only if there are   multiple units).  2. PROBLEM DESCRIPTION  Let n denote the number of agents, and let m denote the  number of units. We only consider the case where m < n  (otherwise the problem becomes trivial). We also assume  that m and n are always known. (This assumption is not  harmful: in environments where anyone can join the auction,  running a redistribution mechanism is typically not a good  idea anyway, because everyone would want to join to collect  part of the redistribution.)  Let the set of agents be {a1, a2, . . . , an}, where ai is the  agent with ith highest report value ˆvi-that is, we have ˆv1 ≥  ˆv2 ≥ . . . ≥ ˆvn ≥ 0. Let vi denote the true value of ai.  Given that the mechanism is strategy-proof, we can assume  vi = ˆvi.  Under the VCG mechanism, each agent among a1, . . . , am  wins a unit, and pays ˆvm+1 for this unit. Thus, the total  VCG payment equals mˆvm+1. When m = 1, this is the  second-price or Vickrey auction.  We modify the mechanism as follows. After running the  original VCG mechanism, the center returns to each agent  ai some amount zi, agent ai"s redistribution payment. We  do not allow zi to depend on ˆvi; because of this, ai"s   incentives are unaffected by this redistribution payment, and the  mechanism remains strategy-proof.  3. LINEAR VCG REDISTRIBUTION  MECHANISMS  We are now ready to introduce the family of linear VCG  redistribution mechanisms. Such a mechanism is defined by  a vector of constants c0, c1, . . . , cn−1. The amount that the  mechanism returns to agent ai is zi = c0 + c1ˆv1 + c2ˆv2 +  . . . + ci−1ˆvi−1 + ciˆvi+1 + . . . + cn−1ˆvn. That is, an agent  receives c0, plus c1 times the highest bid other than the  agent"s own bid, plus c2 times the second-highest other bid,  etc. The mechanism is strategy-proof, because for all i, zi  is independent of ˆvi. Also, the mechanism is anonymous.  It is helpful to see the entire list of redistribution   payments:  z1 = c0 + c1ˆv2 + c2ˆv3 + c3ˆv4 + . . . + cn−2ˆvn−1 + cn−1ˆvn  z2 = c0 + c1ˆv1 + c2ˆv3 + c3ˆv4 + . . . + cn−2ˆvn−1 + cn−1ˆvn  z3 = c0 + c1ˆv1 + c2ˆv2 + c3ˆv4 + . . . + cn−2ˆvn−1 + cn−1ˆvn  z4 = c0 + c1ˆv1 + c2ˆv2 + c3ˆv3 + . . . + cn−2ˆvn−1 + cn−1ˆvn  . . .  zi = c0 + c1ˆv1 + c2ˆv2 + . . . + ci−1ˆvi−1 + ciˆvi+1 + . . . + cn−1ˆvn  . . .  zn−2 = c0 + c1ˆv1 + c2ˆv2 + c3ˆv3 + . . . + cn−2ˆvn−1 + cn−1ˆvn  zn−1 = c0 + c1ˆv1 + c2ˆv2 + c3ˆv3 + . . . + cn−2ˆvn−2 + cn−1ˆvn  zn = c0 + c1ˆv1 + c2ˆv2 + c3ˆv3 + . . . + cn−2ˆvn−2 + cn−1ˆvn−1  1  We thank Rakesh Vohra for pointing us to Moulin"s   working paper.  31  Not all choices of the constants c0, . . . , cn−1 produce a  mechanism that is individually rational, and not all choices  of the constants produce a mechanism that never incurs a  deficit. Hence, to obtain these properties, we need to place  some constraints on the constants.  To satisfy the individual rationality criterion, each agent"s  utility should always be non-negative. An agent that does  not win a unit obtains a utility that is equal to the agent"s  redistribution payment. An agent that wins a unit obtains a  utility that is equal to the agent"s valuation for the unit,   minus the VCG payment ˆvm+1, plus the agent"s redistribution  payment.  Consider agent an, the agent with the lowest bid. Since  this agent does not win an item (m < n), her utility is just  her redistribution payment zn. Hence, for the mechanism  to be individually rational, the ci must be such that zn is  always nonnegative. If the ci have this property, then it  actually follows that zi is nonnegative for every i, for the  following reason. Suppose there exists some i < n and some  vector of bids ˆv1 ≥ ˆv2 ≥ . . . ≥ ˆvn ≥ 0 such that zi < 0.  Then, consider the bid vector that results from replacing ˆvj  by ˆvj+1 for all j ≥ i, and letting ˆvn = 0. If we omit ˆvn  from this vector, the same vector results that results from  omitting ˆvi from the original vector. Therefore, an"s   redistribution payment under the new vector should be the same as  ai"s redistribution payment under the old vector-but this  payment is negative.  If all redistribution payments are always nonnegative, then  the mechanism must be individually rational (because the  VCG mechanism is individually rational, and the   redistribution payment only increases an agent"s utility). Therefore,  the mechanism is individually rational if and only if for any  bid vector, zn ≥ 0.  To satisfy the non-deficit criterion, the sum of the   redistribution payments should be less than or equal to the total  VCG payment. So for any bid vector ˆv1 ≥ ˆv2 ≥ . . . ≥ ˆvn ≥  0, the constants ci should make z1 + z2 + . . . + zn ≤ mˆvm+1.  We define the family of linear VCG redistribution   mechanisms to be the set of all redistribution mechanisms   corresponding to constants ci that satisfy the above constraints  (so that the mechanisms will be individually rational and  have the no-deficit property). We now give two examples of  mechanisms in this family.  Example 1 (Bailey-Cavallo mechanism): Consider the  mechanism corresponding to cm+1 = m  n  and ci = 0 for all  other i. Under this mechanism, each agent receives a   redistribution payment of m  n  times the (m+1)th highest bid from  another agent. Hence, a1, . . . , am+1 receive a redistribution  payment of m  n  ˆvm+2, and the others receive m  n  ˆvm+1. Thus,  the total redistribution payment is (m+1)m  n  ˆvm+2 +(n−m−  1)m  n  ˆvm+1. This redistribution mechanism is individually   rational, because all the redistribution payments are   nonnegative, and never incurs a deficit, because (m + 1) m  n  ˆvm+2 +  (n−m−1)m  n  ˆvm+1 ≤ nm  n  ˆvm+1 = mˆvm+1. (We note that for  this mechanism to make sense, we need n ≥ m + 2.)  Example 2: Consider the mechanism corresponding to  cm+1 = m  n−m−1  , cm+2 = − m(m+1)  (n−m−1)(n−m−2)  , and ci = 0  for all other i. In this mechanism, each agent receives a  redistribution payment of m  n−m−1  times the (m + 1)th   highest reported value from other agents, minus m(m+1)  (n−m−1)(n−m−2)  times the (m+2)th highest reported value from other agents.  Thus, the total redistribution payment is mˆvm+1 −  m(m+1)(m+2)  (n−m−1)(n−m−2)  ˆvm+3. If n ≥ 2m+3 (which is equivalent to  m  n−m−1  ≥ m(m+1)  (n−m−1)(n−m−2)  ), then each agent always receives  a nonnegative redistribution payment, thus the mechanism  is individually rational. Also, the mechanism never incurs  a deficit, because the total VCG payment is mˆvm+1, which  is greater than the amount mˆvm+1 − m(m+1)(m+2)  (n−m−1)(n−m−2)  ˆvm+3  that is redistributed.  Which of these two mechanisms is better? Is there another  mechanism that is even better? This is what we study in  the next section.  4. OPTIMAL REDISTRIBUTION  MECHANISMS  Among all linear VCG redistribution mechanisms, we would  like to be able to identify the one that redistributes the  greatest percentage of the total VCG payment.2  This is not  a well-defined notion: it may be that one mechanism   redistributes more on some bid vectors, and another more on  other bid vectors. We emphasize that we do not assume that  a prior distribution over bidders" valuations is available, so  we cannot compare them based on expected redistribution.  Below, we study three well-defined ways of comparing   redistribution mechanisms: best-case performance, dominance,  and worst-case performance.  Best-case performance. One way of evaluating a   mechanism is by considering the highest redistribution   percentage that it achieves. Consider the previous two examples.  For the first example, the total redistribution payment is  (m + 1)m  n  ˆvm+2 + (n − m − 1)m  n  ˆvm+1. When ˆvm+2 = ˆvm+1,  this is equal to the total VCG payment mˆvm+1. Thus, this  mechanism redistributes 100% of the total VCG payment in  the best case. For the second example, the total   redistribution payment is mˆvm+1 − m(m+1)(m+2)  (n−m−1)(n−m−2)  ˆvm+3. When  ˆvm+3 = 0, this is equal to the total VCG payment mˆvm+1.  Thus, this mechanism also redistributes 100% of the total  VCG payment in the best case.  Moreover, there are actually infinitely many mechanisms  that redistribute 100% of the total VCG payment in the best  case-for example, any convex combination of the above two  will redistribute 100% if both ˆvm+2 = ˆvm+1 and ˆvm+3 = 0.  Dominance. Inside the family of linear VCG   redistribution mechanisms, we say one mechanism dominates another  mechanism if the first one redistributes at least as much as  the other for any bid vector. For the previous two examples,  neither dominates the other, because they each redistribute  100% in different cases. It turns out that there is no   mechanism in the family that dominates all other mechanisms in  the family. For suppose such a mechanism exists. Then,  it should dominate both examples above. Consider the   remaining VCG payment (the VCG payment failed to be   redistributed). The remaining VCG payment of the dominant  mechanism should be 0 whenever ˆvm+2 = ˆvm+1 or ˆvm+3 = 0.  Now, the remaining VCG payment is a linear function of the  ˆvi (linear redistribution), and therefore also a polynomial  function. The above implies that this function can be   written as (ˆvm+2 − ˆvm+1)(ˆvm+3)P(ˆv1, ˆv2, . . . , ˆvn), where P is a  2  The percentage redistributed seems the natural criterion to  use, among other things because it is scale-invariant: if we  multiply all bids by the same positive constant (for example,  if we change the units by re-expressing the bids in euros  instead of dollars), we would not want the behavior of our  mechanism to change.  32  polynomial function. But since the function must be linear  (has degree at most 1), it follows that P = 0. Thus, a   dominant mechanism would always redistribute all of the VCG  payment, which is not possible. (If it were possible, then our  worst-case optimal redistribution mechanism would also   always redistribute all of the VCG payment, and we will see  later that it does not.)  Worst-case performance. Finally, we can evaluate a  mechanism by considering the lowest redistribution   percentage that it guarantees. For the first example, the total   redistribution payment is (m+1)m  n  ˆvm+2 +(n−m−1)m  n  ˆvm+1,  which is greater than or equal to (n−m−1) m  n  ˆvm+1. So in the  worst case, which is when ˆvm+2 = 0, the percentage   redistributed is n−m−1  n  . For the second example, the total   redistribution payment is mˆvm+1 − m(m+1)(m+2)  (n−m−1)(n−m−2)  ˆvm+3, which  is greater than or equal to mˆvm+1(1− (m+1)(m+2)  (n−m−1)(n−m−2)  ). So  in the worst case, which is when ˆvm+3 = ˆvm+1, the   percentage redistributed is 1 − (m+1)(m+2)  (n−m−1)(n−m−2)  . Since we   assume that the number of agents n and the number of units  m are known, we can determine which example mechanism  has better worst-case performance by comparing the two  quantities. When n = 6 and m = 1, for the first example  (Bailey-Cavallo mechanism), the percentage redistributed in  the worst case is 2  3  , and for the second example, this   percentage is 1  2  , which implies that for this pair of n and m,  the first mechanism has better worst-case performance. On  the other hand, when n = 12 and m = 1, for the first   example, the percentage redistributed in the worst case is 5  6  , and  for the second example, this percentage is 14  15  , which implies  that this time the second mechanism has better worst-case  performance.  Thus, it seems most natural to compare mechanisms by  the percentage of total VCG payment that they redistribute  in the worst case. This percentage is undefined when the  total VCG payment is 0. To deal with this, technically, we  define the worst-case redistribution percentage as the largest  k so that the total amount redistributed is at least k times  the total VCG payment, for all bid vectors. (Hence, as long  as the total amount redistributed is at least 0 when the total  VCG payment is 0, these cases do not affect the worst-case  percentage.) This corresponds to the following optimization  problem:  Maximize k (the percentage redistributed in the  worst case)  Subject to:  For every bid vector ˆv1 ≥ ˆv2 ≥ . . . ≥ ˆvn ≥ 0  zn ≥ 0 (individual rationality)  z1 + z2 + . . . + zn ≤ mˆvm+1 (non-deficit)  z1 + z2 + . . . + zn ≥ kmˆvm+1 (worst-case constraint)  We recall that zi = c0 + c1ˆv1 + c2ˆv2 + . . . + ci−1ˆvi−1 +  ciˆvi+1 + . . . + cn−1ˆvn.  5. TRANSFORMATION TO LINEAR  PROGRAMMING  The optimization problem given in the previous section  can be rewritten as a linear program, based on the following  observations.  Claim 1. If c0, c1, . . . , cn−1 satisfy both the individual   rationality and the non-deficit constraints, then ci = 0 for  i = 0, . . . , m.  Proof. First, let us prove that c0 = 0. Consider the  bid vector in which ˆvi = 0 for all i. To obtain individual  rationality, we must have c0 ≥ 0. To satisfy the non-deficit  constraint, we must have c0 ≤ 0. Thus we know c0 = 0.  Now, if ci = 0 for all i, there is nothing to prove. Otherwise,  let j = min{i|ci = 0}. Assume that j ≤ m. We recall that  we can write the individual rationality constraint as follows:  zn = c0 +c1ˆv1 +c2ˆv2 +c3ˆv3 +. . .+cn−2ˆvn−2 +cn−1ˆvn−1 ≥ 0  for any bid vector. Let us consider the bid vector in which  ˆvi = 1 for i ≤ j and ˆvi = 0 for the rest. In this case zn = cj,  so we must have cj ≥ 0. The non-deficit constraint can  be written as follows: z1 + z2 + . . . + zn ≤ mˆvm+1 for any  bid vector. Consider the same bid vector as above. We have  zi = 0 for i ≤ j, because for these bids, the jth highest other  bid has value 0, so all the ci that are nonzero are multiplied  by 0. For i > j, we have zi = cj, because the jth highest  other bid has value 1, and all lower bids have value 0. So  the non-deficit constraint tells us that cj(n − j) ≤ mˆvm+1.  Because j ≤ m, ˆvm+1 = 0, so the right hand side is 0. We  also have n − j > 0 because j ≤ m < n. So cj ≤ 0. Because  we have already established that cj ≥ 0, it follows that  cj = 0; but this is contrary to assumption. So j > m.  Incidentally, this claim also shows that if m = n − 1,  then ci = 0 for all i. Thus, we are stuck with the VCG  mechanism. From here on, we only consider the case where  m < n − 1.  Claim 2. The individual rationality constraint can be   written as follows:  Pj  i=m+1 ci ≥ 0 for j = m + 1, . . . , n − 1.  Before proving this claim, we introduce the following lemma.  Lemma 1. Given a positive integer k and a set of real  constants s1, s2, . . . , sk, (s1t1 + s2t2 + . . . + sktk ≥ 0 for any  t1 ≥ t2 ≥ . . . ≥ tk ≥ 0) if and only if (  Pj  i=1 si ≥ 0 for  j = 1, 2, . . . , k).  Proof. Let di = ti −ti+1 for i = 1, 2, . . . , k−1, and dk =  tk. Then (s1t1 +s2t2 +. . .+sktk ≥ 0 for any t1 ≥ t2 ≥ . . . ≥  tk ≥ 0) is equivalent to ((  P1  i=1 si)d1 + (  P2  i=1 si)d2 + . . . +  (  Pk  i=1 si)dk ≥ 0 for any set of arbitrary non-negative dj).  When  Pj  i=1 si ≥ 0 for j = 1, 2, . . . , k, the above inequality  is obviously true. If for some j,  Pj  i=1 si < 0, if we set dj > 0  and di = 0 for all i = j, then the above inequality becomes  false. So  Pj  i=1 si ≥ 0 for j = 1, 2, . . . , k is both necessary  and sufficient.  We are now ready to present the proof of Claim 2.  Proof. The individual rationality constraint can be   written as zn = c0 + c1ˆv1 + c2ˆv2 + c3ˆv3 + . . . + cn−2ˆvn−2 +  cn−1ˆvn−1 ≥ 0 for any bid vector ˆv1 ≥ ˆv2 ≥ . . . ≥ ˆvn−1 ≥  ˆvn ≥ 0. We have already shown that ci = 0 for i ≤ m.  Thus, the above can be simplified to zn = cm+1ˆvm+1 +  cm+2ˆvm+2+. . .+cn−2ˆvn−2+cn−1ˆvn−1 ≥ 0 for any bid vector.  By the above lemma, this is equivalent to  Pj  i=m+1 ci ≥ 0  for j = m + 1, . . . , n − 1.  Claim 3. The non-deficit constraint and the worst-case  constraint can also be written as linear inequalities involving  only the ci and k.  Proof. The non-deficit constraint requires that for any  bid vector, z1 +z2 +. . .+zn ≤ mˆvm+1, where zi = c0 +c1ˆv1 +  33  c2ˆv2 +. . .+ci−1ˆvi−1 +ciˆvi+1 +. . .+cn−1ˆvn for i = 1, 2, . . . , n.  Because ci = 0 for i ≤ m, we can simplify this inequality to  qm+1ˆvm+1 + qm+2ˆvm+2 + . . . + qnˆvn ≥ 0  qm+1 = m − (n − m − 1)cm+1  qi = −(i−1)ci−1 −(n−i)ci, for i = m+2, . . . , n−1 (when  m + 2 > n − 1, this set of equalities is empty)  qn = −(n − 1)cn−1  By the above lemma, this is equivalent to  Pj  i=m+1 qi ≥ 0  for j = m + 1, . . . , n. So, we can simplify further as follows:  qm+1 ≥ 0 ⇐⇒ (n − m − 1)cm+1 ≤ m  qm+1 + . . . + qm+i ≥ 0 ⇐⇒ n  Pj=m+i−1  j=m+1 cj + (n − m −  i)cm+i ≤ m for i = 2, . . . , n − m − 1  qm+1 + . . . + qn ≥ 0 ⇐⇒ n  Pj=n−1  j=m+1 cj ≤ m  So, the non-deficit constraint can be written as a set of  linear inequalities involving only the ci.  The worst-case constraint can be also written as a set of  linear inequalities, by the following reasoning. The   worstcase constraint requires that for any bid input z1 +z2 +. . .+  zn ≥ kmˆvm+1, where zi = c0 +c1ˆv1 +c2ˆv2 +. . .+ci−1ˆvi−1 +  ciˆvi+1 + . . . + cn−1ˆvn for i = 1, 2, . . . , n. Because ci = 0 for  i ≤ m, we can simplify this inequality to  Qm+1ˆvm+1 + Qm+2ˆvm+2 + . . . + Qnˆvn ≥ 0  Qm+1 = (n − m − 1)cm+1 − km  Qi = (i − 1)ci−1 + (n − i)ci, for i = m + 2, . . . , n − 1  Qn = (n − 1)cn−1  By the above lemma, this is equivalent to  Pj  i=m+1 Qi ≥ 0  for j = m + 1, . . . , n. So, we can simplify further as follows:  Qm+1 ≥ 0 ⇐⇒ (n − m − 1)cm+1 ≥ km  Qm+1 + . . . + Qm+i ≥ 0 ⇐⇒ n  Pj=m+i−1  j=m+1 cj + (n − m −  i)cm+i ≥ km for i = 2, . . . , n − m − 1  Qm+1 + . . . + Qn ≥ 0 ⇐⇒ n  Pj=n−1  j=m+1 cj ≥ km  So, the worst-case constraint can also be written as a set  of linear inequalities involving only the ci and k.  Combining all the claims, we see that the original   optimization problem can be transformed into the following  linear program.  Variables: cm+1, cm+2, . . . , cn−1, k  Maximize k (the percentage redistributed in the  worst case)  Subject to:Pj  i=m+1 ci ≥ 0 for j = m + 1, . . . , n − 1  km ≤ (n − m − 1)cm+1 ≤ m  km ≤ n  Pj=m+i−1  j=m+1 cj + (n − m − i)cm+i ≤ m for  i = 2, . . . , n − m − 1  km ≤ n  Pj=n−1  j=m+1 cj ≤ m  6. NUMERICAL RESULTS  For selected values of n and m, we solved the linear   program using Glpk (GNU Linear Programming Kit). In the  table below, we present the results for a single unit (m = 1).  We present 1−k (the percentage of the total VCG payment  that is not redistributed by the worst-case optimal   mechanism in the worst case) instead of k in the second column  because writing k would require too many significant digits.  Correspondingly, the third column displays the percentage  5 10 15 20 25 30  0.1  0.2  0.3  0.4  0.5  0.6  0.7  0.8  0.9  1  Number of AgentsWorst−caseRedistributionPercentage  1 Unit WO  1 Unit BC  2 Units WO  2 Units BC  3 Units WO  3 Units BC  4 Units WO  4 Units BC  Figure 1: A comparison of the worst-case optimal  mechanism (WO) and the Bailey-Cavallo mechanism  (BC).  of the total VCG payment that is not redistributed by the  Bailey-Cavallo mechanism in the worst case (which is equal  to 2  n  ).  n 1 − k Bailey − Cavallo Mechanism  3 66.7% 66.7%  4 42.9% 50.0%  5 26.7% 40.0%  6 16.1% 33.3%  7 9.52% 28.6%  8 5.51% 25.0%  9 3.14% 22.2%  10 1.76% 20.0%  20 3.62e − 5 10.0%  30 5.40e − 8 6.67e − 2  40 7.09e − 11 5.00e − 2  The worst-case optimal mechanism significantly   outperforms the Bailey-Cavallo mechanism in the worst case.   Perhaps more surprisingly, the worst-case optimal mechanism  sometimes does better in the worst case than the   BaileyCavallo mechanism does on average, as the following   example shows.  Recall that the total redistribution payment of the   BaileyCavallo mechanism is (m + 1)m  n  ˆvm+2 + (n − m − 1)m  n  ˆvm+1.  For the single-unit case, this simplifies to 2  n  ˆv3 + n−2  n  ˆv2.  Hence the percentage of the total VCG payment that is  not redistributed is  ˆv2− 2  n  ˆv3− n−2  n  ˆv2  ˆv2  = 2  n  − 2  n  ˆv3  ˆv2  , which has  an expected value of E( 2  n  − 2  n  ˆv3  ˆv2  ) = 2  n  − 2  n  E ˆv3  ˆv2  .   Suppose the bid values are drawn from a uniform distribution  over [0, 1]. The theory of order statistics tells us that the  34  joint probability density function of ˆv2 and ˆv3 is f(ˆv3, ˆv2) =  n(n − 1)(n − 2)ˆvn−3  3 (1 − ˆv2) for ˆv2 ≥ ˆv3. Now, E ˆv3  ˆv2  =  R 1  0  R ˆv2  0  ˆv3  ˆv2  f(ˆv3, ˆv2)dˆv3dˆv2 = n−2  n−1  . So, the expected value of  the remaining percentage is 2  n  − 2  n  n−2  n−1  = 2  n(n−1)  . For n = 20,  this is 5.26e − 3, whereas the remaining percentage for the  worst-case optimal mechanism is 3.62e−5 in the worst case.  Let us present the optimal solution for the case n = 5 in  detail. By solving the above linear program, we find that the  optimal values for the ci are c2 = 11  45  , c3 = −1  9  , and c4 = 1  15  .  That is, the redistribution payment received by each agent  is: 11  45  times the second highest bid among the other agents,  minus 1  9  times the third highest bid among the other agents,  plus 1  15  times the fourth highest bid among the other agents.  The total amount redistributed is 11  15  ˆv2 + 4  15  ˆv3 − 4  15  ˆv4 +  4  15  ˆv5; in the worst case, 11  15  ˆv2 is redistributed. Hence, the  percentage of the total VCG payment that is not   redistributed is never more than 4  15  = 26.7%.  Finally, we compare the worst-case optimal mechanism to  the Bailey-Cavallo mechanism for m = 1, 2, 3, 4, n = m +  2, . . . , 30. These results are in Figure 1.  We see that for any m, when n = m + 2, the worst-case  optimal mechanism has the same worst-case performance as  the Bailey-Cavallo mechanism (actually, in this case, the  worst-case optimal mechanism is identical to the   BaileyCavallo mechanism). When n > m + 2, the worst-case   optimal mechanism outperforms the Bailey-Cavallo mechanism  (in the worst case).  7. ANALYTICAL CHARACTERIZATION  OF THE WORST-CASE OPTIMAL  MECHANISM  We recall that our linear program has the following form:  Variables: cm+1, cm+2, . . . , cn−1, k  Maximize k (the percentage redistributed in the  worst case)  Subject to:Pj  i=m+1 ci ≥ 0 for j = m + 1, . . . , n − 1  km ≤ (n − m − 1)cm+1 ≤ m  km ≤ n  Pj=m+i−1  j=m+1 cj + (n − m − i)cm+i ≤ m for  i = 2, . . . , n − m − 1  km ≤ n  Pj=n−1  j=m+1 cj ≤ m  A linear program has no solution if and only if either the  objective is unbounded, or the constraints are contradictory  (there is no feasible solution). It is easy to see that k is  bounded above by 1 (redistributing more than 100%   violates the non-deficit constraint). Also, a feasible solution  always exists, for example, k = 0 and ci = 0 for all i. So an  optimal solution always exists. Observe that the linear   program model depends only on the number of agents n and the  number of units m. Hence the optimal solution is a function  of n and m. It turns out that this optimal solution can be  analytically characterized as follows.  Theorem 1. For any m and n with n ≥ m+2, the   worstcase optimal mechanism (among linear VCG redistribution  mechanisms) is unique. For this mechanism, the percentage  redistributed in the worst case is  k∗  = 1 −  `n−1  m  ´  Pn−1  j=m  `n−1  j  ´  The worst-case optimal mechanism is characterized by the  following values for the ci:  c∗  i =  (−1)i+m−1  (n − m)  `n−1  m−1  ´  i  Pn−1  j=m  `n−1  j  ´  1  `n−1  i  ´  n−1X  j=i  n − 1  j  !  for i = m + 1, . . . , n − 1.  It should be noted that we have proved ci = 0 for i ≤ m in  Claim 1.  Proof. We first rewrite the linear program as follows.  We introduce new variables xm+1, xm+2, . . . , xn−1, defined  by xj =  Pj  i=m+1 ci for j = m + 1, . . . , n − 1. The linear  program then becomes:  Variables: xm+1, xm+2, . . . , xn−1, k  Maximize k  Subject to:  km ≤ (n − m − 1)xm+1 ≤ m  km ≤ (m + i)xm+i−1 + (n − m − i)xm+i ≤ m for  i = 2, . . . , n − m − 1  km ≤ nxn−1 ≤ m  xi ≥ 0 for i = m + 1, m + 2, . . . , n − 1  We will prove that for any optimal solution to this linear  program, k = k∗  . Moreover, we will prove that when k = k∗  ,  xj =  Pj  i=m+1 c∗  i for j = m + 1, . . . , n − 1. This will prove  the theorem.  We first make the following observations:  (n − m − 1)c∗  m+1  = (n − m − 1)  (n−m)(n−1  m−1)  (m+1)  Pn−1  j=m (n−1  j )  1  (n−1  m+1)  Pn−1  j=m+1  `n−1  j  ´  = (n − m − 1)  (n−m)(n−1  m−1)  (m+1)  Pn−1  j=m (n−1  j )  1  (n−1  m+1)  (  Pn−1  j=m  `n−1  j  ´  −  `n−1  m  ´  )  = (n − m − 1) m  n−m−1  − (n − m − 1)  m(n−1  m )  (n−m−1)  Pn−1  j=m (n−1  j )  = m − (1 − k∗  )m = k∗  m  For i = m + 1, . . . , n − 2,  ic∗  i + (n − i − 1)c∗  i+1  = i  (−1)i+m−1  (n−m)(n−1  m−1)  i  Pn−1  j=m (n−1  j )  1  (n−1  i )  Pn−1  j=i  `n−1  j  ´  +  (n − i − 1)  (−1)i+m  (n−m)(n−1  m−1)  (i+1)  Pn−1  j=m (n−1  j )  1  (n−1  i+1 )  Pn−1  j=i+1  `n−1  j  ´  =  (−1)i+m−1  (n−m)(n−1  m−1)  Pn−1  j=m (n−1  j )  1  (n−1  i )  Pn−1  j=i  `n−1  j  ´  −  (n − i − 1)  (−1)i+m−1  (n−m)(n−1  m−1)  (i+1)  Pn−1  j=m (n−1  j )  i+1  (n−1  i )(n−i−1)  Pn−1  j=i+1  `n−1  j  ´  =  (−1)i+m−1  (n−m)(n−1  m−1)  Pn−1  j=m (n−1  j )  = (−1)i+m−1  m(1 − k∗  )  Finally,  (n − 1)c∗  n−1  = (n − 1)  (−1)n+m  (n−m)(n−1  m−1)  (n−1)  Pn−1  j=m (n−1  j )  1  (n−1  n−1)  Pn−1  j=n−1  `n−1  j  ´  = (−1)m+n  m(1 − k∗  )  Summarizing the above, we have:  (n − m − 1)c∗  m+1 = k∗  m  (m + 1)c∗  m+1 + (n − m − 2)c∗  m+2 = m(1 − k∗  )  (m + 2)c∗  m+2 + (n − m − 3)c∗  m+3 = −m(1 − k∗  )  (m + 3)c∗  m+3 + (n − m − 4)c∗  m+4 = m(1 − k∗  )  ...  35  (n − 3)c∗  n−3 + 2c∗  n−2 = (−1)m+n−2  m(1 − k∗  )  (n − 2)c∗  n−2 + c∗  n−1 = (−1)m+n−1  m(1 − k∗  )  (n − 1)c∗  n−1 = (−1)m+n  m(1 − k∗  )  Let x∗  j =  Pj  i=m+1 c∗  i for j = m + 1, m + 2, . . . , n − 1, the  first equation in the above tells us that  (n − m − 1)x∗  m+1 = k∗  m.  By adding the first two equations, we get  (m + 2)x∗  m+1 + (n − m − 2)x∗  m+2 = m  By adding the first three equations, we get  (m + 3)x∗  m+2 + (n − m − 3)x∗  m+3 = k∗  m  By adding the first i equations, where i = 2, . . . , n−m−1,  we get  (m + i)x∗  m+i−1 + (n − m − i)x∗  m+i = m if i is even  (m + i)x∗  m+i−1 + (n − m − i)x∗  m+i = k∗  m if i is odd  Finally by adding all the equations, we get  nx∗  n−1 = m if n − m is even;  nx∗  n−1 = k∗  m if n − m is odd.  Thus, for all of the constraints other than the   nonnegativity constraints, we have shown that they are satisfied by  setting xj = x∗  j =  Pj  i=m+1 c∗  i and k = k∗  . We next show  that the nonnegativity constraints are satisfied by these   settings as well.  For m + 1 ≤ i, i + 1 ≤ n − 1, we have  1  i  Pn−1  j=i (n−1  j )  (n−1  i )  = 1  i  Pn−1  j=i  i!(n−1−i)!  j!(n−1−j)!  ≥ 1  i+1  Pn−2  j=i  i!(n−1−i)!  j!(n−1−j)!  ≥  1  i+1  Pn−2  j=i  (i+1)!(n−1−i−1)!  (j+1)!(n−1−j−1)!  = 1  i+1  Pn−1  j=i+1 (n−1  j )  (n−1  i+1 )  This implies that the absolute value of c∗  i is decreasing  as i increases (if the c∗  contains more than one number).  We further observe that the sign of c∗  i alternates, with the  first element c∗  m+1 positive. So x∗  j =  Pj  i=m+1 c∗  i ≥ 0 for  all j. Thus, we have shown that these xi = x∗  i together  with k = k∗  form a feasible solution of the linear program.  We proceed to show that it is in fact the unique optimal  solution.  First we prove the following claim:  Claim 4. If ˆk, ˆxi, i = m + 1, m + 2, . . . , n − 1 satisfy the  following inequalities:  ˆkm ≤ (n − m − 1)ˆxm+1 ≤ m  ˆkm ≤ (m + i)ˆxm+i−1 + (n − m − i)ˆxm+i ≤ m for  i = 2, . . . , n − m − 1  ˆkm ≤ nˆxn−1 ≤ m  ˆk ≥ k∗  Then we must have that ˆxi = ˆx∗  i and ˆk = k∗  .  Proof of claim. Consider the first inequality. We know  that (n − m − 1)x∗  m+1 = k∗  m, so (n − m − 1)ˆxm+1 ≥ ˆkm ≥  k∗  m = (n − m − 1)x∗  m+1. It follows that ˆxm+1 ≥ x∗  m+1  (n − m − 1 = 0).  Now, consider the next inequality for i = 2. We know  that (m + 2)x∗  m+1 + (n − m − 2)x∗  m+2 = m. It follows that  (n−m−2)ˆxm+2 ≤ m−(m+2)ˆxm+1 ≤ m−(m+2)x∗  m+1 =  (n − m − 2)x∗  m+2, so ˆxm+2 ≤ x∗  m+2 (i = 2 ≤ n − m − 1 ⇒  n − m − 2 = 0).  Now consider the next inequality for i = 3. We know  that (m + 3)x∗  m+2 + (n − m − 3)x∗  m+3 = m. It follows that  (n−m−3)ˆxm+3 ≥ ˆkm−(m+3)ˆxm+2 ≥ k∗  m−(m+3)x∗  m+2 =  (n − m − 3)x∗  m+3, so ˆxm+3 ≥ x∗  m+3 (i = 3 ≤ n − m − 1 ⇒  n − m − 3 = 0).  Proceeding like this all the way up to i = n−m−1, we get  that ˆxm+i ≥ x∗  m+i if i is odd and ˆxm+i ≤ x∗  m+i if i is even.  Moreover, if one inequality is strict, then all subsequent   inequalities are strict. Now, if we can prove ˆxn−1 = x∗  n−1,  it would follow that the x∗  i are equal to the ˆxi (which also  implies that ˆk = k∗  ). We consider two cases:  Case 1: n − m is even. We have: n − m even ⇒ n − m − 1  odd ⇒ ˆxn−1 ≥ x∗  n−1. We also have: n−m even ⇒ nx∗  n−1 =  m. Combining these two, we get m = nx∗  n−1 ≤ nˆxn−1 ≤  m ⇒ ˆxn−1 = x∗  n−1.  Case 2: n − m is odd. In this case, we have ˆxn−1 ≤ x∗  n−1,  and nx∗  n−1 = k∗  m. Then, we have: k∗  m ≤ ˆkm ≤ nˆxn−1 ≤  nx∗  n−1 = k∗  m ⇒ ˆxn−1 = x∗  n−1.  This completes the proof of the claim.  It follows that if ˆk, ˆxi, i = m + 1, m + 2, . . . , n − 1 is a  feasible solution and ˆk ≥ k∗  , then since all the inequalities  in Claim 4 are satisfied, we must have ˆxi = x∗  i and ˆk =  k∗  . Hence no other feasible solution is as good as the one  described in the theorem.  Knowing the analytical characterization of the worst-case  optimal mechanism provides us with at least two major   benefits. First, using these formulas is computationally more  efficient than solving the linear program using a   generalpurpose solver. Second, we can derive the following   corollary.  Corollary 1. If the number of units m is fixed, then as  the number of agents n increases, the worst-case percentage  redistributed linearly converges to 1, with a rate of   convergence 1  2  . (That is, limn→∞  1−k∗  n+1  1−k∗  n  = 1  2  . That is, in the  limit, the percentage that is not redistributed halves for   every additional agent.)  We note that this is consistent with the experimental data  for the single-unit case, where the worst-case remaining   percentage roughly halves each time we add another agent.  The worst-case percentage that is redistributed under the  Bailey-Cavallo mechanism also converges to 1 as the   number of agents goes to infinity, but the convergence is much  slower-it does not converge linearly (that is, letting kC  n be  the percentage redistributed by the Bailey-Cavallo   mechanism in the worst case for n agents, limn→∞  1−kC  n+1  1−kC  n  =  limn→∞  n  n+1  = 1). We now present the proof of the   corollary.  Proof. When the number of agents is n, the worst-case  percentage redistributed is k∗  n = 1 −  (n−1  m )  Pn−1  j=m (n−1  j )  . When the  number of agents is n + 1, the percentage becomes k∗  n+1 =  1 −  (n  m)  Pn  j=m (n  j )  . For n sufficiently large, we will have 2n  −  mnm−1  > 0, and hence  1−k∗  n+1  1−k∗  n  =  (n  m)  Pn−1  j=m (n−1  j )  (n−1  m )  Pn  j=m (n  j )  =  n  n−m  2n−1  −  Pm−1  j=0 (n−1  j )  2n−  Pm−1  j=0 (n  j )  , and n  n−m  2n−1  −m(n−1)m−1  2n ≤  1−k∗  n+1  1−k∗  n  ≤ n  n−m  2n−1  2n−mnm−1 (because  `n  j  ´  ≤ ni  if j ≤ i).  Since we have  limn→∞  n  n−m  2n−1  −m(n−1)m−1  2n = 1  2  , and  limn→∞  n  n−m  2n−1  2n−mnm−1 = 1  2  ,  it follows that limn→∞  1−k∗  n+1  1−k∗  n  = 1  2  .  36  8. WORST-CASE OPTIMALITY OUTSIDE  THE FAMILY  In this section, we prove that the worst-case optimal   redistribution mechanism among linear VCG redistribution  mechanisms is in fact optimal (in the worst case) among  all redistribution mechanisms that are deterministic,   anonymous, strategy-proof, efficient and satisfy the non-deficit  constraint. Thus, restricting our attention to linear VCG  redistribution mechanisms did not come at a loss.  To prove this theorem, we need the following lemma. This  lemma is not new: it was informally stated by Cavallo [3].  For completeness, we present it here with a detailed proof.  Lemma 2. A VCG redistribution mechanism is   deterministic, anonymous and strategy-proof if and only if there exists  a function f : Rn−1  → R, so that the redistribution payment  zi received by ai satisfies  zi = f(ˆv1, ˆv2, . . . , ˆvi−1, ˆvi+1, . . . , ˆvn)  for all i and all bid vectors.  Proof. First, let us prove the only if direction, that is,  if a VCG redistribution mechanism is deterministic,   anonymous and strategy-proof then there exists a deterministic  function f : Rn−1  → R, which makes  zi = f(ˆv1, ˆv2, . . . , ˆvi−1, ˆvi+1, . . . , ˆvn)  for all i and all bid vectors.  If a VCG redistribution mechanism is deterministic and  anonymous, then for any bid vector ˆv1 ≥ ˆv2 ≥ . . . ≥ ˆvn, the  mechanism outputs a unique redistribution payment list:  z1, z2, . . . , zn. Let G : Rn  → Rn  be the function that  maps ˆv1, ˆv2, . . . , ˆvn to z1, z2, . . . , zn for all bid vectors. Let  H(i, x1, x2, . . . , xn) be the ith element of G(x1, x2, . . . , xn),  so that zi = H(i, ˆv1, ˆv2, . . . , ˆvn) for all bid vectors and all  1 ≤ i ≤ n. Because the mechanism is anonymous, two  agents should receive the same redistribution payment if  their bids are the same. So, if ˆvi = ˆvj, H(i, ˆv1, ˆv2, . . . , ˆvn) =  H(j, ˆv1, ˆv2, . . . , ˆvn). Hence, if we let j = min{t|ˆvt = ˆvi},  then H(i, ˆv1, ˆv2, . . . , ˆvn) = H(j, ˆv1, ˆv2, . . . , ˆvn).  Let us define K : Rn  → N × Rn  as follows: K(y, x1, x2,  . . . , xn−1) = [j, w1, w2, . . . , wn], where w1, w2, . . . , wn are  y, x1, x2, . . . , xn−1 sorted in descending order, and  j = min{t|wt = y}. ({t|wt = y} = ∅ because y ∈ {w1, w2,  . . . , wn}). Also let us define F : Rn  → R by  F(ˆvi, ˆv1, ˆv2, . . . , ˆvi−1, ˆvi+1, . . . , ˆvn)  = H ◦ K(ˆvi, ˆv1, ˆv2, . . . , ˆvi−1, ˆvi+1, . . . , ˆvn)  = H(min{t|ˆvt = ˆvi}, ˆv1, ˆv2, . . . , ˆvn)  = H(i, ˆv1, ˆv2, . . . , ˆvn) = zi.  That is, F is the redistribution payment to an agent that  bids ˆvi when the other bids are ˆv1, ˆv2, . . . , ˆvi−1, ˆvi+1, . . . , ˆvn.  Since our mechanism is required to be strategy-proof, and  the space of valuations is unrestricted, zi should be   independent of ˆvi by Lemma 1 in Cavallo [3]. Hence, we can simply  ignore the first variable input to F; let f(x1, x2, . . . , xn−1) =  F(0, x1, x2, . . . , xn−1). So, we have for all bid vectors and  i, zi = f(ˆv1, ˆv2, . . . , ˆvi−1, ˆvi+1, . . . , ˆvn). This completes the  proof for the only if direction.  For the if direction, if the redistribution payment   received by ai satisfies zi = f(ˆv1, ˆv2, . . . , ˆvi−1, ˆvi+1, . . . , ˆvn) for  all bid vectors and i, then this is clearly a deterministic and  anonymous mechanism. To prove strategy-proofness, we   observe that because an agent"s redistribution payment is not  affected by her own bid, her incentives are the same as in  the VCG mechanism, which is strategy-proof.  Now we are ready to introduce the next theorem:  Theorem 2. For any m and n with n ≥ m+2, the   worstcase optimal mechanism among the family of linear VCG  redistribution mechanisms is worst-case optimal among all  mechanisms that are deterministic, anonymous, strategy-proof,  efficient and satisfy the non-deficit constraint.  While we needed individual rationality earlier in the   paper, this theorem does not mention it, that is, we can not  find a mechanism with better worst-case performance even if  we sacrifice individual rationality. (The worst-case optimal  linear VCG redistribution mechanism is of course   individually rational.)  Proof. Suppose there is a redistribution mechanism (when  the number of units is m and the number of agents is n) that  satisfies all of the above properties and has a better   worstcase performance than the worst-case optimal linear VCG  redistribution mechanism, that is, its worst-case   redistribution percentage ˆk is strictly greater than k∗  .  By Lemma 2, for this mechanism, there is a function f :  Rn−1  → R so that zi = f(ˆv1, ˆv2, . . . , ˆvi−1, ˆvi+1, . . . , ˆvn) for  all i and all bid vectors. We first prove that f has the  following properties.  Claim 5. f(1, 1, . . . , 1, 0, 0, . . . , 0) = 0 if the number of  1s is less than or equal to m.  Proof of claim. We assumed that for this mechanism,  the worst-case redistribution percentage satisfies ˆk > k∗  ≥  0. If the total VCG payment is x, the total redistribution  payment should be in [ˆkx, x] (non-deficit criterion).   Consider the case where all agents bid 0, so that the total VCG  payment is also 0. Hence, the total redistribution payment  should be in [ˆk · 0, 0]-that is, it should be 0. Hence every  agent"s redistribution payment f(0, 0, . . . , 0) must be 0.  Now, let ti = f(1, 1, . . . , 1, 0, 0, . . . , 0) where the number  of 1s equals i. We proved t0 = 0. If tn−1 = 0, consider the  bid vector where everyone bids 1. The total VCG payment is  m and the total redistribution payment is nf(1, 1, . . . , 1) =  ntn−1 = 0. This corresponds to 0% redistribution, which is  contrary to our assumption that ˆk > k∗  ≥ 0. Now, consider  j = min{i|ti = 0} (which is well-defined because tn−1 = 0).  If j > m, the property is satisfied. If j ≤ m, consider  the bid vector where ˆvi = 1 for i ≤ j and ˆvi = 0 for all  other i. Under this bid vector, the first j agents each get  redistribution payment tj−1 = 0, and the remaining n − j  agents each get tj. Thus, the total redistribution payment  is (n − j)tj. Because the total VCG payment for this bid  vector is 0, we must have (n − j)tj = 0. So tj = 0 (j ≤  m < n). But this is contrary to the definition of j. Hence  f(1, 1, . . . , 1, 0, 0, . . . , 0) = 0 if the number of 1s is less than  or equal to m.  Claim 6. f satisfies the following inequalities:  ˆkm ≤ (n − m − 1)tm+1 ≤ m  ˆkm ≤ (m + i)tm+i−1 + (n − m − i)tm+i ≤ m for  i = 2, 3, . . . , n − m − 1  ˆkm ≤ ntn−1 ≤ m  Here ti is defined as in the proof of Claim 5.  37  Proof of claim. For j = m + 1, . . . , n, consider the bid  vectors where ˆvi = 1 for i ≤ j and ˆvi = 0 for all other i.  These bid vectors together with the non-deficit constraint  and worst-case constraint produce the above set of   inequalities: for example, when j = m + 1, we consider the bid  vector ˆvi = 1 for i ≤ m + 1 and ˆvi = 0 for all other i.  The first m+1 agents each receive a redistribution payment  of tm = 0, and all other agents each receive tm+1. Thus,  the total VCG redistribution is (n − m − 1)tm+1. The   nondeficit constraint gives (n − m − 1)tm+1 ≤ m (because the  total VCG payment is m). The worst-case constraint gives  (n − m − 1)tm+1 ≥ ˆkm. Combining these two, we get the  first inequality. The other inequalities can be obtained in  the same way.  We now observe that the inequalities in Claim 6, together  with ˆk ≥ k∗  , are the same as those in Claim 4 (where the ti  are replaced by the ˆxi). Thus, we can conclude that ˆk = k∗  ,  which is contrary to our assumption ˆk > k∗  . Hence no   mechanism satisfying all the listed properties has a redistribution  percentage greater than k∗  in the worst case.  So far we have only talked about the case where n ≥ m+2.  For the purpose of completeness, we provide the following  claim for the n = m + 1 case.  Claim 7. For any m and n with n = m + 1, the original  VCG mechanism (that is, redistributing nothing) is (uniquely)  worst-case optimal among all redistribution mechanisms that  are deterministic, anonymous, strategy-proof, efficient and  satisfy the non-deficit constraint.  We recall that when n = m+1, Claim 1 tells us that the only  mechanism inside the family of linear redistribution   mechanisms is the original VCG mechanism, so that this   mechanism is automatically worst-case optimal inside this family.  However, to prove the above claim, we need to show that it  is worst-case optimal among all redistribution mechanisms  that have the desired properties.  Proof. Suppose a redistribution mechanism exists that  satisfies all of the above properties and has a worst-case  performance as good as the original VCG mechanism, that  is, its worst-case redistribution percentage is greater than  or equal to 0. This implies that the total redistribution  payment of this mechanism is always nonnegative.  By Lemma 2, for this mechanism, there is a function f :  Rn−1  → R so that zi = f(ˆv1, ˆv2, . . . , ˆvi−1, ˆvi+1, . . . , ˆvn) for  all i and all bid vectors. We will prove that f(x1, x2, . . . , xn−1)  = 0 for all x1 ≥ x2 ≥ . . . ≥ xn−1 ≥ 0.  First, consider the bid vector where ˆvi = 0 for all i. Here,  each agent receives a redistribution payment f(0, 0, . . . , 0).  The total redistribution payment is then nf(0, 0, . . . , 0), which  should be both greater than or equal to 0 (by the above  observation) as well less than or equal to 0 (using the   nondeficit criterion and the fact that the total VCG payment is  0). It follows that f(0, 0, . . . , 0) = 0. Now, let us consider  the bid vector where ˆv1 = x1 ≥ 0 and ˆvi = 0 for all other i.  For this bid vector, the agent with the highest bid receives  a redistribution payment of f(0, 0, . . . , 0) = 0, and the other  n − 1 agents each receive f(x1, 0, . . . , 0). By the same   reasoning as above, the total redistribution payment should be  both greater than or equal to 0 and less than or equal to 0,  hence f(x1, 0, . . . , 0) = 0 for all x1 ≥ 0.  Proceeding by induction, let us assume f(x1, x2, . . . , xk,  0, . . . , 0) = 0 for all x1 ≥ x2 ≥ . . . ≥ xk ≥ 0, for some  k < n − 1. Consider the bid vector where ˆvi = xi for  i ≤ k + 1, and ˆvi = 0 for all other i, where the xi are   arbitrary numbers satisfying x1 ≥ x2 ≥ . . . ≥ xk ≥ xk+1 ≥ 0.  For the agents with the highest k + 1 bids, their   redistribution payment is specified by f acting on an input with  only k non-zero variables. Hence they all receive 0 by   induction assumption. The other n − k − 1 agents each   receive f(x1, x2, . . . , xk, xk+1, 0, . . . , 0). The total   redistribution payment is then (n−k−1)f(x1, x2, . . . , xk, xk+1, 0, . . . , 0),  which should be both greater than or equal to 0, and less  than or equal to the total VCG payment. Now, in this bid  vector, the lowest bid is 0 because k + 1 < n. But since  n = m + 1, the total VCG payment is mˆvn = 0. So  we have f(x1, x2, . . . , xk, xk+1, 0, . . . , 0) = 0 for all x1 ≥  x2 ≥ . . . ≥ xk ≥ xk+1 ≥ 0. By induction, this   statement holds for all k < n − 1; when k + 1 = n − 1, we  have f(x1, x2, . . . , xn−2, xn−1) = 0 for all x1 ≥ x2 ≥ . . . ≥  xn−2 ≥ xn−1 ≥ 0. Hence, in this mechanism, the   redistribution payment is always 0; that is, the mechanism is just  the original VCG mechanism.  Incidentally, we obtain the following corollary:  Corollary 2. No VCG redistribution mechanism   satisfies all of the following: determinism, anonymity,   strategyproofness, efficiency, and (strong) budget balance. This holds  for any n ≥ m + 1.  Proof. For the case n ≥ m + 2: If such a mechanism  exists, its worst-case performance would be better than that  of the worst-case optimal linear VCG redistribution   mechanism, which by Theorem 1 obtains a redistribution   percentage strictly less than 1. But Theorem 2 shows that it is  impossible to outperform this mechanism in the worst case.  For the case n = m + 1: If such a mechanism exists,  it would perform as well as the original VCG mechanism  in the worst case, which implies that it is identical to the  VCG mechanism by Claim 7. But the VCG mechanism is  not (strongly) budget balanced.  9. CONCLUSIONS  For allocation problems with one or more items, the   wellknown Vickrey-Clarke-Groves (VCG) mechanism is efficient,  strategy-proof, individually rational, and does not incur a  deficit. However, the VCG mechanism is not (strongly)  budget balanced: generally, the agents" payments will sum  to more than 0. If there is an auctioneer who is selling  the items, this may be desirable, because the surplus   payment corresponds to revenue for the auctioneer. However, if  the items do not have an owner and the agents are merely  interested in allocating the items efficiently among   themselves, any surplus payment is undesirable, because it will  have to flow out of the system of agents. In 2006,   Cavallo [3] proposed a mechanism that redistributes some of  the VCG payment back to the agents, while maintaining   efficiency, strategy-proofness, individual rationality, and the  non-deficit property. In this paper, we extended this   result in a restricted setting. We studied allocation settings  where there are multiple indistinguishable units of a   single good, and agents have unit demand. (For this specific  setting, Cavallo"s mechanism coincides with a mechanism  proposed by Bailey in 1997 [2].) Here we proposed a family  of mechanisms that redistribute some of the VCG payment  38  back to the agents. All mechanisms in the family are   efficient, strategy-proof, individually rational, and never incur  a deficit. The family includes the Bailey-Cavallo mechanism  as a special case. We then provided an optimization model  for finding the optimal mechanism-that is, the mechanism  that maximizes redistribution in the worst case-inside the  family, and showed how to cast this model as a linear   program. We gave both numerical and analytical solutions  of this linear program, and the (unique) resulting   mechanism shows significant improvement over the Bailey-Cavallo  mechanism (in the worst case). Finally, we proved that the  obtained mechanism is optimal among all anonymous   deterministic mechanisms that satisfy the above properties.  One important direction for future research is to try to  extend these results beyond multi-unit auctions with unit  demand. However, it turns out that in sufficiently general  settings, the worst-case optimal redistribution percentage  is 0. In such settings, the worst-case criterion provides no  guidance in determining a good redistribution mechanism  (even redistributing nothing achieves the optimal worst-case  percentage), so it becomes necessary to pursue other criteria.  Alternatively, one can try to identify other special settings  in which positive redistribution in the worst case is possible.  Another direction for future research is to consider whether  this mechanism has applications to collusion. For example,  in a typical collusive scheme, there is a bidding ring   consisting of a number of colluders, who submit only a single  bid [10, 17]. If this bid wins, the colluders must allocate the  item amongst themselves, perhaps using payments-but of  course they do not want payments to flow out of the ring.  This work is part of a growing literature on designing  mechanisms that obtain good results in the worst case.   Traditionally, economists have mostly focused either on   designing mechanisms that always obtain certain properties (such  as the VCG mechanism), or on designing mechanisms that  are optimal with respect to some prior distribution over the  agents" preferences (such as the Myerson auction [20] and the  Maskin-Riley auction [18] for maximizing expected revenue).  Some more recent papers have focused on designing   mechanisms for profit maximization using worst-case competitive  analysis (e.g. [9, 1, 15, 8]). There has also been growing  interest in the design of online mechanisms [7] where the  agents arrive over time and decisions must be taken before  all the agents have arrived. Such work often also takes a  worst-case competitive analysis approach [14, 13]. It does  not appear that there are direct connections between our  work and these other works that focus on designing   mechanisms that perform well in the worst case. Nevertheless,  it seems likely that future research will continue to   investigate mechanism design for the worst case, and hopefully a  coherent framework will emerge.  10. REFERENCES  [1] G. Aggarwal, A. Fiat, A. Goldberg, J. Hartline,  N. Immorlica, and M. Sudan. Derandomization of  auctions. STOC, 619-625, 2005.  [2] M. J. Bailey. The demand revealing process: to  distribute the surplus. Public Choice, 91:107-126,  1997.  [3] R. Cavallo. Optimal decision-making with minimal  waste: Strategyproof redistribution of VCG payments.  AAMAS, 882-889, 2006.  [4] E. H. Clarke. Multipart pricing of public goods. Public  Choice, 11:17-33, 1971.  [5] B. Faltings. A budget-balanced, incentive-compatible  scheme for social choice. AMEC, 30-43, 2005.  [6] J. Feigenbaum, C. Papadimitriou, and S. Shenker.  Sharing the cost of muliticast transmissions. JCSS,  63:21-41, 2001.  [7] E. Friedman and D. Parkes. Pricing WiFi at  Starbucks - Issues in online mechanism design. EC,  240-241, 2003.  [8] A. Goldberg, J. Hartline, A. Karlin, M. Saks, and  A. Wright. Competitive auctions. Games and  Economic Behavior, 2006.  [9] A. Goldberg, J. Hartline, and A. Wright. Competitive  auctions and digital goods. SODA, 735-744, 2001.  [10] D. A. Graham and R. C. Marshall. Collusive bidder  behavior at single-object second-price and English  auctions. Journal of Political Economy,  95(6):1217-1239, 1987.  [11] J. Green and J.-J. Laffont. Characterization of  satisfactory mechanisms for the revelation of  preferences for public goods. Econometrica,  45:427-438, 1977.  [12] T. Groves. Incentives in teams. Econometrica,  41:617-631, 1973.  [13] M. T. Hajiaghayi, R. Kleinberg, M. Mahdian, and  D. C. Parkes. Online auctions with re-usable goods.  EC, 165-174, 2005.  [14] M. T. Hajiaghayi, R. Kleinberg, and D. C. Parkes.  Adaptive limited-supply online auctions. EC, 71-80,  2004.  [15] J. Hartline and R. McGrew. From optimal limited to  unlimited supply auctions. EC, 175-182, 2005.  [16] L. Hurwicz. On the existence of allocation systems  whose manipulative Nash equilibria are Pareto  optimal, 1975. Presented at the 3rd World Congress of  the Econometric Society.  [17] K. Leyton-Brown, Y. Shoham, and M. Tennenholtz.  Bidding clubs in first-price auctions. AAAI, 373-378,  2002.  [18] E. Maskin and J. Riley. Optimal multi-unit auctions.  In F. Hahn, editor, The Economics of Missing  Markets, Information, and Games, chapter 14,  312-335. Clarendon Press, Oxford, 1989.  [19] H. Moulin. Efficient and strategy-proof assignment  with a cheap residual claimant. Working paper, March  2007.  [20] R. Myerson. Optimal auction design. Mathematics of  Operations Research, 6:58-73, 1981.  [21] R. Myerson and M. Satterthwaite. Efficient  mechanisms for bilateral trading. Journal of Economic  Theory, 28:265-281, 1983.  [22] D. Parkes, J. Kalagnanam, and M. Eso. Achieving  budget-balance with Vickrey-based payment schemes  in exchanges. IJCAI, 1161-1168, 2001.  [23] W. Vickrey. Counterspeculation, auctions, and  competitive sealed tenders. Journal of Finance,  16:8-37, 1961.  39