IEOR E4407: Game-Theoretic Models of Operations
Jay Sethuraman
Midterm
ˆ The exam is 3 hours long; you have 36 hours to turn in your work though. It has 6 questions
in all and is worth 60 points.
ˆ Please write and sign the following honor pledge in your exam: “I have neither given nor
received improper help on this examination”.
ˆ The exam is open book and notes. You can use your computer or calculator to do some
basic calculations. You are not allowed to talk to each other, look things up on the internet,
etc.
ˆ If something is not clear, please make a resonable assumption, state this in your exam, and
continue. If you are convinced that I have made a mistake, please send me email. I’ll check
it a few times tomorrow.
1. (15 points)
(a) Consider a monopolist with a single unit of a divisible good. He can sell any fraction
of it and faces two markets M1 and M2. He can set different prices p1 and p2 in each
of these markets. The demand in M1 at a price p1 is q1 := max{1 − p1, 0}; whereas
the demand in M2 is q2 := max{2 − p2, 0}. Keep in mind that these two markets are
linked, because the total supply of the good available to the monopolist is 1: thus, a
pair of prices (p1, p2) is feasible if the corresponding q1 + q2 ≤ 1. Find a feasible pair
of prices p∗1 and p∗2 for the monopolist that maximizes total profit.
(b) Consider an auctioneer with a single (indivisible) good facing two risk-neutral buyers
with independent valuations uniformly distributed in [0, 1] and [1, 2] respectively. Sup-
pose the auctioneer uses a second-price auction with a reserve price r. What value of
r maximizes expected revenue to the seller. Justify. What is the expected revenue to
the auctioneer?
(c) Consider an auctioneer with a single (indivisible) good facing two risk-neutral buyers
with independent valuations uniformly distributed in [0, 4/5] and [0, 6/5]. Suppose
the auctioneer uses a second-price auction with a reserve price r. What value of r
maximizes expected revenue to the seller. Justify. What is the expected revenue to
the auctioneer?
1
2. (10 points) Consider a first price auction with two bidders, where the highest bidder wins
the auction and pays his own bid. Suppose that it is common knowledge that valuations are
distributed in the interval [0, 1] with cumulative distribution function F (v) = vm. (Think
of m as a fixed positive integer.) Suppose further that the valuations are independently
drawn.
(a) Suppose that bidder i assumes that bidder j bids according to the function bj = kvj +`
for some constants k and `. Write down the expected payoff to bidder i as a function
of his bid and his valuation.
(b) Maximize this payoff in order to derive bidder i’s optimal bid as a function of his
valuation. Use this to find a symmetric Bayes-Nash equilibrium of this game.
3. (9 points) Consider a seller with a single object, and two potential buyers with independent
private valuations. The seller’s value for the object is zero. The values of the buyers are in
the interval [0, 1]. The change from the standard set-up is that the buyer values are drawn
independently from different distributions. Specifically, Buyer 1’s value for the object is
drawn from the distribution F1(x) = x
4, and Buyer 2’s value for the object is distributed
according to F2(x) = x
2. All of this is common knowledge.
(a) (2 points) Find the allocation and payments made by the buyers in the VCG mech-
anism. You should describe this in terms of the realized valuations (v1, v2) for the
buyers.
(b) (2 points) Under the VCG mechanism, find the expected payment of buyer 1 when his
value is x (the expectation is with respect to the value of the other buyer). Similarly,
find the expected payment of buyer 2 when his value is x.
(c) (2 points) Suppose (v1, v2) = (0.6, 0.3). Describe the allocation and payments made by
the buyers under the AGV mechanism for these realized valuations.
(d) (3 points) Describe the optimal mechanism for this problem. You should indicate the
allocation rule and the payment rule, as a function of the valuations. (Note: there will
be some situations in which you do not sell the object.)
2
4. (6 points) Consider the cooperative game with three players {A,B,C} and characteristic
function given by v(∅) = 0; and
v({A}) = v({B}) = v({C}) = 1,
and
v({A,B}) = 2; v({A,C}) = 3; v({B,C}) = 4; v(({A,B,C}) = 6.
Assume that the v(X) describes the profits that the set of agents X can earn if they cooperate
with each other.
(a) Write down the inequalities that characterize the core of the cooperative game.
(b) Find the Shapley value payoff of each player in this cooperative game. Is the Shapley
value of this game also a member of the core?
5. (10 points) Alice and Bob play the following game k times. Alice can cheat (C) or not (H)
in any round; Bob can monitor (M) or trust (T) in any round. They make their choices
simultaneously. If Alice cheats without being monitored, the game stops and Bob pays her
$1 in that period and in every remaining period. (Thus, if k = 10, and she cheats without
being monitored in round 3, she gets $1 in rounds 3 through 10 from Bob.) If Alice cheats,
but is monitored, the game stops and she pays Bob $a in that period and in every remaining
period. If Alice is honest, she receives $b from Bob if she is monitored, and nothing if she is
not; in either case the game continues. The payoffs to Alice and Bob are additive (there is
no discounting). (Note that this is a zero-sum game: Alice’s payoff is exactly the negative
of Bob’s payoff in each case.) Find equilibrium strategies for Alice and Bob in this zero-sum
game. What is Alice’s expected equilibrium payoff as a function of k? (Hint: You may want
to examine the cases k = 1 and k = 2; and then use induction. If you find the general k
case difficult to solve, please include an explicit solution for k = 5.)
6. (10 points) Consider a single-item auction in there are three risk-neutral bidders. Bidder
i observes a private signal Xi drawn from the uniform [0, 1] distribution. The signals are
independent and identically distributed. Suppose the environment is common-value, and
that the value of the item to (any) bidder is max{X1, X2, X3}. Find equilibrium bidding
strategies and the corresponding expected revenue to the seller in a (a) second-price sealed
bid auction; (b) first-price sealed bid auction.
3