COMP559 Tutorial Sheet 2
1. Consider a single item auction setting with more than three players, i.e. n ≥ 3. Are the
following auctions truthful? Explain why.
(a) Give the item to the highest bidder. Charge him an amount equal to the third high-
est bid.
SOLUTION No, it’s not truthful. It is sufficient to construct a particular instance
for which the mechanism is not truthful. Suppose that v1 > v2 > v3 > . . . > vn.
If the bidders bid truthfully, the first bidder gets the item, therefore the utility of
player 2 is 0. Notice that if the second bidder bids b2 = v1 + , for some > 0, he
gets the item and pays payment equal to v3. Therefore her utility becomes v2 − v3,
that is positive.
(b) Give the item to the second highest bidder. Charge him an amount equal to the
third highest bid.
SOLUTION No, it’s not truthful. It is sufficient to construct a particular instance
for which the mechanism is not truthful. Suppose that v1 > v2 > v3, . . . , vn. If the
bidders bid truthfully, the second bidder gets the item, therefore the utility of player
1 is 0. Notice that if the first bidder bids b1, with v2 < b1 < v3, he gets the item and
pays payment equal to v3. Therefore her utility becomes v1 − v3, that is positive.
2. ”Run” VCG mechanism for the path-auction problem of Section 9.3.5.6 of the book. Give
the allocation, and the payments for the instance of Figure 1. (We want to send a single
message from node A to node B).
Figure 1:
SOLUTION This is a trivial application of VCG. The VCG mechanism outputs the
shortest path ADB. The edges that do not belong to the path receive a payment of 0.
The edge AD receives a payment of 7− 4 = 3, while the edge DB receives a payment
of 6− 1 = 5.
3. Consider an auction with two items a,b and three players. The valuations for getting a
single item is as follows v1(a) = 3, v1(b) = 8, v2(a) = 10, v2(b) = 5, v3(a) = 5, v3(b) = 6.
Assume that the valuation for getting both items for each player i are given by
1
(a) vi({a, b}) = vi(a) + vi(b).
(b) (Optional) vi({a, b}) = vi(a) · vi(b).
(c) (Optional)vi({a, b}) = max{vi(a), vi(b)}.
For all the above cases
• Describe the set of possible outcomes A.
• Describe the valuations of each player over A.
• ”Run” the VCG mechanism (compute allocation and payments).
SOLUTION: First we describe the set of the alternatives. We represent each alternative
a ∈ A, by a 0/1 matrix x, with xij = 1, if the item j is assigned to player i according to
a, and xij = 0 otherwise.
a1 =
 1 10 0
0 0
 , a2 =
 1 00 1
0 0
 , a3 =
 1 00 0
0 1
 , a4 =
 0 11 0
0 0
 , a5 =
 0 10 0
1 0
 ,
a6 =
 0 01 1
0 0
 , a7 =
 0 01 0
0 1
 , a8 =
 0 00 1
1 0
 , a9 =
 0 00 0
1 1

(a) The valuation of player 1 is
v1(a1) = 11,
v1(a2) = v1(a3) = 3,
v1(a4) = v1(a5) = 8,
v1(a6) = · · · = v1(a9) = 0,
Similarly you can calculate the valuations for players 2 and 3.
The VCG mechanism finds the outcome a ∈ A that maximises ∑2i=1 vi(a). This
outcome is a4. The VCG payment for the first player is maxb∈A(v2(b) + v3(b)) −
(v2(a4) + v3(a4)) = 16 − 10 = 6. The VCG payment for the second player is
maxb∈A(v1(b) + v3(b)) − (v1(a4) + v3(a4)) = 13 − 8 = 5. The VCG payment for
the third player is maxb∈A(v2(b) + v3(b))− (v2(a4) + v3(a4)) = 18− 18 = 0.
(b) Similar to (a)
(c) Similar to (a)
4. In the Public Project example, show that
∑
i pi < C, when vi ≥ 0 for all i ∈ N .
SOLUTION:
Suppose that
∑
j vj > C, otherwise
∑
i pi = 0. In that case, a player i is pivotal if
without her the project would not succeed, i.e.,
∑
j 6=i vj ≤ C. Let’s denote by X the set
of the pivotal players. As pointed out in the textbook, only the pivotal players pay, and
a pivotal player i pays an amount equal to pi = C −
∑
j 6=i vj . The rest of the players pay
0. Therefore the total amount of money that are collected are
∑
i∈X
pi =
∑
i∈X
C −∑
j 6=i
vj
 = |X| · C −∑
i∈X
∑
j 6=i
vj .
2
In the sum that appears in the above expression, the value vj is counted |X| times for
each player that does not belong to X, and |X| − 1 times for each player that belongs to
X. Therefore
∑
i∈X
pi = |X| · C −
∑
j∈X
(|X| − 1) · vj +
∑
j /∈X
|X| · vj

= |X| · C −
∑
j
(|X| − 1) · vj +
∑
j /∈X
vj

< C −
∑
j /∈X
vj
≤ C,
where for the first inequality is due to the fact that (|X| − 1)∑j vj > (|X| − 1)C.
5. (Optional - see AGT book) Consider a standard social choice setup with n players, a
finite set of alternatives A, and valuation sets Vi ⊆ R|A|.
(a) Write down the definition of an incentive compatible mechanism M = (f, p).
(b) Show that for an incentive compatible mechanism the payments depend only on
the allocation f(v1, . . . , vn) = a, and on the bids of the other players v−i, that is
pi(v1, . . . , vn) = pi(a, v−i).
(c) Given an incentive compatible mechanism M = (f, p), and the bids of the other
players v−i, define the range of player i.
(d) Show that an incentive compatible mechanism M = (f, p), must select the alternative
a that maximizes vi(a)− pi(a, v−i), for every player i, within player i’s range.
SOLUTION: These are definitions and propositions you can find in the AGT textbook
Chapter 9.
6. Consider a single item auction setting with more than three players, i.e. n ≥ 3. Can we
truthfully implement the following social choice rule?
”Assign the item to the bidder with the second highest bid”.(Hint: use WMON
to prove it).
Note: In (1b), we saw that using payments that charge an amount equal to the third
highest bid, doesn’t work. Now we need to prove something more general. Either to show
that there do not exist payments that make the above social choice rule truthful, or to
find some payment rule that implement the above social choice rule truthfully.
SOLUTION:
No we cannot. We shall prove it by using Weak Monotonicity (WMON). The alloca-
tion function of the described mechanism works as follows: for a strategy profile v, the
allocation of bidder i is
xi(v) =
{
1 if vi is the second highest bid/values
0 otherwise.
We know that every truthful mechanism must satisfy WMON. Therefore the aforemen-
tioned mechanism must satisfy WMON. Fix some v−i. Let vi be such that vi has the
3
second highest value/bid in (vi, v−i), or in other words maxk 6=i vk > vi. Also let v′i be such
that v′i > maxk 6=i vk. Clearly, v
′
i > vi.
The mechanism is such that xi = xi(vi, v−i) = 1, and x′i = xi(v
′
i, v−i) = 0. Therefore,
vi(xi)− vi(x′i) = vi − 0 < v′i − 0 = v′i(xi)− v′i(x′i) and this contradicts WMON.
4

欢迎咨询51作业君