Economic Modeling In Networking: A Primer

5m ago
30 Views
0 Downloads
669.15 KB
124 Pages
Transcription

RFoundations and Trends inNetworkingVol. 6, No. 3 (2011) 165–286c 2013 R. A. Berry and R. Johari DOI: 10.1561/1300000011Economic Modeling in Networking: A PrimerBy Randall A. Berry and Ramesh JohariContents1 Introduction1661.1169Endnotes2 99UtilityEfficiency and Pareto OptimalityFairnessQuasilinear Environments: The Role of CurrencyPrice EquilibriaInformationEndnotes3 20227230234Static GamesDominant StrategiesNash EquilibriaMixed StrategiesBayesian GamesRepeated GamesEfficiency LossEndnotes

4 Externalities2364.14.24.34.4237241245248Basic DefinitionsInformational ExternalitiesBargainingEndnotes5 egulationPigovian TaxesThe Vickrey-Clarke-Groves MechanismsAuctionsThe Principal-Agent ProblemEndnotesAcknowledgments283References284

RFoundations and Trends inNetworkingVol. 6, No. 3 (2011) 165–286c 2013 R. A. Berry and R. Johari DOI: 10.1561/1300000011Economic Modeling in Networking: A PrimerRandall A. Berry1 and Ramesh Johari212Electrical Engineering and Computer Science, Northwestern University,Evanston, IL 60208, United States, [email protected] Science and Engineering, Stanford University, Stanford,CA 94305, United States, [email protected] recent years, engineers have been increasingly called upon to havebasic skills in economic modeling and game theory at their disposal fortwo related reasons. First, the economics of networks has a significanteffect on the adoption and creation of network innovations, and second, and perhaps more importantly, engineered networks serve as theplatform for many of our basic economic interactions today. This monograph aims to provide engineering students who have a basic trainingin economic modeling and game theory an understanding of where andwhen game theoretic models are employed, the assumptions underpinning key models, and conceptual insights that are broadly applicable.

1IntroductionIn recent years, network engineers have been increasingly called uponto have basic skills in economic modeling and game theory at their disposal. Economics chiefly concerns itself with the “production, distribution, and consumption of goods and services” (per Merriam–Webster’sDictionary); game theory provides the theoretical foundations on whichmany economic models are built. Recent history has cast economics atthe forefront of network engineering in particular in two ways. First,the economics of networks has a significant effect on the adoption andcreation of network innovations (e.g., regulation of wireless spectrum —or the lack thereof — was a significant catalyst for the development ofWiFi technologies). Second, and perhaps more importantly, engineerednetworks serve as the platform for many of our most basic economicinteractions today. Despite this collision of economics and engineering, our own observation is that the typical networking student doesnot garner economic training until later in their graduate career — ifat all.Given the two facts in the previous paragraph, our position is thatbasic economic understanding is a critical tool in the arsenal of themodern student studying networks. Accordingly, this text is targeted166

167at providing a primer in economic modeling and game theory for suchstudents in engineering, operations research, or computer science. Ourfocus is on providing a grounding for the basics, and particularly anunderstanding of where and when economic models are employed; theassumptions underpinning key models; and conceptual insights thatare broadly applicable. We designed this monograph to be less of amathematical or computational “how-to” guide to economic theory —there are innumerable textbooks available on the subject that addressthat requirement much more effectively. Rather, we felt a significantneed to answer the following types of questions:(1) What is the difference between efficiency and fairness?(2) What assumptions lead to the result that markets are efficient?(3) When is a game theoretic model appropriate?(4) When is Nash equilibrium a reasonable solution concept?(5) Why is one auction format preferable to another?More than just working with economic models, it is important for engineering students to be able to take a critical eye to such models as well.Our monograph is intended to help students develop that critical eye.In this sense, we view this monograph as a complement to a good introductory textbook or course on microeconomics or game theory; somereferences are provided in the endnotes to the introduction.As a more specific example of the type of conceptual grounding weare after, we begin by noting that one can identify two distinct butinterrelated approaches to the use of economic methods in the engineering sciences. First, we observe that in many instances economicmodels are used as a semantic device to aid in modeling an engineeringproblem. In this setting, the system under consideration is typicallydesigned and implemented holistically; however, decentralized implementation requires that we understand the output of many interactingsubcomponents. In some instances, viewing this interaction as a gamecan yield useful insight. In the second approach, game theoretic modelsare used as an economic device to explicitly capture incentives of arange of rational, self-interested parties. Here game theoretic modelsare used to predict the outcome of their interaction, and in some cases

168Introductiondesign mechanisms to control that interaction. In contrast to the semantic approach, in the economic approach many aspects of the game aredictated by practical realities of the economic problem considered.In the semantic approach, the usual goal is to leverage gametheoretic techniques to design an optimal decentralized system. Congestion control is commonly cited as an example of this approach innetworking. Here end-system controllers determine sending rates inresponse to congestion signals from the network; these signals can rangefrom simple (packet loss due to buffer overflow) to complex (activequeue management, or AQM, algorithms to determine explicit congestion notification, or ECN, marks). These algorithms can be naturallyviewed in terms of a market, where the “buyers” are the end systems, and the “sellers” are the capacitated links of the network. Pricesmediate supply and demand, and under certain conditions a marketequilibrium exists and is efficient. Of course, the notion of “buying”and “selling” is purely semantic; however, it serves as a valuable (andpowerful) guide that allows us to bring economic tools to bear on anengineering problem.In the economic approach, by contrast, many features of the gameare dictated by practical realities of the economic problem considered.A timely example is provided in recent studies of peer-to-peer (P2P)filesharing. Here there is a fundamental tension between the fact thata well-functioning filesharing system needs users to contribute content;but in the absence of any other incentive, users generally derive maximum benefit from downloading content, rather than contributing it.Note that in this setting the incentives are real: they are the incentivesof the users contributing to the system, and any game theoretic modelmust start from this basic observation. At the same time, we emphasize that this approach can still involve an element of design: often weare interested in designing protocols or mechanisms that can providethe right incentives to self-interested agents. In that case, the economicapproach shares much in common with the semantic approach to gametheoretic modeling.This kind of distinction may not be immediately evident to thenetwork engineering student taking an economic modeling class for thefirst time. However, we believe it is a first order concern in formulating

