# selfishness_level_of_strategic_games__28cbf678.pdf

Journal of Artificial Intelligence Research 49 (2014) 207 240 Submitted 08/13; published 02/14

Selfishness Level of Strategic Games

Krzysztof R. Apt k.r.apt@cwi.nl Guido Sch afer g.schaefer@cwi.nl Centre for Mathematics and Computer Science (CWI) Networks and Optimization Group Science Park 123 1098 XG Amsterdam The Netherlands

We introduce a new measure of the discrepancy in strategic games between the social welfare in a Nash equilibrium and in a social optimum, that we call selfishness level. It is the smallest fraction of the social welfare that needs to be offered to each player to achieve that a social optimum is realized in a pure Nash equilibrium. The selfishness level is unrelated to the price of stability and the price of anarchy and is invariant under positive linear transformations of the payofffunctions. Also, it naturally applies to other solution concepts and other forms of games. We study the selfishness level of several well-known strategic games. This allows us to quantify the implicit tension within a game between players individual interests and the impact of their decisions on the society as a whole. Our analyses reveal that the selfishness level often provides a deeper understanding of the characteristics of the underlying game that influence the players willingness to cooperate. In particular, the selfishness level of finite ordinal potential games is finite, while that of weakly acyclic games can be infinite. We derive explicit bounds on the selfishness level of fair cost sharing games and linear congestion games, which depend on specific parameters of the underlying game but are independent of the number of players. Further, we show that the selfishness level of the n-players Prisoner s Dilemma is c/(b(n 1) c), where b and c are the benefit and cost for cooperation, respectively, that of the n-players public goods game is (1 c

n)/(c 1), where c is the public good multiplier, and that of the Traveler s Dilemma game is 1

2(b 1), where b is the bonus. Finally, the selfishness level of Cournot competition (an example of an infinite ordinal potential game), Tragedy of the Commons, and Bertrand competition is infinite.

The intelligent way to be selfish is to work for the welfare of others Dalai-Lama1

1. Introduction

The discrepancy in strategic games between the social welfare in a Nash equilibrium and in a social optimum has been long recognized by the economists. One of the flagship examples is Cournot competition, a strategic game involving firms that simultaneously choose the

1. (Bowles, 2004, p. 109).

c 2014 AI Access Foundation. All rights reserved.

Apt & Sch afer

production levels of a homogeneous product. The payofffunctions in this game describe the firms profit in the presence of some production costs, under the assumption that the price of the product depends negatively on the total output. It is well-known (see, e.g., Jehle & Reny, 2011, pp. 174 175) that the price in the social optimum is strictly higher than in the Nash equilibrium, which shows that the competition between the producers of a product drives its price down. In computer science the above discrepancy led to the introduction of the notions of the price of anarchy (Koutsoupias & Papadimitriou, 2009) and the price of stability (Schulz & Moses, 2003; Anshelevich, Dasgupta, Kleinberg, Tardos, Wexler, & Roughgarden, 2008) that measure the ratio between the social welfare in a worst and, respectively, a best Nash equilibrium and a social optimum. This originated a huge research effort aiming at determining both ratios for specific strategic games that possess (pure) Nash equilibria. These two notions are descriptive in the sense that they assess the existing situation. Said differently, these notions quantify the discrepancy between the social welfare in a Nash equilibrium and a social optimum given the initial payofffunctions. In contrast, we propose a notion that is normative in the sense that it explains how to change these payofffunctions to resolve such a discrepancy. Intuitively, we are asking the question how much of the social welfare needs to be added to the players payofffunctions so that their individual preferences can bring them to an optimal outcome for the society. On an abstract level, the approach that we propose here is related to one proposed by Axelrod (1984, p. 134), in chapter How to Promote Cooperation , from where we cite: An excellent way to promote cooperation in a society is to teach people to care about the welfare of others. Our approach draws on the concept of altruistic games (see, e.g., Ledyard, 1995, and more recently Marco & Morgan, 2007). In these games each player s payoffis modified by adding a positive fraction α of the social welfare in the considered joint strategy to the original payoff. The selfishness level of a game is defined as the infimum over all α 0 for which such a modification yields that a social optimum is realized in a pure Nash equilibrium. The underlying property is monotonic in the sense that if for some α 0 a social optimum is a pure Nash equilibrium, then it is also the case for every β α. Intuitively, the selfishness level of a game can be viewed as a measure of the players willingness to cooperate. A low selfishness level indicates that the players are open to align their interests in the sense that a small share of the social welfare is sufficient to motivate them to choose a social optimum. In contrast, a high selfishness level suggests that the players are reluctant to cooperate and a large share of the social welfare is needed to stimulate cooperation among them. An infinite selfishness level means that cooperation cannot be achieved through such means. Notions like the price of stability and the price of anarchy were developed to measure the quality of equilibria. In contrast, our notion of the selfishness level can be regarded as a measure of willingness to cooperate. In general, these notions are incomparable (as we will also argue formally) and provide different insights into the underlying game. Our main motivation for analyzing the selfishness level of strategic games is to gain a deeper understanding of the characteristics that influence the players willingness to cooperate. As it turns out, for several games studied in this paper the selfishness level provides such insights. To illustrate this point, we briefly elaborate on our findings for the public goods game and the fair cost sharing game.

Selfishness Level of Strategic Games

In the public goods game there are n players who want to contribute to a public good. Every player i chooses an amount si [0, b] that he contributes. A central authority collects all individual contributions, multiplies their sum by c > 1 (for simplicity we assume here that n c) and distributes the resulting amount evenly among all players. The payoffof player i is thus pi(s) := b si + c

n P j sj. In the (unique) Nash equilibrium, every player attempts to free ride by contributing 0 to the public good (which is a dominant strategy), while in the social optimum every player contributes the full amount of b. As we will show, the selfishness level of this game is (1 c

n)/(c 1). This bound suggests that the temptation to free ride (i) increases as the number of players grows and (ii) decreases as the parameter c increases. Both phenomena were observed by experimental economists, (see, e.g., the discussion in Ledyard, 1995, Section III.C.2). In comparison, the price of stability (which coincides with the price of anarchy) for this game is c. In a fair cost sharing game every player i chooses a facility from a set of facilities Si E available to him (for simplicity we discuss here only the case where players choose a single facility). The cost ce of every used facility e E is shared evenly among the players using it. As we will prove, the selfishness level of this game is max{0, 1

2cmax/cmin 1}, where cmax and cmin refer to the largest and smallest cost of a facility, respectively. Our analysis therefore reveals a threshold phenomenon which also makes sense intuitively: In order to motivate cooperation among the players it is crucial to convince the players having access to a facility with cost cmin to adhere to a social optimum. If cmax 2cmin this is easy because in a social optimum each such player either shares the cost of a facility e with ce cmin with at least one other player or uses a facility of cost cmin exclusively by himself. Thus, it is in the self-interest of each player to cooperate and choose a social optimum in this case. If cmax > 2cmin these players are reluctant to cooperate and the fraction of the social welfare that needs to be offered to them to incite cooperation grows proportionally to cmax/cmin. Anshelevich et al. (2008) showed that the price of stability and the price of anarchy of this game are Hn and n, respectively, where n denotes the number of players.2 So these measures depend on the number of players. In contrast, our notion reveals a dependency on the discrepancy between the costs of the facilities. A large body of literature in experimental economics indicates that players have a tendency to cooperate in social dilemmas like the Prisoner s dilemma, the Traveler s dilemma or the public goods game, even though such behavior is ruled out by standard game-theoretic analysis. Several studies suggest that the willingness to cooperate depends on certain parameters of the underlying game (like group-size, magnitude of payoffs, etc.); see, e.g., Isaac and Walker (1988), Cooper, De Jong, Forsythe, and Ross (1996), Goeree and Holt (2001), Becker, Carter, and Naeve (2005), and Dreber, Rand, Fudenberg, and Nowak (2008). For example, Dreber et al. observe that in the Prisoner s dilemma the willingness to cooperate increases with the ratio of cost over benefit for cooperation. We therefore study the selfishness level of parameterized versions of these games. Our findings show that the selfishness level also exhibits a dependency on certain parameters of the game. In this paper, we define the selfishness level by taking pure Nash equilibrium as the solution concept. This is in line with how the price of anarchy and price of stability were defined originally (Koutsoupias & Papadimitriou, 2009; Schulz & Moses, 2003; Anshelevich

2. Hn denotes the nth Harmonic number.

Apt & Sch afer

et al., 2008). However, the definition applies equally well to other solution concepts and other forms of games. We discuss these matters in the final section.

1.1 Our Contributions

The main contributions presented in this paper are as follows:

1. We introduce (in Section 2) the notion of selfishness level of a game, derive some basic properties and elaborate on some connections to other efficiency measures and models of altruism.

In particular, we show that the selfishness level of a game is unrelated to the price of stability and the price of anarchy. Moreover, the selfishness level is invariant under positive linear transformations of the payofffunctions. We also show that our model is equivalent to other models of altruism that have been studied before. As a consequence, our bounds on the selfishness level directly transfer to these alternative models.

2. We derive (in Section 3) a characterization result that allows us to determine the selfishness level of a strategic game.

Our characterization shows that the selfishness level is determined by the maximum appeal factor of unilateral profitable deviations from specific social optima, which we call stable. As a result, we can focus on deviations from these stable social optima only. Intuitively, the appeal factor of a single player deviation refers to the ratio of the gain in his payoffover the resulting loss in social welfare.

3. We use (in Section 4) our characterization result to analyze the selfishness level of several classical strategic games.

The games that we study are fundamental and often used to illustrate the consequences of selfish behavior and the effects of competition. A summary of our results is given in Table 1. In particular, we derive explicit bounds on the selfishness level of fair cost sharing games and congestion games with linear delay functions. The obtained bounds depend on specific parameters of the underlying game, which we find informative. We also show that these bounds are tight for certain instances.

4. We also show (in Section 5) that our selfishness level notion naturally extends to other solution concepts and other types of games, for instance mixed Nash equilibria and extensive games.

1.2 Related Work

There are only few articles in the algorithmic game theory literature that study the influence of altruism in strategic games (Caragiannis, Kaklamanis, Kanellopoulos, Kyropoulou, & Papaioannou, 2010; Chen, de Keijzer, Kempe, & Sch afer, 2011; Chen & Kempe, 2008; Elias, Martignon, Avrachenkov, & Neglia, 2010; Hoefer & Skopalik, 2009). In these works, altruistic player behavior is modeled by altering each player s perceived payoffin order to account also for the welfare of others. The models differ in the way they combine the player s

