Multipotential Games

1 Introduction

Models of congestion come with many real-life stories and in various mathematical forms. They seem to originate at transportation engineering [Wardrop, 1952], and they have been analyzed by several researchers from various additional fields, in particular computer science, communication networks, economics, and game theory. 1 Every congestion model gives rise to a game in strategic form (normal form).

Our starting point is the model of [Rosenthal, 1973]. A congestion form is defined by a finite set of players, each of which holding one unit of goods, a finite set of facilities, and per-unit cost functions associated with the facilities. Each player must use a subset of facilities in order to make its unit of goods valuable. The non-empty set of feasible subsets of facilities is player-specific. When a player chooses a subset of facilities her per-facility cost depends on the number of other players that decide to use the facility, and her total cost is the sum of costs of the facilities in this subset.

Each congestion form F defines a game in strategic form, ΓF , which is called a congestion game. In ΓF the strategy set of a player is her set of feasible subsets of facilities, and her cost function is as described above. The distinction between congestion forms and congestion games is important. The form, which is also a sort of game, contains more information than its associated game in strategic form. Two distinct forms may induce isomorphic games. This distinction resembles the distinction between an extensive-form game and its associated strategic form game. For example, a congestion game rarely reveals the structure of the facility cost functions. Indeed, one can think of various natural solution concepts for a congestion form that have no sense in its associated game. For example, the players can choose the facilities sequentially, which gives rise to a multistage game in which we can deal with subgame perfect equilibria and other solution concepts that are natural in multistage games. On the other hand, many interesting conceptual or computational concepts for congestion forms require as input only the game. For example, Nash equilibrium, strong equilibrium, correlated equilibrium, social surplus, and price of anarchy. Two congestion forms are said to be equivalent if they generate isomorphic games. 2

1 See [Altman and Wynter, 2004] for a commendable attempt to unify the research.

Many applications of congestion forms/games come from networks. Hence, one may wish to consider a special type of congestion forms/games, in which facilities are edges in graphs and feasible subset of facilities are routes. It is natural to call such congestion forms network forms, and their associated congestion games network games. A natural question is how much we lose when we restrict attention to network forms. There are many modeling choices to make. We have decided to take the seemingly most restrictive definition: A network form is defined by a directed graph with only one origin and one destination. Nevertheless, we prove that dealing with networks does not restrict the generality. We prove that every congestion form is equivalent to a network form, or equivalently, that every congestion game is isomorphic to a network game. Hence, all other potential candidates for the term network games are isomorphic to network games in our sense, because they are in particular congestion games.

Much of the work on congestion games/forms has been inspired by the fact proved in [Rosenthal, 1973] that every such game has a potential function. The theory of general games that possess potential functions, i.e., of potential games was developed in [Monderer and Shapley, 1996], where the converse to Rosenthal's theorem was proved: Every potential game is isomorphic to a congestion game. However, there are two major differences between the proof that every potential game is isomorphic to a congestion game, and the proof that every congestion game is isomorphic to a network game. First, the proof that every congestion game is isomorphic to a network game is based on a transformation that transforms every congestion form to an equivalent network form. The number of facilities in the network form is twice the number of facilities in the congestion form. Hence we do not lose computational efficiency. In contrast the transformation given in [Monderer and Shapley, 1996] is not computationally efficient. 3

2 Unfortunately, there is no explicit distinction in the CS/AI literature between forms and games. Both are referred to as congestion games.

The second difference concerns the issue of preserving economics properties. The transformation given in this paper that transforms congestion forms to equivalent network forms, preserves the properties of both non-negativity and monotonicity of facility-cost functions.As we show in this manuscript the transformation in [Monderer and Shapley, 1996] does not preserve any of these properties. As all results in CS/AI on network games were proved with various types of monotonicity and non-negativity assumptions, the topic of faithful representation of potential games by congestion games is important if one wants to generalize these results to general potential games. We present here some partial results in this regard.

