DOC PREVIEW
SBU CSE 590 - Introduction to game theory

This preview shows page 1-2-3-24-25-26-27-48-49-50 out of 50 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 50 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 50 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 50 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 50 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 50 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 50 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 50 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 50 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 50 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 50 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 50 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

SBU CSE 590 - Introduction to game theory

Download Introduction to game theory
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 Introduction to game theory 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 Introduction to game theory 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?