Introduction to game theoryIntroduction to game theoryJie GaoComputer Science DepartmentStony Brook UniversityGame theoryGame 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 CSGame 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 paradigmNew algorithm design paradigm• Adversarial.– Worst-case analysis.– Online algorithms.– Cryptography.• Obedient.– Distributed systems.• Strategic.– Agents have their own objectives.– Rational behaviors in a competitive setting.This classThis class• Introduction to games• Nash equilibrium, price of anarchy, price of stability• Best response strategy• Potential game• Load balancing game• Selfish routing• Network designPrisonerPrisoner’’s dilemmas dilemma• 2 criminals: cooperate with each other, or defect/tell the truth to the police.• Payoff function:0, 010, -10D-10, 105, 5CDCMatching penniesMatching pennies• 2 guys put out pennies with head or tail. One wants the pennies to match. The other wants them not to match.-1, 11, -1T1, -1-1, 1HTHBattle of SexesBattle 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.1, 20, 0S0, 02, 1BSBNash equilibriumNash 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 benefitSocial benefit• Mixed strategy: choose option j with probability pj. Σjpj=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 Main questions about Nash equilibriumequilibrium• 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 balancingFirst game: load balancingLoad balancing gameLoad 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 ipj.• 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 strategyBest 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 Load balancing game has a pure NashNash• 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 - pjLk+ pjLoad balancing game has a pure Load balancing game has a pure NashNash• 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?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≤ ΣkLk/m+ pj.– In opt solution, j is assigned to some server, so C(A*) ≥ pj. – ΣkLk is the total processing time for all assignments, so the best algorithm is to evenly partition them among m servers. C(A*) ≥ ΣkLk /m = Σkpk/m. – C(A) = Lj≤ ΣkLk/m+ pj = Σkpk/m + pj≤ C(A*) +C(A*).Summary of load balancing gameSummary of load balancing game• Pure Nash exists.– Why? The best response strategy does not lead to a loop.• Max load of a Nash is at most twice worse.– Use special structure of the problem.• How to find a Nash?– Run the best response strategy, might be slow.Second game: selfish routingSecond game: selfish routingSelfish routingSelfish routing• 1 unit of (splittable) traffic from s to t. Delay is proportional to congestion C(x). • What is the Nash equilibrium?s tC(x)=xC(x)=1All traffic go through the top edge, with delay 1.Selfish routingSelfish routing• Social optimum = sum of delay of all users. • Can social optimum do better?s tC(x)=xC(x)=1½ traffic go through the top edge, with delay ½.½ traffic go through the top edge, with delay 1.Social optimum = ¾.NonNon--linear selfish routinglinear selfish routing• Nash equilibrium: all traffic go through top edge, with delay 1.• Can social optimal do better?s tC(x)=xdC(x)=11-ε traffic go through the top edge, with delay (1-ε)d.ε traffic go through the top edge, with delay 1.Social optimum = (1-ε)d +ε ≅ 0.BraessBraess’’s s ParadoxParadoxInitial networkDelay=1.5BraessBraess’’s s ParadoxParadoxInitial networkDelay=1.5Augmented networkBraessBraess’’s s ParadoxParadoxInitial networkDelay=1.5Augmented networkDelay=2New highway made everyone worse!Selfish routingSelfish routing• Graph G, and k source-sink pairs, siand 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 flowNash
View Full Document