In this paper we actually deal with the above mentioned issues in a more general context. We discuss a generalization of congestion forms (games), in which the facility cost functions are player-specific. This assumption on the facility cost functions is natural in many applications. Forms with player-specific cost functions are called PS-congestion forms, and their associated games in strategic form are called PS-congestion games. 4 We also define and discuss PScongestion forms (games) of type q, or in short, q-congestion forms (games), where q is a positive integer. A PS-congestion form is of type q if the set of vectors of facility cost functions contains at most q distinct vectors, that is there exist at most q types of players. A 1-congestion form (game) is a congestion form (game).

Similarly we introduce a new type of games: q-potential games. A 1-potential game is simply a potential game. Roughly speaking, a game is a q-potential game if the set of players can be partitioned into q non-empty and mutually disjoint subsets Nj, 1 ≤ j ≤ q, in such a way that if we fix the strategies of all players outside Nj, the remaining subgame is a potential game. We show that the proof of equivalence between potential games and congestion games can be extended. That is, every q-congestion game is a q-potential game, and every (finite) q-potential game is isomorphic to a q-congestion game. We notice that every game is an npotential game, where n is the number of players. Therefore, we conclude that every game in strategic form is isomorphic to an n-congestion game. Hence, we get the somewhat surprising result that every game in strategic form is isomorphic to a PS-congestion game. 5

3 The transformation in the proof is linear in the parameters, and [Monderer and Shapley, 1996] gave a lower bound to the number of facilities required by this transformation to represent a given potential game by a congestion game. It is an open question to us whether a computationally efficient transformation exists.

4 Simple and facility symmetric PS-congestion forms/games (see Definition 1) were already discussed, e.g., in [Milchtaich, 1996].

We further prove that for every q ≥ 1, every q-congestion form is equivalent to a q-network form. That is, every game in strategic form is isomorphic to a PS-network game.

2 q-Potential Games and q-Congestion games.

2.1 Isomorphic games

A game in strategic form is a tuple Γ = (N, (Xi)i∈N, (Ci)i∈N), where N is a finite set of players which, whenever convenient, we take to be {1, · · · , n}; Xi is a set of strategies for i; and Ci : X → R is the cost function of i, where X = ×i∈NXi. Γ is called a finite game if the sets of strategies are finite sets. We say that two games Γ1 and Γ2 are isomorphic if each of them is obtained from the other by changing the names of the players and the names of the strategies. That is, there exist bijection functions (i.e., functions which are both one-to-one and onto) τ : N 1 → N 2 and αi : X 1 i →X 2 τ(i) , i ∈ N 1 , such that:

for every i ∈ N 1 and for every (x1j )j∈N 1 ∈ X 1,

2.2 Potential games

Let Γ = (N, (Xi)i∈N , (Ci)i∈N) be a game in strategic form. Let X-i denote the set of strategy profiles of all players but i. A function P : X → R is a potential function 6 for i if for

5 In some contexts it is useful to consider congestion forms, which generalize PS-congestion forms. In such forms the facility cost functions are not only player-specific, but also depend on the identity of the users of the facility. We call such forms ID-congestion forms. Classical ID-congestion forms are congestion forms with weights. Relationships between congestion games, ID-congestion games, and the Shapley value were given for example in [Monderer and Shapley, 1996; Ui, 2000; Monderer, 2006]. Another type of generalization of congestion forms is local-effect games [Leyton-Brown and Tennenholtz, 2003], in which nodes in a graph represent actions, cost functions are associated with nodes, and every such cost function depends on the number of users of the neighboring nodes. These type of games were generalized in [Bhat and Leyton-Brown, 2004] to action-graph games, which were proved to have full expressive power.

