DOC PREVIEW
Duke CPS 296.1 - Concise representations of games

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Concise representations of gamesGames with many agentsCongestion games [Rosenthal 73]Example: writing paper/playing video gameExample: network routingPotential games [Monderer & Shapley 96]Potential games always have a pure-strategy equilibriumEvery congestion game is a potential game!Graphical games [Kearns et al. 01]Action-graph games [Bhat & Leyton-Brown 04]Any normal-form game can be expressed as an action-graph gameAction-graph games can capture the structure of graphical gamesComputing expected utilities in AGGs [Jiang & Leyton-Brown AAAI06]Bayes nets: Rain and sprinklers exampleMore elaborate rain and sprinklers exampleMAIDs [Koller & Milch 03]MAIDs…Concise representations of gamesVincent Conitzer [email protected] with many agents•How do we represent a (say, simultaneous-move) game with n agents?•Even with only 2 actions (pure strategies) per player, there are 2n possible outcomes–Impractical to list them all•Real-world games often have structure that allows us to describe them concisely•E.g., complete symmetry among players–How would we represent such a game?–How many numbers (utilities) do we need to specify?–For more, see e.g., Brandt et al. 2009, Jiang et al. 2009•What other structure can we make use of?Congestion games [Rosenthal 73]•There is a set of resources R•Agent i’s set of actions (pure strategies) Ai is a subset of 2R, representing which subsets of resources would meet her needs –Note: different agents may need different resources•There exist cost functions cr: {1, 2, 3, …} →  such that agent i’s utility for a = (ai, a-i) is -Σr in ai cr(#(r, a)) –#(r, a) is the number of agents that chose r as one of their resourcesExample: writing paper/playing video game•Player 1 needs to write a paper•Player 2 (player 1’s roommate) “needs” to play a video game•Resources: 1’s Laptop (L1), 2’s Laptop (L2), Video game system (V), Internet connection (I), Common room (C), Bedroom (B)–Both rooms have (shared) internet connection, video game system cannot be moved out of common room•Player 1’s action set: {{L1, I, C}, {L1, I, B}}•Player 2’s action set: {{V, C}, {L2, I, C}, {L2, I, B}}•For all resources r, cr(1) = 0, cr(2) = 1•What are the pure-strategy equilibria?Example: network routing•Player 1 has source A and target E•Player 2 has source B and target C•Player 3 has source B and target E•Resources = edges•Player 1’s action set: {{AD,DE}, {AB,BD,DE}, {AC,CD,DE}}•Player 2’s action set: {{AB,AC}, {BD,CD}, {AB,AD,CD}, {BD,AD,AC}}•Player 3’s action set: {{BD,DE}, {AB,AD,DE}, {AB,AC,CD,DE}}•For all resources r, cr(1) = 0, cr(2) = 1, cr(3) = 2•Pure-strategy equilibria?ABCDEPotential games [Monderer & Shapley 96]•A potential game is a game with a potential function p: A →  (A is set of all joint actions (pure strategy profiles, outcomes)) such that•for all players i, all a-i, all ai, all ai’,•ui(ai, a-i) - ui(ai’, a-i) = p(ai, a-i) - p(ai’, a-i)1, 3 6, 63, 5 3, 3Potential function:p(UL) = 0p(UR) = 3p(DL) = 2p(DR) = 0•Can you think of an algorithm for verifying whether a normal-form game is a potential game (i.e., for finding a potential function)?Potential games always have a pure-strategy equilibrium•Recall that ui(ai, a-i) - ui(ai’, a-i) = p(ai, a-i) - p(ai’, a-i)•Hence, let us simply choose argmaxa{p(a)}•For any alternative ai’, ui(ai’, a-i) - ui(a) = p(ai’, a-i) - p(a) ≤ 0, hence it is an equilibrium!•More generally, the set of pure-strategy Nash equilibria is exactly the set of local maxima of the potential function–Local maximum = no player can improve the potential function by herself•Easy algorithm for finding a pure-strategy equilibrium:–Start with any strategy profile–If a player is not best-responding, switch that player’s strategy to a better response (must increase potential)–Terminate when no player can improveEvery congestion game is a potential game!•Use potential p(a) = -Σr Σ1 ≤ i ≤ #(r, a) cr(i)–One interpretation: the sum of the utilities that the agents would have received if each agent were unaffected by all later agents •Why is this a correct potential function?•Suppose you change actions–You stop using some resources (R-), start using others (R+)•Change in your utility equals Σr in R- cr(#(r, a)) - Σr in R+ cr(#(r, a) + 1)•This is also the change in the potential function above•Conversely, every potential game can be modeled as a congestion game–Proof omittedGraphical games [Kearns et al. 01]•Note: all games in this lecture have something to do with graphs, but only the following are considered “graphical games”•Suppose players are vertices of a graph, and each agent is affected only by its neighbors’ actions (and own action)•E.g., physical neighbors on a road:1 2 3 45 6 7 8•Can write u2(a1, a2, a3, a6) rather than u2(a1, a2, a3, a4, a5, a6, a7, a8)–If each agent has two actions, a table requiring 24 = 16 numbers rather than 28 = 256 numbers•Graphical games can model any normal-form game (by using a fully connected graph)Action-graph games [Bhat & Leyton-Brown 04]•Now there is a vertex for every action that a player may take•E.g., action = where to sell hot dogsl1 l2 l3 l4l5 l6 l7 l8•Players’ can have distinct action sets, but they can overlap–E.g., perhaps some players cannot stand in every location–E.g., maybe player 1 lives on the right and can only make it to A1 = {l3, l4, l7, l8}; but player 2 has a car and can make it to any location•Your utility is a function of –Which vertex you choose,–How many other players choose your vertex,–For each neighbor of your vertex, how many players choose that neighborAny normal-form game can be expressed as an action-graph game•Make action sets disjoint,•Connect every action to every action by another playera11a12a13A1a21a23A2a31a32A3Action-graph games can capture the structure of graphical games•Omit edges between actions of players not connected in the graphical gamea11a12a13A1a21a23A2a31a32A3123•But, AGGs can capture more structure than that: e.g., things like:•“Player 1’s utility does not depend on what player 2 does given that player 1 plays a12 (context-specific independence)Computing expected utilities in AGGs[Jiang & Leyton-Brown AAAI06]•How do we compute the expected utility of playing a given action ai, given the other players’ mixed strategies σ-i?–Key step in many


View Full Document

Duke CPS 296.1 - Concise representations of games

Documents in this Course
Lecture

Lecture

18 pages

Lecture

Lecture

6 pages

Lecture

Lecture

13 pages

Lecture

Lecture

5 pages

Load more
Download Concise representations of games
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Concise representations of games and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Concise representations of games 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?