Communication NetworksGames in Networks: OverviewMotivationExamples of GamesIn NetworksGames: Physical LayerGames: MACGames: RoutingGames: TransportGames: Between ProvidersKey ConceptsSlide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Key Concepts: Good StrategySlide 20Slide 21Slide 22Slide 23Communication NetworksA Second CourseJean WalrandDepartment of EECSUniversity of California at BerkeleyGames in Networks: Overview•Motivation•Examples of Game •In Networks•Key ConceptsMotivation•Decisions made by people (agents)•Selfish agents with conflicting interests•Markets (interactions of agents) influence technological development and adoption•Protocols limit or enable strategies•Design protocols to create suitable incentives•Pricing, service choice, contracts, regulations, cooperation, mergers and acquisitions, liability •Game theory models interactions of selfish agentsExamples of Games•Matching Pennies: •Alice and Bob both show a penny•If the faces match, Bob gives Alice $1.00•If the face do not match, Alice gives Bob $1.00•Battle of the Sexes:•Alice and Bob choose to go to the opera or football•They prefer to go together, but Alice loves opera and hates football; Bob loves football and hates opera•Prisoners’ Dilemma:•Alice and Bob are accused of a crime and are interrogated separately•If exactly one pleads guilty, that person gets 1 year and the other five years•If both plead guilty, they get 3 years; if none pleads guilty, they get 2 years.In Networks•Physical•MAC•Routing•Transport•Interactions between providersGames: Physical Layer•Being Loud in a Restaurant•You are heard better if you talk louder•Everybody ends up being very loud and upset by the noise•Power control in CDMA•Each user prefers to transmit at maximum power to improve his capacity•However a user’s increased power reduces the capacity of the other users because of increased interference•Spectrum allocation•Each user prefers a wider spectrum•However, this decreases the capacity of the other usersGames: MAC •Backup Window in WiFi•Each user prefers a smaller backup window size•However, this reduces the throughput of others•Persistence in Aloha•Similar•Priority Class in 11e•Incentive is to claim high priority for all traffic•However, this reduces the quality …Games: Routing•Shortest Path•Users may prefer shortest path•However, this my lead to congested paths•Fastest Paths•Users may prefer fastest path•This may increase average delay•Duplicated Paths•Users may prefer to duplicate their traffic across parallel paths•This may make everybody worse off•Hot potato routing•Send packets off to competitor’s network asapGames: Transport•TCP•Users might want to be more aggressive•If everyone does it, everybody is worse off•Proportional Fairness•Normal: user gets x = w/p•Strategic: user knows p = w + other weights•This leads strategic users to change their bids….Games: Between Providers•Interactions between network providers•User ---[AT&T]----[Verizon]--- User•What are the incentives for Verizon to provide good service to AT&T’s clients?•How should one allocate profits?•User ---[AT&T]---[Google]•What are the incentives for AT&T to provide good service to Google?•Should AT&T be allowed to charge Google more for some services?Key Concepts•Game:•Multiple Agents•Agents act in some order, possibly multiple times•When she acts, agent knows some information about previous actions, possibly incomplete•Ultimate reward of each agent depends on the actions of all the agents•Agents may have incomplete information about each other and the game evolution may be random•The choice of the actions may be randomizedKey Concepts•Game Example: Matching PenniesH TH 1, -1 -1, 1T -1, 1 1, -1Actions of AliceActions of BobReward of AliceReward of Bob•One-Shot Game•Both players play simultaneously•Each player knows both reward functions•One-Shot Game•Both players play simultaneously•Each player knows both reward functionsKey Concepts•Game Example: Battle of the Sexes•One-Shot Game•Both players play simultaneously•Each player knows both reward functions•One-Shot Game•Both players play simultaneously•Each player knows both reward functionsO FO 4, 1 2, 2F 0, 0 1, 4O = OperaF = FootballKey Concepts•Game Example: Prisoners’ Dilemma•One-Shot Game•Both players play simultaneously•Each player knows both reward functions•One-Shot Game•Both players play simultaneously•Each player knows both reward functionsG = plead guiltyNG = plead not guiltyG NGG 3, 3 1, 5NG 5, 1 2, 2Key Concepts•Game Example: Dynamic•2-player, 3-step game: P1, P2, P1•P1 does not see the action of P2•Each player knows both reward functions•2-player, 3-step game: P1, P2, P1•P1 does not see the action of P2•Each player knows both reward functionsKey Concepts•Game Example: Cournot Duopoly•One-shot game•Continuous action space•Each player knows both reward functions•One-shot game•Continuous action space•Each player knows both reward functionsTwo firms produce quantity q1 and q2 of a productThe price is A – q1 – q2For i = 1, 2 the profit of firm i is qi(A – q1 – q2) - CqiTwo firms produce quantity q1 and q2 of a productThe price is A – q1 – q2For i = 1, 2 the profit of firm i is qi(A – q1 – q2) - CqiKey Concepts•Game Example: Bayesian•One-shot game•Continuous action space•Each player has an incomplete knowledge of some reward functions•One-shot game•Continuous action space•Each player has an incomplete knowledge of some reward functionsTwo firms produce quantity q1 and q2 of a productThe price is A – q1 – q2For i = 1, 2, the profit of firm i is qi(A – q1 – q2) – CiqiFor i = 1, 2, firm i knows Ci but only knows the distribution of C2 - iTwo firms produce quantity q1 and q2 of a productThe price is A – q1 – q2For i = 1, 2, the profit of firm i is qi(A – q1 – q2) – CiqiFor i = 1, 2, firm i knows Ci but only knows the distribution of C2 - iKey Concepts•Strategy:•Rule that specifies how to act at any time, as a function (possibly randomized) of the information available•Good Strategy?•Dominant•Iterated deletion of dominated strategies•Nash Equilibrium •Other concepts … later.Key Concepts: Good Strategy•Dominant Strategy:•Best, no matter what the other players do•Example: Being loud in a
View Full Document
Unlocking...