Introduction to game theory Jie Gao Computer Science Department Stony Brook University Game theory How selfish agents interact Chess poker both parties want to win Traditionally studied in economics sociology etc Model the physical world How do selfish agents behave how does cooperation appear Game theory in CS Selfish agents computers ISPs cell phones Context Internet ad hoc networks Decentralized ownership and operation Passive side study the behaviors of selfish parties Nash equilibrium I e stable state Active side design mechanisms that motivate selfish agents to act as desired Auction pricing New algorithm design paradigm Adversarial Obedient Worst case analysis Online algorithms Cryptography Distributed systems Strategic Agents have their own objectives Rational behaviors in a competitive setting This class Introduction to games Nash equilibrium price of anarchy price of stability Best response strategy Potential game Load balancing game Selfish routing Network design Prisoner s dilemma 2 criminals cooperate with each other or defect tell the truth to the police Payoff function C D C D 5 5 10 10 10 10 0 0 Matching pennies 2 guys put out pennies with head or tail One wants the pennies to match The other wants them not to match H T H 1 1 1 1 T 1 1 1 1 Battle of Sexes A boy and a girl want to go to either a softball or a baseball game The girl prefers softball and the boy prefers baseball But they prefer to be with each other B S B 2 1 0 0 S 0 0 1 2 Nash equilibrium Pure strategy choose one of the options Nash equilibrium if no player will be better off by switching to another strategy provided that the other users stick to their current strategies Nash equilibrium is a stable state Pure Nash equilibrium may not exist nor unique Social benefit Mixed strategy choose option j with probability pj j pj 1 Mixed Nash equilibrium always exists Proved by Nash The social value the sum of the payoffs In the prisoner s dilemma game the Nash equilibrium does not give the maximum social value the price of non cooperation Main questions about Nash equilibrium Does the game have a pure Nash equilibrium Is it unique How does the social value of a Nash equilibrium compare to the best possible outcome with cooperation and central control The price of anarchy ratio of the worst Nash compared with the social optimum The price of stability ratio of the best Nash compared with the social optimum How to compute a Nash Is it hard First game load balancing Load balancing game There are m servers n jobs Job j has load pj The response time of server i is proportional to its load Lj j assigned to i pj Each job wants to be assigned to the server that minimizes its response time Nash equilibrium an assignment such that job j is assigned to server i and for any other server k Lj Lk pj Does a pure Nash exist Best response strategy Start with an arbitrary state Each node chooses the best strategy that maximizes its own payoff given the current choices of the others Use the best response strategy to argue the existence of a Nash Find some quantity that monotonically improves Argue that after a finite number of steps this process stops A Nash is a local optimum Load balancing game has a pure Nash Order the servers with decreasing load i e the decreasing response time L1 L2 Lm Job j moves from server i to k Lk pj Li L1 Li Lk Lm Li pj Lk pj Load balancing game has a pure Nash Reorder the servers the load sequence decreases There are a finite number of possibly exponential assignments So best response switching terminates although can be rather slow How bad is a Nash Claim the max load of a Nash equilibrium A is within twice the max load of the optimum C A 2 minA C A Proof Let j be a job assigned to the max loaded server i Lj Lk pj for all other server k Sum over all servers Lj k Lk m pj In opt solution j is assigned to some server so C A pj k Lk is the total processing time for all assignments so the best algorithm is to evenly partition them among m servers C A k Lk m k pk m C A Lj k Lk m pj k pk m pj C A C A Summary of load balancing game Pure Nash exists Max load of a Nash is at most twice worse Why The best response strategy does not lead to a loop Use special structure of the problem How to find a Nash Run the best response strategy might be slow Second game selfish routing Selfish routing 1 unit of splittable traffic from s to t Delay is proportional to congestion C x C x x s C x 1 t What is the Nash equilibrium All traffic go through the top edge with delay 1 Selfish routing Social optimum sum of delay of all users Can social optimum do better C x x s C x 1 t traffic go through the top edge with delay traffic go through the top edge with delay 1 Social optimum Non linear selfish routing Nash equilibrium all traffic go through top edge with delay 1 Can social optimal do better C x xd s C x 1 t 1 traffic go through the top edge with delay 1 d traffic go through the top edge with delay 1 Social optimum 1 d 0 Braess s Paradox Initial network Delay 1 5 Braess s Paradox Initial network Delay 1 5 Augmented network Braess s Paradox Initial network Augmented network Delay 1 5 Delay 2 New highway made everyone worse Selfish routing Graph G and k source sink pairs si and ti The traffic on edge e is f e Delay function d f e Each pairs minimizes its delay Traffic is splittable The cost of a flow is the average delay Nash flow A flow is at Nash equilibrium if all flow are routed along minimum latency paths given the current congestion condition Nash flows do arise in distributed shortest path routing protocols e g BGP Price of anarchy Nash flow do not minimize the global delay Lack of coordination leads to inefficiency How inefficient are Nash flows in realistic network Hope it is close to optimum If so we can be lazy But this is not true C x xd s C x 1 t 1 traffic go through the top edge with delay 1 d traffic go through the top edge with delay 1 Social optimum 1 d 0 Approaches Approach 1 better hardware Total cost of Nash flow at rate r is less than the optimal cost at rate 2r Approach 2 restrict the congestion function If the latency is linear function ax b the cost of Nash flow is less than 4 3 opt cost Third game network design Selfish network design Slide made by Roughgarden How do they share the cost If nodes can take free ride …