Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: zz-x2580
STAT 155 Midterm Solutions
Name:
ID:
Instructions: This test will be available on Tuesday 07/22/2020 at 4pm on
b-courses/pages/midterm. The solutions must be submitted to Gradescope by
10pm on Wednesday 07/22/2020. Late submissions will not be accepted. All
work must be shown in order to receive full credit. Attempt as much as you
can; partial credit will be awarded for incomplete solutions with intermediate
steps written out or explained clearly. This exam is open book, open notes but
no other resources. Feel free to email us during the midterm if you have any
concerns.
Problem # Points Your score
1 2
2 20
3 15
4 8
5 20
Total 65
c© Copyright 2020 by Adam Lucas
1
1. Statistics and the entire academic enterprise are based on one quality –
integrity. We are all part of a community that doesn’t fabricate evidence,
doesn’t fudge data, doesn’t present other people’s work as our own, doesn’t
lie and cheat. You trust that we will treat you fairly and with respect.
We trust that you will treat us and your fellow students fairly and with
respect. Please transcribe the UC Berkeley’s Honor Code below
and sign your name next to it:1
“I certify that all solutions will be entirely my own and that I will not
consult or share information with other people during the exam. I promise
I will act with honesty, integrity, and respect for others.”
1If you decide to type your solutions (e.g. using LATEX), you can type the answer to this
question too.
2
2. Suppose there are k identical items for sale and n bidders. A bidder i
can only receive items from some publicly known set Si (for example, you
may imagine that initially items are stored in many different storehouses
scattered across the country, and each bidder can only order items from
storehouses that are less than 100 miles away from her location). The
utility of bidder i is vixi−pi, where xi is the number of items that he got,
vi is his private valuation, and pi is his payment.
(a) Suppose each bidder can get several items from her set. Find the
welfare-maximizing DSIC auction.
Solution. To maximize welfare each item i should be allocated to the
highest bidder among the set {j : i ∈ Sj} i.e. among the bidders who
are able to order this item. (Another way to describe this allocation
rule is the following: first give the all the items that the highest
bidder can get to the highest bidder, then give all remaining items
that the second highest bidder can get to the second highest bidder
and so on). The corresponding DSIC auction is the following: each
item i is sold to the highest bidder from the set {j : i ∈ Sj} at the
price equal to the second highest bid from that set. In other words,
each item is sold separately in the second-price auction among the
bidders who can get it. It is dominant to bid truthfully in each
of those single-item auctions, so it is dominant to bid truthfully in
our auction. Moreover, each of those auctions yields non-negative
utility for bidding truthfully, and thus so does our overall auction.
Therefore, our proposed auction is DSIC.
For the following parts suppose that each bidder only can
buy one item, and consider the following auction:
Bidders are served one by one, in the order of their bids
starting from the highest;
At the turn of bidder i he gets the first unsold item from Si.
If there are no such items, bidder i doesn’t get anything,
and all the bidders who got items but haven’t paid yet
pay the bid of bidder i.
For example: Suppose there are four bidders and three items,
S1 = S2 = {1, 2}, S3 = {1}, S4 = {3}, b1 = 4, b2 = 3,
b3 = 2 and b1 = 1. The first bidder will get item 1
since this is the first unsold item in S1, the second will
then get item 2, the third will get nothing, and the last
bidder will get item 3. Bidders 1 and 2 will pay 2, and
bidders 3 and 4 will not pay anything.
(b) Is the allocation rule of this auction monotone?
3
Solution. Yes, if all items from your set were already sold before
your turn, then decreasing your bid cannot help as it will only post-
pone your turn and all the items will still be sold.
(c) Is this allocation welfare-maximizing?
Solution. No it’s not. Suppose there are two bidders and two items,
S1 = {1, 2}, S2 = {1}, b1 = 2 and b2 = 1. In the auction above the
first bidder will get item 1, and the second will get nothing. However,
the welfare-maximizing allocation is ”second bidder gets item 1, first
bidder gets item 2”.
(d) Is this auction DSIC?
Solution. No. Consider the case when there are 3 bidders and two
items, S1 = {1}, S2 = S3 = {2}, b1 = 3, b2 = 2 and b3 = 1 , the
highest bidder will get item 1, and will pay the third highest price 1.
But she can avoid paying anything by decreasing her bid to b1 = 0.5
to be the lowest. If she does that, she will still get her item (as no
one else can buy it), but for free.
4
3. There is one unit of infinitely divisible good for sale, and there are two
bidders who are willing to buy some shares of it. The utility of bidder i
when he gains yi of the good is vi log(1 + yi)− pi where pi is the payment
and vi is the private valuation of bidder i.
(a) Represent this in the form of single-parameter environment. Note
that in a single parameter environment, there is a feasible set X of
vectors (x1, ..., xn), each bidder has private valuations vi, and utility
is linear in both xi and vi.
Solution. Let’s do the change of variables: xi = log(1 + yi). Then
the utility of i-th bidder after getting the good is vixi, and the feasible
set is X = {x : ex1 + ex2 ≤ 3, x1 ≥ 0, x2 ≥ 0}.
(b) What is the welfare-maximizing allocation rule? Is it monotone?
Solution. We need to maximize the following quantity:
b1 log(1 + y1) + b2 log(2− y1)
in y1 ∈ [0, 1]. Take the derivative:
b1
1 + y1
− b2
2− y1 .
the derivative is decreasing in y1, and is zero at y1 =
2b1−b2
b1+b2
. Thus,
the allocation that maximizes utility is
y1(b1, b2) =
0, if b1 ≤ b2/2
2b1−b2
b1+b2
, if b2/2 < b1 < 2b2
1, if b1 ≥ 2b2.
In terms of x:
x1(b1, b2) =
0, if b1 ≤ b2/2
log 3b1b1+b2 , if b2/2 < b1 < 2b2
log 2, if b1 ≥ 2b2.
The allocation for the second player can be obtained by swapping
the indices. It’s monotone as it is a welfare-maximizing allocation in
a single-parameter environment.
(c) Which payment mechanism extends the rule from the previous part
to a DSIC auction?
5
Solution. The interesting part is b2/2 < b1 < 2b2. We need to
compute ∫ b1
0
tx′(t, b2) dt =
∫ b1
b2/2
t
t+ b2
3t
2b2
(t+ b2)2
dt
=
∫ b1
b2/2
b2
t+ b2
dt
=b2 log
b1 + b2
1.5b2
.
So the payment function is
p1(b1, b2) =
0, if b1 ≤ b2/2
b2 log
b1+b2
1.5b2
, if b2/2 < b1 < 2b2
2b2 log 2, if b1 ≥ 2b2.
The payment for the other player can be obtained by swapping the
indices.
6
4. Find the optimal single-item DSIC auction in with n bidders whose pri-
vate valuations are independent and distributed on [0, 1] with distribution
function F (x) = 1− exp
(
− x1−x
)
.
Solution. The virtual evaluation function for this distribution is
φ(x) = x−1− F (x)
F ′(x)
= x−
exp
(
− x1−x
)
(
1 + 1x−1
)′
exp
(
− x1−x
) = x−(x−1)2 = 3x−x2−1.
It’s strictly increasing on [0, 1], and it’s root is 3−
√
5
2 . Thus, the optimal
DSIC auction is the second price auction with reserve price 3−
√
5
2 .
7
5. Consider the following auction: There are k identical items represented as
vertices of a graph. We say two vertices are adjacent if they are connected
by an edge. Items corresponding to adjacent vertices are incompatible.
Each of n bidders can get several items however no bidder can get incom-
patible items. For example an auction on the graph below has 4 items and
3 out of n bidders win these items. We color items the same color if they
are bought by the same bidder (three different colors means 3 different
bidders buy the four items). In this example the red items are bought by
the same bidder (notice that they are compatible items since the vertices
aren’t adjacent). The degree of a vertex is the number of edges connect-
ing to the vertex. In the example below, the degree of the green vertex is
3.
The utility of bidder i is vixi − pi, where xi is the number of items that
she got, vi is her private valuation and pi is the payment that she made.
The welfare maximization problem for this auction can be shown to be
NP-hard. As usual we will consider a greedy allocation algorithm which
is computed in polynomial time.
(a) Consider the following greedy allocation algorithm:
for item i = 1 . . . k:
Allocate item i to the highest bidder who doesn’t
yet possess any item incompatible with item i.
For example: suppose there are 2 bidders and 3 items, the
second item is incompatible with the first. If b1 > b2,
then the first item is given to bidder 1, the second item
is given to bidder 2 (as bidder 1 already has an item
which is incompatible with item 2), and the third item
is given to bidder 1.
Show that this allocation rule is not monotone for some graphs and
some orderings of vertices.
Solution. Suppose there are 2 bidders and 3 items, the first item is
incompatible with other two. Suppose b1 > b2, then the algorithm
will assign the first item to the first bidder and other two to the second
bidder. Thus, the first bidder can obtain more items by bidding less,
and taking place of the second bidder.
8
(b) We show next that the rule above achieves at least 1/(d + 1) of the
maximum welfare, where d is the maximum vertex degree in the
graph of items. Assume truthful bidding (i.e. bi = vi).
i. Fix a welfare-maximizing allocation. Consider an item i. Denote
the bidder to whom item i is assigned by the welfare-maximizing
allocation asmi. Denote the bidder to whom item i is assigned by
the greedy algorithm as gi. Argue that if our algorithm assigned
item i to a lower bidder (i.e. bmi ≥ bgi), it means that there is
an item i′ < i, incompatible with i, which was given to bidder
mi.
ii. Denote the smallest such i′ above, by f(i). If our algorithm
assigned item i to a bidder, who is at least as good as mi, denote
f(i) = i. Doing this for every item i defines a function f from
the set of items {1, 2, . . . , k} to itself. Below is an example for
k = 3.
Argue that any item has at most d+ 1 pre-images (i.e. the size
of f−1(i) is at most d+1). In the picture above, f−1(1) = {1, 2}
has size 2.
iii. The maximal possible welfare is
∑
i bmi . We can write∑
i
bmi ≤
∑
i
bgf(i)
≤(d+ 1)
∑
i
bgi .
Explain this set of inequalities and how it completes the proof.
Solution. i. mi should get an item incompatible with i because
otherwise the greedy algorithm would assign item i to mi or a
higher bidder, as it allocates each item to the highest bidder who
doesn’t possess an incompatible item.
ii. pre-images of i are either i itself or incompatible items; since
there are at most d incompatible items, the size of pre-image is
at most d+ 1.
iii. If bmi ≤ bgi , then f(i) = i and bmi ≤ bgf(i) . If bmi > bgi then
item f(i) was given to mi by greedy algorithm, so bmi = bgf(i) . In
both cases bmi ≤ bgf(i) which justifies the first inequality. Since