6 In [Monderer and Shapley, 1996], four types of potential functions were defined: exact potential, weighted potential, ordinal potential, and generalized ordinal potential. The term "potential" was used interchangeably with the term "exact potential". In recent literature, some other types of potentials have been considered. For example, best-response potential [Voorneveld, 2000], pseudopotentials ([Dubey et al., 2006]), ,various types of strong potentials [Holzman and Law-yone (Lev-tov), 1997], potential functions for mechanism design [Jehiel et al., 2004], several types of potential functions that represent various acyclicity properties [Kukushkin, 2002; 2004], and generalized potential functions [Moriss and Ui, 2004]. In some other works, the term potential is used for ordinal or generalized ordinal potentials. In this paper we keep the terminology of [Monderer and Shapley, 1996].

every xi, yi ∈ Xi, and for every x-i ∈ X-i,

Following [Monderer and Shapley, 1996], Γ is a potential game if there exists a function P which is a potential for every player i.

2.3 Congestion forms and congestion games

For the basic model of congestion forms and congestion games we follow [Rosenthal, 1973] and [Monderer and Shapley, 1996].

A Congestion Form is a tuple F = (M,N, (Σi)i∈N, (ca)a∈M), where M is a finite set consisting of m elements, which are called facilities, N is a finite set consisting of n elements, which are called players; For every i ∈ N, Σi ⊆ 2M \ {∅} is a non empty set of subsets of facilities, which is called the feasible set of i, and for every a ∈ M ca : [0,∞) → R is the per-unit facility cost function associated with a ∈ M; If k of the users choose a, each of them pays ca(k).

Every congestion form F = (M,N, (Σi)i∈N, (ca)a∈M) defines a game in strategic form ΓF , in which the set of players is N, Σi is the set of strategies of i, and for every i ∈ N the cost function of player i is defined on Σ = ×i∈NΣi as

where na(A) = |{j ∈ N : a ∈ Aj}|. 7 A game Γ in strategic form is called a congestion game if Γ = ΓF for some congestion form F. Two congestion forms are equivalent if they generate isomorphic congestion games.

2.4 Player-specific facility cost functions

When the cost functions associated with the facilities are player-specific we get a congestion form with playerspecific facility cost functions or, in short a PS-congestion form. Formally: A PS-Congestion Form is a tuple F = (M,N, (Σi)i∈N, ((cia)a∈M)i∈N) such that all components except for the cost functions are defined as in a congestion form, and cia : [0,∞) → R is i's facility cost function associated with a ∈ M; If k of the users choose a, agent i pays cia (k).

Definition 1 A PS-congestion form is facility-symmetric if Σi = Σj for every i, j ∈ N. A PS-congestion form is simple if Σi contains only singletons for every player i.

Every PS-congestion form F = (M, N, (Σi)i∈N , ((cia )a∈M)i∈N) uniquely defines a game in strategic form ΓF , in which the set of players is N, Σi is the set of strategies of i, and for every i ∈ N the cost function of player i is defined as follows:

7 Hence, only the values of ca on the set of integers {1, · · · , n} are relevant. However, it will be useful later, and it does not restrict the generality, to define ca on the whole interval [0,∞).

A game Γ in strategic form is called a PS-congestion game if Γ = ΓF for some PS-congestion form F. Thus, every congestion form is a PS-congestion form, and every congestion game is a PS-congestion game.

2.5 q-Congestion forms and q-congestion games

Roughly speaking, a PS-congestion form is of type q if the players can be partitioned into q types, where two players are of the same type if they share the same facility cost functions. Formally, Let F = (M,N, (Σi)i∈N, ((cia)a∈M)i∈N) be a PS-congestion form. A finite set K ⊆ (R[0,∞) )M is a cover for F if for every player i there exists c = (ca)a∈M ∈ K such that for every a ∈ M cia = ca.