Selfishness Level of Strategic Games

Selfishness level

Ordinal potential games

Weakly acyclic games

Fair cost sharing games (singleton)

Fair cost sharing games (integer costs)

Linear congestion games (singleton)

(1 δmax)amin 1

Linear congestion games (integer coefficients)

2(L max min 1)}

Prisoner s Dilemma for n players

Public goods game

Traveler s dilemma

Cournout competition

Tragedy of the commons

Bertrand competition

Table 1: Selfishness level of the games studied in this paper. see Section 4 for the definitions of the respective parameters of the games.

individual payoffwith the payoffs of the other players. All these studies are descriptive in the sense that they aim at understanding the impact of altruistic behavior on specific strategic games.

Closest to our work are the articles by Elias et al. (2010) and by Chen et al. (2011). Elias et al. study the inefficiency of equilibria in network design games (which constitute a special case of the cost sharing games considered here) with altruistic (or, as they call it, socially-aware) players. As we do here, they define each player s cost function as his individual cost plus α times the social cost. They derive lower and upper bounds on the price of anarchy and the price of stability, respectively, of the modified game. In particular, they show that the price of stability is at most (Hn + α)/(1 + α), where n is the number of players.

Chen et al. (2011) introduce a framework to study the robust price of anarchy, which refers to the worst-case inefficiency of other solution concepts such as coarse correlated equilibria (see Roughgarden, 2009) of altruistic extensions of strategic games. In their model, player i s perceived cost is a convex combination of (1 γi) times his individual cost plus γi times the social cost, where γi [0, 1] is the altruism level of player i. If all players have a uniform altruism level γi = γ, this model relates to the one we consider here by setting α = γ/(1 γ) (see Section 2.3 for details). Although not being the main focus of the paper, the authors also provide upper bounds of 2/(1 + γ) and (1 γ)Hn + γ on the price of stability for linear congestion games and fair cost sharing games, respectively.

Note that in all three cases mentioned above the price of stability approaches 1 as α goes to . This seems to suggest that the selfishness level of these games is . However, this is not the case as our analyses reveal.

Apt & Sch afer

Two other models of altruism were proposed in the literature. Chen and Kempe (2008) define the perceived cost of a player as (1 β) times his individual cost plus β/n times the social cost, where β [0, 1]. Caragiannis et al. (2010) define the perceived cost of player i as (1 δ) times his individual cost plus δ times the sum of the costs of all other players (i.e., excluding player i), where δ [0, 1]. Also these two models can be shown to be equivalent to our model using simple transformations (see Section 2.3 for details). Subsequently, we mention a few related approaches that are normative. Conceptually, our selfishness level notion is related to the Stackelberg threshold introduced by Sharma and Williamson (2009) (see also Kaporis & Spirakis, 2009). The authors consider network routing games in which a fraction of β [0, 1] of the flow is first routed centrally and the remaining flow is then routed selfishly. The Stackelberg threshold refers to the smallest value of β that is needed to improve upon the social cost of a Nash equilibrium flow. In a related paper, Hoefer and Skopalik (2009) study the minimum number, termed the optimal stability threshold, of (pure) altruists that are needed in a congestion game to induce a Nash equilibrium as a social optimum. They show that this number can be computed in polynomial time for singleton congestion games. In network congestion games, researchers studied the effect of imposing tolls on the edges of the network in order to reduce the inefficiency of Nash equilibria (see, e.g., Beckmann, Mc Guire, & Winsten, 1956). From a high-level perspective, these approaches can also be regarded as normative. Recently, Capraro (2013) proposed a new normative approach to measure incentive for cooperation in symmetric games in which there is a tension between selfish and altruistic behavior. The solution concept is a pure Nash equilibrium of a transformed game in which the strategies are certain mixed strategic of the original game. These strategies depend on the incentive and risk of deviating from cooperation in the original game. Strikingly, Capraro s conclusions about the influence of the parameters in the Prisoner s Dilemma, Traveler s Dilemma and the public goods game are consistent with ours. There are several other papers that propose notions allowing to assess the stability of Nash equilibria. We mention a few of them below. Christodoulou, Koutsoupias, and Spirakis (2011) study the inefficiency of approximate Nash equilibria in congestion games. In a (1+ε)-approximate Nash equilibrium the cost of each player is at most (1+ε) times the cost he experiences in every unilateral deviation. The authors derive (almost) tight bounds on the price of stability and the price of anarchy for linear (non-atomic and atomic) congestion games as a function of ε. In particular, they obtain a bound of min{1, (1 +

3)} on the price of stability for atomic linear congestion games. In this context, an alternative notion to assess the stability of Nash equilibria that comes to one s mind is to consider the smallest ε 0 for which a social optimum is realized as a (1 + ε)-Nash equilibrium. Note that the above bound implies that such an ε is at most 1 for linear congestion games. We comment on this idea in more detail in Section 5.2. Anshelevich, Das, and Naamad (2009) consider the problem of incentivizing players to participate in socially desirable matchings by adding switching costs to player deviations. In their model, the additional cost that a player incurs by changing his strategy accounts for an ε fraction of his individual cost. Adopting this viewpoint, the authors study the inefficiency of (1 + ε)-approximate stable matchings. They derive bounds on the price of stability and the price of anarchy of (1 + ε)-approximate stable matchings as a function of

Selfishness Level of Strategic Games

ε 0. Related to this work is the article of Bir o, Manlove, and Mittal (2010) who study the problem of computing an optimal matching having a minimum number of blocking pairs. Furthermore, Balcan, Blum, and Mansour (2009) study the impact of advertising strategies to players in order to induce them to select more efficient equilibria. More precisely, in their model an authority first proposes a strategy to each player which is then accepted by each player with probability α. Each accepting player adheres to the proposed strategy and all remaining players play a best response (assuming that the strategies of the accepting players are fixed). In a final step all players follow a best response dynamics until a Nash equilibrium is reached. The authors analyze the inefficiency of the resulting equilibria for fair cost sharing games, machine scheduling games and party affiliation games. In particular, for fair cost sharing games they show that the expected cost of the resulting equilibrium is at most a factor O(log n/α) away from a social optimum.

2. Selfishness Level

In this section, we formally introduce our notion of selfishness level, establish some properties and relate it to other notions of altruism.

2.1 Definition

A strategic game (in short, a game) G = (N, {Si}i N, {pi}i N) is given by a set N = {1, . . . , n} of n > 1 players, a non-empty set of strategies Si for every player i N, and a payofffunction pi for every player i N with pi : S1 Sn R. The players choose their strategies simultaneously and every player i N aims at choosing a strategy si Si so as to maximize his individual payoffpi(s), where s = (s1, . . . , sn). We call s S1 Sn a joint strategy and denote its ith element by si. We denote (s1, . . . , si 1, si+1, . . . , sn) by s i and similarly with S i. Further, we write (s i, s i) for (s1, . . . , si 1, s i, si+1, . . . , sn), where we assume that s i Si. Sometimes, when focusing on player i we write (si, s i) instead of s. A joint strategy s is a Nash equilibrium if for all i {1, . . . , n} and s i Si, pi(si, s i) pi(s i, s i). Further, given a joint strategy s we call the sum SW(s) := Pn i=1 pi(s) the social welfare of s. When the social welfare of s is maximal we call s a social optimum. We shall also consider a cost variant of the games in which we use the cost functions, written as ci, instead of the payofffunctions pi. In such a setup the objective of each player is to minimize his costs, so a joint strategy s is a Nash equilibrium if for all i {1, . . . , n} and s i Si, ci(si, s i) ci(s i, s i). Further, instead of the social welfare one considers the social cost of s, defined as SC(s) := Pn i=1 ci(s). Given a strategic game G := (N, {Si}i N, {pi}i N) and α 0 we define the game G(α) := (N, {Si}i N, {ri}i N) by putting ri(s) := pi(s) + αSW(s). So when α > 0 the payoffof each player in the G(α) game depends on the social welfare of the players. G(α) is then an altruistic version of the game G. Suppose now that for some α 0 a pure Nash equilibrium of G(α) is a social optimum of G(α). Then we say that G is α-selfish. We define the selfishness level of G as

inf{α R+ | G is α-selfish}. (1)

Apt & Sch afer

Here we adopt the convention that the infimum of an empty set is . Further, we stipulate that the selfishness level of G is denoted by α+ iffthe selfishness level of G is α R+ but G is not α-selfish (equivalently, the infimum does not belong to the set). We show below (Theorem 2) that pathological infinite games exist for which the selfishness level is of this kind; none of the other studied games is of this type. We give some remarks before we proceed.

1. The above definitions refer to strategic games in which each player i maximizes his payofffunction pi and the social welfare of a joint strategy s is given by SW(s). These definitions obviously apply to the case when we use cost functions and the social cost.

2. Other definitions of an altruistic version of a game are conceivable and, depending on the underlying application, might seem more natural than the one we use here. However, we show in Section 2.3 that our definition is equivalent to several other models of altruism that have been proposed in the literature.

3. The selfishness level refers to the smallest α such that some Nash equilibrium in G(α) is also a social optimum. Alternatively, one might be interested in the smallest α such that every Nash equilibrium in G(α) corresponds to a social optimum. However, as explained in Section 5.2, this alternative notion is not always very meaningful.

4. The definition extends in the obvious way to other solution concepts (e.g., mixed or correlated equilibria) and other forms of games (e.g., subgame perfect equilibria in extensive games). We briefly comment on these extensions in Section 5.

Note that the social welfare of a joint strategy s in G(α) equals (1 + αn)SW(s), so the social optima of G and G(α) coincide. Hence we can replace in the definition of an α-selfish game the reference to a social optimum of G(α) by one to a social optimum of G. This is what we shall do in the proofs below. Intuitively, a low selfishness level means that the share of the social welfare needed to induce the players to choose a social optimum is small. This share can be viewed as an incentive needed to realize a social optimum. Let us illustrate this definition on various simple examples.

Example 1. Prisoner s Dilemma

Consider the Prisoner s Dilemma game G (on the left) and the resulting game G(α) for α = 1 (on the right). In the latter game the social optimum, (C, C), is also a Nash equilibrium. One can easily check that for α < 1, (C, C) is also a social optimum of G(α) but not a Nash equilibrium. So the selfishness level of this game is 1.

