UNIVERSITY OF SOUTHAMPTON COMP6207W1 SEMESTER 2 EXAMINATION 2014 - 2015 ADVANCED INTELLIGENT AGENTS DURATION 120 MINS (2 Hours) This paper contains 10 questions Answer ALL questions from section A (30 marks) and THREE of the FIVE questions from section B (42 marks). An outline marking scheme is shown in brackets to the right of each ques- tion. This examination is worth 72%. The coursework was worth 28%. University approved calculators MAY be used. A foreign language word to word® translation dictionary (paper version) is permitted provided it contains no notes, additions or annotations. Page 1 of 12 Copyright 2015 c© University of Southampton Page 1 of 12 2 COMP6207W1 Section A Question A1. Consider the variant of the Battle of Sexes game in Table 1: C D A (2, 1) (0, 0) B (0, 0) (1, 2) TABLE 1: Battle of Sexes game. (a) Find all its Nash equilibria—both in mixed and pure strategies. [2 marks] (b) Calculate the correlated equilibrium that corresponds to the mixed strategy Nash equilibrium of this game. [1 marks] (c) Show one more correlated equilibrium. [1 marks] (d) Find—both pure and mixed—the safety level (maximin) strategies of player 1. Indicate his corresponding (expected) payoffs. [2 marks] Copyright 2015 c© University of Southampton Page 2 of 12 3 COMP6207W1 Question A2. Consider the 2-player game in Table 2: L C R T 7, 2 5, 4 6, 3 M 8, 2 3, 1 3, 5 B 2, 2 6, 3 5, 3 TABLE 2: 2-player game. (a) For each player, indicate all his best responses in pure strategies against any (pure) action of his opponent. Is there a pure strategy Nash equilibrium? [2 marks] (b) Can a pure strategy equlibrium be obtained by elimination of (weakly) dominated strategies? If so, what is the order of elimination? [1 marks] (c) Is there a best response strategy which is not rationalisable? Explain your answer. [2 marks] (d) Find all rationalisable strategies for both players. [2 marks] (e) Is there a strong equilibrium in this game? Show one, if it exists. Explain your answer. [1 marks] Copyright 2015 c© University of Southampton TURN OVER Page 3 of 12 4 COMP6207W1 Question A3. (a) Describe the revenue equivalence theorem and its main implications. [2 marks] (b) Discuss why, despite the revenue equivalence theorem, truthful auc- tions are preferred. In doing so, discuss the main assumptions made and Wilson’s doctrine. [3 marks] Copyright 2015 c© University of Southampton Page 4 of 12 5 COMP6207W1 Question A4. Consider the sponsored search setting in Table 3 containing 4 ads (agents) and 2 slots. Here, vi is the agent’s value when his ad is clicked, and qi is the quality assigned to that ad by the search engine. In addition, each of the 2 slots has a position-dependent probability λj for position j, where λ1 = 1.0 and λ2 = 0.5. The click probability of ad i in position j is given by qi × λj. Ad (Agent) Value Quality 1 v1 = 1 q1 = 0.3 2 v2 = 2 q2 = 0.7 3 v3 = 3 q3 = 0.2 4 v4 = 4 q3 = 0.3 TABLE 3: The valuations and qualities of the agents and their ads. (a) Assuming truthful reporting, compute the position and payments of the agents when using the GSP auction. [3 marks] (b) Compute the agents’ (expected) utilities in this allocation. [2 marks] (c) In this setting, can any of the agents benefit by misreporting? Explain. [2 marks] Copyright 2015 c© University of Southampton TURN OVER Page 5 of 12 6 COMP6207W1 Question A5. The school board is voting whether to award the contract for building a new elementary school to Aasgaard Architects (A), Bob’s Builders (B), Cobber Construction (C) or Dora’s Developers (D). There are 12 members of the board, whose preferences over the candi- dates are distributed as follows: Ranking # voters 5 : B C D A 3 : B C A D 3 : C A D B 1 : A D C B (a) The school board votes using Borda count. Which company will get the contract? [2 marks] (b) Does this seem fair? Why or why not? [1 marks] (c) Could you suggest a better voting procedure to the school board? Justify your suggestion. [1 marks] Copyright 2015 c© University of Southampton Page 6 of 12 7 COMP6207W1 Section B Question B1. (a) For games in Table 4 and 5 verify if they possess a potential function (exact, ordinal or generalised ordinal). Provide such a function if it exists, or prove why it is not possible. [3 marks] H T H (1,−1) (−1, 1) T (−1, 1) (1,−1) TABLE 4: Matching Pennies. C D A (2, 1) (0, 0) B (0, 0) (1, 2) TABLE 5: Battle of Sexes. (b) Is there a game with a unique pure strategy Nash Equilibrium, which does not have a generalised ordinal potential? Give an example of such a game if it exists, or prove why it is not possible. [2 marks] (c) Consider the congestion game G = 〈N,R, (Si)i∈N , (ur)r∈R〉 where: • N = {1, 2} - set of two agents • R = {r1, r2} - set of two resources • ∀i ∈ N , Si = {r1, r2} - set of strategies for each agent (an agent can select either resource r1 or resource r2 but not both – that is, G is a resource selection game) • ∀r ∈ R, ur(k) is the utility to each user of resource r if the total number of its users is k. Write down the payoff matrix for this game. Prove that a pure Nash equilibrium must exist for any assignment of utility functions ur(k). [4 marks] Copyright 2015 c© University of Southampton TURN OVER Page 7 of 12 8 COMP6207W1 (d) Let G be a resource selection game with agents N = {1, . . . , n}, resources R = {r1, . . . , rm}, strategy sets Si ⊆ R for i ∈ N and utility functions ur for r ∈ R. Show that if the utility functions ur are monotonically decreasing, then every pure strategy Nash equilbrium of G is a strong equilibrium. [5 marks] Copyright 2015 c© University of Southampton Page 8 of 12 9 COMP6207W1 Question B2. Consider the cooperative game (N, v) with three agents N = {a, b, c}, represented as an MC-net as follows: (a, 5) (a ∧ b, 4) (b, 3) (a ∧ c,−2) (c, 2) (b ∧ c,−1) (a ∧ b ∧ c, 2) (a) Find the characteristic function of the game. [3 marks] (b) Verify if the game is motonone. [2 marks] (c) Verify if the game is super-additive. [2 marks] (d) Compute the Shapley value for all the agents. [5 marks] (e) Is the Shapley payoff distribution in the core of the game? Why? [2 marks] Copyright 2015 c© University of Southampton TURN OVER Page 9 of 12 10 COMP6207W1 Question B3. Facebook applies the Groves mechanism with Clarke pivot rule (a.k.a. VCG) for its display advertising. Consider a setting where 2 slots are sold using this mechanism for a visiting user, and there are 3 interested advertisers (agents) A, B, and C competing for these slots. One of the slots is more prominent and therefore more valuable to all agents. Also, two of the advertisers, A and B are direct competitors since they are selling similar products (e.g. Apple vs Microsoft). Therefore, if A’s ad is shown in either slot, the value of the remaining slot for B is diminished, and similar for A if B’s ad is shown. Consequently, the utility not only depends on which slot they receive, but also on who receives the other slot (there are so-called allocative externalities). All advertisers prefer to receive both slots compared to one slot. The valuations are given in Table 6, where v indicates the value without the slot awarded to the direct competitor, and v′ the value in case the other slot is given to the direct competitor. Agent Slot 1 Slot 2 Slots 1 and 2 A vA,1 = 2.0,v′A,1 = 1.5 vA,2 = 1.6,v ′ A,2 = 0.9 vA,1+2 = 2.3 B vB,1 = 2.5,v′B,1 = 1.6 vB,2 = 2.0,v ′ B,2 = 1.5 vB,1+2 = 2.9 C vC,1 = 1.0 vC,2 = 0.7 vC,1+2 = 1.1 TABLE 6: Agent Preferences (a) Briefly describe the revelation principle and its main implication. [2 marks] (b) Given the valuations in Table 6, what is the allocation that maximises social welfare? How much is the social welfare in this case? [3 marks] (c) Compute the transfers for all agents when applying the Groves mech- anism with the Clarke pivot rule. [6 marks] (d) Show whether the resulting transfers are (1) individually rational, (2) weakly budget balanced, (3) strongly budget balanced. [3 marks] Copyright 2015 c© University of Southampton Page 10 of 12 11 COMP6207W1 Question B4. (a) Consider the following voting profile: Ranking # voters 5 : B E A C D 3 : C E A D B 3 : D A E C B 1 : A C E D B Find the winner of the election held using each of the following voting schemes. Provide the corresponding winning score or the elimination procedure when relevant. (i) Plurality vote. (ii) STV. (iii) Maximin. (iv) Copeland. Is there a Condorcet winner or a Condorcet loser in this profile? [10 marks] (b) Use the following voting profile to prove that no positional scoring rule with a strictly descending scoring vector will satisfy the Condorcet principle: Ranking # voters 3 : A B C 2 : B C A 1 : B A C 1 : C A B [4 marks] Copyright 2015 c© University of Southampton TURN OVER Page 11 of 12 12 COMP6207W1 Question B5. Consider the problem of finding a stable matching between two equal- sized sets of elements (the set of boys and the set of girls). (a) Construct an example, in which there is more than one stable match- ing. (You only need two boys and two girls to do this.) [4 marks] (b) Suppose that the boys all have different favourite girls. How many steps does it take for the Gale-Shapley algorithm to converge? Ex- plain! [2 marks] (c) Suppose that the boys have identical preferences. How many steps does it take for the algorithm to converge? Explain! [3 marks] (d) Suppose preferences are given by Tables 7 and 8: 1 2 3 4 5 Adam Beth Amy Diane Ellen Cara Bill Diane Beth Amy Cara Ellen Carl Beth Ellen Cara Diane Amy Dan Amy Diane Cara Beth Ellen Eric Beth Diane Amy Ellen Cara TABLE 7: Boys’ preferences. 1 2 3 4 5 Amy Eric Adam Bill Dan Carl Beth Carl Bill Dan Adam Eric Cara Bill Carl Dan Eric Adam Diane Adam Eric Dan Carl Bill Ellen Dan Bill Eric Carl Adam TABLE 8: Girls’ preferences. Find a stable matching using the Gale-Shapley algorithm with boys making proposals. Find a stable matching using the Gale-Shapley algorithm with girls making proposals. [5 marks] Copyright 2015 c© University of Southampton END OF PAPER Page 12 of 12
欢迎咨询51作业君
