DOC PREVIEW
Berkeley ELENG 228A - Overview on Games in Networks

This preview shows page 1-2 out of 5 pages.

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

Unformatted text preview:

I Motivation for Applying Game Theory to NetworksII Examples of Two Person GamesIII Dominant Strategies and Nash EquilibriumsReferences1EE228a - Lecture 16 - Spring 2006Overview on Games in NetworksJean Walrand, scribed by Phoebus Chen (phoebusc AT eecs)AbstractThis lecture gives in overview on Game Theory and how it applies to Networks. Game theory is a method to study howto distribute controllers and algorithms and how these controllers and algorithms interact to result in global behaviors. Morespecifically, game theory can be used to look at contention amongst users at the physical, MAC, and transport layers, and alsoto study routing algorithms and pricing/service strategies between network providers. This lecture provides several examples ofcanonical two-person games, and introduce some basic concepts in game theory such as dominant strategies and Nash equilibriums.I. MOTIVATION FOR APPLYING GAME THEORY TO NETWORKSGame Theory was a mathematical framework developed in the field of economics to model the interaction of selfish agents withconflicting interests in a market. Competition in the market drives technological development and adoption of new technologies.The competition between network providers determines pricing, service choice, contracts, regulations, cooperation, mergers andacquisitions, and liability. For instance, in a voice network where two users are connected by a network bridging Verizon andAT&T, what are the incentives for Verizon to provide good service to AT&T customers? If a collaborative agreement is reachedbetween Verizon and AT&T, how should the profits be allocated? Another example is a scenario where many AT&T internet userswish to access Google’s website and services. Here, we ask what are the incentives for AT&T to provide good service to Google,and whether AT&T should be allowed to charge Google more for some services because Google traffic is consuming more AT&Tnetwork resources.Game Theory is also particularly suited to modeling communication networks because its model of the interaction betweenagents parallels the interaction of users in a communication network. The protocols for communication over a network representthe rules of a game and the goal of good protocol design is to create rules that maximize the utility, or well being, of all theusers. Examples of measures of utility would be the total throughput in the network, the fairness of bandwidth allocations amongstusers, or the maximum latency of all the end-to-end communication routes. Various networking layers – in particular, the physical,MAC, routing, and transport layers – are amenable to modeling as games.For instance in the physical layer, we can study power control in CDMA and spectrum allocation as a game between users.In CDMA power control, each user prefers to transmit at a maximum power to improve his capacity, but interference betweenusers means that increasing the power of one user means reducing the capacity of another user. This is analogous to speakingloudly in a noisy restaurant: if everyone speaks louder to hear their own conversations, the restaurant just becomes more noisy.Similarly, in spectrum allocation, all users prefer to use a wider spectrum, but increasing one’s capacity would mean a decreasedcapacity for another user.Games in the MAC layer involve congestion control and getting access to transmit over the network. For instance, in a carriersense multiple access medium such as WiFi, each user would like to get access to the channel more often, which means a userwould prefer to use a smaller backup window size. But again, if everyone uses a smaller backup window, there is more of achance for collisions and this may result in lower throughput for everyone. A similar situation arises with persistence in Alohanetworks. Another example of “gaming” the network concerns the implementation of priority classes in 802.11e. There is anincentive for a user to claim high priority for all traffic to get better throughput. But if all users do this, then it defeats the purposeof implementing priority levels in the protocol.The choice of routing paths can also be analyzed as a game between users. For instance, while a particular user may preferto route using the shortest path, if all users choose their shortest path the traffic may be routed through the same links in thenetwork, leading to congestion. Also, each user may prefer to route via the fastest path to decrease the latency of its own trafficbut if everyone routes via their fastest paths it may actually result in increased delay for everyone, again because of congestion.Yet another example is that users may prefer to duplicate their traffic across parallel paths to increase the reliability of theirend-to-end connection, but again everyone doing so may result in congestion and worse network reliability. Lastly, games canbe used to analyze the resulting global performance/behavior of“Hot Potato” routing schemes, where a network provider sendspackets off to a competitor’s network as soon as possible to reduce the consumption of resources in his own network.The same issues mentioned above also appear at the transport layer, making some aspects suitable for modeling as a game.For instance, in TCP, an individual user might want to increase his transmission window size and send packets at a higher rateover the network, but again if everyone does this network congestion will make everyone worse off. In schemes of allocatingbandwidth using proportional fairness, users place a bid for bandwidth by choosing an amount to pay per unit time, w, and receivein return a a flow x = w/p where p is a charge per unit flow. A strategic user r know that p is a function of his bid wrand thebids of other users. If r knows the bids w of other users, he may wish to change his bid to get a better price.In all these examples, game theory would help define protocols and design mechanisms to align the actions of selfish userswith actions that would help benefit the global community of users. That is, users need to have the right incentives to use networkresources in a manner that respects the needs of other users by not consuming all the network bandwidth, etc.2II. EXAMPLES OF TWO PERSON GAMESThis section presents some basic terminology and concepts in game theory in the context of three simple two-person games.These are the matching pennies game, the battle of the sexes, and the prisoners’ dilemma. We then look at a few


View Full Document

Berkeley ELENG 228A - Overview on Games in Networks

Documents in this Course
FAST TCP

FAST TCP

57 pages

Load more
Download Overview on Games in Networks
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 Overview on Games in Networks 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 Overview on Games in Networks 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?