Congestion game - Knowledge

38:. There is a set of resources (e.g. roads or communication links); there are several players who need resources (e.g. drivers or network users); each player chooses a subset of these resources (e.g. a path in the network); the delay in each resource is determined by the number of players choosing a subset that contains this resource. The cost of each player is the sum of delays among all resources he chooses. Naturally, each player wants to minimize his own delay; however, each player's choices impose a negative 89: 4576:. This characterization remain valid when restricted to two-player games, three-resource games, singleton games, games with symmetric strategies, or games with integral weights. Moreover, a class of functions guarantees the existence of a weighted potential, if and only if either (1) it contains only affine functions, or (2) it contains only 4281:

Milchtaich considered the special case of weighted CGs in which each strategy is a path in a given undirected graph ("network CG"). He proved that every finite game can be represented as a weighted network congestion game, with nondecreasing (but not necessarily negative) cost-functions. This implies

2423:. If we start with any strategy-vector, pick a player arbitrarily, and let him change his strategy to a better strategy for him, and repeat, then the sequence of improvements must be finite (that is, the sequence will not cycle). This is because each such improvement strictly increases the potential. 6595:

When cost functions are additively-separable with logarithmic variable-cost function, and there are at most three players, the CG has the best-response improvement property, hence it has a PNE. However, it might not have the finite-improvement property. For more than three players, the existence of

4673:

is the same for all resources. This characterization remain valid when restricted to four-player games, four-resource games, singleton games, games with symmetric strategies, or games with integral weights. For two-player games, a class of functions guarantees the existence of a weighted potential,

6417:

When only pure-strategies are considered, these two notions are equivalent, since the logarithm of a product is a sum. Moreover, when players may have resource-specific weights, the setting with resource-specific delay functions can be reduced to the setting with a universal delay function. Games

6574:

If the weights are player-independent (equivalently: the CG is unweighted and the delay-functions are resource-specific), then it has the FIP, hence it has a PNE. If the cost-functions are additively-separable, then the game even has an exact potential function. The result holds even if the cost

3991:

as in an atomic CG, there are finitely many players, each of whom has a certain load to transfer. As in nonatomic CGs, each player can split his load into fractional loads going through different paths, like a transportation company choosing a set of paths for mass transportation. In contrast to

6099:

resources, and the negative effect of congestion on the payoff is much higher than the positive value of the resources. Then there are n! different PNEs: every one-to-one matching of players to resources is a PNE, as no player would move to a resource occupied by another player. However, if a

6618:

Milchtaich considered the special case of CGs with player-specific costs, in which each strategy is a path in a given graph ("network CG"). He proved that every finite game can be represented as an (unweighted) network congestion game with player-specific costs, with nondecreasing (but not

3999:

and Nachum Shimkin in 1993, in the context of communication networks. They show that, for a simple network with two nodes and multiple parallel links, the Nash equilibrium is unique under reasonable convexity conditions, and has some interesting monotonicity properties. For general network

7028:

from two ends of a tank. The fish distribution between the two ends was, on average, similar to the ratio of the food supply rates, so that no individual fish could increase his feeding rate by moving to the other side. Mlichtaich presents a more general treatment of CGs in

740:

Now, the only pure Nash equilibrium is (OAT,OAT): any player switching to OBT increases his cost from 2.6 to 2.8. An equilibrium still exists, but it is not effiicent: the sum of costs is 5.2, while the sum of cost in (OAT,OBT) and (OBT,OAT) is 4.6.

563:

in this game are (OAT,OBT) and (OBT,OAT): any unilateral change by one of the players increases the cost of this player (note that the values in the table are costs, so players prefer them to be smaller). In this example, the Nash equilibrium is

4293:

has that property. Milchtaich characterized networks that guarantee the existence of PNE, as well as the finite-improvement property, with the additional condition that a player with a lower weight has weakly more allowed strategies (formally,

5150:. It represents a setting in which several people simultaneously choose a place to go to (e.g. a room, a settlement, a restaurant), and their payoff is determined both by the place and by the number of other players choosing the same place. 5811: 5628: 3937: 4857:

is the same for all resources. This characterization remain valid when restricted to three-player games. For two-player games, a class of functions guarantees the existence of PNE if and only if all functions in it are of the form

4282:

that not every such game has a PNE. Concrete examples of weighted CGs without PNE are given by Libman and Orda, as well as Goemans Mirrokni and Vetta. This raises the question of what conditions guarantee the existence of PNE.

4441:

In the special case in which every player is allowed to use any strategy ("public edges"), there are more networks that guarantee the existence of PNE; a complete characterization of such networks is posed as an open problem.

3505: 2045:, but rather a discrete integral of sorts. The critical property of a potential function for a congestion game is that if one player switches strategy, the change in his delay is equal to the change in the potential function. 379:

get easily congested, meaning the more players pass through a point, the greater the delay of each player becomes, so having both players go through the same connection point causes extra delay. Formally, the delay in each of

2481:. There is a continuum of players, the players are considered "infinitesimally small", and each individual player has a negligible effect on the congestion. Nonatomic CGs were studied by Milchtaich, Friedman and Blonsky. 6641:

If all strategies are paths in a network ("network CG"), and all players have the same set of strategies ("symmetric CG"), then a PNE can be computed in polynomial time by maximizing the potential, through reduction to

4759:

Harks and Klimm prove a similar result for the existence of PNE: they prove that a class of functions guarantees the existence of PNE if and only if either (1) it contains only affine functions, or (2) it contains only

3155: 5954: 1968: 6692:

Their algorithm identifies a short sequence of best-response moves, that leads to an approximate equilibrium. They also show that, for more general CGs, attaining any polynomial approximation of PNE is PLS-complete.

6632:

The proof of existence of PNE is constructive: it shows a finite algorithm (an improvement path) that always finds a PNE. This raises the question of how many steps are required to find this PNE? Fabrikant,

5967:

When there are three or more players, even best-response paths might be cyclic. However, every CG still has a PNE. The proof is constructive and shows an algorithm that finds a Nash equilibrium in at most

3723: 1467: 5117: 4835: 4651: 2043: 1687: 2840: 6804: 6575:

functions are not monotonically-increasing with the load. If the cost-functions are not additively-separable, then FIP may not hold, and there may be no potential function, but a PNE still exists.

6222: 5424: 1189: 4145: 6366: 4245: 1759: 1327: 4918: 4734: 3772: 2933: 1392: 61:. Later, Monderer and Shapley proved a converse result: any game with an exact potential function is equivalent to some congestion game. Later research focused on questions such as: 6116:

with players on one side and resources on the other side, where each player is adjacent to all the resources that his copies choose in the unique PNE. Then G contains no cycles.

2479: 6567:

containing the costs of all players, sorted from large to small. Whenever a player deviates to a resource with a smaller cost for him, the vector of costs becomes smaller in the

4392: 6124:

A special case of the player-specific delay functions is that the delay functions can be separated into a player-specific factor and a general factor. There are two sub-cases:

4266:

If there are only two strategies (and arbitrarily many players with possibly different delay functions), then the game has the finite-improvement property (and thus has a PNE).

6067: 5334: 3538: 2255: 2166: 6013: 5956:. This shows that the finite-improvement property does not hold, so the game cannot have a potential function (not even a generalized-ordinal-potential function). However: 5259: 4332: 2304: 6734:

In general, a weighted network CG may not have a PNE. Milchtaich proves that deciding whether a given weighted network CG has a PNE is NP-hard even in the following cases:

6557: 6507: 6585:

players, a PNE exists, though the best-response improvement property might not hold. In contrast, there is a CG with separable costs and resource-independent weights with

2209: 1538: 6856: 5190: 3799: 6646:. The algorithm can be adapted to nonatomic CGs: under certain smoothness assumptions, a Nash equilibirum in such a game can be approximated in strongly-polynomial time. 3611: 3379: 2708: 1072: 6653:. This implies that there are examples with exponentially-long improvement paths. It also implies that finding a Nash equilibrium reachable from a specified state is 6461: 6399: 6255: 5634: 5451: 4996: 4066: 3631: 2869: 1421: 1262: 5023: 4855: 4671: 4176: 3977: 3957: 3651: 3326: 3306: 3279: 3256: 3232: 3205: 3178: 2996: 2969: 2735: 2668: 2638: 2600: 2414: 2387: 2367: 2344: 2120: 2093: 1835: 1808: 1599: 1565: 1039: 503: 3066: 690: 1009: 6108:

goes to infinity. Moreover, in a "large" (nonatomic) crowding game, there is generically a unique PNE. This PNE has an interesting graph-theoretic property. Let

5279: 5210: 5043: 4938: 4754: 3819: 3578: 3558: 3399: 3346: 3016: 2775: 2755: 2573: 2550: 2530: 2503: 2324: 2066: 1855: 1780: 1619: 1495: 1223: 1092: 983: 960: 941: 921: 902: 882: 863: 843: 824: 804: 776: 667: 647: 628: 608: 589: 476: 456: 437: 417: 398: 377: 354: 334: 314: 294: 274: 254: 234: 214: 194: 174: 154: 134: 114: 3827: 4433:

of one or more networks from a set of six "allowed networks"; an equivalent condition is that no network from a set of six "forbidden network" is embedded in

6619:

necessarily negative) cost-functions. A complete characterization of networks that guarantee the existence of PNE in such CGs is posed as an open problem.

6592:

When cost functions are additively-separable with linear variable-cost functions, the CG has a weighted potential, hence it has the FIP, hence it has a PNE.

1195:. In general, different players may have different sets, for example, if each player has a different source and/or a different target. Such CGs are called 3404: 76: 6675:

With linear delay functions, the approximation ratio is 2+ε, and the runtime is polynomial in the number of playres, the number of resources, and 1/ε.

508:

Good outcome in this game will be for the two players to "coordinate" and pass through different connection points. Can such outcome be achieved?

4269:

If there are only two players (with possibly different delay functions), then the game has the finite-best-response property (and thus has a PNE).

3071: 6748:

Caragiannis, Fanelli, Gravin and Skopalik present an algorithm that computes a constant-factor approximation PNE in weighted CGs. In particular:

5819: 1885: 6723:

Panagopoulou and Spirakis show empirical evidence that the algorithm of Fotakis, Kontogiannis and Spirakis in fact runs in time polynomial in

6649:

If the strategies can be general subsets, or the players may have different sets of strategies ("asymmetric CG"), then computing a PNE is

4572:

Harks, Klimm and Mohring prove that a class of functions guarantees the existence of an exact potential, if and only if it contains only

65:

Does the existence of equilibrium, as well as the existence of a potential function, extend to more general models of congestion games?

6701:

Fotakis, Kontogiannis and Spirakis present an algorithm that, in any weighted network CG with linear delay functions, finds a PNE in

4255:

Milchtaich considered the special case of weighted CGs in which each strategy is a single resource ("singleton CG"), the weights are

3656: 1429: 6720:

algorithm: players enter the game in descending order of their weight, and choose a best-response to existing players' strategies.

6671:

Caragiannis, Fanelli, Gravin and Skopalik present an algorithm that computes a constant-factor approximation PNE. In particular:

6668:

Even-Dar, Kesselman and Mansour analyze the number of steps required for convergence to equilibrium in a load-balancing setting.

5048: 4957:

The basic CG model can be extended by allowing the delay function of each resource to depend on the player. So for each resource

4767: 4583: 1977: 6872:!)-approximate PNE. Their algorithm identifies a short sequence of best-response moves, that leads to such an approximate PNE. 1624: 2780: 8962: 8794: 8739: 8702: 8665: 8567: 8379: 8064: 7613: 6982:

Since every CG has a Nash equilibrium, the next natural topic is to analyze their quality. This is done using the concept of

6755: 6088:; every strong PNE of a crowding game can be attained as a subgame-perfect equilibrium of a sequential version of the game. 5445:

function. For example, suppose there are three resources x,y,z and two players A and B with the following delay functions:

2369:

is a pure Nash equilibrium. Fixing all but one player, any improvement in strategy by that player corresponds to decreasing

6984: 6563:). The proof is based on a vector-valued potential function. For each state of the game, the potential is a vector of size 69: 6864:

To prove their results, they show that, although weighted CGs may not have a potential function, every weighted CG can be

6137: 5339: 1100: 7024:

Milinsky describes an experiment in which a natural CG converges into a Nash equilibrium. In his experiment, he fed six

8229: 8008: 7828: 7748: 4075: 4272:

If there are three or more strategies and three or more players with different delay functions, a PNE might not exist.

9077: 9058: 7568: 6281: 4263:

If all players have the same delay functions, then the game has the finite-improvement property (and thus has a PNE).

4181: 6019:: for any initial strategy-vector, at least one best-response path starting at this vector has a length of at most 1699: 1267: 8861:"Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure" 6084:

in which the players' actions are a PNE in the original simultaneous game. Every crowding game has at least one

4861: 4677: 3728: 2882: 1336: 8906:

Kukushkin, N. S.; Men'Shikov, I. S.; Men'Shikova, O. R.; Morozov, V. V. (1990). "Resource allocation games".

