Nash equilibria in two-resource congestion games with player-specific payoff functions

Khanchouche, Fatima; Sbabou, Samir; Smaoui, Hatem; Ziad, Abderrahmane Article Nash equilibria in two-resource congestion games with player-specific payoff functions Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Khanchouche, Fatima; Sbabou, Samir; Smaoui, Hatem; Ziad, Abderrahmane (2024) : Nash equilibria in two-resource congestion games with player-specific payoff functions, Games, ISSN 2073-4336, MDPI, Basel, Vol. 15, Iss. 2, pp. 1-10, https://doi.org/10.3390/g15020007 This Version is available at: https://hdl.handle.net/10419/330076 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Citation: Khanchouche, F.; Sbabou, S.; Smaoui, H.; Ziad, A. Nash Equilibria in Two-Resource Congestion Games with Player-Specific Payoff Functions. Games 2024,15, 7. https://doi.org/ 10.3390/g15020007 Academic Editor: Ulrich Berger Received: 12 December 2023 Revised: 6 February 2024 Accepted: 18 February 2024 Published: 26 February 2024 Copyright: © 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). games Article Nash Equilibria in Two-Resource Congestion Games with Player-Specific Payoff Functions Fatima Khanchouche 1,*,†, Samir Sbabou 2,†, Hatem Smaoui 3,† and Abderrahmane Ziad 4,5,† 1Fundamental and Numerical Mathematics Laboratory, Department of Mathematics, Faculty of Sciences, Ferhat Abbas University of Setif 1, Setif 19137, Algeria 2Center of Research in Economics and Management, University of Caen, Esplanade de la Paix, 14000 Caen, France; samir[email protected] 3Center of Economics and Management of the Indian Ocean, University of Réunion, 15 Avenue René Cassin, BP 7115, 97715 Saint Denis, Cedex 9, France; [email protected] 4CREM—Centre de Recherche en Économie et Management, UNICAEN—Université de Caen Normandie, NU—Normandie Université, 14000 Caen, France; [email protected] 5Laboratoire de Mathématiques Appliquées (LaMA), Ferhat Abbas University of Setif 1, Setif 19137, Algeria *Correspondence: [email protected]; Tel.: +213-699573750 †These authors contributed equally to this work. Abstract: In this paper, we examine the class of congestion games with player-specific payoff functions introduced by Milchtaich, I. (1996). Focusing on the special case of two resources, we give a short and simple method for identifying all Nash equilibria in pure strategies. We also provide a computation algorithm based on our theoretical analysis. Keywords: game theory; Nash equilibria; congestion games; price of anarchy 1. Introduction Congestion games provide a rich theoretical framework for modeling and analyzing problems of sharing limited resources involving self-interested agents. This class of noncooperative games, originally introduced by Rosenthal [1] , has various applications, particularly in economics and computer science, such as network design and routing, facilities location, and load balancing (see, for example, Roughgarden [2] , Konur and Geunes [3] and Suri et al. [4] ). In Rosenthal’s model, each player’s strategy is to choose a subset of resources from a common set of available resources. The player’s utility, when selecting a particular combination of resources, is the sum of the payoffs derived from the use of each resource included in their choice. The payoff resulting from the use of a given resource depends only on the number of players sharing that resource. Rosenthal [1] demonstrated the existence, for each of these games, of an exact potential function; hence, they always admit at least one (pure) Nash equilibrium. Monderer and Shapley [5] later established that any potential game (i.e., admitting an exact potential function) is isomorphic to a congestion game (A Nash equilibrium is a strategy profile that is stable against unilateral deviations. An exact potential function is a real-valued function defined over the set of strategy profiles, such that the variation in the utility of any player who changes his strategy is equal to the corresponding variation of this function. When a potential function exists, Nash equilibria correspond to the maxima of this function). Since Rosenthal’s seminal paper, a considerable amount of literature has developed around the study of Nash equilibria in a multitude of classes and subclasses of congestion games resulting from expansions, restrictions, and variations on the original model. The most significant part of this extensive and highly active research is devoted to network congestion games (where the resources are the edges of a given undirected graph, and each strategy is a pathinthis graph)and weighted congestiongames(where different players mayhavedifferent effects on the congestion). For results on the existence (and complexity) of Nash equilibria in Games 2024,15, 7. https://doi.org/10.3390/g15020007 https://www.mdpi.com/journal/games Games 2024,15, 7 2 of 10 these games, which we do not address here, see Fabrikant et al. [6] , Fotakis et al. [7] , Fotakis et al. [8] , Holzman and Monderer [9] , Panagopoulou et al. [10] , Mavronicolas et al. [11] and Ackermann et al. [12] . In this paper, we focus on another class of congestion games, known as congestion games with player-specific payoff functions. Introduced independently by [ 13 , 14 ], this type of game generalizes the Rosenthal model in that it allows for the consideration of player heterogeneity, but also imposes two limiting conditions (this paper complements and updates our working paper (khanchouche et al. [15] )). Each player can choose only one resource at a time (no longer a subset of resources) and has their own payoff functions. These functions, no longer common to all players, are assumed to decrease with the number of players choosing the same resource. Milchtaich [14] proved that each game in this class admits at least one (pure) Nash equilibrium. In particular, he showed that, in the general case, best-replay paths can be cyclic but any arbitrary (initial) strategy profile can be connected to a Nash equilibrium via a bestreply path. Furthermore, when the payoff functions are the same for all players (symmetric case) or when there are only two resources, the game possesses the finite improvement property (FIP, all improvement paths are finite). (A best-reply (resp. an improvement) path is a sequence of strategy profiles in which each strategy profile differs from the preceding one in only one strategy and the unique deviator best-improves (resp. strictly-improves) her utility.) Note that the result concerning the symmetric case can be obtained as a simple consequence of Rosenthal’s theorem (it being a special case of the original model) and the fact that the existence of an exact potential function implies the FIP (Monderer and Shapley [5] ). In the symmetric case sometimes referred to as singleton congestion games, it is not only possible to compute a Nash equilibrium, or even an optimal Nash equilibrium, in polynomial time (Ieong et al. [16] , Ackermann et al. [17] ), but there also exists a method that enables the generation of all Nash equilibria in such a game (Sbabou et al. [18] ). In what follows, we aim to extend the result of Sbabou et al. [18] to the non-symmetric case. We will limit ourselves to situations where only two resources are available, as the general case is currently beyond the scope of this generalization. To the best of our knowledge, apart from the aforementioned paper, no study has focused on the characterization of the set of all Nash equilibria in a given congestion game. However, the exhaustive enumeration of equilibria (when possible) beyond its intrinsic theoretical interest can prove very useful when it comes, for example, to comparing these equilibria, classifying them, choosing the optimal equilibrium, or measuring the consequences of a non-optimal choice (price of anarchy, Koutsoupias and Papadimitriou [19]). Among all subclasses of congestion games studied in Milchtaich [14] , only symmetric games and non-symmetric games with two resources satisfy the FIP. We know that this property implies the existence of an ordinal potential function (Monderer and Shapley [5] ) and that Nash equilibria correspond to the maxima of this function. It is probably for this reason that the generation of all Nash equilibria is possible in these two particular cases and a priori difficult to obtain in the general case. However, unlike the generally used algorithms, the method we propose does not use the potential function (which is not known in our case) nor the convergence of best-replay paths (which does not generate all the equilibria). Our approach is based on moving from the framework of cardinal utilities to that of ordinal utilities. (Several studies consider games with ordinal utility functions (Cruz and Simaan [20] , Xu [21] , Durieu et al. [22] , Ouenniche et al. [23] ). In these games, known as ordinal games, it is generally assumed that players cannot evaluate the outcomes of the game in a numerical way. Note that we do not retain this assumption here and that we use the ordinal framework only to simplify our analysis.) This transition is purely technical and does not affect the set of Nash equilibria. The remainder of the paper is organized as follows. Section 2provides basic definitions and notations concerning congestion games. Section 3establishes our main results. Section 4provides an algorithm based on our theoretical analysis, which generates the complete list of Nash equilibria in the case of two resources. Section 5concludes the paper. Games 2024,15, 7 3 of 10 2. Basic Definitions and Notations We begin by defining congestion games with player-specific payoff functions as introduced by Milchtaich [14] . We then adopt an approach similar to Sbabou et al. [18] to describe these games within the framework of ordinal preferences. Acongestiongamewithplayer-specificpayofffunctions isatuple G= (N , R , (dr i)i∈N,r∈R) where N={ 1, .. . , n} is a set of n players, R={ 1, .. . , m} a set of m resources available to all players. For all i∈N and r∈R , dr i is a decreasing function on { 1, .. . , n} giving the payoff that player i receives for choosing resource r (this specific gain depends only on the number of players using this resource). A strategy profile is a n -tuple σ= (σ1 , .. . , σn) such that σi∈R , ∀i∈N . Thus, the strategy set for each player is R (a player’s strategy consists of any single resource in R ), and the set of strategy profiles is Rn=R×. .. ×R . For a strategy profile σ and a resource r , the congestion on resource r is defined by nr(σ) = |{i∈N:σi=r}| (i.e., the number of players using r ). The vector (n1(σ) , .. . , nm(σ)) is the congestion vector corresponding to the strategy profile σ . The utility of player i for a strategy profile σ is given by ui(σ) = dσi i(nσi(σ)). A Nash equilibrium of the game G is a strategy profile σ= (σ1 , . . . , σn) such that no player can benefit from joining a (possibly empty) sub-set of players sharing a different resource. Thus, if we denote by σ−i the (n− 1 ) -tuple of strategies obtained from σ by excluding the strategy of player i (so that σ= (σi , σ−i)) , we must have ui(σ)≥ ui(r , σ−i) , ∀i∈N , ∀r∈R\ {σi} . When a player i deviates (unilaterally) to choose a resource r ( r=σi ), she increases the congestion on r by 1. Hence, we have ui(r , σ−i) = dr i(nr(r , σ−i)) = dr i(nr(σ) + 1 ) . We can therefore write that σ is a Nash equilibrium if and only if dσi i(nσi(σ)) ≥dr i(nr(σ) + 1), for all iin Nand rin R\ {σi}. In this particular game, a player’s utility depends on only two variables: the resource r that she selects and the number, k , of players who use this resource. In fact, the utility of a player i is totally determined by her (cardinal) preferences over the pairs (r , k) of R× { 1, . . . , n} . These preferences can be represented by a mapping vi:R× { 1, . . . , n} → R defined by vi(r , k) = dr i(k) (note that vi is decreasing with k ). Thus, in this type of game, the study of Nash equilibria can be reduced to the study of player preferences on pairs (r , k) . This simplification is the basis of the method that we present here, which makes it possible to identify all the Nash equilibria in the case of two resources. To apply this method, we do not need the precise numerical values that the functions vi can take. Instead, we will solely utilize the rankings generated by these functions on the pairs (r , k) . Consequently, we will move to the framework of ordinal preferences and introduce the definition of congestion games within this ordinal context. The (ordinal) utility of player i will be represented by a weak ordering (i.e., a reflexive, transitive, and complete binary relation) ≾i on R× { 1, . . . , n} , such that for all pairs (r , k) and (r′ , k′) , the notation (r , k)≾i(r′ , k′) means that, for player i , sharing resource r′ with k′− 1 other players is at least as good as sharing resource r with k− 1 other players. The associated relations of strict preference and indifference, denoted by ≺i and ∼i , respectively, are interpreted in a similar way. Note that for each player i∈N , the ordinal preference ≾i is such that (r , k)≾i(r , k′) , for all (r , k) and (r , k′) in R× { 1, . . . , n} where k′<k (player i always prefers (or is indifferent to) sharing resource r with a smaller number of other players). We can now present the definition of (singleton) congestion games with playerspecific ordinal utilities (which we also call (ordinal) non-symmetric singleton congestion game), along with the definition of a Nash equilibrium in this framework. Definition 1. A (singleton) congestion game with player-specific ordinal utilities is a tuple G= (N , R , (≾i)i∈N) where N={ 1, . . . , n} is a set of n players, R={ 1, . . . , m} a set of m resources, and for all i∈N , ≾i is a weak ordering representing the ordinal utility of player i over the pairs (r , k) of R× { 1, . . . , n} . For all i in N , ≾i is assumed to be decreasing with k . A strategy profile is a n -tuple σ= (σ1 , . . . , σn) in Rn . A strategy profile σ= (σ1 , . . . , σn) is a Nash equilibrium of G if (σi , nσi(σ)) ≿i(r , nr(σ) + 1 ) , for all i in N and all r in R\ {σi} (no player prefers joining a group of players sharing a different resource). Games 2024,15, 7 4 of 10 It should be noted that the games described by this definition are more general than those introduced by [ 14 ]. The method we will present in the following section applies to games with ordinal utilities as well as to those with cardinal utilities. In the second case, it is sufficient, before applying this method, to replace the numerical values taken by the cardinal utility functions with the orders that they induce on the pairs (r,k). We conclude this section with an example illustrating and clarifying this transition. In this example, and in, the remainder of the paper, for simplicity, we will often use the notation k . r (or kr ) to denote the pair (r,k). Example 1. Let G be a congestion game with specific-player payoff functions, where N={ 1,2,3 } and R ={a,b,c}. Suppose the specific payoff functions are given by: da 1(1) = 9, da 1(2) = 7, da 1(3) = 2, db 1(1) = 20, db 1(2) = 6, db 1(3) = 6, dc 1(1) = 15, dc 1(2) = 12, dc 1(3) = 9; da 2(1) = 8, da 2(2) = 4, da 2(3) = 4, db 2(1) = 13, db 2(2) = 7, db 2(3) = 5, dc 2(1) = 13, dc 2(2) = 11, dc 2(3) = 1; da 3(1) = 9, da 3(2) = 7, da 3(3) = 2, db 3(1) = 25, db 3(2) = 17, db 3(3) = 14, dc 3(1) = 8, dc 3(2) = 6, dc 3(3) = 5. The cardinal preferences of the three players on the pairs (r , k) , described by the functions vi (i =1,2,3) are then such that: v1(a,3)<v1(b,3) = v1(b,2)<v1(a,2)<v1(c,3) = v1(a,1)<v1(c,2)<v1(c,1)<v1(b,1); v2(c,3)<v2(a,3) = v2(a,2)<v2(b,3)<v2(b,2)<v2(a,1)<v2(c,2)<v2(b,1) = v2(c,1); v3(a,3)<v3(c,3)<v3(c,2)<v3(a,2)<v3(c,1)<v3(a,1)<v3(b,3)<v3(b,2)<v3(b,1). Using the simplified notation for pairs (e.g., 2 a for (a ,2 ) and c for (c ,1 ) ), the ordinal preferences are given by: 3a≺13b∼12b≺12a≺13c∼1a≺12c≺1c≺1b; 3c≺23a∼22a≺23b≺22b≺2a≺22c≺2b∼2c; 3a≺33c≺32c≺12a≺1c≺3a≺33b≺32b≺3b. We can easily verify that, in this game, the strategy profile (c , c , b) is a Nash equilibrium. Indeed, we have 2c≿1a and 2c≿12b; 2c≿2a and 2c≿22b; b ≿3a and b ≿33c. 3. Results for the Two-Resource Case For the remainder of the paper, we set the number of resources at two and denote the set of these two resources by R={a , b} . We will present two results ( Propositions 1 and 2 ), which allow a complete description of the structure of the set of all Nash equilibria. Proposition 1 applies when all ordinal player preferences are strict. It indicates, in particular, that all Nash equilibria correspond to the same congestion vector (the vector giving the number of players having chosen each resource) and determines this vector. Proposition 2 applies when players’ preferences may include ties. It specifies the complete list of congestion vectors corresponding to Nash equilibria. The information provided by these two Propositions allows us, in the case of two resources, to easily draw up the exhaustive list of Nash equilibria for any congestion game with player-specific payoff functions. 3.1. Case 1: Strict Preference Orders To develop our approach, we need to extend player preferences to the pairs (a ,0 ) , (a , n+ 1 ) , (b ,0 ) , and (b , n+ 1 ) . We will use the following notation. For all players i∈N , we denote (a ,0 )≻i(b , n+ 1 ) (or 0 ·a≻i(n+ 1 )·b by adopting the simplified notation) when (a ,1 )≺i(b , n) . Similarly, we denote (b ,0 )≻i(a , n+ 1 ) (or 0 ·b≻i(n+ 1 )·a ) when (b ,1 )≺i(a , n) . Note that this extension is purely technical. It allows us to introduce the following integers: pi=max {p∈ {0, 1, . . . , n}:(a,p)≻i(b,n+1−p)} qi=max {q∈ {0, 1, . . . , n}:(b,q)≻i(a,n+1−q)} Games 2024,15, 7 5 of 10 The integer pi denotes the maximum size of a group choosing resource a in a given strategy profile, to which player i can belong. Beyond this size, player i will choose resource b . Indeed, by definition of pi , we have pi·a≻i(n+ 1 −pi)·b and (pi+ 1 )·a≺i(n−pi)·b . The integer qi is interpreted in the same way; replacing a with b . It is easy to see: pi+qi=n , ∀i∈N . Indeed, by the definition of pi , we have, on the one hand, pi·a≻i(n+ 1 −pi)·b (which implies that qi<n+ 1 −pi ), and on the other hand, (pi+ 1 )·a≺i(n−pi)·b (which implies that qi≥n−pi ). Using the list of integers pi and qi , ∀i∈N , we define two other integers which will be used to identify the congestion vector that can correspond to a Nash equilibrium of the game: n(a) = max {p∈ {0, 1, . . . , n}:|{i∈N:pi≥p}| ≥ p} n(b) = max {q∈ {0, 1, . . . , n}:|{i∈N:qi≥q}| ≥ q} The integer n(a) (resp. n(b) ) represents the maximum size of a group of players that can choose resource a (resp. b ) without any member of this group having an interest in deviating from his strategy. By construction of n(a) and n(b) , we necessarily have n(a) + n(b) = n . Finally, to state our first proposition, we introduce the following three sets In order to describe all Nash equilibria, we introduce the three following sets: A(G) = {i∈N:pi>n(a)} B(G) = {i∈N:pi<n(a)} C(G) = {i∈N:pi=n(a)} Note that N is the disjoint union of these three sets. Each of them may be empty and |C(G)| ≥ n(a)− |A(G)|. Proposition 1. Let R={a , b} and G(N , R , (≺)i∈N) be a singleton congestion game where all preference orderings are strict. 1. G admits at least one Nash equilibrium. All equilibria correspond to the same congestion vector: v = (n(a),n(b)). 2. Each Nash equilibrium of G , σ∗= (σ∗ 1 , . . . , σ∗ n) , is characterized by a unique (possibly empty) subset D of C(G) , of cardinal n(a)− |A(G)| , such that: For all i∈N , σ∗ i=a if i∈A(G)∪D and σ∗ i=b if i ∈B(G)∪(C\D). 3. The game admits exactly |C(G)| n(a)−|A(G)| Nash equilibria. In particular, if n(a) = |A(G)| the game admits a single Nash equilibrium (here, the notation (n p)designates the binomial coefficient). Proof. (1) By definition of n(a) , there are at least n(a) players i∈N such that pi≥n(a) . Therefore, we choose n(a) players satisfying this condition, including all players for whom pi>n(a) . Denote by A the set of these players. For all players who are in B=N\A , we must have pi≤n(a) and therefore qi≥n(b) . It is easy, returning to the definition of pi and qi , to verify that the profile σ∗= (σ∗ 1 , . . . , σ∗ n) defined by σ∗ i=a if i∈A and σ∗ i=b if i∈B is a Nash equilibrium. Conversely, let σ∗ be a Nash equilibrium of G and let (α , β) be the congestion vector associated with σ∗ . Suppose that α>n(a) . As σ∗ is a Nash equilibrium, there exist α players such that pi≥α , which contradicts the maximality of n(a) . We must, therefore, have α≤n(a) . Similarly, we show that β≤n(b) . As α+β=n and n(a) + n(b) = n, we necessarily have α=n(a)and β=n(b). (2) Let D be a (possibly empty) subset of C(G) , of cardinal n(a)− |A(G)| . Let σ∗= (σ∗ 1 , . . . , σ∗ n) be the strategy profile defined by: For all i∈N , σ∗ i=a if i∈A(G)∪D and σ∗ i=b if i∈B(G)∪(C(G)\D) . The profile σ∗ is a Nash equilibrium. Indeed, let i∈A(G)∪D . By definition of A(G) and D , we have pi≥n(a) . By definition of pi and the assumption of monotonicity, we obtain: n(a)·a≿i(n(b) + 1 )·b . Similarly, we show that for all i in B(G)∪(C(G)\D , n(b)·b≿i(n(a) + 1 )·a . Reciprocally, let σ∗= (σ∗ 1 , . . . , σ∗ n) be a Nash equilibrium of G . We know from (1) that the congestion vector associated with Games 2024,15, 7 6 of 10 σ∗ is (n(a) , n(b)) . We must have σ∗ i=a if i∈A(G) and σ∗ i=b if i∈B(G) . We just have to consider D={i∈N:σ∗ i=aand i/∈A(G)}. (3) The result is obtained by a simple calculation from (2). Example 2. Let N={ 1,2,3,4,5,6 } and R={a , b} . Suppose that the players’ preferences are given by the following strict orderings: Player 1 : 6b≺5b≺4b≺6a≺5a≺3b≺4a≺3a≺2b≺2a≺b≺a Player 2 : 6a≺6b≺5b≺4b≺5a≺4a≺3a≺3b≺2a≺2b≺a≺b Player 3 : 6b≺6a≺5a≺4a≺3a≺2a≺5b≺4b≺3b≺2b≺a≺b Player 4 : 6a≺6b≺5b≺4b≺5a≺4a≺3a≺3b≺2b≺2a≺b≺a Player 5 : 6a≺6b≺5b≺4b≺5a≺4a≺3a≺2a≺a≺3b≺2b≺b Player 6 : 6b≺5b≺4b≺6a≺5a≺4a≺3a≺2a≺3b≺2b≺a≺b To simplify the notation, we have omitted indices in the players’ preference orders. For each player i , we look for the integer pi (the greatest p such that p·a≻i(n+ 1 −p)·b and (n−p)·b≻i(p+1)·a). We have : p1=4 : 4a≻13b and 2b≻15a p2=3 : 3a≻24b and 3b≻24a p3=1 : 1a≻36b and 5b≻32a p4=3 : 3a≻44b and 3b≻44a p5=3 : 3a≻54b and 3b≻54a p6=3 : 3a≻54b and 3b≻54a So, we can verify that n(a) = 3and n(b) = 3. The only congestion vector corresponding to a Nash equilibrium is the vector ( 3,3 ) . Furthermore, we have A(G) = { 1 } , B(G) = { 3 } and C(G) = { 2,4,5,6 } . By theorem 1, we know that there are exactly C2 4 = 6 different Nash equilibria. All these equilibria are determined as follow: σ∗=a if i ∈A(G)and σ∗=b if i ∈B(G). Each of them is characterized by a subset D of C(G) with |D|= 2and σ∗ i=a if i∈D . Hence, the list of the Nash equilibria of this game is: (a,a,b,a,b,b),(a,a,b,b,a,b),(a,a,b,b,b,a), (a,b,b,a,b,a),(a,b,b,a,a,b),(a,b,b,b,a,a). 3.2. Case 2: Preference Orders with Ties As in the previous case, we introduce the integers pi and qi , which are defined this time by: pi=max {p∈ {0, 1, . . . , n}:(a,p)≿i(b,n+1−p)} qi=max {q∈ {0, 1, . . . , n}:(b,q)≿i(a,n+1−q)} For all i∈N , pi and qi have the same meaning as in the previous case. However, we do not necessarily have pi+qi=n because of the possible presence of ties. Hence, pi+qi≥n , for all i∈N . It is therefore possible to have pi+qi>n for some players, i . This point is important because, in this case, there is a possibility of having more than one congestion vector corresponding to a Nash equilibrium. Using the list of integers pi and qi , we define n(a) and n(b) as in Case 1. These two integers will be used to identify the congestion vectors that can correspond to the Nash equilibrium of the game. It is easy to see that n(a) + n(b)≥n , and we will show (Proposition 2); that if v= (α , β) is a congestion vector corresponding to a Nash equilibrium, then we must have α≤n(a) , β≤n(b) and α+β=n . For each vector v= (α , β) satisfying these three conditions, we introduce the three following sets: A(G,v) = {i∈N:pi≥αand qi<β},B(G,v) = {i∈N:pi<αand qi≥β}, Games 2024,15, 7 7 of 10 and C(G,v) = {i∈N:pi≥αand qi≥β} We can now state our second proposition. Proposition 2. Let R={a , b} and G(N , R , (≾)i∈N) be a singleton congestion game where the preference orders may include ties. 1. Each congestion vector v= (α , β) such that α≤n(a) , β≤n(b) and α+β=n , corresponds to (at least) one Nash equilibrium of G. 2. Each Nash equilibrium of G , σ∗= (σ∗ 1 , . . . , σ∗ n) , with congestion vector v= (α , β) is characterized by a unique (possibly empty) subset D of C(G , v) , of cardinal α− |A(G , v)| , such that: ∀i∈N, σ∗ i=a if i ∈A(G,v)∪D and σ∗ i=b if i ∈B(G,v)∪(C(G,v)\D). Proof. (1) Let v= (α , β) be a congestion vector such that α≤n(a) , β≤n(b) and α+β=n . Let D be a (possibly empty) subset of C(G , v) , of cardinal α− |A(G , v)| . Let σ∗= (σ∗ 1, . . . , σ∗ n) be a strategy profile such that: For all i∈N , σ∗ i=a if i∈A(G , v)∪D and σ∗ i=b if i∈B(G , v)∪(C(G , v)\D) . σ∗ is a Nash equilibrium. Indeed, let i∈A(G,v)∪D . By definition of A(G , v) and of D , we have pi≥α . By definition of pi and by the assumption of monotonicity, we obtain: α·a≿i(β+ 1 )·b . Similarly, we show that for all i in B(G,v)∪(C(G,v)\D),β·b≿i(α+1)·a. (2) Let σ∗= (σ∗ 1 , . . . , σ∗ n) be a Nash equilibrium of G and let v= (α , β) be the congestion vector associated with this equilibrium. We have α≤n(a) , otherwise there exist α players i with pi≥α>n(a) . This is impossible by definition of n(a) . Similarly, we show that β≤n(b) . By definition of a congestion vector, we also have α+β=n . As σ∗ is a Nash equilibrium, for any i∈N , we must have: σ∗ i=a if i∈A(G , v) and σ∗ i=b if i∈B(G , v) . We just need to consider D={i∈N:σ∗ i=aand i/∈A(G , v)} and to note that the case pi<αand qi<βis not possible. Example 3. Let N={ 1,2,3,4,5 } and R={a , b} . Suppose that the player’s preferences are given by the following weak orderings: Player 1 : 5a≺5b≺4b≺4a≺3b∼3a∼2a≺2b∼a≺b Player 2 : 5b∼4b∼5a∼4a∼3b∼3a∼2a∼2b∼a∼b Player 3 : 5a≺5b≺4b≺4a∼3b∼3a∼2b≺2a≺a≺b Player 4 : 5b≺4b≺5a≺4a∼3b∼3a∼2b≺2a≺b≺a Player 5 : 5b∼4b∼5a∼4a∼3b∼3a∼2a∼2b∼a∼b It is easy to see that: p1= 3, q1= 3, p2= 5, q2= 5, p3= 4, q3= 3, p4= 4, q4= 3, p5= 5, q5= 5. Hence, n(a) = 4and n(b) = 3. By proposition 2, the possible congestion vectors are: v1= ( 4,1 ) , v2= ( 3,2 ) , v3= ( 2,3 ) . Since v1= ( 4,1 ) , we have A(G , v1) = ∅ , B(G , v1) = { 1 } and C(G , v1) = { 2,3,4,5 } . Thus, there exists a unique equilibrium corresponding to v1 , which is given by the profile (b , a , a , a , a) . Similarly, as v2= ( 3,2 ) , we obtain A(G , v2) = ∅ , B(G , v2) = ∅ and C(G , v3) = { 1,2,3,4,5 } . The Nash equilibria corresponding to v2are: (b,b,a,a,a),(b,a,b,a,a),(b,a,a,b,a),(b,a,a,a,b),(a,b,a,a,b), (a,a,b,a,b),(a,a,a,b,b),(a,b,a,b,a),(a,b,b,a,a),(a,a,b,b,a). Games 2024,15, 7 8 of 10 Finally, for v3= ( 2,3 ) , we have A(G , v3) = ∅ , B(G , v3) = ∅ and C(G , v3) = { 1,2,3,4,5 } . The Nash equilibria corresponding to v3are: (b,b,b,a,a),(b,b,a,b,a),(b,b,a,a,b),(b,a,a,b,b),(a,b,b,b,a), (a,a,b,b,b),(b,a,b,b,a),(b,a,b,a,b),(a,b,b,a,b),(a,b,a,b,b). 4. Algorithms and Computation Examples The aim of this section is to illustrate and justify the theoretical results provided in this article. We will apply these results to propose two algorithms (Algorithm 1 and Algorithm 2) that allow us to calculate all Nash equilibria and to identify the best-cost equilibrium and the worst-cost equilibrium. In the previous sections, we considered congestion games with utility functions. However, the literature that is interested in optimal Nash equilibria generally considers congestion games with cost functions. The transition from utilities to costs is easily done by multiplying the numerical values of the utilities by − 1. The bestcost (resp. worst-cost) equilibria is the one that minimizes (resp. maximizes) the total cost. The price of anarchy (PoA) Koutsoupias and Papadimitriou [19] is defined as the ratio between the worst-cost equilibrium and the optimal ’centralized’ solution. The price of stability ( PoS ) Anshelevich et al. [24] is defined as the ratio between the best-cost equilibrium and the optimal ’centralized’ solution. In the applications we present here, we do not calculate PoA or PoS . Instead, we consider the quotient between them, which corresponds to the quotient between the social cost evaluated in the worst Nash equilibrium and the social cost evaluated in the best Nash equilibrium. The results of our experiments show that when the number of players increases, the PoA/PoS quotient also increases. For a number of players n= 1000, we find that this quotient is given by PoA/PoS ≈ 3.5, which means that the social cost of choosing the worst Nash equilibrium is 3.5 greater than the social cost when players choose the best Nash equilibrium. The coordination between actors may, therefore, be needed to reduce this cost significantly. These results were observed when preferences were strict or included ties (see Figures 1and 2below). We cannot confirm whether our two algorithms have polynomial time complexity. However, in practical applications, they have shown good performance in the instances we have processed. For n = 1000, the execution time remains reasonable, with t = 8 s for strict preferences and t = 60 s when preferences include ties. The increased execution time in the latter case is attributed to the higher number of congestion vectors. Algorithm 1: Find all Nash equilibria Input: Congestion game G= (N,R,≺i), cardinal utilities of each players 1: Let i:=1 2: repeat 3: Increase iby one 4: Find the integers (pi,qi) 5: Find the integers n(a),n(b) 6: Find A(G),B(G),C(G),D 7: until i=n Output: σ∗ i(all Nash equilibria). Algorithm 2: Find the best and the worst Nash equilibrium Input: σ∗ i(all Nash equilibria), Sthe sum of the utility of each Nash equilibrium 1: Let i:=1 2: repeat 3: Increase iby one 4: Find the best Nash equilibrium 5: Find the Worst Nash equilibrium 6: until i=n Output: σ∗ i(the best and worst Nash equilibria).