1.1 Endnotes169any economic model in a networking setting. As we will see in theremainder of the text, it is a distinction that informs many of theconcepts we present.The remainder of the monograph is organized as follows. InChapter 2, we introduce the basics of welfare analysis — the economic analysis of efficient allocation of resources among competinguses. In Chapter 3, we discuss game theoretic foundations, including arange of equilibrium concepts. In Chapter 4, we discuss externalities —the (positive or negative) impact of one individual’s actions on others.In Chapter 5, we discuss mechanism design — the design of economicenvironments (such as markets) that yield desirable outcomes.A note on organization. Every section of every chapter is organizedin an identical manner. Each section begins with a preamble setting thestage without technical details. The subsections then progress throughMethodology (describing the technical approach); Examples (illustratingthe methodology); and Discussion (describing key conceptual issuesrelated to the section topic). The discussion subsections in particularplay a significant role in our book: they delve beyond the “how” ofeconomic modeling and game theory, and deal largely with the “why.”Each chapter concludes with a section of Endnotes that lists severalreferences for the material discussed in the chapter. The literature oneconomics and game theory is vast. We have not tried to provide acomprehensive bibliography, but rather focus on a few key referencesto provide interested readers with a starting point for exploring thematerial in greater depth.A note on terminology. Throughout the monograph, we refer toindividuals as “players,” “agents,” or “users”; we use the terms interchangeably.1.1EndnotesFor more background on game theory we refer the readers to one ofmany books available on this subject such as Gibbons [12], Fudenberg and Tirole [11], Osborne and Rubinstein [32], Myerson [28], andOwen [33]. Also, Mas–Colell et al. [24] provides a good introduction to game theory as well many other aspects of microeconomics.

170IntroductionIn theoretical computer science, algorithmic questions related to gametheory have been increasingly studied; Nisan et al. [31] providesan excellent overview of this work. In communication networking,Walrand [42] is a good tutorial on economic issues relevant to communication networks, including situations where game theoretic modelingis used.

2WelfareIn the context of resource allocation, welfare analysis uses an economicapproach to study the overall benefit (or welfare) generated under alternative mechanisms for allocation of scarce resources. For our purposes,welfare analysis serves as a benchmark approach to resource allocationin engineered systems, and in particular allows us to introduce severalessential concepts in economic modeling. We begin in Section 2.1 byintroducing the notion of utility, the value that is derived by an individual from consumption of resources. Next, in Section 2.2, we discussefficiency and define Pareto optimality, a way to measure the welfareof allocation choices. In Section 2.3, we discuss fairness considerations,and in particular how different notions of fairness lead to differentways of choosing between Pareto optimal outcomes. In Section 2.4, weintroduce a particularly useful model of utility, where all market participants measure their utilities in a common unit of currency; these areknown as quasilinear environments. In Section 2.5, we discuss the roleof prices in mediating resource allocation through markets, and connectprice equilibria to efficient market outcomes — as well as discuss somereasons why efficiency may fail to be achieved in markets. Finally, inSection 2.6, we briefly discuss the role of information in markets, and inparticular discuss the welfare consequences of information asymmetries.171

172Welfare2.1UtilityUtility provides a basic means of representing an individual’s preferences for consumption of different allocations of goods or services.Utility is a central concept in the analysis of efficiency of economicsystems, because it provides a metric with which to measure the satisfaction of an individual user. Welfare analysis is ultimately concernedwith the utility levels generated by resource allocations across the system as a whole, but clearly a major building block in this exercise is tocharacterize the value of resources to a single user.2.1.1MethodologySince utility functions are meant to capture an agent’s preferences, westart by defining a preference relation for an agent. Suppose that thereis a set J of resources available in the system, and let xr (xjr , j J)denote a bundle of these resources allocated to user r. A preferencerelation, , is a binary relation used to model a user’s preferences fordifferent possible bundles, so that if xr yr , then user r finds xr atleast as “good” as yr .“Utility” refers to an assignment of value to each possible bundlethat is aligned with an agent’s preferences. Formally, a preference relation, , is represented by a utility function, Ur (xr ), if Ur (xr ) Ur (yr )whenever xr yr , i.e., if a larger utility indicates that a bundle is morepreferred by an agent. In some examples, the user’s preferences and sotheir utility may depend only on a lower-dimensional function of theresource bundle; for example, in the case of resource allocation in networks, a user’s utility may be a function only of the total rate allocationthey receive. In these cases we adapt our notation accordingly.There are two features of utility functions that are natural toconsider in our context.Monotonicity. We only consider utility functions that are nondecreasing, i.e., if every component of the allocated resource vector weaklyincreases, then the utility weakly increases as well. This means thatevery individual prefers more resources to less resources. A key implicitreason that monotonicity is plausible is the notion of free disposal:that excess resources can always be “disposed of” without any cost or

2.1 Utility173penalty. With free disposal,