Example 2. Battle of the Sexes

Selfishness Level of Strategic Games

Here each Nash equilibrium is also a social optimum, so the selfishness level of this game is 0.

Example 3. Matching Pennies

Since the social welfare of each joint strategy is 0, for each α the game G(α) is identical to the original game in which no Nash equilibrium exists. So the selfishness level of this game is . More generally, the selfishness level of a constant sum game is 0 if it has a Nash equilibrium and otherwise it is .

Example 4. Game with a bad Nash equilibrium The following game results from equipping each player in the Matching Pennies game with a third strategy E (for edge):

Its unique Nash equilibrium is (E, E). It is easy to check that the selfishness level of this game is . (This is also an immediate consequence of Theorem 4 (iii) below.)

Example 5. Game with no Nash equilibrium Consider a game G on the left and the resulting game G(α) for α = 1 on the right.

The game G has no Nash equilibrium, while in the game G(1) the social optimum, (C, C), is also a Nash equilibrium. As in the Prisoner s Dilemma game one can easily check that for α < 1, (C, C) is also a social optimum of G(α) but not a Nash equilibrium. So the selfishness level of the game G is 1.

2.2 Properties

Recall that, given a finite game G that has a Nash equilibrium, its price of stability is the ratio SW(s)/SW(s ) where s is a social optimum and s is a Nash equilibrium with the highest social welfare in G. The price of anarchy is defined as the ratio SW(s)/SW(s ) where s is a social optimum and s is a Nash equilibrium with the lowest social welfare in G. So the price of stability of G is 1 iffits selfishness level is 0. However, in general there is no relation between these two notions. The following observation also shows that the selfishness level of a finite game can be an arbitrary real number.

Apt & Sch afer

Theorem 1. For every finite α > 0 and β > 1 there is a finite game whose selfishness level is α and whose price of stability is β.

Proof. Consider the following generalized form, which we denote by PD(α, β), of the Prisoner s Dilemma game G with x = α

In this game and in each game G(γ) with γ 0, (C, C) is the unique social optimum. To compute the selfishness level we need to consider a game G(γ) and stipulate that (C, C) is its Nash equilibrium. This leads to the inequality 1 + 2γ (γ + 1)(x + 1), from which it follows that γ x

1 x, i.e., γ α. So the selfishness level of G is α. Moreover, its price of stability is β, since (D, D) is the only Nash equilibrium.

The notion of the selfishness level is invariant under simple payofftransformations. It is a direct consequence of the following observation, where given a game G and a value a we denote by G + a (respectively, a G) the game obtained from G by adding to each payoff function the value a (respectively, by multiplying each payofffunction by a).

Proposition 1. Consider a game G and α 0.

(i) For every a, G is α-selfish iffG + a is α-selfish.

(ii) For every a > 0, G is α-selfish iffa G is α-selfish.

Proof. (i) It suffices to note that r[a]i(s) = ri(s)+αan+a, where ri and r[a]i are the payoff functions of player i in the games G(α) and (G + a)(α). So for every joint strategy s

s is a Nash equilibrium of G(α) iffit is a Nash equilibrium of (G + a)(α),

s is social optimum of G(α) iffit is a social optimum of (G + a)(α).

(ii) It suffices to note that for every a > 0, r[a]i(s) = ari(s), where this time r[a]i is the payofffunction of player i in the game (a G)(α), and argue as above.

Proposition 1 implies that the selfishness level is invariant under the game transformations of the form t(G) := a G+b, where a > 0. This is in contrast to the notions of the price of anarchy and the price of stability that are invariant only under the game transformations of the form t(G) := a G, where a > 0. Note that the selfishness level is not invariant under a multiplication of the payofffunctions by a value a 0. Indeed, for a = 0 each game a G has the selfishness level 0. For a < 0 take the game G from Example 4 whose selfishness level is . In the game a G the joint strategy (E, E) is both a Nash equilibrium and a social optimum, so the selfishness level of a G is 0. The above proposition also allows us to frame the notion of selfishness level in the following way. Suppose the original n-player game G is given to a game designer who has a fixed budget of SW(s) for each joint strategy s and that the selfishness level of G is α < . How should the game designer then distribute the budget of SW(s) for each joint strategy s

Selfishness Level of Strategic Games

among the players such that the resulting game has a Nash equilibrium that coincides with a social optimum? By scaling G(α) by the factor a := 1/(1 + αn) we ensure that for each joint strategy s its social welfare in the original game G and in a G(α) is the same. Using Proposition 1, we conclude that α is the smallest non-negative real such that a G(α) has a Nash equilibrium that is a social optimum. The game a G(α) can then be viewed as the intended transformation of G. That is, each payofffunction pi of the game G is transformed into the payofffunction

1 + αnpi(s) + α

1 + αn SW(s).

Let us return now to the borderline case of the selfishness level that we denoted by α+. We have the following result.

Theorem 2. For every α 0 there exists a game whose selfishness level is α+.

Proof. We first prove the result for α = 0. That is, we show that there exists a game that is α-selfish for every α > 0, but is not 0-selfish. To this end we use the games PD(α, β) defined in the proof of Theorem 1. We construct a strategic game G = (N, {Si}i N, {pi}i N) with two players N = {1, 2} by combining, for an arbitrary but fixed β > 1, infinitely many PD(α, β) games with α > 0 as follows: For each α > 0 we rename the strategies of the PD(α, β) game to, respectively, C(α) and D(α) and denote the corresponding payofffunctions by pα i . The set of strategies of each player i N is Si = {C(α) | α > 0} {D(α) | α > 0} and the payoffof i is defined as

pi(si, s i) :=

