Games on Networks Introduction and Research Example Jessica L Heier Prepared for ISYE 6230 Joint work with Dr zlem Ergun and Dr Julie Swann April 24 2008 Outline Introduction to Games on Networks Network Congestion Games Results on a Disaster Response Problem Modeling as a network congestion game 1 Games on Networks Context Traffic on congested highways Traffic on computer networks Production by competing firms using common resources Common Theme Decision makers players use common resources links Cost to each player depends on the number of players using the same resources Games on Networks Braess Paradox Interaction of selfish behavior with network properties may not be intuitive c x x v s c x 1 t c x 1 w c x x Selfish flow splits equally each player s cost 3 2 c x x v c x 1 c x 0 s c x 1 w t c x x All flow uses s v w t each player s cost 2 2 Games on Networks Definitions Nonatomic large number of players each control infinitesimal amount of traffic impact of single player negligible Atomic each player controls finite fraction of traffic individual impact measurable Splittable individual can choose multiple routes Unsplittable individual must route all of her traffic on a single route Symmetric options available to all players identical Asymmetric players have different route options Network Congestion Games Input Set of n players Set of resources E e1 e2 em Action sets Si 2E for each player i Delay function on resource e is given by de j where j is number of players using e Game is atomic because players make discrete choices 3 Network Congestion Games States of Game Each player chooses a subset of resources from his action set si Si State is determined by all players choices s s1 sn Cost to Players Let fs e i e si THINK number of players using resource e in state s Then ci s e si de fs e In words the cost of state s to player i is the sum of the delays on each of the resources that i uses and those delays depend on the total number of customers using those resources Network Congestion Games Nash Equilibria Definition State s is a NE if for all i we have ci s1 si sn ci s1 si sn Player i cannot improve his cost by changing ONLY his own choice Theorem Pure strategy NE guaranteed to exist Due to Rosenthal 1973 4 Network Congestion Games Example What are the pure Nash equilibria in this network ANSWER 0 0 x 0 t 0 x Any state of the game in which 2 players choose one of the expensive arcs 1 player chooses the other 0 0 Disaster Response Logistics challenges Limited planning opportunity Damaged infrastructure Constrained resources Urgency But why game theory 5 Decentralization in Disaster Response Households choosing evacuation routes Evacuees deciding where to seek shelter Individuals traveling to supply distribution locations Individuals optimize own objectives but decisions impact entire system Photo Credits Top J Andrews Lufkin Daily News Bottom E Edahl FEMA Our Problem There exist facilities from which individuals will pick up emergency supplies Affected individuals choose from among the facilities which one to visit considering Travel time Travel time plus congestion System cost travel times plus facility congestion of all users 6 An Example A dA1 Travel Time 1 B Facility Congestion Number of Customers y1 C t y2 2 D An Example Facility Assignments A B dA1 1 y1 C t y2 Centralized Solution Congestion Facility 1 2 2 4 Facility 2 2 2 4 2 D 7 An Example Facility Assignments A dA1 B 1 y1 C t y2 Centralized Solution Congestion Facility 1 2 2 4 Facility 2 2 2 4 2 D Decentralized Congestion Solution Facility 1 3 3 9 Facility 2 1 1 1 Definitions Centralized System A decision maker determines the actions of all system users to minimize a system wide objective Decentralized System Individual users make decisions to optimize selfish objectives impacting other users and the system wide performance Nash User Equilibrium A solution in which no individual can improve his objective by unilaterally changing his choice Price of Anarchy Cost of Worst Nash Equilibrium Cost of Central Optimal Solution Price of Stability Cost of Best Nash Equilibrium Cost of Central Optimal Solution 8 Research Questions Do Nash equilibria exist How does decentralized system performance compare to central optimal control How can information be used to improve performance Literature Congestion game implies pure Nash equilibrium is guaranteed to exist Rosenthal 1973 Finding Nash equilibrium Fabrikant et al 2004 Price of anarchy PLS complete for asymmetric network congestion games and non network congestion games Polynomial for symmetric network congestion games 4 3 for splittable flow and linear latencies Roughgarden and Tardos 2002 for unsplittable flow and general latencies same source 2 5 for unsplittable flow and linear latencies Awerbuch et al 2005 Improving price of anarchy e g Roughgarden 2007 pricing capacity augmentation and central control 9 Our Contribution Unsplittable flow Asymmetric network congestion game Each individual must choose exactly one facility Paths are not identical for all individuals Information to improve system performance Centralized Problem Central Optimal Solution The Benchmark n d x xij ij ij i 1 j 1 j 1 i 1 n Minimize m m Distance m s t j 1 Congestion x ij 1 x ij 0 1 2 for all i Each Individual Served for all i j Binary Variables Assign Individual i to Facility j Convex Cost Flow Problem Polynomially solvable e g with reduction to min cost flow and capacity scaling 10 Decentralized Problem with Information Consider three scenarios No Information Full Information Each user minimizes his own travel time All other users choices fixed and known User minimizes his own travel time plus congestion Partial Information Central decision maker provides information to influence individuals choices No Information Problem No Information Case The Individual s Problem Minimize travel time arg min d ij j Trivial to find simultaneous solution for all individuals How much does individuals myopic behavior impact the system Network Where No Information Performs Poorly 11 Price of Anarchy No Information Theorem 1 The price of anarchy in the no information case is O m the number of facilities Proof Sketch For n customers and m facilities 2 Decentralized Cost n D 1 2 Central Optimal Cost n D m d d Our Contribution Unsplittable flow 9 Price of anarchy for no information is not a constant increases with m Asymmetric network congestion game Paths are not identical for all individuals Information to improve