C103 (Spring 2020) – Final Solutions
1. Consider the TTC algorithm for the given housing market:
Step1: Agents1,2and6pointto5;agents4and5pointto1;and3pointsto4. The only cycle formed consists of 1 and 5. Therefore, 1 receives e and 5 receives a. The remaining agents and objects are N1 = {2,3,4,6} and X1 = {b,c,d,f}.
Step 2: All agents (including 4) point to 4. The only cycle is the self-cycle con- sisting of 4, so 4 receives d. The remaining agents and objects are N2 = {2,3,6} andX2 ={b,c,f}.
Copyright By PowCoder代写 加微信 powcoder
Step 3: Agent 2 points to 3; 3 points to 6; and 6 points to 2. We have a three-cycle where 2 receives c, 3 receives f, and 6 receives b. There are no remaining agents and objects, i.e., N3 = X3 = ∅, so the algorithm terminates.
The resulting assignment is μT T C = (1e, 2c, 3f, 4d, 5a, 6b). By the Roth-Postlewaite Theorem μTTC gives the unique assignment in the core.
Take any price vector p = (pa, pb, pc, pd, pe, pf ) such that the price of an object is decreasing in the step in which that object is allocated in the TTC algorithm (for example p = (3, 1, 1, 2, 3, 1)). Then, (μT T C , p) is a Walrasian equilibrium.
(a) Step 1: U is strictly dominated by 21δM + 12δD. Step 2: m is strictly dominated by 12δL + 12δR. Step 3: D is strictly dominated by M.
Step 4: L is strictly dominated by R.
So (M, R) is the only pure strategy profile that survives IESDS.
(b) Step 1: Player 1 is rational.
Step 2: Player 2 knows that Player 1 is rational. Player 2 is rational.
Step 3: Player 1 knows that Player 2 knows that Player 1 is rational. Player 1 knows that Player 2 is rational. Player 1 is rational.
Step 4: Player 2 knows that Player 1 knows that Player 2 knows that Player 1 is rational. Player 2 knows that Player 1 knows that Player 2 is rational. Player 2 knows that Player 1 is rational. Player 2 is rational.
(c) By a result from class, the set of strategies played with positive probability in a NE survive IESDS. Therefore, there can not be any NE (mixed or pure strategy) other than (M, R). Furthermore, since by Nash’s result every finite
normal-form game has a NE, (M, R) must be a NE. So (M, R) is the unique NE of this game.
The ex-post efficient allocations of the objects and the pivotal mechanism transfers for the two type profiles are:
Two things about the above example are noteworthy. First, at the true-type profile θ, agents 2 and 3 can jointly misrepresent their types as θˆ and θˆ and
k∗(θ1, θ2, θ3) = t1(θ1,θ2,θ3) = t2(θ1,θ2,θ3) = t3(θ1,θ2,θ3) =
k∗(θ,θˆ,θˆ) = 123
t (θ ,θˆ,θˆ) = 1123
t (θ ,θˆ,θˆ) = 2123
t (θ ,θˆ,θˆ) = 3123
(2, 0, 0) (0+0)−(4+4)=−8 (10+0)−(10+0)=0 (10+0)−(10+0)=0 (0,1,1) (9+9)−(9+9)=0 (0+9)−(10+0)=−1 (0+9)−(10+0)=−1
obtain a payoff of 3=4-1 each, instead of zero. So even though VCG mecha- nisms are strategy-proof/dsic, they may be prone to collusive manipulation. Secondly, when the pivotal mechanism interpreted as a package auction, the revenues of the seller are not monotone: Even though all valuations are higher at the second profile, the seller’s total revenue is less (2 instead of 8).
4. We will give a counterexample. Let X = {x,y,z}, e(x) = 2, e(y) = 1.5, and e(z) = 0, and let g(z) > g(y) > g(x). Note that z = c({x,y,z}), but x = c({x,z}). So c fails Sen’s condition α. Therefore by the revealed preference theorem, there is no rational preference R on X such that c = cR.
5. The virtual valuations of the bidders are:
c1(x1)=x1−1−x1 =2×1−1 and c2(x2)=x2−1−21×2 =2×2−2
which are both strictly increasing, so the regularity condition is satisfied. By Myerson’s result, the allocation probabilities in a revenue-maximizing IR and BIC direct auction mechanism are as follows: The highest virtual valuation bidder
receives the object if her virtual valuation is nonnegative; and the seller keeps the object if both virtual valuations are negative.
Bidder 1 gets the object if and only if c1(x1) ≥ 0 and c1(x1) ≥ c2(x2) if and only if x1 ≥ 21 and x1 + 12 ≥ x2
Bidder 2 gets the object if and only if c2(x2) ≥ 0 and c2(x2) ≥ c1(x1) if and only if
x2≥1 and x2≥x1+21
(Note: For valuation pairs satisfying x1 ≥ 12 , x2 ≥ 1 and x2 = x1 + 12 , either bidder can get the object.)
The object is not always allocated to one of the two bidders: If x1 < 12 and x2 < 1, then the seller keeps the object.
The object is not always allocated to the bidder with the highest valuation: If x2 − 21 ≤ x1 < x2 and x1 ≥ 12 (e.g. x1 = 0.75 and x2 = 1), then bidder 2 has the highest valuation, but bidder 1 receives the object.
6. Since all agents find those on the other side acceptable, in all stable matchings all agents must be matched (otherwise any unmatched man-woman would form a blocking pair). Therefore, there are 3! = 6 matchings that are candidate stable matchings. We will argue that exactly three out of those six matchings are stable.
We can use the DA algorithm to find the woman-optimal and man-optimal stable matchings (both algorithms terminate in the first step): μW = (1c,2a,3b) and μM = (1a,2b,3c). We know from the Gale-Shapley Theorem that both μM and μW are stable.
The matching μ = (1b, 2c, 3a) is also stable. To see this, we will use the following property of the given preference profile: For any given pair of agents i,j from different sides, i top ranks j if and only if j bottom ranks i. Note that at μ, all agents are matched to their second-ranked partner. Suppose a pair of agents i, j forms a blocking pair. Then i must top rank j, implying that j bottom ranks i, so i, j can’t form a blocking pair. Therefore, μ is pairwise stable. It is also individually rational since all agents find those on the other side acceptable, showing that μ is a stable matching.
We next show that none of the three other matchings where all agents are matched is stable. In any such matching ν, at least one woman w is matched to her top choice and at least one woman w′ is matched to her bottom choice. Let m = ν(w). Since w top ranks m, m must bottom rank w. So (m,w′) form a blocking pair, showing that ν is not stable.1
1More specifically, ν = (1c,2b,3a) is blocked by (1,b); ν = (1b,2a,3c) is blocked by (2,c); and ν = (1a, 2c, 3b) is blocked by (3, a).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com