CMU School of Computer Science1515--780: Graduate AI780: Graduate AIComputational Game TheoryComputational Game TheoryMichael BenischCarnegie Mellon University, School of Computer ScienceCMU School of Computer ScienceOutlineOutline• What is a game?• Multi-Objective Optimization vs. Game Theory• Importance of Game Theory in AIq Helps agents select strategiesq Guarantees about artificially designed mechanismsq Automated analysis of strategic modelsq Games in the real world• Solving games with AIq Computing Nash equilibriaq Complexity results on solving gamesq Alternative solution conceptsCMU School of Computer ScienceO utline (c o nt’d )O utline (c o nt’d )• Building games with AIq Mechanism design problem and Revelation Principleq Game theoretic properties of auctions: 1stprice, 2ndprice, eBayq Implementation in dominant strategiesq Vickrey-Clarke-Groves Mechanismq Automated Mechanism DesignCMU School of Computer ScienceBackgroundCMU School of Computer ScienceWhat is a Game?What is a Game?• A game is a multi-agent model of the relationships betw een agen t’s action s an d in cen tives.q When agents are self-interested the game models an optimization processq Games can have underlying probabilistic models to describe uncertain outcomesCMU School of Computer ScienceQuestions asked about a gameQuestions asked about a game• How should an agent behave?• What is the most likely state the game will settle in?• Can the game be designed to incentivizespecific actions?CMU School of Computer ScienceMultiMulti--Objective OptimizationObjective Optimization• Class of optimization models involving simultaneously optimizing multiple objectives:)(...)()(21xfxfxfn maxxf1(x)f2(x)Solution: Pareto-optimal curve(set of points where each obj. fn. cannot grow larger without decreasing another).Optimization ModelCMU School of Computer ScienceMultiMulti--Objective Optimization vs. Objective Optimization vs. Game TheoryGame Theory• Games are similar to multi-objective optimization models, differences are:q Each objective function is owned by a different agent.q The decision variables are partitioned into those controlled by the owner of each objective function.x = {x1, x2, … , xk, … , xm}• Agent 1 owns f1and controls variables x1, … , xk )(...)()( 21xfxfxfnCMU School of Computer ScienceMultiMulti--Objective Optimization vs. Objective Optimization vs. G a m e The o ry (c o nt’d )G a m e The o ry (c o nt’d )Action of Player 1Pareto Optimal Curve(solution to multi-objective optimization problem)f1(x)f2(x)Nash EquilibriumAction of Player 2CMU School of Computer ScienceAI + Game TheoryAI + Game Theory• Help agents select strategies• Help design games that have certain properties• Help analysts understand a systemCMU School of Computer ScienceReal World GamesReal World Games• Games related to warfareq Pursuit and evasion: dogfights, missiles, troopsq Strategic resource deployment: troops, weapons• Games related to economicsq Auctions: FCC Spectrum, Google keywordsq Buying/Selling: resource procurement, stock market, dynamic pricing• Games related to networksq Network formation: social, corporate, P2Pq Graphical games: dependency of player actions is described by network between players• Recreational gamesq Perfect information: chess, checkers, goq Limited information: poker, football, video gamesCMU School of Computer ScienceSolving Games with AICMU School of Computer ScienceReview: NotationReview: Notation• Agent = player: set of all players is N = {1,… ,n}• Action = move: choice that an agent can make at a point in the game• Strategy ai: mapping from distinguishable states of the game to actions• Strategy set Si: strategies available to agent iCMU School of Computer ScienceReview: NotationReview: Notation• Strategy profile S = {s1, … , sn}: one strategy per agent• Utility function ui(S): mapping from strategy profiles to utilities for player i• Opposing profile, S-i: strategies of agents other than i (in general the notation –i excludes i)CMU School of Computer ScienceReview: Key Review: Key ConceptsConcepts• Normal Form (Matrix, Simultaneous) Game:q Outcome functions are matrices for each playerq A p layer’s matrix indicates his utility for playing each possible action against any opponent profile.• Example NFG: P rison er’s D ilem m aC Dc (3,3) (0,5)d (5,0) (1,1)CMU School of Computer ScienceReview: Key Review: Key ConceptsConcepts• Extensive Form Game: provides additional tree structure to game, allowing for players to take turns sequentially (also called sequential form).• Example EFG: Iterative Rock-Paper-ScissorsP1P2 P2 P2L WRRR … SSSr (0,0) … (1,-1)p (1,-1) … (-1,1)s (-1, 1) … (0,0)ConversionCMU School of Computer ScienceReview: Key Review: Key ConceptsConcepts• EFG Imperfect information and Chance nodes: players cannot observe all prior moves and some m oves are m ad e by “n atu re”R P Sr(1,-1) 50%(-1,1) 50%(-1,1) (1,-1)p (1,-1)(1,-1) 50%(-1,1) 50%(-1,1)s (-1, 1) (1,-1)(1,-1) 50%(-1,1) 50%ConversionP1P2 P2 P2Information set: player 2 does not know which node he is in.L WNaLW50%50%Chance node: nature takes an action randomly w/ specified probabilityCMU School of Computer ScienceReview: Key Review: Key ConceptsConcepts• Mixed strategy (profile): a randomized strategy that specifies probabilities with which to take each action.• Best response: the action corresponding to the highest (expected) utility given the actions of other players. q Proposition: any player has apure strategy best response toevery opponent (mixed) profileC Dc (3,3) (0,5)d (5,0) (1,1)[0.75, 0.25]C Dc (3,3) (0,5)d (5,0) (1,1)CMU School of Computer ScienceSolving GamesSolving Games• Solving a game: predicting (or suggesting) agent behavior and the resulting outcome(s) of the game.• Solution concept: the principle by which agents are assumed to act.q Default concept is Nash equilibrium: players will settle into a profile when they cannot unilaterally improve.C Dc (3,3) (0,5)d (5,0) (1,1)CMU School of Computer ScienceFinding Nash Finding Nash EquilibriaEquilibria• Existence: Nash proved at least one equilibrium in (potentially) mixed strategies always existsq Proof sketch: Uses B rou w er’s fixed point theorem w h ich states th at every “regu lar” n-D function has at least one fixed point x such that f(x) = x.• Zero-sum games: linear