Let q be a positive integer. We say that F is a q-congestion form if it has a cover H with |H| ≤ q. Obviously, if F is a q-congestion form, F is a (q + 1)-congestion form. Because K = {(c1a)a∈M, · · · , (cna)a∈M} is a cover for F , every n-person PS-congestion form is an n-congestion form. Let 1 ≤ q(F) ≤ n be the index of F , defined as the minimal cardinality of a cover for F. Obviously, F is a congestion form if and only if q(F) = 1. If F is a q-congestion form, ΓF is called a q-congestion game.

2.6 q-Potential games

Let Γ = (N, (Xi)i∈N , (Ci)i∈N) be a game in strategic form. Let H be a set of real-valued functions defined on X. We say that H is a cover of Γ if for every i ∈ N there exists P ∈ H, which is a potential function for i. Let q be a positive integer. We say that Γ is a q-potential game if it has a cover H with |H| ≤ q. Obviously, if Γ is a q-potential game, Γ is a (q+1)- potential game. Because Ci itself is a potential for i, every n-person game is an n-potential game. Let 1 ≤ q(Γ) ≤ n be the potential index of Γ, defined as the minimal cardinality of a cover for Γ. Obviously, Γ is a potential game, if and only if Γ is a 1-potential game if and only if q(Γ) = 1.

Let Γ be a q-potential game . Let H = {P1, · · · , Pq}, |H| = q, be a cover of Γ, and let Hs be the set of all players i such that Ps is a potential function for i. A partition of the player set N to q nonempty and mutually disjoint subsets π = (Ns)qs=1 , is consistent with H if Ps is a potential function for every i ∈ Ns, that is, Ns ⊆ Hs for every 1 ≤ s ≤ q. In a potential game with a potential function P, all players behave as if there exists one player whose goal is to minimize P over X. In a q-potential game with a cover H = {P1, · · · , Pq} and an H-consistent partition π = (Ns)qs=1 , the players behave as if there are q players, Is, 1 ≤ s ≤ q, playing a q-person game with the set of strategies X[s] for player Is, where X[s] = ×i∈Ns Xi. For x = (x[s])1≤s≤q, the cost function of Is is Ps. Note that every equilibrium x in the associated q-person game is also an equilibrium in the original game. Similarly, every correlated equilibrium corresponds to a correlated equilibrium. 8

Unfortunately, as is shown in the next example, a cover with a minimal cardinality may have more than one consistent partition. In particular, the partition of the players' set to q subsets in a q-potential game with an index q is not uniquely determined by the game. Bellow is an example for a 3-player game with a potential index 2 in which both partitions 12, 3 and 1, 23 are consistent with the same cover H, where |H| = 2.

8 However, a mixed-strategy equilibrium in the associated qperson game corresponds only to a correlated equilibrium in the original game, and not necessarily to a mixed-strategy equilibrium.

Example 1 We construct a game Γ. The strategy set of every player 1 ≤ i ≤ 3 is {0, 1}. The cost functions are: C1(x) = C1(x1, x2, x3) = x2x3, C2(x) = x1x3, C3(x) = x1x3 + x1x2. We first show that this is not a 1-potential game. Indeed, by [Monderer and Shapley, 1996] it suffices to show that there exists a closed path of strategy profiles in X, γ = x(0), x(1), x(2), x(3), x(4) with x(0) = x(4), such that x(t + 1) is obtained from x(t) by changing the strategy of exactly one player, it, 0 ≤ t ≤ 3, and such that I(γ) ̸= 0, where

Indeed, for the path γ = (0, 1, 0), (1, 1, 0), (1, 1, 1), (0, 1, 1), (0, 1, 0), I(γ) = -1. Observe that P(x) = 0 for every x ∈ X is a potential function for both player 1 and player 2, and that C2 is a potential function for both player 2 and player 3. Hence, H = {0,C2} is a cover for Γ, and both partitions 12, 3 and 1, 23 are consistent with H.

2.7 Representation of q-potential games by q-congestion forms

It was proved in [Rosenthal, 1973] that every congestion game is a potential game. It was proved in [Monderer and Shapley, 1996] that every finite potential game is isomorphic to a congestion game. The two theorems are extended in this section.