( pα i (si, s i) if {si, s i} {C(α), D(α)} for some α > 0 0 otherwise.

Every social optimum of G is of the form (C(α), C(α)), where α > 0. (Note that we exploit that β > 1 here.) By the argument given in the proof of Theorem 1, (C(α), C(α)) with α > 0 is a Nash equilibrium in the game G(α) because the deviations from C(α) to a strategy C(γ) or D(γ) with γ = α yield a payoffof 0. Thus, G is α-selfish for every α > 0. Finally, observe that G is not 0-selfish because every Nash equilibrium of G is of the form (D(α), D(α)), where α > 0. To deal with the general case we prove two claims that are of independent interest.

Claim 1. For every game G and α 0 there is a game G such that G (α) = G.

Proof. We define the payoffof player i in the game G by

p i(s) := pi(s) α

1 + nαSW(s),

Apt & Sch afer

where pi is his payoffin the game G. Denote by SW (s) the social welfare of a joint strategy s in the game G and by r i the payofffunction of player i in the game G (α). Then

r i(s) = p i(s) + αSW (s)

1 + nαSW(s) + α SW(s) nα

1 + nαSW(s)

= pi(s) + α α

Claim 2. For every game G and α, β 0

G(α + β) = G(α) β

Proof. Denote by SW (s) the social welfare of a joint strategy s in the game G(α), by pi, ri and r the payofffunctions of player i in the games G, G(α), and G(α)( β

1+nα). Then

ri(s) := pi(s) + αSW(s),

r i(s) = ri(s) + β

1 + nαSW (s)

= pi(s) + αSW(s) + β

1 + nα(SW(s) + nαSW(s))

= pi(s) + α + β

1 + nα + βnα

= pi(s) + (α + β)SW(s),

which proves the claim.

To prove the general case fix α 0 and β > 0 and take a game G whose selfishness level is 0+. By Claim 1 there is a game G such that G (α) = G. Then G is not α-selfish, since G is not 0-selfish. Further, by Claim 2

G (α + β) = G (α) β

But by its choice the game G is β

1+nα-selfish, so G is (α + β)-selfish, which concludes the proof.

Selfishness Level of Strategic Games

2.3 Alternative Definitions

Our definition of the selfishness level depends on the way the altruistic versions of the original game are defined. Three other models of altruism were proposed in the literature. As before, let G := (N, {Si}i N, {pi}i N) be a strategic game. Consider the following four definitions of altruistic versions of G:

Model A (Elias et al., 2010): For every α 0, G(α) := (N, {Si}i N, {rα i }i N) with

rα i (s) = pi(s) + αSW(s) i N. (2)

Model B (Chen & Kempe, 2008): For every β [0, 1], G(β) := (N, {Si}i N, {rβ i }i N) with rβ i (s) = (1 β)pi(s) + β

n SW(s) i N. (3)

Model C (Chen et al., 2011): For every γ [0, 1], G(γ) := (N, {Si}i N, {rγ i }i N) with

rγ i (s) = (1 γ)pi(s) + γSW(s) i N. (4)

Model D (Caragiannis et al., 2010): For every δ [0, 1], G(δ) := (N, {Si}i N, {rδ i }i N) with rγ i (s) = (1 δ)pi(s) + δ(SW(s) pi(s)) i N. (5)

Our selfishness level notion for Model A extends to Models B, C and D in the obvious way: We say that G is β-selfish for some β [0, 1] iffa pure Nash equilibrium of the altruistic version G(β) is also a social optimum. The selfishness level of G with respect to Model B is then defined as the infimum over all β [0, 1] such that G is β-selfish. The respective notions for Models C and D are defined analogously. The following theorem shows that the selfishness level of a game with respect to Models A, B, C and D relate to each other via simple transformations. (Note that for Model D this transformation only applies for δ [0, 1

Theorem 3. Consider a strategic game G := (N, {Si}i N, {pi}i N) and its altruistic versions defined according to Models A, B, C and D above.

(i) G is α-selfish with α R+ iffG is β-selfish with β = αn

1+αn [0, 1].

(ii) G is α-selfish with α R+ iffG is γ-selfish with γ = α

1+α [0, 1].

(iii) G is α-selfish with α R+ iffG is δ-selfish with δ = α

Proof. We prove the following more general claim. Fix x, y > 0. For every λ [0, 1

x], define G(λ) := (N, {Si}i N, {rλ i }i N) with

rλ i (s) = (1 xλ)pi(s) + λ

y SW(s). (6)

We show that G is α-selfish for α 0 iffG is λ-selfish for λ = αy

1+αxy [0, 1

Apt & Sch afer

By substituting λ = αy

1+αxy in (6), we obtain

rλ i (s) = 1

1 + αxypi(s) + α

1 + αxy SW(s) = 1

1 + αxyrα i (s).

As a consequence, since 1

1+αxy > 0 for every α 0 the pure Nash equilibria and social optima, respectively, of G(λ) and 1

1+αxy G(α) coincide. Thus, G is λ-selfish iff 1

1+αxy G is α-selfish. Also, it follows from Proposition 1 that 1

1+αxy G is α-selfish iffG is α-selfish. Further, note that

1 + αxy = 1

That is, the selfishness level of G with respect to Model A is iffthe selfishness level of G with respect to G(λ) is 1

x. Now, (i) follows from the above with x = 1 and y = n, (ii) follows with x = y = 1 and (iii) follows with x = 2 and y = 1.

3. A Characterization Result

We now characterize the games with a finite selfishness level. To this end we shall need the following notion. We call a social optimum s stable if for all i N and s i Si the following holds:

if (s i, s i) is a social optimum, then pi(si, s i) pi(s i, s i).

In other words, a social optimum is stable if no player is better offby unilaterally deviating to another social optimum. It will turn out that in order to determine the selfishness level of a game we need to consider deviations from its stable social optima. Consider a deviation s i of player i from a stable social optimum s. If player i is better offby deviating to s i, then by definition the social welfare decreases, i.e., SW(si, s i) SW(s i, s i) > 0. If in the original game this decrease is small, while the gain for player i is large, then strategy s i is an attractive and socially acceptable option for player i. We define player i s appeal factor of strategy s i given the social optimum s as

AFi(s i, s) := pi(s i, s i) pi(si, s i)

SW(si, s i) SW(s i, s i).

In what follows we shall characterize the selfishness level in terms of bounds on the appeal factors of profitable deviations from a stable social optimum. First, note the following properties of social optima.

Lemma 1. Consider a strategic game G := (N, {Si}i N, {pi}i N) and α 0.

(i) If s is both a Nash equilibrium of G(α) and a social optimum of G, then s is a stable social optimum of G.

Selfishness Level of Strategic Games

(ii) If s is a stable social optimum of G, then s is a Nash equilibrium of G(α) ifffor all i N and s i Ui(s), α AFi(s i, s), where

Ui(s) := {s i Si | pi(s i, s i) > pi(si, s i)}. (7)

The set Ui(s), with the > sign replaced by , is called an upper contour set (see, e.g., Ritzberger, 2002, p. 193). Note that if s is a stable social optimum, then s i Ui(s) implies that SW(si, s i) > SW(s i, s i).

Proof. (i) Suppose that s is both a Nash equilibrium of G(α) and a social optimum of G. Consider some joint strategy (s i, s i) that is a social optimum. By the definition of a Nash equilibrium pi(si, s i) + αSW(si, s i) pi(s i, s i) + αSW(s i, s i),

so pi(si, s i) pi(s i, s i), as desired. (ii) Suppose that s is a stable social optimum of G. Then s is a Nash equilibrium of G(α) ifffor all i N and s i Si

pi(si, s i) + αSW(si, s i) pi(s i, s i) + αSW(s i, s i). (8)

If pi(si, s i) pi(s i, s i), then (8) holds for all α 0 since s is a social optimum. If pi(s i, s i) > pi(si, s i), then, since s is a stable social optimum of G, we have SW(si, s i) > SW(s i, s i). So (8) holds for all i N and s i Si iff

α pi(s i, s i) pi(si, s i)

SW(si, s i) SW(s i, s i) = AFi(s i, s)

holds for all i N and s i Ui(s).

This leads us to the following result.

Theorem 4. Consider a strategic game G := (N, {Si}i N, {pi}i N).

(i) The selfishness level of G is finite iffa stable social optimum s exists for which α(s) := supi N, s i Ui(s) AFi(s i, s) is finite.

(ii) If the selfishness level of G is finite, then it equals mins SSO α(s), where SSO is the set of stable social optima.

(iii) If G is finite, then its selfishness level is finite iffit has a stable social optimum. In particular, if G has a unique social optimum, then its selfishness level is finite.

(iv) If β > α 0 and G is α-selfish, then G is β-selfish.

Proof. (i) and (iv) follow by Lemma 1, (ii) by (i) and Lemma 1, and (iii) by (i).

Using the above theorem we now exhibit a class of games for n players for which the selfishness level is unbounded. In fact, the following more general result holds.

Apt & Sch afer

Theorem 5. For each function f : N R+ there exists a class of games for n players, where n > 1, such that the selfishness level of a game for n players equals f(n).

Proof. Assume n > 1 players and that each player has two strategies, 1 and 0. Denote by 1 the joint strategy in which each strategy equals 1 and by 1 i the joint strategy of the opponents of player i in which each entry equals 1. The payofffor each player i is defined as follows:

0 if s = 1 f(n) if si = 0 and j < i, sj = 1 f(n)+1

n 1 otherwise.

So when s = 1, pi(s) = f(n) if i is the smallest index of a player with si = 0 and otherwise pi(s) = f(n)+1

n 1 . Note that SW(1) = 0 and SW(s) = 1 if s = 1. So 1 is a unique social optimum. We have pi(0, 1 i) pi(1) = f(n) and SW(1) SW(0, 1 i) = 1. So by Theorem 4 (ii) the selfishness level equals f(n).

4. Examples

We now use the above characterization result to determine or compute an upper bound on the selfishness level of some selected games. First, we exhibit a well-known class of games (see Monderer & Shapley, 1996) for which the selfishness level is finite.

4.1 Ordinal Potential Games

Given a game G := (N, {Si}i N, {pi}i N), a function P : S1 Sn R is called an ordinal potential function for G if for all i N, s i S i and si, s i Si, pi(si, s i) > pi(s i, s i) iffP(si, s i) > P(s i, s i). A game that possesses an ordinal potential function is called an ordinal potential game.

Theorem 6. Every finite ordinal potential game has a finite selfishness level.

Proof. Each social optimum with the largest potential is a stable social optimum. So the claim follows by Theorem 4 (ii).

In particular, every finite congestion game (see Rosenthal, 1973) has a finite selfishness level. We shall derive explicit bounds for two special cases of these games in Sections 4.3 and 4.4.

4.2 Weakly Acyclic Games

Given a game G := (N, {Si}i N, {pi}i N), a path in S1 Sn is a sequence (s1, s2, . . . ) of joint strategies such that for every k > 1 there is a player i such that sk = (s i, sk 1 i ) for some s i = sk 1 i (see, e.g., Monderer & Shapley, 1996). A path is called an improvement path if it is maximal and for all k > 1, pi(sk) > pi(sk 1), where i is the player who deviated from sk 1. A game G has the finite improvement property (FIP) if every improvement path is finite. A game G is called weakly acyclic if for every joint strategy there exists a finite improvement path that starts at it (see, e.g., Milchtaich, 1996; Young, 1993).

Selfishness Level of Strategic Games

Finite games that have the FIP coincide with the ordinal potential games. So by Theorem 6 these games have a finite selfishness level. In contrast, the selfishness level of a weakly acyclic game can be infinite. Indeed, the following game is easily seen to be weakly acyclic:

Yet, on the account of Theorem 4 (iii), its selfishness level is infinite.

4.3 Fair Cost Sharing Games

In this and the next subsection we consider cost-minimization instead of payoff-maximization games. Recall that in these games each player i wants to minimize his individual cost function ci and that the social cost is defined as SC(s) = P i ci(s). In a fair cost sharing game (see, e.g., Anshelevich et al., 2008) players allocate facilities and share the cost of the used facilities in a fair manner. Formally, a fair cost sharing game is given by G = (N, E, {Si}i N, {ce}e E), where N = {1, . . . , n} is the set of players, E is the set of facilities, Si 2E is the set of facility subsets available to player i, and ce R+ is the cost of facility e E. It is called a singleton cost sharing game if for every i N and for every si Si: |si| = 1. For a joint strategy s S1 Sn let xe(s) be the number of players using facility e E, i.e., xe(s) = |{i N | e si}|. The cost of a facility e E is evenly shared among the players using it. That is, the cost of player i is defined as ci(s) = P e si ce/xe(s). We first consider singleton cost sharing games. Let cmax = maxe E ce and cmin = mine E ce refer to the maximum and minimum costs of the facilities, respectively.

Proposition 2. The selfishness level of a singleton cost sharing game is at most max{0, 1

cmin 1}. Moreover, this bound is tight.

This result should be contrasted with the price of stability of Hn and the price of anarchy of n for cost sharing games (Anshelevich et al., 2008). Cost sharing games admit an exact potential function and thus by Theorem 6 their selfishness level is finite. However, as the tight example given in the proof of Proposition 2 below shows, the selfishness level can be arbitrarily large (as cmax/cmin ) even for n = 2 players and two facilities. In order to prove Proposition 2, we first derive an expression of the appeal factor for arbitrary fair cost sharing games, which we then specialize to singleton cost sharing games to prove the claim. Let s be a stable social optimum. Note that s exists by Theorem 4 (iii) and Theorem 6. Because we consider a cost minimization game here the appeal factor of player i is defined as

AFi(s i, s) := ci(si, s i) ci(s i, s i)

SC(s i, s i) SC(si, s i) (9)

and the condition in Theorem 4 (i) reads α(s) := maxi N, s i Ui(s) AFi(s i, s), where Ui(s) := {s i Si | ci(s i, s i) < ci(si, s i)}.

Apt & Sch afer

Fix some player i and let s = (s i, s i) for some s i Ui(s). We use xe and x e to refer to xe(s) and xe(s ), respectively. Note that

xe + 1 if e s i \ si, xe 1 if e si \ s i, xe otherwise.

ci(s) ci(s i, s i) = X

xe + 1. (10)

Further, it is not difficult to verify that

SC(s i, s i) SC(s) = X

e s i\si: xe=0 ce X

e si\s i: xe=1 ce. (11)

AFi(s i, s) =

P e si\s i: xe 2 ce

xe P e s i\si: xe 1 ce

P e s i\si: xe=0 ce P e si\s i: xe=1 ce 1. (12)

We use the above to prove Proposition 2.

Proof of Proposition 2. Let s be a stable social optimum (which exists by Theorem 4 (iii) and Theorem 6). If Ui(s) = for every i N then the selfishness level is 0 by Theorem 4 (ii). Otherwise, there is some player i N with Ui(s) = . Recall that in a singleton cost sharing game, each player s strategy set consists of singleton facility sets. Let si = {e} and s i = {e } be the singleton sets of the facilities chosen by player i in s and in s = (s i, s i) with s i Ui(s). Clearly, e = e . Note that SC(s i, s i) SC(s) must be positive because s i Ui(s) and thus (11) implies that xe = 0. Therefore, (10) reduces to ci(s) ci(s i, s i) = ce/xe ce . If xe = 1 then ce > ce because s i Ui(s). But this is a contradiction to the assumption that SC(s i, s i) SC(s) = ce ce > 0. Thus xe 2. Note that this also implies that ce > 2ce and thus cmax > 2cmin. Using (12), we obtain

AFi(s i, s) =

The claim now follows by Theorem 4 (ii). The following example shows that this bound is tight. Suppose N = {1, 2}, E = {e1, e2}, S1 = {{e1}}, S2 = {{e1}, {e2}}, ce1 = cmax and ce2 = cmin with cmax > 2cmin. The joint strategy s = ({e1}, {e1}) is the unique social optimum with SC(s) = cmax and c2(s) = cmax/2. Suppose player 2 deviates to s 2 = {e2}. Then SC(s 2, s1) = cmax +cmin and c2(s 2, s1) = cmin. Thus AFi(s 2, s) = (1

2cmax cmin)/cmin = 1

2cmax/cmin 1.

Selfishness Level of Strategic Games

The following example shows that a bound similar to the one above, i.e., bounding the selfishness level in terms of the ratio cmax/cmin, does not hold for arbitrary fair cost sharing games. In particular, it shows that the minimum difference between any two costs of facilities (here ε) must enter a bound of the selfishness level for arbitrary fair cost sharing games.

Example 6. Let N = {1, 2}, E = {e1, e2, e3}, S1 = {{e1}}, S2 = {{e1, e3}, {e2}}, ce1 = cmax, ce2 = cmin + ε for some ε > 0 and ce3 = cmin. The joint strategy s = ({e1}, {e1, e3}) is the unique social optimum with SC(s) = cmax + cmin and c2(s) = cmax/2 + cmin. Suppose player 2 deviates to s 2 = {e2}. Then SC(s 2, s1) = cmax + cmin + ε and c2(s 2, s1) = cmin + ε. Thus AFi(s 2, s) = (1

2cmax ε)/ε = 1

2cmax/ε 1, which approaches as ε 0.

We next derive a bound for arbitrary fair cost sharing games with non-negative integer costs. Let L be the maximum number of facilities that any player can choose, i.e., L := maxi N,si Si |si|.

Proposition 3. The selfishness level of a fair cost sharing game with non-negative integer costs is at most max{0, 1

2Lcmax 1}. Moreover, this bound is tight.

Proof. Let s be a stable social optimum. As in the proof of Proposition 2, if Ui(s) = for every i N then the selfishness level is 0 by Theorem 4 (ii). Otherwise, there is some player i N with Ui(s) = . Let s = (s i, s i) for some s i Ui(s). Note that the denominator of the appeal factor in (12) is at least 1 because s is stable, s i Ui(s) and ce N for each e E. Thus

AFi(s i, s) =

P e si\s i: xe 2 ce

xe P e s i\si: xe 1 ce

P e s i\si: xe=0 ce P e si\s i: xe=1 ce 1

e si\s i: xe 2

The claim follows by Theorem 4 (ii). The following example shows that the bound is tight. Suppose we are given L and cmax. Let N = {1, . . . , n} and E = {e1, . . . , en} where n = L + 1. Define Si = {{ei}} for every i N \ {n} and Sn = {{e1, . . . , en 1}, {en}}. Let cei = cmax for every i N \ {n} and cen = 1. The joint strategy s = ({e1}, . . . , {en 1}, {e1, . . . , en 1}) is the unique social optimum with SC(s) = (n 1)cmax and cn(s) = (n 1)cmax/2. Suppose player n deviates to s n = {en}. Then SC(s n, s n) = (n 1)cmax + 1 and cn(s n, s n) = 1. Thus AFi(s n, s) = 1

2(n 1)cmax 1 = 1

Remark 1. We can bound the selfishness level of a fair cost sharing game with non-negative rational costs ce Q+ for every facility e E by using Proposition 3 and the following scaling argument: Simply scale all costs to integers, e.g., by multiplying them with the least common multiplier q N of the denominators. Note that this scaling does not change the selfishness level of the game by Proposition 1. However, it does change the maximum facility cost and thus q enters the bound. Also note that this scaling implicitly takes care of the effect observed in Example 6: Suppose that cmax and cmin are integers and ǫ = 1/q for some q N. Then all costs are multiplied by q and Proposition 3 yields a (non-tight) bound of qcmax 1 = cmax/ǫ 1 on the selfishness level, which approaches as q .

Apt & Sch afer

4.4 Linear Congestion Games

In a congestion game G := (N, E, {Si}i N, {de}e E) we are given a set of players N = {1, . . . , n}, a set of facilities E with a delay function de : N R+ for every facility e E, and a strategy set Si 2E for every player i N. For a joint strategy s S1 Sn, define xe(s) as the number of players using facility e E, i.e., xe(s) = |{i N | e si}|. The goal of a player is to minimize his individual cost ci(s) = P e si de(xe(s)). Here we call a congestion game symmetric if there is some common strategy set S 2E

such that Si = S for all i. It is singleton if every strategy si Si is a singleton set, i.e., for every i N and for every si Si, |si| = 1. In a linear congestion game, the delay function of every facility e E is of the form de(x) = aex + be, where ae, be R+ are non-negative real numbers. We first derive a bound on the selfishness level for symmetric singleton linear congestion games. As it turns out, a bound similar to the one for singleton cost sharing games does not extend to symmetric singleton linear congestion games. Instead, the crucial insight here is that the selfishness level depends on the discrepancy between facilities in a stable social optimum. We make this notion more precise. Let s be a stable social optimum and let xe refer to xe(s). Define the discrepancy between two facilities e and e with ae + ae > 0 under s as

δ(xe, xe ) = 2aexe + be

ae + ae 2ae xe + be

ae + ae . (13)

We show below that δ(xe, xe ) [ 1, 1]. Define δmax(s) as the maximum discrepancy between any two facilities e and e under s with ae + ae > 0 and δ(xe, xe ) < 1; more formally, let

δmax(s) = max e,e E{δ(xe, xe ) | ae + ae > 0 and δ(xe, xe ) < 1}.

Let δmax be the maximum discrepancy over all stable social optima, i.e., δmax = maxs SSO δmax(s). Further, let max := maxe E(ae + be) and min := mine E(ae + be). Moreover, let amin be the minimum non-zero coefficient of a latency function, i.e., amin = mine E:ae>0 ae.

Proposition 4. The selfishness level of a symmetric singleton linear congestion game is at most

(1 δmax)amin 1

Moreover, this bound is tight.

We first prove that the discrepancy between two facilities is bounded:

Claim 3. Let s be a social optimum and e, e E be two facilities with ae + ae > 0. Then the discrepancy between e and e under s satisfies δ(xe, xe ) [ 1, 1].

Proof. Let t = xe + xe be the total number of players on facilities e and e under s. Note that since s is a social optimum and strategy sets are symmetric, t is distributed among xe and xe such that the social cost of these two facilities is minimized. Said differently, xe = x minimizes the function

f(x, t) := aex2 + bex + ae (t x)2 + be (t x).

Selfishness Level of Strategic Games

It is not hard to verify that the minimum of f(x, t) (for fixed t) is attained at the (not necessarily integral) point

x0 := 2ae t be + be

2(ae + ae ) .

Because f(x, t) is a parabola with its minimum at x0, the integral point xe that minimizes f(x, t) is given by the point obtained by rounding x0 to the nearest integer. Let xe := x0+ 1

2δ be this point, where δ = δ(xe, xe ) [ 1, 1], and xe = t xe. Note that the choice of δ is unique, unless x0 is half-integral in which case δ { 1, 1}. Solving these equations for δ yields the definition in (13).

Proof of Proposition 4. Let s be a stable social optimum. Note that s exists by Theorem 4 (iii) and Theorem 6. If Ui(s) = for every i N then the selfishness level is 0 by Theorem 4 (ii). Otherwise, there is some player i N with Ui(s) = . Let s = (s i, s i) for some s i Ui(s). We use xe and x e to refer to xe(s) and xe(s ) for every facility e E, respectively. Note that for every e E we have

xe + 1 if e s i \ si, xe 1 if e si \ s i, xe otherwise.

Let si = {e} and s i = {e } be the sets of facilities chosen by player i in s and s , respectively. Exploiting (14), we obtain

ci(si, s i) ci(s i, s i) = aexe + be ae (xe + 1) be . (15)

SC(s i, s i) SC(si, s i) = ae (2xe + 1) + be ae(2xe 1) be. (16)

Note that we have ci(si, s i) ci(s i, s i) > 0 because s i Ui(s) and by the definition of Ui(s) in (7). Further, SC(s i, s i) SC(si, s i) > 0 because s is a stable social optimum and s i Ui(s). Thus, it must hold that ae + ae > 0; otherwise ae = ae = 0 and (15) and (16) yield a contradiction. Let δ = δ(xe, xe ) be the discrepancy between e and e under s. Note that δ [ 1, 1] by Claim 3. Using the definition of δ in (13), we can rewrite (15) and (16) as

ci(si, s i) ci(s i, s i) = 1

2(ae + ae )δ + 1

and SC(s i, s i) SC(si, s i) = (1 δ)(ae + ae ).

We conclude that δ = 1. Thus,

AFi(s i, s) = 1

2 (ae + ae )δ + be be 2ae

(1 δ)(ae + ae ) = 1

2 (ae + be) (ae + be )

(1 δ)(ae + ae ) 1

(1 δmax)amin 1

Apt & Sch afer

The claim now follows by Theorem 4 (ii). The following example shows that this bound is tight even for n = 2 players and two facilities. Let N = {1, 2}, E = {e, e } and S1 = S2 = {{e}, {e }}. Suppose we are given δ [0, 1) and ae R+. Define de(x) = (2 + δ)ae and de (x) = ae x. The joint strategy s = ({e}, {e }) is the unique social optimum with SC(s) = (3+ δ)ae . Further c1(s) = (2+ δ)ae and c2(s) = ae . Suppose player 1 deviates to s 1 = {e }. Then SC(s 1, s2) = 4ae and c1(s 1, s2) = 2ae . Thus AFi(s 1, s) = δ/(1 δ), which matches precisely the upper bound given above. The case δ [ 1, 0] is proven analogously.

Observe that the selfishness level depends on the ratio ( max min)/amin and 1/(1 δmax). In particular, the selfishness level becomes arbitrarily large as δmax approaches 1. We next derive a bound for the selfishness level of arbitrary congestion games with linear delay functions and non-negative integer coefficients, i.e., de(x) = aex + be with ae, be N for every e E. Let L be the maximum number of facilities that any player can choose, i.e., L := maxi N,si Si |si|.

Proposition 5. The selfishness level of a linear congestion game with non-negative integer coefficients is at most max{0, 1

2(L max min 1)}. Moreover, this bound is tight.

For linear congestion games, the price of anarchy is known to be 5

2 (see Christodoulou & Koutsoupias, 2005; Awerbuch, Azar, & Epstein, 2013). Our bound shows that the selfishness level depends on the maximum number of facilities in a strategy set and the magnitude of the coefficients of the delay functions.

Proof of Proposition 5. Let s be a stable social optimum. Note that s exists by Theorem 4 (iii) and Theorem 6. If Ui(s) = for every i N then the selfishness level is 0 by Theorem 4 (ii). Otherwise, there is some player i N with Ui(s) = . Let s = (s i, s i) for some s i Ui(s). We use xe and x e to refer to xe(s) and xe(s ), respectively. Exploiting (14), we obtain

ci(si, s i) ci(s i, s i) = X

(aexe + be) X

e s i\si (ae(xe + 1) + be).

SC(s i, s i) SC(si, s i) = X

e s i\si (xe + 1)(ae(xe + 1) + be) xe(aexe + be)

(xe 1)(ae(xe 1) + be) xe(aexe + be)

e s i\si (ae(2xe + 1) + be) X

(ae(2xe 1) + be).

Given a congestion vector x = (xe)e E, define P(x) := P e si\s i(aexe + be) and Q(x) := P e s i\si(ae(xe + 1) + be). Note that P(x) and Q(x) are integers because ae, be N for

Selfishness Level of Strategic Games

every facility e E. Note that with these definitions, P(1) = P e si\s i(ae + be) and Q(0) = P e s i\si(ae + be). We have

AFi(s i, s) = P(x) Q(x)

2Q(x) Q(0) 2P(x) + P(1).

Because s i Ui(s), we know that P(x) > Q(x) and 2Q(x) Q(0) > 2P(x) P(1). So we obtain Q(x) + 1 P(x) Q(x) + 1

2(P(1) Q(0) 1).

Exploiting these inequalities, we obtain

AFi(s i, s) 1

2(P(1) Q(0) 1) = 1

(ae + be) X

e s i\si (ae + be) 1

2(|si \ s i| max |s i \ si| min 1).

Note that |s i \ si| 1; otherwise, s i si and thus SC(s i, s i) SC(s) which contradicts s i Ui(s). The above expression is thus at most 1

2(L max min 1). The claim now follows by Theorem 4 (ii). The following example shows that this bound is tight. Fix L, max and min such that (2n 1) min = L max + 1 for some integer n. Consider a congestion game with N = {1, . . . , n} and E = {e1, . . . , e L+1}. Define Si = {{e L+1}} for every i N \ {n} and Sn = {{e1, . . . , e L}, {e L+1}}. Let de L+1(x) = minx and dei(x) = max for every i {1, . . . , L}. For the joint strategy s = ({e L+1}, . . . , {e L+1}, {e1, . . . , e L}) we have SC(s) = min(n 1)2 + L max and cn(s) = L max. If player n deviates to s n = {e L+1} we have SC(s n, s n) = minn2 = min(n 1)2 + min(2n 1) and cn(s n, s n) = minn. Exploiting that (2n 1) min = L max + 1, we conclude that SC(s) < SC(s n, s n) and cn(s) > cn(s n, s n) (for n 3). Thus, s is a social optimum and s n Ui(s). We obtain

AFn(s n, s) = L max minn

min(2n 1) L max = L max 1

2(L max + min + 1)

2(L max min 1).

Remark 2. We can use Proposition 5 and the scaling argument outlined in Remark 1 to derive bounds on the selfishness level of congestion games with linear delay functions and non-negative rational coefficients.

4.5 Prisoner s Dilemma for n Players

We assume that each player i N = {1, . . . , n} has two strategies, 1 (cooperate) and 0 (defect). We put pi(s) := csi + b P j =i sj, where b > c. Intuitively, b stands for the benefit of cooperation and c for the cost of cooperation.

Proposition 6. The selfishness level of the n-players Prisoner s Dilemma game is c

Apt & Sch afer

Intuitively, this means that when the number of players in the Prisoner s Dilemma game increases, a smaller share of the social welfare is needed to resolve the underlying conflict. The same observation holds for the value of the benefit. That is, the acuteness of the dilemma diminishes with the number of players and also diminishes when the value of the benefit grows. The formal reason is that the appeal factor of each unilateral deviation from the social optimum is inversely proportional to the number of players and inversely proportional to the benefit.

Proof. In this game s = 1 is the unique social optimum, with for each i N, pi(s) = bn (b + c) and SW(s) = bn2 (b + c)n. Consider now the joint strategy (s i, s i) in which player i deviates to the strategy s i = 0. We have then pi(s i, s i) = bn b and SW(s i, s i) = bn2 (b + c)n + c b(n 1). Hence AFi(s i, s) = c

b(n 1) c. The claim now follows by Theorem 4 (ii).

In particular, for n = b = 2 and c = 1 we get the original Prisoner s Dilemma game considered in Example 1 and as already argued there the selfishness level is then 1.

4.6 Public Goods

We consider the public goods game with n players. Every player i N = {1, . . . , n} chooses an amount si [0, b] that he contributes to a public good, where b R+ is the budget. The game designer collects the individual contributions of all players, multiplies their sum by c > 1 and distributes the resulting amount evenly among all players. The payoffof player i is thus pi(s) := b si + c

n P j N sj.

Proposition 7. The selfishness level of the n-players public goods game is max 0, 1 c

In this game, every player has an incentive to free ride by contributing 0 to the public good (which is a dominant strategy if c n). This is exactly as in the n-players Prisoner s Dilemma game (where defect is a dominant strategy if c > 0). However, the above proposition reveals that for fixed c, in contrast to the Prisoner s Dilemma game, this temptation becomes stronger as the number of players increases. Also, for a fixed number of players this temptation becomes weaker as c increases.

Proof of Proposition 7. Note that SW(s) = bn+(c 1) P i N si. The unique social optimum of this game is therefore s = b with pi(s) = cb for every i N and SW(s) = cbn. Suppose player i deviates from s by choosing s i [0, b). Then pi(s i, s i) = cb+(1 c

n)(b s i). Thus,

pi(s i, s i) pi(s) = (1 c

n)(b s i) and SW(s) SW(s i, s i) = (c 1)(b s i).

n 0 then Ui(s) = and the selfishness level is zero. Otherwise, 1 c

n > 0 and Ui(s) = [0, b). We conclude that in this case AFi(s i, s) = (1 c

n)/(c 1) for every s i Ui(s). The claim now follows by Theorem 4 (ii).

Selfishness Level of Strategic Games

4.7 Traveler s Dilemma

This is a strategic game discussed by Basu (1994) with two players N = {1, 2}, strategy set Si = {2, . . . , 100} for every player i, and payofffunction pi for every i defined as

si if si = s i si + b if si < s i s i b otherwise,

where b > 1 is the bonus.

Proposition 8. The selfishness level of the Traveler s Dilemma game is b 1

Proof. The unique social optimum of this game is s = (100, 100), while (2, 2) is its unique Nash equilibrium. If player i deviates from s to a strategy s i 99, while the other player remains at 100, the respective payoffs become s i+b and s i b, so the social welfare becomes 2s i. So AFi(s i, s) = (s i +b 100)/(200 2s i). The maximum, b 1

2 , is reached when s i = 99. So the claim follows by Theorem 4 (ii).

Intuitively, this means that as the bonus b increases a larger share of the social welfare needs to be used to ensure cooperation.

4.8 Tragedy of the Commons

Assume that each player i N = {1, . . . , n} has the real interval [0, 1] as its set of strategies. Each player s strategy is his chosen fraction of a common resource. Let (see Osborne, 2005, Exercise 63.1 and Tardos & Vazirani, 2007, pp. 6 7):

pi(s) := max 0, si 1

This payofffunction reflects the fact that player s enjoyment of the common resource depends positively from his chosen fraction of the resource and negatively from the total fraction of the common resource used by all players. Additionally, if the total fraction of the common resource by all players exceeds a feasible level, here 1, then player s enjoyment of the resource becomes zero.

Proposition 9. The selfishness level of the n-players Tragedy of the Commons game is .

Intuitively, this result means that in this game no matter how much we involve the players in sharing the social welfare we cannot achieve that they will select a social optimum.

Proof. We first determine the stable social optima of this game. Fix a joint strategy s and let t := P j N sj. If t > 1, then the social welfare is 0. So assume that t 1. Then SW(s) = t(1 t). This expression becomes maximal precisely when t = 1

2 and then it equals 1

4. So this game has infinitely many social optima and each of them is stable. Take now a stable social optimum s. So P j N sj = 1

2. Fix i {1, . . . , n}. Denote si by a and consider a strategy x of player i such that pi(x, s i) > pi(a, s i). Then P j =i sj +x = 1

2, so SW(a, s i) > SW(x, s i).

Apt & Sch afer

We have pi(a, s i) = a

2 and SW(a, s i) = 1

4. Further, pi(x, s i) > pi(a, s i) implies P j =i sj + x < 1 and hence

pi(x, s i) = x(a + 1

2 x) and SW(x, s i) = (1

2 a + x)(1 1

2 + a x) = 1

Also x = a. Hence

AFi(x, s) = pi(x, s i) pi(a, s i)

SW(a, s i) SW(x, s i) = (a x)(x 1

(a x)2 = x 1

a x = 1 + a 1

Since pi(x, s i) pi(a, s i) = (a x)(x 1

2) we have pi(x, s i) > pi(a, s i) iffa < x < 1

2 or a > x > 1

2, since P j =i sj+a = 1

2. So the conjunction of pi(x, s i) > pi(a, s i) and SW(x, s i) < SW(a, s i) holds iffa < x < 1

2. Now maxa<x< 1

2 AFi(x, s) = . But s was an arbitrary stable social optimum, so the claim follows by Theorem 4 (i).

4.9 Cournot Competition

We consider Cournot competition for n firms with a linear inverse demand function and constant returns to scale (see, e.g., Jehle & Reny, 2011, pp. 174 175). So we assume that each player i N = {1, . . . , n} has a strategy set Si = R+ and payofffunction pi(s) := si(a b P j N sj) csi for some given a, b, c, where a > c 0 and b > 0. The price of the product is represented by the expression a b P j N sj and the production cost corresponding to the production level si by csi. In what follows we rewrite the payofffunction as pi(s) := si(d b P j N sj), where d := a c. Note that the payoffs can be negative, which was not the case in the tragedy of the commons game. Still the proofs are very similar for both games.

Proposition 10. The selfishness level of the n-players Cournot competition game is .

Proof. We first determine the stable social optima of this game. Fix a joint strategy s and let t := P j N sj. Then SW(s) = t(d bt). This expression becomes maximal precisely when t = d

2b. So this game has infinitely many social optima and each of them is stable. Take now a stable social optimum s. So P j N sj = d

2b. Fix i N. Let u := P j =i sj. For every strategy z of player i

pi(z, s i) = bz2 + (d bu)z and SW(z, s i) = bz2 + (d 2bu)z + u(d bu).

Denote now si by y and consider a strategy x of player i such that pi(x, s i) > pi(y, s i). Then u + x = d

2b, so SW(y, s i) > SW(x, s i). We have

pi(x, s i) pi(y, s i) = b(x2 y2) + (d bu)(x y)

= b(x y)(x + y + u d

b ) = b(x y)(x d

where the last equality holds since u d

2b) on the account of the equality u+y = d

2b. Further,

SW(y, s i) SW(x, s i) = b(x2 y2) (d 2bu)(x y)

= b(x y)(x + y + 2u d

b) = b(x y)2,

Selfishness Level of Strategic Games

where the last equality holds since 2u d

b = 2y on the account of the equality u + y = d

2b. We have x = y. Hence

AFi(x, s) = pi(x, s i) pi(y, s i)

SW(y, s i) SW(x, s i) = x d

x y = 1 + y d

Since pi(x, s i) pi(y, s i) = b(y x)(x d

2b) we have pi(x, s i) pi(y, s i) > 0 iffy < x < d

2b or y > x > d

2b. But y d

2b, since u + y = d

2b. So the conjunction of pi(x, s i) > pi(y, s i) and SW(x, s i) > SW(y, s i) holds iffy < x < d

2b. Now supy<x< d

2b AFi(x, s) = . But s was an arbitrary stable social optimum, so the claim follows by Theorem 4 (i).

This proof shows that for every stable social optimum s, for every player there exist deviating strategies with an arbitrary high appeal factor. In fact, limx y+ AFi(x, s) = , i.e., the appeal factor of the deviating strategy x converges to when it converges from the right to the original strategy y in s.

4.10 Bertrand Competition

Next, we consider Bertrand competition, a game concerned with a simultaneous selection of prices for the same product by two firms (see, e.g., Jehle & Reny, 2011, pp. 175 177). The product is then sold by the firm that chose the lower price. In the case of a tie the product is sold by both firms and the profits are split. We assume that each firm has identical marginal costs c > 0 and no fixed cost, and that each strategy set Si equals [c, a

b), where c < a

b. The payofffunction for player i {1, 2} is given by

pi(si, s3 i) :=

(si c)(a bsi) if c < si < s3 i 1

2(si c)(a bsi) if c < si = s3 i 0 otherwise.

Proposition 11. The selfishness level of the Bertrand competition game is .

Proof. Let d := a+bc

2b . If SW(s) > 0, then SW(s) = (s0 c)(a bs0), where s0 := min(s1, s2). Note that d (c, a

b ), since by the assumption bc < a. Hence s is a social optimum iff min(s1, s2) = d. If s is a social optimum with s1 = s2, then player i with the larger si can profitably deviate to s3 i (that equals d), while (s3 i, s3 i) remains a social optimum. So the only stable social optimum is (d, d). Fix i {1, 2}. Note that if si is slightly lower than d, then pi(si, d) > pi(d, d). Further,

lim si d (pi(si, d) pi(d, d)) = 1

2(d c)(a bd), while lim si d (SW(d, d) SW(si, d)) = 0

and SW(d, d) SW(si, d) = 0 for si = d. Hence

pi(si, d) pi(d, d)

SW(d, d) SW(si, d) = .

The claim now follows by Theorem 4 (i).

Apt & Sch afer

5. Extensions and Future Research Directions

We introduced the selfishness level of a game as a new measure of discrepancy between the social welfare in a Nash equilibrium and in a social optimum. Our studies reveal that the selfishness level often provides deeper insights into the characteristics that influence the players willingness to cooperate. We conclude by mentioning some natural extensions and future research directions.

5.1 Extensions

The definition of the selfishness level naturally extends to other solution concepts and other forms of games.

5.1.1 Mixed Nash Equilibria

For mixed Nash equilibria we can simply adapt our definitions by stipulating that a strategic game G is α-selfish if a mixed Nash equilibrium of G(α) is a social optimum, where now we also allow social optima in mixed strategies. The selfishness level of G is then defined as before in (1). For example, with this notion the selfishness level of the Matching Pennies game (Example 3) is 0 since its unique mixed Nash equilibrium, (1

2T), is also a social optimum. The Matching Pennies game has no pure Nash equilibrium. In contrast, the game from Example 4 does have a pure Nash equilibrium. When we use mixed Nash equilibria its selfishness level also becomes 0. So in both games the selfishness level changed from , when pure Nash equilibria are used, to 0, when mixed Nash equilibria are used. Further, a finite selfishness level of a finite game can decrease when we use mixed Nash equilibria. As an example consider the following amalgamation of the Matching Pennies (with payoffs increased by 2) and Prisoner s Dilemma (with payoffs increased by 1) games:

This game has a unique stable social optimum, (C, C), and a unique pure Nash equilibrium, (D, D). It is easy to check using Theorem 4 (ii) that its selfishness level is 1. On the other hand, when we use mixed Nash equilibria then the selfishness level becomes 0. Indeed, (1

2T) is both a mixed Nash equilibrium and a social optimum in mixed strategies.

5.1.2 Extensive Games

We can also consider extensive games and subgame perfect equilibria. As an example consider the six-period version of the centipede game (see, e.g., Osborne, 2005):

Selfishness Level of Strategic Games

1 2 1 2 1 2

(1, 0) (0, 2) (3, 1) (2, 4) (5, 3) (4, 6)

C C C C C C

S S S S S S

In its unique subgame perfect equilibrium each player chooses S in every period and the resulting payoffs are (1, 0). In contrast, the social optimum is obtained when each player chooses C in every period and the resulting payoffs are (6, 5). We seek α such that in the resulting game G(α) the latter pair of strategies forms a subgame perfect equilibrium. In particular, player 2 should choose in the last round of G(α) the action C. This happens when 5 + (6 + 5)α 6 + (4 + 6)α which holds iffα 1. Now, for α = 1 the game G(α) has the following payoffs:

1 2 1 2 1 2

(2, 1) (2, 4) (7, 5) (8, 10) (13, 11) (14, 16)

C C C C C C

S S S S S S

So in this game the pair of strategies in which each player chooses C in every period is both a subgame perfect equilibrium and a social optimum and yields the payoffs (17, 16). We conclude that the (appropriately adapted) selfishness level for this game is 1. We leave for future work the study of such alternatives.

5.2 Future Research Directions

There are several intriguing questions that we left open. We discuss a few future research directions below.

5.2.1 Abstract Games

It would be interesting to define the notion of a selfishness level for abstract games. These are games in which the payoffs are replaced by preference relations (see Osborne & Rubinstein, 1994). By a preference relation on a set A we mean here a linear ordering on A. More precisely, an abstract game is defined as (N, {Si}i N, { i}i N) where each i is player s i preference relation defined on the set S1 Sn of joint strategies. By a realization of an abstract game (N, {Si}i N, { i}i N) we mean any strategic game (N, {Si}i N, {pi}i N) such that for all i N and s, s S1 Sn we have s i s iff pi(s) i pi(s ). Unfortunately, it is not clear how to do this. First, note that the notion of a Nash equilibrium is well defined for abstract games. However, there is no counterpart of the notion of a social optimum, since there is no global preference relation on the set of joint strategies. It is tempting to circumvent this difficulty by defining the notion of a selfishness level of an abstract game G using its realizations G and the corresponding games G (α(G )), where

Apt & Sch afer

α(G ) is the selfishness level of G . Unfortunately the resulting strategic games G (α(G )), where G is a realization of G are not realizations of a single abstract game, so this detour does not allow us to associate with the initial abstract game another one. As an example take two realizations of the abstract Prisoner s Dilemma game and the corresponding games G (α(G )):

So both realizations have the selfishness level 1 but the transformed games do not correspond to the same abstract game, since in the first transformed game we have p2(D, C) p2(D, D), while in the second one p2(D, D) > p2(D, C).

5.2.2 Selfishness Function

In our approach we assigned to each game a positive real number, its selfishness level. A natural generalization of this idea would be to assign to each game G the function f G : R+ R+, where f(α) equals the price of stability of the game G(α). Then the selfishness level of G is inf{α R+ | f G(α) = 1}. The function f G has been studied for altruistic extensions of linear congestion games and fair cost sharing games (Chen et al., 2011; Elias et al., 2010). However, in these papers only upper bounds on f G are derived, which in light of the results obtained here cannot be tight. It would be interesting to determine f G exactly for these games. This would probably require a generalization of the characterization result presented in this paper.

5.2.3 Alternative Approach Based on the Price of Anarchy

We defined the selfishness level of a game as the smallest α such that the price of stability of G(α) is 1. Alternatively, one might define the selfishness level as the smallest α such that the price of anarchy of G(α) is 1. This alternative approach often yields the value . Take for instance the following coordination game G:

Then for every α 0 (A, A) is a social optimum in G(α) with the social welfare 2 + 4α, while (B, B) is a Nash equilibrium in G(α) with the social welfare 0. So this alternative selfishness level of the game G is , while the original selfishness level is of course 0. As another example consider the game G below left and the corresponding game G(α) below right:

1 + 2α, 1 + 2α

3 + 3α, 3 + 3α

Selfishness Level of Strategic Games

Its selfishness level is 1, since this is the smallest value α for which (A, B) is a Nash equilibrium in G(α). On the other hand, if we focus on the price of anarchy, then we need to choose the smallest α such that (A, A) is not a Nash equilibrium in G(α) while (A, B) is. This is the case iff3α > 1 + 2α, i.e., when α > 1. So this alternative selfishness level of the game G is 1+. In view of these examples we find this alternative approach not very promising. Still, it might be interesting to clarify for which games it yields finite values.

5.2.4 Alternative Approach Based on Approximate Nash Equilibria

As mentioned in the related work section, an alternative approach to measure the stability of equilibria of a game is the following. Given a payoff-maximization game G = (N, {Si}i N, {pi}i N), we call G ε-stable for some ε 0 if there exists a social optimum s that is also a (1 + ε)-approximate Nash equilibrium, i.e., for every player i N and every s i Si, (1 + ε)pi(s) pi(s i, s i).3 We define the stability level of G as the infimum over all ε 0 such that G is ε-stable. Intuitively, a stability level of ε means that if we alter the players incentives by scaling their payoffs by a factor of (1 + ε) then a social optimum is realized as a Nash equilibrium. It would be interesting to study how the stability level of a game relates to its selfishness level. Using the above definitions, it is easy to see that when a game G admits a social optimum s such that for every player i N and every s i Si, pi(s) SW(s) SW(s i, s i), then G is α-stable if G is α-selfish.4 Said differently, the stability level of G is at most its selfishness level. Similarly, when the reverse inequality holds then G is ε-selfish if G is ε-stable. In particular, the above observation can be applied to fair cost sharing games, where for every joint strategy s it holds that for every i N and every s i Si, ci(s i, s i) SC(s i, s i) SC(s) (see also (11) in Section 4.3). We conclude that the stability level of a fair cost sharing game G is at most its selfishness level. As a consequence, our bounds on the selfishness level derived in Section 4.3 extend to the stability level in this case. Further, it is not hard to verify that the stability level for singleton cost sharing games is at least max{0, 1

2cmax/cmin 1} and for cost sharing games with integer costs is at least max{0, 1

2Lcmax 1} by considering the examples given in the proofs of Proposition 2 and Proposition 3, respectively. Thus, for these games the stability level coincides with the selfishness level. However, it can be seen that these two notions do not always coincide. The public goods game is another example where it holds that there exists a social optimum s such that for every player i N and every s i Si, pi(s) SW(s) SW(s i, s i) (see proof of Proposition 7). Thus, the stability level of this game is at most the selfishness level. In fact, simple calculations show that the stability level is max{0, (1 c

n)/c} max{0, (1 c

n)/(c 1)}, where the latter is the selfishness level of the game. We leave it for future work to further investigate the stability level and its relation to the selfishness level.

3. For cost-minimization games, we require that ci(s) (1 + ε)ci(s i, s i). 4. For cost-minimization games, this inequality reads ci(s i, s i) SC(s i, s i) SC(s).

Apt & Sch afer

5.2.5 Other Social Welfare Functions

In this paper we exclusively concentrated on social welfare functions which are defined as the sum of the individual payoffs of the players. We leave it for future research to study the selfishness level of games for other social welfare functions, e.g., maximizing the minimum payoffof all players.

Acknowledgments

A preliminary version of this paper appeared in the Proceedings of the 5th International Symposium on Algorithmic Game Theory (Apt & Sch afer, 2012). We acknowledge initial discussions with Po-An Chen and final discussions with Valerio Capraro. We also thank anonymous reviewers of the preliminary version for their valuable comments. We are particularly grateful to all three reviewers of JAIR for the most helpful remarks. Krzysztof R. Apt is also affiliated with the University of Amsterdam, Institute for Logic, Language and Computation, Science Park 107, 1098 XG Amsterdam, The Netherlands. Guido Sch afer is also affiliated with the VU University Amsterdam, Department of Econometrics and Operations Research, De Boelelaan 1105, 1081 HV Amsterdam, The Netherlands.

Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., & Roughgarden, T. (2008). The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4), 1602 1623.

Anshelevich, E., Das, S., & Naamad, Y. (2009). Anarchy, stability, and utopia: Creating better matchings. In Proc. 2nd International Symposium on Algorithmic Game Theory (SAGT09), Lecture Notes in Computer Science 5814, pp. 159 170. Springer.

Apt, K. R., & Sch afer, G. (2012). Selfishness level of strategic games. In Proc. 5th International Symposium on Algorithmic Game Theory (SAGT12), pp. 13 24. Springer.

Ashlagi, I., Monderer, D., & Tennenholtz, M. (2008). On the value of correlation. Journal of Artificial Intelligence Research, 33, 575 613.

Awerbuch, B., Azar, Y., & Epstein, A. (2013). The price of routing unsplittable flow. SIAM Journal on Computing, 42(1), 160 177.

Axelrod, R. (1984). The Evolution of Cooperation. Basic Books.

Balcan, M.-F., Blum, A., & Mansour, Y. (2009). Improved equilibria via public service advertising. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 728 737. Society for Industrial and Applied Mathematics.

Basu, K. (1994). The traveler s dilemma: paradoxes of rationality in game theory. American Economic Review, 84(2), 391 395.

Becker, T. C., Carter, M., & Naeve, J. (2005). Experts playing the traveler s dilemma. Tech. rep. 252/2005, Department of Economics, University of Hohenheim, Germany.

Selfishness Level of Strategic Games

Beckmann, M., Mc Guire, B., & Winsten, C. (1956). Studies in the Economics of Transportation. Yale University Press, New Haven.

Bir o, P., Manlove, D. F., & Mittal, S. (2010). Size versus stability in the marriage problem. Theoretical Computer Science, 411(16 18), 1828 1841.

Bowles, S. (2004). Microeconomics: Behavior, Institutions, and Evolution. Princeton University Press, Princeton.

Capraro, V. (2013). A model of human cooperation in social dilemmas. PLo S ONE, 8(8), 1 6. e72427.

Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M., & Papaioannou, E. (2010). The impact of altruism on the efficiency of atomic congestion games. In Proc. 5th Symposium on Trustworthy Global Computing, pp. 172 188.

Chen, P.-A., & Kempe, D. (2008). Altruism, selfishness, and spite in traffic routing. In Proc. 10th ACM Conference on Electronic Commerce, pp. 140 149.

Chen, P.-A., de Keijzer, B., Kempe, D., & Sch afer, G. (2011). The robust price of anarchy of altruistic games. In Proc. 7th Workshop on Internet and Network Economics, pp. 383 390.

Christodoulou, G., & Koutsoupias, E. (2005). The price of anarchy of finite congestion games. In Proc. 37th Annual ACM Symposium on Theory of Computing, pp. 67 73.

Christodoulou, G., Koutsoupias, E., & Spirakis, P. G. (2011). On the performance of approximate equilibria incongestion games. Algorithmica, 61(1), 116 140.

Cooper, R., De Jong, D. V., Forsythe, R., & Ross, T. W. (1996). Cooperation without reputation: Experimental evidence from prisoner s dilemma games. Games and Economic Behavior, 12(2), 187 218.

Dreber, A., Rand, D., Fudenberg, D., & Nowak, M. (2008). Winners don t punish. Nature, 452, 348 351.

Elias, J., Martignon, F., Avrachenkov, K., & Neglia, G. (2010). Socially-aware network design games. In Proc. INFOCOM 2010, pp. 41 45.

Feldman, M., & Tamir, T. (2009). Approximate strong equilibrium in job scheduling games. Journal of Artificial Intelligence Research, 36, 387 414.

Fiat, A., Karlin, A., Koutsoupias, E., & Vidali, A. (2013). Approaching utopia: strong truthfulness and externality-resistant mechanisms. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pp. 221 230. ACM.

Goeree, J. K., & Holt, C. A. (2001). Ten little treasures of game theory and ten intuitive contradictions. American Economic Review, 91, 1402 1422.

Hoefer, M., & Skopalik, A. (2009). Altruism in atomic congestion games. In Proc. 17th European Symposium on Algorithms, pp. 179 189.

Isaac, R. M., & Walker, J. M. (1988). Group size effects in public goods provision: The voluntary contributions mechanism. The Quarterly Journal of Economics, 103(1), 179 199.

Apt & Sch afer

Jehle, G., & Reny, P. (2011). Advanced Microeconomic Theory (Third edition). Addison Wesley, New York, NY.

Jurca, R., & Faltings, B. (2009). Mechanisms for making crowds truthful. Journal of Artificial Intelligence Research, 34, 209 253.

Kaporis, A. C., & Spirakis, P. G. (2009). The price of optimum in stackelberg games on arbitrary single commodity networks and latency functions. Theoretical Computer Science, 410(8-10), 745 755.

Koutsoupias, E., & Papadimitriou, C. H. (2009). Worst-case equilibria. Computer Science Review, 3(2), 65 69.

Ledyard, J. O. (1995). Public Goods: A Survey of Experimental Research, chap. 2, pp. 111 194. The Handbook of Experimental Economics. Princeton University Press.

Marco, G. D., & Morgan, J. (2007). Slightly altruistic equilibria in normal form games. Working paper No 185, Center for Studies in Economics and Finance, University of Salerno, Italy. Available from http://www.csef.it/WP/wp185.pdf.

Milchtaich, I. (1996). Congestion games with player-specific payofffunctions. Games and Economic Behaviour, 13, 111 124.

Monderer, D., & Shapley, L. S. (1996). Potential games. Games and Economic Behaviour, 14, 124 143.

Osborne, M. J. (2005). An Introduction to Game Theory. Oxford University Press, Oxford.

Osborne, M. J., & Rubinstein, A. (1994). A Course in Game Theory. The MIT Press, Cambridge, Massachusetts.

Ritzberger, K. (2002). Foundations of Non-cooperative Game Theory. Oxford University Press, Oxford.

Rosenthal, R. W. (1973). A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, pp. 65 67.

Roughgarden, T. (2009). Intrinsic robustness of the price of anarchy. In Proc. 41st Annual ACM Symposium on Theory of Computing, pp. 513 522.

Schulz, A. S., & Moses, N. E. S. (2003). On the performance of user equilibria in traffic networks. In SODA, pp. 86 87.

Sharma, Y., & Williamson, D. P. (2009). Stackelberg thresholds in network routing games or the value of altruism. Games and Economic Behavior, 67(1), 174 190.

Tardos, E., & Vazirani, V. J. (2007). Basic solution concepts and computational issues. In Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. J. (Eds.), Algorithmic Game Theory, chap. 1, pp. 3 28. Cambridge University Press.

Young, H. P. (1993). The evolution of conventions. Econometrica, 61(1), 57 84.