--- title: "Multi-Population Congestion Games With Incomplete Information" authors: - "Charlotte Roman" - "Paolo Turrini" doi: "10.24963/ijcai.2019/80" url: "https://ijcai.org/proceedings/2019/80" pdf: "https://ijcai.org/proceedings/2019/0080.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "565-571" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Resource Allocation" - "Agent-based and Multi-agent Systems: Noncooperative Games" - "Agent-based and Multi-agent Systems: Algorithmic Game Theory" --- # Multi-Population Congestion Games With Incomplete Information Charlotte Roman, Paolo Turrini *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 565-571. DOI: [10.24963/ijcai.2019/80](https://doi.org/10.24963/ijcai.2019/80) ## Abstract Congestion games have many important applications to systems where only limited knowledge may be available to players. Here we study traffic networks with multiple origin-destination pairs, relaxing the simplifying assumption of agents having complete knowledge of the network structure. We identify a ubiquitous class of networks, i.e., rings, for which we can safely increase the agents’ knowledge without affecting their own overall performance - known as immunity to Informational Braess’ Paradox - closing a gap in the literature. By extension of this performance measure to include the welfare of all agents, i.e., minimisation of social cost, we show that IBP is a widespread phenomenon and no network is immune to it. ## Full text ## 1 Introduction With the rising popularity of GPS route-guidance systems, many travellers rely on information about route choice to help them make navigation decisions. It is natural to assume that more information about paths available to a driver would only reduce their expected journey time. However, this has been shown not to be the case [Acemoglu et al., 2018]: presenting new options can change the decision-making of some selfinterested agents, causing an overall re-routing which makes them worse off. Congestion games are the standard framework of algorithmic game theory to study the equilibria of traffic flows. These are non-cooperative games of perfect information where selfinterested actors choose sets of available resources, where the cost of each resource depends on its overall usage. In the traffic-specific Wardrop model [Wardrop, 1952], resources form an undirected network in which the players wish to travel between origin and destination nodes, and the cost of each edge typically represents the expected travel time. Rational players seek to minimise their overall cost by selecting the appropriate path. On top of that, all players have an origin-destination (OD) pair which corresponds to the nodes they wish to travel between, and players with the same OD pair are grouped into populations. ∗Contact Author It is likely that travel costs will change over time e.g. from road improvements or temporary construction works. Braess' Paradox (BP) [Braess, 1968] occurs when the cost of a resource is reduced but the total cost to the population increases. BP assumes the state of the system is in a user equilibrium (or Wardrop equilibrium), where every player has minimised personal costs of travel given the actions of others. BP is based on the assumption that agents have complete information about the network structure. However, this assumption is often not met in practical situations, when, typically, actors have incomplete knowledge of their available paths. Recently, information constrained user equilibrium (ICUE) [Acemoglu et al., 2018] has been introduced, where each player minimises their travel costs given their current knowledge. The equilibrium is reached through one-step improvements and gives rise to Informational Braess' Paradox (IBP) which occurs when users' cost at ICUE increase as a result of their information set expanding. ICUE is certainly a more realistic tool to predict traffic flows, but the study of equilibria in congestion games with incomplete information is still at its infancy. In particular, while the relationship between network structure and immunity to IBP has been characterised for single-population congestion games [Acemoglu et al., 2018], for the more complex and realistic multi-population variant the exact conditions are still unknown. On top of that, IBP has only been formulated looking at one group, i.e., the one that acquires new knowledge, but not at the welfare of all agents, which is the standard social cost metric used for congestion games. Our contribution. In this paper, we advance the analysis of congestion games played by heterogeneous boundedly rational agents, in two important ways. Firstly, we establish how a ubiquitous class of networks, rings, are immune to IBP, settling a conjecture in [Acemoglu et al., 2018]. Secondly, we extend the analysis of IBP to take into account the welfare of all agents, rather than a subset of them, showing that under this measure IBP is a widespread phenomenon and no network is immune to it. Our analysis is an important first step for the design of road systems that do not penalise the acquisition of new knowledge. Related literature. Since the seminal work by Braess [Braess, 1968], the topic of routing paradoxes has been extensively explored [Murchland, 1970; Zhao et al., 2014]. Congestion games appear often in transportation systems [Fisk, 1980; Pas and Principio, 1997; Zhao et al., 2014; Yao et al., 2018] but they also apply to a wide variety of real-world systems, with applications to telecommunication [Orda et al., 1993] and electrical networks [Roughgarden, 2005]. Player heterogeneity has been a topic of much interest, e.g. through player-specific resource cost functions [Milchtaich, 1996] representing varied preferences [Cole et al., 2018] or uncertainties [Beier et al., 2004; Sekar et al., 2018], while more complex models may consider driver's uncertainties over road conditions or demand [Meir and Parkes, 2015]. There is evidence that providing incomplete information to drivers about road capacities may be worse than providing no information at all [Arnott et al., 1991]. Along the same line, Liu et al. [Liu et al., 2016] studied heterogeneity among players regarding the quality of information they receive and how that affects the equilibrium costs. Paper structure. Section 2 presents the preliminary notions and definitions needed for our results. Section 3 proves that multi-population congestion games on ring networks will not allow travellers acquiring knowledge to be negatively impacted by information. An alternative performance measure, i.e., social cost, is posed in Section 4, which induces losses in utility by some agent independently of the network topology. We conclude discussing future research directions. ## 2 Preliminaries ## 2.1 Congestion Games Let N = {1, ..., n} be a nonempty finite set of agents populations. In each population, we suppose there exists heterogeneity among knowledge of the resources (due to previous experience, use of GPS systems etc.), i.e., Ki ≥ 1 information types of players in each population i. We refer to a player from population i of type k as (i, k), which we abbreviate ik, where the demand for a type, i.e., the traffic rate associated with that population, is dik ≥ 0. Each population has a nonempty finite resource set Ei, where information types can restrict such knowledge, i.e., each population-type pair is associated with a known set Eik ⊆ Ei. We assume that each Ei is made of relevant resources, i.e., those which are used in at least one strategy, and that strategy sets Sik ⊆ 2Eik only contain resources from their information set and are disjoint for distinct populations. Denote E as the irredundant resource set E = ⋃i∈N Ei. Finally, resource cost functions ce : R≥0 → R≥0 ∪ {∞} such that e ∈ E are assumed to be continuous, non-decreasing and non-negative. Formally, a nonatomic congestion game is defined as a tuple M = (N, (Ki), (Eik), (Sik), (ce)e∈E, (dik)), with i ∈ N and k ∈ Ki . The outcome of all players of type (i, k) choosing strategies leads to a strategy distribution xik satisfying ∑sik∈Sik xik sik = dik and xik sik ≥ 0, ∀sik ∈ Sik. A strategy distribution or outcome x = (xik ){i∈N, k∈Ki} is feasible if ∑sik∈Sik xik sik = dik, ∀i ∈ N, k ∈ Ki. Henceforth, we focus, without loss of generality, on feasible strategies. Figure 1: Braess' paradox on the Wheatstone network. When d = 1, the social cost of travel is 32 before and 2 after reducing the costs of the middle edge. ![Image](https://ijcai.org/proceedings/2019/fulltext/80/image_000000_05a659f35f3f6619ba58c7ba8af46091d70818e047399ff531a0b0e4eb4bb6d0.png) Denote the load on e in an outcome x to be fe(x) = ∑i∈N ∑si∈Si xisi 1si (e) where 1 is the indicator function. In x, a player from population i receives a cost function C(sik, x) = Cik(sik, x) = ∑e∈sik ce(fe(x)) when selecting strategy sik ∈ Sik. An information constrained user equilibrium (ICUE) is a strategy distribution x such that all players choose a strategy of minimum cost: ∀i ∈ N, k ∈ Ki and strategies sik, s′ik ∈ S(i,k) such that xisik > 0 we have Cik(sik, x) ≤ Cik(s′ik , x). The social cost is the total cost incurred to all players SC(x) = ∑i∈N ∑k∈Ki Cik(x)dik. Braess' paradox is a phenomenon that arises when the cost of a resource is strictly decreased yet results in a strict increase in the social cost of the equilibria. This can be observed in the Wheatstone network in Figure 1. A set of systems (E, Si)i∈N admits Braess' paradox (BP) if there are two nonatomic congestion games M = (N,E, (Si)i∈N, (ce)e∈E, (di)i∈N) and M′ = (N,E, (Si)i∈N, (c′e )e∈E, (d′i )i∈N) where c′e (t) ≤ ce(t), ∀t ≥ 0 and d′i ≤ di, ∀i ∈ N, and two UE x and x′ , such that SC(x) < SC(x′ ). If no suchMandM′ exist, then we say that the network is immune to Braess' paradox. Informational Braess' paradox (IBP) occurs when one player's type has its information set expanded, without loss of generality type (1, 1), and this paradoxically increases their strategy cost. More formally, IBP occurs if there exist expanded information sets ( ˜E(i,k)){i∈N, k∈Ki} with E(1,1) ⊂ ˜E(1,1) and E(i,k) = ˜E(i,k) for any (i, k) ̸= (1, 1) with associated ICUE x and ˜x, where the costs increase for the expanded information player C(1,1)(x) < C(1,1)( ˜x). ## 2.2 Graph Theory A simple network G = (V, E) is an undirected graph with at most one edge between any pair of nodes and no self-loops. A path is an ordered collection of edges such that adjacent pairs of edges share a node. If a path visits no node more than once then it is called acyclic. A tree is a connected simple network that has only acyclic paths. A ring is a network such that every node connects to exactly two others, forming a single continuous loop. A network congestion game is played on an undirected network G = (V,E), where the resources are edges and players move between the distinct origin and destination terminal nodes oi, di ∈ V for any i ∈ N. The strategies of players are choices of paths such that no vertex is visited more than once and such that the start and end nodes are the associated origin and destination. If a network is two-terminal then there is a single origin and destination pair for players to travel between. An asymmetric or multi-population game is one in which there are multiple OD pairs. Figure 2: A Wheatstone network is embedded in any grid. ![Image](https://ijcai.org/proceedings/2019/fulltext/80/image_000001_cfecdc5781c4387416b83c3134685f4ec5331e79987dcddc5950d034356b426f.png) We say that a two-terminal network is linearly independent (LI) if each path has at least one edge that does not belong to any other path. A network is series linearly independent (SLI) if and only if (i) it comprises a single LI network, or (ii) it is constructed by connecting two SLI networks in series. For two SLI networks Gi and Gj, a coincident block is a common LI subnetwork of Gi and Gj with the same set of terminal nodes. An embedding is a collection of injective maps from the sets of relevant resources to the irredundant resources. For example, Figure 2 shows how the Wheatstone network is embedded in a grid road system. ## 2.3 Immunity to IBP The following theorems from the literature specify the known conditions for IBP to not occur. The first result is for congestion games with only one population of players. For multiple populations, the conditions for immunity to IBP are unknown, with Theorem 2 establishing a fairly direct sufficient condition for the multi-population case. Theorem1. [Acemoglu et al., 2018] A two-terminal network congestion game played on network G is immune to IBP if and only if G is an SLI network. Theorem 2. [Acemoglu et al., 2018] For any asymmetric network congestion game on network G, where ∀i ∈ N Gi = (Vi,Ei) is the relevant network, IBP does not occur if the following hold: (a) ∀i ∈ N, Gi is SLI (b) For all distinct i, j ∈ N, either Ei ∩ Ej = ∅, or Ei ∩ Ej consists of all coincident blocks of Gi and Gj . Notice that the conditions from Theorem 2 do not depend on information restrictions. The result does, however, depend on the maximal information sets of populations which combine to form the relevant network. ## 3 Circuit Games and IBP In this section, we formally introduce circuits, most commonly found in matroid theory, for which immunity to IBP was an open question [Acemoglu et al., 2018]. As discussed with more detail, later on, circuits model common transportation networks, such as stadiums exit routes. Consider a set system (E, C), where E is the set of resources and C ⊆ 2E , with the following axioms: - ∅ /∈ C; - If C1, C2 ∈ C and C1 ⊆ C2, then C1 = C2, - For any two distinct C1, C2 ∈ C such that e ∈ C1 ∩ C2, there is a member C3 ∈ C such that C3 ⊆ (C1 ∪C2)\{e}. Then C is a circuit over E. A circuit game is a congestion game in which every relevant network Gi = (Vi, Ei) ∀i ∈ N is a circuit. We now establish this useful lemma, whose proof we only sketch due to space limitations. Proposition 1. A circuit game cannot exist on a network G that is not simple. Proof sketch. Let e1, e2 be two nodes in a non-simple network which are connected multiple times. Let e1 ∈ Ei, and therefore e2 ∈ Ei. By definition, the relevant network of i must be a circuit Ci and it must be that e1, e2 ∈ Ci. It is easy to see that C ′ i = {e1, e2} is a circuit. But then, if C ′ i ⊆ Ci then Ci = C ′ i . So i can only travel between the end nodes of e1 and e2. There must exist another population j ̸= i whose strategies also include e1 and e2 and must also travel on the circuit Cj = {e1, e2} = Ci. But then i = j, which is a contradiction. Hence, G must be simple. Proposition 1, notice, implies that any ring forms a circuit game. Now we are in a position to prove the following: Proposition 2. Any two-terminal circuit game is immune to IBP. The proof of Proposition 2 follows from Theorem 1 since it can be shown, using Proposition 1, that a circuit game network is SLI. This result confirms the current classification of IBP immunity from Theorem 2. When considering multiple origin-destination pairs, the circuit axioms now apply to slightly more complex structures than simple rings. A circuit game can comprise connected rings such that the OD pairs do not allow for traversal between rings. Before we can prove the immunity to IBP for such structures, we pose the more general statement that not all player types can be negatively impacted by a single information expansion. We omit the proof for the general case, but we give the idea behind the proof technique and present the full reasoning for the case of n = 2. Proposition 3. Let Mbe an asymmetric circuit game and let ( ˜E(i,k)){i∈N, k∈Ki} be expanded information sets such that E(1,1) ⊂ ˜E(1,1) and E(i,k) = ˜E(i,k) for any (i, k) ̸= (1, 1), with associated ICUE x and ˜x. Then there exists at least one player type (i, k) i ∈ N, k ∈ Ki such that C(i,k)(˜x) ≤ C(i,k)(x). Proof idea. In a circuit, we can show that each population has at most two strategies. Each population that has only one strategy will not affect the equilibria before and after the information expansion, except the type (1, 1) whose strategy set expands. So we can assume that for n populations there are at most n + 1 types. Since there are n populations with distinct OD pairs, the game must be embedded in a 2n-edge circuit. Now if we compare the contradiction assumption for each of the types, we know that the strategy they use before the expansion must have strictly less flow on at least one of the edges in the strategy than afterwards. Now if we compare all n + 1 inequalities we will find that there is always a contradiction since the demands of populations must be nonnegative. Figure 3: A circuit with two populations. ![Image](https://ijcai.org/proceedings/2019/fulltext/80/image_000002_bbb60b643e828600d32e4065580686bfbdf049b0221ac783d1a7d3cb1e6710c4.png) The following example shows that for the case where n = 2 as displayed in Figure 3. There can be up to four types when n = 2, but it is sufficient to show the result for only two types as the same reasoning holds with or without the other types. Example 1. Let there be two populations each with distinct OD pairs. Strategy sets of player type (1, 1) are S11 = {s1} before and ˜ S11 = {s1, s2} after expansion with demand d11 > 0. Player type (2, 2) strategies are S22 = {t1, t2} with demand d22 > 0. In order to reach a contradiction, suppose that there does not exist such a player as defined in Proposition 3. Namely, C11(˜x) > C11(x) and C22(˜x) > C22(x). Consider the feasible strategy distributions x. Since type (1, 1) has only one strategy, we have xs1 11 = d11. In order for every player's cost to increase, we must have that (1, 1) strictly prefers to deviate to the other strategy. Now suppose that (2, 2) plays xt1 22 = pd22, xt2 22 = (1 - p)d22 where p ∈ [0, 1]. The cost functions for players are: where Now examine the feasible strategy distributions ˜x. Consider ˜xs1 11 = d11 as the strategy distribution for population 1. This could only be an ICUE if it was a dominant strategy given the total demand of population 2, which we know is not true given the deviation from s1 in strategy distribution x. So we must have ˜xs1 11 = qd11 and ˜xs1 11 = (1-q)d11 where q ∈ [0, 1). For population 2, let the strategy distribution be xt1 22 = ˜ pd22, xt2 22 = (1 - ˜ p)d22 where ˜ p ∈ [0, 1]. The cost functions after information expansion are: where The contradiction assumption, C11(x) < C11(˜x), gives us: Since cost functions are non-decreasing, this implies that we must have either f1 < ˜ f1 or f2 < ˜ f2. In terms of demands, either d11 + (1 - p)d22 < qd11 + (1 - ˜ p)d22 or d11 +pd22 < qd11 + ˜ pd22. If both these hold, we have ˜ p + (1-q)d11 d22 < p and ˜ p + (1-q)d11 d22 > p, which leads to a contradiction. Now suppose p, ˜ p ∈ (0, 1). Then the second contradiction assumption, C22(x) < C22(˜x), leads to: Similarly, by nondecreasing cost functions, we must have either f1 < ˜ f1 or f3 < ˜ f3. It must also be true that at least one of f2 < ˜ f2 or f4 < ˜ f4 is true. Suppose we have f1 < ˜ f1 and f4 < ˜ f4, this also leads to the contradiction of ˜ p+ (1-q)d11 d22 < p and ˜ p+ (1-q)d11 d22 > p. So it must be true that f3 < ˜ f3 and f2 < ˜ f2. But this gives us ˜ p < (1-q) d11 d22 +p and ˜ p > (1 - q) d11 d22 + p, hence, we have reached a contradiction for p, ˜ p ∈ (0, 1). Now suppose p = [0, 1), ˜ p ∈ [0, 1). Then we have This gives us (1-q)d11 d22 + ˜ p < p which means p > 0 since d11, d22 > 0. So ˜ p = 0, otherwise, we have the case as above. However, this implies we have which again, as above, will lead to a contradiction. Now suppose p = (0, 1], ˜ p ∈ (0, 1]. The contradiction assumption now gives us: Hence, qd11 d22 + p < ˜ p. Using similar reasoning as before, we see that we must have p < 1 and ˜ p = 1. Thus, Hence, we reach a contradiction. Now suppose p = [0, 1), ˜ p = (0, 1]. Then we see that So we must have that (i) and (iii) hold so we have (1-q)d11 d22 + ˜ p < p. Hence, we must have p, ˜ p ∈ (0, 1) which we have already shown to be contradictory. Now suppose p = (0, 1], ˜ p = [0, 1). Then we have This implies (1-q)d11 d22 + p < ˜ p must hold, which means that we have p, ˜ p ∈ (0, 1), leading to the final contradiction. Now that we have shown that a circuit game will not increase all player's costs from information distribution simultaneously, we can prove that information cannot harm the player who receives it. Theorem 3. Any circuit game is immune to IBP. Proof. By the definition of IBP, there exists an information type whose information set expands. Assume without loss of generality that type (1, 1) are those players with expanded information sets. To reach a contradiction, assume that C(1,1)(˜x) > C(1,1)(x) where x and ˜x are the ICUEs reached before and after the information set of type (1, 1) is expanded respectively. Since each player's relevant network is a circuit, the possible paths are divided into the two directions that one can travel around the circuit. By Proposition 1, there is only a single edge that can connect any two nodes, so each population must have two linearly independent paths available to them. Player type (1, 1) with restricted information set has only one possible path before expansion and player type (1, 2) has two paths available to them: S(1,1) = {sa} and S(1,2) = {sa, sb}. For any two distinct i, j ∈ N, either Ei ∩ Ej = ∅ or Ei ∩ Ej = C. If E1 ∩ Ej = ∅, then we do not need to consider population j as it will not affect the equilibrium costs of (1, 1). So assume that for all j ∈ N we have E1 ∩ Ej = C. Now suppose that type kj ∈ Kj only has one choice of path. Then we can consider an equivalent game where the costs of resources e ∈ E(j,kj) are increased to ce(fe(x) + djkj ). Hence, we can assume that for any j ∈ N\{1}, there exists only one information type (j, 2) where each player has full information about relevant resources. If (1, 1) does not choose sb after the information set expansion, then the ICUE remains unchanged and we are done. Therefore, ˜xsb 11 > 0 and ˜xsa 11 < xsa 11 = d11. Suppose that ∑e∈sa fe(˜x) ≤ ∑e∈sa fe(x). For ˜xsa 11 ≥ 0, then, following on from the definition of ICUE, we have ∑e∈sb ce(fe(˜x)) ≤ ∑e∈sa ce(fe(˜x)). Since ce is continuous and non-decreasing, we reach the following contradic- Hence, we have that ∑e∈sa fe(˜x) > ∑e∈sa fe(x).Now divide the player types into two sets as follows: A = {i ∈ N, j ∈ {1, 2} : Cij(˜x) > Cij(x)}; and B = {i ∈ N, j ∈ {1, 2} : Cij(˜x) ≤ Cij(x)}. By the contradiction assumption, A is nonempty and Proposition 3 tells us that B is nonempty. All possible paths between any two nodes from the irredundant network ˆG form the set S. Divide this into two distinct sets as SA = {s ∈ S : C(s, ˜x) > C(s, x)} and SB = {s ∈ S : C(s, ˜x) ≤ C(s, x)}. Consequently, we must have that maxs∈SA {C(s, x) - C(s, ˜x)} < 0 and mins∈SB {C(s, x) - C(s, ˜x)} ≥ 0. Consider these two simple claims: Claim 1: If i ∈ A and s ∈ SB then xsi = 0. This immediately follows from definitions: by definition of SB, C(s, x) ≥ C(s, ˜x); by definition of ICUE, C(s, x) ≥ Ci(˜x); by definition of A, we must have Ci(˜x) > Ci(x). Hence, xsi = 0. Claim 2: If i ∈ B and s ∈ SA then ˜xsi = 0. Again, this follows from definitions: by definition of SB, C(s, ˜x) > C(s, x); by definition of ICUE, C(s, x) ≥ Ci(x); and finally, by definition of A, Ci(x) > Ci(˜x). Hence, ˜xsi = 0. For ease of notation, let demands for paths in SA and SB be dA = ∑s∈SA ∑i∈N xsi , ˜ dA = ∑s∈SA ∑i∈N ˜xsi , dB = ∑s∈SB ∑i∈N xsi and ˜ dB = ∑s∈SB ∑i∈N ˜xsi . It follows from Claims 1 and 2 that we have ˜ dA ≤ dA and ˜ dB ≥ dB. Since A and B are nonempty, it also follows that both SA and SB are nonempty. Claim 3: Let Sα, Sβ be any nonempty partition of S. If we have ˜ dα ≤ dα and ˜ dβ ≥ dβ, then We will prove Claim 3 by induction on the number of edges and the number of populations. The base case is a circuit with three edges and one population. All possible paths of the network are S = {e1, e2, e3, e1e2, e1e3, e2e3}. Let the population's strategy set be S = {e1e2, e3}, and their information set before expansion be E = {e1, e2}. This two-terminal game is SLI, so by Theorem 2, it is immune to IBP. For any s ∈ S such that s /∈ S, s contributes no demand to dα, ˜ dα, dβ or ˜ dβ, hence, any such s can be randomly assigned to one of the sets Sα and Sα. Since e1e2 ∈ E, the demand for this strategy can only reduce after the information expansion, e1e2 ∈ Sα. The demand for e3 can only increase after the information expansion, e3 ∈ Sβ. Since there is no IBP, we must have If C(e1e2, ˜x) ≤ C(e3, ˜x) then C(e1e2, x) - C(e1e2, ˜x) ≥ 0. If C(e1e2, ˜x) ≥ C(e3, ˜x), then C(e3, x) ≤ C(e3, ˜x) as fe3 (x) < fe3 (˜x). Hence, maxs∈Sα {C(s, x) - C(s, ˜x)} ≥ mins∈Sβ {C(s, x) - C(s, ˜x)}. Now consider a subdivision of this circuit. The same reasoning holds, hence, it is true for a circuit with any number of edges. Now we assume that Claim 3 is true for n - 1 populations on a circuit with an arbitrary number of edges and we will show how the addition of another population will not affect this property. WLOG, consider player type (1, 1) with strategy sets S11 = {sα} and ˜ S11 = {sα, sβ}. If ∀s ∈ S such that s /∈ S11 ∪ ... ∪ Sn2, then s contributes no demand to dα, ˜ dα, dβ or ˜ dβ. Hence, can be arbitrarily assigned to one of the sets Sα and Sβ. We can assume C(sα, x) ≥ C(sβ, x) since otherwise C(s, x) - C(s, ˜x) = 0 ∀s ∈ S and Claim 3 is immediately true. Hence, we know that the demand for sα will strictly reduce, and the demand for sβ will strictly increase. For any i ∈ N\{1}, their strategy set is Si = {sαi, sβi}. It must be the case that ∀i ∈ N\{1} if demand for sαi increases, the demand for sβi must reduce. Suppose that ∃i ∈ N\{1} such that the demands for sαi, sβi remain the same, then we can form an equivalent game of n - 1 populations, for which we assumed the claim to be true. Therefore, in each population, we must have a strict increase in demand for one strategy and strict decrease for the other. Since we assumed ˜ dα ≤ dα, ˜ dβ ≥ dβ, and that both Sα and Sβ are nonempty, in every possible allocation of strategies to Sα and Sβ there exists i ∈ N such that exactly one strategy of Si belongs to Sα. Hence, there always exists a population i ∈ N whose strategies belong in both Sα and Sβ. Without loss of generality, let the demand for sαi increase and belong to Sα and demand for sβi reduce and belong to Sβ. Then we must have that Ci(sαi, ˜x) ≤ Ci(sβi, ˜x) and Ci(sαi, x) ≥ Ci(sβi, x). Therefore we have Ci(sαi, x) - Ci(sαi, ˜x) ≥ Ci(sβi, x) - Ci(sβi, ˜x). This concludes the induction step and so we have proved Claim 3. Figure 4: A stadium is a ring, hence a circuit. ![Image](https://ijcai.org/proceedings/2019/fulltext/80/image_000003_2af329a3da59f2895b83a868e47d3d6ba770f051c2a70281e419da00f3928b93.png) Finally, with the partition of SA and SB and the claims, we reach the following contradiction: An interesting application of this theorem is considering pedestrian exit-routing in sports stadiums, such as in Figure 4. Divide player populations as those who are seated in the same block and wish to use the same mode of transport. Knowledge of the layout can differ between people and can be distributed through signs or movement restrictions provided by the stadium. If pedestrians are only allowed to exit their seat block through a single exit, as in Figure 4, then the overlapping network of all populations is a ring. Hence, information cannot harm the expected travel times of exiting the stadium. However, if visitors are allowed to walk between seat blocks before exiting the stadium the network no longer has immunity to IBP. These results, therefore, have useful implications for planning purposes e.g., evacuation routes. ## 4 IBP for Social Cost Thus far, we defined IBP to be the comparison between equilibrium costs of a player whose information set is expanded. A natural weakness of using IBP to analyse the system as a whole is that it does not incorporate any effects that the information expansion has on all players. From a mechanism design perspective, it is also relevant to compare the social costs of the ICUEs. In this section, we define our own version of the IBP, which is measured against social cost, and show that its occurrence is independent of network topology. Define Informational Braess' Paradox for Social Cost (IBPSC) as the case when one type of player has their information set strictly expanded which causes an increase to the social cost, defined as the sum of all agents' disutilities. IBP is a special case of IBPSC that occurs when information harms the informed player. In order to consider how the social cost will change in an ICUE equilibrium, we need the following lemma for the simplest circuit network - two-node, two-edge ring. Lemma 1. Any two-terminal network with at least two distinct paths has the 2-edge ring embedded in it. We can now prove IBPSC can occur on any two-terminal network. Theorem 4. For any two-terminal network there exists (Ki)i∈N and (ce)e∈E such that IBPSC occurs. To prove this, it suffices to show that there always exists an assignment of information sets and cost functions on the 2-edge ring such that IBPSC exists. This is left as a simple exercise to the interested reader. The occurrence of IBPSC is independent of the topology of the network due to inefficiencies. Through the assignment of information sets, an ICUE outcome can be found with a cost strictly less than any UE. Any ICUE that is not a UE must, therefore, be unstable, as at least one player wishes to deviate from it if they have their information set expanded. Hence, there will always exist an assignment of information sets for any network where the social cost expands as information sets expand. Theorem 5. No network is immune to IBPSC. This result extends from the two-terminal case, implying there is further research needed to understand the impact of information distribution. ## 5 Conclusion We have analysed nonatomic congestion games where multiple populations of individuals have incomplete knowledge of the network structure, studying how the distribution of information affects utility. Specifically, we have identified a natural class of networks, i.e., rings, that are immune to performance deterioration for the agents acquiring new information, known as Informational Braess' Paradox, settling a conjecture in [Acemoglu et al., 2018]. We have also shown that under an alternative definition of performance, analogous to Braess' Paradox, no network has immunity. Potential future directions include the characterisation of all immune structures, the extension of the analysis to atomic congestion games and the connection to games with unawareness. We believe that the identification of safe network structure is bound to fundamentally impact the design of transportation networks; aiding decongestion of ring roads and pedestrian evacuation in stadia. ## References 1. [Acemoglu et al., 2018] Daron Acemoglu, Ali Makhdoumi, Azarakhsh Malekian, and Asu Ozdaglar. Informational braess' paradox: The effect of information on traffic con- gestion. Operations Research, 66(4):893-917, 2018. 2. [Arnott et al., 1991] Richard Arnott, Andre De Palma, and Robin Lindsey. Does providing information to drivers re- duce traffic congestion? Transportation Research Part A: General, 25(5):309-318, 1991. 3. [Beier et al., 2004] René Beier, Artur Czumaj, Piotr Krysta, and Berthold Vöcking. Computing equilibria for conges- tion games with (im)perfect information. In SODA, pages 746-755. SIAM, 2004. 4. [Braess, 1968] Dietrich Braess. Uber ein paradoxon aus der verkehrsplanung. Unternehmensforschung, 12(1):258- 268, 1968. 5. [Chen et al., 2015] Xujin Chen, Zhuo Diao, and Xiaodong Hu. Excluding braess's paradox in nonatomic selfish rout- ing. International Symposium on Algorithmic Game The- ory, pages 309-318, 2015. 6. [Cole et al., 2018] Richard Cole, Thanasis Lianeas, and Ev- dokia Nikolova. When does diversity of agent preferences improve outcomes in selfish routing? IJCAI, pages 173- 179, 2018. 7. [Epstein et al., 2009] Amir Epstein, Michal Feldman, and Yishay Mansour. Efficient graph topologies in network routing games. Games and Economic Behavior, 66, 2009. 8. [Fisk, 1980] Caroline Fisk. Some developments in equilib- rium traffic assignment. Transportation Research Part B: Methodological, 14(3):243-255, 1980. 9. [Fujishige et al., 2017] Satoru Fujishige, Michel X. Goe- mans, Tobias Harsk, Britta Peis, and Rico Zenklusen. Ma- troids are immune to braess' paradox. Mathematics of Op- erations Research, 42(3):745-761, 2017. 10. [Liu et al., 2016] Jeffrey Liu, Saurabh Amin, and Galina Schwartz. Effects of information heterogeneity in bayesian routing games. 2016. 11. [Meir and Parkes, 2015] Reshef Meir and David C. Parkes. Congestion games with distance-based strict uncertainty. AAAI, pages 986-992, 2015. 12. [Milchtaich, 1996] Igal Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13(1):111-124, 1996. 13. [Milchtaich, 2006] Igal Milchtaich. Network topology and the efficiency of equilibrium. Games and Economic Be- havior, 57(2):321-346, 2006. 14. [Murchland, 1970] John D. Murchland. Braess's paradox of traffic flow. Transportation Research, 4(4):391-394, 1970. 15. [Orda et al., 1993] Ariel Orda, Raphael Rom, and Nahum Shimkin. Competitive routing in multiuse communica- tion networks. IEEE/ACM Transactions on Networking, 1(5):510-521, 1993. 16. [Pas and Principio, 1997] Eric I. Pas and Shari L. Principio. Braess' paradox: Some new insights. Transportation Re- search Part B: Methodological, 31(3):265-276, 1997. 17. [Roughgarden, 2004] Tim Roughgarden. Stackelberg scheduling strategies. SIAM journal on computing, 33(2):332-350, 2004. 18. [Roughgarden, 2005] Tim Roughgarden. Selfish Routing and the Price of Anarchy. The MIT Press, 2005. 19. [Sekar et al., 2018] Shreyas Sekar, Liyuan Zheng, Lillian J. Ratliff, and Baosen Zhang. Uncertainty in multi- commodity routing networks: When does it help? Annual American Control Conference (ACC), pages 6553-6558, 2018. 20. [Wardrop, 1952] John Glen Wardrop. Some theoretical as- pects of road traffic research. Inst Civil Engineers Proc, 1:325-378, 1952. 21. [Yaïche et al., 2000] Haïkel Yaïche, Ravi R. Mazumdar, and Catherine Rosenberg. A game theoretic framework for bandwidth allocation and pricing in broadband networks. IEEE/ACM Transactions on Networking, 8(5):667-678, 2000. 22. [Yao et al., 2018] Jia Yao, Zhanhong Cheng, Jingtong Dai, Anthony Chen, and Shi An. Traffic assignment paradox incorporating congestion and stochastic perceived error simultaneously. Transportmetrica A: Transport Science, 2018. 23. [Zhao et al., 2014] Chunxue Zhao, Baibai Fu, and Tianming Wang. Braess paradox and robustness of traffic networks under stochastic user equilibrium. Transportation Re- search Part E, 61:135-141, 2014.