6513:), then the CG has the FIP, hence it has a PNE. The same holds if the base costs are resource-independent ( 6423: 2677:

We allow players in a type to distribute fractionally over their strategy set. That is, for every strategy

9045: 2458: 8979: 6664:

can be presented as a game whose pure equilibria are guaraneed to exist by a potential-function argument.

6081: 4457:

guarantees that every PNE is Pareto-efficient, iff three simple "forbidden networks" are not embedded in

4337: 2122:. Elements that are in both of the strategies remain unaffected, elements that the player leaves (i.e. 511:

The following matrix expresses the costs of the players in terms of delays depending on their choices:

9013: 8498: 8315: 8273: 7867: 7784: 7694: 7420: 7370: 7276: 7237: 7198: 7101: 6022: 5284: 3510: 2214: 2125: 8949:. Lecture Notes in Computer Science. Vol. 4051. Berlin, Heidelberg: Springer. pp. 572–583. 8689:. Lecture Notes in Computer Science. Vol. 4051. Berlin, Heidelberg: Springer. pp. 501–512. 8652:. Lecture Notes in Computer Science. Vol. 4708. Berlin, Heidelberg: Springer. pp. 633–644. 8366:. Lecture Notes in Computer Science. Vol. 2719. Berlin, Heidelberg: Springer. pp. 502–513. 8051:. Lecture Notes in Computer Science. Vol. 6756. Berlin, Heidelberg: Springer. pp. 539–551. 7030: 7009: 6643: 5971: 4473: 6738:

There are two players; all players are allowed to use all paths; all cost-functions are nonnegative.

5215: 4297: 4015:, different players may have different effects on the congestion. For example, in a road network, a 2260: 7600:. Lecture Notes in Computer Science. Vol. 4286. Berlin, Heidelberg: Springer. pp. 87–98. 6516: 6466: 2389:, which cannot happen at a minimum. Now since there are a finite number of configurations and each 1225:. CGs in which a strategy can only be a path in a given graph (as in the above example) are called 4000:

topologies, more complex conditions are required to guarantee the uniqueness of Nash equilibrium.

2171: 1500: 8645: 8044: 6816: 6085: 5156: 4520: 3777: 5806:{\displaystyle d_{B,y}(1)<d_{B,x}(0)<d_{B,x}(2)<d_{B,z}(0)<d_{B,z}(2)<d_{B,y}(2)} 5623:{\displaystyle d_{A,x}(1)<d_{A,y}(0)<d_{A,y}(2)<d_{A,z}(0)<d_{A,z}(2)<d_{A,x}(2)} 3583: 3351: 2680: 1044: 7001: 6702: 6634: 1878:

that assigns a value to each outcome. Moreover, this construction will also show that iterated

27: 4519:

Holzman and Law-Yone also characterize the networks that guarantee that every atomic CG has a

8359: 6433: 6371: 6227: 4968: 4761: 4577: 4566: 4038: 3616: 3235: 8003: 7823: 7743: 2848: 1400: 1241: 8362:. In Baeten, Jos C. M.; Lenstra, Jan Karel; Parrow, Joachim; Woeginger, Gerhard J. (eds.). 7075: 6806:, and the runtime is polynomial in the number of playres, the number of resources, and 1/ε. 6741:

There are two players; the CG is unweighted; the costs are player-specific and nonnegative.

5001: 4840: 4656: 4154: 3962: 3942: 3636: 3311: 3284: 3264: 3241: 3210: 3183: 3163: 2974: 2947: 2713: 2646: 2616: 2578: 2392: 2372: 2352: 2329: 2098: 2071: 1813: 1786: 1577: 1543: 1017: 481: 7054:

Rosenthal, Robert W. (1973), "A class of games possessing pure-strategy Nash equilibria",

7018:: Fotakis, Kontogiannis and Spirakis study CGs in which players participate in coalitions. 6091:

In general, a crowding game might have many different PNE. For example, suppose there are

3025: 672: 8: 6016: 4469: 3932:{\displaystyle \textstyle \delta (\sum _{e\in Q}d_{e}(x_{e})-\sum _{e\in P}d_{e}(x_{e}))} 3281:

is indeed a Nash equilibrium. Assume for contradiction that there exists a collection of

2671: 988: 46: 8942: 8682: 6731:. They also propose an initial strategy-vector that dramatically speeds this algorithm. 8995: 8923: 8888: 8859:

Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander (2015-03-27).

8800: 8772: 8763:

Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander (2011-10-01).

8745: 8623: 8573: 8466: 8254: 8202: 8150: 7984: 7937: 7675: 7593: 7574: 7490: 7351: 7304: 7179: 7171: 7079: 5264: 5195: 5028: 4923: 4739: 3804: 3563: 3543: 3384: 3331: 3001: 2760: 2740: 2558: 2535: 2515: 2488: 2309: 2051: 1840: 1765: 1604: 1568: 1480: 1208: 1077: 968: 945: 926: 906: 887: 867: 848: 828: 809: 789: 761: 652: 632: 613: 593: 574: 461: 441: 422: 402: 383: 362: 339: 319: 299: 279: 259: 239: 219: 199: 179: 159: 139: 119: 99: 8726:. STOC '04. New York, NY, USA: Association for Computing Machinery. pp. 604–612. 8683:"Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions" 8554:. STOC '04. New York, NY, USA: Association for Computing Machinery. pp. 604–612. 8316:"Pure Strategy Nash Equilibrium in a Group Formation Game with Positive Externalities" 7824:"Topological Uniqueness of the Nash Equilibrium for Selfish Routing with Atomic Users" 5963:

With only two players, every finite best-response property holds. Hence, a PNE exists.

9054: 8958: 8927: 8880: 8841: 8836: 8819: 8790: 8735: 8698: 8661: 8627: 8615: 8563: 8528: 8474: 8458: 8419: 8375: 8335: 8293: 8246: 8194: 8142: 8103: 8060: 8025: 7976: 7929: 7887: 7845: 7804: 7765: 7724: 7679: 7667: 7609: 7564: 7529: 7494: 7482: 7440: 7390: 7343: 7296: 7257: 7218: 7163: 7121: 7083: 4550:

a certain property if every weighted CG in which all delay functions are elements of

8804: 8154: 7941: 7578: 7308: 7183: 5960:

With only two resources, the finite improvement property holds. Hence, a PNE exists.

8991: 8950: 8915: 8892: 8872: 8831: 8782: 8749: 8727: 8690: 8653: 8644:

Mavronicolas, Marios; Milchtaich, Igal; Monien, Burkhard; Tiemann, Karsten (2007).

8607: 8577: 8555: 8518: 8510: 8450: 8411: 8367: 8327: 8285: 8238: 8186: 8134: 8093: 8052: 8017: 7968: 7921: 7879: 7837: 7796: 7757: 7714: 7706: 7657: 7649: 7601: 7556: 7521: 7474: 7432: 7382: 7355: 7335: 7288: 7249: 7210: 7155: 7113: 7063: 6714: 6661: 6650: 6578:

If the weights are resource-independent, then a PNE exists in the following cases:

4559: 4524: 4289:

a certain property if every weighted network CG in which the underlying network is

3500:{\displaystyle \textstyle \sum _{e\in Q}d_{e}(x_{e})<\sum _{e\in P}d_{e}(x_{e})} 8206: 7988: 7957:"Characterizing the Existence of Potential Functions in Weighted Congestion Games" 9037: 9023: 8945:. In Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). 8685:. In Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). 8657: 8056: 7874:. Automata, Languages and Programming: Algorithms and Complexity (ICALP-A 2004). 7638:"Network topology and equilibrium existence in weighted network congestion games" 7071: 6654: 6113: 6077: 4573: 4569:

guarantees the existence of a weighted potential, and hence the existence of PNE.

1871: 1867: 560: 50: 8242: 7000:: Facchini, van Megen, Borm and Tijs extend Rosenthal's model to a setting with 2419:

The existence of a potential function has an additional implication, called the

9029: 9019: 8765:"Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games" 8764: 7548: 6868:

by a certain potential game. This lets them show that every weighted CG has a (

5442: 4562:

guarantees the existence of an exact potential, and hence the existence of PNE.

58: 8611: 8514: 8415: 8098: 8081: 7972: 7883: 7710: 7653: 7525: 7478: 7386: 7323: 7292: 9071: 8905: 8884: 8845: 8619: 8532: 8462: 8423: 8371: 8339: 8297: 8250: 8198: 8146: 8107: 8029: 7980: 7933: 7891: 7849: 7808: 7769: 7728: 7671: 7533: 7486: 7444: 7394: 7347: 7300: 7261: 7222: 7167: 7125: 7005: 6717: 6568: 3019: 1879: 356:

is more likely to be chosen by each player), as in the picture at the right.

57:, PNE). During the proof, he in fact proved that every congestion game is an 9041: 8731: 8594:

Facchini, Giovanni; van Megen, Freek; Borm, Peter; Tijs, Stef (1997-03-01).

8559: 8138: 7956: 7925: 7637: 7462: 6426:. The following is known about weighted singleton CGs with separable costs: 3150:{\displaystyle \textstyle \Phi =\sum _{e\in E}\int _{0}^{x_{e}}d_{e}(z)\,dz} 8724:

Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

8552:

Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

8478: 8331: 8289: 8021: 7841: 7800: 7761: 7436: 7253: 7214: 7117: 5949:{\displaystyle (z,y)\to (y,y)\to (y,z)\to (x,z)\to (x,x)\to (z,x)\to (z,y)} 4250: 4147:. An important special case is when the weight depends only on the player ( 8719: 8595: 8547: 8399: 8190: 8122: 7909: 7509: 7371:"Local smoothness and the price of anarchy in splittable congestion games" 6606:

CG with separable player-specific preferences is isomorphic to a weighted

5122: 3992:

nonatomic CGs, each player has a non-negligible effect on the congestion.

2431:

Below we present various extensions and variations on the basic CG model.

1963:{\displaystyle \textstyle \Phi =\sum _{e\in E}\sum _{k=1}^{x_{e}}d_{e}(k)} 8786: 7560: 7025: 6745:

The proof is by reduction from the directed edge-disjoint paths problem.

6419: 4411: 3996: 45:

The research of congestion games was initiated by the American economist

39: 23: 8954: 8694: 8174: 7719: 7596:. In Spirakis, Paul; Mavronicolas, Marios; Kontogiannis, Spyros (eds.). 4530:

Richman and Shimkin characterize the networks that guarantee that every

49:

in 1973. He proved that every congestion game has a Nash equilibrium in

9033: 8919: 8523: 8470: 8438: 8258: 8224: 8082:"Pure Nash equilibria in player-specific and weighted congestion games" 8004:"On the Existence of Pure Nash Equilibria in Weighted Congestion Games" 7662: 7605: 7553:

46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)

7277:"Bounding the inefficiency of equilibria in nonatomic congestion games" 7175: 7143: 7067: 4259:, and all players have the same strategy set. The following is proved: 4020: 3801:. The equivalent analysis of the change holds when we look at edges in 2670:

are monotone and positive, but we now add the assumption that they are

2306:. This change in potential is precisely the change in delay for player 8718:

Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (2004-06-13).

8546:

Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (2004-06-13).

7866:

Fotakis, Dimitris; Kontogiannis, Spyros; Spirakis, Paul (2005-12-08).

7594:"The Equilibrium Existence Problem in Finite Network Congestion Games" 7339: 1191:. CGs in which all players have the same set of strategies are called 568:- the players choose different lanes and the sum of costs is minimal. 4497: 4430: 4415: 88: 31: 8876: 8454: 1097:

In the above example, both players have the same set of strategies:

8643: 7159: 6880:

In summary, CGs can be classified according to various parameters:

6696: 1229:. CGs in which a strategy can only be a single resource are called 8860: 8777: 8769:

2011 IEEE 52nd Annual Symposium on Foundations of Computer Science

8123:"Algorithms for pure Nash equilibria in weighted congestion games" 8080:

Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold (2009-04-06).

