There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. Our main result is an impossibility theorem which rules out linear rebate functions with non-zero efficiency in heterogeneous object assignment. Motivated by this theorem, we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with nonzero efficiency are possible when the valuations for the objects have some relationship. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed.
Consider that p resources are available and each of n > p
agents is interested in utilizing one of them. Naturally. we
should assign these resource such that those who value
them most get it. Since Groves mechanisms [
Often, the surplus money is not really needed in many
social settings such as allocations by the Government among
its departments, etc. Since strict budget balance cannot
coexist with DSIC and AE (Green-Laffont theorem [
In this paper, we consider the following problem. There are n agents and p heterogeneous objects (n p > 1). Each agent desires one object out of these p objects. Each agent’s valuation for any of the objects is independent of his valuations for the other objects. Valuations of the different agents are also mutually independent. Our goal is to design a mechanism for assignment of the p objects among the n agents which is allocatively efficient, dominant strategy incentive compatible, and maximizes the rebate (which is equivalent to minimizing the budget imbalance). In addition, we would like the mechanism to satisfy feasibility and individual rationality. Thus, we seek to design a Groves mechanism for assigning p heterogeneous objects among n agents satisfying: 1) Feasibility (F) or weak budget balance. That is, the total payment to the agents should be less than or equal to the total received payment. 2) Individual Rationality (IR), which means that each agent’s utility by participating in the mechanism should be non-negative. 3) Minimizes budget imbalance.
We call such a mechanism Groves redistribution mechanism or simply redistribution mechanism. Designing a redistribution mechanism involves design of an appropriate rebate function. If in a redistribution mechanism, the rebate function for each agent is a linear function of the valuations of the remaining agents, we refer to such a mechanism as a linear redistribution mechanism (LRM). In many situations, design of an appropriate LRM turns out to be a problem of solving a linear program.
Due to the Green-Laffont theorem [
Our paper seeks to non-trivially extend the results of
Moulin [
As it is impossible to achieve allocative efficiency, DSIC,
and budget balance simultaneously, we have to compromise
on one of these properties. Faltings [
In this paper, we investigate the question of existence of a linear rebate function for redistribution of surplus in assignment of heterogeneous objects. Our result shows that in general, when the domain of valuations for each agent is p R+, it is impossible to design a linear rebate function, with non-zero efficiency, for the heterogeneous settings. However, we can relax the assumption of independence of valuations of different objects to get a linear rebate function with nonzero efficiency. Another way to get around the impossibility theorem is to relax the linearity requirement of a rebate function. In particular, our contributions in this paper can be summarized as follows.
We first prove the impossibility of existence of a linear rebate function with non-zero efficiency for the heterogeneous settings when the domain of valuations for each agent is Rp+ and the valuations for the objects are independent.
When the objects are heterogeneous but the values for the objects of an agent can be derived from one single number, that is, the private information is still single dimensional, we design a Groves redistribution mechanism which is linear, anonymous, deterministic, feasible, individually rational, and efficient. In addition, the mechanism is worst case optimal.
We show the existence of a non-linear rebate function
that has non-zero efficiency. This is different from
the rebate function presented in [
The paper is organized as follows. In Section 2, we
introduce the notation followed in the paper and describe
some background work from the literature. In Section 3,
we state and prove the impossibility result. We derive an
extension of the WCO mechanism for heterogeneous objects
but with single dimensional private information in Section
4. The impossibility result does not rule out possibility of
non-linear rebate functions with strictly positive efficiency.
We show this with a redistribution mechanism, BAILEY,
which is Bailey’s mechanism [
The notation used is summarized in Table 2. Note that,
where the context is clear, we will use t; ti; ri; k, and vi to
indicate t(b); ti(b); ri(b); k(b), and vi(k(b)) respectively. In
this paper, we assume that the payment made by agent i is
of the form ti( ) ri( ), where ti( ) is agent i’s payment in
the Clarke pivotal mechanism [
When the objects are identical, every agent i has the same value for each object, call it vi. Without loss of generality, we will assume, v1 v2 : : : vn. In Clarke pivotal mechanism, the first p agents will receive the objects and each of these p agents will pay vp+1. So, the surplus in the n N p i j R+
i bi b K k(b) k (b) k i(b) vi(k(b))
v
ti(b)
t(b)
t i
ri(b)
e
system is pvp+1. For this situation, Moulin [
Guo and Conitzer [
p) n
1 j
Pn 1
k=p riW CO =
cj yj n 1 X j=p+1 n p n k for j = p + 1; : : : ; n 1: The efficiency of this mechanism is e , where e is given by, This has been shown to be optimal in the sense that no other mechanism can guarantee greater than e fraction redistribution in the worst case.
of
with Non-Zero
We have just reviewed the design of a redistribution mechanism for homogeneous objects. We have seen that the WCO mechanism is a linear function of the types of agents. We now explore the general case. In the homogeneous case, the bids are real numbers which can be arranged in decreasing order. The Clarke surplus is a linear function of these ordered bids. For the heterogeneous scenario, this p would not be the case. Each bid bi belongs to R+; hence, there is no unique way of defining an order among the bids. Moreover, the Clarke surplus is not a linear function of the received bids in the heterogeneous case. So, we cannot expect any linear/affine rebate function of types to work well at all type profiles. We will prove this formally.
We first generalize a theorem due to Guo and Conitzer
[
Theorem 3.1: Any deterministic, anonymous rebate function f is DSIC iff, ri = f (v1; v2; : : : ; vi 1; vi+1; : : : ; vn) 8 i 2 N (3) where, v1 < v2 < : : : < vn.
Proof: We provide only a sketch of the proof.
The “if” part: If ri takes the form given by equation (3), then the rebate of agent i is independent of his valuation. The allocation rule satisfies allocative efficiency. So, the mechanism is still Groves and hence DSIC. The rebate function defined is deterministic. If two agents have the same bids, then, as per the ordering defined in Appendix, <, they will have the same ranking. Suppose agents i and i + 1 have the same bids. Thus vi < vi+1 and vi+1 < vi. So, ri = f (v1; v2; : : : ; vi 1; vi+1; : : : ; vn) and ri+1 = f (v1; v2; : : : ; vi; vi+2; : : : ; vn). Since vi = vi+1, ri = ri+1. Thus the rebate function is anonymous.
The “only if” part: The homogeneous objects case is a special case of the mechanism. When objects are homogeneous, the ordering of the bids < matches the ordering on real numbers. If the rebate function is not in the form defined in the theorem, the rebate function would not simultaneously satisfy the DSIC, anonymity, and deterministic properties. This is because the above form of the rebate function is a necessary condition when the objects are identical. Thus we need a rebate function in this form in heterogeneous settings as well. We now state and prove the main result of this paper.
Theorem 3.2: If a redistribution mechanism is feasible and individually rational, then there cannot exist a linear rebate function which satisfies all the following properties: DSIC deterministic anonymous non-zero efficiency.
Proof : Assume that there exists a linear function, say f , which satisfies the above properties. Let v1 < v2 < : : : < vn. Then according to Theorem 3.1, for each agent i, ri = = f (v1; v2; : : : ; vi 1; vi+1; : : : ; vn) (c0; ep) + (c1; v1) + : : : + (cn 1; vn) where, ci = (ci1; ci2; : : : ; cip) 2 Rp, ep = (1; 1; : : : ; 1) 2 Rp, and ( ; ) denotes the inner product of two vectors in Rp. Now, we will show that the worst case performance of f will be zero. To this end, we will study the structure of f , step by step.
Observation 1: Consider type profile (v1; v2; : : : ; vn) where v1 = v2 = : : : = vn = (0; 0; : : : ; 0). For this type profile, (4) (5) (6) the total Clarke surplus is zero and ri = (c0; ep) 8 i 2 N . Individual rationality implies, From, (4) and (5), it is easy to see that, (c0; ep) = 0: Observation 2: Consider type profile (v1; v2; : : : ; vn) where v1 = (1; 0; 0; : : : ; 0) and v2 = : : : ; vn = (0; 0; : : : ; 0). For this type profile, r1 = 0 and if i 6= 1, ri = c11 0 for individual rationality. For this type profile, the Clarke surplus is zero. Thus, for feasibility, Pi ri = (n 1)c11 t = 0. This implies, c11 = 0.
In the above profile, by considering v1 = (0; 1; ; 0; : : : ; 0), we get c12 = 0. Similarly, one can show c13 = c14 = : : : = c1p = 0.
Observation 3: Continuing like above with, v1 = v2 = : : : = vi = ep, and vi+1 = (1; 0 : : : ; 0) or (0; 1; 0 : : : ; 0); : : : or (0; : : : ; 0; 1); we get, ci+1 = (0; 0; : : : ; 0) 8 i p 1. Thus, ri
8 (cp+1; vp+2) + : : : + (cn 1; vn) : if i = < (cp+1; vp+1) + : : : + (ci 1; vi 1) : +(ci; vi+1) + : : : + (cn 1; vn) : otherwise p + 1
We now claim that the efficiency of this mechanism is zero. That is, in the worst case, the fraction of the Clarke surplus that gets redistributed is zero. Suppose we show that there exists a type profile, for which the Clarke surplus is non-zero and the rebate to each agent is zero. Then the theorem is proved. So, it remains to show the existence of such a type profile. Consider the type profile: Feasibility should imply the total redistributed amount is less than the surplus, that is, (c0; ep) and vp+1 = vp+2 : : : = vn = (0; 0; : : : ; 0).
Now, with this type profile, agent 1 pays (p 1), agent 2 pays (p 2); : : : ; agent (p 1) pays 1 and the remaining agents pay 0. Thus, the Clarke payment received is non-zero but it can be seen that ri = 0 for all the agents. The above theorem provides disappointing news. It rules out the possibility of a linear redistribution mechanism for the heterogeneous settings which will have non-zero efficiency. However, there are two ways to get around it.
1) The domain of types under which Theorem 3.2 holds is, i = Rp+; 8 i 2 N . One idea is to restrict the domain of types. In Section 4, we design a worst case optimal linear redistribution mechanism when the valuations of agents for the heterogeneous objects have a certain type of relationship. 2) Explore the existence of a rebate function which is not a linear and yields a non-zero performance. We explore this in Section 5.
neous Objects When Valuations have Scaling
Consider a scenario where the objects are not identical but the valuations for the objects are related and can be derived by a single parameter. As a motivating example, consider the website somefreeads.com and assume that there are p slots available for advertisements and there are n agents interested in displaying their ads. Naturally, every agent will have a higher preference for a higher slot. Define click through rate of a slot as the number of times the ad is clicked, when the ad is displayed in that slot, divided by the number of impressions. Let the click through rates for slots be 1 2 3 : : : p. Assume that each agent has the same value for each click by the user, say vi. So, the agent’s value for the jth slot will be j vi. Let us use the phrase valuations with scaling based relationship to describe such valuations. We define this more formally below.
Definition 4.1: We say the valuations of the agents have scaling based relationship if there exist positive real numbers 1; 2; 3; : : : ; p > 0 such that, for each agent i 2 N , the valuation for object j, say ij , is of the form ij = j vi, where vi 2 R+ is a private signal observed by agent i. Without loss of generality, we assume, 1 2 3 : : : p > 0. We immediately note that the homogeneous setting is a special case that arises when 1 = 2 = 3 = : : : = p > 0
For the above setting, we design a Groves mechanism
which is almost budget balanced and optimal in the worst
case. Our mechanism is similar to that of Guo and Conitzer
[
The following theorem by Guo and Conitzer [
Theorem 4.1: For given n and real numbers a1; a2; : : : ; an, for any x1 x2 : : : xn 0, a1x1+a2x2+: : : anxn 0 iff
0 8j = 1; 2 : : : ; n j X ai i=1
We will use a linear rebate function. (For simplifying equations, we will assume that there are (n p) virtual objects, with p+1 = p+2 = : : : = n = 0). We propose the following mechanism:
The bids are sorted in decreasing order.
The highest bidder will be allotted the first object, the second highest bidder will be allotted the second object, and so on.
Agent i will pay ti ri, where ti is the Clarke payment and ri is the rebate.
ti =
p X( j j=i j+1)vj+1
ri = c0 + c1v1 + : : : + ci 1vi 1 + civi+1 + : : : + cn 1vn The mechanism is required to be individually rational and feasible.
The mechanism will be individually rational iff ri 0 8i 2 N . That is, 8 i 2 N , c0 + c1v1 + : : : + ci 1vi 1 + civi+1 + : : : + cn 1vn 0: The mechanism will be feasible if the total redistributed payment is less than or equal to the surplus. That is, Pi ri t = Pi ti or t Pi ri 0, where,
p t = X j( j j+1)vj+1:
j=1 With the above setup, we now derive c0; c1; : : : ; cn 1 that will maximize the fraction of the surplus which is redistributed among the agents.
Step 1: First, we claim that, c0 = c1 = 0. This can be proved as follows. Consider the type profile, v1 = v2 = : : : = vn = 0. For this type profile, individual rationality implies ri = c0 0 and t = 0. So for feasibility, Pi ri = nc0 t = 0. That is, c0 should be zero. Similarly, by considering type profile v1 = 1; v2 = : : : = vn = 0, we get c1 = 0. Step 2: Using c0 = c1 = 0,
The feasibility condition can be written as: (j 1)( j 1 j ) (j
1)cj 1 (n
) j)cj vj (n 1)cn 1vn 0 (7) n 1 ( X j=2 n 1 X j=2 +(n j)cj vj + (n 1)cn 1vn Step 4: Define 1 = 1 2, and for i = 2; : : : ; p; let i = i( i i+1) + i 1. Now, inequalities (7), (8), and (9) have to be satisfied for all values of v1 v2 : : : vn. Invoking Theorem (4.1), we need to satisfy the following set of inequalities: e p e i 1 n Pi 1 j=2 cj + (n
Pj i=2 ci
e 1 n Pi 1 j=2 cj + (n
i)ci e p n Pjn=21 cj 0 8j = 2; : : : n (n 2)c2 i)ci p
1 1 i 1 i = 3; : : : ; p p i = p + 1; : : : ; n
1 (10) Now, the social planner wishes to design a mechanism that maximizes e subject to the above constraints.
Define xj = Pij=2 ci for j = 2; : : : ; n 1. This is equivalent to solving the following linear program. maximize e s:t:
2)x2 i)xi e 1 (n 1 e i 1 ixi 1 + (n i 1 i = 3; : : : ; p e p ixi 1 + (n i)xi p i = p + 1; : : : ; n e p nxn 1 p xi 0 8i = 2; : : : ; n 1 1 (11) So, given n and p, the social planner will have to solve the above optimization problem and determine the optimal values of e; c2; c3; : : : ; cn 1. It would be of interest to derive a closed form solution for the above problem.
The discussion above can be summarized as the following theorem.
Theorem 4.2: When the valuations of the agents have scaling based relationship, for any p and n > p + 1, the linear redistribution mechanism obtained by solving LP (11) is worst case optimal among all Groves redistribution mechanisms that are feasible, individually rational, deterministic, and anonymous.
Proof: This can be proved following the line of arguments
of Guo and Conitzer [
the Heterogeneous Setting
We should note that the homogeneous objects case is a
special case of the heterogeneous objects case in which each
bidder submits the same bid for all objects. Thus, we cannot
expect any redistribution mechanism to perform better than
the homogeneous objects case. For n p+1, the worst case
redistribution is zero for the homogeneous case and so will
be for the heterogeneous case. So, we assume n > p+1. We
construct a redistribution scheme by applying the mechanism
proposed by Bailey [
First, consider the case when p = 1. Let the valuations of
the agents for the object be, v1 v2 : : : vn. The agent
with the highest valuation will receive the object and would
pay the second highest bid. Cavallo [
Motivated by this scheme, we propose a scheme for the heterogeneous setting. Suppose agent i is excluded from the system. Then let t i be the Clarke surplus in the system (defined in Table 2). Define,
riB = n1 t i 8 i 2 N (13) As the Clarke surplus is always positive, riB 0 for all i. Thus, this scheme satisfies individual rationality. t i t 8 i (revenue monotonicity). So, Pi riB = Pi n1 t i n n1 t = t. Thus, this scheme is feasible.
We now show that the BAILEY scheme has non-zero efficiency if n 2p + 1. First we state two lemmas. The proof will be given in Appendix B. These lemma’s are useful in designing redistribution mechanisms for the heterogeneous settings as well as in analysis of the mechanisms. Lemma 2 is used to show non-zero efficiency of the BAILEY mechanism. Lemma 1 is used to find an allocatively efficient outcome for the settings under consideration. Also, this lemma 1 is useful in determining the Clarke payments.
Lemma 1: If we sort the bids of all the agents for each object, then 1) An optimal allocation, that is an allocatively efficient allocation, will consist of the agents having bids among the p highest bids for each object. 2) Consider an optimal allocation k . If any of the p agents receiving objects in k is dropped, then there always exists an allocation k i that is an optimal allocation (on the remaining n 1 agents) which allocates objects to the remaining (p 1) agents. The objects that these p-1 agents receive in k i, may not however be the same as the objects they are allocated in k .
Lemma 2: There are at most 2p agents involved in deciding the Clarke payment.
Note: When the objects are identical, the bids of (p + 1) agents are involved in determining the Clarke payment.
Now, we show non-zero efficiency of the BAILEY redistribution scheme.
Proposition 1: The BAILEY redistribution scheme has non-zero efficiency, if n 2p + 1.
Proof: In Lemma 2, we have shown that there will be at most 2p agents involved in determining the Clarke surplus. Thus, given a type profile, there will be (n 2p) agents, for whom, t i = t and this implies that at least n n2p t will be redistributed.
Note: The proof of Proposition 1 indicates that the efficiency of this mechanism is at least n n2p .
We addressed the problem of assigning p heterogeneous objects among n > p competing agents. When the valuations of the agents are independent of each other and their valuations for each object are independent of valuations on the other objects, we proved the impossibility of the existence of a linear redistribution mechanism with nonzero efficiency. Then we explored two approaches to get around this impossibility. In the first approach, we showed that linear rebate functions with non-zero efficiency are possible when the valuations for the objects have scaling based relationship. In the second approach, we showed that rebate functions with non-zero efficiency are possible if linearity is relaxed.
It would be interesting to see if we can characterize the situations under which linear redistribution mechanisms with non-zero efficiency are possible for heterogeneous settings. Another interesting problem to explore is to design redistribution mechanisms that are worst case optimal for heterogeneous settings.
We will define a ranking among the agents. This ranking is used crucially in proving Theorem 3.1 on rebate function. This theorem is similar to Cavallo’s theorem on characterization of DSIC, deterministic, anonymous rebate functions for homogeneous objects. We would not be actually computing the order among the bidders. We will use this order for proving impossibility of the linear rebate function with the desired properties.
When we are defining ranking/ordering among the agents, we expect the following properties to hold true: Any permutation of the objects and the corresponding permutation on bid vector, (bi1; bi2; : : : ; bip) for each agent i, should not change the ranking. That is, the ranking should be independent of the order in which the agents are expected to bid for this objects. Two bidders with the same bid vectors should have the same rank.
By increasing the bid on any of the objects, the rank of an agent should not decrease.
This is a very crucial step. First, find out all feasible allocations of the p objects among the n agents, each agent receiving at most one object. Sort these allocations, according to the valuation of an allocation. Call this list L. To find the ranking between i and j, we use the following algorithm.
1) Lij = L 2) Delete all the allocations from Lij which contain both i and j. 3) Find out the first allocation in Lij which contains one of the agents i or j. Say k0.
a) Suppose this allocation contains i and has value strictly greater than any of the remaining allocations from Lij containing j, then we say, i j. b) Suppose this allocation contains j and has value strictly greater than any of the remaining allocations from Lij containing i, then we say, j i. 4) If the above step is not able to decide the ordering between i and j, let A = fk 2 Kjv(k) = v(k0)g. Update Lij = Lij nA and recur to step (2) till EITHER there is no allocation containing the agent i or j OR
the ordering between i and j is decided. 5) If the above steps do not give either of i j or j i, we say, i j or i < j as well as j < i
Before we state some properties of this ranking system <, we will explain it with an example. Let there be two items A and B, and four bidders. That is, p = 2; n = 4 and let their bids be: b1 = (4; 5); b2 = (2; 1); b3 = (1; 4); and b4 = (1; 0).
Now, allocation (A = 1; B = 3) has the highest valuation among all the allocations. So, agent 1 agent 1 agent 3 agent 3 agent 2 agent 4 agent 2 agent 4 (14) Now, in L13 defined in the procedure above, the allocation (A = 2; B = 1) has strictly higher value than any other allocation in which the agent 3 is present. So, Thus, agent 1
agent 3: agent 1 agent 3
agent 2 and agent 1 agent 3 agent 4 In L24, the allocation (A = 2; B = 1) has strictly higher value than any other allocation in which the agent 4 is present. Thus, the ranking of the agents is, agent 1 agent 3 agent 2 agent 4 We can show that the ranking defined above, satisfies the following properties.
1) < defines a total order on set of bids. 2) < is independent of the order of the objects.
Suppose an optimal allocation contains an agent whose bid for his winning object, say j, is not in the top p bids for the jth object. There are other (p 1) winners in an optimal allocation. So, there exists at least one agent whose bid is in the top p bids for the jth object and does not win any object. Thus, allocating him the jth object, we have an allocation which has higher valuation than the declared optimal allocation.
Suppose an agent i who receives an object in an optimal allocation is removed from the system. The agent will have at most one bid in the top p bids for each object. So, agents now having bids in the top p bids, will be at the pth position. It can be seen that there will be at most one agent in an optimal allocation who is on the pth position for the object he wins. If there is more than one agent in an optimal allocation on the pth position for the object they win, then we can improve on this allocation. Hence, after removing i, there will be at most one more agent who will be a part of a new optimal allocation.
Proof: The argument is as follows: 1) Sort the bids of the agents for each object. 2) The optimal allocation consists of agents having bids in the p highest bids for each of the objects (Lemma 1). 3) For computing the Clarke payment of the agent i, we remove the agent and determine an optimal allocation. And, using his bid, the valuation of optimal allocation with him and without him will determine his payment. This is done for each agent i. As per Lemma 1, if any agent from an optimal allocation is removed from the system, there exists a new optimal allocation which consists of at least (p 1) agents who received the objects in the original optimal allocation. 4) There will be p agents receiving the objects and determining their payments will involve removing one of them at a time, there will be at most p more agents who will influence the payment. Thus, there are at most 2p agents involved in determining the Clarke payment.