Game theory in computer science Shengyu Zhang The Chinese University of Hong Kong
Shengyu Zhang The Chinese University of Hong Kong
Map Intro to strategic-form games aTwo forms Examples oNE and CE Algorithmic questions in games Hardness of finding an NE and CE Congestion games Game theory applied to computer science
Map ◼ Intro to strategic-form games ❑ Two forms ❑ Examples ❑ NE and CE ◼ Algorithmic questions in games ❑ Hardness of finding an NE and CE ❑ Congestion games ◼ Game theory applied to computer science
Part I.strategic-form games
Part I. strategic-form games
Game:Two basic forms SCISSORS strategic (normal)form extensive form
Game: Two basic forms strategic (normal) form extensive form
First example:Prisoner's dilemma Two prisoners are on trial for a crime,each can either confess or remain silent. Confess Silent If both silent:both serve 2 years. If only one confesses:he 4 5 serves 1 year and the other Confess 4 serves 5 years. If both confess:both serve 4 years. 2 What would you do if you Silent are Prisoner Blue?Red? 5 2
First example: Prisoner’s dilemma ◼ Two prisoners are on trial for a crime, each can either confess or remain silent. ◼ If both silent: both serve 2 years. ◼ If only one confesses: he serves 1 year and the other serves 5 years. ◼ If both confess: both serve 4 years. ◼ What would you do if you are Prisoner Blue? Red? Confess Silent Confess 4 4 5 1 Silent 1 5 2 2