7910:"Algorithms for pure Nash equilibria in weighted congestion games" 7744:"Topological Conditions for Uniqueness of Equilibrium in Networks" 4023:. In general, the weight of a player may depend on the resource ( 35: 8941:

Fotakis, Dimitris; Kontogiannis, Spyros; Spirakis, Paul (2006).

8858: 8762: 8314:

Konishi, Hideo; Le Breton, Michel; Weber, Shlomo (1997-10-01).

8272:

Konishi, Hideo; Le Breton, Michel; Weber, Shlomo (1997-01-01).

9028: 6927:

Cost functions for different players using the same resource:

3718:{\displaystyle \textstyle \int _{0}^{x_{e}+\delta }d_{e}(z)dz} 1462:{\displaystyle d_{e}:\mathbb {N} \longrightarrow \mathbb {R} } 42:

on the other players, which may lead to inefficient outcomes.

8818:

Fortune, Steven; Hopcroft, John; Wyllie, James (1980-02-01).

6875: 6627: 5135:

Each player chooses a single resource (such games are called

4949:

There are many other papers about weighted congestion games.

4016: 3725:. Differentiating the integral, this change is approximately 8717: 8681:

Gairing, Martin; Monien, Burkhard; Tiemann, Karsten (2006).

8545: 8121:

Panagopoulou, Panagiota N.; Spirakis, Paul G. (2007-02-09).

7908:

Panagopoulou, Panagiota N.; Spirakis, Paul G. (2007-02-09).

7463:"Representation of finite games as network congestion games" 5336:; hence, a strategy vector is a PNE iff for every player i, 4410:(a graph made of one or more single-edge networks connected 3939:, which is less than zero. This is a contradiction, as then 96:

Consider a traffic net where two players originate at point

8980:"An Evolutionarily Stable Feeding Strategy in Sticklebacks" 8940: 8225:"Generic Uniqueness of Equilibrium in Large Crowding Games" 7865: 6104:

times, then the set of PNEs converges to a single point as

5112:{\displaystyle \textstyle \sum _{e\in P_{i}}d_{i,e}(x_{e})} 4558:

Fotakis, Kontogiannis and Spirakis prove that the class of

2939: 754:

The basic definition of a CG has the following components.

26:. They represent situations which commonly occur in roads, 7955:

Harks, Tobias; Klimm, Max; Möhring, Rolf H. (2011-07-01).

6076:. This means that, for every ordering of the players, the 4830:{\displaystyle a_{e}\cdot \exp {(\phi \cdot x_{e})}+b_{e}} 4646:{\displaystyle a_{e}\cdot \exp {(\phi \cdot x_{e})}+b_{e}} 4480:

Milchtaich analyzes the effect of network topology on the

4445:

Mlichtaich analyzes the effect of network topology on the

2038:{\displaystyle \textstyle \sum _{e\in E}x_{e}d_{e}(x_{e})} 8596:"CONGESTION MODELS AND WEIGHTED BAYESIAN POTENTIAL GAMES" 8593: 8358:

Even-Dar, Eyal; Kesselman, Alex; Mansour, Yishay (2003).

8047:. In Aceto, Luca; Henzinger, Monika; Sgall, Jiří (eds.). 7324:"Competitive routing in multiuser communication networks" 6613: 6413:

is a general delay function (the same for all resources).

6401:

is a constant that represents the fixed cost of resource

6269:

is a general delay function (the same for all resources).

4515:

contains an embedded network of a particular simple type.

3157:, replacing the discrete integral with the standard one. 1682:{\displaystyle \textstyle \sum _{e\in P_{i}}d_{e}(x_{e})} 8357: 8045:"Restoring Pure Equilibria to Weighted Congestion Games" 7421:"Congestion Games with Player-Specific Payoff Functions" 6752:

With linear delay functions, the approximation ratio is

6257:

is a constant that represents the base cost of resource

4251:

Weighted singleton CGs with resource-independent weights

2835:{\displaystyle \textstyle \sum _{P\in S_{i}}f_{P}=r_{i}} 7199:"Dynamics and Rationality in Ordered Externality Games" 6799:{\displaystyle {\frac {3+{\sqrt {5}}}{2}}+O(\epsilon )} 6418:

with separable cost functions occur in load-balancing,

5123:

Player-specific costs in singleton CGs (crowding games)

8499:"Weighted congestion games with separable preferences" 8079: 7547:

Goemans, M.; Mirrokni, Vahab; Vetta, A. (2005-10-01).

5052: 3831: 3660: 3408: 3234:

is a continuous function of the strategy. Then by the

3075: 2784: 1981: 1889: 1628: 8817: 8313: 8271: 7368: 6819: 6758: 6519: 6469: 6436: 6374: 6284: 6230: 6140: 6025: 5974: 5822: 5637: 5454: 5342: 5287: 5267: 5218: 5198: 5159: 5051: 5031: 5004: 4971: 4926: 4864: 4843: 4770: 4742: 4680: 4659: 4586: 4340: 4300: 4184: 4157: 4078: 4041: 3965: 3945: 3830: 3807: 3780: 3731: 3659: 3639: 3619: 3586: 3566: 3546: 3513: 3407: 3387: 3354: 3334: 3314: 3287: 3267: 3244: 3213: 3186: 3166: 3074: 3028: 3004: 2977: 2950: 2885: 2851: 2783: 2763: 2743: 2716: 2683: 2649: 2619: 2581: 2561: 2538: 2518: 2491: 2461: 2395: 2375: 2355: 2332: 2312: 2263: 2217: 2174: 2128: 2101: 2074: 2054: 1980: 1888: 1843: 1816: 1789: 1768: 1702: 1627: 1607: 1580: 1546: 1503: 1483: 1432: 1403: 1339: 1270: 1244: 1211: 1103: 1080: 1047: 1020: 991: 971: 948: 929: 909: 890: 870: 851: 831: 812: 792: 764: 675: 655: 635: 616: 596: 577: 484: 464: 444: 425: 405: 386: 365: 342: 322: 302: 282: 262: 242: 222: 202: 182: 162: 142: 122: 102: 8680: 8400:"Atomic Resource Sharing in Noncooperative Networks" 8120: 7907: 7695:"Network topology and the efficiency of equilibrium" 7546: 7510:"Atomic Resource Sharing in Noncooperative Networks" 7369:

Roughgarden, Tim; Schoppmann, Florian (2015-03-01).

6622: 6217:{\displaystyle d_{i,e}(x_{e})=a_{i,e}\cdot d(x_{e})} 6080:

in which each player in turn picks a strategy has a

4940:

is a monotone function (the same for all resources).

4756:

is a monotone function (the same for all resources).

3824:

Therefore, the change in potential is approximately

2944:

Strategies are now collections of strategy profiles

2875:

is defined as the sum of fractions of players using

5419:{\displaystyle d_{i,e}(x_{e})\leq d_{i,f}(x_{f}+1)} 4674:if and only if all functions in it are of the form 3328:but are not a Nash equilibrium. Then for some type 1184:{\displaystyle S_{1}=S_{2}=\{\{OA,AT\},\{OB,BT\}\}} 8042: 6850: 6798: 6551: 6501: 6455: 6393: 6360: 6249: 6216: 6061: 6007: 5948: 5805: 5622: 5437:In general, CGs with player-specific delays might 5418: 5328: 5273: 5253: 5204: 5184: 5111: 5037: 5017: 4990: 4932: 4912: 4849: 4829: 4748: 4728: 4665: 4645: 4565:Panagopoulou and Spirakis prove that the class of 4386: 4326: 4239: 4170: 4139: 4060: 3995:Splittable CGs were first analyzed by Ariel Orda, 3971: 3951: 3931: 3813: 3793: 3766: 3717: 3645: 3625: 3605: 3572: 3552: 3532: 3499: 3393: 3373: 3340: 3320: 3300: 3273: 3250: 3226: 3199: 3172: 3149: 3060: 3010: 2990: 2963: 2927: 2863: 2834: 2769: 2749: 2729: 2702: 2662: 2632: 2594: 2567: 2544: 2524: 2497: 2473: 2408: 2381: 2361: 2338: 2318: 2298: 2249: 2203: 2160: 2114: 2087: 2060: 2037: 1962: 1849: 1829: 1802: 1774: 1753: 1681: 1613: 1593: 1559: 1532: 1489: 1461: 1415: 1386: 1321: 1256: 1217: 1183: 1086: 1066: 1033: 1003: 977: 954: 935: 915: 896: 876: 857: 837: 818: 798: 770: 684: 661: 641: 622: 602: 583: 497: 470: 450: 431: 411: 392: 371: 348: 328: 308: 288: 268: 248: 228: 208: 188: 168: 148: 128: 108: 8650:Mathematical Foundations of Computer Science 2007 8646:"Congestion Games with Player-Specific Constants" 7954: 7274: 6053: 6032: 5999: 5978: 5261:. If the player switches to a different strategy 4952: 4140:{\displaystyle x_{e}=\sum _{i:e\in P_{i}}w_{i,e}} 9069: 8043:Kollias, Konstantinos; Roughgarden, Tim (2011). 6697:Computing an equilibrium in weighted network CGs 4500:of one or more networks of several simple kinds. 92:The directed graph for a simple congestion game. 7782: 7100:Monderer, Dov; Shapley, Lloyd S. (1996-05-01). 7099: 6964:Strategy sets of different players: different ( 6361:{\displaystyle d_{i,e}(x_{e})=a_{i,e}+d(x_{e})} 4402:guarantees the finite-improvement property iff 4240:{\displaystyle x_{e}=\sum _{i:e\in P_{i}}w_{i}} 1861: 7821: 7321: 3982: 1477:). Given a vector of strategies, the delay on 9053:. Cambridge, UK: Cambridge University Press. 8865:ACM Transactions on Economics and Computation 8820:"The directed subgraph homeomorphism problem" 7783:Holzman, Ron; Law-Yone, Nissan (1997-10-01). 7322:Orda, A.; Rom, R.; Shimkin, N. (1993-10-01). 7008:are potential games, and therefore have pure 4492:guarantees that the PNE costs are unique iff 2434: 8648:. In Kučera, Luděk; Kučera, Antonín (eds.). 8274:"Equilibria in a Model with Partial Rivalry" 7822:Richman, Oran; Shimkin, Nahum (2007-02-01). 7275:Roughgarden, Tim; Tardos, Éva (2004-05-01). 5816:The following is a cyclic improvement path: 5179: 5173: 5142:All players have the same set of strategies. 4003: 3261:The final step is to show that a minimum of 3018:, the collection of all valid profiles is a 1837:would not decrease the delay experienced by 1381: 1356: 1205:In general, a strategy can be any subset of 1178: 1175: 1157: 1151: 1133: 1130: 8439:"Habitat Selection as an Evolutionary Game" 6119: 4285:In particular, we say that a certain graph 3959:was not minimized. Therefore, a minimum of 1754:{\displaystyle (P_{1},P_{2},\ldots ,P_{n})} 1322:{\displaystyle (P_{1},P_{2},\ldots ,P_{n})} 8943:"Atomic Congestion Games Among Coalitions" 8496: 8397: 8222: 8175:"Crowding games are sequentially solvable" 8172: 8001: 7741: 7692: 7635: 7591: 7507: 7460: 7418: 7141: 6876:Summary of congestion game classifications 6628:Computing an equilibrium in unweighted CGs 3068:. We now define the potential function as 2532:players, as in the discrete case, we have 2416:is monotone, there exists an equilibrium. 2211:, and the elements the player joins (i.e. 1689:; each player wants to minimize his delay. 571:In contrast, suppose the delay in each of 8835: 8776: 8522: 8097: 7718: 7661: 7053: 6994:are somewhat related to congestion games. 5146:This special case of CG is also called a 4913:{\displaystyle a_{e}\cdot f(x_{e})+b_{e}} 4729:{\displaystyle a_{e}\cdot f(x_{e})+b_{e}} 3767:{\displaystyle \delta \cdot d_{e}(x_{e})} 3507:. The idea now is to take a small amount 3139: 2928:{\displaystyle x_{e}=\sum _{P\ni e}f_{P}} 1455: 1447: 359:The roads from both connection points to 8977: 8720:"The complexity of pure Nash equilibria" 8548:"The complexity of pure Nash equilibria" 8398:Libman, Lavy; Orda, Ariel (2001-08-01). 8127:ACM Journal of Experimental Algorithmics 8002:Harks, Tobias; Klimm, Max (2012-08-01). 7914:ACM Journal of Experimental Algorithmics 7785:"Strong Equilibrium in Congestion Games" 7508:Libman, Lavy; Orda, Ariel (2001-08-01). 7377:. Computer Science and Economic Theory. 7196: 6813:polynomials, the approximation ratio is 6682:polynomials, the approximation ratio is 4511:guarantee that PNE costs are unique iff 2940:Existence of equilibria in nonatomic CGs 1387:{\displaystyle x_{e}=\#\{i:e\in P_{i}\}} 87: 7235: 6610:CG with player-independent preference. 4537: 4276: 4151:), that is, each player i has a weight 2737:denote the fraction of players in type 2613:picks a strategy from the strategy set 9070: 9012:Lecture notes of Yishay Mansour about 8908:Computational Mathematics and Modeling 8218: 8216: 8168: 8166: 8164: 7903: 7901: 7861: 7859: 7631: 7629: 7627: 7625: 7456: 7454: 6614:Network CGs with player-specific costs 6069:, which terminates at an equilibrium. 4425:guarantees the existence of a PNE iff 4414:), or to a parallel network connected 1874:. This can be shown by constructing a 8639: 8637: 8589: 8587: 8492: 8490: 8488: 8436: 8393: 8391: 8360:"Convergence Time to Nash Equilibria" 8353: 8351: 8349: 8309: 8307: 7238:"Anonymous Games with Binary Actions" 6884:Number and splittability of players: 6705:(polynomial in the number of players 5153:In a crowding game, given a strategy 4418:with one or two single-edge networks. 1041:for each player, where each strategy 778:of congestible elements (also called 8179:International Journal of Game Theory 7642:International Journal of Game Theory 7467:International Journal of Game Theory 7414: 7412: 7410: 7408: 7406: 7404: 7137: 7135: 7095: 7093: 7056:International Journal of Game Theory 7049: 7047: 6985:Price of anarchy in congestion games 2474:{\displaystyle n\rightarrow \infty } 8947:Automata, Languages and Programming 8687:Automata, Languages and Programming 8364:Automata, Languages and Programming 8213: 8161: 8049:Automata, Languages and Programming 7898: 7856: 7622: 7451: 7328:IEEE/ACM Transactions on Networking 6946:Possible strategies: one resource ( 4387:{\displaystyle |S_{i}|\geq |S_{j}|} 2451:is the limit of a standard CG with 13: 8996:10.1111/j.1439-0310.1979.tb00669.x 8634: 8584: 8485: 8388: 8346: 8304: 8230:Mathematics of Operations Research 8088:. Internet and Network Economics. 8009:Mathematics of Operations Research 7829:Mathematics of Operations Research 7749:Mathematics of Operations Research 7144:"Congestion Models of Competition" 6036: 5982: 5127:Milchtaich introduced and studied 3966: 3946: 3640: 3315: 3268: 3245: 3167: 3076: 2468: 2376: 2356: 2333: 1890: 1353: 14: 9089: 9006: 7549:"Sink Equilibria and Convergence" 7401: 7132: 7090: 7044: 6623:Computing a pure Nash equilibrium 4019:adds congestion much more than a 3207:is continuous by assumption, and 2421:finite improvement property (FIP) 2346:is in fact a potential function. 1882:finds a Nash equilibrium. Define 8978:Milinski, Manfred (2010-04-26). 7236:Blonski, Matthias (1999-08-01). 7197:Friedman, Eric J. (1996-09-01). 6809:When delay functions are degree- 6709:and the sum of players' weights 6678:When delay functions are degree- 6062:{\displaystyle r{n+1 \choose 2}} 5329:{\displaystyle d_{i,f}(x_{f}+1)} 4944: 4429:is homeomorphic to a connection 3613:, we have increased its load by 3533:{\displaystyle \delta <f_{P}} 3348:, there exists some improvement 2349:Now observe that any minimum of 2250:{\displaystyle e\in Q_{i}-P_{i}} 2161:{\displaystyle e\in P_{i}-Q_{i}} 70:inefficiency of congestion games 8984:Zeitschrift für Tierpsychologie 8971: 8934: 8899: 8852: 8811: 8756: 8711: 8674: 8539: 8497:Milchtaich, Igal (2009-11-01). 8430: 8265: 8173:Milchtaich, Igal (1998-12-01). 8114: 8073: 8036: 7995: 7948: 7815: 7776: 7742:Milchtaich, Igal (2005-02-01). 7735: 7693:Milchtaich, Igal (2006-11-01). 7686: 7636:Milchtaich, Igal (2015-08-01). 7585: 7540: 7501: 7461:Milchtaich, Igal (2013-11-01). 7419:Milchtaich, Igal (1996-03-01). 6589:players in which no PNE exists. 6008:{\displaystyle {n+1 \choose 2}} 5131:in the following special case: 4068:, and the load on the resource 3160:As a function of the strategy, 2643:As before, the delay functions 744: 9024:Potential and congestion games 9014:Potential and congestion games 7598:Internet and Network Economics 7362: 7315: 7268: 7229: 7190: 7004:. They prove that the related 6843: 6837: 6793: 6787: 6355: 6342: 6314: 6301: 6211: 6198: 6170: 6157: 5943: 5931: 5928: 5925: 5913: 5910: 5907: 5895: 5892: 5889: 5877: 5874: 5871: 5859: 5856: 5853: 5841: 5838: 5835: 5823: 5800: 5794: 5772: 5766: 5744: 5738: 5716: 5710: 5688: 5682: 5660: 5654: 5617: 5611: 5589: 5583: 5561: 5555: 5533: 5527: 5505: 5499: 5477: 5471: 5413: 5394: 5372: 5359: 5323: 5304: 5254:{\displaystyle d_{i,e}(x_{e})} 5248: 5235: 5129:CGs with player-specific costs 5105: 5092: 4953:Player-specific cost functions 4894: 4881: 4810: 4791: 4710: 4697: 4626: 4607: 4380: 4365: 4357: 4342: 4327:{\displaystyle w_{i}<w_{j}} 3925: 3922: 3909: 3877: 3864: 3835: 3761: 3748: 3705: 3699: 3493: 3480: 3448: 3435: 3136: 3130: 3049: 3029: 2465: 2299:{\displaystyle d_{e}(x_{e}+1)} 2293: 2274: 2198: 2185: 2048:Consider the case when player 2031: 2018: 1956: 1950: 1748: 1703: 1675: 1662: 1567:is assumed to be positive and 1527: 1514: 1451: 1316: 1271: 985:players. In the above example 1: 7037: 6552:{\displaystyle a_{i,e}=a_{i}} 6502:{\displaystyle a_{i,e}=a_{e}} 6015:steps. Moreover, every CG is 2426: 1970:. Note that this function is 22:(CG) are a class of games in 16:Class of games in game theory 8837:10.1016/0304-3975(80)90009-2 8824:Theoretical Computer Science 8658:10.1007/978-3-540-74456-6_56 8086:Theoretical Computer Science 8057:10.1007/978-3-642-22012-8_43 7872:Theoretical Computer Science 7868:"Selfish unsplittable flows" 6918:resource-independent weights 6100:crowding game is replicated 4965:, there is a delay function 4472:does not occur, iff it is a 4406:is homeomorphic to either a 4149:resource-independent weights 3979:must be a Nash equilibrium. 3258:attains its global minimum. 2575:is associated with a number 2555:of players, where each type 2509:set of congestible elements. 2257:) increase the potential by 2204:{\displaystyle d_{e}(x_{e})} 2168:) decrease the potential by 1862:Existence of Nash equilibria 1533:{\displaystyle d_{e}(x_{e})} 7: 8503:Games and Economic Behavior 8320:Games and Economic Behavior 8243:10.1287/moor.25.3.349.12220 7961:Theory of Computing Systems 7789:Games and Economic Behavior 7699:Games and Economic Behavior 7425:Games and Economic Behavior 7281:Games and Economic Behavior 7242:Games and Economic Behavior 7203:Games and Economic Behavior 7106:Games and Economic Behavior 7022:Congestion games in nature: 6976: 6851:{\displaystyle d^{2d+o(d)}} 6660:Every problem in the class 6082:subgame-perfect equilibrium 5185:{\displaystyle P_{i}=\{e\}} 3983:Splittable congestion games 3794:{\displaystyle \delta ^{2}} 1761:such that, for each player 1264:and a vector of strategies 1014:A finite set of strategies 749: 694: 692:. Then the cost matrix is: 513: 10: 9094: 8278:Journal of Economic Theory 7375:Journal of Economic Theory 6992:ּResource allocation games 6129:Multiplicatively-separable 3606:{\displaystyle x_{e}\in Q} 3560:and move them to strategy 3540:of players using strategy 3374:{\displaystyle Q\in S_{i}} 2703:{\displaystyle P\in S_{i}} 2435:Nonatomic congestion games 1810:with a different strategy 1696:is a vector of strategies 1067:{\displaystyle P\in S_{i}} 83: 79:of finding an equilibrium? 8515:10.1016/j.geb.2009.03.009 8404:Telecommunication Systems 8223:Milchtaich, Igal (2000). 8099:10.1016/j.tcs.2008.12.035 7973:10.1007/s00224-011-9315-x 7884:10.1016/j.tcs.2005.09.024 7711:10.1016/j.geb.2005.09.005 7654:10.1007/s00182-014-0443-9 7592:Milchtaich, Igal (2006). 7514:Telecommunication Systems 7479:10.1007/s00182-012-0363-5 7387:10.1016/j.jet.2014.04.005 7293:10.1016/j.geb.2003.06.004 7142:Milchtaich, Igal (1996). 7031:interspecific competition 6922:resource-specific weights 4025:resource-specific weights 4004:Weighted congestion games 2606:of traffic for that type. 786:). In the above example, 116:and need to get to point 68:What is the quantitative 9078:Game theory game classes 8372:10.1007/3-540-45061-0_41 7010:Bayesian-Nash equilibria 6953:) or path in a network ( 6713:). Their algorithm is a 6463:are player-independent ( 6120:Separable cost functions 3381:over the current choice 316:is a little closer than 77:computational complexity 9047:Algorithmic Game Theory 8732:10.1145/1007352.1007445 8612:10.1023/A:1004991825894 8560:10.1145/1007352.1007445 8437:Brown, Joel S. (1990). 8416:10.1023/A:1016770831869 8139:10.1145/1187436.1216584 7926:10.1145/1187436.1216584 7526:10.1023/A:1016770831869 7148:The American Naturalist 6581:When there are at most 6456:{\displaystyle a_{i,e}} 6394:{\displaystyle a_{i,e}} 6250:{\displaystyle a_{i,e}} 6072:Every crowding game is 4991:{\displaystyle d_{i,e}} 4061:{\displaystyle w_{i,e}} 3626:{\displaystyle \delta } 2512:Instead of recognizing 8332:10.1006/game.1997.0542 8290:10.1006/jeth.1996.2203 8022:10.1287/moor.1120.0543 7842:10.1287/moor.1060.0229 7801:10.1006/game.1997.0592 7762:10.1287/moor.1040.0122 7437:10.1006/game.1996.0027 7254:10.1006/game.1998.0699 7215:10.1006/game.1996.0074 7118:10.1006/game.1996.0044 7002:incomplete information 6998:Incomplete information 6852: 6800: 6703:pseudo-polynomial time 6553: 6503: 6457: 6395: 6362: 6251: 6218: 6063: 6009: 5950: 5807: 5624: 5420: 5330: 5275: 5255: 5206: 5186: 5113: 5039: 5019: 4992: 4934: 4914: 4851: 4831: 4750: 4730: 4667: 4647: 4388: 4328: 4241: 4172: 4141: 4062: 3973: 3953: 3933: 3815: 3795: 3768: 3719: 3647: 3627: 3607: 3574: 3554: 3534: 3501: 3395: 3375: 3342: 3322: 3302: 3275: 3252: 3228: 3201: 3174: 3151: 3062: 3012: 2992: 2965: 2929: 2865: 2864:{\displaystyle e\in E} 2836: 2771: 2751: 2731: 2704: 2664: 2634: 2596: 2569: 2546: 2526: 2499: 2475: 2410: 2383: 2363: 2340: 2320: 2300: 2251: 2205: 2162: 2116: 2089: 2062: 2039: 1964: 1939: 1851: 1831: 1804: 1776: 1755: 1683: 1615: 1595: 1561: 1534: 1491: 1463: 1417: 1416:{\displaystyle e\in E} 1388: 1323: 1258: 1257:{\displaystyle e\in E} 1219: 1185: 1088: 1068: 1035: 1005: 979: 956: 937: 917: 898: 878: 859: 839: 820: 800: 772: 686: 663: 643: 624: 604: 585: 499: 472: 452: 433: 413: 394: 373: 350: 330: 310: 290: 270: 250: 230: 210: 190: 170: 150: 130: 110: 93: 28:communication networks 9022:and Noam Nisan about 8191:10.1007/s001820050086 6853: 6801: 6554: 6504: 6458: 6396: 6363: 6252: 6219: 6074:sequentially solvable 6064: 6010: 5951: 5808: 5625: 5421: 5331: 5281:, his delay would be 5276: 5256: 5207: 5187: 5114: 5040: 5020: 5018:{\displaystyle P_{i}} 4993: 4935: 4915: 4852: 4850:{\displaystyle \phi } 4832: 4762:exponential functions 4751: 4731: 4668: 4666:{\displaystyle \phi } 4648: 4578:exponential functions 4567:exponential functions 4534:CG has a unique PNE. 4523:, a unique PNE, or a 4474:series-parallel graph 4389: 4329: 4242: 4173: 4171:{\displaystyle w_{i}} 4142: 4063: 3974: 3972:{\displaystyle \Phi } 3954: 3952:{\displaystyle \Phi } 3934: 3816: 3796: 3769: 3720: 3648: 3646:{\displaystyle \Phi } 3628: 3608: 3575: 3555: 3535: 3502: 3396: 3376: 3343: 3323: 3321:{\displaystyle \Phi } 3303: 3301:{\displaystyle f_{P}} 3276: 3274:{\displaystyle \Phi } 3253: 3251:{\displaystyle \Phi } 3236:extreme value theorem 3229: 3227:{\displaystyle x_{e}} 3202: 3200:{\displaystyle d_{e}} 3175: 3173:{\displaystyle \Phi } 3152: 3063: 3013: 2993: 2991:{\displaystyle S_{i}} 2971:. For a strategy set 2966: 2964:{\displaystyle f_{P}} 2930: 2866: 2837: 2772: 2752: 2732: 2730:{\displaystyle f_{P}} 2705: 2665: 2663:{\displaystyle d_{e}} 2635: 2633:{\displaystyle S_{i}} 2597: 2595:{\displaystyle r_{i}} 2570: 2547: 2527: 2500: 2476: 2411: 2409:{\displaystyle d_{e}} 2384: 2382:{\displaystyle \Phi } 2364: 2362:{\displaystyle \Phi } 2341: 2339:{\displaystyle \Phi } 2321: 2301: 2252: 2206: 2163: 2117: 2115:{\displaystyle Q_{i}} 2090: 2088:{\displaystyle P_{i}} 2063: 2040: 1965: 1912: 1852: 1832: 1830:{\displaystyle Q_{i}} 1805: 1803:{\displaystyle P_{i}} 1777: 1756: 1684: 1616: 1596: 1594:{\displaystyle P_{i}} 1562: 1560:{\displaystyle d_{e}} 1535: 1492: 1464: 1418: 1389: 1324: 1259: 1220: 1186: 1089: 1069: 1036: 1034:{\displaystyle S_{i}} 1006: 980: 957: 938: 918: 899: 879: 860: 840: 821: 806:is the set of roads ( 801: 773: 687: 664: 644: 625: 605: 586: 500: 498:{\displaystyle x^{2}} 473: 453: 434: 414: 395: 374: 351: 331: 311: 291: 271: 251: 231: 211: 191: 171: 156:is connected to node 151: 131: 111: 91: 55:pure Nash equilibrium 8787:10.1109/FOCS.2011.50 8771:. pp. 532–541. 7561:10.1109/SFCS.2005.68 7555:. pp. 142–151. 6817: 6756: 6517: 6467: 6434: 6372: 6282: 6273:Additively-separable 6228: 6138: 6023: 5972: 5820: 5635: 5452: 5340: 5285: 5265: 5216: 5196: 5157: 5049: 5029: 5002: 4969: 4924: 4862: 4841: 4768: 4740: 4678: 4657: 4584: 4554:has that property. 4542:We say that a class 4538:General weighted CGs 4338: 4298: 4277:Weighted network CGs 4257:resource-independent 4182: 4155: 4076: 4039: 4027:): for every player 3963: 3943: 3828: 3805: 3778: 3729: 3657: 3637: 3617: 3584: 3564: 3544: 3511: 3405: 3385: 3352: 3332: 3312: 3285: 3265: 3242: 3211: 3184: 3164: 3072: 3061:{\displaystyle ^{n}} 3026: 3002: 2975: 2948: 2883: 2849: 2781: 2761: 2741: 2714: 2681: 2647: 2617: 2579: 2559: 2536: 2516: 2489: 2459: 2393: 2373: 2353: 2330: 2310: 2261: 2215: 2172: 2126: 2099: 2072: 2052: 1978: 1886: 1841: 1814: 1787: 1766: 1700: 1625: 1605: 1578: 1544: 1501: 1481: 1430: 1401: 1337: 1268: 1242: 1209: 1101: 1078: 1045: 1018: 989: 969: 946: 927: 907: 888: 868: 849: 829: 810: 790: 762: 685:{\displaystyle 0.8x} 673: 669:players go there is 653: 633: 614: 594: 575: 482: 478:players go there is 462: 442: 423: 403: 384: 363: 340: 320: 300: 280: 260: 240: 220: 200: 180: 160: 140: 136:. Suppose that node 120: 100: 59:exact potential game 8955:10.1007/11786986_50 8695:10.1007/11786986_44 8600:Theory and Decision 6902:Weight of players: 6637:and Talwar proved: 6559:for every resource 4998:. Given a strategy 4394:). He proved that: 3688: 3119: 2609:Each agent in type 2602:, representing the 1974:the social welfare 1569:monotone increasing 1004:{\displaystyle n=2} 697: 516: 47:Robert W. Rosenthal 9030:Vazirani, Vijay V. 8920:10.1007/BF01128293 7606:10.1007/11944874_9 7068:10.1007/BF01737559 6848: 6796: 6549: 6499: 6453: 6430:If the base costs 6391: 6358: 6247: 6214: 6059: 6005: 5946: 5803: 5620: 5416: 5326: 5271: 5251: 5212:experiences delay 5202: 5182: 5109: 5108: 5075: 5045:experiences delay 5035: 5015: 4988: 4930: 4910: 4847: 4827: 4746: 4726: 4663: 4643: 4484:of the PNE costs: 4384: 4324: 4237: 4226: 4168: 4137: 4120: 4058: 4035:, there is weight 3969: 3949: 3929: 3928: 3898: 3853: 3811: 3791: 3764: 3715: 3714: 3661: 3643: 3623: 3603: 3570: 3550: 3530: 3497: 3496: 3469: 3424: 3391: 3371: 3338: 3318: 3298: 3271: 3248: 3224: 3197: 3170: 3147: 3146: 3098: 3097: 3058: 3008: 2988: 2961: 2925: 2914: 2861: 2832: 2831: 2807: 2767: 2747: 2727: 2700: 2660: 2630: 2592: 2565: 2542: 2522: 2495: 2471: 2406: 2379: 2359: 2336: 2316: 2296: 2247: 2201: 2158: 2112: 2085: 2058: 2035: 2034: 1997: 1960: 1959: 1911: 1876:potential function 1847: 1827: 1800: 1772: 1751: 1679: 1678: 1651: 1621:experiences delay 1611: 1591: 1557: 1530: 1487: 1459: 1413: 1384: 1319: 1254: 1215: 1181: 1084: 1064: 1031: 1001: 975: 952: 933: 913: 894: 874: 855: 835: 816: 796: 768: 695: 682: 659: 639: 620: 600: 581: 514: 495: 468: 448: 429: 409: 390: 369: 346: 326: 306: 286: 266: 246: 226: 206: 186: 166: 146: 126: 106: 94: 9018:Lecture notes of 8964:978-3-540-35905-0 8796:978-0-7695-4571-4 8741:978-1-58113-852-8 8704:978-3-540-35905-0 8667:978-3-540-74456-6 8569:978-1-58113-852-8 8381:978-3-540-45061-0 8092:(17): 1552–1563. 8066:978-3-642-22012-8 7615:978-3-540-68141-0 7340:10.1109/90.251910 7102:"Potential Games" 6957:) or any subset ( 6779: 6773: 6509:for every player 6424:habitat selection 6051: 5997: 5274:{\displaystyle f} 5205:{\displaystyle i} 5053: 5038:{\displaystyle i} 4933:{\displaystyle f} 4749:{\displaystyle f} 4198: 4092: 3883: 3838: 3814:{\displaystyle P} 3633:, so its term in 3573:{\displaystyle Q} 3553:{\displaystyle P} 3454: 3409: 3394:{\displaystyle P} 3341:{\displaystyle i} 3082: 3011:{\displaystyle n} 2899: 2845:For each element 2785: 2777:. By definition, 2770:{\displaystyle P} 2750:{\displaystyle i} 2568:{\displaystyle i} 2545:{\displaystyle n} 2525:{\displaystyle n} 2498:{\displaystyle E} 2319:{\displaystyle i} 2061:{\displaystyle i} 1982: 1896: 1850:{\displaystyle i} 1775:{\displaystyle i} 1629: 1614:{\displaystyle i} 1574:Given a strategy 1490:{\displaystyle e} 1397:For each element 1238:For each element 1218:{\displaystyle E} 1087:{\displaystyle E} 978:{\displaystyle n} 955:{\displaystyle T} 936:{\displaystyle B} 916:{\displaystyle B} 897:{\displaystyle O} 877:{\displaystyle T} 858:{\displaystyle A} 838:{\displaystyle A} 819:{\displaystyle O} 799:{\displaystyle E} 771:{\displaystyle E} 738: 737: 662:{\displaystyle x} 642:{\displaystyle T} 623:{\displaystyle B} 603:{\displaystyle T} 584:{\displaystyle A} 557: 556: 471:{\displaystyle x} 451:{\displaystyle T} 432:{\displaystyle B} 412:{\displaystyle T} 393:{\displaystyle A} 372:{\displaystyle T} 349:{\displaystyle A} 329:{\displaystyle B} 309:{\displaystyle A} 289:{\displaystyle T} 269:{\displaystyle B} 249:{\displaystyle O} 229:{\displaystyle T} 209:{\displaystyle A} 189:{\displaystyle O} 169:{\displaystyle T} 149:{\displaystyle O} 129:{\displaystyle T} 109:{\displaystyle O} 9085: 9064: 9052: 9038:Roughgarden, Tim 9000: 8999: 8975: 8969: 8968: 8938: 8932: 8931: 8903: 8897: 8896: 8856: 8850: 8849: 8839: 8815: 8809: 8808: 8780: 8760: 8754: 8753: 8715: 8709: 8708: 8678: 8672: 8671: 8641: 8632: 8631: 8591: 8582: 8581: 8543: 8537: 8536: 8526: 8494: 8483: 8482: 8434: 8428: 8427: 8395: 8386: 8385: 8355: 8344: 8343: 8311: 8302: 8301: 8269: 8263: 8262: 8220: 8211: 8210: 8170: 8159: 8158: 8118: 8112: 8111: 8101: 8077: 8071: 8070: 8040: 8034: 8033: 7999: 7993: 7992: 7952: 7946: 7945: 7905: 7896: 7895: 7863: 7854: 7853: 7819: 7813: 7812: 7780: 7774: 7773: 7739: 7733: 7732: 7722: 7690: 7684: 7683: 7665: 7633: 7620: 7619: 7589: 7583: 7582: 7544: 7538: 7537: 7505: 7499: 7498: 7473:(4): 1085–1096. 7458: 7449: 7448: 7416: 7399: 7398: 7366: 7360: 7359: 7319: 7313: 7312: 7272: 7266: 7265: 7233: 7227: 7226: 7194: 7188: 7187: 7139: 7130: 7129: 7097: 7088: 7086: 7051: 6968:) or identical ( 6943:cost-functions). 6857: 6855: 6854: 6849: 6847: 6846: 6805: 6803: 6802: 6797: 6780: 6775: 6774: 6769: 6760: 6558: 6556: 6555: 6550: 6548: 6547: 6535: 6534: 6508: 6506: 6505: 6500: 6498: 6497: 6485: 6484: 6462: 6460: 6459: 6454: 6452: 6451: 6400: 6398: 6397: 6392: 6390: 6389: 6367: 6365: 6364: 6359: 6354: 6353: 6335: 6334: 6313: 6312: 6300: 6299: 6256: 6254: 6253: 6248: 6246: 6245: 6223: 6221: 6220: 6215: 6210: 6209: 6191: 6190: 6169: 6168: 6156: 6155: 6068: 6066: 6065: 6060: 6058: 6057: 6056: 6047: 6035: 6014: 6012: 6011: 6006: 6004: 6003: 6002: 5993: 5981: 5955: 5953: 5952: 5947: 5812: 5810: 5809: 5804: 5793: 5792: 5765: 5764: 5737: 5736: 5709: 5708: 5681: 5680: 5653: 5652: 5629: 5627: 5626: 5621: 5610: 5609: 5582: 5581: 5554: 5553: 5526: 5525: 5498: 5497: 5470: 5469: 5425: 5423: 5422: 5417: 5406: 5405: 5393: 5392: 5371: 5370: 5358: 5357: 5335: 5333: 5332: 5327: 5316: 5315: 5303: 5302: 5280: 5278: 5277: 5272: 5260: 5258: 5257: 5252: 5247: 5246: 5234: 5233: 5211: 5209: 5208: 5203: 5191: 5189: 5188: 5183: 5169: 5168: 5118: 5116: 5115: 5110: 5104: 5103: 5091: 5090: 5074: 5073: 5072: 5044: 5042: 5041: 5036: 5024: 5022: 5021: 5016: 5014: 5013: 4997: 4995: 4994: 4989: 4987: 4986: 4939: 4937: 4936: 4931: 4919: 4917: 4916: 4911: 4909: 4908: 4893: 4892: 4874: 4873: 4856: 4854: 4853: 4848: 4836: 4834: 4833: 4828: 4826: 4825: 4813: 4809: 4808: 4780: 4779: 4755: 4753: 4752: 4747: 4735: 4733: 4732: 4727: 4725: 4724: 4709: 4708: 4690: 4689: 4672: 4670: 4669: 4664: 4652: 4650: 4649: 4644: 4642: 4641: 4629: 4625: 4624: 4596: 4595: 4574:affine functions 4560:linear functions 4525:Pareto-efficient 4496:is a connection 4470:Braess's paradox 4468:guarantees that 4408:parallel network 4393: 4391: 4390: 4385: 4383: 4378: 4377: 4368: 4360: 4355: 4354: 4345: 4333: 4331: 4330: 4325: 4323: 4322: 4310: 4309: 4246: 4244: 4243: 4238: 4236: 4235: 4225: 4224: 4223: 4194: 4193: 4177: 4175: 4174: 4169: 4167: 4166: 4146: 4144: 4143: 4138: 4136: 4135: 4119: 4118: 4117: 4088: 4087: 4067: 4065: 4064: 4059: 4057: 4056: 3978: 3976: 3975: 3970: 3958: 3956: 3955: 3950: 3938: 3936: 3935: 3930: 3921: 3920: 3908: 3907: 3897: 3876: 3875: 3863: 3862: 3852: 3820: 3818: 3817: 3812: 3800: 3798: 3797: 3792: 3790: 3789: 3773: 3771: 3770: 3765: 3760: 3759: 3747: 3746: 3724: 3722: 3721: 3716: 3698: 3697: 3687: 3680: 3679: 3669: 3652: 3650: 3649: 3644: 3632: 3630: 3629: 3624: 3612: 3610: 3609: 3604: 3596: 3595: 3579: 3577: 3576: 3571: 3559: 3557: 3556: 3551: 3539: 3537: 3536: 3531: 3529: 3528: 3506: 3504: 3503: 3498: 3492: 3491: 3479: 3478: 3468: 3447: 3446: 3434: 3433: 3423: 3400: 3398: 3397: 3392: 3380: 3378: 3377: 3372: 3370: 3369: 3347: 3345: 3344: 3339: 3327: 3325: 3324: 3319: 3307: 3305: 3304: 3299: 3297: 3296: 3280: 3278: 3277: 3272: 3257: 3255: 3254: 3249: 3233: 3231: 3230: 3225: 3223: 3222: 3206: 3204: 3203: 3198: 3196: 3195: 3179: 3177: 3176: 3171: 3156: 3154: 3153: 3148: 3129: 3128: 3118: 3117: 3116: 3106: 3096: 3067: 3065: 3064: 3059: 3057: 3056: 3047: 3046: 3017: 3015: 3014: 3009: 2997: 2995: 2994: 2989: 2987: 2986: 2970: 2968: 2967: 2962: 2960: 2959: 2934: 2932: 2931: 2926: 2924: 2923: 2913: 2895: 2894: 2870: 2868: 2867: 2862: 2841: 2839: 2838: 2833: 2830: 2829: 2817: 2816: 2806: 2805: 2804: 2776: 2774: 2773: 2768: 2756: 2754: 2753: 2748: 2736: 2734: 2733: 2728: 2726: 2725: 2709: 2707: 2706: 2701: 2699: 2698: 2669: 2667: 2666: 2661: 2659: 2658: 2639: 2637: 2636: 2631: 2629: 2628: 2601: 2599: 2598: 2593: 2591: 2590: 2574: 2572: 2571: 2566: 2551: 2549: 2548: 2543: 2531: 2529: 2528: 2523: 2504: 2502: 2501: 2496: 2480: 2478: 2477: 2472: 2415: 2413: 2412: 2407: 2405: 2404: 2388: 2386: 2385: 2380: 2368: 2366: 2365: 2360: 2345: 2343: 2342: 2337: 2325: 2323: 2322: 2317: 2305: 2303: 2302: 2297: 2286: 2285: 2273: 2272: 2256: 2254: 2253: 2248: 2246: 2245: 2233: 2232: 2210: 2208: 2207: 2202: 2197: 2196: 2184: 2183: 2167: 2165: 2164: 2159: 2157: 2156: 2144: 2143: 2121: 2119: 2118: 2113: 2111: 2110: 2094: 2092: 2091: 2086: 2084: 2083: 2067: 2065: 2064: 2059: 2044: 2042: 2041: 2036: 2030: 2029: 2017: 2016: 2007: 2006: 1996: 1969: 1967: 1966: 1961: 1949: 1948: 1938: 1937: 1936: 1926: 1910: 1868:Nash equilibrium 1856: 1854: 1853: 1848: 1836: 1834: 1833: 1828: 1826: 1825: 1809: 1807: 1806: 1801: 1799: 1798: 1781: 1779: 1778: 1773: 1760: 1758: 1757: 1752: 1747: 1746: 1728: 1727: 1715: 1714: 1694:Nash equilibrium 1688: 1686: 1685: 1680: 1674: 1673: 1661: 1660: 1650: 1649: 1648: 1620: 1618: 1617: 1612: 1600: 1598: 1597: 1592: 1590: 1589: 1566: 1564: 1563: 1558: 1556: 1555: 1539: 1537: 1536: 1531: 1526: 1525: 1513: 1512: 1496: 1494: 1493: 1488: 1471:latency function 1468: 1466: 1465: 1460: 1458: 1450: 1442: 1441: 1422: 1420: 1419: 1414: 1393: 1391: 1390: 1385: 1380: 1379: 1349: 1348: 1328: 1326: 1325: 1320: 1315: 1314: 1296: 1295: 1283: 1282: 1263: 1261: 1260: 1255: 1224: 1222: 1221: 1216: 1190: 1188: 1187: 1182: 1126: 1125: 1113: 1112: 1093: 1091: 1090: 1085: 1073: 1071: 1070: 1065: 1063: 1062: 1040: 1038: 1037: 1032: 1030: 1029: 1010: 1008: 1007: 1002: 984: 982: 981: 976: 961: 959: 958: 953: 942: 940: 939: 934: 922: 920: 919: 914: 903: 901: 900: 895: 883: 881: 880: 875: 864: 862: 861: 856: 844: 842: 841: 836: 825: 823: 822: 817: 805: 803: 802: 797: 777: 775: 774: 769: 698: 691: 689: 688: 683: 668: 666: 665: 660: 648: 646: 645: 640: 629: 627: 626: 621: 609: 607: 606: 601: 590: 588: 587: 582: 517: 504: 502: 501: 496: 494: 493: 477: 475: 474: 469: 457: 455: 454: 449: 438: 436: 435: 430: 418: 416: 415: 410: 399: 397: 396: 391: 378: 376: 375: 370: 355: 353: 352: 347: 335: 333: 332: 327: 315: 313: 312: 307: 295: 293: 292: 287: 275: 273: 272: 267: 255: 253: 252: 247: 235: 233: 232: 227: 215: 213: 212: 207: 195: 193: 192: 187: 175: 173: 172: 167: 155: 153: 152: 147: 135: 133: 132: 127: 115: 113: 112: 107: 36:natural habitats 20:Congestion games 9093: 9092: 9088: 9087: 9086: 9084: 9083: 9082: 9068: 9067: 9061: 9050: 9009: 9004: 9003: 8976: 8972: 8965: 8939: 8935: 8904: 8900: 8877:10.1145/2614687 8871:(1): 2:1–2:32. 8857: 8853: 8816: 8812: 8797: 8761: 8757: 8742: 8716: 8712: 8705: 8679: 8675: 8668: 8642: 8635: 8592: 8585: 8570: 8544: 8540: 8495: 8486: 8455:10.2307/2409448 8435: 8431: 8396: 8389: 8382: 8356: 8347: 8312: 8305: 8270: 8266: 8221: 8214: 8171: 8162: 8119: 8115: 8078: 8074: 8067: 8041: 8037: 8000: 7996: 7953: 7949: 7906: 7899: 7864: 7857: 7820: 7816: 7781: 7777: 7740: 7736: 7691: 7687: 7634: 7623: 7616: 7590: 7586: 7571: 7545: 7541: 7506: 7502: 7459: 7452: 7417: 7402: 7367: 7363: 7320: 7316: 7273: 7269: 7234: 7230: 7195: 7191: 7140: 7133: 7098: 7091: 7052: 7045: 7040: 6979: 6933:player-specific 6878: 6824: 6820: 6818: 6815: 6814: 6768: 6761: 6759: 6757: 6754: 6753: 6699: 6655:PSPACE-complete 6630: 6625: 6616: 6602:Every weighted 6543: 6539: 6524: 6520: 6518: 6515: 6514: 6493: 6489: 6474: 6470: 6468: 6465: 6464: 6441: 6437: 6435: 6432: 6431: 6379: 6375: 6373: 6370: 6369: 6349: 6345: 6324: 6320: 6308: 6304: 6289: 6285: 6283: 6280: 6279: 6235: 6231: 6229: 6226: 6225: 6205: 6201: 6180: 6176: 6164: 6160: 6145: 6141: 6139: 6136: 6135: 6122: 6114:bipartite graph 6078:sequential game 6052: 6037: 6031: 6030: 6029: 6024: 6021: 6020: 5998: 5983: 5977: 5976: 5975: 5973: 5970: 5969: 5821: 5818: 5817: 5782: 5778: 5754: 5750: 5726: 5722: 5698: 5694: 5670: 5666: 5642: 5638: 5636: 5633: 5632: 5599: 5595: 5571: 5567: 5543: 5539: 5515: 5511: 5487: 5483: 5459: 5455: 5453: 5450: 5449: 5401: 5397: 5382: 5378: 5366: 5362: 5347: 5343: 5341: 5338: 5337: 5311: 5307: 5292: 5288: 5286: 5283: 5282: 5266: 5263: 5262: 5242: 5238: 5223: 5219: 5217: 5214: 5213: 5197: 5194: 5193: 5164: 5160: 5158: 5155: 5154: 5125: 5099: 5095: 5080: 5076: 5068: 5064: 5057: 5050: 5047: 5046: 5030: 5027: 5026: 5009: 5005: 5003: 5000: 4999: 4976: 4972: 4970: 4967: 4966: 4955: 4947: 4925: 4922: 4921: 4904: 4900: 4888: 4884: 4869: 4865: 4863: 4860: 4859: 4842: 4839: 4838: 4821: 4817: 4804: 4800: 4790: 4775: 4771: 4769: 4766: 4765: 4741: 4738: 4737: 4720: 4716: 4704: 4700: 4685: 4681: 4679: 4676: 4675: 4658: 4655: 4654: 4637: 4633: 4620: 4616: 4606: 4591: 4587: 4585: 4582: 4581: 4540: 4379: 4373: 4369: 4364: 4356: 4350: 4346: 4341: 4339: 4336: 4335: 4318: 4314: 4305: 4301: 4299: 4296: 4295: 4279: 4253: 4231: 4227: 4219: 4215: 4202: 4189: 4185: 4183: 4180: 4179: 4162: 4158: 4156: 4153: 4152: 4125: 4121: 4113: 4109: 4096: 4083: 4079: 4077: 4074: 4073: 4046: 4042: 4040: 4037: 4036: 4006: 3985: 3964: 3961: 3960: 3944: 3941: 3940: 3916: 3912: 3903: 3899: 3887: 3871: 3867: 3858: 3854: 3842: 3829: 3826: 3825: 3806: 3803: 3802: 3785: 3781: 3779: 3776: 3775: 3755: 3751: 3742: 3738: 3730: 3727: 3726: 3693: 3689: 3675: 3671: 3670: 3665: 3658: 3655: 3654: 3638: 3635: 3634: 3618: 3615: 3614: 3591: 3587: 3585: 3582: 3581: 3565: 3562: 3561: 3545: 3542: 3541: 3524: 3520: 3512: 3509: 3508: 3487: 3483: 3474: 3470: 3458: 3442: 3438: 3429: 3425: 3413: 3406: 3403: 3402: 3386: 3383: 3382: 3365: 3361: 3353: 3350: 3349: 3333: 3330: 3329: 3313: 3310: 3309: 3292: 3288: 3286: 3283: 3282: 3266: 3263: 3262: 3243: 3240: 3239: 3218: 3214: 3212: 3209: 3208: 3191: 3187: 3185: 3182: 3181: 3180:is continuous: 3165: 3162: 3161: 3124: 3120: 3112: 3108: 3107: 3102: 3086: 3073: 3070: 3069: 3052: 3048: 3042: 3038: 3027: 3024: 3023: 3003: 3000: 2999: 2982: 2978: 2976: 2973: 2972: 2955: 2951: 2949: 2946: 2945: 2942: 2919: 2915: 2903: 2890: 2886: 2884: 2881: 2880: 2850: 2847: 2846: 2825: 2821: 2812: 2808: 2800: 2796: 2789: 2782: 2779: 2778: 2762: 2759: 2758: 2757:using strategy 2742: 2739: 2738: 2721: 2717: 2715: 2712: 2711: 2694: 2690: 2682: 2679: 2678: 2654: 2650: 2648: 2645: 2644: 2624: 2620: 2618: 2615: 2614: 2586: 2582: 2580: 2577: 2576: 2560: 2557: 2556: 2537: 2534: 2533: 2517: 2514: 2513: 2490: 2487: 2486: 2460: 2457: 2456: 2437: 2429: 2400: 2396: 2394: 2391: 2390: 2374: 2371: 2370: 2354: 2351: 2350: 2331: 2328: 2327: 2311: 2308: 2307: 2281: 2277: 2268: 2264: 2262: 2259: 2258: 2241: 2237: 2228: 2224: 2216: 2213: 2212: 2192: 2188: 2179: 2175: 2173: 2170: 2169: 2152: 2148: 2139: 2135: 2127: 2124: 2123: 2106: 2102: 2100: 2097: 2096: 2079: 2075: 2073: 2070: 2069: 2053: 2050: 2049: 2025: 2021: 2012: 2008: 2002: 1998: 1986: 1979: 1976: 1975: 1944: 1940: 1932: 1928: 1927: 1916: 1900: 1887: 1884: 1883: 1872:pure strategies 1866:Every CG has a 1864: 1842: 1839: 1838: 1821: 1817: 1815: 1812: 1811: 1794: 1790: 1788: 1785: 1784: 1767: 1764: 1763: 1742: 1738: 1723: 1719: 1710: 1706: 1701: 1698: 1697: 1669: 1665: 1656: 1652: 1644: 1640: 1633: 1626: 1623: 1622: 1606: 1603: 1602: 1585: 1581: 1579: 1576: 1575: 1551: 1547: 1545: 1542: 1541: 1521: 1517: 1508: 1504: 1502: 1499: 1498: 1482: 1479: 1478: 1454: 1446: 1437: 1433: 1431: 1428: 1427: 1402: 1399: 1398: 1375: 1371: 1344: 1340: 1338: 1335: 1334: 1310: 1306: 1291: 1287: 1278: 1274: 1269: 1266: 1265: 1243: 1240: 1239: 1210: 1207: 1206: 1121: 1117: 1108: 1104: 1102: 1099: 1098: 1079: 1076: 1075: 1074:is a subset of 1058: 1054: 1046: 1043: 1042: 1025: 1021: 1019: 1016: 1015: 990: 987: 986: 970: 967: 966: 947: 944: 943: 928: 925: 924: 908: 905: 904: 889: 886: 885: 869: 866: 865: 850: 847: 846: 830: 827: 826: 811: 808: 807: 791: 788: 787: 763: 760: 759: 752: 747: 706: 703: 674: 671: 670: 654: 651: 650: 634: 631: 630: 615: 612: 611: 595: 592: 591: 576: 573: 572: 561:Nash equilibria 525: 522: 489: 485: 483: 480: 479: 463: 460: 459: 443: 440: 439: 424: 421: 420: 404: 401: 400: 385: 382: 381: 364: 361: 360: 341: 338: 337: 321: 318: 317: 301: 298: 297: 281: 278: 277: 261: 258: 257: 241: 238: 237: 221: 218: 217: 201: 198: 197: 181: 178: 177: 176:via two paths: 161: 158: 157: 141: 138: 137: 121: 118: 117: 101: 98: 97: 86: 51:pure strategies 17: 12: 11: 5: 9091: 9081: 9080: 9066: 9065: 9059: 9026: 9020:Michal Feldman 9016: 9008: 9007:External links 9005: 9002: 9001: 8970: 8963: 8933: 8898: 8851: 8830:(2): 111–121. 8810: 8795: 8755: 8740: 8710: 8703: 8673: 8666: 8633: 8606:(2): 193–206. 8583: 8568: 8538: 8509:(2): 750–757. 8484: 8449:(3): 732–746. 8429: 8410:(4): 385–409. 8387: 8380: 8345: 8326:(1): 161–182. 8303: 8284:(1): 225–237. 8264: 8237:(3): 349–364. 8212: 8185:(4): 501–509. 8160: 8113: 8072: 8065: 8035: 8016:(3): 419–436. 7994: 7947: 7897: 7878:(2): 226–239. 7855: 7836:(1): 215–232. 7814: 7775: 7756:(1): 225–244. 7734: 7705:(2): 321–346. 7685: 7648:(3): 515–541. 7621: 7614: 7584: 7569: 7539: 7520:(4): 385–409. 7500: 7450: 7431:(1): 111–124. 7400: 7361: 7334:(5): 510–521. 7314: 7287:(2): 389–403. 7267: 7248:(2): 171–180. 7228: 7189: 7160:10.1086/285878 7154:(5): 760–783. 7131: 7112:(1): 124–143. 7089: 7042: 7041: 7039: 7036: 7035: 7034: 7019: 7013: 7006:Bayesian games 6995: 6989: 6978: 6975: 6974: 6973: 6962: 6944: 6925: 6900: 6877: 6874: 6862: 6861: 6845: 6842: 6839: 6836: 6833: 6830: 6827: 6823: 6807: 6795: 6792: 6789: 6786: 6783: 6778: 6772: 6767: 6764: 6743: 6742: 6739: 6698: 6695: 6690: 6689: 6676: 6666: 6665: 6658: 6647: 6629: 6626: 6624: 6621: 6615: 6612: 6600: 6599: 6598: 6597: 6593: 6590: 6576: 6572: 6546: 6542: 6538: 6533: 6530: 6527: 6523: 6496: 6492: 6488: 6483: 6480: 6477: 6473: 6450: 6447: 6444: 6440: 6420:M/M/1 queueing 6415: 6414: 6388: 6385: 6382: 6378: 6357: 6352: 6348: 6344: 6341: 6338: 6333: 6330: 6327: 6323: 6319: 6316: 6311: 6307: 6303: 6298: 6295: 6292: 6288: 6276:cost functions 6270: 6244: 6241: 6238: 6234: 6213: 6208: 6204: 6200: 6197: 6194: 6189: 6186: 6183: 6179: 6175: 6172: 6167: 6163: 6159: 6154: 6151: 6148: 6144: 6132:cost functions 6121: 6118: 6055: 6050: 6046: 6043: 6040: 6034: 6028: 6017:weakly acyclic 6001: 5996: 5992: 5989: 5986: 5980: 5965: 5964: 5961: 5945: 5942: 5939: 5936: 5933: 5930: 5927: 5924: 5921: 5918: 5915: 5912: 5909: 5906: 5903: 5900: 5897: 5894: 5891: 5888: 5885: 5882: 5879: 5876: 5873: 5870: 5867: 5864: 5861: 5858: 5855: 5852: 5849: 5846: 5843: 5840: 5837: 5834: 5831: 5828: 5825: 5814: 5813: 5802: 5799: 5796: 5791: 5788: 5785: 5781: 5777: 5774: 5771: 5768: 5763: 5760: 5757: 5753: 5749: 5746: 5743: 5740: 5735: 5732: 5729: 5725: 5721: 5718: 5715: 5712: 5707: 5704: 5701: 5697: 5693: 5690: 5687: 5684: 5679: 5676: 5673: 5669: 5665: 5662: 5659: 5656: 5651: 5648: 5645: 5641: 5630: 5619: 5616: 5613: 5608: 5605: 5602: 5598: 5594: 5591: 5588: 5585: 5580: 5577: 5574: 5570: 5566: 5563: 5560: 5557: 5552: 5549: 5546: 5542: 5538: 5535: 5532: 5529: 5524: 5521: 5518: 5514: 5510: 5507: 5504: 5501: 5496: 5493: 5490: 5486: 5482: 5479: 5476: 5473: 5468: 5465: 5462: 5458: 5415: 5412: 5409: 5404: 5400: 5396: 5391: 5388: 5385: 5381: 5377: 5374: 5369: 5365: 5361: 5356: 5353: 5350: 5346: 5325: 5322: 5319: 5314: 5310: 5306: 5301: 5298: 5295: 5291: 5270: 5250: 5245: 5241: 5237: 5232: 5229: 5226: 5222: 5201: 5181: 5178: 5175: 5172: 5167: 5163: 5144: 5143: 5140: 5124: 5121: 5107: 5102: 5098: 5094: 5089: 5086: 5083: 5079: 5071: 5067: 5063: 5060: 5056: 5034: 5012: 5008: 4985: 4982: 4979: 4975: 4954: 4951: 4946: 4943: 4942: 4941: 4929: 4907: 4903: 4899: 4896: 4891: 4887: 4883: 4880: 4877: 4872: 4868: 4846: 4824: 4820: 4816: 4812: 4807: 4803: 4799: 4796: 4793: 4789: 4786: 4783: 4778: 4774: 4757: 4745: 4723: 4719: 4715: 4712: 4707: 4703: 4699: 4696: 4693: 4688: 4684: 4662: 4640: 4636: 4632: 4628: 4623: 4619: 4615: 4612: 4609: 4605: 4602: 4599: 4594: 4590: 4570: 4563: 4539: 4536: 4517: 4516: 4501: 4478: 4477: 4462: 4439: 4438: 4419: 4382: 4376: 4372: 4367: 4363: 4359: 4353: 4349: 4344: 4321: 4317: 4313: 4308: 4304: 4278: 4275: 4274: 4273: 4270: 4267: 4264: 4252: 4249: 4234: 4230: 4222: 4218: 4214: 4211: 4208: 4205: 4201: 4197: 4192: 4188: 4165: 4161: 4134: 4131: 4128: 4124: 4116: 4112: 4108: 4105: 4102: 4099: 4095: 4091: 4086: 4082: 4055: 4052: 4049: 4045: 4005: 4002: 3989:splittable CG, 3984: 3981: 3968: 3948: 3927: 3924: 3919: 3915: 3911: 3906: 3902: 3896: 3893: 3890: 3886: 3882: 3879: 3874: 3870: 3866: 3861: 3857: 3851: 3848: 3845: 3841: 3837: 3834: 3810: 3788: 3784: 3763: 3758: 3754: 3750: 3745: 3741: 3737: 3734: 3713: 3710: 3707: 3704: 3701: 3696: 3692: 3686: 3683: 3678: 3674: 3668: 3664: 3642: 3622: 3602: 3599: 3594: 3590: 3580:. Now for any 3569: 3549: 3527: 3523: 3519: 3516: 3495: 3490: 3486: 3482: 3477: 3473: 3467: 3464: 3461: 3457: 3453: 3450: 3445: 3441: 3437: 3432: 3428: 3422: 3419: 3416: 3412: 3390: 3368: 3364: 3360: 3357: 3337: 3317: 3308:that minimize 3295: 3291: 3270: 3247: 3221: 3217: 3194: 3190: 3169: 3145: 3142: 3138: 3135: 3132: 3127: 3123: 3115: 3111: 3105: 3101: 3095: 3092: 3089: 3085: 3081: 3078: 3055: 3051: 3045: 3041: 3037: 3034: 3031: 3020:compact subset 3007: 2985: 2981: 2958: 2954: 2941: 2938: 2937: 2936: 2922: 2918: 2912: 2909: 2906: 2902: 2898: 2893: 2889: 2860: 2857: 2854: 2843: 2828: 2824: 2820: 2815: 2811: 2803: 2799: 2795: 2792: 2788: 2766: 2746: 2724: 2720: 2697: 2693: 2689: 2686: 2675: 2657: 2653: 2641: 2627: 2623: 2607: 2589: 2585: 2564: 2541: 2521: 2510: 2494: 2470: 2467: 2464: 2436: 2433: 2428: 2425: 2403: 2399: 2378: 2358: 2335: 2315: 2295: 2292: 2289: 2284: 2280: 2276: 2271: 2267: 2244: 2240: 2236: 2231: 2227: 2223: 2220: 2200: 2195: 2191: 2187: 2182: 2178: 2155: 2151: 2147: 2142: 2138: 2134: 2131: 2109: 2105: 2082: 2078: 2068:switches from 2057: 2033: 2028: 2024: 2020: 2015: 2011: 2005: 2001: 1995: 1992: 1989: 1985: 1958: 1955: 1952: 1947: 1943: 1935: 1931: 1925: 1922: 1919: 1915: 1909: 1906: 1903: 1899: 1895: 1892: 1863: 1860: 1859: 1858: 1846: 1824: 1820: 1797: 1793: 1771: 1750: 1745: 1741: 1737: 1734: 1731: 1726: 1722: 1718: 1713: 1709: 1705: 1690: 1677: 1672: 1668: 1664: 1659: 1655: 1647: 1643: 1639: 1636: 1632: 1610: 1588: 1584: 1572: 1554: 1550: 1529: 1524: 1520: 1516: 1511: 1507: 1486: 1457: 1453: 1449: 1445: 1440: 1436: 1425:delay function 1412: 1409: 1406: 1395: 1383: 1378: 1374: 1370: 1367: 1364: 1361: 1358: 1355: 1352: 1347: 1343: 1333:is defined as 1318: 1313: 1309: 1305: 1302: 1299: 1294: 1290: 1286: 1281: 1277: 1273: 1253: 1250: 1247: 1236: 1235: 1234: 1214: 1203: 1180: 1177: 1174: 1171: 1168: 1165: 1162: 1159: 1156: 1153: 1150: 1147: 1144: 1141: 1138: 1135: 1132: 1129: 1124: 1120: 1116: 1111: 1107: 1083: 1061: 1057: 1053: 1050: 1028: 1024: 1012: 1000: 997: 994: 974: 963: 951: 932: 912: 893: 873: 854: 834: 815: 795: 767: 751: 748: 746: 743: 736: 735: 732: 729: 725: 724: 721: 718: 714: 713: 710: 707: 704: 701: 681: 678: 658: 638: 619: 599: 580: 555: 554: 551: 548: 544: 543: 540: 537: 533: 532: 529: 526: 523: 520: 492: 488: 467: 447: 428: 408: 389: 368: 345: 325: 305: 285: 265: 245: 225: 205: 185: 165: 145: 125: 105: 85: 82: 81: 80: 73: 66: 15: 9: 6: 4: 3: 2: 9090: 9079: 9076: 9075: 9073: 9062: 9060:0-521-87282-0 9056: 9049: 9048: 9043: 9039: 9035: 9031: 9027: 9025: 9021: 9017: 9015: 9011: 9010: 8997: 8993: 8989: 8985: 8981: 8974: 8966: 8960: 8956: 8952: 8948: 8944: 8937: 8929: 8925: 8921: 8917: 8913: 8909: 8902: 8894: 8890: 8886: 8882: 8878: 8874: 8870: 8866: 8862: 8855: 8847: 8843: 8838: 8833: 8829: 8825: 8821: 8814: 8806: 8802: 8798: 8792: 8788: 8784: 8779: 8774: 8770: 8766: 8759: 8751: 8747: 8743: 8737: 8733: 8729: 8725: 8721: 8714: 8706: 8700: 8696: 8692: 8688: 8684: 8677: 8669: 8663: 8659: 8655: 8651: 8647: 8640: 8638: 8629: 8625: 8621: 8617: 8613: 8609: 8605: 8601: 8597: 8590: 8588: 8579: 8575: 8571: 8565: 8561: 8557: 8553: 8549: 8542: 8534: 8530: 8525: 8520: 8516: 8512: 8508: 8504: 8500: 8493: 8491: 8489: 8480: 8476: 8472: 8468: 8464: 8460: 8456: 8452: 8448: 8444: 8440: 8433: 8425: 8421: 8417: 8413: 8409: 8405: 8401: 8394: 8392: 8383: 8377: 8373: 8369: 8365: 8361: 8354: 8352: 8350: 8341: 8337: 8333: 8329: 8325: 8321: 8317: 8310: 8308: 8299: 8295: 8291: 8287: 8283: 8279: 8275: 8268: 8260: 8256: 8252: 8248: 8244: 8240: 8236: 8232: 8231: 8226: 8219: 8217: 8208: 8204: 8200: 8196: 8192: 8188: 8184: 8180: 8176: 8169: 8167: 8165: 8156: 8152: 8148: 8144: 8140: 8136: 8132: 8128: 8124: 8117: 8109: 8105: 8100: 8095: 8091: 8087: 8083: 8076: 8068: 8062: 8058: 8054: 8050: 8046: 8039: 8031: 8027: 8023: 8019: 8015: 8011: 8010: 8005: 7998: 7990: 7986: 7982: 7978: 7974: 7970: 7966: 7962: 7958: 7951: 7943: 7939: 7935: 7931: 7927: 7923: 7919: 7915: 7911: 7904: 7902: 7893: 7889: 7885: 7881: 7877: 7873: 7869: 7862: 7860: 7851: 7847: 7843: 7839: 7835: 7831: 7830: 7825: 7818: 7810: 7806: 7802: 7798: 7795:(1): 85–101. 7794: 7790: 7786: 7779: 7771: 7767: 7763: 7759: 7755: 7751: 7750: 7745: 7738: 7730: 7726: 7721: 7716: 7712: 7708: 7704: 7700: 7696: 7689: 7681: 7677: 7673: 7669: 7664: 7659: 7655: 7651: 7647: 7643: 7639: 7632: 7630: 7628: 7626: 7617: 7611: 7607: 7603: 7599: 7595: 7588: 7580: 7576: 7572: 7570:0-7695-2468-0 7566: 7562: 7558: 7554: 7550: 7543: 7535: 7531: 7527: 7523: 7519: 7515: 7511: 7504: 7496: 7492: 7488: 7484: 7480: 7476: 7472: 7468: 7464: 7457: 7455: 7446: 7442: 7438: 7434: 7430: 7426: 7422: 7415: 7413: 7411: 7409: 7407: 7405: 7396: 7392: 7388: 7384: 7380: 7376: 7372: 7365: 7357: 7353: 7349: 7345: 7341: 7337: 7333: 7329: 7325: 7318: 7310: 7306: 7302: 7298: 7294: 7290: 7286: 7282: 7278: 7271: 7263: 7259: 7255: 7251: 7247: 7243: 7239: 7232: 7224: 7220: 7216: 7212: 7208: 7204: 7200: 7193: 7185: 7181: 7177: 7173: 7169: 7165: 7161: 7157: 7153: 7149: 7145: 7138: 7136: 7127: 7123: 7119: 7115: 7111: 7107: 7103: 7096: 7094: 7085: 7081: 7077: 7073: 7069: 7065: 7061: 7057: 7050: 7048: 7043: 7032: 7027: 7023: 7020: 7017: 7014: 7011: 7007: 7003: 6999: 6996: 6993: 6990: 6987: 6986: 6981: 6980: 6971: 6967: 6966:asymmetric CG 6963: 6960: 6956: 6952: 6949: 6945: 6942: 6938: 6934: 6930: 6926: 6923: 6919: 6915: 6912: 6908: 6905: 6901: 6898: 6894: 6893:splittable CG 6890: 6887: 6883: 6882: 6881: 6873: 6871: 6867: 6860: 6840: 6834: 6831: 6828: 6825: 6821: 6812: 6808: 6790: 6784: 6781: 6776: 6770: 6765: 6762: 6751: 6750: 6749: 6746: 6740: 6737: 6736: 6735: 6732: 6730: 6726: 6721: 6719: 6718:best-response 6716: 6712: 6708: 6704: 6694: 6688: 6685: 6681: 6677: 6674: 6673: 6672: 6669: 6663: 6659: 6656: 6652: 6648: 6645: 6644:min-cost flow 6640: 6639: 6638: 6636: 6635:Papadimitriou 6620: 6611: 6609: 6605: 6594: 6591: 6588: 6584: 6580: 6579: 6577: 6573: 6570: 6569:leximin order 6566: 6562: 6544: 6540: 6536: 6531: 6528: 6525: 6521: 6512: 6494: 6490: 6486: 6481: 6478: 6475: 6471: 6448: 6445: 6442: 6438: 6429: 6428: 6427: 6425: 6421: 6412: 6408: 6404: 6386: 6383: 6380: 6376: 6350: 6346: 6339: 6336: 6331: 6328: 6325: 6321: 6317: 6309: 6305: 6296: 6293: 6290: 6286: 6277: 6274: 6271: 6268: 6264: 6260: 6242: 6239: 6236: 6232: 6206: 6202: 6195: 6192: 6187: 6184: 6181: 6177: 6173: 6165: 6161: 6152: 6149: 6146: 6142: 6133: 6130: 6127: 6126: 6125: 6117: 6115: 6111: 6107: 6103: 6098: 6094: 6089: 6087: 6083: 6079: 6075: 6070: 6048: 6044: 6041: 6038: 6026: 6018: 5994: 5990: 5987: 5984: 5962: 5959: 5958: 5957: 5940: 5937: 5934: 5922: 5919: 5916: 5904: 5901: 5898: 5886: 5883: 5880: 5868: 5865: 5862: 5850: 5847: 5844: 5832: 5829: 5826: 5797: 5789: 5786: 5783: 5779: 5775: 5769: 5761: 5758: 5755: 5751: 5747: 5741: 5733: 5730: 5727: 5723: 5719: 5713: 5705: 5702: 5699: 5695: 5691: 5685: 5677: 5674: 5671: 5667: 5663: 5657: 5649: 5646: 5643: 5639: 5631: 5614: 5606: 5603: 5600: 5596: 5592: 5586: 5578: 5575: 5572: 5568: 5564: 5558: 5550: 5547: 5544: 5540: 5536: 5530: 5522: 5519: 5516: 5512: 5508: 5502: 5494: 5491: 5488: 5484: 5480: 5474: 5466: 5463: 5460: 5456: 5448: 5447: 5446: 5444: 5440: 5435: 5433: 5429: 5410: 5407: 5402: 5398: 5389: 5386: 5383: 5379: 5375: 5367: 5363: 5354: 5351: 5348: 5344: 5320: 5317: 5312: 5308: 5299: 5296: 5293: 5289: 5268: 5243: 5239: 5230: 5227: 5224: 5220: 5199: 5176: 5170: 5165: 5161: 5151: 5149: 5148:crowding game 5141: 5138: 5134: 5133: 5132: 5130: 5120: 5100: 5096: 5087: 5084: 5081: 5077: 5069: 5065: 5061: 5058: 5054: 5032: 5010: 5006: 4983: 4980: 4977: 4973: 4964: 4960: 4950: 4945:Other results 4927: 4905: 4901: 4897: 4889: 4885: 4878: 4875: 4870: 4866: 4844: 4822: 4818: 4814: 4805: 4801: 4797: 4794: 4787: 4784: 4781: 4776: 4772: 4763: 4758: 4743: 4721: 4717: 4713: 4705: 4701: 4694: 4691: 4686: 4682: 4660: 4638: 4634: 4630: 4621: 4617: 4613: 4610: 4603: 4600: 4597: 4592: 4588: 4579: 4575: 4571: 4568: 4564: 4561: 4557: 4556: 4555: 4553: 4549: 4546:of functions 4545: 4535: 4533: 4528: 4526: 4522: 4514: 4510: 4506: 4502: 4499: 4495: 4491: 4487: 4486: 4485: 4483: 4475: 4471: 4467: 4463: 4460: 4456: 4452: 4451: 4450: 4448: 4443: 4436: 4432: 4428: 4424: 4420: 4417: 4413: 4409: 4405: 4401: 4397: 4396: 4395: 4374: 4370: 4361: 4351: 4347: 4319: 4315: 4311: 4306: 4302: 4292: 4288: 4283: 4271: 4268: 4265: 4262: 4261: 4260: 4258: 4248: 4232: 4228: 4220: 4216: 4212: 4209: 4206: 4203: 4199: 4195: 4190: 4186: 4163: 4159: 4150: 4132: 4129: 4126: 4122: 4114: 4110: 4106: 4103: 4100: 4097: 4093: 4089: 4084: 4080: 4071: 4053: 4050: 4047: 4043: 4034: 4031:and resource 4030: 4026: 4022: 4018: 4014: 4011: 4001: 3998: 3993: 3990: 3980: 3917: 3913: 3904: 3900: 3894: 3891: 3888: 3884: 3880: 3872: 3868: 3859: 3855: 3849: 3846: 3843: 3839: 3832: 3822: 3808: 3786: 3782: 3774:, with error 3756: 3752: 3743: 3739: 3735: 3732: 3711: 3708: 3702: 3694: 3690: 3684: 3681: 3676: 3672: 3666: 3662: 3620: 3600: 3597: 3592: 3588: 3567: 3547: 3525: 3521: 3517: 3514: 3488: 3484: 3475: 3471: 3465: 3462: 3459: 3455: 3451: 3443: 3439: 3430: 3426: 3420: 3417: 3414: 3410: 3388: 3366: 3362: 3358: 3355: 3335: 3293: 3289: 3259: 3237: 3219: 3215: 3192: 3188: 3158: 3143: 3140: 3133: 3125: 3121: 3113: 3109: 3103: 3099: 3093: 3090: 3087: 3083: 3079: 3053: 3043: 3039: 3035: 3032: 3021: 3005: 2983: 2979: 2956: 2952: 2920: 2916: 2910: 2907: 2904: 2900: 2896: 2891: 2887: 2878: 2874: 2858: 2855: 2852: 2844: 2826: 2822: 2818: 2813: 2809: 2801: 2797: 2793: 2790: 2786: 2764: 2744: 2722: 2718: 2695: 2691: 2687: 2684: 2676: 2673: 2655: 2651: 2642: 2625: 2621: 2612: 2608: 2605: 2587: 2583: 2562: 2554: 2539: 2519: 2511: 2508: 2492: 2484: 2483: 2482: 2462: 2454: 2450: 2446: 2442: 2432: 2424: 2422: 2417: 2401: 2397: 2347: 2313: 2290: 2287: 2282: 2278: 2269: 2265: 2242: 2238: 2234: 2229: 2225: 2221: 2218: 2193: 2189: 2180: 2176: 2153: 2149: 2145: 2140: 2136: 2132: 2129: 2107: 2103: 2080: 2076: 2055: 2046: 2026: 2022: 2013: 2009: 2003: 1999: 1993: 1990: 1987: 1983: 1973: 1953: 1945: 1941: 1933: 1929: 1923: 1920: 1917: 1913: 1907: 1904: 1901: 1897: 1893: 1881: 1880:best response 1877: 1873: 1869: 1844: 1822: 1818: 1795: 1791: 1782: 1769: 1743: 1739: 1735: 1732: 1729: 1724: 1720: 1716: 1711: 1707: 1695: 1691: 1670: 1666: 1657: 1653: 1645: 1641: 1637: 1634: 1630: 1608: 1586: 1582: 1573: 1570: 1552: 1548: 1522: 1518: 1509: 1505: 1484: 1476: 1475:cost function 1472: 1469:(also called 1443: 1438: 1434: 1426: 1410: 1407: 1404: 1396: 1376: 1372: 1368: 1365: 1362: 1359: 1350: 1345: 1341: 1332: 1311: 1307: 1303: 1300: 1297: 1292: 1288: 1284: 1279: 1275: 1251: 1248: 1245: 1237: 1232: 1231:singleton CGs 1228: 1212: 1204: 1201: 1198: 1194: 1193:symmetric CGs 1172: 1169: 1166: 1163: 1160: 1154: 1148: 1145: 1142: 1139: 1136: 1127: 1122: 1118: 1114: 1109: 1105: 1096: 1095: 1081: 1059: 1055: 1051: 1048: 1026: 1022: 1013: 998: 995: 992: 972: 964: 949: 930: 910: 891: 871: 852: 832: 813: 793: 785: 781: 765: 757: 756: 755: 742: 733: 730: 727: 726: 722: 719: 716: 715: 711: 708: 700: 699: 693: 679: 676: 656: 636: 617: 597: 578: 569: 567: 562: 552: 549: 546: 545: 541: 538: 535: 534: 530: 527: 519: 518: 512: 509: 506: 490: 486: 465: 445: 426: 406: 387: 366: 357: 343: 323: 303: 283: 263: 243: 223: 203: 183: 163: 143: 123: 103: 90: 78: 74: 71: 67: 64: 63: 62: 60: 56: 52: 48: 43: 41: 37: 33: 29: 25: 21: 9046: 8990:(1): 36–40. 8987: 8983: 8973: 8946: 8936: 8911: 8907: 8901: 8868: 8864: 8854: 8827: 8823: 8813: 8768: 8758: 8723: 8713: 8686: 8676: 8649: 8603: 8599: 8551: 8541: 8506: 8502: 8446: 8442: 8432: 8407: 8403: 8363: 8323: 8319: 8281: 8277: 8267: 8234: 8228: 8182: 8178: 8130: 8126: 8116: 8089: 8085: 8075: 8048: 8038: 8013: 8007: 7997: 7967:(1): 46–70. 7964: 7960: 7950: 7917: 7913: 7875: 7871: 7833: 7827: 7817: 7792: 7788: 7778: 7753: 7747: 7737: 7720:10419/259308 7702: 7698: 7688: 7645: 7641: 7597: 7587: 7552: 7542: 7517: 7513: 7503: 7470: 7466: 7428: 7424: 7378: 7374: 7364: 7331: 7327: 7317: 7284: 7280: 7270: 7245: 7241: 7231: 7209:(1): 65–76. 7206: 7202: 7192: 7151: 7147: 7109: 7105: 7059: 7055: 7026:sticklebacks 7021: 7015: 6997: 6991: 6983: 6970:symmetric CG 6969: 6965: 6958: 6954: 6950: 6947: 6941:nonseparable 6940: 6936: 6932: 6928: 6921: 6917: 6913: 6910: 6906: 6903: 6897:nonatomic CG 6896: 6892: 6888: 6885: 6879: 6869: 6866:approximated 6865: 6863: 6858: 6810: 6747: 6744: 6733: 6728: 6724: 6722: 6710: 6706: 6700: 6691: 6686: 6683: 6679: 6670: 6667: 6651:PLS-complete 6631: 6617: 6607: 6603: 6601: 6596:PNE is open. 6586: 6582: 6564: 6560: 6510: 6416: 6410: 6406: 6402: 6275: 6272: 6266: 6262: 6258: 6131: 6128: 6123: 6109: 6105: 6101: 6096: 6095:players and 6092: 6090: 6073: 6071: 5966: 5815: 5438: 5436: 5431: 5427: 5152: 5147: 5145: 5137:singleton CG 5136: 5128: 5126: 4962: 4958: 4956: 4948: 4764:of the form 4580:of the form 4551: 4547: 4543: 4541: 4531: 4529: 4518: 4512: 4508: 4504: 4493: 4489: 4481: 4479: 4465: 4458: 4454: 4446: 4444: 4440: 4434: 4426: 4422: 4407: 4403: 4399: 4290: 4287:G guarantees 4286: 4284: 4280: 4256: 4254: 4148: 4069: 4032: 4028: 4024: 4012: 4009: 4007: 3994: 3988: 3986: 3823: 3260: 3159: 2943: 2876: 2872: 2610: 2603: 2552: 2506: 2455:players, as 2452: 2448: 2444: 2440: 2438: 2430: 2420: 2418: 2348: 2047: 1971: 1875: 1865: 1783:, replacing 1762: 1693: 1474: 1470: 1424: 1330: 1230: 1226: 1199: 1196: 1192: 783: 779: 753: 745:Basic result 739: 696:Cost Matrix 570: 565: 558: 515:Cost Matrix 510: 507: 358: 95: 75:What is the 54: 44: 34:markets and 19: 18: 9042:Tardos, Éva 9034:Nisan, Noam 8524:10419/96071 7663:10419/95995 7381:: 317–342. 6959:general CG) 4961:and player 4412:in parallel 3997:Raphael Rom 3401:. That is, 2879:, that is, 1423:there is a 1227:network CGs 758:A base set 40:externality 24:game theory 8914:(4): 433. 8133:: 2.7–es. 7920:: 2.7–es. 7038:References 7016:Coalitions 6955:network CG 6904:unweighted 6405:to player 6261:to player 6086:strong PNE 4548:guarantees 4532:splittable 4521:strong PNE 4482:uniqueness 4447:efficiency 4021:motorcycle 2672:continuous 2445:continuous 2427:Extensions 1197:asymmetric 734:(3.6,3.6) 723:(1.8,2.8) 8928:120639586 8885:2167-8375 8846:0304-3975 8778:1104.2690 8628:123623707 8620:1573-7187 8533:0899-8256 8463:0014-3820 8443:Evolution 8424:1572-9451 8340:0899-8256 8298:0022-0531 8251:0364-765X 8199:1432-1270 8147:1084-6654 8108:0304-3975 8030:0364-765X 7981:1433-0490 7934:1084-6654 7892:0304-3975 7850:0364-765X 7809:0899-8256 7770:0364-765X 7729:0899-8256 7680:253723798 7672:1432-1270 7534:1572-9451 7495:253713700 7487:1432-1270 7445:0899-8256 7395:0022-0531 7348:1558-2566 7301:0899-8256 7262:0899-8256 7223:0899-8256 7168:0003-0147 7126:0899-8256 7084:121904640 7062:: 65–67, 6948:singleton 6937:separable 6929:identical 6791:ϵ 6604:singleton 6193:⋅ 5929:→ 5911:→ 5893:→ 5875:→ 5857:→ 5839:→ 5443:potential 5376:≤ 5192:, player 5062:∈ 5055:∑ 5025:, player 4876:⋅ 4845:ϕ 4798:⋅ 4795:ϕ 4788:⁡ 4782:⋅ 4692:⋅ 4661:ϕ 4614:⋅ 4611:ϕ 4604:⁡ 4598:⋅ 4498:in series 4449:of PNE: 4431:in series 4416:in series 4362:≥ 4213:∈ 4200:∑ 4107:∈ 4094:∑ 3967:Φ 3947:Φ 3892:∈ 3885:∑ 3881:− 3847:∈ 3840:∑ 3833:δ 3783:δ 3736:⋅ 3733:δ 3685:δ 3663:∫ 3641:Φ 3621:δ 3598:∈ 3515:δ 3463:∈ 3456:∑ 3418:∈ 3411:∑ 3359:∈ 3316:Φ 3269:Φ 3246:Φ 3168:Φ 3100:∫ 3091:∈ 3084:∑ 3077:Φ 2908:∋ 2901:∑ 2856:∈ 2794:∈ 2787:∑ 2688:∈ 2469:∞ 2466:→ 2441:nonatomic 2377:Φ 2357:Φ 2334:Φ 2235:− 2222:∈ 2146:− 2133:∈ 1991:∈ 1984:∑ 1914:∑ 1905:∈ 1898:∑ 1891:Φ 1733:… 1638:∈ 1631:∑ 1601:, player 1452:⟶ 1408:∈ 1369:∈ 1354:# 1301:… 1249:∈ 1052:∈ 965:A set of 780:resources 731:(2.8,1.8) 720:(2.6,2.6) 566:efficient 559:The pure 32:oligopoly 9072:Category 9044:(2007). 8805:14879292 8479:28567976 8155:17903962 7942:17903962 7579:17850062 7309:10778635 7184:55004212 6977:See also 6911:weighted 6727:and log 6368:, where 6224:, where 5441:admit a 5426:for all 4920:, where 4837:, where 4736:, where 4653:, where 4503:A graph 4488:A graph 4464:A graph 4453:A graph 4421:A graph 4398:A graph 4334:implies 4010:weighted 2998:of size 2674:as well. 2485:We keep 750:Notation 296:, where 8893:5581666 8750:1037326 8578:1037326 8471:2409448 8259:3690472 7356:1184436 7176:2463089 7076:0319584 6608:network 3653:is now 1540:. Each 784:factors 84:Example 9057: 8961: 8926: 8891: 8883: 8844: 8803: 8793: 8748: 8738: 8701: 8664: 8626: 8618: 8576: 8566: 8531: 8477: 8469: 8461: 8422: 8378: 8338: 8296: 8257: 8249: 8207:125221 8205: 8197: 8153: 8145: 8106: 8063: 8028: 7989:912932 7987: 7979: 7940: 7932: 7890: 7848: 7807: 7768: 7727: 7678: 7670: 7612: 7577: 7567: 7532: 7493: 7485: 7443: 7393: 7354: 7346: 7307: 7299: 7260: 7221: 7182: 7174: 7166: 7124: 7082: 7074: 6935:(with 6916:(with 6886:atomic 6715:greedy 6422:, and 6265:, and 4178:, and 2871:, the 2710:, let 2507:finite 1329:, the 553:(6,6) 542:(2,3) 336:(i.e. 9051:(PDF) 8924:S2CID 8889:S2CID 8801:S2CID 8773:arXiv 8746:S2CID 8624:S2CID 8574:S2CID 8467:JSTOR 8255:JSTOR 8203:S2CID 8151:S2CID 7985:S2CID 7938:S2CID 7676:S2CID 7575:S2CID 7491:S2CID 7352:S2CID 7305:S2CID 7180:S2CID 7172:JSTOR 7080:S2CID 6587:eight 6583:three 6112:be a 4527:PNE. 4507:does 4017:truck 4008:In a 3987:In a 2553:types 2443:(aka 2326:, so 649:when 550:(3,2) 539:(5,5) 458:when 53:(aka 9055:ISBN 8959:ISBN 8881:ISSN 8842:ISSN 8791:ISBN 8736:ISBN 8699:ISBN 8662:ISBN 8616:ISSN 8564:ISBN 8529:ISSN 8475:PMID 8459:ISSN 8420:ISSN 8376:ISBN 8336:ISSN 8294:ISSN 8247:ISSN 8195:ISSN 8143:ISSN 8104:ISSN 8061:ISBN 8026:ISSN 7977:ISSN 7930:ISSN 7888:ISSN 7846:ISSN 7805:ISSN 7766:ISSN 7725:ISSN 7668:ISSN 7610:ISBN 7565:ISBN 7530:ISSN 7483:ISSN 7441:ISSN 7391:ISSN 7344:ISSN 7297:ISSN 7258:ISSN 7219:ISSN 7164:ISSN 7122:ISSN 6409:and 5776:< 5748:< 5720:< 5692:< 5664:< 5593:< 5565:< 5537:< 5509:< 5481:< 4312:< 3518:< 3452:< 2873:load 2604:rate 1331:load 923:and 728:OBT 717:OAT 712:OBT 610:and 547:OBT 536:OAT 531:OBT 419:and 236:and 8992:doi 8951:doi 8916:doi 8873:doi 8832:doi 8783:doi 8728:doi 8691:doi 8654:doi 8608:doi 8556:doi 8519:hdl 8511:doi 8451:doi 8412:doi 8368:doi 8328:doi 8286:doi 8239:doi 8187:doi 8135:doi 8094:doi 8090:410 8053:doi 8018:doi 7969:doi 7922:doi 7880:doi 7876:348 7838:doi 7797:doi 7758:doi 7715:hdl 7707:doi 7658:hdl 7650:doi 7602:doi 7557:doi 7522:doi 7475:doi 7433:doi 7383:doi 7379:156 7336:doi 7289:doi 7250:doi 7211:doi 7156:doi 7152:147 7114:doi 7064:doi 6939:or 6931:or 6920:or 6909:or 6895:or 6662:PLS 5439:not 5139:s); 4785:exp 4601:exp 4509:not 4072:is 3022:of 2095:to 1972:not 1870:in 1497:is 1473:or 1200:CGs 782:or 709:OAT 677:0.8 528:OAT 9074:: 9040:; 9036:; 9032:; 8988:51 8986:. 8982:. 8957:. 8922:. 8910:. 8887:. 8879:. 8867:. 8863:. 8840:. 8828:10 8826:. 8822:. 8799:. 8789:. 8781:. 8767:. 8744:. 8734:. 8722:. 8697:. 8660:. 8636:^ 8622:. 8614:. 8604:42 8602:. 8598:. 8586:^ 8572:. 8562:. 8550:. 8527:. 8517:. 8507:67 8505:. 8501:. 8487:^ 8473:. 8465:. 8457:. 8447:44 8445:. 8441:. 8418:. 8408:17 8406:. 8402:. 8390:^ 8374:. 8348:^ 8334:. 8324:21 8322:. 8318:. 8306:^ 8292:. 8282:72 8280:. 8276:. 8253:. 8245:. 8235:25 8233:. 8227:. 8215:^ 8201:. 8193:. 8183:27 8181:. 8177:. 8163:^ 8149:. 8141:. 8131:11 8129:. 8125:. 8102:. 8084:. 8059:. 8024:. 8014:37 8012:. 8006:. 7983:. 7975:. 7965:49 7963:. 7959:. 7936:. 7928:. 7918:11 7916:. 7912:. 7900:^ 7886:. 7870:. 7858:^ 7844:. 7834:32 7832:. 7826:. 7803:. 7793:21 7791:. 7787:. 7764:. 7754:30 7752:. 7746:. 7723:. 7713:. 7703:57 7701:. 7697:. 7674:. 7666:. 7656:. 7646:44 7644:. 7640:. 7624:^ 7608:. 7573:. 7563:. 7551:. 7528:. 7518:17 7516:. 7512:. 7489:. 7481:. 7471:42 7469:. 7465:. 7453:^ 7439:. 7429:13 7427:. 7423:. 7403:^ 7389:. 7373:. 7350:. 7342:. 7330:. 7326:. 7303:. 7295:. 7285:47 7283:. 7279:. 7256:. 7246:28 7244:. 7240:. 7217:. 7207:16 7205:. 7201:. 7178:. 7170:. 7162:. 7150:. 7146:. 7134:^ 7120:. 7110:14 7108:. 7104:. 7092:^ 7078:, 7072:MR 7070:, 7058:, 7046:^ 6972:). 6951:CG 6924:); 6914:CG 6907:CG 6891:, 6889:CG 6407:i, 6278:: 6134:: 5434:. 5119:. 4247:. 4013:CG 3821:. 3238:, 2505:a 2449:CG 2447:) 2439:A 1692:A 1094:. 962:). 884:, 845:, 705:p1 702:p2 524:p1 521:p2 505:. 30:, 9063:. 8998:. 8994:: 8967:. 8953:: 8930:. 8918:: 8912:1 8895:. 8875:: 8869:3 8848:. 8834:: 8807:. 8785:: 8775:: 8752:. 8730:: 8707:. 8693:: 8670:. 8656:: 8630:. 8610:: 8580:. 8558:: 8535:. 8521:: 8513:: 8481:. 8453:: 8426:. 8414:: 8384:. 8370:: 8342:. 8330:: 8300:. 8288:: 8261:. 8241:: 8209:. 8189:: 8157:. 8137:: 8110:. 8096:: 8069:. 8055:: 8032:. 8020:: 7991:. 7971:: 7944:. 7924:: 7894:. 7882:: 7852:. 7840:: 7811:. 7799:: 7772:. 7760:: 7731:. 7717:: 7709:: 7682:. 7660:: 7652:: 7618:. 7604:: 7581:. 7559:: 7536:. 7524:: 7497:. 7477:: 7447:. 7435:: 7397:. 7385:: 7358:. 7338:: 7332:1 7311:. 7291:: 7264:. 7252:: 7225:. 7213:: 7186:. 7158:: 7128:. 7116:: 7087:. 7066:: 7060:2 7033:. 7012:. 6988:. 6961:. 6899:; 6870:d 6859:. 6844:) 6841:d 6838:( 6835:o 6832:+ 6829:d 6826:2 6822:d 6811:d 6794:) 6788:( 6785:O 6782:+ 6777:2 6771:5 6766:+ 6763:3 6729:W 6725:n 6711:W 6707:n 6687:. 6684:d 6680:d 6657:. 6571:. 6565:n 6561:e 6545:i 6541:a 6537:= 6532:e 6529:, 6526:i 6522:a 6511:i 6495:e 6491:a 6487:= 6482:e 6479:, 6476:i 6472:a 6449:e 6446:, 6443:i 6439:a 6411:d 6403:e 6387:e 6384:, 6381:i 6377:a 6356:) 6351:e 6347:x 6343:( 6340:d 6337:+ 6332:e 6329:, 6326:i 6322:a 6318:= 6315:) 6310:e 6306:x 6302:( 6297:e 6294:, 6291:i 6287:d 6267:d 6263:i 6259:e 6243:e 6240:, 6237:i 6233:a 6212:) 6207:e 6203:x 6199:( 6196:d 6188:e 6185:, 6182:i 6178:a 6174:= 6171:) 6166:e 6162:x 6158:( 6153:e 6150:, 6147:i 6143:d 6110:G 6106:m 6102:m 6097:n 6093:n 6054:) 6049:2 6045:1 6042:+ 6039:n 6033:( 6027:r 6000:) 5995:2 5991:1 5988:+ 5985:n 5979:( 5944:) 5941:y 5938:, 5935:z 5932:( 5926:) 5923:x 5920:, 5917:z 5914:( 5908:) 5905:x 5902:, 5899:x 5896:( 5890:) 5887:z 5884:, 5881:x 5878:( 5872:) 5869:z 5866:, 5863:y 5860:( 5854:) 5851:y 5848:, 5845:y 5842:( 5836:) 5833:y 5830:, 5827:z 5824:( 5801:) 5798:2 5795:( 5790:y 5787:, 5784:B 5780:d 5773:) 5770:2 5767:( 5762:z 5759:, 5756:B 5752:d 5745:) 5742:0 5739:( 5734:z 5731:, 5728:B 5724:d 5717:) 5714:2 5711:( 5706:x 5703:, 5700:B 5696:d 5689:) 5686:0 5683:( 5678:x 5675:, 5672:B 5668:d 5661:) 5658:1 5655:( 5650:y 5647:, 5644:B 5640:d 5618:) 5615:2 5612:( 5607:x 5604:, 5601:A 5597:d 5590:) 5587:2 5584:( 5579:z 5576:, 5573:A 5569:d 5562:) 5559:0 5556:( 5551:z 5548:, 5545:A 5541:d 5534:) 5531:2 5528:( 5523:y 5520:, 5517:A 5513:d 5506:) 5503:0 5500:( 5495:y 5492:, 5489:A 5485:d 5478:) 5475:1 5472:( 5467:x 5464:, 5461:A 5457:d 5432:f 5430:, 5428:e 5414:) 5411:1 5408:+ 5403:f 5399:x 5395:( 5390:f 5387:, 5384:i 5380:d 5373:) 5368:e 5364:x 5360:( 5355:e 5352:, 5349:i 5345:d 5324:) 5321:1 5318:+ 5313:f 5309:x 5305:( 5300:f 5297:, 5294:i 5290:d 5269:f 5249:) 5244:e 5240:x 5236:( 5231:e 5228:, 5225:i 5221:d 5200:i 5180:} 5177:e 5174:{ 5171:= 5166:i 5162:P 5106:) 5101:e 5097:x 5093:( 5088:e 5085:, 5082:i 5078:d 5070:i 5066:P 5059:e 5033:i 5011:i 5007:P 4984:e 4981:, 4978:i 4974:d 4963:i 4959:e 4928:f 4906:e 4902:b 4898:+ 4895:) 4890:e 4886:x 4882:( 4879:f 4871:e 4867:a 4823:e 4819:b 4815:+ 4811:) 4806:e 4802:x 4792:( 4777:e 4773:a 4744:f 4722:e 4718:b 4714:+ 4711:) 4706:e 4702:x 4698:( 4695:f 4687:e 4683:a 4639:e 4635:b 4631:+ 4627:) 4622:e 4618:x 4608:( 4593:e 4589:a 4552:C 4544:C 4513:G 4505:G 4494:G 4490:G 4476:. 4466:G 4461:. 4459:G 4455:G 4437:. 4435:G 4427:G 4423:G 4404:G 4400:G 4381:| 4375:j 4371:S 4366:| 4358:| 4352:i 4348:S 4343:| 4320:j 4316:w 4307:i 4303:w 4291:G 4233:i 4229:w 4221:i 4217:P 4210:e 4207:: 4204:i 4196:= 4191:e 4187:x 4164:i 4160:w 4133:e 4130:, 4127:i 4123:w 4115:i 4111:P 4104:e 4101:: 4098:i 4090:= 4085:e 4081:x 4070:e 4054:e 4051:, 4048:i 4044:w 4033:e 4029:i 3926:) 3923:) 3918:e 3914:x 3910:( 3905:e 3901:d 3895:P 3889:e 3878:) 3873:e 3869:x 3865:( 3860:e 3856:d 3850:Q 3844:e 3836:( 3809:P 3787:2 3762:) 3757:e 3753:x 3749:( 3744:e 3740:d 3712:z 3709:d 3706:) 3703:z 3700:( 3695:e 3691:d 3682:+ 3677:e 3673:x 3667:0 3601:Q 3593:e 3589:x 3568:Q 3548:P 3526:P 3522:f 3494:) 3489:e 3485:x 3481:( 3476:e 3472:d 3466:P 3460:e 3449:) 3444:e 3440:x 3436:( 3431:e 3427:d 3421:Q 3415:e 3389:P 3367:i 3363:S 3356:Q 3336:i 3294:P 3290:f 3220:e 3216:x 3193:e 3189:d 3144:z 3141:d 3137:) 3134:z 3131:( 3126:e 3122:d 3114:e 3110:x 3104:0 3094:E 3088:e 3080:= 3054:n 3050:] 3044:i 3040:r 3036:, 3033:0 3030:[ 3006:n 2984:i 2980:S 2957:P 2953:f 2935:. 2921:P 2917:f 2911:e 2905:P 2897:= 2892:e 2888:x 2877:e 2859:E 2853:e 2842:. 2827:i 2823:r 2819:= 2814:P 2810:f 2802:i 2798:S 2791:P 2765:P 2745:i 2723:P 2719:f 2696:i 2692:S 2685:P 2656:e 2652:d 2640:. 2626:i 2622:S 2611:i 2588:i 2584:r 2563:i 2540:n 2520:n 2493:E 2463:n 2453:n 2402:e 2398:d 2314:i 2294:) 2291:1 2288:+ 2283:e 2279:x 2275:( 2270:e 2266:d 2243:i 2239:P 2230:i 2226:Q 2219:e 2199:) 2194:e 2190:x 2186:( 2181:e 2177:d 2154:i 2150:Q 2141:i 2137:P 2130:e 2108:i 2104:Q 2081:i 2077:P 2056:i 2032:) 2027:e 2023:x 2019:( 2014:e 2010:d 2004:e 2000:x 1994:E 1988:e 1957:) 1954:k 1951:( 1946:e 1942:d 1934:e 1930:x 1924:1 1921:= 1918:k 1908:E 1902:e 1894:= 1857:. 1845:i 1823:i 1819:Q 1796:i 1792:P 1770:i 1749:) 1744:n 1740:P 1736:, 1730:, 1725:2 1721:P 1717:, 1712:1 1708:P 1704:( 1676:) 1671:e 1667:x 1663:( 1658:e 1654:d 1646:i 1642:P 1635:e 1609:i 1587:i 1583:P 1571:. 1553:e 1549:d 1528:) 1523:e 1519:x 1515:( 1510:e 1506:d 1485:e 1456:R 1448:N 1444:: 1439:e 1435:d 1411:E 1405:e 1394:. 1382:} 1377:i 1373:P 1366:e 1363:: 1360:i 1357:{ 1351:= 1346:e 1342:x 1317:) 1312:n 1308:P 1304:, 1298:, 1293:2 1289:P 1285:, 1280:1 1276:P 1272:( 1252:E 1246:e 1233:. 1213:E 1202:. 1179:} 1176:} 1173:T 1170:B 1167:, 1164:B 1161:O 1158:{ 1155:, 1152:} 1149:T 1146:A 1143:, 1140:A 1137:O 1134:{ 1131:{ 1128:= 1123:2 1119:S 1115:= 1110:1 1106:S 1082:E 1060:i 1056:S 1049:P 1027:i 1023:S 1011:. 999:2 996:= 993:n 973:n 950:T 931:B 911:B 892:O 872:T 853:A 833:A 814:O 794:E 766:E 680:x 657:x 637:T 618:B 598:T 579:A 491:2 487:x 466:x 446:T 427:B 407:T 388:A 367:T 344:A 324:B 304:A 284:T 276:- 264:B 256:- 244:O 224:T 216:- 204:A 196:- 184:O 164:T 144:O 124:T 104:O 72:?

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index