[SOLVED] Cs 5854: networks, crowds, and markets homework 3

Part 1: Matching Markets and Exchange Networks
1. Consider two sellers, a and b, each offering a distinct house for sale, and a set of two buyers,
x and y. x has a value of 2 for a’s house and 4 for b’s house, while y has a value of 3 for a’s
house and 6 for b’s house, summarized in the following table.
Buyer a’s house b’s house
value for x 2 4
value for y 3 6
(a) Suppose that a charges a price of 0 for her house, and b charges a price of 1. Is this set
of prices market-clearing? As part of your answer, say what the preferred choice graph
is with this given set of prices, and use this to justify your answer.
(b) If the above prices are not market-clearing, compute a set of market-clearing prices p
with an associated matching M. Explain how you found them and why they are marketclearing (you don’t necessarily need to use Theorem 8.8 in the notes for this, but it could
be helpful).
(c) For the market equilibrium computed above (corresponding to a set of market-clearing
prices), compute the social value of the buyers and the social welfare of the buyers and
sellers. Briefly explain why these are the maximum possible in this matching market
context.
2. Suppose now we have a set of three sellers a, b, and c, and a three buyers labeled, x, y, and
z. The valuations of the buyers are summarized in the following table.
Buyer a’s house b’s house c’s house
value for x 5 7 1
value for y 2 3 1
value for z 5 4 4
(a) Using the algorithm from Theorem 8.8 in the notes, compute a market equilibrium
(consisting of a matching and set of prices). Show your work.
(b) Recall that in chapter 9, we showed that every matching market context can be encoded
as an exchange network, and furthermore, exchange networks are “asymmetric” in the
sense that the buyers and sellers have the same role. As a result, we can flip the script
such that the sellers are now the “buyers” and the buyers are now the “sellers.” The
corresponding matching market context now has the following set of values.
Seller if x buys if y buys if z buys
value possible for a 5 2 5
value possible for b 7 3 4
value possible for c 1 1 4
You can think of the value of a seller being the maximum value it can charge for a home.
Now the prices for the buyer correspond to discounts on the house (increasing value for
the buyers).
2
Using the algorithm from Theorem 8.8 in the notes, compute a market equilibrium
(consisting of a matching and set of “prices”) for this new matching market context.
Show your work.
(c) Interpret the matching and “prices” computed in part (b) as a matching and actual prices
charged when selling the houses. How do these values compare to those computed in
part (a)? Give a 1-3 sentence intuitive explanation of why the values might be different.
In particular, explain what the consequence is that the algorithm of Theorem 8.8 always
has a “free” item in the resulting market equilibrium.
3. (a) We observed (Claim 9.5) that an exchange network consisting of a cyclic graph of 3
nodes has no stable outcome. Does this generalize to every cyclic graph? If not, can we
characterize for which values of n the n-node cyclic graph has a stable outcome? Justify
your answers.
(b) Show by constructing an example that an exchange network that contains a 3-node cycle
(but doesn’t necessarily entirely consist of one) can still have a stable outcome.
Part 2: Auctions and Mechanism Design
4. Consider an auction where a seller wants to sell one unit of a good to a group of bidders.
The seller runs a sealed-bid, second-price auction. Your firm will bid in the auction, but it
does not know for sure how many other bidders will participate in the auction. There will
be either two or three other bidders in addition to your firm. All bidders have independent,
private values for the good. Your firm’s value for the good is c. What bid should your firm
submit, and how does it depend on the number of other bidders who show up? Give a brief
(1-3 sentence) explanation for your answer.
5. Consider a second-price, sealed-bid auction with two bidders who have independent, private
values vi which are either 1 or 3. For each bidder, suppose the probabilities of vi being 1 or
3 are independent (from other bidders) and both 1/2. (If there is a tie at a bid of x for the
highest bid the winner is selected at random from among the highest bidders and the price
is x.)
(a) What is the seller’s expected revenue from the auction? Justify your answer.
(b) Assume that we add a third bidder that behaves identically to the first two (whose value
vi
is also chosen independently of those for the first two). What is the seller’s expected
revenue? Justify your answer.
(c) Explain the trend you noticed between parts (a) and (b)—that is, why changing the
number of bidders affects (or doesn’t affect) the seller’s expected revenue.
* Bonus Question 1. Let’s say we define a “third-price auction” in the same manner that
we defined the first-price and second-price auctions. Is this mechanism DST, NT, or neither?
Does it DST-implement, NT-implement, Nash-implement, or fail to implement social welfare
maximization? Justify your answers, by proof or by counterexample.
Part 3: Sponsored Search
3
6. Suppose a search engine has two ad slots that it can sell. Slot a has a clickthrough rate of
10 and slot b has a clickthrough rate of 5. There are three advertisers who are interested in
these slots. Advertiser x values clicks at 3 per click, advertiser y values clicks at 2 per click,
and advertiser z values clicks at 1 per click.
Compute the socially optimal allocation and the VCG prices for it (using the Clarke pivot
rule). Show your work in full, and explain what your answer means in the sponsored search
context.
Part 4: Implementing Matching Market Pricing
The goal of this exercise is to implement an algorithm for finding market-clearing and VCG
prices in a bipartite matching market. Include your code in matching market.py.
7. Recall the procedure constructed in Theorem 8.8 of the notes to find a market equilibrium in
a matching market.
(a) The first step of this procedure involves either finding a perfect matching or a constricted
set. Recall that this can be done using maximum flow. Now, using your maximum-flow
implementation from assignment 2, implement an algorithm that finds either a perfect
matching M or a constricted set S in a bipartite graph.
(b) Now, given a bipartite matching frame with n players, n items, and values of each player
for each item, implement the full procedure to find a market equilibrium.
(c) Submit your code along with its output on the matching market frame in figure 8.3 as
well as 3 other small (10-20 node) test examples of your choice. Include the input and
outputs in a file called p7.txt.
8. Now, given a matching market frame, we will implement VCG pricing in this frame according
to the results of Theorem 10.8 in the notes.
(a) In order to do this, we must find the socially optimal outcome. Briefly justify that the
outcome that your algorithm from the previous question finds is socially optimal (this
can be done by simply stating 1-2 theorems from the notes).
(b) Finally, implement the VCG mechanism and Clarke pivot rule to construct an algorithm
that produces a positive set of VCG prices in any matching market frame.
(c) Submit your code along with its output on the matching market frame in figure 8.3 as
well as 3 other small (10-20 node) test examples of your choice. Include the input and
outputs in a file called p8.txt.
9. Now simulate your VCG pricing algorithm in the following context.
(a) First, construct a graph of 20 buyers and 20 items. Assume that “item” i is actually a
bundle of i identical goods. Now assign each player a random value per good (say, from
1 to 50; ties can be allowed). You shouldn’t need to do any additional work on your
algorithm to do this, instead just set each buyer’s value per bundle appropriately. How
should we set these values?
4
(b) Having set the values accordingly, run your VCG pricing algorithm and turn in the
results in a file called p9.txt. Explain why the results you obtained make sense in the
context above.
* Bonus Question 2. (Please note that each part of this question is intended to be harder
than the previous parts; each part will be graded separately, and you are not required to do
the whole thing.)
(a) Implement an algorithm for GSP pricing in a matching-market context. Compare your
VCG prices from the previous question to the GSP prices when run in the same contexts
(with the same randomness). Also, try to find and characterize some contexts where
VCG and GSP prices are similar, and where they are wildly different. Include a file
called bonus-2a.txt displaying input and output on a few examples.
(b) GSP isn’t truthful, so interesting things might happen if we run BRD on a GSP matching
market auction (where a player’s “strategy” is their valuation report). Implement an
algorithm that picks a random starting point and runs BRD to attempt to find a GSP
equilibrium state. What happens? Does BRD converge; if so, how quickly? Include a
file called bonus-2b.txt displaying input and output on a few examples.
(c) (Very difficult.) Either prove that BRD will converge in a GSP context, or disprove it
by counterexample.
Part 5: Exchange Networks for Uber
We will construct a simplified market scenario for a ridesharing app like Uber. Our world will
consist of an n × n grid (think of 100 × 100 as a test example), and there will be two types of
participants, riders and drivers.
• A rider R is specified by a current location (x0, y0) ∈ [n]×[n], a desired destination (x1, y1) ∈
[n] × [n], and a value for reaching that destination.
• A driver D is specified by a current location (x0, y0) ∈ [n] × [n].
We define the cost of a matching between a rider R and a driver D, c(R, D), to be the distance
from the driver to the rider and then to the destination (measured via manhattan distance, so the
distance from (0, 0) to (5, 2) is 7).
10. Encode the above example as an exchange network and implement it in ‘uber.py.’ Namely,
define a graph G = (V, E) where the vertices are the riders and drivers and there is an edge
between every rider and driver. What value should we associate with each edge in the graph?
Justify your answer.
11. Using your algorithm for matching markets above, implement a procedure (in uber.py) that
computes a stable outcome in this context. Note that there may not be the same number of
riders and drivers.
(a) Construct at least two test examples with at least 5 riders and drivers. Discuss what
the stable outcome is for your chosen examples. Explain what your results say about
how much the riders are charged and how much the drivers are profiting.
5
(b) Implement a procedure that on a 100×100 grid (1) generates r riders (located randomly
in the grid) each with a value of 100, d drivers (also located randomly in the grid) and
(2) computes a stable outcome given this context. Run your procedure many times when
r = d (say, 10 each), r is much less than d (say, 5 vs. 20), and when r is much greater
than d (say, 20 vs. 5). Discuss your results in detail. Specifically, discuss prices and
profits for different ranges of r and d.
12. With ridesharing apps, drivers often have preferences for where they want to drive. For
example, they know they are more likely to get a high value ride from the airport. Describe
in a few sentences how you you could modify the existing setup to include driver’s preferences.
* Bonus question 3 Suppose that the city implements a public transportation system. The
cost to take the public transportation system is a+b·dist(initial location, destintation), where
a is a fixed base fare and b is some constant factor multiplier. Furthermore, anyone can take
this public transportation system from any location.
(a) Implement a procedure that includes the public transportation option in when computing
the stable outcome above. Does a stable outcome always exist in this case?
(b) Choose different values for a and b and discuss how it affects the prices charged to riders/
profits of drivers.
(c) (Open ended: variable points awarded based on quality of solution.) Extend your context
to include other additional factors that you might find interesting. Summarize what you
did and what results you found in your writeup.
6