COMP323 Exam Paper 2008-09

PAPER CODE NO.EXAMINER:Dr.P.Krysta

COMP323DEPARTMENT:Computer Science Tel.No.54266

JANUARY2009EXAMINATIONS

Introduction to Computational Game Theory

TIME ALLOWED:Two and a Half Hours

INSTRUCTIONS TO CANDIDATES

Answer SEVEN questions in Section A.

Answer THREE questions in Section B.

If you attempt to answer more questions than the required number of questions(in any section), the marks awarded for the excess questions answered will be discarded(starting with your lowest mark).

Section A

1.For each of the following known games,point out what are the types of games from game

theory together with appropriate solution concepts(equilibria)that model these games: Prisoner’s Dilemma,Chess,Tick-Tack-Toe,Matching Pennies.(4marks)

Note,that the game Tick-Tack-Toe is also known as Noughts-And-Crosses.

2.Describing applications of game theory in computer science:

(a)Describe the application of game theory in Google’s sponsored search.(You should

describe the setting in more detail,and in particular,explain the game theoretic as-

pects.)(6marks)

(b)Give two other examples of applications of game theory in computer science,or ap-

plications of computer science within game theory.(no details required)(4marks) 3.What is the main obstacle in applying the VCG mechanism for optimization problems like

Combinatorial Auction?Justify your answer.(5marks)

4.Explain the connection between zero-sum strategic games,mixed strategy Nash equilibria,

and linear programming.(5marks)

5.Consider the following strategic situation of an arms race.We have two countries,and

each country can build an arsenal of nuclear bombs,or can refrain from doing so.Assume also that each country’s favorite outcome is that it has bombs and the other country does not;the next best outcome is that neither country has any bombs;the next best outcome is that both countries have bombs(what matters is relative strength,and bombs are costly to build);and the worst outcome is that only the other country has bombs.

Model the described scenario as a strategic game:

(a)De?ne an appropriate strategic game by:de?ning the set of players,action sets,and

by presenting the players’preferences by using preference relations and by using a

table of payoffs.(6marks)

(b)Is there any other,famous game that the de?ned game in5a is equivalent to(i.e.,the

two games only differ in the names of strategies,but the players’preferences are the

same)?(4marks)

When answering question5b you should explicitly spell out the correspondence between the two games,i.e.,say how the players’strategies correspond to one another.

6.For the following given game,?nd all its pure Nash equilibria by using the method of best

response functions.Note,that you need to provide some justi?cation while applying this

method here.(8marks)

7.Consider the problem of auctioning a single good among a set of potential buyers using

the second price auction(more precisely we are interested in the second-price sealed-bid

auction with perfect information).

(a)De?ne this setting as a strategic game,i.e.,de?ne the set of players,actions,players’

preferences(de?ned in a convenient way),etc.(5marks)

(b)Give an example of a(pure)Nash equilibrium of this game and argue(justify)that it

indeed is a Nash equilibrium.(8marks)

Section B

1.(Modelling strategic games).Consider the following two-player game,played in ancient

Rome(known as“micatio”or“Morra”):The players simultaneously hold up some?ngers and each guesses the total number of?ngers held up.If exactly one player guesses cor-rectly,the other player pays her the amount of her guess(in pounds,say).If either both players guess correctly or neither does so,then no payments are made.Consider a version of the game in which the number of?ngers each player may hold up is restricted to be either one or two.

(a)Model this situation as a(zero-sum)strategic game,i.e.,de?ne the players,their strate-

gies,and give a table with the payoffs.Note that each player has4relevant actions.

(10marks)

(b)Using the method of best response functions,show that this game does not possess

any pure Nash equilibrium.(5marks)

2.(Buying a path in a network).Consider the communication network,modeled as a graph

G=(V,E)in the picture below.Each link e∈E is owned by a different player,and has the cost c e>0shown in the table below for using his link to carry some message.Assume we use the VCG mechanism to buy a path between the vertices s and t in the picture.

(a)Determine the output of VCG mechanism,i.e.,the output s?t path.(5marks)

(b)Compute the VCG payments of all players in this example by using the Clarke rule.

Explain your derivation of the payment for one of the players.(10marks)

3.(Monotonicity of algorithms for CA).Consider the problem of Combinatorial Auction (CA)with single-parameter agents.We have the following instance of CA:there are 4goods {1,2,3,4},and 5buyers,who desire the sets S 1={1,2,4},S 2={3},S 3={1,4},S 4={2},and S 5={2,3},respectively.Their valuations are v 1=4√3,v 2=1,v 3=5√2,v 4=3,and v 5=2√2,respectively.Answer the following questions:

(a)Simulate on this instance the Greedy algorithm from the lectures and ?nd the output

solution.(2marks)

(b)We know that algorithm Greedy is monotone.Explain what it means to say that this

algorithm is monotone on the considered instance of CA.(3marks)

(c)A monotone algorithm implies critical values for each buyer.Find the critical values

for all winning agents in the output solution of Greedy (explain your derivation in each case).(8marks)

(d)What is the connection between incentive-compatible mechanisms for CA (like Greedy),

monotonicity and critical values ?(2marks)

4.(GSP and VCG mechanisms for sponsored search auctions).Consider the following spon-sored search keyword auction:there are three slots (k =3)and four bidders (advertisers;n =4).The slots have the following click-through-rates:α1=10,α2=5and α3=2.Bidders have the following per-click valuations:v 1=11,v 2=7,v 3=4and v 4=1.Suppose that the bidders bid truthfully,i.e.,their bids are b 1=11,b 2=7,b 3=4and b 4=1,respectively.

(a)Determine the outcome (assignment)of the VCG mechanism and that of the GSP

mechanism in the de?ned instance.(3marks)

(b)Compute the VCG payments of the winning bidders and their payoffs under the VCG

auction.(5marks)

(c)Compute the GSP payments of the winning bidders and their payoffs under the GSP

auction (assuming,as in 4b,that the bidders bid truthfully,i.e.,b 1=v 1,b 2=v 2,b 3=v 3and b 4=v 4).(4marks)

(d)What are the revenues under the VCG and GSP auctions in this example ?The com-

parison of these two revenues highlights a more general phenomenon –why is it im-portant to companies like Google or Yahoo ?(3marks)

When answering 4b and 4c explain your derivations,possibly by giving appropriate for-mulas.