=Paper=
{{Paper
|id=Vol-494/paper-19
|storemode=property
|title=Redistribution Mechanisms for the Assignment of Heterogeneous Objects
|pdfUrl=https://ceur-ws.org/Vol-494/famaspaper1.pdf
|volume=Vol-494
|dblpUrl=https://dblp.org/rec/conf/mallow/GujarN09
}}
==Redistribution Mechanisms for the Assignment of Heterogeneous Objects==
https://ceur-ws.org/Vol-494/famaspaper1.pdf
Redistribution Mechanisms for Assignment of Heterogeneous Objects
Sujit Gujar Y Narahari
Dept of Computer Science and Automation Dept of Computer Science and Automation
Indian Institute of Science Indian Institute of Science
Bangalore, India Bangalore, India
sujit@csa.iisc.ernet.in hari@csa.iisc.ernet.in
Abstract far as possible, preserving DSIC and AE. This idea was
originally proposed by Laffont [11]. The total payment made
There are p heterogeneous objects to be assigned to n by the mechanism as a redistribution will be referred to as
competing agents (n > p) each with unit demand. It is the rebate to the agents.
required to design a Groves mechanism for this assign- In this paper, we consider the following problem. There
ment problem satisfying weak budget balance, individual are n agents and p heterogeneous objects (n ≥ p > 1).
rationality, and minimizing the budget imbalance. This calls Each agent desires one object out of these p objects. Each
for designing an appropriate rebate function. Our main agent’s valuation for any of the objects is independent of his
result is an impossibility theorem which rules out linear valuations for the other objects. Valuations of the different
rebate functions with non-zero efficiency in heterogeneous agents are also mutually independent. Our goal is to design
object assignment. Motivated by this theorem, we explore a mechanism for assignment of the p objects among the
two approaches to get around this impossibility. In the first n agents which is allocatively efficient, dominant strategy
approach, we show that linear rebate functions with non- incentive compatible, and maximizes the rebate (which is
zero efficiency are possible when the valuations for the equivalent to minimizing the budget imbalance). In addition,
objects have some relationship. In the second approach, we would like the mechanism to satisfy feasibility and
we show that rebate functions with non-zero efficiency are individual rationality. Thus, we seek to design a Groves
possible if linearity is relaxed. mechanism for assigning p heterogeneous objects among n
Keywords: Groves Mechanism, Budget imbalance, Redistri- agents satisfying:
bution mechanism, Rebate function
1) Feasibility (F) or weak budget balance. That is, the
total payment to the agents should be less than or equal
1. Introduction to the total received payment.
2) Individual Rationality (IR), which means that each
Consider that p resources are available and each of n > p
agent’s utility by participating in the mechanism
agents is interested in utilizing one of them. Naturally. we
should be non-negative.
should assign these resource such that those who value
3) Minimizes budget imbalance.
them most get it. Since Groves mechanisms [13], [3], [6]
have attractive game theoretic properties such as domi- We call such a mechanism Groves redistribution mech-
nant strategy incentive compatibility (DSIC) and allocative anism or simply redistribution mechanism. Designing a
efficiency (AE), Groves mechanisms are widely used in redistribution mechanism involves design of an appropriate
practice. However, in general, a Groves mechanism need not rebate function. If in a redistribution mechanism, the rebate
be budget balanced. That is, the total transfer of money in function for each agent is a linear function of the valuations
the system may not be zero. So the system will be left with of the remaining agents, we refer to such a mechanism as a
a surplus or deficit. Using Clarke’s mechanism [3], we can linear redistribution mechanism (LRM). In many situations,
ensure under fairly weak conditions that there is no deficit design of an appropriate LRM turns out to be a problem of
of money, that is the mechanism is weakly budget balanced. solving a linear program.
In such a case, the system or the auctioneer will be left with Due to the Green-Laffont theorem [5], we cannot guaran-
some money. tee 100% redistribution at all type profiles. So a performance
Often, the surplus money is not really needed in many index for the redistribution mechanism would be the worst
social settings such as allocations by the Government among case redistribution. That is, the fraction of the surplus which
its departments, etc. Since strict budget balance cannot is guaranteed to be redistributed irrespective of the bid
coexist with DSIC and AE (Green-Laffont theorem [5]), we profiles. This fraction will be referred to as efficiency in
would like to redistribute the surplus to the participants as the rest of the paper (Note: This efficiency is not to be
confused with allocative efficiency). The advantage of worst of different objects to get a linear rebate function with non-
case analysis is that, it does not require any distributional zero efficiency. Another way to get around the impossibility
information on the type sets of the agents. It is desirable theorem is to relax the linearity requirement of a rebate
that the rebate function is deterministic and anonymous. function. In particular, our contributions in this paper can
A rebate function is said to be anonymous if two agents be summarized as follows.
having the same bids get the same rebate. So, the aim • We first prove the impossibility of existence of a
is to design an anonymous, deterministic rebate function linear rebate function with non-zero efficiency for the
which maximizes the efficiency and satisfies feasibility and heterogeneous settings when the domain of valuations
individual rationality. for each agent is Rp+ and the valuations for the objects
Our paper seeks to non-trivially extend the results of are independent.
Moulin [12] and Guo and Conitzer [8] who have indepen- • When the objects are heterogeneous but the values
dently designed a Groves mechanism in order to redistribute for the objects of an agent can be derived from one
the surplus when objects are identical (homogeneous objects single number, that is, the private information is still
case). Their mechanism is deterministic, anonymous, and single dimensional, we design a Groves redistribution
has maximum efficiency over all possible Groves redis- mechanism which is linear, anonymous, deterministic,
tribution mechanisms. We will refer to their mechanism feasible, individually rational, and efficient. In addition,
as the worst case optimal (WCO) mechanism. The WCO the mechanism is worst case optimal.
Mechanism is a linear redistribution mechanisms. In this • We show the existence of a non-linear rebate function
paper, we concentrate on designing a linear redistribution that has non-zero efficiency. This is different from
mechanism for the heterogeneous objects case. the rebate function presented in [7] which is only
conjectured to have non-zero efficiency.
1.1. Relevant Work The paper is organized as follows. In Section 2, we
introduce the notation followed in the paper and describe
As it is impossible to achieve allocative efficiency, DSIC, some background work from the literature. In Section 3,
and budget balance simultaneously, we have to compromise we state and prove the impossibility result. We derive an
on one of these properties. Faltings [4] and Guo and Conitzer extension of the WCO mechanism for heterogeneous objects
[9] achieve budget balance by compromising on AE. If we but with single dimensional private information in Section
are interested in preserving AE and DSIC, we have to settle 4. The impossibility result does not rule out possibility of
for a non-zero surplus or a non-zero deficit of the money non-linear rebate functions with strictly positive efficiency.
(budget imbalance) in the system. To reduce budget imbal- We show this with a redistribution mechanism, BAILEY,
ance, various rebate functions have been designed by Bailey which is Bailey’s mechanism [1] applied to the settings
[1], Cavallo [2], Moulin [12], and Guo and Conitzer [8]. under consideration in Section 5. We will conclude the paper
Moulin [12] and Guo and Conitzer [8] designed a Groves in Section 6. We need an ordering of the bids of the agents
redistribution mechanism for assignment of p homogeneous which we define in Appendix A.
objects among n > p agents with unit demand. Guo and
Conitzer [10] designed a redistribution mechanism which is
optimal in the expected sense for the homogeneous objects 2. Preliminaries and Notation
setting. Thus, it will require some distributional information
over the type sets of the agents. Gujar and Narahari [7] have The notation used is summarized in Table 2. Note that,
designed a non-linear rebate function in the heterogeneous where the context is clear, we will use t, ti , ri , k, and vi to
settings. However they only conjectured that the rebate indicate t(b), ti (b), ri (b), k(b), and vi (k(b)) respectively. In
function has a non-zero efficiency and is worst case optimal. this paper, we assume that the payment made by agent i is
To the best of our knowledge, linear rebate functions have of the form ti (·) − ri (·), where ti (·) is agent i’sPpayment in
not been investigated in the heterogeneous settings. the Clarke pivotal mechanism [3]. We refer to i ti , as the
total Clarke payment or the surplus in the system.
1.2. Contributions and Outline
2.1. Optimal Worst Case Redistribution when Ob-
In this paper, we investigate the question of existence jects are Identical
of a linear rebate function for redistribution of surplus in
assignment of heterogeneous objects. Our result shows that When the objects are identical, every agent i has the same
in general, when the domain of valuations for each agent is value for each object, call it vi . Without loss of generality,
Rp+ , it is impossible to design a linear rebate function, with we will assume, v1 ≥ v2 ≥ . . . ≥ vn . In Clarke pivotal
non-zero efficiency, for the heterogeneous settings. However, mechanism, the first p agents will receive the objects and
we can relax the assumption of independence of valuations each of these p agents will pay vp+1 . So, the surplus in the
n Number of agents
N Set of the agents = {1, 2, . . . , n}
p Number of objects
i Index for an agent, i = 1, 2, . . . , n
j Index for object, j = 1, 2, . . . , p
R+ Set of positive real numbers
Θi The space of valuations of agent i, = Rp+
bi Bid submitted by agent i, = (bi1 , bi2 , . . . , bip ) ∈ Θi
b (b1 , b2 , . . . , bn ), the bid vector
K The set of all allocations of p objects to n agents, each getting at most one object
k(b) An allocation, k(. ) ∈ K, corresponding to the bid profile b
k∗ (b) An allocatively efficient allocation when the bid profile is b
∗ (b)
k−i An allocatively efficient allocation when the bid profile is b and agent i is
excluded from the system
vi (k(b)) Valuation of the allocation k to the agent i,
when b is the bid profile P
v v : K → R, the valuation function, v(k(b)) = i∈N vi (k(b))
ti (b) Payment made by agent i in the Clarke “ pivotal mechanism, ” when the bid
profile is b, ti (b) = vi (k∗ (b)) − v(k∗ (b)) − v(k−i ∗ (b))
t(b) The ClarkeP payment, that is, the total payment received from all the agents,
t(b) = i∈N ti
t−i The Clarke payment received in the absence of the agent i
ri (b) Rebate to agent i when bid profile is b P
ri (b)
e The efficiency of the mechanism, = inf b:t6=0 t(b)
Table 1. Notation
system is pvp+1 . For this situation, Moulin [12] and Guo and
Conitzer [8] have independently designed a redistribution n−1
mechanism. p
e∗ = 1 −
Guo and Conitzer [8] maximize the worst case fraction of Pn−1 n − 1
the total surplus which gets redistributed. This mechanism k=p k
is called the WCO mechanism. Moulin [12] minimizes
the ratio of budget imbalance to the value of an optimal This has been shown to be optimal in the sense that no
allocation, that is the value of an allocatively efficient other mechanism can guarantee greater than e∗ fraction
allocation. The WCO mechanism coincides with Moulin’s redistribution in the worst case.
feasible and individually rational mechanism. Both the above
mechanisms work as follows. After receiving bids from 3. Impossibility of Linear Rebate Function
the agents, bids are sorted in decreasing order. The first with Non-Zero
p agents receive the objects. Each agent’s Clarke payment Efficiency
is calculated, say ti . Every agent i pays, pi = ti − ri ,
where, ri is the rebate function for an agent i. Suppose
We have just reviewed the design of a redistribution
y1 ≥ y2 ≥ . . . ≥ yn−1 are the bids of the (n − 1) agents
mechanism for homogeneous objects. We have seen that the
excluding the agent i, then the rebate to the agent i is given
WCO mechanism is a linear function of the types of agents.
by,
We now explore the general case. In the homogeneous
case, the bids are real numbers which can be arranged in
n−1
X decreasing order. The Clarke surplus is a linear function
riW CO = cj yj (1)
of these ordered bids. For the heterogeneous scenario, this
j=p+1
would not be the case. Each bid bi belongs to Rp+ ; hence,
where, there is no unique way of defining an order among the bids.
Moreover, the Clarke surplus is not a linear function of
n−1 the received bids in the heterogeneous case. So, we cannot
(−1)j+p−1 (n − p)
n−1
p−1
n−1 expect any linear/affine rebate function of types to work well
X
cj =
at all type profiles. We will prove this formally.
n − 1 Pn−1 n − 1 k
j k=p
k=j
We first generalize a theorem due to Guo and Conitzer
j k
(2) [8]. The context in which Guo and Conitzer [8] stated and
for j = p + 1, . . . , n − 1. proved the theorem is in the homogeneous setting. We show
The efficiency of this mechanism is e∗ , where e∗ is given by, that this result holds true in the heterogeneous objects case
also. The symbol < denotes the order over the bids of the the total Clarke surplus is zero and ri = (c0 , ep ) ∀ i ∈ N .
agents, as defined in the Appendix A.2. Individual rationality implies,
Theorem 3.1: Any deterministic, anonymous rebate func-
tion f is DSIC iff, (c0 , ep ) ≥ 0 (4)
ri = f (v1 , v2 , . . . , vi−1 , vi+1 , . . . , vn ) ∀ i ∈ N (3) Feasibility should imply the total redistributed amount is less
than the surplus, that is,
where, v1 < v2 < . . . < vn . X
Proof: We provide only a sketch of the proof. ri = n(c0 , ep ) 6 0 (5)
i
• The “if” part: If ri takes the form given by equation
(3), then the rebate of agent i is independent of his From, (4) and (5), it is easy to see that, (c0 , ep ) = 0.
valuation. The allocation rule satisfies allocative effi-
ciency. So, the mechanism is still Groves and hence Observation 2: Consider type profile (v1 , v2 , . . . , vn ) where
DSIC. The rebate function defined is deterministic. v1 = (1, 0, 0, . . . , 0) and v2 = . . . , vn = (0, 0, . . . , 0). For
If two agents have the same bids, then, as per the this type profile, r1 = 0 and if i 6= 1, ri = c11 ≥ 0 for
ordering defined in Appendix, <, they will have the individual rationality. For this type
P profile, the Clarke surplus
same ranking. Suppose agents i and i + 1 have the is zero. Thus, for feasibility, i ri = (n − 1)c11 ≤ t = 0.
same bids. Thus vi < vi+1 and vi+1 < vi . So, This implies, c11 = 0.
ri = f (v1 , v2 , . . . , vi−1 , vi+1 , . . . , vn ) and ri+1 = In the above profile, by considering v1 = (0, 1, , 0, . . . , 0),
f (v1 , v2 , . . . , vi , vi+2 , . . . , vn ). Since vi = vi+1 , ri = we get c12 = 0. Similarly, one can show c13 = c14 = . . . =
ri+1 . Thus the rebate function is anonymous. c1p = 0.
• The “only if” part: The homogeneous objects case is
a special case of the mechanism. When objects are Observation 3: Continuing like above with, v1 = v2 = . . . =
homogeneous, the ordering of the bids < matches the ≥ vi = ep , and vi+1 = (1, 0 . . . , 0) or (0, 1, 0 . . . , 0), . . . or
ordering on real numbers. If the rebate function is not (0, . . . , 0, 1), we get, ci+1 = (0, 0, . . . , 0) ∀ i ≤ p − 1. Thus,
in the form defined in the theorem, the rebate function
(cp+1 , vp+2 ) + . . . + (cn−1 , vn ) : if i ≤ p + 1
would not simultaneously satisfy the DSIC, anonymity, ri = (c , v ) + . . . + (c , v )
p+1 p+1 i−1 i−1
and deterministic properties. This is because the above
+(ci , vi+1 ) + . . . + (cn−1 , vn ) : otherwise
form of the rebate function is a necessary condition
when the objects are identical. Thus we need a rebate We now claim that the efficiency of this mechanism is
function in this form in heterogeneous settings as well. 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
We now state and prove the main result of this paper. non-zero and the rebate to each agent is zero. Then the
Theorem 3.2: If a redistribution mechanism is feasible theorem is proved. So, it remains to show the existence of
and individually rational, then there cannot exist a linear such a type profile. Consider the type profile:
rebate function which satisfies all the following properties:
• DSIC
v1 = (2p − 1, 2p − 2, . . . , p)
• deterministic
v2 = (2p − 2, 2p − 3, . . . , p − 1)
.. (6)
• anonymous .
• non-zero efficiency. vp = (p, p − 1, . . . , 1)
Proof : Assume that there exists a linear function, say f ,
and vp+1 = vp+2 . . . = vn = (0, 0, . . . , 0).
which satisfies the above properties. Let v1 < v2 < . . . <
Now, with this type profile, agent 1 pays (p − 1), agent
vn . Then according to Theorem 3.1, for each agent i,
2 pays (p − 2), . . . , agent (p − 1) pays 1 and the remaining
ri = f (v1 , v2 , . . . , vi−1 , vi+1 , . . . , vn ) agents pay 0. Thus, the Clarke payment received is non-zero
= (c0 , ep ) + (c1 , v1 ) + . . . + (cn−1 , vn ) but it can be seen that ri = 0 for all the agents.
where, ci = (ci1 , ci2 , . . . , cip ) ∈ Rp , ep = (1, 1, . . . , 1) ∈
Rp , and (·, ·) denotes the inner product of two vectors in The above theorem provides disappointing news. It rules out
Rp . Now, we will show that the worst case performance of the possibility of a linear redistribution mechanism for the
f will be zero. To this end, we will study the structure of heterogeneous settings which will have non-zero efficiency.
f , step by step. However, there are two ways to get around it.
1) The domain of types under which Theorem 3.2 holds
Observation 1: Consider type profile (v1 , v2 , . . . , vn ) where is, Θi = Rp+ , ∀ i ∈ N . One idea is to restrict the
v1 = v2 = . . . = vn = (0, 0, . . . , 0). For this type profile, domain of types. In Section 4, we design a worst
case optimal linear redistribution mechanism when the • The agents submit their bids.
valuations of agents for the heterogeneous objects have • The bids are sorted in decreasing order.
a certain type of relationship. • The highest bidder will be allotted the first object, the
2) Explore the existence of a rebate function which is second highest bidder will be allotted the second object,
not a linear and yields a non-zero performance. We and so on.
explore this in Section 5. • Agent i will pay ti −ri , where ti is the Clarke payment
and ri is the rebate.
4. A Redistribution Mechanism for Heteroge- X p
neous Objects When Valuations have Scaling ti = (αj − αj+1 )vj+1
j=i
Based Relationship
• Let agent i’s rebate be,
Consider a scenario where the objects are not identical ri = c0 + c1 v1 + . . . + ci−1 vi−1 + ci vi+1 + . . . + cn−1 vn
but the valuations for the objects are related and can be
derived by a single parameter. As a motivating example, The mechanism is required to be individually rational and
consider the website somefreeads.com and assume that feasible.
• The mechanism will be individually rational iff ri ≥
there are p slots available for advertisements and there are
n agents interested in displaying their ads. Naturally, every 0 ∀i ∈ N . That is, ∀ i ∈ N ,
agent will have a higher preference for a higher slot. Define c0 + c1 v1 + . . . + ci−1 vi−1 + ci vi+1 + . . . + cn−1 vn ≥ 0.
click through rate of a slot as the number of times the ad
• The mechanism will be feasible if the total redistributed
is clicked, when the ad is displayed in that slot, divided by
payment is less
P than or equal P to the surplus. That is,
the number of impressions. Let the click through rates for P
ri ≤ t = t i or t − i ri ≥ 0, where,
slots be α1 ≥ α2 ≥ α3 . . . ≥ αp . Assume that each agent i i
p
has the same value for each click by the user, say vi . So, X
the agent’s value for the j th slot will be αj vi . Let us use the t= j(αj − αj+1 )vj+1 .
j=1
phrase valuations with scaling based relationship to describe
such valuations. We define this more formally below. With the above setup, we now derive c0 , c1 , . . . , cn−1 that
Definition 4.1: We say the valuations of the agents have will maximize the fraction of the surplus which is redis-
scaling based relationship if there exist positive real numbers tributed among the agents.
α1 , α2 , α3 , . . . , αp > 0 such that, for each agent i ∈ N , the
valuation for object j, say θij , is of the form θij = αj vi , Step 1: First, we claim that, c0 = c1 = 0. This can be proved
where vi ∈ R+ is a private signal observed by agent i. as follows. Consider the type profile, v1 = v2 = . . . = vn =
Without loss of generality, we assume, α1 ≥ α2 ≥ α3 . . . ≥ 0. For this type profile, individual rationality
P implies ri =
αp > 0. We immediately note that the homogeneous setting c0 ≥ 0 and t = 0. So for feasibility, i ri = nc0 ≤ t = 0.
is a special case that arises when α1 = α2 = α3 = . . . = That is, c0 should be zero. Similarly, by considering type
αp > 0 profile v1 = 1, v2 = . . . = vn = 0, we get c1 = 0.
For the above setting, we design a Groves mechanism
which is almost budget balanced and optimal in the worst Step 2: Using c0 = c1 = 0,
case. Our mechanism is similar to that of Guo and Conitzer • The feasibility condition can be written as:
[8] and our proof uses the same line of arguments. n−1
(
X
The following theorem by Guo and Conitzer [8] will be (j − 1)(αj−1 − αj ) − (j − 1)cj−1
used to design our mechanism. j=2
Theorem 4.1: For given n and real numbers )
a1 , a2 , . . . , an , −(n − j)cj vj − (n − 1)cn−1 vn ≥ 0 (7)
for any x1 ≥ x2 ≥ . . . xn ≥ 0,
j
X • The individual rationality condition can be written as
a1 x1 +a2 x2 +. . . an xn ≥ 0 iff ai ≥ 0 ∀j = 1, 2 . . . , n c2 v2 + . . . + ci−1 vi−1 + ci vi+1 + . . . + cn−1 vn ≥ 0 (8)
i=1
Step 3:PWhen we say our mechanism’s efficiency is e, we
4.1. The Proposed Mechanism mean, i ri ≥ et, that is,
n−1
We will use a linear rebate function. (For simplifying X
− e(j − 1)(αj−1 − αj ) + (j − 1)cj−1
equations, we will assume that there are (n − p) virtual j=2
objects, with αp+1 = αp+2 = . . . = αn = 0). We propose
the following mechanism: +(n − j)cj vj + (n − 1)cn−1 vn ≥ 0 (9)
Step 4: Define β1 = α1 −α2 , and for i = 2, . . . , p, let βi = as BAILEY redistribution mechanism. It is crucial to note
i(αi − αi+1 ) + βi−1 . Now, inequalities (7), (8), and (9) have that the non-zero efficiency of the BAILEY mechanism does
to be satisfied for all values of v1 ≥ v2 ≥ . . . ≥ vn . not trivially follow from that of the mechanism in [1].
Invoking Theorem (4.1), we need to satisfy the following
set of inequalities: 5.1. BAILEY Mechanism
Pj
i=2 ci ≥ 0 ∀j = 2, . . . n − 1 First, consider the case when p = 1. Let the valuations of
eβ ≤ (n − 2)c2 ≤ β1
Pi−1 1 the agents for the object be, v1 ≥ v2 ≥ . . . ≥ vn . The agent
eβi−1 ≤ n j=2 cj + (n − i)ci ≤ βi−1 i = 3, . . . , p with the highest valuation will receive the object and would
Pi−1
eβp ≤ n j=2 cj + (n − i)ci ≤ βp i = p + 1, . . . , n − 1 pay the second highest bid. Cavallo [2] proposed the rebate
Pn−1
eβp ≤ n j=2 cj ≤ βp function as,
(10) r1 = r2 = n1 v3
(12)
Now, the social planner wishes to design a mechanism that ri = n1 v2 i > 2
maximizes e subjectPjto the above constraints. Motivated by this scheme, we propose a scheme for the
Define xj = i=2 ci for j = 2, . . . , n − 1. This is heterogeneous setting. Suppose agent i is excluded from the
equivalent to solving the following linear program. system. Then let t−i be the Clarke surplus in the system
(defined in Table 2). Define,
maximize e 1
s.t. ri B = t−i ∀ i ∈ N (13)
n
eβ1 ≤ (n − 2)x2 ≤ β1 B
• As the Clarke surplus is always positive, ri ≥ 0 for
eβi−1 ≤ ixi−1 + (n − i)xi ≤ βi−1 i = 3, . . . , p
all i. Thus, this scheme satisfies individual rationality.
eβp ≤ ixi−1 + (n − i)xi ≤ βp i = p + 1, . . . , n − 1 −i
P B
eβp ≤ nxn−1 ≤ βp
• t
P 1≤ −i t ∀ i (revenue monotonicity). So,
1
i ri =
t ≤ n t = t. Thus, this scheme is feasible.
xi ≥ 0 ∀i = 2, . . . , n − 1 i n n
(11) We now show that the BAILEY scheme has non-zero
So, given n and p, the social planner will have to solve efficiency if n ≥ 2p + 1. First we state two lemmas. The
the above optimization problem and determine the optimal proof will be given in Appendix B. These lemma’s are
values of e, c2 , c3 , . . . , cn−1 . It would be of interest to derive useful in designing redistribution mechanisms for the hetero-
a closed form solution for the above problem. geneous settings as well as in analysis of the mechanisms.
The discussion above can be summarized as the following Lemma 2 is used to show non-zero efficiency of the BAILEY
theorem. mechanism. Lemma 1 is used to find an allocatively efficient
Theorem 4.2: When the valuations of the agents have outcome for the settings under consideration. Also, this
scaling based relationship, for any p and n > p + 1, the lemma 1 is useful in determining the Clarke payments.
linear redistribution mechanism obtained by solving LP (11) Lemma 1: If we sort the bids of all the agents for each
is worst case optimal among all Groves redistribution mech- object, then
anisms that are feasible, individually rational, deterministic, 1) An optimal allocation, that is an allocatively efficient
and anonymous. allocation, will consist of the agents having bids
Proof: This can be proved following the line of arguments among the p highest bids for each object.
of Guo and Conitzer [8]. 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
5. Non-linear Redistribution Mechanisms for allocation (on the remaining n − 1 agents) which
the Heterogeneous Setting allocates objects to the remaining (p − 1) agents. The
∗
objects that these p-1 agents receive in k−i , may not
We should note that the homogeneous objects case is a however be the same as the objects they are allocated
special case of the heterogeneous objects case in which each in k ∗ .
bidder submits the same bid for all objects. Thus, we cannot Lemma 2: There are at most 2p agents involved in decid-
expect any redistribution mechanism to perform better than ing the Clarke payment.
the homogeneous objects case. For n ≤ p+1, the worst case Note: When the objects are identical, the bids of (p + 1)
redistribution is zero for the homogeneous case and so will agents are involved in determining the Clarke payment.
be for the heterogeneous case. So, we assume n > p+1. We Now, we show non-zero efficiency of the BAILEY redis-
construct a redistribution scheme by applying the mechanism tribution scheme.
proposed by Bailey [1] to the heterogeneous settings. We Proposition 1: The BAILEY redistribution scheme has
refer to this proposed mechanism on heterogeneous objects non-zero efficiency, if n ≥ 2p + 1.
Proof: In Lemma 2, we have shown that there will be at [8] M. Guo and V. Conitzer, “Worst-case optimal redistribution
most 2p agents involved in determining the Clarke surplus. of VCG payments,” in EC ’07: Proceedings of the 8th ACM
Thus, given a type profile, there will be (n − 2p) agents, for conference on Electronic Commerce. New York, NY, USA:
ACM, 2007, pp. 30–39.
whom, t−i = t and this implies that at least n−2pn t will be
redistributed. [9] ——, “Better redistribution with inefficient allocation in
multi-unit auctions with unit demand,” in EC ’08: Proceed-
ings of the 9th ACM conference on Electronic commerce.
Note: The proof of Proposition 1 indicates that the effi- New York, NY, USA: ACM, 2008, pp. 210–219.
ciency of this mechanism is at least n−2p
n .
[10] ——, “Optimal-in-expectation redistribution mechanisms,” in
6. Conclusion AAMAS ’08: Proceedings of the 7th international joint confer-
ence on Autonomous agents and multiagent systems. Rich-
We addressed the problem of assigning p heterogeneous land, SC: International Foundation for Autonomous Agents
objects among n > p competing agents. When the valuations and Multiagent Systems, 2008, pp. 1047–1054.
of the agents are independent of each other and their
valuations for each object are independent of valuations [11] J. Laffont and E. Maskin, “A differential approach to expected
utility maximizing mechanisms,” in Aggregation and Revela-
on the other objects, we proved the impossibility of the
tion of Preferences, J. J. Laffont, Ed., 1979.
existence of a linear redistribution mechanism with non-
zero efficiency. Then we explored two approaches to get [12] H. Moulin, “Almost budget-balanced VCG mechanisms to
around this impossibility. In the first approach, we showed assign multiple objects,” Journal of Economic Theory, 2008,
that linear rebate functions with non-zero efficiency are in Press.
possible when the valuations for the objects have scaling [13] W. Vickrey, “Counterspeculation, auctions, and competitive
based relationship. In the second approach, we showed that sealed tenders,” Journal of Finance, vol. 16, no. 1, pp. 8–37,
rebate functions with non-zero efficiency are possible if March 1961.
linearity is relaxed.
It would be interesting to see if we can characterize Appendix A.
the situations under which linear redistribution mechanisms Ordering of the Agents Based on Bid Profiles
with non-zero efficiency are possible for heterogeneous
settings. Another interesting problem to explore is to design We will define a ranking among the agents. This ranking
redistribution mechanisms that are worst case optimal for is used crucially in proving Theorem 3.1 on rebate function.
heterogeneous settings. This theorem is similar to Cavallo’s theorem on characteriza-
References tion of DSIC, deterministic, anonymous rebate functions for
homogeneous objects. We would not be actually computing
[1] M. J. Bailey, “The demand revealing process: To distribute the order among the bidders. We will use this order for
the surplus,” Public Choice, vol. 91, no. 2, pp. 107–26, April
1997. proving impossibility of the linear rebate function with the
desired properties.
[2] R. Cavallo, “Optimal decision-making with minimal waste:
strategyproof redistribution of VCG payments,” in AAMAS
’06: Proceedings of the Fifth International Joint Conference
A.1. Properties of the Ranking System
on Autonomous Agents and Multiagent Systems. New York,
NY, USA: ACM, 2006, pp. 882–889. When we are defining ranking/ordering among the agents,
we expect the following properties to hold true:
[3] E. Clarke, “Multi-part pricing of public goods,” Public
• Any permutation of the objects and the corresponding
Choice, vol. 11, pp. 17–23, 1971.
permutation on bid vector, (bi1 , bi2 , . . . , bip ) for each
[4] B. Faltings, “A budget-balanced, incentive-compatible scheme agent i, should not change the ranking. That is, the
for social choice,” in Agent-Mediated Electronic Commerce, ranking should be independent of the order in which
AMEC. Springer, 2005, pp. 30–43.
the agents are expected to bid for this objects.
[5] J. R. Green and J. J. Laffont, Incentives in Public Decision • Two bidders with the same bid vectors should have the
Making. Amsterdam: North-Holland Publishing Company, same rank.
1979. • By increasing the bid on any of the objects, the rank
[6] T. Groves, “Incentives in teams,” Econometrica, vol. 41, pp. of an agent should not decrease.
617–631, 1973.
A.2. Ranking among the Agents
[7] S. Gujar and Y. Narahari, “Redistribution of VCG payments
in assignment of heterogeneous objects,” in Proceedings of
4th International Workshop on Internet and Network Eco- This is a very crucial step. First, find out all feasible
nomics, WINE 2008. Springer, 2008, pp. 438–445. allocations of the p objects among the n agents, each
agent receiving at most one object. Sort these allocations, 3) If two bids are the same, then they are equivalent in
according to the valuation of an allocation. Call this list L. this order.
To find the ranking between i and j, we use the following 4) By increasing a bid, no agent will decrease his rank.
algorithm. If agent i < agent j, we will also say vi < vj .
1) Lij = L
2) Delete all the allocations from Lij which contain both Appendix B.
i and j. B.1. Proof of Lemma 1
3) Find out the first allocation in Lij which contains one
of the agents i or j. Say k 0 . Proof:
a) Suppose this allocation contains i and has value • Suppose an optimal allocation contains an agent whose
strictly greater than any of the remaining alloca- bid for his winning object, say j, is not in the top p bids
tions from Lij containing j, then we say, i j. for the j th object. There are other (p − 1) winners in
b) Suppose this allocation contains j and has value an optimal allocation. So, there exists at least one agent
strictly greater than any of the remaining alloca- whose bid is in the top p bids for the j th object and does
tions from Lij containing i, then we say, j i. not win any object. Thus, allocating him the j th object,
4) If the above step is not able to decide the ordering we have an allocation which has higher valuation than
between i and j, let A = {k ∈ K|v(k) = v(k 0 )}. the declared optimal allocation.
Update Lij = Lij \A and recur to step (2) till EITHER • Suppose an agent i who receives an object in an optimal
• there is no allocation containing the agent i or j allocation is removed from the system. The agent will
OR have at most one bid in the top p bids for each object.
• the ordering between i and j is decided. So, agents now having bids in the top p bids, will be at
5) If the above steps do not give either of i j or j i, the pth position. It can be seen that there will be at most
we say, i ≡ j or i < j as well as j < i one agent in an optimal allocation who is on the pth
Before we state some properties of this ranking system <, position for the object he wins. If there is more than one
we will explain it with an example. Let there be two items agent in an optimal allocation on the pth position for the
A and B, and four bidders. That is, p = 2, n = 4 and let object they win, then we can improve on this allocation.
their bids be: b1 = (4, 5), b2 = (2, 1), b3 = (1, 4), and b4 = Hence, after removing i, there will be at most one more
(1, 0). agent who will be a part of a new optimal allocation.
Now, allocation (A = 1, B = 3) has the highest valuation
among all the allocations. So,
B.2. Proof of Lemma 2
agent 1 agent 2
agent 1 agent 4 Proof: The argument is as follows:
(14)
agent 3 agent 2 1) Sort the bids of the agents for each object.
agent 3 agent 4 2) The optimal allocation consists of agents having bids
Now, in L13 defined in the procedure above, the allocation in the p highest bids for each of the objects (Lemma
(A = 2, B = 1) has strictly higher value than any other 1).
allocation in which the agent 3 is present. So, 3) For computing the Clarke payment of the agent i, we
remove the agent and determine an optimal allocation.
agent 1 agent 3.
And, using his bid, the valuation of optimal allocation
Thus, with him and without him will determine his payment.
agent 1 agent 3 agent 2 and This is done for each agent i. As per Lemma 1, if any
agent from an optimal allocation is removed from the
agent 1 agent 3 agent 4 system, there exists a new optimal allocation which
In L24 , the allocation (A = 2, B = 1) has strictly higher consists of at least (p − 1) agents who received the
value than any other allocation in which the agent 4 is objects in the original optimal allocation.
present. Thus, the ranking of the agents is, 4) There will be p agents receiving the objects and
determining their payments will involve removing one
agent 1 agent 3 agent 2 agent 4 of them at a time, there will be at most p more agents
We can show that the ranking defined above, satisfies the who will influence the payment. Thus, there are at
following properties. most 2p agents involved in determining the Clarke
payment.
1) < defines a total order on set of bids.
2) < is independent of the order of the objects.