Paper deep dive
Deriving the Pure Price of Anarchy for Networked Resource Allocation Games
Vartika Singh, Philip N. Brown
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 9/16/2026, 7:20:59 AM
Summary
This paper addresses the problem of optimal utility design in multi-agent resource allocation games with arbitrary information networks. The authors develop a linear program to derive the pure Price of Anarchy (pPoA) for any system objective and information network. Key findings include proving that for supermodular objectives, a fully communication-denied marginal contribution utility is optimal regardless of the network structure. For submodular objectives, the design is shown to be robust to communication failures. Specifically, for weighted maximum coverage (set cover) games, the marginal contribution utility design provably optimizes the pPoA, achieving a value of 1/2 under various network conditions, including those with blind, isolated, and normal agents.
Entities (11)
Relation Signals (8)
Vartika Singh → authored → Deriving the Pure Price of Anarchy for Networked Resource Allocation Games
confidence 99% · Deriving the Pure Price of Anarchy for Networked Resource Allocation Games Vartika Singh Philip N. Brown
Philip N. Brown → authored → Deriving the Pure Price of Anarchy for Networked Resource Allocation Games
confidence 99% · Deriving the Pure Price of Anarchy for Networked Resource Allocation Games Vartika Singh Philip N. Brown
Linear Program → derives → Pure Price of Anarchy
confidence 95% · We develop a linear program that derives the optimal pPoA for any arbitrary information network and arbitrary system objective.
Communication-Denied Utility → appliesto → Supermodular Objective Functions
confidence 94% · For supermodular objective functions, we prove that counterintuitively, a fully communication-denied utility design is optimal irrespective of the original information network.
Communication-Denied Utility → optimizes → Pure Price of Anarchy
confidence 94% · For supermodular objective functions, we prove that counterintuitively, a fully communication-denied utility design is optimal irrespective of the original information network.
Marginal Contribution Utility → appliesto → Weighted Maximum Coverage
confidence 93% · When the system objective is weighted maximum coverage, the marginal contribution utility design provably optimizes the pPoA for a wide variety of information networks of interest.
Marginal Contribution Utility → →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:This work considers multi-agent coordination with arbitrary information networks among the agents using a game-theoretic approach. A system designer aims to assign local utility functions to the agents to guide their actions toward a desired system objective. The performance of the assigned local utilities is measured by the well known pure price of anarchy (pPoA) metric that equals the ratio of the system objective at the worst pure Nash equilibrium of the corresponding game to the optimal system objective. Our aim is to derive the utility functions which optimize the pPoA-based performance guarantees for any given information network and system objective. We develop a linear program that derives the optimal pPoA for any arbitrary information network and arbitrary system objective. Our work is the first to solve optimal utility design for arbitrary networks; our techniques generalize previous approaches which considered only the full-information setting. For supermodular objective functions, we prove that counterintuitively, a fully communication-denied utility design is optimal irrespective of the original information network. For submodular system objectives, an exhaustive numerical analysis suggests that the optimal utility design is robust to communication failures even for this case. When the system objective is weighted maximum coverage, the marginal contribution utility design provably optimizes the pPoA for a wide variety of information networks of interest.
Tags
Links
- Source: https://arxiv.org/abs/2609.12077v1
- Canonical: https://arxiv.org/abs/2609.12077v1
Trouble viewing inline? Open PDF directly →
Full Text
107,890 characters extracted from source content.
Expand or collapse full text
Deriving the Pure Price of Anarchy for Networked Resource Allocation Games Vartika Singh Philip N. Brown †thanks: This material is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-23-1-0171, the Army Research Office under grant number W911NF-25-1-0239, and the National Science Foundation under grant number ECCS-2440836.†thanks: Vartika Singh conducted this research while with the University of Colorado Colorado Springs, Colorado Springs, CO, 80918 USA (email: singh.vsvartika@gmail.com). †thanks: Philip N. Brown is with the University of Colorado Colorado Springs, Colorado Springs, CO, 80918 USA (email: pbrown2@uccs.edu). He performed this research while a Visiting Professor at Politecnico di Torino, Italy. Abstract This work considers multi-agent coordination with arbitrary information networks among the agents using a game-theoretic approach. A system designer aims to assign local utility functions to the agents to guide their actions toward a desired system objective. The performance of the assigned local utilities is measured by the well known pure price of anarchy (pPoA) metric that equals the ratio of the system objective at the worst pure Nash equilibrium of the corresponding game to the optimal system objective. Our aim is to derive the utility functions which optimize the pPoA-based performance guarantees for any given information network and system objective. We develop a linear program that derives the optimal pPoA for any arbitrary information network and arbitrary system objective. Our work is the first to solve optimal utility design for arbitrary networks; our techniques generalize previous approaches which considered only the full-information setting. For supermodular objective functions, we prove that counterintuitively, a fully communication-denied utility design is optimal irrespective of the original information network. For submodular system objectives, an exhaustive numerical analysis suggests that the optimal utility design is robust to communication failures even for this case. When the system objective is weighted maximum coverage, the marginal contribution utility design provably optimizes the pPoA for a wide variety of information networks of interest. Index Terms: Network Games, PoA, Resource Allocation. I Introduction With applications in air traffic control [1, 2], robotic networks [3, 4], airport security [5], transportation networks [6] and medical sciences [7, 8] etc, multi-agent coordination has emerged as a topic of interest among researchers. Coordinating agents in a centralized manner can be expensive or even infeasible; thus, a game-theoretic approach for distributed control has become a natural solution technique [9, 10, 11, 12, 14, 13]. In the game-theoretic approach, a system designer endows every agent with a local utility function to guide their actions. The utility functions are selected so that the induced game’s Nash equilibria achieve a favorable system objective value. The designer then assigns agents an appropriate distributed algorithm to ensure they converge to a Nash equilibrium [15]. Then, the performance of the assigned utility functions is measured by the price of anarchy (PoA) metric which equals the ratio of the system objective at the worst performing equilibrium to that at the optimal [16]. The system designer aims to assign utility functions to the agents to induce the optimal price of anarchy. The coordination problem becomes more challenging when some agents lose access to information regarding the actions of other agents. This could be due to constraints on information sharing, or a communication failure, or due to jamming by an adversary. Thus, the system designer must consider information networks while designing the utilities of the agents. The existing literature considers such information networks among the agents and provides lower and upper bounds on the optimal PoA [18, 19, 20, 21, 17]. However, most of the literature is focused on specific submodular system objective functions and specific utility functions, and lacks a methodology to derive the utility functions that optimize the PoA for general system objectives and general information networks. On the other hand, the literature that considers general system objectives [9, 10] focuses solely on full information networks where all agents can observe the actions of all other agents; i.e., the possibility of arbitrary information networks among the agents is not considered. We aim to address this gap and build upon the framework of [9] to include the information networks. In [9], the authors derive the optimal PoA for general system objectives by solving a linear program (LP) for a complete network. In the present paper, we focus our attention on the subproblem of optimizing pure Nash equilibria; thus, we state all of our results in terms of the PoA defined in pure strategies known as the pure price of anarchy (pPoA). We develop an LP that derives the optimal pPoA for any general system objective and also any arbitrary information network. Our models combine the anonymous separable resource allocation games of [9] with the information network parameterization of [17] to allow for substantial modeling expressiveness. The combination of these allows for modeling quite general settings, including facility location, target assignment, sensor coverage, and network interdiction problems as described in [11, 12, 22]. Our main contributions are as follows: (i) a linear program deriving the optimal pPoA for any system objective and information network; (i) we prove that when the system objective is supermodular, the fully communication-denied marginal contribution utility is optimal regardless of the underlying information network; (i) the optimal pPoA is at most 1/21/2 for set cover games if there is any communication failure; (iv) the well-known marginal contribution utility design is optimal for a set cover game with a network of blind, isolated and normal agents; (v) if the information graph among the agents is such that each pair of agent has at least one agent able to observe the other, the marginal contribution leads to pPoA of 1/21/2 for set cover games. This work also contributes to the bounds in the existing literature. For example, for a set cover game with a blind, an isolated and two normal agents, [17] provides a lower bound of 1/6, [19] provides a lower bound of 1/2, and [20] provides an upper-bound of 1/2 for optimal price of anarchy. This work directly proves the optimal price of anarchy equals 1/2 for such a network. Further, to the best of our knowledge, the literature contains no bounds for the optimal price of anarchy for supermodular games with arbitrary information networks. This work provides the closed form expression for optimal PoA for such games, completely independent of the network. We also consider the robustness of the pPoA-optimizing utility design to unanticipated communication failures. For supermodular system objectives, the optimal utility design for the full information case is proved to be optimal even when a communication failure leading to arbitrary information network occurs. For submodular games, we numerically show that optimal utility functions for the full-information case perform near optimally even after a communication failure happens. Further, the numerical examples also seem to indicate that the optimal pPoA is monotone with respect to the connectedness of the information network. I Problem Description Let ℛ=r1,…,rm R=\r_1,…,r_m\ be a finite set of resources where every resource r∈ℛr∈ R is associated with a value vr≥0v_r≥ 0. Let N=1,…,nN=\1,…,n\ be a finite set of agents. Each agent i∈Ni∈ N has action set i⊆2ℛ A_i 2 R; the set of resources selected by agent i is written ai∈ia_i∈ A_i. The welfare generated at a resource r depends on vrv_r and the number of agents selecting r. Let :=1×⋯×n A:= A_1×…× A_n denote the set of action profiles of the agents. For =(a1,…,an)∈ a=(a_1,…,a_n)∈ A, define ||r| a|_r to be the number of agents selecting resource r in action profile a. Then the total welfare generated under action profile a, W:→ℝW: A is given by W() W( a) = = ∑r∈∪iaivrw(||r), _r∈ _ia_iv_rw(| a|_r), (1) where basis function w(||r)>0w(| a|_r)>0 scales the value of a resource r depending on the number of agents selecting it. We make the following standing assumptions: A.1 The system objective is W()>0W( a)>0 for some ∈ a∈ A. A.2 The basis function w(0)=0w(0)=0 and w(j)>0w(j)>0 for j>0j>0. The aim of the system designer is to assign local utility functions to the agents that guide their actions towards an action profile that maximizes the system objective (1). If assumption A.1 is not true for some problem, then all the action profiles lead to the system objective value of zero irrespective of utility functions chosen by system designer, thus A.1 is justified. Prior work [9] has observed that if w(j)=0w(j)=0 for j>0j>0, the resulting PoA is 0; hence the restriction of assumption A.2. Without loss of generality, we scale w(1)=1w(1)=1 throughout the paper. This framework to model a resource allocation problem is considered in [9], which we generalize to consider general information networks among the agents in this work. I-A Local Utilities and Utility Generating Mechanism In contrast to prior work [9], we consider general information networks, where the information available to the agents can be described using an information graph ℳ:=(ℳ1,…,ℳn) M:=( M_1,…, M_n), where ℳi⊆N M_i N is the set of agents whose actions agent i can observe (naturally, i∈ℳi∈ M_i). Whereas in [9], a full information network is considered with ℳi=N M_i=N for all i∈Ni∈ N. Let [p][p] represent the set 1,…,p\1,…,p\ for any positive integer p and 0,[p]\0,[p]\ represent 0,1,…,p\0,1,…,p\. Since the agents can observe a subset of agents, we modify the local utilities defined in [9] to cater to this. Let ||rℳi| a| M_i_r be the number of agents in ℳi M_i that select resource r in action profile a. Let fi:[n]→ℝf_i:[n] be a utility generating mechanism chosen by the system designer (for agent i) that scales the perceived value of a resource if it is chosen by ||rℳi| a| M_i_r number of agents with assumption f(0)=0f(0)=0. Then, the local utility functions can be defined as, Ui() U_i( a) = = ∑r∈aivrfi(||rℳi), for i∈N. _r∈ a_iv_rf_i(| a| M_i_r), 14.22636pt for i∈ N. (2) In [9], the system designer always chooses the same utility generating mechanism f for all the agents, since all the agents have access to the same information i.e., fi=f_i=f for all i∈Ni∈ N. However, in our work, the system designer can choose different utility generating mechanisms for different agents in (2). Three well-known examples of local utility functions and corresponding utility generating mechanisms are as follows [10, 19]. I-A1 Marginal Contribution Utility In this mechanism, the utility of an agent equals the marginal gain in the system objective when that player participates. That is, the utility of agent i at action profile a equals Ui() U_i( a) = = ∑r∈aivr[w(||rℳi)−w(||rℳi−1)]. _r∈ a_iv_r[w(| a| M_i_r)-w(| a| M_i_r-1)]. The above utility is obtained by utility generating mechanism fimcf^mc_i defined as fimc(x)=w(x)−w(x−1) for x∈[|ℳi|] and fimc(0)=0.f mc_i(x)=w(x)-w(x-1) for x∈[| M_i|] and f mc_i(0)=0. (3) I-A2 Equal Share Utility The well-known equal share utility for an agent i in action profile a equals Ui() U_i( a) = = ∑r∈aivrw(||rℳi)||rℳi. _r∈ a_iv_r w(| a| M_i_r)| a| M_i_r. Such a utility is obtained by utility generating mechanism fiesf es_i defined as fies(x)=w(x)x for x∈[|ℳi|] and fies(0)=0.f es_i(x)= w(x)x for x∈[| M_i|] and f es_i(0)=0. (4) I-A3 Communication-Denied Utility The communication-denied (called “blind” in [19]) utility for an agent i in action profile a equals Ui() U_i( a) = = ∑r∈aivr. _r∈ a_iv_r. Such a utility is obtained by utility generating mechanism ficdf cd_i defined as ficd(x)=1 for x≥1 and ficd(0)=0.f cd_i(x)=1 for x≥ 1 and f cd_i(0)=0. (5) I-B Resulting Class of Games and Solution Once the system designer chooses a utility generating mechanism fii∈N\f_i\_i∈ N, this induces a game among the agents defined by G=⟨ℛ,w,N,ii∈N,ℳ,fii∈N⟩G= R,w,N,\ A_i\_i∈ N, M,\f_i\_i∈ N . This work focuses on the solution concept of pure strategy Nash equilibrium (PNE) for any G, defined as follows. For any a, let (a~i,a−i)( a_i,a_-i) represent the action profile where agent i unilaterally deviates to a~i a_i from aia_i. Then PNE is defined as Definition 1 (Pure Strategy Nash Equilibrium) For any G, an action profile a is a pure strategy Nash equilibrium if Ui()≥Ui(a~i,a−i)U_i( a)≥ U_i( a_i,a_-i) for all a~i∈i a_i∈ A_i and all i∈Ni∈ N. The utility design literature has broadly adopted PNE as a solution concept of interest, due to the fact that in many relevant classes of games, games are guaranteed to possess a PNE and simple learning distributed dynamics are guaranteed to converge to a PNE [25, 22, 9]. Thus, establishing bounds on the performance of pure Nash equilibria is of interest to the system designer since such a bound serves as an algorithmic approximation ratio for an entire class of distributed algorithms. In the context of this paper, it is important to note that the existence of PNE is dependent on a combination of the utility generating mechanism and the specific information network; there are combinations of network and utility generating mechanism such that some game instances do not possess a PNE. Nonetheless, as we will discuss, many meaningful results can still be shown by focusing solely on PNE. Thus, for the remainder of the paper we restrict our attention only to the games that have at least one pure strategy Nash equilibrium. The specific ramifications of this restriction will be discussed where applicable; in some cases, we will even show that this restriction is actually made without loss of generality. Let aopta opt denote an optimal action profile. The aim of the system designer is to choose utility generating mechanisms fii∈N\f_i\_i∈ N such that W(aNE)W(a NE) is ‘close’ to W(aopt)W(a opt) for all PNE, aNEa NE, of the resulting game. In general, the exact resource set ℛ R and exact action sets of the agents ii∈N\ A_i\_i∈ N may not be known at design-time. The system designer may only know the basis function w(⋅)w(·) and information graph ℳ M, and choose mechanism fii∈N\f_i\_i∈ N based on this information. Thus it is important to derive the performance guarantee of fii∈N\f_i\_i∈ N for all possible games. For any w and ℳ M, the system designer chooses fii∈N\f_i\_i∈ N which leads to a class of games fi,wℳ G_\f_i\,w M that have G.1 n agents, any possible ℛ R, any possible ii∈N\ A_i\_i∈ N, G.2 system objective W(⋅)W(·) defined in (1) with w(⋅)w(·) as the basis function, G.3 local utilities as in (2) with fii∈N\f_i\_i∈ N as utility generating mechanism and ℳ M as the information graph. G.4 at least one PNE. Then, the performance of f can be measured using the Price of Anarchy (PoA) metric (see [16]), defined as pPoA(fi,w,ℳ)=infG∈fi,wℳ(min∈PNE(G)W()max∈W()), pPoA(\f_i\,w, M)= _G∈ G_\f_i\,w M ( _ a∈ PNE(G)W( a) _ a∈ AW( a) ), (6) where PNE(G) PNE(G) is the set of all PNE of G∈fi,wℳG∈ G_\f_i\,w M11 1 Here, for any game G which possesses no PNE (i.e., PNE(G)=∅ PNE(G)= ), we define the ratio in (6) to be 1. However, note that fi,wℳ G_\f_i\,w M trivially always possesses at least one game G such that PNE(G)≠∅ PNE(G)≠ , so (6) is always well-defined. In order to derive the performance guarantee of fii∈N\f_i\_i∈ N, we will define a linear program which will also turn out to be instrumental in deriving the utility generating mechanism fiopti∈N\f^opt_i\_i∈ N that will result in optimal performance. The next section presents the required structure which facilitates this. Remark: This work considers the resource allocation problem considered in [9] and extends the problem to general information networks among the agents. The introduction of general information networks makes the resource allocation problem widely applicable in presence of possible communication failures, constrained information sharing, and other applications. Fig. 1: A general network (a) and corresponding classes (b). All the agents can see the actions of all other agents except agent 44 who can not observe the actions of agent 55. Thus, the information available to various agents equals ℳi=1,2,3,4,5 M_i=\1,2,3,4,5\ for i=1,2,3,5i=1,2,3,5 and ℳ4=1,2,3,4 M_4=\1,2,3,4\. Agents 11, 22 and 33 observe the same set of agents and are observed by the same set of agents, hence belong to the same class 1 C_1. Agent 55 also observes the same set of agents but cannot be observed by agent 44, thus belongs to class 2 C_2. Agent 44 belongs to class 3 C_3. Then 1=2=1,2,3 N_1= N_2=\ C_1, C_2, C_3\ and 3=1,4 N_3=\ C_1, C_4\, and C.1-C.3 are satisfied. I-C Information Graph and Classes One can utilize the given information graph ℳ M to partition the set of agents to classes of agents with ‘similar attributes’. We say two agents i and i~ i are similar if (i) they can observe the same set of agents, that is, ℳi=ℳi~ M_i= M_ i, and (i) if they can be observed by the same set of agents, that is, ℳi′:i∈ℳi′,i′∈N=ℳi′:i~∈ℳi′,i′∈N\ M_i :i∈ M_i ,\ i ∈ N\=\ M_i : i∈ M_i ,\ i ∈ N\. The motivation behind such a partition stems from the fact that similar agents affect the game in a similar manner; thus, the system designer can assign them the same local utility functions. Let j C_j represent a class of similar agents and j N_j be the set of agents whose actions agents in class j C_j can observe (see Figure 1). A partition of N such that similar agents are assigned to the same class is accomplished by creating classes where C.1 every agent is assigned to exactly one class, C.2 every agent in class j C_j observes every other agent in j C_j, C.3 every agent in j C_j observes every agent in classes j N_j given by m(j):m(j)∈j\ C_m(j):m(j)∈ O_j\ where j⊆[k] O_j [k]. Observe that C.2 along with C.3 implies that ℳi=ℳi′ M_i= M_i for i,i′∈ji,i ∈ C_j. Further, C.3 also implies that all the agents in a class are observed by the same set of agents.22 2 It is important to note that the partitioning of any network according to C.1-C.3 is not restrictive. Indeed, any network can be partitioned by making singleton classes i=i C_i=\i\ for i∈Ni∈ N. Then, any network can be completely specified using (,)( C, N) where =1,…k C=\ C_1,… C_k\ is the set of classes of agents for some k≤nk≤ n, and =1,…,k N=\ N_1,…, N_k\ represents the information available to various classes. Thus from here onward we refer to (,)( C, N) as the information network. Throughout the paper, i∈Ni∈ N represents an agent, j C_j represents a class with j∈[k]j∈[k] where k represents the number of classes in the network (,)( C, N). I-D Pure Price of Anarchy for Network (,)( C, N) For any information network (,)( C, N), all the agents in any class j C_j are similar hence the system designer can assign them the same utility generating mechanism. Let κj _j represent the number of agents in class j C_j. Let sj=∑l∈[k]κll∈js_j= _l∈[k] _l 1_\ C_l∈ N_j\ be the total number of agents that any i∈ji∈ C_j can observe (note that sj=|ℳi|s_j=| M_i| for all i∈ji∈ C_j). Then we use fj:[sj]→ℝf_j:[s_j] to represent the utility generating mechanism for class j C_j for any j∈[k]j∈[k], that is, for all i∈ji∈ C_j the utility generating mechanism fi=fjf_i=f_j. Let ||rj| a| N_j_r be the number of agents in j N_j selecting resource r in action profile a. Then, the utility of an agent i∈ji∈ C_j defined in (2) modifies to Ui(ai,a−i) U_i(a_i,a_-i) = = ∑r∈aivrfj(||rj). _r∈ a_iv_rf_j(| a| N_j_r). (7) When the system designer chooses a set of utility generating mechanisms represented by f=fjj∈[k]f=\f_j\_j∈[k] for a given network (,)( C, N) and basis function w, this defines a class of games f,w(,) G_f,w^( C, N) that satisfy G.1−G.2G.1-G.2, and have G.5 local utilities given by (7) with fjj∈[k]\f_j\_j∈[k] as utility generating mechanism and (,)( C, N) as the network, where =1,…,k C=\ C_1,…, C_k\ and =1,…,k N=\ N_1,…, N_k\ for k≤nk≤ n. The performance of f for the information network (,)( C, N) with basis function w and utility generating mechanism f can be measured by modifying the pPoA (6) to the following:33 3 As in (6), for any game G which possesses no PNE (i.e., PNE(G)=∅ PNE(G)= ), we define the ratio in (8) to be 1. However, note that f,w(,) G_f,w^( C, N) trivially always possesses at least one game G such that PNE(G)≠∅ PNE(G)≠ , so (8) is always well-defined. pPoA(f,w,,)=infG∈f,w(,)(min∈PNE(G)W()max∈W()). pPoA(f,w, C, N)= _G∈ G_f,w^( C, N) ( _ a∈ PNE(G)W( a) _ a∈ AW( a) ). (8) The authors in [9] provide a linear program that characterizes the pPoA for any utility generating mechanism for the full information case; this can be viewed as a special case of our problem with information network (,)( C, N) where =1 C=\ C_1\, 1=1 N_1= C_1 and 1=N C_1=N. Further, they provide another linear program that derives the optimal utility generating mechanism, again only for the full information case, and requiring all agents to have the same utility generating mechanism. In this work, we aim to derive a linear program that caters to general information networks and solves (8). I Supermodular Games We first consider the resource allocation games where the system objective is supermodular and non-decreasing[9]. A supermodular objective function is achieved by non-decreasing and convex basis function w(⋅)w(·). That is, we assume that the basis function w(⋅)w(·) satisfies the following: w(j+1) w(j+1) ≥ ≥ w(j) with w(0)=0 and w(j) with w(0)=0 and (9) w(j+1)−w(j) w(j+1)-w(j) ≥ ≥ w(j)−w(j−1) for all j∈[n−1]. w(j)-w(j-1) for all j∈[n-1]. The first main result presented in Theorem 1 derives the pPoA for supermodular games with arbitrary information networks. Authors in [10] provide a similar result for the special case where all the agents belong to one class, =1 C= C_1 and 1=1 N_1= C_1; in other words, all the agents can observe the actions of all the other agents. Theorem 1 (proof in Appendix B) extends that result to any arbitrary information network. Theorem 1 For any supermodular game with n agents, information network (,)( C, N), and basis function w(⋅)w(·) satisfying (9), (i) For any f, the pure price of anarchy satisfies pPoA(f,w,,)≤nw(n). pPoA(f,w, C, N)≤ nw(n). (10) (i) The communication-denied utility mechanism fcd:=fjcdj∈[k]f cd:=\f cd_j\_j∈[k] as in (5) obtains the upper bound on PoA in (10). Note that the upper bound on pPoA for a resource allocation game with supermodular basis function does not depend upon the network structure. Further, the upper bound is achieved by communication-denied utility mechanism and any game is guaranteed to have a PNE under this utility mechanism. This makes communication-denied utility mechanism an optimal utility mechanism for supermodular games. The optimal pPoA does not change when one has a full information case, or arbitrary information network where some of the agents cannot observe the actions of some other agents. Further, because it preemptively severs communication, the communication-denied utility mechanism is optimal for any arbitrary information network (,)( C, N), and hence by construction it is robust against unanticipated communication failures among the agents. Note that the above theorem does not claim that the optimal utility generating mechanism is unique. Indeed, [10] proves that the equal share utility generating mechanism (4) is optimal for the full-information case; but interestingly it achieves the same pPoA bound as in our Theorem 1 in (10). Our result demonstrates the essential robustness of multiagent coordination in supermodular games. Note also that if network dynamics are sufficiently slow compared to agent action dynamics, this result essentially applies to dynamic networks as well. Remark 1 It is important to point out that Theorem 1’s restriction to the pure price of anarchy is without loss of generality: the upper bound in (10) applies to mixed Nash equilibria as well, and the communication-denied utility generating mechanism always results in games which are guaranteed to possess at least one pure Nash equilibrium (proved in [19]). IV Submodular Games Now we present the results on pure price of anarchy for another very important class of resource allocation problems, which have a non-decreasing and submodular objective function (e.g.,[19, 21]). Such an objective function is achieved by a non-decreasing and concave basis function. That is, the basis function w(⋅)w(·) satisfies the following: w(j+1) w(j+1) ≥ ≥ w(j) with w(0)=0 and w(j) with w(0)=0 and (11) w(j+1)−w(j) w(j+1)-w(j) ≤ ≤ w(j)−w(j−1) for all j∈[n−1]. w(j)-w(j-1) for all j∈[n-1]. For submodular games, a result analogous to Theorem 1 does not hold; the pure price of anarchy can depend upon the information network (,)( C, N) and basis function w under consideration. Thus, we provide the results for information networks that are commonly considered in the literature [19, 21], while the case of any arbitrary information networks (and arbitrary basis function) is deferred to Section V. Nonetheless, note that our theorems in this section give analytical results which apply to broad classes of information networks, rather than very specific fixed ones. IV-A Set Cover Games Consider the special class of submodular games widely known as set cover games [12], where the basis function w is defined as w(j)=1 for all j≥1 and w(0)=0.w(j)=1 for all j≥ 1 and w(0)=0. (12) Such a basis function implies that once a resource is selected by an agent, there is no gain in system objective if more agents select the same resource. IV-A1 A General Upper Bound on Networked Set Cover Games The next theorem (proof in Appendix B) provides an upper bound on the pure price of anarchy for set cover games for information networks where some agents can observe the actions of only a subset of agents. Theorem 2 Consider a set cover game with n agents, information network (,)( C, N), and basis function w(⋅)w(·) satisfying (12). If the information network is not full-information, i.e., there exist classes l∈ C_l∈ C and p∈ C_p∈ C such that p∉l C_p ∈ N_l, then pPoA(f,w,,) pPoA(f,w, C, N) ≤ ≤ 12. 12. (13) If the hypothesis of above theorem is not satisfied by a network (,)( C, N), that implies that all the agents can observe the actions chosen by all other agents leading to a full information network. For set cover games with full information, it is known that the optimal PoA is 1−1/e≈0.631-1/e≈ 0.63 [12]. However, our Theorem 2 implies that if there is even one agent whose actions can not be observed by some other agent, the pure price of anarchy immediately reduces to 12 12. This result implies that if there is a communication failure in a system leading to some agents not being able to observe the others, the PoA will always be less than half irrespective of the size of the network, number of agents in the system and the choice of utility generating mechanism. IV-A2 Set Cover Games with Blind and Isolated Agents An interesting case of information networks is the one with blind, isolated and normal agents. We borrow the terminology of blind and isolated agents from [19], and define these agents as follows: 1. Blind Agents: These are the agents who cannot observe anyone but themselves; however, they can be observed by other agents in the system. Formally, an agent i∈ji∈ C_j for some j∈[k]j∈[k] is blind if j=i C_j=\i\ and j=j N_j= C_j, and there exists some p∈[k]\jp∈[k] \j\ such that j∈p C_j∈ N_p. Let B⊆ C_B C represent the collection of classes of blind agents. 2. Isolated Agents: These agents cannot observe any other agents but themselves. Further, they cannot be observed by any other agents. Formally, an agent i∈ji∈ C_j for some j∈[k]j∈[k] is isolated if j=i C_j=\i\ and j=j N_j= C_j, and j∉p C_j ∈ N_p for any p∈[k]\jp∈[k] \j\. Let I⊆ C_I C represent the collection of classes of isolated agents. 3. Normal Agents: These are the agents who can observe all the agents except isolated agents. Formally, an agent i∈ji∈ C_j for some j∈[k]j∈[k] is normal if j=i:i∉B∪I C_j=\i:i ∈ C_B∪ C_I\, and j=j,B N_j=\ C_j, C_B\. For a network consisting of blind, isolated and normal agents, we have the following result (proof in Appendix B). Theorem 3 Consider a set cover game with information network (,)( C, N) such that there are κ1 _1 blind agents, κ2 _2 isolated agents and n−κn-κ normal agents where κ:=κ1+κ2>0κ:= _1+ _2>0 and with basis function w satisfying (12). Then, (i) The pure price of anarchy satisfies pPoA(f,w,,)≤max11+κ,1n. pPoA(f,w, C, N)≤ \ 11+κ, 1n \. (14) (i) If κ1>0 _1>0, the marginal contribution utility mechanism fmc:=fjmcj∈[k]f mc:=\f mc_j\_j∈[k] as in (3) obtains the bound in (14). (i) If κ1=0 _1=0, the marginal contribution utility mechanism fmcf mcas in (3) satisfies pPoA(fmc,w,,)=max12+κ,1n. pPoA(f mc,w, C, N)= \ 12+κ, 1n \. (15) For a network with blind, isolated and normal agents, the existence of PNE is guaranteed for any utility generating mechanism. By above theorem, for such a network with at least one blind agent, the marginal contribution utility emerges to be optimal utility generating mechanism leading to the price of anarchy in (14). In fact [19, Theorem 2] derives the PoA at marginal contribution for set cover games for the network with blind, isolated and normal agents, which matches with the PoA of (14) and (15) in respective cases. Thus, our present theorem completes the characterization from [19] by further proving that there is no other mechanism that can perform better than marginal contribution in set cover games with blind, isolated and normal agents. IV-A3 Set Cover Games with General Networks We now present a result that is applicable to a more general network, and depicts the robustness of the game-theoretic approach to the communication failure provided that a certain level of ‘connectedness’ in the information graph N is maintained (proof in Appendix B). Theorem 4 Consider a set cover game with w(⋅)w(·) as in (12) and an information network (,)( C, N) such that out of any two agents at least one observes the other but not all agents can see all other agent. In other words, for every j∈ C_j∈ C and l∈ C_l∈ C, either j∈l C_j∈ N_l or l∈j C_l∈ N_j or both. Further, there exist classes l∈ C_l∈ C and p∈ C_p∈ C such that p∉l C_p ∈ N_l. Then the marginal contribution utility mechanism fmc:=fjmcj∈[k]f mc:=\f mc_j\_j∈[k] obtains the PoA 12 12. From Theorem 2, the pure price of anarchy is at most half if there is even one class j C_j that cannot observe the actions of agents in another class l C_l. However, Theorem 4 implies that even if there are multiple pairs of classes j C_j and l C_l such that j C_j cannot observe the actions of agents in l C_l, as long as l C_l can observe the actions of agents in j C_j, then the pPoA under marginal contribution does not degrade any further and equals 1/21/2. Figure 2(a) presents an example of such a network with three classes. Fig. 2: A network with three classes such that for every j∈ C_j∈ C and l∈ C_l∈ C, either j∈l C_j∈ N_l or l∈j C_l∈ N_j (left). From Theorem 4, the PoA under marginal contribution for this network is 12 12 irrespective of the number of agents in any class. The right sub-figure has another network with three classes, such that 1=1 N_1=\ C_1\, 2=1,2 N_2=\ C_1, C_2\ and 3=3 N_3=\ C_3\. By Theorem 5, the pure PoA under marginal contribution satisfies 13≤pPoA(f,w,,)≤12 13≤ pPoA(f,w, C, N)≤ 12. The next theorem provides a result applicable to more general class of networks that do not have the same level of connectedness as in Theorem 4. Consider the isolated classes and blind classes as generalization of isolated and blind agents, where a group of agents loses the ability to observe the actions of other agents outside the group. A blind class is one that only observes its own class but is observed by some other class, an isolated class is the one that only observes its own class and furthermore is not observed by any other class, and a normal class is one that is neither blind nor isolated. Formally, j C_j is an isolated class if j=j N_j= C_j and j∉l C_j ∈ N_l for l≠jl≠ j, and j C_j is a blind class if j=j N_j= C_j and j∈l C_j∈ N_l for some l≠jl≠ j. For a network with blind and isolated classes, we have the following (proof in Appendix B): Theorem 5 Consider a set cover game with network (,)( C, N) with kik_i isolated, kbk_b blind and knk_n normal classes. Define k1:=ki+kbk_1:=k_i+k_b and note that k=||=ki+kb+knk=| C|=k_i+k_b+k_n. Then, (i) When kn<k_n<k the pure price of anarchy satisfies pPoA(f,w,,)≤max11+k1,1k. pPoA(f,w, C, N)≤ \ 11+k_1, 1k \. (16) (i) If there is at least one blind class, i.e., kb,kn≥1k_b,k_n≥ 1, then then the marginal contribution utility mechanism fmc:=fjmcj∈[k]f mc:=\f mc_j\_j∈[k] satisfies pPoA(fmc,w,,)≥1k pPoA(f mc,w, C, N)≥ 1k (17) (i) If there is no blind class, i.e., kb=0k_b=0 and ki,kn≥1k_i,k_n≥ 1 or no normal class, i.e., kn=0k_n=0, the marginal contribution utility mechanism fmc:=fjmcj∈[k]f mc:=\f mc_j\_j∈[k] satisfies pPoA(fmc,w,,)≥11+k. pPoA(f mc,w, C, N)≥ 11+k. (18) Interestingly, in both Theorem 4 and Theorem 5, the bounds on the PoA do not depend upon the number of agents in various classes, and only on the number of classes in the network (,)( C, N). Figure 2(b) presents an example of a network with three classes that satisfies the condition in part (i) of Theorem 5. IV-B General Submodular Games Now we consider the case of general submodular games. Section V provides a linear program (LP) that derives the pure price of anarchy for any given basis function, utility generating mechanism and any arbitrary information network. This allows for numerical computation of the pure price of anarchy even in cases when closed-form expressions are difficult to obtain. We solve the LP and derive the pure PoA for various submodular basis functions and present some interesting observations. In the following, submodular basis functions of the form w(j)=jdw(j)=j^d with d∈[0,1]d∈[0,1] are considered; d=0d=0 corresponds to set cover games, and d>0d>0 covers a wide class of submodular functions. Hence, we refer to d as the submodularity parameter. In this section, we restrict our attention to the information networks with normal, blind and isolated agents. For such games, the PNE is guaranteed to exist for any utility generating mechanism. Hence one can optimize over utility generating mechanism f in the LP in (21) to derive optimal utility generating mechanism and optimal price of anarchy. The non-linear terms of the form λjfj _jf_j that arise upon considering f as a decision variable is taken care by the virtue of Lemma 5, which implies that the scaling of fjf_j with a positive coefficient doesn’t alter PoA. See Remark 2 for more details. The code for computing/optimizing PoA is available at [27]. All the observations presented in the section are empirical. IV-B1 Robustness We first study the robustness of the optimal full information utility generating mechanism represented by f∗f^* from [9, Theorem 4], and show that it is quite robust to communication failures. In Figure 4, a submodular basis function with a low submodularity parameter (d=0.25d=0.25) in the left sub-figure and a high submodularity parameter (d=0.75d=0.75) in the right sub-figure is considered. The LP in Section V provides the pure price of anarchy for f∗f^* and one can calculate optimal PoA by further optimizing over f for the networks with blind/isolated agents. The PoA when agents continue using f∗f^* even when there is a communication failure is not significantly different than the optimal PoA specific to the information network, indicating significant robustness to communication failures. Fig. 3: The optimal utility generating mechanism f∗f^* corresponding to the full information case where all the agents can observe the actions of all other agents is ‘almost’ optimal for any network (,)( C, N) with blind and normal agents. With low submodularity parameter d=0.25d=0.25 (left), the marginal contribution utility mechanism fmcf mc performs better than f∗f^* but with high submodularity parameter d=0.75d=0.75 (right) f∗f^* outperforms fmcf mc. Thus, f∗f^* is robust against communication failures. Fig. 4: The PoA at optimal utility generating mechanism f∗f^* corresponding to the full information case where all agents can observe the actions of all other agents converges to the optimal PoA for a network (,)( C, N) with 22 blind and 1313 normal agents as submodularity parameter increases (left). When the number of blind agents increases to 55, the PoA at f∗f^* and optimal PoA become indistinguishable (right) for any value of submodularity parameter. This depicts the robustness of f∗f^* to communication failure irrespective of the submodular basis function w under consideration. Figure 4 also depicts the PoA of the marginal contribution utility; when the submodularity parameter is low, marginal contribution performs very close to the optimal mechanism. This appears to be because a low submodularity parameter is “close” to a set cover game where marginal contribution has been proved to be optimal. When the submodularity parameter is higher, the performance of the marginal contribution utility degrades. However, with more blind agents, the marginal contribution and f∗f^* converge to the optimal PoA. Interestingly, the PoA with high submodularity parameter remains more than half even when all the agents become blind as opposed to set cover games, where even one communication failure leads to an optimal PoA of less than half. In Figure 4, the number of blind agents is fixed to 2 in the left sub-figure and 5 in the right sub-figure, and we plot the PoA at f∗f^* and the optimal PoA for various submodularity parameters d. The PoA at f∗f^* and the optimal PoA both improve with the submodularity parameter. Further, it is clear that f∗f^* is robust to communication failures irrespective of the submodularity parameter. The gap between the optimal PoA and PoA at f∗f^* becomes negligible as more agents in the system become compromised. Hence, our results indicate that the system designer can assign the f∗f^* utility mechanism to the agents irrespective of the information network, and the PoA remains almost optimal even if there is an unanticipated communication failure. Fig. 5: Optimal PoA for a network with κ blind agents and n−κn-κ normal agents is better than that for a network with κ isolated agents and n−κn-κ normal agents where κ varies from 00 to n when submodularity parameter is fixed to d=0.5d=0.5 and n=15n=15 (left). Further, the optimal PoA is monotonically decreasing when more agents become blind or isolated in respective networks. When κ is fixed to 33 and submodularity parameter d is varied in interval [0,1][0,1], the network with κ blind agents outperforms the network with κ isolated agents. This implies that the optimal PoA is monotone with respect to the ‘connectedness’ of the information network among the agents. IV-B2 Monotonicity Now we study the optimal PoA as the communication level in the network varies; for example, we would say that a system with blind agents is more connected than a system with only isolated agents. Figure 5 gives numerical evidence that at least in the case of blind and isolated agents, when the network is less connected, the PoA decreases. In the left sub-figure, as more agents become compromised and the network becomes less connected, the optimal PoA also degrades. Furthermore, the optimal PoA for a network with blind agents is better than that of a network with isolated agents since the network with blind agents is more connected. In the right sub-figure, the number of compromised agents is fixed to 3 out of 15 total agents. The resulting plot indicates that regardless of the submodularity parameter, the network with blind agents has a better PoA than the network with isolated agents. This suggests that a system with higher connectivity may have better optimal performance than one with lower connectivity; however, this has not been proved and may be an interesting area for future work. V Arbitrary Games The previous sections consider the cases of supermodular and submodular games and provide various theorems deriving the pure price of anarchy for specific information networks. In this section we provide a linear program (LP) in Theorem 6 that solves (8) for any information network (,)( C, N), basis function w and utility generating mechanism chosen by the system designer; this LP is the analytical machinery that underlies all of the technical results from Sections I and IV. Note that the basis function in this section is no longer restricted to submodular or supermodular functions. V-A Notations for LP We first provide the notation required to present the linear programs. Let (,)( C, N) be an arbitrary network with k classes. Recall κj _j represents the number of agents in class j C_j, i.e., κj=|j|≥1 _j=| C_j|≥ 1 for j∈[k]j∈[k]. Let j:=l:l∈j O_j:=\l: C_l∈ N_j\ represent the indices of classes whose agents can be observed by agents of j C_j; that is, j=ll∈j N_j=\ C_l\_l∈ O_j for j∈[k]j∈[k]. Let sjs_j represent the number of agents in j N_j, i.e., sj=∑l∈jκls_j= _l∈ O_j _l. The forthcoming linear programs in (24) (primal) and (21) (dual) perform a search for pPoA-minimizing game instances parameterized by a given (f,w,,)(f,w, C, N). The primal LP’s decision variables encode resource values in the underlying game instances; these resources are apportioned to agent action sets in such a way that the intended equilibrium and optimal behavior is realized. The following notation facilitates these LPs by providing a uniform method of indexing the requisite decision variables and constraints. Define a set ℐℛ I_ R of action configurations as below which will index the constraint set of the LP deriving the pPoA(f,w,,) pPoA(f,w, C, N) defined in (8). ℐℛ I_ R -5.69054pt := := ((a1,x1,b1),…,(ak,xk,bk)): -5.69054pt \ ((a_1,x_1,b_1),…,(a_k,x_k,b_k) ): (19) (aj,xj,bj)∈ℕ≥03, 0≤aj+xj+bj≤κj, (a_j,x_j,b_j) ^3_≥ 0,\ 0≤ a_j+x_j+b_j≤ _j, ajxjbj=0 or aj+xj+bj=κj for j∈[k]. 14.22636pta_jx_jb_j=0 or a_j+x_j+b_j= _j for j∈[k] \. Let action configuration t be defined to be (t1…,tk)(t_1…,t_k) where tj=(aj,xj,bj)t_j=(a_j,x_j,b_j); in the formulation of the primal LP, each tjt_j represents a specific configuration of action choices for agents within class j C_j. Then a typical element of ℐℛ I_ R is t∈ℐℛt∈ I_ R. For any configuration t∈ℐℛt∈ I_ R define the equilibrium coverage AtA_t, the observable equilibrium coverage At,jA_t,j and the optimal coverage BtB_t as follows: At A_t := := ∑j∈[k]aj+xj,Bt:=∑j∈[k]bj+xj and _j∈[k]a_j+x_j, 5.69054ptB_t\ :=\ _j∈[k]b_j+x_j and At,j A_t,j := := ∑l∈jal+xl for all j∈[k]. _l∈ O_ja_l+x_l 5.69054pt for all j∈[k]. (20) With all the above notations defined, we are now ready to present the linear programs. TABLE I: Summary of Notation Symbol Description n Total number of agents w Basis function (,)( C,N) Network with k classes k Number of classes j C_j Set of agents in class j fjf_j Utility generating mechanism for class j C_j κj _j Number of agents in class j j N_j Set of classes observable for class j jO_j Index of classes observable by agents of class j sjs_j Total observable agents for class j ℐRI_R Set of action configurations (19) t=(t1,…,tk)t=(t_1,…,t_k) Action configuration; element of ℐRI_R tj=(aj,xj,bj)t_j=(a_j,x_j,b_j) Agent actions in class j at configruation t AtA_t Equilibrium coverage at configuration t BtB_t Optimal coverage at configuration t At,jA_t,j Observable equilibrium coverage at configuration t V-B LP deriving PoA for any Utility Generating Mechanism The next theorem provides a linear program that characterizes pPoA(f,w,,) pPoA(f,w, C, N) in (8) for any information network (,)( C, N), any basis function w and any utility generating mechanism f chosen by system designer. Theorem 6 (LP to characterize PoA) For a given network (,)( C, N), basis function w and utility generating mechanism f=fjj∈[k]f=\f_j\_j∈[k], (i) If fj(1)≤0f_j(1)≤ 0 for any j∈[k]j∈[k], then pPoA(f,w,,)=0 pPoA(f,w, C, N)=0. (i) If fj(1)>0f_j(1)>0 for all j∈[k]j∈[k], then, pPoA(f,w,,) pPoA(f,w, C, N) = = 1μ∗ 1μ^* where μ∗μ^* is the finite solution of the following LP in the unknowns μ∈ℝμ and λj∈ℝ≥0 _j _≥ 0 for j∈[k]j∈[k]: μ∗= μ^*= minμ,λ1,…,λkμ subject to -14.22636pt _μ, _1,…, _k\ \ μ 14.22636pt subject to (21) w(Bt)+∑j∈[k]λj[ajfj(At,j)−bjfj(At,j+1)]≤μw(At) -42.67912ptw(B_t)+ _j∈[k] _j[a_jf_j(A_t,j)-b_jf_j(A_t,j+1)]≤μ w(A_t) for all t∈ℐℛ, 133.72786pt for all t∈ I_ R, where fj(0)=fj(sj+1)=w(0)=0 for all j∈[k]. -42.67912pt where f_j(0)=f_j(s_j+1)=w(0)=0 for all j∈[k]. A similar LP is presented in [9, Theorem 2] that derives the PoA for any utility generating mechanism for a network with full information. Theorem 6 extends that result to cater for any general information network; such an extension is non-trivial and the proof is presented in Appendix A. In Appendix A, an LP is derived that computes the PoA, and the LP in above theorem is the dual LP of the same. The above LP has has k+1k+1 variables and ∏j=1k(2κj2+2) _j=1^k(2 _j^2+2) constraints. Remark 2 (Optimal PoA) In an information network with blind, isolated and normal agents, the PNE is guaranteed to exist for all utility generating mechanism. Hence, one can optimize over f to derive the optimal utility generating mechanism and optimal PoA. When f is considered as a decision variable, the terms λjajfj(At,j) _ja_jf_j(A_t,j) and λjbjfj(At,j+1) _jb_jf_j(A_t,j+1) become non-linear, however, they can be replaced by another utility generating mechanism f~j(⋅):=λjfj(⋅) f_j(·):= _jf_j(·) without changing the PoA by Lemma 5 making the optimization problem linear again. To do so, note that any feasible λj>0 _j>0 for all j: consider t∈ℐℛt∈ I_ R with bj=1b_j=1 and all other components zero, then λj≥fj(1) _j≥ f_j(1), and by Theorem 6 part (i), fj(1)>0f_j(1)>0 for non-zero PoA (zero PoA cannot be optimal). Then, the resulting LP has μ,f~μ, f as the decision variable. It is easy to extend the arguments in [9, Lemma 4] to show that the resulting LP achieves the optimal solution with bounded components. VI Conclusions We consider the utility design problem in networked multi-agent coordination using game theory with an aim to derive optimal utility designs and optimal performance guarantees measured by the price of anarchy (PoA) metric. Closed form expressions for optimal utility design leading to optimal PoA for supermodular and submodular system objectives for various networks are derived. For any general system objective and information network, two linear programs (LP) are provided — (i) the first LP characterizes the exact PoA for any utility design choice and (i) the second LP derives the optimal utility design and optimal PoA. Our work settles several open questions in utility design for networked multiagent systems (for example, optimal PoA for networked supermodular problems) and highlights several others (for example, extensions such as studying non-submodular problems through the lens of the strong price of anarchy as in [28]). We believe the problem of (non)-existence of pure-strategy Nash equilibrium to be of particular interest. When networks among agents are nontrivial and PNE may not exist, classical arguments for the relevance of PNE (e.g., potential game-based arguments) lose weight. In these cases, it may be more relevant to study performance guarantees in games from the standpoint of the limiting behavior of learning rules rather than static equilibrium concepts such as PNE. In such dynamic settings, it will be interesting to see how guarantees compare to the limited static ones which we derive here. Furthermore, future work could investigate whether our LP formulations can be used to prove closed-form bounds for other standard submodular functions, for example the curvature parameterization used in [29]. Finally, it would be interesting to study generally the relationship between fixed utility generating mechanisms such as fmcf mc and optimal mechanisms over all infomation networks. Appendix A Proofs of Section V We first provide another linear program (LP) in Theorem 7 in the following which is instrumental in proving Theorem 6. Define the following set which will facilitate the constraints of the LP in Theorem 7: ℐ I := := ((a1,x1,b1),…,(ak,xk,bk)):(aj,xj,bj)∈ℕ≥03, \((a_1,x_1,b_1),…,(a_k,x_k,b_k)):(a_j,x_j,b_j) ^3_≥ 0, (22) 0≤aj+xj+bj≤κj for j∈[k]. 28.45274pt0\ ≤\ a_j+x_j+b_j\ ≤\ _j for j∈[k] \. 14.22636pt Recall t is defined to be (t1…,tk)(t_1…,t_k) where tj=(aj,xj,bj)t_j=(a_j,x_j,b_j). Then a typical element of ℐ I is t∈ℐt∈ I. Further, for any t define AtA_t, At,jA_t,j and BtB_t as in (20). Theorem 7 (Primal LP to characterize PoA) For a given network (,)( C, N), basis function w and utility generating mechanism f=fjj∈[k]f=\f_j\_j∈[k], (i) If fj(1)≤0f_j(1)≤ 0 for any j∈[k]j∈[k], then pPoA(f,w,,)=0 pPoA(f,w, C, N)=0. (i) If fj(1)>0f_j(1)>0 for all j∈[k]j∈[k], then pPoA(f,w,,) pPoA(f,w, C, N) = = 1W∗ 1W^* (23) where W∗W^* is the finite value of the following LP in the unknowns θ(t)\θ(t)\: W∗ W^* = = max∑t∈ℐθ(t)w(Bt)θ(t)subject to _θ(t) _t∈ Iw(B_t)θ(t) 14.22636pt subject to (24) ∑t∈ℐ[ajfj(At,j)−bjfj(At,j+1)]θ(t)≥0,j∈[k] -28.45274pt _t∈ I[a_jf_j(A_t,j)-b_jf_j(A_t,j+1)]θ(t)≥ 0, 5.69054ptj∈[k] ∑t∈ℐw(At)θ(t)=1, -28.45274pt _t∈ Iw(A_t)θ(t)=1, θ(t)≥0for allt∈ℐ, -28.45274ptθ(t)≥ 0\ 5.69054pt for all\ \ t∈ I, and fj(0)=fj(sj+1)=w(0)=0,∀j∈[k]. -28.45274pt\ f_j(0)=f_j(s_j+1)=w(0)=0,\ ∀\ j∈[k]. Proof: Part (i) follows by [9, Lemma 1]. Towards part (i), we first come up with a reduced class of games ^f,w(,)⊆f,w(,) G_f,w^( C, N) G_f,w^( C, N) such that PoA over class of games ^f,w(,) G_f,w^( C, N) is same as that over the class of games f,w(,) G_f,w^( C, N). Then we re-write (8) as a constrained optimization problem in (25). Next, we consider a relaxation of (25) in (26) and show the equivalence of (26) and (24). Lastly, using Lemma 3 we show that the relaxation is indeed tight, and optimization problems (25) and (26) are equivalent which completes the proof. Let ^f,w(,) G_f,w^( C, N) be the set of games that contains one G G for each G∈f,w(,)G∈ G_f,w^( C, N) such that G G matches G in everything except the action sets of the agents. The action set of any agent i in G G only contains the action at the worst NE of G and that at an optimal action profile, that is, i=aiNE,aiopt A_i=\a NE_i,a opt_i\. By Lemma 1, the price of anarchy pPoA(f,w,,)=1W∗ pPoA(f,w, C, N)= 1W^*, where W∗W^* is the solution of following optimization problem: W∗ W^* = = supG^∈^f,w(,)W(aopt) _ G∈ G_f,w^( C, N)W(a opt) s.t. Ui(aNE)≥Ui(aiopt,a−iNE)∀i∈N, U_i(a NE)≥ U_i(a opt_i,a NE_-i) 14.22636pt∀\ \ i∈ N, (25) W(aNE)=1. W(a NE)=1. To construct a linear program solving optimization problem in (25) consider the following relaxation: V∗ V^* = = supG^∈f,w(,)W(aopt) _ G∈ G_f,w^( C, N)W(a opt) s.t. ∑i∈j[Ui(aNE)−Ui(aiopt,a−iNE)]≥0,for j∈[k], _i∈ C_j [U_i(a NE)-U_i(a opt_i,a NE_-i) ]≥ 0, 14.22636pt for j∈[k], (26) W(aNE)=1. W(a NE)=1. Further, let (a) xj,r∈0,[κj]x_j,r∈\0,[ _j]\ be the number of agents in j C_j selecting resource r in both aNEa NE and aopta opt. (b) aj,r+xj,r∈0,[κj]a_j,r+x_j,r∈\0,[ _j]\ be the number of agents in j C_j selecting resource r in aNEa NE. (c) bj,r+xj,r∈0,[κj]b_j,r+x_j,r∈\0,[ _j]\ be the number of agents in j C_j selecting resource r in aopta opt. (d) ArA_r be total number of agents who select resource r at aNEa NE, thus Ar:=∑j∈[k]aj,r+xj,rA_r:= _j∈[k]a_j,r+x_j,r. (e) Ar,jA_r,j be the number of agents from classes j O_j who select resource r at aNEa NE, thus Ar,j:=∑l∈jal,r+xl,rA_r,j:= _l∈ O_ja_l,r+x_l,r. (f) BrB_r be total number of agents who select resource r at aopta opt thus Br:=∑j∈[k]bj,r+xj,rB_r:= _j∈[k]b_j,r+x_j,r. For each t∈ℐt∈ I of (22), define ℛ(t) R(t) as follows: ℛ(t) R(t) = = r∈ℛ:aj,r+xj,r=aj+xj,xj,r=xj \r∈ R:a_j,r+x_j,r=a_j+x_j,\ x_j,r=x_j (27) bj,r+xj,r=bj+xj for j∈[k] 28.45274ptb_j,r+x_j,r=b_j+x_j for j∈[k]\ to be the set of all the resources that are selected by exactly aj+xja_j+x_j agents from j C_j at aNEa NE, bj+xjb_j+x_j at aopta opt and xjx_j agents in both aNEa NE and aopta opt. Further define θ(t)θ(t) to be the sum of the values of the resources in ℛ(t) R(t), i.e., θ(t)=∑r∈ℛ(t)vrθ(t)= _r∈ R(t)v_r. We can use θ\θ\ to define the quantities in (26). Let At,Bt,At,jA_t,B_t,A_t,j be as in (20), then W(aNE) W(a NE) = = ∑r∈ℛvrw(Ar) _r∈ Rv_r\ w(A_r) (28) = = ∑t∈ℐw(At)∑r∈ℛ(t)vr=∑t∈ℐw(At)θ(t). _t∈ Iw(A_t) _r∈ R(t)v_r= _t∈ Iw(A_t)θ(t). Using similar logic, we get W(aopt) W(a opt) = = ∑t∈ℐw(Bt)θ(t) and _t∈ Iw(B_t)θ(t) 14.22636pt and (29) ∑i∈jUi(aNE) _i∈ C_jU_i(a NE) = = ∑t∈ℐ(aj+xj)fj(At,j)θ(t). _t∈ I(a_j+x_j)f_j(A_t,j)θ(t). (30) Lastly, ∑i∈jUi(aiopt,a−iNE) _i∈ C_jU_i(a opt_i,a NE_-i) equals =∑r∈ℛvr[xj,rfj(Ar,j)+bj,rfj(Ar,j+1)] -19.91692pt= _r∈ Rv_r[x_j,rf_j(A_r,j)+b_j,rf_j(A_r,j+1)] =∑t∈ℐ[xjfj(At,j)+bjfj(At,j+1)]θ(t). -19.91692pt= _t∈ I[x_jf_j(A_t,j)+b_jf_j(A_t,j+1)]θ(t). (31) Thus, the optimization problem (26) is equivalent to W∗ W^* = = supθ(t)∑t∈ℐw(Bt)θ(t) _θ(t) _t∈ Iw(B_t)θ(t) s.t. ∑t∈ℐ[ajfj(At,j)−bjfj(At,j+1)]θ(t)≥0,j∈[k], -28.45274pt _t∈ I[a_jf_j(A_t,j)-b_jf_j(A_t,j+1)]θ(t)≥ 0, 2.84526ptj∈[k], (32) ∑t∈ℐw(At)θ(t)=1, -28.45274pt _t∈ Iw(A_t)θ(t)=1, θ(t)≥0 for all t∈ℐ, -28.45274ptθ(t)≥ 0\ 14.22636pt for all \ \ t∈ I, and fj(0)=fj(sj+1)=w(0)=0,∀j∈[k]. -28.45274pt\ f_j(0)=f_j(s_j+1)=w(0)=0,\ ∀\ j∈[k]. To see that the maximum in above is achieved, note that the objective function is continuous in θ\θ\. All θ(t)≥0θ(t)≥ 0 are bounded below. The constraint on W(aNE)=1W(a NE)=1 implies that θ(t)θ(t) is bounded for all t∈ℐt∈ I with At≥1A_t≥ 1. For t∈ℐt∈ I such that At=0A_t=0, the equilibrium constraint for class j C_j can be re-written as, ∑t∈ℐAt=0bjfj(1)θ(t) _ subarrayct∈ I\\ A_t=0 subarrayb_jf_j(1)θ(t) ≤ ≤ ∑t∈ℐAt≥1[ajfj(At,j−bjfj(At,j+1)]θ(t) _ subarrayct∈ I\\ A_t≥ 1 subarray[a_jf_j(A_t,j-b_jf_j(A_t,j+1)]θ(t) which provides the required boundedness as fj(1)>0f_j(1)>0. Thus θ(t)\θ(t)\ belong to a compact domain and optimization problem in (26) is equivalent to the linear program in (24). Clearly, V∗≥W∗V^*≥ W^* since any feasible point for optimization problem (25) is also a feasible point for optimization problem (26) and hence for (24). Lemma 3 (presented next) shows that V∗≤W∗V^*≤ W^*, obtaining the proof of Theorem 7. ■ Lemma 1 Let ^f,w(,) G_f,w^( C, N) be the set of games that contains one G G for each G∈f,w(,)G∈ G_f,w^( C, N) such that G G matches G in everything except the action sets of the agents. The action set of any agent i in G G only contains the action at the worst NE of G and that at an optimal action profile, that is, i=aiNE,aiopt A_i=\a NE_i,a opt_i\. Then price of anarchy pPoA(f,w,,) pPoA(f,w, C, N) of (8) equals 1W∗ 1W^*, where W∗W^* is the solution of following optimization problem: W∗ W^* = = infG^∈^f,w(,)1W(aopt) _ G∈ G_f,w^( C, N) 1W(a opt) s.t. Ui(aNE)≥Ui(aiopt,a−iNE)∀i∈N, U_i(a NE)≥ U_i(a opt_i,a NE_-i) 14.22636pt∀\ \ i∈ N, (33) W(aNE)=1. W(a NE)=1. Proof: The proof follows in the exact same manner as in step 2 of the proof of [9, Theorem 2]. We reproduce the proof here for the sake of completion. Using Lemma 2, it is sufficient to consider the games in ^f,w(,) G_f,w^( C, N) to derive the pPoA(f,w,,) pPoA(f,w, C, N). By [9, Lemma 2], for every game G∈f,w(,)G∈ G_f,w^( C, N) and hence for every game G^∈^f,w(,) G∈ G_f,w^( C, N), the system objective W(aNE)>0W(a NE)>0. Now for a fixed game G G, create another game G~ G that matches G G in every aspect except the value of resources. Each resource in game G G is scaled by W(aNE)W(a NE) of G G in the game G~ G. Basically, a resource r with value vrv_r in game G G now has value of vrW(aNE) v_rW(a NE) in game G~ G. With this scaling, the worst performing equilibrium and optimal action profile remain unchanged. However, the system objective at worst equilibrium of G~ G, W(aNE)W(a NE), equals 1 using (1) while the PoA of G G and G~ G remain equal. Further, G^∈^f,w(,):W(aNE)=1⊆^f,w(,)\ G∈ G_f,w^( C, N):W(a NE)=1\ G_f,w^( C, N). Hence, following similar arguments as in proof of Lemma 2, it is clear that the PoA over class ^f,w(,) G_f,w^( C, N) is the same as the subclass that is constrained to W(aNE)=1W(a NE)=1. Thus the PoA in (8) can be computed using (33). This completes the proof. ■ Lemma 2 The price of anarchy over ^f,w(,) G_f,w^( C, N) of Lemma 1 is same as that over f,w(,) G_f,w^( C, N), that is, pPoA(f,w,,)=infG∈^f,w(,)(min∈PNE(G)W()max∈W()). pPoA(f,w, C, N)= _G∈ G_f,w^( C, N) ( _ a∈ PNE(G)W( a) _ a∈ AW( a) ). Proof: The proof follows in the exact same manner as in step 1 of the proof of [9, Theorem 2]. We reproduce the proof here for the sake of completion. By definition ^f,w(,)⊆f,w(,) G_f,w^( C, N) G_f,w^( C, N), and for any game G∈f,w(,)G∈ G_f,w^( C, N), there is a game G^∈^f,w(,) G∈ G_f,w^( C, N) such that G and G G have the same pure price of anarchy, min∈PNE(G^)W()max∈W()=min∈PNE(G)W()max∈W(). _ a∈ PNE( G)W( a) _ a∈ AW( a)= _ a∈ PNE(G)W( a) _ a∈ AW( a). Hence the proof. ■ Lemma 3 Consider W∗W^* as in (25) and V∗V^* as in (26). It holds that V∗≤W∗V^*≤ W^*. Proof: Let θ(t)\θ(t)\ be any feasible solution of LP (24) with objective value V. We construct a game instance G that satisfies the constraints of (25) with the same objective value. This will conclude V∗≤W∗V^*≤ W^*. Let n~:=∏j=1kκj n:= _j=1^k _j. Let ℛ=ℐ×[n~] R= I×[ n]. For each (t,q)∈ℛ(t,q)∈ R, construct resources r(t,q)r(t,q) with value vr(t,q)=θ(t)n~v_r(t,q)= θ(t) n. For each j∈[k]j∈[k], t∈ℐt∈ I and l∈[κj]l∈[ _j] define the following sets: Kj(t,l) K_j(t,l) = = r(t,q):q=(l−1)n~κj+1,…,ln~κj \r_(t,q):q=(l-1) n _j+1,…,l n _j \ Add sets Kj(t,l)K_j(t,l) to the action sets of agents in class j C_j in the following manner. For fixed t, arrange κj _j sets Kj(t,l)K_j(t,l) in a circle indexed by l∈[κj]l∈[ _j] in clockwise direction. Then, order the agents in class j C_j from 11 to κj _j. For the agent in i-th position, add aj+xja_j+x_j sets to the equilibrium action aijNEa NE_ij starting from set Kj(t,i)K_j(t,i) moving clockwise. For optimal action aijopta opt_ij, add bj+xjb_j+x_j sets starting from Kj(t,1+(i−1−bj)modκj)K_j(t,1+(i-1-b_j) _j) moving clockwise44 4 With slight abuse of notation, we use aijNEa NE_ij and aijopta opt_ij to represent the action set of player at the i-th position in j C_j, whereas this player may have been assigned a different label from [n][n] in the original problem.. Formally, aijNE=Kj(t,l):aj+xj≥1+((l−i)modκj),l∈[κj], -19.91692pta NE_ij=\K_j(t,l):a_j+x_j≥ 1+((l-i) -8.53581pt _j),l∈[ _j]\, aijopt=Kj(t,l):bj+xj≥1+(l−i+bj)modκj,l∈[κj]. -19.91692pta opt_ij -5.69054pt=\K_j(t,l):b_j+x_j≥ 1+(l-i+b_j) -8.53581pt _j,l∈[ _j]\. This process is repeated for all t, all i∈ji∈ C_j and all j C_j. For example, consider an instance with aj=2a_j=2, xj=2x_j=2, bj=1b_j=1, κj=6 _j=6 and i=2i=2 for some j C_j. Then aj+xj≥1+((l−i)modκj)a_j+x_j≥ 1+((l-i) _j) is true only for l=2,3,4l=2,3,4 and 55, and bj+xj≥1+(l−i+bj)modκjb_j+x_j≥ 1+(l-i+b_j) _j is true only for l=1,2,3l=1,2,3. Hence, agent i selects aj+xj=4a_j+x_j=4 sets of resources at equilibrium, bj+xj=3b_j+x_j=3 sets of resources at optimal action; and resources in xj=2x_j=2 sets Kj(t,2)K_j(t,2) and Kj(t,3)K_j(t,3) are common in equilibrium and optimal actions. It is not difficult to show that this construction results in a game where for all t∈ℐt∈ I, B.1 Any resource r(t,q)r_(t,q) for q∈[n~]q∈[ n] has a value of θ(t)n~ θ(t) n. B.2 Any r(t,q)r_(t,q) for q∈[n~]q∈[ n] is selected by exactly aj+xja_j+x_j agents from j C_j at aNEa NE, thus AtA_t agents (see (20)). Further, r(t,q)r_(t,q) is selected by bj+xjb_j+x_j agents from class j C_j at aopta opt (thus BtB_t agents). B.3 Each agent in j C_j selects (aj+xj)(a_j+x_j) sets out of Kj(t,l)l∈[κj]\K_j(t,l)\_l∈[ _j] at aNEa NE, each of which contains n~κj n _j resources. Thus every agent selects n~κj(aj+xj) n _j(a_j+x_j) resources at aNEa NE. Every agent selects bj+xjb_j+x_j such sets at aopta opt, thus selects n~κj(bj+xj) n _j(b_j+x_j) resources. Further, xjx_j sets, and hence n~κjxj n _jx_j resources are common in aNEa NE and aopta opt. We now prove that W(aNE)=1W(a NE)=1 and W(aopt)=VW(a opt)=V. Observe that W(aNE)=∑t∈ℐ∑q∈[n~]vr(t,q)=∑t∈ℐθ(t)w(At)=1 W(a NE)= -2.84526pt _t∈ I _q∈[ n] -2.84526ptv_r(t,q)= _t∈ Iθ(t)w(A_t)=1 5.69054pt (34) by the constraint in the LP in (24). Similar arguments prove that W(aopt)=VW(a opt)=V. For any t∈ℐt∈ I, the resource r(t,q)r_(t,q) is selected by At,j=∑p∈jap+xpA_t,j= _p∈ O_ja_p+x_p agents from j N_j for j∈[k]j∈[k]. The function (38) of Lemma 4 at aNEa NE equals, Gj(aNE)=∑q∈[n~]∑t∈ℐθ(t)n~∑l=1At,jfj(l)=1n~∑t∈ℐn~θ(t)∑l=1At,jfj(l).G_j(a NE)= _q∈[ n] _t∈ I θ(t) n _l=1^A_t,jf_j(l)= 1 n _t∈ I nθ(t) _l=1^A_t,jf_j(l). (35) When an agent i∈ji∈ C_j unilaterally deviates from aNEa NE to (aiopt,a−iNE)(a opt_i,a NE_-i), then each Kj(t,l)∈aiNEK_j(t,l)∈ a NE_i which is not in aiopta opt_i would be selected one less time, and each Kj(t,l)∈aioptK_j(t,l)∈ a opt_i which is not in aiNEa NE_i would be selected one more time. Thus, aja_j sets of the type Kj(t,l)K_j(t,l) get selected by one less agent and bjb_j sets of the type Kj(t,l)K_j(t,l) get selected by one extra agent. Thus for each t∈ℐt∈ I, n~κjaj n _ja_j resources get selected by At,j−1A_t,j-1 agents from j N_j and n~κjbj n _jb_j resources get selected by At,j+1A_t,j+1 agents from j N_j, rest are selected by At,jA_t,j agents from j N_j. Then Gj(aiopt,a−iNE)G_j(a opt_i,a NE_-i) equals, =1n~∑t∈ℐθ(t)[n~bjκj∑l=1At,j+1fj(l)+n~ajκj∑l=1At,j−1fj(l) -21.33955pt=\ 1 n _t∈ Iθ(t) [ nb_j _j _l=1^A_t,j+1f_j(l)+ na_j _j _l=1^A_t,j-1f_j(l) +(n~−n~ajκj−n~bjκj)∑l=1At,jfj(l)] 71.13188pt+ ( n- na_j _j- nb_j _j ) _l=1^A_t,jf_j(l) ] (36) =1n~∑t∈ℐθ(t)[n~bjfj(At,j+1)κj−n~ajfj(At,j)κj+n~∑l=1At,jfj(l)]. -21.33955pt=\ 1 n _t∈ Iθ(t) [ nb_jf_j(A_t,j+1) _j- na_jf_j(A_t,j) _j+ n _l=1^A_t,jf_j(l) ]. From (35) and (36), Gj(aNE)−Gj(aiopt,a−iNE)G_j(a NE)-G_j(a opt_i,a NE_-i) equals =1κj∑t∈ℐθ(t)[ajfj(At,j)−bjfj(At,j+1)]≥ 0 -21.33955pt= 1 _j _t∈ Iθ(t)[a_jf_j(A_t,j)-b_jf_j(A_t,j+1)]\ ≥\ 0 (37) by the constraint in the LP (24). Similar arguments follow for all j∈[k]j∈[k]. By Lemma 4 (presented next), aNEa NE is a Nash equilibrium, hence satisfying the constraints in (25). ■ Lemma 4 For any j∈[k]j∈[k], let Gj(⋅)G_j(·) be defined as Gj() G_j( a) = = ∑r∈∪iaivr∑l=1||rjfj(l). _r∈ _ia_iv_r _l=1^| a|_r N_jf_j(l). (38) Then, Gj()−Gj(bi,a−i)=Ui()−Ui(bi,a−i)G_j( a)-G_j(b_i,a_-i)=U_i( a)-U_i(b_i,a_-i) for all bi∈ib_i∈ A_i, i∈ji∈ C_j and all j∈[k]j∈[k]. Proof: When an agent i∈ji∈ C_j deviates to bi=ai 1∪R2b_i=\a_i R_1\∪ R_2 where R1,R2⊂ℛR_1,R_2⊂ R, then Ui(bi,a−i)=∑r∈ai 1vrfj(||rj)+∑r∈R2vrfj(||rj+1) U_i(b_i,a_-i)= _r∈ a_i R_1v_rf_j(| a| N_j_r)+ _r∈ R_2v_rf_j(| a| N_j_r+1) =Ui(ai,a−i)−∑r∈R1vrfj(||rj)+∑r∈R2vrfj(||rj+1). =U_i(a_i,a_-i)- _r∈ R_1v_rf_j(| a| N_j_r)+ _r∈ R_2v_rf_j(| a| N_j_r+1). Further, Gj(bi,a−i)G_j(b_i,a_-i) equals, = = Gj()−∑r∈R1vrfj(||rj)+∑r∈R2vrfj(||rj+1). G_j( a)- _r∈ R_1v_rf_j(| a| N_j_r)+ _r∈ R_2v_rf_j(| a| N_j_r+1). Hence the proof. ■ Proof of Theorem 6 The dual of the LP in (24) equals (see e.g.,[26]) μ∗ μ^* = = minλ1≥0,…,λk≥0,μ∈ℝμ subject to _ _1≥ 0,…, _k≥ 0,μ \ \ μ 14.22636pt subject to (39) w(Bt)+∑j∈[k]λj[ajfj(At,j)−bjfj(At,j+1)]≤μw(At) -42.67912ptw(B_t)+ _j∈[k] _j[a_jf_j(A_t,j)-b_jf_j(A_t,j+1)]≤μ w(A_t) t∈ℐℛ, 142.26378pt\ t∈ I_ R, fj(0)=fj(sj+1)=w(0)=0,∀j∈[k]. f_j(0)=f_j(s_j+1)=w(0)=0,∀\ j∈[k]. By strong duality ([26]), μ∗μ^* of above equals W∗W^* of (24). It remains to show that considering all t∈ℐt∈ I of (22) is equivalent to considering all t∈ℐℛt∈ I_ R of (19). Observe that t∈ℐt∈ I such that At=0A_t=0 or Bt=0B_t=0 are all contained in ℐℛ I_ R. Next, we show that the constraints corresponding to t∈ℐt∈ I such that At≠0A_t≠ 0 and Bt≠0B_t≠ 0 are equivalent to the constraints corresponding to t∈ℐℛt∈ I_ R. For any t∈ℐt∈ I such that At≠0A_t≠ 0, Bt≠0B_t≠ 0, consider t′t such that aj′+xj′=aj+xja_j +x_j =a_j+x_j and bj′+xj′=bj+xjb_j +x_j =b_j+x_j for all j. Consider a change of coordinates from t to t~=(t~1…,t~k) t=( t_1…, t_k) where t~j t_j equals (lj,xj,mj)(l_j,x_j,m_j) with lj:=aj+xjl_j:=a_j+x_j and mj:=bj+xjm_j:=b_j+x_j. Then the constraint in (39) can be re-written as μw(At) μ w(A_t) ≥ ≥ w(Bt)+∑j∈[k]λj[ljfj(At,j)−mjfj(At,j+1) w(B_t)+ _j∈[k] _j[l_jf_j(A_t,j)-m_jf_j(A_t,j+1) (40) +xj[fj(At,j+1)−fj(At,j)]] 42.67912pt+x_j[f_j(A_t,j+1)-f_j(A_t,j)]] 5.69054pt for all t~∈ℐ t∈ I, where ℐ I equals (t~1…,t~k):(lj,xj,mj)∈ℕ≥03, 0≤lj−xj+mj≤κj, -21.33955pt \( t_1…, t_k):(l_j,x_j,m_j) ^3_≥ 0,\ 0≤ l_j-x_j+m_j≤ _j, lj≥xj,mj≥xj,∑j∈[k]lj≠0,∑j∈[k]mj≠0 l_j≥ x_j,\ m_j≥ x_j,\ _j∈[k]l_j≠ 0,\ _j∈[k]m_j≠ 0 and 1≤∑j∈[k](lj−xj+mj)≤n. 5.69054pt and \ 1\ ≤\ _j∈[k](l_j-x_j+m_j)≤\ n \. In the remainder of this proof, fix ljl_j for all j, and let xjx_j and mjm_j move freely in ℐ I. When lj=κjl_j= _j for all j∈[k]j∈[k], then mj=xjm_j=x_j since mj−xj≥0m_j-x_j≥ 0 and −xj+mj≤0-x_j+m_j≤ 0. This implies bj=0b_j=0 for all j, and note that this point is also contained in ℐℛ I_ R. Now consider the t~∈ℐ t∈ I such that lj≠κjl_j≠ _j for at least one j∈[k]j∈[k], and define two sets ℛ1 R_1 and ℛ2 R_2 as, ℛ1 R_1 = = j∈[k]:fj(At,j+1)−fj(At,j)≤0, \j∈[k]:\ f_j(A_t,j+1)-f_j(A_t,j)≤ 0\, ℛ2 R_2 = = j∈[k]:fj(At,j+1)−fj(At,j)>0. \j∈[k]:\ f_j(A_t,j+1)-f_j(A_t,j)>0\. For any fixed lj,mjl_j,m_j for j∈[k]j∈[k], the most binding constraint in (40) arises when xjx_j is picked as small as possible for j∈ℛ1j∈ R_1 (since xj≥0x_j≥ 0 and is multiplied with a negative coefficient), and xjx_j is picked as large as possible for j∈ℛ2j∈ R_2 (since xj≥0x_j≥ 0 and is multiplied with a positive coefficient). For j∈ℛ1j∈ R_1, since xj≥lj+mj−κjx_j≥ l_j+m_j- _j, for fixed mjm_j and ljl_j, the smallest value xjx_j can take is xj=max0,lj+mj−κjx_j= \0,l_j+m_j- _j\. There are two possibilities, B.1 when lj+mj≤κjl_j+m_j≤ _j, that is when aj+bj+2xj≤na_j+b_j+2x_j≤ n, then xj=0x_j=0 implying ajxjbj=0a_jx_jb_j=0, B.2 when lj+mj>κjl_j+m_j> _j, that is when aj+bj+2xj>κja_j+b_j+2x_j> _j then xj=lj+mj−κjx_j=l_j+m_j- _j implying aj+xj+bj=κja_j+x_j+b_j= _j. Similarly, for j∈ℛ2j∈ R_2, since xj≤ljx_j≤ l_j and xj≤mjx_j≤ m_j, for fixed mjm_j and ljl_j largest value of xjx_j is x=minlj,mjx= \l_j,m_j\. Again, there are two possibilities, B.3 when lj≤mjl_j≤ m_j, that is when aj≤bja_j≤ b_j then xj=ljx_j=l_j and thus aj=0a_j=0 implying ajxjbj=0a_jx_jb_j=0, B.4 when lj>mjl_j>m_j, that is when aj>bja_j>b_j then xj=mjx_j=m_j and thus bj=0b_j=0 implying ajxjbj=0a_jx_jb_j=0. In all, for any j∈[k]j∈[k], exactly one of the B.1-B.4 holds at the most binding constraint. Since all such quantities are included in ℐℛ I_ R, it is sufficient to consider ℐℛ I_ R and LP in (39) is equivalent to the LP (21). ■ Lemma 5 Consider any αj>0 _j>0 for j∈[k]j∈[k] and any utility generating mechanism f=fjj∈[k]f=\f_j\_j∈[k]. Define another utility generating mechanism fα=fjαj∈[k]f^α=\f^α_j\_j∈[k] as fjα(x)=α.fj(x)f^α_j(x)=α.f_j(x) for all j∈[k]j∈[k]. Then for any w and network (,)( C, N), PoA(fα,w,,)=pPoA(f,w,,). PoA(f^α,w, C, N)= pPoA(f,w, C, N). (41) Proof: The proof immediately follows from the constraint in (primal) LP (24) in Theorem 7. ■ Appendix B To follow the proofs in this section, one needs familiarize themselves with the result of Theorem 6, although the proof of Theorem 6 is not required in this section. The quantities defined in Section V-A are also used in most of the proofs presented in the following. Proof of Theorem 1 By Lemma 5 in Appendix A, we can restrict our attention to utility generating mechanism f such that fj(1)=1f_j(1)=1 for all j∈[k]j∈[k]. Consider a t∈ℐℛt∈ I_ R defined in (19) with At=0A_t=0 and Bt≠0B_t≠ 0. Such a t implies that ∑j∈[k]bj≥1 _j∈[k]b_j≥ 1 by (20). The constraint in LP (21) deriving pPoA(f,w,,) pPoA(f,w, C, N) at this t equals ∑j∈[k]bjλj _j∈[k]b_j _j ≥ ≥ w(∑j∈[k]bj) for all bj∈0,[κj]. w ( _j∈[k]b_j ) for all b_j∈\0,[ _j]\. (42) If t is such that bj=κjb_j= _j, the above constraint becomes ∑j∈[k]κjλj _j∈[k] _j _j ≥ ≥ w(n). w(n). (43) Observe that in the above, equality is achieved when λj=w(n)/n _j=w(n)/n for all j. When k=1k=1, λ1≥w(n)/n _1≥ w(n)/n. When k≥2k≥ 2, if λl<w(n)/n _l<w(n)/n, then there must be some λp>w(n)/n _p>w(n)/n for the constraint to be true for l,p∈[k]l,p∈[k]. Further, when t∈ℐℛt∈ I_ R is such that At≠0A_t≠ 0 and Bt=0B_t=0, define A~t,j=At,j|xj=0 A_t,j=A_t,j|_x_j=0, the constraint in (21) at this t equals μ≥1w(∑j∈[k]aj)∑j∈[k]λjajf(A~t,j) for all aj∈0,[κj].μ≥ 1w ( _j∈[k]a_j ) _j∈[k] _ja_jf( A_t,j) for all a_j∈\0,[ _j]\. 5.69054pt (44) The above constraint for a t with aj=1a_j=1 and al=0a_l=0 for l∈[k] ∈[k] j implies μ≥λjμ≥ _j for all j. Hence, μ μ ≥ ≥ w(n)n thus w(n)n 14.22636pt thus (45) pPoA(f,w,,) pPoA(f,w, C, N) ≤ ≤ 1μ≤nw(n) for all f. 1μ\ ≤\ nw(n) for all f. (46) Now consider the communication denied utility generating mechanism of (5); we prove that the upper bound on pPoA(f,w,,) pPoA(f,w, C, N) in (46) is achieved. Consider a t∈ℐℛt∈ I_ R such that At≠0A_t≠ 0. We first prove that the constraints with Bt≠0B_t≠ 0 are implied by those with Bt=0B_t=0. The LP constraint (21) when At≠0A_t≠ 0 and Bt≠0B_t≠ 0 equals μ μ ≥ ≥ 1w(At)(w(Bt)−∑j∈[k]λjbjCLOSE 1w(A_t) (w(B_t)- _j∈[k] _jb_j (47) +∑j∈[k]λjajAt,j≠0). 85.35826pt+ _j∈[k] _ja_j 1_\A_t,j≠ 0\ ). Observe that the RHS of the above constraint is less than or equal to following: ≤1w(At)(∑j∈[k]λj(bj+xj)−∑j∈[k]λjbjCLOSE -19.91692pt≤ 1w(A_t) ( _j∈[k] _j(b_j+x_j)- _j∈[k] _jb_j +∑j∈[k]λjajAt,j≠0), 99.58464pt+ _j∈[k] _ja_j 1_\A_t,j≠ 0\ ), (48) ≤1w(At)∑j∈[k]λj(aj+xj)At,j≠0). -19.91692pt≤ 1w(A_t) _j∈[k] _j(a_j+x_j) 1_\A_t,j≠ 0\). (49) In the above (48) follows from (42) as bj+xj∈0,[κj]b_j+x_j∈\0,[ _j]\, and (49) follows by the fact that At,j≠0=1 1_\A_t,j≠ 0\=1 when xj≠0x_j≠ 0 or aj≠0a_j≠ 0. Further, from (44) and (49), it is clear that (44) implies (47) since aj+xj∈0,[κj]a_j+x_j∈\0,[ _j]\. Thus, the only binding constraints are of the form (42) and (44). In these constraints, the coefficient of λj _j is always positive hence at optimality, λj=w(n)/n _j=w(n)/n for all j∈[k]j∈[k]. Finally, the RHS (44) upon substituting λj\ _j\ becomes = = w(n)n1w(∑j∈[k]aj)∑j∈[k]ajA~t,j≠0 w(n)n 1w ( _j∈[k]a_j ) _j∈[k]a_j 1_\ A_t,j≠ 0\ (50) ≤ ≤ w(n)n∑j∈[k]ajw(∑j∈[k]aj)≤w(n)n. w(n)n _j∈[k]a_jw ( _j∈[k]a_j )\ ≤\ w(n)n. 28.45274pt (51) In the above, (51) follows from the fact that w(j)j w(j)j is an increasing function because of supermodularity. Hence by (46) and (51) μ=w(n)nμ= w(n)n which results in the PoA of nw(n) nw(n). ■ Proof of Theorem 2 Consider a network (,)( C, N) and any utility generating mechanism f. If fj(1)≤0f_j(1)≤ 0 for any j, by Theorem 6 pPoA(f,w,,)=0 pPoA(f,w, C, N)=0 and we have nothing to prove. Now consider any f such that fj(1)>0f_j(1)>0 for all j∈[k]j∈[k]. From Theorem 6, the constraints in the LP (21) deriving the PoA when w(⋅)w(·) satisfies (12) equals μAt≠0≥Bt≠0+∑j∈[k]λj[ajfj(At,j)−bjfj(At,j+1)].μ 1_\A_t≠ 0\≥ 1_\B_t≠ 0\+ _j∈[k] _j[a_jf_j(A_t,j)-b_jf_j(A_t,j+1)]. (52) When t is such that bj=1b_j=1 and rest of the components of t are zero, (52) becomes λj _j ≥ ≥ 1fj(1) for any j∈[k]. 1f_j(1) for any j∈[k]. (53) Choose another t∈ℐℛt∈ I_ R such that al=1a_l=1, xp=1x_p=1 and rest of the components of t are zero. Then (52) becomes μ μ ≥ ≥ 1+λlfl(1)≥ 2 1+ _lf_l(1)\ ≥\ 2 (54) where the second inequality follows by (53). Thus any feasible μ for LP (21) is at least 2 implying the optimal μ∗≥2μ^*≥ 2. Then, pPoA(f,w,,) pPoA(f,w, C, N) = = 1μ∗≤12 for all f. 1μ^*\ ≤\ 12 for all f. (55) ■ Lemma 6 Let (μ∗,λ1∗,…,λk∗)(μ^*,λ^*_1,…,λ^*_k) be the solution of LP (21) deriving pPoA(f,w,,) pPoA(f,w, C, N). If w(⋅)w(·) satisfies (12) and fj=fjmcf_j=f mc_j as in (3) for all j∈[k]j∈[k], then λj∗=1λ^*_j=1 for all j∈[k]j∈[k]. Proof: Consider the constraint in the LP (21) deriving the pPoA(f,w,,) pPoA(f,w, C, N) when w(⋅)w(·) satisfies (12) given in (52) at marginal contribution utility (3): μAt≠0≥Bt≠0+∑j∈[k]λj[ajAt,j=1−bjAt,j=0].μ 1_\A_t≠ 0\≥ 1_\B_t≠ 0\+ _j∈[k] _j[a_j 1_\A_t,j=1\-b_j 1_\A_t,j=0\]. (56) For any t such that bj=1b_j=1 for some j∈[k]j∈[k] and rest of the components are zero, the above constraint implies λj≥1 _j≥ 1. This holds for all j∈[k]j∈[k]. To prove that λj∗=1 _j^*=1, we show that the only binding constraints on μ have a positive coefficient of λj _j for all j. Since the LP is a minimization problem, λj _j must take smallest possible value at the optimal, and hence must be 1 for all j∈[k]j∈[k]. If the number of classes k=1k=1, then At=At,1A_t=A_t,1 and hence any constraint involving μ (i.e., with At≠0A_t≠ 0) has the coefficient of λ1 _1 as non-negative. Thus, at optimality λ1 _1 takes the smallest possible value and equals λ1∗=1λ^*_1=1. If k≥2k≥ 2, then any constraint involving μ (i.e., with At≠0A_t≠ 0) that has negative coefficient of λj _j for any j∈[k]j∈[k] is implied by another constraint with positive coefficient of λj _j. To see this, fix t such that At≠0A_t≠ 0 and say λp _p has a negative coefficient; this implies At,p=0A_t,p=0 and bp>0b_p>0. Note that At≠0A_t≠ 0 implies that al+xl>0a_l+x_l>0 for some l∈[k]l∈[k] and l≠pl≠ p. Then (56) at such t equals μ μ ≥ ≥ 1+λlalAt,l=1−λpbp 1+ _la_l 1_\A_t,l=1\- _pb_p (57) +∑j∈[k]\p,lλj[ajAt,j=1−bjAt,j=0]. + _j∈[k] \p,l\ _j[a_j 1_\A_t,j=1\-b_j 1_\A_t,j=0\]. Consider another t~∈ℐℛ t∈ I_ R such that bl=1b_l=1, bp=0b_p=0 and rest of the components of t~ t match with those at t. Then (56) at t~ t equals μ μ ≥ ≥ 1+λlalAt,l=1 1+ _la_l 1_\A_t,l=1\ (58) +∑j∈[k]\p,lλj[ajAt,j=1−bjAt,j=0]. + _j∈[k] \p,l\ _j[a_j 1_\A_t,j=1\-b_j 1_\A_t,j=0\]. Clearly, (58) implies (57). Similar reasoning follows for all λj _j with negative coefficients. Hence, at optimality λj∗=1λ^*_j=1 for all j∈[k]j∈[k]. ■ Proof of Theorem 3 We first prove part (i). Consider the case when κ<nκ<n. Then there are κ+1κ+1 classes: κ classes for blind and isolated agents and one class for the normal agents. Without loss of generality, let tjt_j for j=1,…,κ1j=1,…, _1 correspond to blind agents, and for j=κ1+1,…,κj= _1+1,…,κ correspond to isolated agents. Let tκ+1t_κ+1 correspond to normal agents. Any f with fj(1)≤0f_j(1)≤ 0 for any j∈[k]j∈[k] has the PoA zero. Now consider f with fj(1)>0f_j(1)>0 for all j. The constraint in the LP deriving the PoA for such f is given by (52). Consider a t∈ℐℛt∈ I_ R with a1,…aκ=1a_1,… a_κ=1, xκ+1=1x_κ+1=1 and rest of the components zero. Then At≠0A_t≠ 0 and Bt≠0B_t≠ 0 so that (52) becomes μ μ ≥ ≥ 1+∑j∈[κ]λjfj(1)≥ 1+κ 1+ _j∈[κ] _jf_j(1)\ ≥\ 1+κ (59) where the second inequality follows from (53). Using similar logic as in (55), we obtain pPoA(f,w,,) pPoA(f,w, C, N) ≤ ≤ 11+κ when κ<n. 11+κ when κ<n. (60) When κ=nκ=n, then there are n classes with each class having exactly one agent who cannot observe any other agent. Consider a t∈ℐℛt∈ I_ R such that a1,…an=1a_1,… a_n=1 and the rest of the components are zero. Using similar arguments as above we obtain pPoA(f,w,,) pPoA(f,w, C, N) ≤ ≤ 1n when κ=n. 1n when κ=n. (61) Using (60) and (61), pPoA(f,w,,) pPoA(f,w, C, N) ≤ ≤ max11+κ,1n for any κ∈[n]. \ 11+κ, 1n \ for any κ∈[n]. 22.76219pt (62) Now we prove part (i) using our LP (21) in the following. Consider κ<nκ<n, then (52) at fmc=(f1mc,…,fjmc)f mc=(f mc_1,…,f mc_j) equals (56). By Lemma 6, at optimality in LP (21), λj∗=1 _j^*=1 for all j. Thus, the optimal μ∗μ^* satisfies (let l:=κ+1l:=κ+1), μ∗At≠0 μ^* 1_\A_t≠ 0\ ≥ ≥ ∑j∈[κ][ajaj+xj=1−bjaj+xj=0] _j∈[κ][a_j 1_\a_j+x_j=1\-b_j 1_\a_j+x_j=0\] (63) +alAt,l=1−blAt,l=0+Bt≠0. +a_l 1_\A_t,l=1\-b_l 1_\A_t,l=0\+ 1_\B_t≠ 0\. Now observe that if t is such that alAt,l=1=1a_l 1_\A_t,l=1\=1, then ajaj+xj=1=0a_j 1_\a_j+x_j=1\=0 for all j∈[κ1]j∈[ _1] by the definition of blind and normal agents and (20). The RHS of (63) for such t can at most be 1+κ21+ _2 which is obtained when aj=1a_j=1 for all j=κ1+1,…,κj= _1+1,…,κ, bj>0b_j>0 for some j∈[κ1]j∈[ _1] and rest of the components are zero. If t∈ℐℛt∈ I_ R is such that alAt,l=1=0a_l 1_\A_t,l=1\=0, then the RHS of (63) is at most 1+κ1+κ which is obtained when aj=1a_j=1 for all j∈[κ]j∈[κ], bl>0b_l>0 and rest of the components are zero. Since 1+κ>1+κ21+κ>1+ _2, the optimal μ∗=1+κμ^*=1+κ, and PoA equals 11+κ 11+κ. When κ=nκ=n, then the RHS of (63) is at most n which is achieved at aj=1a_j=1 for all j, thus μ∗=nμ^*=n, and the PoA equals 1n 1n. Thus, PoA(fmc,w,,)=max11+κ,1n for κ∈[n]. PoA(f mc,w, C, N)= \ 11+κ, 1n \ for κ∈[n]. (64) This proves part (i). Towards part (i), observe that the case of κ≥n−1κ≥ n-1 is exactly the same as the case of κ=nκ=n in part (i), and has the PoA of 1n 1n achieved at marginal contribution. Now consider and the marginal contribution utility generating mechanism and note that the optimal μ∗μ^* satisfies the following: μ∗At≠0≥Bt≠0+∑j∈[κ+1][ajaj+xj=1−bjaj+xj=0]μ^* 1_\A_t≠ 0\≥ 1_\B_t≠ 0\+ _j∈[κ+1][a_j 1_\a_j+x_j=1\-b_j 1_\a_j+x_j=0\] (65) The most binding constraint is obtained at t∈ℐℛt∈ I_ R such that aj=1a_j=1 for all j∈[κ+1]j∈[κ+1], bj=1b_j=1 for some j, and rest of the components are zero. This implies μ∗=2+κμ^*=2+κ, hence the PoA at marginal contribution equals 12+κ 12+κ. Thus the proof. ■ Proof of Theorem 4 Since there exist classes l∈ C_l∈ C and p∈ C_p∈ C such that p∉l C_p ∈ N_l, by Theorem 2, pPoA(f,w,,)≤12 pPoA(f,w, C, N)≤ 12. The constraint in the LP (21) deriving the PoA when w(⋅)w(·) satisfies (12) and fj=fjmcf_j=f mc_j as in (3) for all j∈[k]j∈[k] is given by (56). Let (μ∗,λ1∗,…,λk∗)(μ^*,λ^*_1,…,λ^*_k) represent the optimal solution of this LP, then by Lemma 6, μ∗μ^* satisfies the following for all t∈ℐℛt∈ I_ R such that At≠0A_t≠ 0: μ∗≥Bt≠0+∑j∈[k][ajAt,j=1−bjAt,j=0].μ^*≥ 1_\B_t≠ 0\+ _j∈[k][a_j 1_\A_t,j=1\-b_j 1_\A_t,j=0\]. (66) For a network (,)( C, N) as in theorem hypothesis, there can be at most one index j∈[k]j∈[k] such that ajAt,j=1=1a_j 1_\A_t,j=1\=1 for any t∈ℐℛt∈ I_ R . To see this, say a1At,1=1a_1 1_\A_t,1=1\, this is possible only when a1=1a_1=1, x1=0x_1=0 and aj=xj=0a_j=x_j=0 for all j∈1\1j∈ O_1 \1\ which implies ajAt,j=1=0a_j 1_\A_t,j=1\=0 for such j. Further, all j∈[k]\1j∈[k] O_1 must satisfy 1∈j C_1∈ N_j by the theorem hypothesis, which implies ajAt,j=1=0a_j 1_\A_t,j=1\=0 as a1=1a_1=1. Thus for all t∈ℐℛt∈ I_ R Bt≠0+∑j∈[k][ajAt,j=1−bjAt,j=0] 1_\B_t≠ 0\+ _j∈[k][a_j 1_\A_t,j=1\-b_j 1_\A_t,j=0\] ≤ ≤ 2 2 where the equality is achieved for a t∈ℐℛt∈ I_ R such that a1=1a_1=1 and bj=1b_j=1 for some j≠1j≠ 1. Hence μ∗=2μ^*=2, and the PoA at fmcf mc equals 12 12. Thus the proof. ■ Proof of Theorem 5 Let ¯⊆ C C denote the set of ‘blind’ or ‘isolated’ classes, then k1=|¯|k_1=| C|. Towards part (i), the constraint in the LP deriving PoA for any f equals (52). When k1<k_1<k, consider a t∈ℐℛt∈ I_ R with aj=1a_j=1 for all j∈[k]j∈[k] such that j∈¯ C_j∈ C, xj=1x_j=1 for some j∈[k]j∈[k] such that j∈\¯ C_j∈ C C, and all other components zero. Since λj≥1fj(1) _j≥ 1f_j(1) by (53), the constraint (52) at such t gives μ μ ≥ ≥ 1+k1, thus 1+k_1, thus pPoA(f,w,,) pPoA(f,w, C, N) = = 1μ∗≤1μ≤11+k1. 1μ^*\ ≤\ 1μ\ ≤\ 11+k_1. (67) When k1=k_1=k, consider the constraint in the LP (52) deriving PoA for any f at t∈ℐℛt∈ I_ R with aj=1a_j=1 for all j∈[k]j∈[k] and all other are components zero. Since λj≥1fj(1) _j≥ 1f_j(1) by (53), the constraint becomes μ≥kμ≥ k and using similar arguments as in (67), we get pPoA(f,w,,) pPoA(f,w, C, N) ≤ ≤ 1k. 1k. (68) This proves part (i). Toward part (i), consider the marginal contribution utility generating mechanism (3). The constraint for any t∈ℐℛt∈ I_ R is then given by (56). By Lemma 6 the optimal solution (μ∗,λ1∗,…,λk∗)(μ^*,λ^*_1,…,λ^*_k) satisfies (66). Observe that the RHS of (66) has the following upper bound: Bt≠0+∑j∈[k]ajAt,j=1. 1_\B_t≠ 0\+ _j∈[k]a_j 1_\A_t,j=1\. (69) Since kb,kn≥1k_b,k_n≥ 1, let p C_p be the blind class. By definition, there exists some l C_l such that p∈l C_p∈ N_l. Hence either apAt,p=1=1a_p 1_\A_t,p=1\=1 or alAt,l=1=1a_l 1_\A_t,l=1\=1; both terms cannot be simultaneously positive since p∈l C_p∈ N_l. Hence, the term in (69) is at most k, thus at optimality, μ∗≤k thus PoA(fmc,w,,)=1μ∗≥1k. μ^*≤ k thus PoA(f mc,w, C, N)\ =\ 1μ^*\ ≥\ 1k. (70) This proves part (i). Toward part (i), when kb=0k_b=0 and ki,kn≥1k_i,k_n≥ 1, note that there exists no p∈¯ C_p∈ C and l∈\¯ C_l∈ C C such that p∈l C_p∈ N_l, the term in (69) is at most 1+k1+k, thus μ∗≤k thus PoA(fmc,w,,)=1μ∗≥11+k. μ^*≤ k thus PoA(f mc,w, C, N)\ =\ 1μ^*\ ≥\ 11+k. (71) When kn=0k_n=0 and hence k1=kb+ki=k_1=k_b+k_i=k, consider the marginal contribution as in (3). The constraint deriving PoA for any t∈ℐℛt∈ I_ R is then given by (56). Note that the most binding constraints are the ones with t such that aj=1a_j=1, xj=0x_j=0 and bj=1b_j=1 for all j∈[k]j∈[k]. That is, μ μ ≥ ≥ 1+∑j∈[k]λj. 1+ _j∈[k] _j. By Lemma 6 we get μ∗=1+kμ^*=1+k, and hence pPoA(f,w,,)≥11+k pPoA(f,w, C, N)≥ 11+k. This proves part (i). ■ References References [1] Castelli, L., Pesenti, R., & Ranieri, A. (2011). “The design of a market mechanism to allocate air traffic flow management slots.” Transportation research part C: Emerging technologies, 19(5). [2] Vossen, T. (2002). “Fair allocation concepts in air traffic management.” PhD thesis, University of Maryland, College Park, MD. [3] Alexis, K., Nikolakopoulos, G., Tzes, A., & Dritsas, L. (2009). “Coordination of helicopter UAVs for aerial forest-fire surveillance.” Applications of intelligent control to engineering systems, 169-193. [4] Kuntze, Helge-Björn, Christian W. Frey, Igor Tchouchenkov, Barbara Staehle, Erich Rome, Kai Pfeiffer, Andreas Wenzel, and Jürgen Wöllenstein. “Seneka-sensor network with mobile robots for disaster management.” In 2012 IEEE Conference on Technologies for Homeland Security (HST), p. 406-410. IEEE, 2012.” [5] Pita, James, Manish Jain, Janusz Marecki, Fernando Ordóñez, Christopher Portway, Milind Tambe, Craig Western, Praveen Paruchuri, and Sarit Kraus. “Deployed armor protection: the application of a game theoretic model for security at the los angeles international airport.” In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: industrial track, p. 125-132. 2008. [6] Spieser, K., Treleaven, K., Zhang, R., Frazzoli, E., Morton, D., & Pavone, M. (2014). “Toward a systematic approach to the design and evaluation of automated mobility-on-demand systems: A case study in Singapore.” Road vehicle automation, 229-245. [7] Servant, A., Qiu, F., Mazza, M., Kostarelos, K., & Nelson, B. J. (2015). “Controlled in vivo swimming of a swarm of bacteria-like microrobotic flagella.” Advanced Materials, 27(19), 2981-2988. [8] Ishiyama, K., Sendoh, M., & Arai, K. I. (2002). “Magnetic micromachines for medical applications.” Journal of Magnetism and Magnetic Materials, 242, 41-46. [9] Paccagnan, D., Chandan, R., & Marden, J. R. (2019). “Utility design for distributed resource allocation—part i: Characterizing and optimizing the exact price of anarchy.” IEEE Transactions on Automatic Control, 65(11), 4616-4631. [10] Paccagnan, D., & Marden, J. R. (2021). “Utility design for distributed resource allocation—part i: Applications to submodular, covering, and supermodular problems.” IEEE Transactions on Automatic Control, 67(2), 618-632. [11] Vetta, A. (2002, November). “Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions.” In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. (p. 416-425). IEEE. [12] Gairing, M. (2009, December). “Covering games: Approximation through non-cooperation.” In International Workshop on Internet and Network Economics (p. 184-195). Berlin, Heidelberg: Springer Berlin Heidelberg. [13] Ramaswamy, V., Paccagnan, D., & Marden, J. R. (2021). “Multiagent maximum coverage problems: The tradeoff between anarchy and stability.” IEEE Transactions on Automatic Control, 67(4), 1698-1712. [14] J. H. Seaton and P. N. Brown, “On the Intrinsic Fragility of the Price of Anarchy,” in IEEE Control Systems Letters, vol. 7, p. 3573-3578, 2023 [15] B. C. Collins, S. Xu and P. N. Brown, “A Coupling Approach to Analyzing Games with Dynamic Environments,” in IEEE Transactions on Automatic Control, 2025. [16] Papadimitriou, C. (2001, July). “Algorithms, games, and the internet.” In Proceedings of the thirty-third annual ACM symposium on Theory of computing (p. 749-753). [17] Brown, P. N., Seaton, J. H., & Marden, J. R. (2023). “Robust networked multiagent optimization: designing agents to repair their own utility functions.” Dynamic Games and Applications, 13(1), 187-207. [18] Grimsman, D., Ali, M. S., Hespanha, J. P., & Marden, J. R. (2018). “The impact of information in distributed submodular maximization.” IEEE Transactions on Control of Network Systems, 6(4), 1334-1343. [19] Grimsman, D., Seaton, J. H., Marden, J. R., & Brown, P. N. (2020, December). “The cost of denied observation in multiagent submodular optimization.” In 2020 59th IEEE Conference on Decision and Control (CDC) (p. 1666-1671). IEEE. [20] Grimsman, D., Brown, P. N., & Marden, J. R. (2022, December). “Valid utility games with information sharing constraints.” In 2022 IEEE 61st Conference on Decision and Control (CDC) (p. 5739-5744). IEEE. [21] Seaton, J. H., & Brown, P. N. (2022). “All stable equilibria have improved performance guarantees in submodular maximization with communication-denied agents.” IEEE Control Systems Letters, 6, 2491-2496. [22] Marden, J. R., & Shamma, J. S. (2012). “Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation.” Games and Economic Behavior, 75(2), 788-808. [23] Nash Jr, J. F. (1950). “Equilibrium points in n-person games.” Proceedings of the national academy of sciences, 36(1), 48-49. [24] Monderer, D., & Shapley, L. S. (1996). “Potential games.” Games and economic behavior, 14(1), 124-143. [25] Fudenberg, D., & Levine, D. K. (1998). “The theory of learning in games” (Vol. 2). MIT press. [26] Bertsimas, D., & Tsitsiklis, J. N. (1997). “Introduction to linear optimization” (Vol. 6, p. 479-530). Belmont, MA: Athena Scientific. [27] https://github.com/vsvartika/Network-Games [28] Ferguson, B. L., Paccagnan D., Pradelski, B. S. R., and Marden, J. R., “Collaborative Coalitions in Multi-Agent Systems: Quantifying the Strong Price of Anarchy for Resource Allocation Games,” in 2023 62nd IEEE Conference on Decision and Control (CDC), Dec. 2023, p. 3238–3243. [29] [1] Y. Filmus and J. Ward, “Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search,” SIAM J. Comput., vol. 43, no. 2, p. 514–542, Jan. 2014. Vartika Singh (Member, IEEE) received the Bachelor of Technology in Textile Chemistry from Dr. A.P.J. Abdul Kalam Technical University, Lucknow, Uttar Pradesh, India in 2018. She received the Master of Technology and PhD in Industrial Engineering and Operations Research from Indian Institute of Technology Bombay, Mumbai, Maharashtra, India in 2024. After graduating, she worked as a postdoctoral research associate in the Department of Computer Science at the University of Colorado Colorado Springs until 2025 under the supervision of Philip N. Brown. Her research interests include multi-agent coordination using game theory and competitive Markov decision processes. Philip N. Brown (Member, IEEE) is an Associate Professor in the Department of Computer Science at the University of Colorado Colorado Springs and a Spring 2026 Visiting Professor at the Politecnico di Torino. Philip received the Bachelor of Science in Electrical Engineering in 2007 from Georgia Tech. He received the Master of Science in Electrical Engineering in 2015 from the University of Colorado at Boulder under the supervision of Jason R. Marden, where he was a recipient of the University of Colorado Chancellor’s Fellowship. He received the PhD in Electrical and Computer Engineering from the University of California, Santa Barbara under the supervision of Jason R. Marden. He received the 2018 CCDC Best PhD Thesis Award from UCSB, the Best Paper Award from GameNets 2021, a 2023 AFOSR Young Investigator Program award, a 2025 NSF CAREER award, and a 2025 ARO Early Career Program award. Philip is interested in the interactions between engineered and social systems.