The path player game: A network game from the point of view of the network providers

Mathematical Methods of Operations Research manuscript No. (will be inserted by the editor) The Path Player Game A network game from the point of view of the network providers Justo Puerto1, Anita Sch¨obel2, Silvia Schwarze2 1University of Sevilla, Faculty of Mathematics, C/ Tarfia, s/n, 41012 Sevilla, Spain 2Inst. f. Num. and App. Mathematics, University of G¨ottingen, Lotzestr. 16–18, 37083 G¨ottingen, Germany, e-mail: [email protected] Received: date / Revised version: date Abstract We introduce the path player game, a noncooperative network game with a continuum of mutually dependent set of strategies. This game models network flows from the point of view of competing network operators. The players are represented by paths in the network. They have to decide how much flow shall be routed along their paths. The competitive nature of the game is due to the following two aspects: First, a capacity bound on the overall network flow links the decisions of the players. Second, edges may be shared by several players which might have conflicting goals. In this paper, we prove the existence of feasible and pure-strategy equilibria in path player games, which is a non-trivial task due to non-continuity of payoff functions and the infinite, mutually dependent strategy sets. We analyze different instances of path player games in more detail and present characterizations of equilibria for these cases. Key words Network games – Equilibria – Path player games 1 Introduction Various types of games on networks have been studied in recent years. For instance in routing games [24,5] flow has to be transported from origin to destination nodes. In load balancing games [20,6] load is to be assigned to resources. In facility location games and service provider games [29,7], facilities have to be located and assigned to the demand points. Network design games [9,2] and coordination games [14,17,4] describe the generation of networks. In [13,15], properties of social networks are studied. 2 Justo Puerto et al. In this work we study a new type of routing game. Usually, in routing games the problem of sending flow in a network is considered from the point of view of the flow itself, assuming that the flow can choose a path from origin to destination. An aspect, which has not been considered yet, is the behavior of the path owners, when they are allowed to choose the amount of flow that will be sent along their paths. This new approach models systems where paths are owned by decision makers, like in public transportation, energy or information networks. The decision makers offer a certain bandwidth to be used by the flow, like a bandwidth of electricity, or a certain daily frequency of trains. Equilibria in this model describe a stable market situation among competing path owners. A rough description of path player games is given as follows: Consider a network Gand a set of players P, one for each path P∈ P where the flow is defined as f:P → R|P| +. Each player’s strategy is to choose a nonnegative flow fP. An upper bound on the flow is given by the flow rate r, which shall not be exceed by the overall flow in the network. The flow rate is motivated by the limited capacity of the network resources and may arise from society regulations like a limitation of traffic for ecological or security reasons. Furthermore, each single player has a lower bound, the security limit ωP. This aspect is important, e.g. in transport optimization. The violation of both types of bounds is penalized. More detailed, the benefit is given by three parts: First of all, a cost functions ce(x) is assigned to each edge e. It is dependent on the flow x sent along the edge. If the bounds rand ωPare satisfied, the income of a player is given by the sum of costs over the edges that belong to his path. If one of the bounds is violated, a constant (negative) benefit is payed. Hence, the resulting benefit function is in general not continuous. Note that the benefit needs also not be strictly increasing. So a player is not necessarily interested in routing as much flow as possible. Handling too much flow could mean increasing operating costs, for instance due to over-hours or additional maintenance. The competitive aspect of the game is given by the flow rate that has to be satisfied by the overall network flow, and by the fact that the paths may own edges shared with other paths. Hence, the flow on an edge depends on the flow on all paths using the edge. The players sharing an edge may have different objectives regarding that edge, which leads up to competitive situations. Violation of the flow rate rneeds to be avoided in any case, since it leads to infeasible solutions. This is done by introducing a high penalty. Another way is to forbid infeasible solutions. This approach results in a game in which the strategy sets of the players are mutually dependent. Such games are called generalized Nash equilibrium (GNE) games, see [16,10]. An often studied question in GNE games is the existence of equilibria. Path player games are special instances of GNE games, see [22]. Their structure allows to prove the existence of equilibria. Note that both approaches, the approach The Path Player Game 3 of this paper using fixed strategy sets with a penalty, and the GNE path player game with dependent strategy sets are worthwhile to consider. Application The following application of path player games is under consideration in the framework of the European project ARRIVAL [1]: To create a public transportation network, like a railway or bus network, lines have to be installed. In particular, the lines are given by their stops, for instance a railway line may go from Hamburg to Basel with intermediate stops in between. Assigned to each line is its frequency, i.e. how often the line travels within a given time horizon, for instance twice a day. The line plan has to satisfy the customers’ demand and has to respect upper bounds to limit the frequencies on the edges. These bounds are usually given for security reasons, e.g. only one train is allowed to be on a block1at any time. Summarizing, the question of line planning is: Which lines and what frequencies shall be installed such that demand and security constraints are satisfied? This problem can be modeled as a type of path player game, called line planning game, in which the potential lines are the players choosing their frequencies as strategies. In contrast to cost- or customer-oriented objectives, see [25], the goal of the line planning game is to minimize the average delay of each line, and hence to obtain a line plan which is robust against delays, see [26] for first results and numerical studies using data from interregional trains in Germany. Related games The following three types of network games are related to path player games. We have already mentioned routing games, where the network flow is analyzed from the point of view of the flow. A routing game is played on a congested network, and the flow is assumed to consist of a finite or infinite number of players, acting independently and selfishly. Each of them chooses a path from the source to the destination that minimizes the cost of traveling along that path. This model can be seen as a counterpart to the path player game, as it represents the point of view of the travelers, while in the path player game the situation is analyzed from the path owners’ point of view. The path player game is also related to bandwidth allocation games, as described in [19,18]. In bandwidth allocation games capacitated links are used by several players, sending bids to a central manager. The manager answers with prices that are proportional to the bids and cares for satisfying the capacity constraints. Each user has its own utility function that determines his payoff depending on the price and the bid. Price taking users just accept the price given by the manager, while price anticipating users may adjust their bids. In the path player game, the bids correspond to the strategies. Contrary to bandwidth games, they are not answered by a manager, but directly accepted. However, in the path player game, all con- 1Between two stations, a track is separated into smaller units, namely into blocks. 4 Justo Puerto et al. tinuous and nonnegative cost functions are allowed, while in bandwidth allocation strictly increasing, continously differentiable and concave functions (so called elastic traffic) are required. Note that in bandwidth allocation the existence of equilibria can not be guaranteed, but in path player games we are able to prove the existence for continuous cost functions. Another model describing the behavior of path owners is that of path auctions, see e.g. [8,3]. Here each edge is owned by a player, and a central manager has the task to buy a shortest path from sto tfrom the edge owners. The edge owners know the price of their edge, but they are allowed to report a wrong price if they benefit from lying. The goal is to develop a payment mechanism such that every edge owner is interested to tell the truth. Such a mechanism is called truth telling. In a path player game in a network consisting of parallel edges from sto t, the path owners are edge owners as well, such that the path player game can be seen as a special case of path auction games. The paper is organized as follows. In Section 2 we introduce the game model. In Section 3 we show that feasible equilibria in pure strategies exist. Further properties of path player games are discussed in Section 4. These are used in Section 5 to give necessary and sufficient conditions for equilibria in the case of strictly increasing cost functions. The paper ends with some suggestions for future work. 2 The Model We consider a given network G= (V, E) with vertices v∈Vand edges e∈E. A path Pin Gis given by a sequence of edges e∈E:P= (e1, ...., ek). By Pwe denote the set of all paths Pin Gfrom the single source sto the single sink t, thus the set Pis given by the structure of the network G. Each of the paths P∈ P represents a player2in the path player game. Each player proposes an amount of flow fPthat he wants to be routed along his path. The complete flow is represented by a function f:P → R|P| +, while the flow on path Pis denoted by fP. For each edge e∈E, the flow fealong the edge can hence be determined by the sum of the flows on paths that contain e, i.e. fe=X P:e∈P fP. We assume that the demand is high enough to ensure that the players can implement the flow they proposed. Note that this is a considerable difference to bidding games, like bandwidth allocation or path auction games. Each edge eis associated with a cost function ce(·), that depends on the flow on e. The cost function represents the income of the edge owners and we 2In the course of this paper we will denote both, the path and the corresponding player with P, as both notations are handled equivalently. The Path Player Game 5 assume these functions to be continuous and nonnegative for nonnegative flows, i.e. ce(x)≥0 for x≥0. If the edge belongs to more than one owner, we assume that each player receives the same income. (It is possible to generalize this model by allowing the owners to share the fee in an arbitrary way.) To calculate the cost of a path P, we sum up the costs of the edges belonging to that path, i.e., cP(f) = X e∈P ce(fe). These costs are, however, not directly the benefit of player Psince there are two more issues to handle: –We require that the sum of flows in the network is bounded by a given flow rate r. It can be interpreted as a network capacity. We call a flow ffeasible for a flow rate rif PP∈P fP≤rholds. If the flow rate is exceeded, the flow is called infeasible and all players receive a penalty of M, with Mbeing a large number. –Furthermore, a security system for the players is implemented: If the flow of a player Plies below the so called security limit ωP≥0, he will receive a fixed security payment κP>−M. In this case, the path Pis called underloaded, while we call Ploaded, if fP> ωP. For positive κP, the security limit and payment serve as an insurance that guarantees a fixed income for each player. On the other hand, if κP<0, the security payment is a penalty for underloaded paths. This penalty may represent for instance additional costs for maintaining an unused resource. Summarizing, we obtain the benefit function in the path player game: Definition 1 The benefit function of player P∈ P in a path player game for f≥0|P| is given as: bP(f) =    cP(f)if PP∈P fP≤r∧fP≥ωP κPif PP∈P fP≤r∧fP< ωP −M if PP∈P fP> r , where cP(f) = Pe∈Pce(fe). Some remarks about path player games should be added. –There is a continuum of strategies as a player is allowed to choose any nonnegative real number. The benefit (or payoff) a player obtains after fixing a strategy depends on the strategies of all players. –The path player game is noncooperative and thus it is possible that the flow created by the decisions of the players is not feasible. For instance if the benefit is a nondecreasing function, each player will try to get as much flow as possible such that the sum of all proposed flows may exceed the flow rate. Unfortunately, it turns out that even equilibria may be infeasible. Nevertheless, we will prove in Theorem 1 that feasible equilibria do exist. 6 Justo Puerto et al. 3 Equilibria for General Benefit Functions In this section we analyze equilibria in path player games for general benefit functions while, later in Section 5, we derive additional results for strictly increasing cost functions. The definition of equilibria in path player games follows the definition of a Nash equilibrium (see e.g. [21]): A flow f∗is an equilibrium in a given path player game if and only if for all players P∈ P and for all fP≥0 it holds that bP(f∗ −P, f∗ P)≥bP(f∗ −P, fP).(1) We will call the equilibrium feasible if f∗is a feasible flow, infeasible otherwise. An equilibrium is a game situation where none of the players is able to obtain a better outcome by changing his strategy unilaterally. Such a situation characterizes a stable state of the system. In order to find equilibria in the path player game we have to look at the benefit of a single player who changes his own strategy, while the strategies of the competitors remain fixed. We define f−P∈R|P|−1 +by deleting the component belonging to path P, such that we can fix the strategies f−Pof the competitors and just consider the influence of fP. We obtain cP(f−P, fP) = X e∈P ce fP+X Pk∈P\{P}:e∈Pk fPk , with a constant term PPk∈P\{P}:e∈PkfPk. In the following, if we want to stress the fact that f−Pis fixed with respect to the cost or benefit function, we will denote cP(f) = cP(f−P, fP) or bP(f) = bP(f−P, fP), respectively. If ce(fe) are convex (concave) functions, then cP(f−P, fP) is also a convex (concave) function. Finally, we introduce the decision limit of player Pas dP(f−P) = r−X Pk∈P\{P} fPk. The set [0, dP(f−P)] is called the decision interval of player P. It contains all feasible strategies for P. From its definition we obtain the following corollary: If there is one player sending as much flow as possible (without violating the decision limit), then this is true for all players. Corollary 1 Any flow fsatisfies: If there is a player Pkwith fPk=dPk(f−Pk) then all players P∈ P satisfy fP=dP(f−P). Figure 1 shows an example of a benefit function bP(f−P, fP) for fixed f−P. The function depends only on the scalar fPand is characterized by three parts: The two constant regions generated by the security payment κP, the infeasibility penalty −M, and the middle part, created by the cost function cP(f−P, fP). As the players want to maximize their benefit, we define the best reaction set for a player Pwith respect to a given flow f−Pas fmax P(f−P) = {fP≥0 : fPmaximizes bP(f−P, fP)}. The Path Player Game 7 bP(f−P, fP) fP ωPdP fmax P κP −M Fig. 1 Benefit function bP(f−P, fP) for fixed f−P In this paper, we assume to have continuous cost functions. As a result, we obtain nonempty best reaction sets: Lemma 1 Consider a path player game with cost functions ce(fe)being continuous for all edges e∈E. Then, the sets fmax P(f−P)are nonempty for all P∈ P and for all f∈R|P| +. Lemma 1 can be proved by considering the three parts of bP(f−P, fP) and applying Weierstrass extreme value theorem. Example 1 fmax P(f−P) can be empty in the case of non-continuous cost functions, see Figure 2. fP dP ωP κP −M bP(f−P, fP) Fig. 2 Best reaction set fmax P(f−P) is empty Best reaction sets are useful for the following characterization of equilibria. A flow is an equilibrium if each player is choosing a best reaction strategy with respect to the strategies of his opponents: Corollary 2 In a path player game a flow f∗is an equilibrium if and only if for all P∈ P it is satisfied that f∗ P∈fmax P(f∗ −P). 8 Justo Puerto et al. For infinite games with continuous benefits it is known that there exists an equilibrium in mixed strategies if the strategy spaces are nonempty and compact. Even more, if we assume continuous and quasi-concave benefit functions, there exists a pure-strategy equilibrium (see e.g., [11] for both results). In our game, we may have non-continuous benefit functions. If we just consider feasible flows, we furthermore have to deal with dependent strategy sets. Therefore, it is not evident that in path player games equilibria always exist, and if yes, it is still not clear if there is a feasible equilibria among them. We will in the following prove even more: the existence of feasible equilibria in pure strategies. Theorem 1 (Existence of feasible equilibria) In a path player game with continuous cost functions ce(fe)for all edges e∈E, there is at least a feasible equilibrium in pure strategies ˆ fsuch that ˆ fP∈fmax P(ˆ f−P)∀P∈ P. Proof Consider the set of feasible flows F=(f:fP≥0∀P∈ P ∧ X P∈P fP≤r). The set Fis closed, bounded and convex. Furthermore consider the singlevalue function, T:F→R|P| defined as T(f) = f′whose components f′ P=t(fP) are given by f′ P=fP+   min fm P−fP,fm P−fP PPk∈P:fPk<fm Pk (fm Pk−fPk)·dif fP< fm P fm P−fPif fP≥fm P , (2) where fm P= min {fmax P(f−P)}is chosen as the smallest flow that is benefit maximizing3and d=r−PP∈P fPis the flow left that can be distributed among the players maintaining feasibility. Note that by definition of dPit holds for any feasible flow f∈Fand all P∈ P that d=dP(f−P) + X Pk∈P\{P} fPk−X P∈P fP=dP(f−P)−fP≥0. Note furthermore, that by Lemma 1 fm Pexists and that by definition of fmax P(f−P) it holds that 0≤fm P≤dP(f−P) = r−X Pk∈P\{P} fPk.(3) An interpretation of the function Tis given right after this proof. In the following we prove that Tis a continuous function of Finto itself. Then, by Brouwer’s fixed point theorem a fixed point f=T(f) exists in F. Finally, we will show that each fixed point in Fis representing an equilibrium in pure 3Note that for the proof it is not important which fP∈fmax Pis chosen for fm P as long as it is well-defined. The Path Player Game 9 strategies, so that we will be able to guarantee the existence of a feasible equilibrium in pure strategies. Part a) (T:F→F) First note that f′ P≥0∀P∈ P. Denote the sets P1={P∈ P :fP< fm P} and P2={P∈ P :fP≥fm P}. X P∈P f′ P=X P∈P1 fP+ min (fm P−fP,fm P−fP PPk∈P1(fm Pk−fPk)·d)! +X P∈P2 (fP+fm P−fP) =X P∈P fP+X P∈P1 min (fm P−fP,fm P−fP PPk∈P1(fm Pk−fPk)·d) + ≤0 z}| { X P∈P2 (fm P−fP) ≤X P∈P fP+X P∈P1 fm P−fP PPk∈P1(fm Pk−fPk)·d =X P∈P fP+d=X P∈P fP+r−X P∈P fP =r . Therefore, f′∈Fsince f′ P≥0∀P∈ P and PP∈P f′ P≤r. Part b) (T(f) is continuous) We distinguish the following exhaustive cases: i) fP> fm P: f′ P=fm P∀fP> fm P, i.e. t(fP) is continuous ii) fP=fm P+ 0: f′ P=fm Pfor fP=fm P+0, i.e. t(fP) is continuous to the right fP=fm P+0 iii) fP< fm P: Consider g(f) = fm P−fPand h(f) = fm P−fP PPk∈P1(fm Pk−fPk)·d. The functions g(f) and h(f) are continuous and so the minimum of both functions is continuous too. It follows that t(fP) with f′ P=fP+ min {g(f); h(f)}is continuous. iv) fP=fm P−0: Consider the following marginal value of the mapping that we take for each flow fwhere fP→fm P−0: lim f:fP→fm P−0      →fm P z}|{ fP+ min          →0 z}| { fm P−fP, ≥0 z}| { fm P−fP PPk∈P1(fm Pk−fPk)· ≥0 z}|{ d              =fm P. 16 Justo Puerto et al. Example 2 (5) ;NCS property. Consider a game on a network with two paths, as illustrated in Figure 6. A flow rate r= 1 has to be routed from sto t. On both paths the costs are cP(x) = x, and we set ω1=κ1= 1 and ω2=κ2= 0. In this game, a flow fwith PP∈P fP< r is not an equilibrium as fmax 2(f−2) = {d2(f−2)} for all f−2, i.e. player 2 would in any case use up the remaining flow rate. On the other hand, each flow fwith PP∈P fP=ris an equilibrium flow. If PP∈P fP=rholds, player 2 can not find any better strategy as he will always try to get as much flow as possible, while player 1 is also not able to improve his payoff as his benefit function is anyway constant over [0,1]. That means, this game fulfills condition (5). Nevertheless, the game has not NCS property. There is no f1≥ω1with b1(f1, f2)> κ1and so path 1 is destroying the NCS property of the game. st c2(x) = x;ω2= 0; κ2= 0 c1(x) = x;ω1= 1, κ1= 1 r= 1 Fig. 6 Game graph of Example 2 st ω2= 0 ω1= 2 r= 1 Fig. 7 Game graph of Example 3 Example 3 (5) ;non-triviality. Consider the game illustrated in Figure 7. The graph consists of two paths, and we choose ω1= 2 and ω2= 0. The remaining components of the game, as cost functions and security payments may be chosen arbitrarily, but it is important that the cost functions are strictly increasing. With a similar argument as in Example 2, it is possible to show that this game fulfills (5). Nevertheless, the game is trivial, as PP∈P ωP> r. If a game has strictly increasing cost functions and general security limit, but we can not ensure NCS property or the non-triviality of the game (and thus can not apply Theorem 2), we are still able to give a necessary condition for a profile of flows to be an equilibrium. Lemma 4 If a flow fin a path player game with strictly increasing cost functions ce(fe)on all edges e∈Eis a feasible equilibrium then at least one of the following two cases holds: (i)PP∈P fP=r, The Path Player Game 17 (ii)fP< ωP∀P∈ P . Proof Let fbe a feasible equilibrium such that (i) and (ii) are both not true. Since (i) does not hold, PP∈P fP< r. Then fP< dP(f−P)∀P∈ P. Since (ii) is also not true, ∃¯ Pwith f¯ P≥ω¯ P. Then b¯ P(f−¯ P, f′ ¯ P)> b¯ P(f−¯ P, f ¯ P)∀f′ ¯ P∈(f¯ P, d ¯ P(f−¯ P)], as according to Proposition 2, bP(f−P, fP) is strictly increasing over this domain. It follows that f¯ P/∈fmax ¯ P(f−¯ P). But this is a contradiction to fbeing an equilibrium. ⊓⊔ The following lemma provides a statement about the converse of Lemma 4. Lemma 5 Consider a path player game with strictly increasing cost functions ce(fe). Let fbe a flow with the following properties: (i)PP∈P fP=r, (ii)fP< ωP∀P∈ P . Then, f is a feasible equilibrium. For the proof it suffices to show that for all players P, increasing or decreasing fPwill not lead to an improvement of the benefit bP. The following examples demonstrate that only one of the two conditions (i) and (ii) is not sufficient to guarantee a feasible equilibrium. Example 4 ((i)∧ ¬(ii);fis feasible equilibrium) Consider a game consisting of two disjoint paths connecting sand t, i.e. P={1,2}. Set r= 1, ω1=ω2= 0.25 and the security payment κ1=κ2= 2. With cost functions cP(x) = xfor P= 1,2, the flow f= (0.5,0.5) fulfills (i) but not (ii). This flow with b1(f) = b2(f) = 0.5 is not an equilibrium as fmax 1(0.5) = fmax 2(0.5) = [0,0.25). Example 5 (¬(i)∧(ii);fis feasible equilibrium) Consider a game consisting of two disjoint paths, P={1,2}. Set r= 1, ω1=ω2= 0.5 and κ1=κ2= 0.1. With cost functions cP(x) = xfor P= 1,2, a flow f= (0.45,0.45) with b1(f) = b2(f) = 0.1 is no equilibrium as fmax 1(0.45) = fmax 2(0.45) = 0.55. We have seen that a feasible flow with property (ii) need not be an equilibrium. This does not change if we assume to have a trivial game or a game without NCS property. The following example illustrates the assertion. Example 6 Consider again a game consisting of two disjoint paths connecting sand t, i.e. P={1,2}. Set r= 5 and ωP= 3 for P= 1,2, i.e. the game is trivial. Furthermore, choose κP= 1 for P= 1,2 and c1(f1) = f1, c2(f2) = f2/10. This game does not satisfy NCS property as for all f1≥0 there is no f2∈[ω2, d2(f1)] such that b2(f1, f2)> κ2. Consider the feasible flow f= (0,0). The flow ffulfills (ii) and dP(f−P) = rfor all P. Nevertheless, since b1(d1(0),0) = 5 > b1(0,0) = κ1= 1 this flow is not an equilibrium. 18 Justo Puerto et al. We remark that in [28] further results for other types of cost functions have been derived. This includes a necessary condition for differentiable costs. It is also sufficient if the costs are differentiable and concave, and if the game has no security limit. Finally, for convex costs a dominating strategy set is determined. 6 Conclusion and Further Research In this paper, we presented results for equilibria in a new network game, the path player game. We proved the existence of feasible equilibria in pure strategies. Furthermore, we presented a necessary condition for equilibria if the cost functions are strictly increasing. If the game furthermore satisfies the NCS property, we obtained even a necessary and sufficient condition. Path player games have various aspects which are currently under research. In [23] the concept of path player games is extended to games on polyhedra allowing more general dependencies among strategy sets. Treating path player games as GNE games (instead of penalizing infeasible solutions) provides a simpler (continuous) payoff function. This is an advantage in the analysis of a potential function (see [22]), which turns out to exist for the path player game in both versions. Moreover, it turns out that path player games may have multiple equilibria. This motivates the analysis of nondominated solutions in the sense of Pareto, see [27] for some first results on the relation between equilibria and Pareto solutions. An extension for future research is to consider not paths but complete subgraphs as players. This reflects the fact that in real-world situations network providers usually own a subnetwork. Furthermore, some applications require integer solutions. Thus, the extension of the path player game to an integer version is of interest; for the line planning game it has already implemented in [28]. The results for the line planning game (see [26]) are promising and motivate further research in this field. Moreover, repeated or stochastic versions of the game could be considered to refine the set of equilibria. Finally, it is open work to analyze the situation as an optimization problem, that means to look for minimal cost flows in the network, and to compare them with the equilibria of the game. References 1. ARRIVAL: Algorithms for robust and online railway optimization: improving the validity and reliability of large scale systems. Funded by the “Future and Emerging Technologies” Unit of the EC within the 6th Framework Programme of the European Commission, http://arrival.cti.gr/. 2. E. Anshelevich, A. Dasgupta, J. Kleinberg, ´ E. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. In Proc. of FOCS04, pages 295–304. 2004. The Path Player Game 19 3. A. Archer and ´ E. Tardos. Frugal path mechanisms. In Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 991–999. ACM Press, 2002. 4. Y. Bramoull´e, D. L´opez-Pintado, S. Goyal, and F. Vega-Redondo. Network formation and anti-coordination games. International Journal of Game Theory, 33(1):1–19, 2004. 5. J.R. Correa, A.S. Schulz, and N.E. Stier Moses. Selfish routing in capacitated networks. Mathematics of Operations Research, 29(4):961–976, 2004. 6. A. Czumaj, P. Krysta, and B. V¨ocking. Selfish traffic allocation for server farms. In Proc. of STOC02, pages 287–296. 2002. 7. N. Devanur, N. Garg, R. Khandekar, V. Pandit, A. Saberi, and V.V. Vazirani. Price of anarchy, locality gap, and a network service provider game. In Proc. of WINE05, pages 1046–1055. 2005. 8. E. Elkind, A. Sahai, and K. Steiglitz. Frugality in path auctions. In Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 701– 709. ACM Press, 2004. 9. A. Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou, and S. Shenker. On a network creation game. In Proc. of the 22th annual symposium on Principles of distributed computing, pages 347–351. 2003. 10. F. Facchinei and J.-S. Pang. Exact penalty functions for generalized Nash problems. In G. Di Pillo and M. Roma, editors, Large-scale nonlinear optimization, pages 115–126. Springer, 2006. 11. D. Fudenberg and J. Tirole. Game Theory. MIT Press, Cambridge, 1991. 12. C.J. Goh and X.Q. Yang. Vector equilibrium problem and vector optimization. European Journal of Operational Research, 116:615–628, 1999. 13. D. G´omez, E. Gonz´alez-Arang¨uena, C. Manuel, G. Owen, M. del Pozo, and J. Tejada. Centrality and power in social networks: a game theoretic approach. Mathematical Social Sciences, 46:27–54, 2003. 14. S. Goyal and F. Vega-Redondo. Network formation and social coordination. Games and Economic Behavior, 50:178–207, 2005. 15. B. Grofman and G. Owen. A game theoretic approach to measuring degree of centrality in social networks. Social Networks, 4(3):213–224, 1982. 16. P.T. Harker. Generalized Nash games and quasi-variational inequalities. European Journal of Operational Research, 54:81–94, 1991. 17. M.O. Jackson. Allocation rules for network games. Games and Economic Behavior, 51:128–154, 2005. 18. R. Johari and J.N. Tsitsiklis. Efficiency loss in a network resource allocation game. Mathematics of Operations Research, 29(3):407–435, 2004. 19. F. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunications, 8:33–37, 1997. 20. D. Monderer and L.S. Shapley. Potential games. Games and Economic Behavior, 14:124–143, 1996. 21. G. Owen. Game Theory. Academic Press, San Diego, third edition, 1995. 22. J. Puerto, A. Sch¨obel, and S. Schwarze. A class of infinite potential games. Technical Report 2006-15, Institut f¨ur Numerische und Angewandte Mathematik, Universit¨at G¨ottingen, 2006. Preprint Reihe. 23. J. Puerto, A. Sch¨obel and S. Schwarze. Games on polyhedra. Working Paper. 24. T. Roughgarden. Selfish routing and the price of anarchy. MIT Press, Cambridge, 2005. 25. A. Sch¨obel. Customer-Oriented Optimization in Public Transportation. Springer, New York, 2006. 20 Justo Puerto et al. 26. A. Sch¨obel and S. Schwarze. A game-theoretic approach to line planning. In Proc. of ATMOS06, Sept. 2006, Zurich, http://drops.dagstuhl.de/opus/volltexte/2006/688. 27. A. Sch¨obel and S. Schwarze. Dominance and equilibria in the path player game. In Proc. of OR2005, pages 489–494. 2006. 28. S. Schwarze. Path Player Games: Analysis, Generalization and Application. PhD thesis, University of G¨ottingen. 29. A. Vetta. Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In Proc. of FOCS02, pages 416–425. 2002. View publication statsView publication stats