Theorem 1

1. Every q-congestion game is a q-potential game.
2. Every finite q-potential game is isomorphic to a qcongestion game.

The proof of Theorem 1 is given in the full version.

We end with a somewhat surprising corollary:

Corollary 1 Every game in strategic form is isomorphic to a PS-congestion game.

Proof: As we noticed above, every game in strategic form is an n-potential game. By Theorem 1 every n-potential game is isomorphic to an n-congestion game.

3 Network Forms and Network Games

Much of the literature about congestion forms has been motivated by transportation systems and by digital networks. In such models, facilities are edges in a graph, and feasible sets of facilities are routes. In this paper the terms network form and network game are defined in a specific way. All other graphical models fall under the category of congestion forms (games).

Consider a loop-free directed graph GR with a finite set of vertices V = VGR, and a set of edges E = EGR. 9 Every feasible subset of facilities for i represents a feasible route (a path with distinct vertices) in the graph. For every o, d ∈ V , o ̸= d we denote by R(o, d) the set of all routes that connect o to d. A PS-network form is a PS-congestion form F = (M, N, (Σi)i∈N , ((cia)a∈M)i∈N) for which there exists a directed graph, and two distinct vertices in this graph o and d, with R(o, d) ̸= ∅ such that M ⊆ E and Σi ⊆ R(o, d) for every agent i. A game Γ in strategic form is called a PS-network game if Γ = ΓF for some PS-network form F. Naturally, a q-network form is a PS-network form of type q, and a q-network game is a PS-network game derived from a q-network form. A 1-network form is also called a network form, and a 1-network game is also called a network game.

Theorem 2 Every q-congestion form is equivalent to a qnetwork form.

Proof: Let F = (M,N, (Σi)i∈N, ((cia)a∈M)i∈N) be a qcongestion form. Assume M = {a1, . . . , am}, and let K = {b1, · · · , bm} be an arbitrary finite copy of M that does not intersect with M. We construct a graph GR as follows: The set of vertices is V = {1, · · · ,m+ 1}. For every 1 ≤ j ≤ m we connect j to j + 1 with two edges, aj, bj. That is, j is the tail of both aj and bj, and j + 1 is the head of both. We denote o = 1 and d = m+1. For every Ai ∈ Σi we associate a route αAi as follows: αAi = z1, z2, · · · , zm, where zj = aj if aj ∈ Ai, and zj = bj if aj ̸∈ Ai. With the edges aj we associate the cost function (ciaj )i∈N, and with the edges bj we associate the cost functions which are constantly zero. It is obvious that we constructed a PS-network form of type q, and that the q-network game derived from this form is isomorphic to ΓF .

The following example together with its associated figure illustrates the proof of Theorem 2.

Example 2 Consider the congestion form F,in which N = {1, 2}, M = {a1, a2, a3, a4}, Σ1 = {{a1, a2}, {a3, a4}}, and Σ2 = {{a1, a3}, {a2, a4}}. F is transformed to the network form shown in Figure 1 in which Σ∗1 = {a1a2b3b4, b1b2a3a4}, and Σ∗2 = {a1b2a3b4, b1a2b3a4}. The cost functions on the aj-links, j = 1, 2, 3, 4 are the original cost functions, and the cost functions on the bj-links are constantly zero.

9 One may use non-directed graphs. In this paper we basically follows the definition of [Holzman and Law-yone (Lev-tov), 2003].

10 Other graphical representations of games have been analyzed in the literature of computer science and artificial intelligence. In some of these representations the focus is on dependencies among players' utility functions (see, e.g., [Kearns et al., 2001;

Proof: The proof follows from combining Corollary 1 with Theorem 2.

4 Faithful representations

