STAT 155 HW from GAME Theory, Alive. Due MAR 20: ----------- Chapter 3: 3.7 + 3.10 Chapter 4: 4.4 + 4.10 Due APR 3: ----------- Chapter 4: 4.5 + 4.8 + 4.12 + 4.13 In problem 4.13: The cost of traveling a given road depends on the total number of drivers k that use this road according to the formula. Due APR 10: ----------- P1. Chapter 6: 6.1 P2. Consider a Majority vote on 5 candidates where the vote passes if at least 3 voters support the vote. Assume that the value of passing the vote is 1 and of not passing is 0. Find the Shapely value of each of the 5 voters. P3. Solve the previous problem for n=2k+1 voters for k > 1 where the vote passes if at least k+1 voters support it. P4. Consider an Electoral College vote on 3 states each with 1,000,001 voters. The vote passes if at least 2 state pass the vote by Majority (that is at least 500,001 of the voters vote for it). Assume that the value of passing the vote is 1 and not passing it is 0. Find the Shapely values of each of the voters. Problems to be reviewed on Apr 8: --------------------------------- 3.3 3.5 4.1 4.8 and 4.14 HW Due APR 17: -------------- Problem 4.7 + the following: . Consider an auction where a seller sells two identical items. There are n buyer each interested in exactly one item: Player i has value v_i for having on item, value v_i for having the two items and value 0 for having no item. Consider the following auction where the items go to the two highest bidders and the price each of them pay is given by the 3rd bid. Show that all bidders bidding their value is a pure Nash Equilibrium. HW Due APR 24: -------------- 1. A secret S mod 7 is distributed using a degree 2 polynomial F (mod 7), so that each set of 3 players can recover the secret. A. Suppose F(1) = 4, F(2) = 2 and F(4) = 4 - find the secret. B. Is it possible that F(3) = 4? Is it possible that F(5) = 4? Explain your answer. 2. Devise a protocol to share a secret S between players 1,2,3,4,5,6,7 s.t. if either {1,2,3} collaborate or {4,5,6,7} collaborate then they can recover the secret exactly , but any set A of players not containing either {1,2,3} or {4,5,6,7} does not have any information on the secret. (Explain your answer; a formal proof is not required). 3. Consider a parliament P = {1,2,3,4,5,6,7,8,9} consisting of 3 parties A1 = {1,2,3}, A2 = {4,5,6} and A3 = {7,8,9} Devise a protocol to share a secret S between the members of P such that: Any 4 members, 2 belonging to one party and 2 to another, can recover the secret (e.g. {1,2,4,5} or {1,2,4,6} or {4,6,8,9} can recover the secret) but any set of members not containing such 4 members does not have any information on the secret (e.g. sets {1,2,3,4,7} or {7,8,9,5,2} have no information on the secret). (Explain your answer; a formal proof is not required). HW Due MAY 1: -------------- 1. Consider the "cake" given by the interval [-1,1] with the algebra of sets (slices) given by finite unions of intervals. Let u1,u2,u3,u4 be 4 probability measures on the interval: u1 has density 1/2, u2 has density (1+x)/2, u3 has density (1-x)/2 and u4 has density 1.5*x^2 (x^2 is the square of x). Find a partition of the interval/cake into 4 slices A1,A2,A3,A4 s.t: u1(A1), u2(A2), u3(A3) and u4(A4) are all at least 1/4. 2. Same as problem 1 - but let the cake now be [0,1] and have 5 functions u_1,u_2,u_3,u_4 and u_5 where u_j has density (j+1) x^j (that is (j+1) times x to the j'th power). 3. Suppose there are 10 items and 4 players the values of the items to the players is given by: I 01 02 03 04 05 06 07 08 09 10 A: 14 15 20 20 12 17 17 19 19 20 B: 10 13 17 18 15 18 15 18 13 16 C: 16 20 16 10 15 15 17 13 18 20 D: 20 10 20 13 17 11 20 15 12 19 Find a partition of the items between the 4 players such that the max envy between any two players is at most 20 and the envy graph contains no directed cycles. HW Due May 8 (exam prep): -------------------------- Solve the following 5 problems: 1. Let G1 be a subtraction game with subtraction set {1,3,4} Let G2 be a subtraction game with subtraction set {2,4,5} Let G3 be a subtraction game with subtraction set {1,2,3,4,5,6,7} who has a winning strategy from starting position (60,60,60) in G1 + G2 + G3? Explain carefully each step of your derivation. 2. Consider the following 4X4 matrix: 1101 0000 1000 0110 and a hide and seek game on the matrix. Find optimal strategies for the two players. (state the results you are using). 3. 10 drivers wish to drive from point A to point B using the following roads: C -------------- E | | | | | | A----------------B | | | | | | D----------------F The cost of using road AB per driver using it is 5k+5 where k is the number of drivers using the road. For CE it is k+1; for DF it is k+1; for AC it is 2k+1; for AD it is 3k+1; for EB it is 3k+1 and for FB it is 2k+1. find a pure Nash equilibrium for the game. 4. Consider k players 1,2,...,k and n items denoted a,b,c ... Let v_i(a) be the value of items a to player i. A. Show that it is possible do divide the n items between the k players such that the number of ordered pairs of players (i,j) such that i envies j is at most k-1. B. For every k construct an example where it is impossible to divide n items between the k players such that the number of ordered pairs of players (i,j) such that i envies j is at most k-2 (you are allowed to chose n to be any number). 5. Consider the following rankings x: a > b > c > d y: b > a > c > d z: a > b > c > d w: a > b > d > c a: y > x > z > w b: x > y > z > w c: x > y > w > z d: x > y > z > w Find *all* stable matchings of {a,b,c,d} and {x,y,z,w} (justify your claims!)