Pin34-christin.dvi

Near Rationality and Competitive Equilibria in Networked
christin@sims.berkeley.edu jensg@sims.berkeley.edu chuang@sims.berkeley.edu School of Information Management and Systems ABSTRACT
in considering network participants as selfish [30] or competing[29] entities. For instance, in an effort to discourage free-riding, A growing body of literature in networked systems research relieson game theory and mechanism design to model and address the some deployed peer-to-peer systems such as KaZaA or BitTorrent potential lack of cooperation between self-interested users. Most [9] rely on simple incentive mechanisms. More generally, as sum- game-theoretic models applied to system research only describe marized in [13, 26, 30], a number of recent research efforts have competitive equilibria in terms of pure Nash equilibria, that is, a been applying concepts from game theory and mechanism designto networked systems in an effort to align the incentives of each situation where the strategy of each user is deterministic, and is her (self-interested) user with the goal of maximizing the overall sys- best response to the strategies of all the other users. However, theassumptions necessary for a pure Nash equilibrium to hold may be too stringent for practical systems. Using three case studies on net- A cornerstone of game theory and mechanism design is the no- work formation, computer security, and TCP congestion control, tion of competitive equilibrium, which is used to predict user be- we outline the limits of game-theoretic models relying on Nash havior and infer the outcome of a competitive game. As discussedin [26], the concept of Nash equilibrium is predominantly used in equilibria, and we argue that considering competitive equilibria ofa more general form helps in assessing the accuracy of a game the- system research to characterize user behavior. Assuming each user oretic model, and can even help in reconciling predictions from obtains a utility dependent on the strategy she adopts, a Nash equi- game-theoretic models with empirically observed behavior.
librium is defined as a set of strategies from which no user willingto maximize her own utility has any incentive to deviate [25].
While Nash equilibria are a very powerful tool for predicting Categories and Subject Descriptors
outcomes in competitive environments, their application to system C.2 [Computer Systems Organization]: Computer-Communication
design generally relies on a few assumptions, notably, that (1) each participant is infallible (i.e., perfectly rational), and that (2) eachuser has perfect knowledge of the structure of the game, includ- General Terms
ing strategies available to every other participant and their asso-ciated utilities. There seems to be a class of problems for which these assumptions may be too restrictive, for instance, characteriz-ing competitive equilibria in systems where participants have lim- Keywords
ited knowledge of the state of the rest of the network.
Distributed systems, Game theory, Competitive equilibria, Model- As a practical example of the potential limits of a game theoreti- cal analysis of a networked system solely based on Nash equilibria,one can argue that, in the case of a peer-to-peer file-sharing system INTRODUCTION
that does not provide incentives for users to share, the unique Nashequilibrium leads to the “tragedy of the commons [18],” that is, a Empirical evidence of phenomena such as free-riding in peer-to- situation where users do not share anything to minimize the cost peer systems [1] or unfairness in ad-hoc networks [19] challenges they incur, thereby leading the entire system to collapse. The mere the traditional system design assumption that all users of a network fact that, in practice, some users are sharing files, even in peer-to- are able and willing to cooperate for the greater good of the commu- peer systems that do not rely on incentive mechanisms, hints that a nity. Hence, system architects have become increasingly interested Nash equilibrium is not actually reached.
The argument that Nash equilibria may be too restrictive to char- acterize networked systems is not entirely new. In [14], Friedmanand Shenker notably argued that equilibria resulting from learn- Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are ing behaviors were a tool better suited for characterizing how net- not made or distributed for profit or commercial advantage and that copies work users share network resources than Nash equilibria. In this bear this notice and the full citation on the first page. To copy otherwise, to paper, we take a quite different stand, by advocating to consider republish, to post on servers or to redistribute to lists, requires prior specific competitive equilibria of a slightly more general form than pure Nash equilibria. More precisely, we argue that using simple exten- SIGCOMM’04 Workshops, Aug. 30+Sept. 3, 2004, Portland, Oregon, USA.
sions of pure Nash equilibria (1) helps to assess the robustness of a Copyright 2004 ACM 1-58113-942-X/04/0008 .$5.00.
game-theoretic model to small deviations from expected behavior, with a Nash prediction of a game but always contains a small er- thereby providing insight in the accuracy of the model, and (2) may ror. She is playing in an auction with an asymmetry between the help reconcile empirical observations with analytical modeling.
expected cost of overshooting and undershooting the Nash solu- We illustrate our point by presenting three case studies, on net- tion. If overshooting is less costly, the player’s strategy will most work formation, security, and TCP congestion control, where out- likely contain a small upward bias. If a substantial part of the other comes predicted by Nash equilibria are not entirely correlated by players shares this marginal bias the outcome of the auction can empirical observations. In each case study, we investigate if and be surprisingly far away from a Nash prediction [15]. Similarly, how more general forms of competitive equilibria can be used to in a sealed-bid auction the Nash equilibrium outcome predicts that better describe observed behavior, or if, on the other hand, the a player with a lower valuation will only sometimes win the auc- tioned good. However, this outcome is more likely if players share The remainder of this paper is organized as follows. In Section 2, small imperfections in the execution of their Nash strategies [21].
we provide some background by formally discussing the concept Such systematic and non-systematic deviations and their out- of Nash equilibrium and its extensions or potential alternatives. In comes have been motivation to formulate more generalized models Section 3, we present our case studies. Finally, in Section 4, we of strategic behavior that include the notion of the Nash equilib- discuss our findings, outline a possible agenda for future research, rium as a special case. In particular, to relax the assumption of per- and draw conclusions from our observations.
fect rationality required by the concept of Nash equilibrium, somehave introduced the concept of bounded rationality. Players that BACKGROUND
are bounded rational are not necessarily picking the best strategyavailable across the entire decision space, but instead are allowed We consider strategic interactions (called games) of the follow- to make small errors on a number of levels, such as the evaluation ing simple form: the individual decision-makers (also called play- of the payoffs associated with a strategy, the assessment of the best ers) of a game simultaneously choose actions that are derived from available strategy, or the execution of a specific strategy.
their available strategies. The players will receive payoffs that de- Some techniques to model bounded rationality introduce (possi- pend on the combination of the actions chosen by each player.
bly small) amounts of noise into the decision-making process. As More precisely, consider a set N = {1, ., n} of players. De- an example, the noisy introspection model [16] relies on (possi- note as Si the set of pure (i.e., deterministic) strategies available to bly many) layers of speculation on the beliefs about other players’ player i, and denote as si an arbitrary member of i’s strategy set. A beliefs. When all beliefs are perfectly correct, adding layers of probability distribution over pure strategies is called a mixed strat- speculation can only converge to a Nash equilibrium. However, the egy σi. Accordingly, the set of mixed strategies for each player, Σi, authors of [16] show that, by including some small (noisy) uncer- contains the set of pure strategies, Si, as degenerate cases. Each tainty in the conjectures about other players beliefs, the game can player’s randomization is statistically independent of those of the produce outcomes significantly different from a Nash equilibrium.
other players. Then, ui represents player i’s payoff (or utility) func- Another model of equilibrium with bounded rationality, called tion: ui(σi, σ−i) is the payoff to player i given her strategy (σi) Quantal Response Equilibrium, or QRE [23], has been used to and the other players’ strategies (summarized as σ−i). An n-player characterize equilibria in games where users make errors on the game can then be described as G = {N; Σi, Σ−i; ui, u−i}.
computation of the payoffs associated with a given strategy. Given Players are in a Nash equilibrium if a change in strategies by any two strategies and their associated payoffs (u1, u2), with u1 > one of them would lead that player to obtain a lower utility than u2, an a priori rational player may choose the strategy yielding if she remained with her current strategy [25]. Formally, we can u2 if she makes errors (ε1, ε2) in the computation of the pay- offs (u1, u2) such that u1 + ε1 < u2 + ε2. McFadden showedthat, in such a context, one could express the probability of choos- DEFINITION 1. A vector of mixed strategies σ∗ = (σ∗1, ., σ∗n) ∈ ing the strategy yielding u1 as a power function Pr(choose 1) = Σ comprises a mixed-strategy Nash equilibrium of a game G if, for eλu1/(eλu1 + eλu2), where λ is a factor that characterizes the prob- all i ∈ N and for all σi ∈ Σi, ui(σi, σ∗−i) − ui(σ∗i, σ∗−i) ≤ 0. ability of the player making a mistake in the choice of the “right”strategy [22]. Namely, λ = 0 indicates that the player chooses A pure-strategy Nash equilibrium is a vector of pure strategies, at random regardless of the payoffs, while λ → ∞ converges to s∗ ∈ S, that satisfies the equivalent condition.
the Nash behavior of always selecting the strategy with the higher The main advantage of the concept of Nash equilibrium resides payoff. At the Quantal Response Equilibrium, the vector of mixed in its simplicity. However, because Nash equilibria rely on very strategies σ∗ used by the players satisfies σ∗ = T (u(σ∗)), where stringent assumptions on the capabilities and objectives of each u(.) is the function that maps a set of mixed strategies to a set of player, they can predict counter-intuitive or unrealistic outcomes.
payoffs, and T (.) is the function that maps a set of payoffs to a set Thus, the economics community has provided an increasing num- of mixed strategies.1 Thus, a QRE results in a set of conditions on ber of refinements to strengthen the concept of Nash equilibrium (e.g., perfect vs. proper equilibria). Similarly, some have investi- Models such as QRE or noisy introspection are very useful as gated how to weaken the rational choice assumptions on which the an empirical structure for uncovering features of payoffs from field Nash equilibrium concept is built: a rational player is expected to data, or to obtain relationships between observables and primitives demonstrate error-free decision-making, to have perfect foresight of interest [17]. In other words, models and equilibrium concepts of the game and to be unbounded in her computational abilities. In- for bounded rationality can help reconcile data observed experi- tuitively, players such as network users (which are not necessarily mentally with a game theoretic analysis.
perfectly rational) or automated agents (which can be faulty, due to For the preliminary analysis we present in this paper, we will fo- software bugs or misconfiguration, or have limited computational cus on a particular type of bounded rational behavior, called near resources) will likely deviate from these rigid assumptions.
rationality [3, 27]. In near rational equilibria a player who is not As an illustration of how the assumptions required in a Nash equilibrium may need to be relaxed in practice, consider, an expe- 1The Brouwer fixed point theorem indicates that such an equilib- rienced player whose strategy choice is almost perfectly correlated rium exists as soon as the function T (e(.)) is continuous.
perfectly maximizing her utility cannot improve her payoff by a Network Formation
substantial amount by playing her Nash strategy more accurately.
For our first case study, we briefly discuss network formation by While the personal losses for a player are potentially very small, self-interested parties. Following seminal work in economics [20], the equilibria derived often represent substantial departures from a network formation has lately received relatively significant atten- prediction based on perfect Nash optimizing behavior. As we will tion in the networking research community. We refer the interested discuss in the remainder of this paper, models of near rationality reader to recent studies, such as [7, 11], for an in-depth discussion are appropriate for the description of empirical phenomena but can of the problem. Here, our only focus is to show how considering also contribute explanations and predictions of strategic behavior.
near rational behavior, as opposed to Nash behavior, can help us In addition, we will also illustrate how models of near rational- validate or invalidate a game theoretic model.
ity can be used to assess the accuracy and robustness of a given We define a network as a set of n nodes connected by a set of game-theoretic model, which can possibly lead to refinements of k directed links (where k ≤ 2n(n − 1)). Each node is used to store items that are of interest to other nodes. We follow the genericnetwork model described in [6] where each node can request items, CASE STUDIES
serve items, or forward requests between other nodes. As in [6], weassume shortest-path routing. Using a few simplifying assumptions In this section, we present three case studies on network forma- (e.g., all nodes are considered to have the same capabilities, all tion, security, and TCP congestion control. For each of the case links have the same establishment cost, and requests for items are studies, we describe the interaction between the different partici- uniformly distributed over the entire network), the authors of [6] pants in terms of a game, and note the discrepancies between the express the cost associated to each node i as game outcome as predicted by a Nash equilibrium and the behav-ior observed empirically. Allowing for near rationality allows us to + lEdi,j + rEbj,k(i) + m deg(i) , determine if the outcome is highly sensitive to small variations in player behavior, in which case the model might need to be refined.
where Edi,j is the expected value of the topological distance (hop- In cases where the model seems sufficiently robust, we then discuss count) between node i and another node j, Ebj,k(i) is the expected whether considering near rational players can lead to more accurate value of the probability that node i is on the path between two arbitrary nodes j and k, and deg(i) is the out-degree of node i,that is, the number of nodes node i links to. The constants s, l, r Preliminaries
and m represent the nominal costs associated with storing an item, Before we delve into the details of each case study, we discuss retrieving an item one hop away, routing a request between two in more details the equilibrium concept that we use for the analysis other nodes, and maintaining a connection to another node, respec- in the remainder of this paper. As we mentioned before, we are tively. From this cost model, we can immediately define the utility interested in assessing if near rationality can help us build better game theoretic models for networked systems. Here, we will focus on a simple, but powerful model of near rationality, called the ε- Assume that nodes can choose which links they maintain, but do The ε-equilibrium concept [27] is relaxing the conception of a not have any control over the items they hold, and honor all routing fully rational player to a model where each player is satisfied to requests. In other words, nodes are selfish when it comes to link get close to (but does not necessarily achieve) her best response to establishment, but are obedient once links are established.
the other player’s strategies. No player can increase her utility bymore than ε by choosing another strategy. Therefore, we locate an PROPOSITION 1. With the utility function given in Eq. (1), if ε-equilibrium by identifying a strategy for each player so that her m < l/n, the fully connected network where each node links to payoff is within ε of the maximum possible payoff given the other every other node is a unique pure Nash equilibrium. Formally, an ε-equilibrium can be defined as follows: ROPOSITION 2. If m > l/n, the star-shaped network, where all links connect to or from a central node, is a pure Nash equilib- DEFINITION 2. A vector of mixed strategies σε = (σε Σ comprises a mixed-strategy ε-equilibrium of a game G if, for Propositions 1 and 2, whose proofs are in Appendix A, tell us all i ∈ N, for all σi ∈ Σi, and a fixed ε > 0, ui(σi, σε−i) − that, if maintaining links is cheap, or if the network is small, the ui(σεi, σε−i) ≤ ε. only Nash equilibrium is the fully connected network. If maintain- A pure-strategy ε-equilibrium is a vector of pure strategies, sε ∈ S, ing links is more expensive, or if the network is large, a star-shaped that satisfies the equivalent condition. If we allow ε = 0 this con- network is a possible Nash equilibrium.2 While the star may not be dition reduces to the special case of a Nash equilibrium. Thus, one a unique Nash equilibrium, the high aggregate utility of the star [6] can consider ε-equilibria as a more generalized solution concept suggests it may dominate other potential Nash equilibria. We note that the authors of [20] obtain comparable results using a slightly We emphasize again that other equilibrium concepts, including bounded rationality models, are probably equally, if not more, use- Thus, if the model is accurate, and if nodes behave fully ratio- ful in modeling and analyzing networked systems. However, since nally, we should expect predominance of fully-connected or star- the main objective of this paper is to show how equilibrium con- shaped networks in practice. However, if instead of considering cepts that are conceptually quite close to Nash equilibria can help Nash equilibrium, we now consider an ε-equilibrium, then, for any improve the game theoretic analysis of networked systems, we de- m ∈ [l/n − ε, l/n + ε], any network topology constitutes an ε- fer the discussion of the applicability of more elaborate models equilibrium. (This can be proven by simply including ε in all the of near (or bounded) rationality to future work, and will use ε- 2In the limit case where m is exactly equal to l/n, any network equilibria for the analysis in the remainder of this section.
derivations of Appendix A.) Additionally, if, to account for fail- that, while the size n of the network does not play a central role in ures in link establishment due for instance to lossy channels, we our model, we expect the scenario we describe to be more realistic allow nodes to use mixed strategies instead of being restricted to in the case of a small corporate or university network, that is when pure strategies, we conjecture that the range of possible values for m such that any network is an ε-equilibrium is much larger than2ε.
PROPOSITION 3. The game described above has a unique pure In other words, even a detailed cost model as proposed in [6] Nash equilibrium, where all users choose an identical security level appears to be highly sensitive to small changes in player behav- ior. This high sensitivity hints that the game model needs to berefined, an intuition which is corroborated by empirical measure- Proposition 3, whose proof we derive in Appendix B, tells us that, ments. While star-shaped topologies or full meshes can indeed be for a Nash equilibrium to hold, all users have to choose the highest found in existing networks (e.g., many small local area networks level of security available. As in the first case study, one could con- use star topologies), measurement studies of Internet topologies sider pure ε-equilibria to check the sensitivity of the model to small exhibit much more varied results [12]. Among the reasons why changes in player behavior. It can be shown that, for this specific Internet topologies do not solely consist of an interconnection of game, pure ε-equilibria produce results very close to Proposition 3, star-shaped and fully connected networks, one can cite capacity and thus the model seems reasonably robust to small perturbations.
constraints [7] or monetary incentives, which are not included in In fact, due to the symmetry of the game, one can conjecture that, regardless of the value of the penalty P , all users would implement While proposing a game-theoretic model that captures these ad- the same security level in a pure equilibrium.
ditional factors is outside of the scope of this paper, we summarize However, available data from large networks, e.g., [8], docu- the outcome of this first case study as follows: considering near ments that different systems present highly heterogeneous security rationality instead of perfect rationality can help us evaluate the ro- vulnerabilities, which in turn indicates that implemented security bustness of a model to small perturbations in the players actions. If levels are highly disparate across machines. Hence, in the context the model seems to lack robustness, its chances of being an accurate of the security game we just described, a Nash equilibrium does not seem to accurately describe observed behavior.
Some of the possible explanations for the heterogeneity of the Protection Against Security Threats
implemented security levels can be captured by more elaborateequilibrium models. In particular, (1) users have incomplete in- With our second case study, we hope to show that slightly mod- formation on the levels of security deployed by other users, (2) ifying the description of a game to account for near rationality al- the perceived benefit of installing security patches may be smaller lows to significantly improve the predictive quality of the game than the overhead patching incurs, and (3) some users may be gam- when compared to empirically observed behavior. To that effect, bling (knowingly or not) on the seriousness of the security threats we look at the level of security users choose in a network subject they face. These three arguments all make the case for considering to a security threat. Specifically, we focus on protection against ε-equilibria (to account for (1) and (2)) with mixed strategies (to potential distributed denial of service (DDoS) attacks. In the first account for (2) and (3)), rather than a pure Nash equilibrium.
stage of a DDoS attack, an attacker looks for a (set of) machine(s)whose control she can easily seize, to use as a platform to launch PROPOSITION 4. There exist mixed-strategy ε-equilibria with an attack of larger magnitude. For instance, by obtaining total con- ε ≤ P/4 where all chosen security levels are distributed over the trol of a machine on a network, an attacker may be able to retrieve passwords and gain access to more secure machines on the samenetwork.
Proposition 4, which we prove in Appendix B, indicates that con- We model here a network of n users, who are all potential tar- sidering ε-equilibria with mixed strategies allows us to predict large gets in the initial stage of a DDoS attack. If we characterize the dispersion of the chosen security levels, even for relatively low val- level of computer security that each user i adopts by a variable si, ues of ε. This result seems to be more in line with the available the user(s) with the lowest si (i.e., si = smin = mini{si}) will measurement data. We further note that analogous results have be compromised. We assume that each user can infer the security been recently derived to quantitatively model price dispersion phe- level si used by every other user (e.g., by probing), and no finite nomena [5], where assuming a Nash equilibrium likewise fails to security level si can be selected to guarantee a protection against all attacks. We further assume that the cost of implementing a secu- We emphasize that Proposition 4 only states that near rational- rity policy si is a monotonic increasing function of si. Specifically, ity can explain dispersion. In particular, the proof of Proposition 4 to simplify the notations, we consider here that each user i that is we present in Appendix B uses a specific distribution function to not compromised pays si to implement their security policy. The show that there exist mixed ε-equilibria, with ε relatively small, compromised user(s), say user j, pays a fixed penalty P ≥ si (for that result in dispersion of the security levels over the entire spec- any si), independent of the security level smin she has chosen.
trum (0, P ). However, we do not claim that the specific distribution While very simplified, we conjecture this game is a relatively used in the proof is a realistic characterization of user behavior; in accurate model of the first stage of DDoS attacks that have been fact, we believe that further work is required to provide a distribu- carried out in practice [10].3 We defer the study of the deployment tion function that accurately describes the mixed strategies imple- of the attack beyond the first stage to future work. Also, we stress Additionally, one can direct two critiques at the discussion on the 3 While this type of attack shares some similarities with worm prop- security game we just presented. First, the discrepancies between agation, notably searching for insecure machines [24], a worm typ- the behavior predicted by a Nash equilibrium and that observed in ically propagates by infecting all machines on a network that arebelow a certain, fixed, security level, which is different from our practice may be due to an inaccurate game model, rather than from hypothesis that only the machines with the lowest level of security assuming a given type of equilibrium. Second, one can argue that while the assumption of perfect rationality, as required in a pure Nash equilibrium, is very debatable when strategies are selected by Therefore, having an ε-equilibrium implies that, for any αi, humans (such as in the security game), perfect rationality is a muchmore reasonable assumption in the case of automated agents. How- ui(αi, α−i) − ui(αi, α−i) ≤ ε , ever, neither of these arguments invalidates our case for consider- ing near rationality as an additional tool to improve game theoreticmodeling of networked systems.
(A + αi)(A + αi) TCP Congestion Control
If we allow αi = 0 and αi → ∞, an ε-equilibrium can only oc- The last case study we propose has for object to further our cur for ε ≥ c, that is, when ε is larger than the maximum utility case that considering near rationality is helpful in refining game- achievable. In such a scenario, ε is so large that all players select a theoretic models for networked systems. This third case study value for their parameter αi at random.
relies on a game-theoretic analysis of the TCP transport protocol Adding the assumption that variations of αi are bounded leads [2]. Each TCP sender relies on an additive-increase-multiplicative- to much more interesting results.5 Specifically, let us impose αi − decrease (AIMD) algorithm to adjust its sending rate in function of αi ≤ K for K ∈ N. For simplicity, let us set the initial values for the congestion experienced on the path from sender to receiver.
αi to the default value in TCP implementations, that is, αi = 1 for In [2], Akella et al. present a game-theoretic analysis to model all i. Then, we have A = n − 1 and 0 ≤ αi ≤ K + 1. Substituting competition between different TCP senders for three of the most in Eq. (2), we have a ε-equilibrium as soon as popular variants of TCP, namely, TCP Tahoe, TCP Reno and TCP SACK. In the TCP Game they describe, players are the TCP sources (i ∈ {1, . . . , n}), which are allowed to adjust their individual ad-ditive increase (αi) and multiplicative decrease (βi) parameters. In Hence, in a network with a large number of TCP senders, the de- the TCP Game, the utility of each player is equal to her goodput, fault TCP implementation can be an ε-equilibrium for small values which is defined as the total amount of data transfered over a time of ε. This is one of the possible explanations why the predicted interval, minus the amount of data that had to be retransmitted (pre- Nash behavior that all users would turn off TCP congestion control sumably because of losses in the network) over the same time in- One of the insights presented in [2] is that, for TCP SACK, a pure DISCUSSION
Nash equilibrium results in αi → ∞ (infinite additive increase) if We have shown through three case studies that considering com- βi is held fixed, while βi → 1 (no multiplicative decrease) if αi is petitive equilibria of a more general form than pure Nash equilibria held fixed. Simply stated, if all players in a TCP SACK network can be beneficial in systems research. In particular, we discussed were behaving according to a Nash equilibrium, they would simply how allowing players to slightly deviate from their optimal utility turn off congestion control, which would likely result in the net- can help reconcile game-theoretic models and observed player be- work suffering from complete congestion collapse. However, TCP SACK is increasingly deployed on the Internet [4], and yet, we The first case study on network formation showed how slightly do not observe congestion collapse phenomena due to misbehaving relaxing the assumption that the players are perfectly rational was useful in assessing the sensitivity of a game theoretic model to One of the possible reasons proposed by the authors of [2] for small perturbations, thereby helping to evaluate its likelihood to the continued stable operation of the Internet is that a given user be a realistic model. The second case study on the implementation may face technical difficulties to modify the behavior of her ma- of security policies showed how the interaction of uncertainties in chine to behave greedily. We submit this potential explanation can the decision making process and the payoff evaluation could be be partially captured by considering an ε-equilibrium instead of a used to explain empirical behavior. The third case study on TCP Nash equilibrium. The cost of modifying the behavior of a given congestion control showed how combining refinements to a model machine can indeed be viewed as a switching cost, to be included description with a relaxation of the assumptions in force by em- ploying a more generalized equilibrium concept can improve the For simplicity, we assume here that players can only modify their match between the (analytically) predicted outcome and the (em- additive increase parameter αi. (An analogous study can be carried out if we allow changes to βi.) The authors of [2] show that, with From a system design perspective, we note that, even in games TCP SACK, player i’s utility (goodput) is given by in which the actions of each player resulting in a pure Nash equilib- rium are undesirable from the system designer’s perspective, near rational players may actually settle for a desirable outcome. This is a possible explanation why the Internet does not suffer from con- where c denotes the total capacity (bandwidth-delay product di- gestion collapse, despite the inefficiency of the Nash equilibrium vided by the round-trip-time) of the bottleneck link, and in the TCP SACK game. Conversely, potentially desirable out- comes associated with a Nash equilibrium may prove difficult to reach unless all players are perfectly rational. The security game 5Note that there are several possible justifications for bounding the variations on αi. For instance, because obtaining perfect knowl- 4 In fact, the authors of [2] point out that the Nash equilibria for TCP edge of the state of the entire network is difficult (or impossible) NewReno and TCP SACK are similar. TCP NewReno and TCP for a given user, each user may instead incrementally probe the net- SACK combined currently account for an overwhelming majority work to discover her optimal setting for αi. Such a probing behav- of all traffic on the Internet, which hints that the observed stable ior can be captured as a repeated game where, for each repetition, operation of the Internet probably does not result from having a αi − αi ≤ K. This type of model thus presents some similarities mix of different TCP variants in the network.
with the learning behavior that is thoroughly studied in [14].
we described presents an instance of such a phenomenon. Thus, it [7] B.-G. Chun, R. Fonseca, I. Stoica, and J. Kubiatowicz.
appears that taking into account uncertainty factors can be useful in Characterizing selfishly constructed overlay networks. In both game specification and mechanism design.
Proc. IEEE INFOCOM’04, Hong Kong, Mar. 2004.
An alternative to modeling near rationality is to refine the game [8] Cisco Secure Consulting. Vulnerability statistics report.
specification, to capture all factors with any conceivable influence on the game outcome. However, we argue that the two approaches are not exclusive. In fact, as shown in the first case study, refine- [9] B. Cohen. Incentives build robustness in BitTorrent. In Proc. ments to the game description are probably of interest when the 1st Workshop on Econ. of Peer-to-Peer Syst., Berkeley, CA, near rationality assumption yields substantial deviations from the outcome predicted by a Nash equilibrium. Research on bounded- [10] D. Dittrich. The DoS project’s “trinoo” distributed denial of reasoning and bounded-optimality models [28] provides a solid service attack tool, Oct. 1999. Available from As a follow-up on our case studies, we are interested in gathering experimental data, through user surveys, on how security levels are [11] A. Fabrikant, A. Luthra, E. Maneva, C. Papadimitriou, and chosen in practice, and in investigating how well this data can be S. Shenker. On a network creation game. In Proc. ACM described using game-theoretic models. We are also planning on PODC’03, pages 347–351, Boston, MA, July 2003.
conducting simulation studies to assess the actual impact of uncer- [12] M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law tainties and of mixed strategies on network formation.
relationships of the Internet topology. In Proc. ACM Last, we believe that this research has uncovered a few open SIGCOMM’99, pages 251–262, Boston, MA., Aug. 1999.
problems that may warrant future investigation. First, our case [13] J. Feigenbaum and S. Shenker. Distributed algorithmic studies seem to show that considering other types of equilibria be- mechanism design: Recent results and future directions. In sides Nash equilibria can help expand the applicability of game- Proc. DIAL-M’02, pages 1–13, Atlanta, GA, Sept. 2002.
theoretic models to networked systems. While the ε-equilibriumused in this paper is an interesting tool, many other equilibrium [14] E. Friedman and S. Shenker. Learning and implementation models have been investigated in the literature, e.g., [3, 16, 23].
on the Internet. Working paper. Available from http:// We conjecture that different types of equilibrium may be appropri- ideas.repec.org/p/rut/rutres/199821.html, ate for different networking problems, and believe that providing a classification of networking problems according to the specific [15] J. Goeree and C. Holt. Ten little treasures of game theory and types of equilibrium that best characterize them would be valuable.
ten intuitive contradictions. Amer. Econ. Rev., More generally, one can also ask how a game-theoretic model can capture that the rationality of each participant may vary across [16] J. Goeree and C. Holt. A model of noisy introspection.
users: some users may be obedient, some others may be fully ratio- Games Econ. Behav., 46(2):365–382, Feb. 2004.
nal, some may be faulty [13]. Finding if and how game-theoretical [17] P. Haile, A. Hortac¸su, and G. Kosenok. On the empirical models can accommodate heterogeneous populations of players may content of quantal response equilibrium. Cowles Foundation help us design better systems, and certainly poses a number of in- Discussion Paper Series, (1432), Aug. 2003.
[18] G. Hardin. The tragedy of the commons. Science, ACKNOWLEDGMENTS
[19] H.-Y. Hsieh and R. Sivakumar. Performance comparison of cellular and multi-hop wireless networks: A quantitative This work is supported in part by the National Science Founda- study. In Proc. ACM SIGMETRICS’01, pages 113–122, tion through grants ANI-0085879 and ANI-0331659. We thank the anonymous reviewers for their insightful comments, which greatly [20] M. Jackson and A. Wolinsky. A strategic model for social and economic networks. J. Econ. Theory, 71(1):44–74, Oct.
1996.
REFERENCES
[21] P. Klemperer. Using and abusing economic theory. J. Europ. Econ. Assoc., 1(2/3):272–300, April-May 2003.
[1] E. Adar and B. Huberman. Free riding on Gnutella. First [22] D. McFadden. Econometric analaysis of qualitative response models. In Z. Grilliches and M. Intriligator, editors, [2] A. Akella, S. Seshan, R. Karp, S. Shenker, and Handbook of Econometrics, volume II, pages 1396–1456.
C. Papadimitriou. Selfish behavior and stability of the Elsevier, Amsterdam, Netherlands, 1984.
Internet: A game-theoretic analysis of TCP. In Proc. ACM [23] R. McKelvey and T. Palfrey. Quantal response equilibria for SIGCOMM’02, pages 117–130, Pittsburgh, PA, Aug. 2002.
normal form games. Games Econ. Behav., 10(1):6–38, July [3] G. Akerlof and J. Yellen. Can small deviations from rationality make significant differences to economic [24] D. Moore, V. Paxson, S. Savage, C. Shannon, S. Staniford, equilibria? Amer. Econ. Rev., 75(4):708–720, Sept. 1985.
and N. Weaver. Inside the Slammer worm. IEEE Security [4] M. Allman. A web server’s view of the transport layer. ACM and Privacy, 1(4):33–39, July 2003.
Comp. Comm. Rev., 30(5):10–20, Oct. 2000.
[25] J. Nash. Non-cooperative games. Annals of Mathematics, [5] M. Baye and J. Morgan. Price dispersion in the lab and on the Internet: Theory and evidence. RAND J. Econ., 35(3), [26] C. Papadimitriou. Algorithms, games and the Internet. In Proc. ACM STOC’01, pages 749–753, Heraklion, Crete, [6] N. Christin and J. Chuang. On the cost of participating in a peer-to-peer network. In Proc. IPTPS’04, San Diego, CA, [27] R. Radner. Collusive behavior in noncooperative epsilon-equilibria of oligopolies with long but finite lives. J. PROOFS OF PROPOSITIONS 3 AND 4
Econ. Theory, 22:136–154, 1980.
We first consider that users are only allowed pure strategies, and [28] S. Russell and D. Subramanian. Provably bounded-optimal agents. J. Artif. Intel. Res., 2:575–609, May 1995.
PROOF OF PROPOSITION 3. Without loss of generality, we as- [29] S. Shenker. Making greed work in networks: A sume that users {1, . . . , k}, with 1 ≤ k ≤ n, choose a security game-theoretic analysis of switch service disciplines.
IEEE/ACM Trans. Networking, 3(6):819–831, Dec. 1995.
min < si for all i ∈ {k + 1, . . . , n}. Thus, each user i for i ∈ {1, . . . , k} is compromised, and has a utility ui = −P . Users [30] J. Shneidman and D. Parkes. Rationality and self-interest in in i ∈ {k + 1, . . . , n} cannot be compromised because si > smin peer-to-peer networks. In Proc. IPTPS’03, pages 139–148, and therefore have a utility ui = −si.
Suppose a user i in {1, . . . , k} were to increase her security level to si = smin +h for h > 0. User i’s utility would become −smin− APPENDIX
h. However, because the original constellation of security levelsforms a Nash equilibrium, we know that such a change of strategy PROOFS OF PROPOSITIONS 1 AND 2
results in a decrease of user i’s utility for any h > 0. That is, for Here, we first show that the fully connected network is the only Nash equilibrium if and only if m < l/n, before showing that, if m > l/n, the star-shaped network characterizes a Nash equilib- smin − h + P ≤ 0 , which reduces to smin ≥ P − h for any h > 0, so that smin ≥P by continuity. By hypothesis, s ROOF OF PROPOSITION 1. In a fully connected network, no node can create additional links. If a given node i removes one of min = P . Since for any i, smin ≤ si ≤ P , we obtain k = n, its links, deg(i) decreases from (n − 1) to (n − 2), but, at the same i = P is the only possible Nash equilibrium. The time, one of the nodes i = i is now at a distance of 2 from i. Thus, i = −P , and cannot be increased by picking a different security level, which confirms that Suppose now that users choose their security level probabilisti- cally. More precisely, the probability that user i picks a security and the difference in utility for node i, between the strategy of re- level si below a value s is characterized by the cumulative distri- moving one link and the strategy consisting in maintaining all links, is m − l/n. To have a pure Nash equilibrium, we therefore need to i (s) = P r[si ≤ s].
have m − l/n ≤ 0, which is true if and only if m ≤ l/n.
PROOF OF PROPOSITION 4. Consider the following continuous Suppose now that we have m < l/n, and a network that is not fully connected. In particular, consider that a node i can decide whether to create a link to another node i = i. Before addition of the link i → i , i is at a distance 2 ≤ d i,i ≤ n − 1 of i. After creation of the link i → i , i is at a distance 1 of i. Thus, by creat- ing the link i → i , Edi,j at least decreases by (2 − 1)/n = 1/n.
We use Eui(s) to denote the expected value of the utility ui(s) in Adding the link i → i also results in deg(i) increasing by one, so function of a security level s. Because ui(s) = −P if all users j = that the addition of the link i → i eventually results in a change i choose security levels higher than s, and ui(s) = −s otherwise, in the node i’s utility equal to −m + l/n, which, by hypothesis, is strictly positive. Hence, node i always has an incentive to add linksto nodes it is not connected to. Using the same reasoning for all Eui(s) = −P (P r[sj > s])n−1 − s(1 − (P r[sj > s])n−1) , nodes, we conclude that the fully connected network is the unique which can be expressed in terms of F Nash equilibrium if m < l/n.
Eui(s) = −P (1 − Fsi (s))n−1 − s(1 − (1 − Fsi(s))n−1) . (4) Consider now a star-shaped network, where all links connect to or from a central node, say node 0, and assume that m > l/n.
Substituting Fsi (s) by its expression given in Eq. (3), Eq. (4) re-duces to PROOF OF PROPOSITION 2. Node 0 is fully connected to the rest of the network, and therefore cannot create additional links. If Eui(s) = −P + s node 0 removes one of its links, one of the n − 1 other nodes be- A study of the variations of Eui(s) in function of s ∈ [0, P ] indi- comes unreachable, which implies Ed0,j → ∞, and u0 → −∞.
cates that Eui(s) ≥ Eui(0) = −P and that Eui(s) ≤ Eui(P/2), Thus, node 0 has no incentive in modifying its set of links. Like- with Eui(P/2) = −3P/4. Thus, if we have ε = P/4, any vari- wise, peripheral nodes do not remove their (only) link to the central ation of the expected utility is smaller ε, which characterizes an node, to avoid having their utility ui → −∞.
ε-equilibrium. In other words, we have shown, by providing a Suppose now that a peripheral node i creates an additional link to another peripheral node i = i. An argument identical to that used i (s), that there exist ε-equilibria with ε ≤ P/4 where the security levels si can be spread out over the entire in- in the proof of Proposition 1 shows that the addition of the link terval [0, P ]. Note that we only present an existence proof here.
i → i results in a change in the node i’s utility equal to −m + l/n.
It is unclear whether the chosen c.d.f Fs Here, however, m > l/n, so that −m+l/n < 0, and node i has no i (s) is an accurate depic- tion of how security levels are chosen in reality, and it is likewise incentive in adding the link i → i . Thus, the star-shaped network entirely possible that there exist other distributions of the security is a pure Nash equilibrium, which may not be unique.
levels over [0, P ] that result in ε-equilibria for ε

Source: http://conferences.sigcomm.org/sigcomm/2004/workshop_papers/pin34-christin1.pdf