In many real-life applications it is natural to assume that the facility cost functions of a PS-congestion form have a special structure. In particular, it is natural to assume that the facility cost functions are nonnegative and in addition are either non-decreasing or non-increasing, depending on the context. It is easy to check that the particular representation method described in the proof of Theorem 1 (or in the analogous proof in [Monderer and Shapley, 1996]) may represent a finite q-potential game with nonnegative costs by a q-congestion form in which some of the facility cost functions take negative values. Actually, the representation method depends on the choice of the potential functions. However, it can be seen that there exists a finite 1-potential game such that for every choice of a potential function the representation method yields a 1-congestion form with some facility cost functions that take negative values. This suggest three questions:

Question 1: Can every finite q-potential game with nonnegative cost functions be represented (up to an isomorphism) by a q-congestion form with non-negative facility cost functions?

Question 2: Can every finite q-potential game with nonnegative cost functions be represented (up to an isomorphism) by a q-congestion form with non-negative and non-decreasing cost functions?

Question 3: Can every finite q-potential game with nonnegative costs be represented (up to an isomorphism) by a q-congestion form with non-negative and non-increasing cost functions?

We show that the answer to Question 2 is negative by the next example:

Example 3 Consider the following parametric game with z > 0.

x2

y2

Γz is a congestion game because it is a potential game with a potential function Pz, where

Koller and Milch, 2001; Mura, 2000; Vickrey and Koller, 2002]). Other types of representations focus on actions' dependencies- see [Leyton-Brown and Tennenholtz, 2003; Bhat and Leyton-Brown, 2004].

Let N = {1, 2}. Assume in negation that Γz is isomorphic to ΓF , where F = (M, N, (Σi)2i=1 , (ca)a∈M) is a congestion form in which the cost functions are non-negative and nondecreasing. In particular, for every facility a

Because ΓF is isomorphic to Γz, we may assume that the feasible sets in F are parameterized as follows: Σ1 = {Ax1 ,Ay1 }, and Σ2 = {Ax2 ,Ay2 }. Also, without loss of generality we can assume that M = Ax1 ∪ Ay1 ∪ Ax2 ∪ Ay2 . Note that

Therefore, ca(1) = 0 for every a ∈ Ay2 \Ay1 , and ca(2) = 0 for every a ∈ Ay2 ∩ Ay1 . Since ca(1) ≤ ca(2), we conclude that ca(1) = 0 for every a ∈ Ay2 . It follows that

On the other hand,

and therefore ∑a∈Ay2 ∩Ax1 ca(2) = 0, contradicting < ∗ >.

Note, however, that Γz in Example 3 can be represented by a simple congestion game with non-negative and nonincreasing cost functions. Consider the congestion form Fz with two resources a, b. ca(1) = ca(2) = 0. cb(1) = z, and cb(2) = 0. It is easily verified that ΓFz is isomorphic to Γz. Hence, Question 1 and 3 can still have positive answers.

If we are less ambitious, and we allow representing qpotential games with r-congestion games with r > q, we show in the full paper that the answer to the modified version of Question 1 and 2 is positive. The proof of the following lemma is given in the full version:

Lemma 1 Every game in strategic form with non-negative cost functions is isomorphic to a PS-congestion game derived from a PS-congestion form with non-negative and nondecreasing facility cost functions.

We end this section with an example showing two congestion forms with the same combinatorial structure (same set of facilities and same feasible sets) and with positive cost functions that represent the same game. However, the facility cost functions in one of them are decreasing and in the other, increasing.

Consider the parametric congestion forms F, in which M = {a, b, c, d}, Σ1 = {{a, b}, {c, d}}, Σ2 = {{a, c}, {d, d}}. The cost functions are

Hence, Γ can be represented by this particular congestion form if there exists a solution to the following linear system with 8 equations and 8 variables:

It is easy to see that this system has solutions depending on two parameters s, t:

Obviously t = 1, s = 6 gives a congestion form with positive and increasing cost functions, while t = 6, s = 1 give a congestion form with positive and decreasing cost functions.