The Impact of Local Information on the Performance
of Multiagent Systems

arXiv:1710.01409v1 [cs.GT] 3 Oct 2017

Vinod Ramaswamy, Dario Paccagnan, and Jason R. Marden
Abstract
How does the control architecture of a multiagent system impact the achievable performance guarantees? In this paper we answer this question relative to
a class of resource allocation problems, termed multiagent set covering problems.
More specifically, we demonstrate how the degree of information available to each
agent imposes constraints on the achievable efficiency guarantees associated with
the emergent collective behavior. We measure these efficiency guarantees using the
well-known metrics of price of anarchy and price of stability, which seek to bound the
performance of the worst and best performing equilibria, respectively. Our first result demonstrates that when agents only know local information about the resources
they can select, a system operator is forced to manage an inherent trade-off between
the price of anarchy and price of stability, i.e., improving the quality of the worst
equilibria comes at the expenses of the best equilibria. Our second result demonstrates that a system operator can move well beyond this price of anarchy / price
of stability frontier by designing a communication protocol that provides agents
with a limited amount of system-level information beyond these local quantities.

Introduction
There is no denying the fact that multiagent systems represent the systems of the future,
with wide ranging applications in cooperative robotics [1], resource and task allocation [2],
supply chain management [3], surveillance [4], among others. One concrete example is the
problem of monitoring the perimeter of a wild fire, where the goal is to deploy a collection
of unmanned aerial vehicles (UAV), each making independent surveillance decisions in
response to local information [5]. While technological developments have paved the way
Date: October 3, 2017
This work is supported by SNSF Grant #P1EZP2-172122, ONR Grant #N00014-15-1-2762 and NSF
Grant #ECCS-1351866.
V. Ramaswamy was with the Department of Electrical, Computer, and Energy Engineering, University
of Colorado at Boulder. D. Paccagnan and J. R. Marden are with the Department of Electrical and
Computer Engineering, University of California, Santa Barbara, USA, dariop@control.ee.ethz.ch,
jrmarden@ece.ucsb.edu. D. Paccagnan is also with the Automatic Control Laboratory, Swiss Federal
Institute of Technology, Zurich, Switzerland.

1

for the realization of such futuristic systems, our basic understanding of networked control
architectures and of the role of information, has ultimately hindered their realization.
A multiagent system can be characterized by a collection of individual subsystems,
each making independent decisions in response to locally available information. At a high
level, the design of a networked control architecture entails specifying two key elements:
the information available to each subsystem, attained either through sensing or communication, and a decision-making mechanism that prescribes how each subsystem processes
available information to take decisions. The need for distributed decision-making stems
from the scale, spacial distribution, and sheer quantity of information associated with
such systems which excludes the possibility for centralized decision making. For example,
in the problem of monitoring the perimeter of a wild fire, each individual UAV may be
required to make surveillance choices using only information regarding its own aerial view
of the landscape as well as minimal information regarding the location of neighboring
UAVs due to limited communication capabilities.
The quality of a networked control architecture is ultimately gauged by several dimensions including the stability and efficacy of the emergent collective behavior, characteristics
of the transient behavior, as well as the level of information propagated throughout the
system. Two central questions associated with the design process that we seek to address
in this paper are as follows:
(i) What are the decision-making rules that optimize the performance of the emergent
collective behavior for a given level of information?
(ii) What is the value of information in networked control architectures? That is, how
does informational availability translate to attainable performance guarantees for
the emergent behavior through the design of appropriate decision-making mechanisms?
For example, how do information limitations to the UAVs impact the quality at which
the UAVs can collectively monitor the perimeter of a wild fire?
Multiagent surveillance problems highlight several challenges inherent to the design
of such networked control architectures [6, 7]. For this class of problems, the goal is to
derive local decision-making rules for the individual subsystems (i.e., sensors) ensuring
that sensors efficiently allocate themselves over a given mission space without the need
for centralized coordination. A common assumption in the existing literature is that each
2

subsystem is endowed with information pertaining to its local environment as well as the
surveillance choices of neighboring sensors [6]. Within these confines, researchers have
established a wide range of local decision-making rules that ensure the collective behavior will settle at an allocation; however, the performance guarantees associated with this
allocation have often been overlooked. Motivated by this omission, recent work in [8]
characterizes the best attainable performance guarantees as a function of the underlying
informational dependencies for such multi-agent surveillance problems. For systems comprised of n sensor, [8] demonstrates that any decision-making rule that relies solely on
local information can at best guarantee that the resulting collective behavior is within
(1/n) of the optimal system behavior. However, if agents are equipped with slightly more
information regarding the state of the system, this impossibility result vanishes and one
can easily design networked architectures with a limiting behavior that is guaranteed to
be within (1/2) of the optimal behavior [8]. The resounding message from the result above
is that informational dependencies play a fundamental role in the attainable performance
guarantees associated with networked control architectures.
The goal of this paper is to shed further light on the interplay between informational
availability and performance guarantees for a class of set covering problems. Covering
problems consist of a collection of resources, each with a respective value or worth, and
a collection of agents, each capable of covering various subsets of resources. The overarching goal is to establish a networked control architecture that allows agents to reach
the optimal allocation through a process where the individual agents adjust their covering choice based on available information. Of specific interest will be identifying how
the information available to the individual agents impacts the attainable performance
guarantees associated with the underlying architecture.
We approach this problem through a game theoretic lens where we model the individual
agents as players in a game and each agent is associated with a local objective function
that guides its decision-making process [9]. We treat these local objective functions as
our design parameter and focus our analysis on characterizing the performance guarantees
associated with the resulting equilibria of the designed game. An equilibrium of a game is
an outcome where each agent is satisfied with their choice given the choices of the other
agents. We concentrate our analysis on two well-studied performance metrics in the game
theoretic literature termed the price of anarchy and price of stability [10, 11]. Informally,
the price of anarchy seeks to provide performance guarantees associated with the worst
3

performing equilibrium relative to the optimal allocation. The price of stability, on the
other hand, seeks to provide similar performance guarantees when restricting attention to
the best performing equilibrium. The lack of uniqueness of equilibria implies that these
bounds are often quite different.
Our first result concentrates on deriving the agent objective functions that optimize
the quality of the resulting equilibria when individual agents are only aware of information
regarding the resources they can select. For this class of informational dependencies, we
show that there does not exist agent objective functions that simultaneously optimize
both the price of anarchy and price of stability. Rather, there is a fundamental trade-off
between these two performance measures. In other words, improving the performance of
the worst equilibrium necessarily comes at the expense of the performance of the best
equilibrium. In Theorem 3, we characterize this fundamental trade-off and identify the
agent objective functions that reach this price of anarchy / price of stability frontier. This
result is one of the first in the existing literature that demonstrates a fundamental tradeoff between the price of anarchy and price of stability. Whether or not this trade-off is a
more fundamental feature of networked architectures is an open and interesting question.
Our second result seeks to address the question of whether providing the agents with
additional information, i.e., system-level attributes beyond information relative to the
local resources, can permit the design of networked architectures with performance guarantees breaching this frontier. In Theorem 4, we answer this question in the affirmative
as we identify a minimal (and easily attainable) piece of system-level information that
can permit the realization of decision-making rules with performance guarantees beyond
the price of anarchy / price of stability frontier provided in Theorem 3. It is important to
stress that the specific make-up of this information is not necessarily important; rather,
the importance of this result centers on the fact that certain attributes of the system can
be exploited in networked architectures if those attributes are propagated to the agents.
Minimizing the amount of information that needs to be propagated throughout the system to move beyond the frontier is clearly an important question that warrants future
attention.

4

Model and Performance Metrics
In this section we introduce the multiagent set covering problem and our game theoretic
model for the design of local decision-making mechanisms [12]. Further, we define the
objectives and performance metrics of interest, as well as provide a review of the relevant
literature.

Covering problems
Let R = {r1 , r2 , . . . , rm } be a finite set of resources where each resource r ∈ R is associated
with a value vr ≥ 0 defining its importance. We consider a covering problem where the
goal is to allocate a collection of agents N = {1, . . . , n} to resources in R in order to
maximize the cumulative value of the covered resources. The set of possible assignments
for each agent i ∈ N is given by Ai ⊆ R and we express an allocation by the tuple
a = (a1 , a2 , . . . , an ) ∈ A = A1 × · · · × An .2 The total value, or welfare, associated with
an allocation a is given by
X

W (a) =

vr .

r∈∪i∈N ai

The goal of the covering problem is to find an optimal allocation, i.e., an allocation
aopt ∈ A such that W (aopt ) ≥ W (a) for all a ∈ A.3 We will often express an allocation
a as (ai , a−i ) with the understanding that a−i = (a1 , . . . , ai−1 , ai+1 , . . . , an ) denotes the
collection of choices of the agents other than agent i.

A game theoretic model
This paper focuses on deriving distributed mechanisms for attaining near optimal solutions
to covering problem where the individual agents make independent covering choices in
response to local available information. Specifically, in this section we assume that each
2

Many of the forthcoming results hold for the more general multi-selection covering problem where
each agent’s action set is of the form Ai ⊆ 2R . However, in this paper we present solely the singleton
selection problem for a more direct exposition.
3
Approximation algorithms for finding a near optimal solution to such covering problems, or more
general submodular optimization problems, have been extensively studied in the literature [13, 14, 15, 16].
The focus of this literature is predominantly on centralized algorithms for finding near optimal allocations.
By centralized, we mean a computer program that takes in the full problem specification and outputs an
allocation. In contrast, our focus is on distributed solutions where there is no such central authority and
each decision-making entity has incomplete information about the system as a whole.

5

agent i has information only regarding the resources that the agent can select, i.e., the
resources Ai ⊆ R. Rather than directly specifying a decision-making process, here we
focus on the design of local agent objective functions that adhere to these informational
dependencies and will ultimately be used to guide the agents’ selection process. To that
end, we consider the framework of distributed welfare games [9] where each agent is
associated with a local utility or objective function Ui : Ai → R and for any allocation
a = (ai , a−i ) ∈ A, the utility of agent i is
Ui (ai = r, a−i ) = vr · f (|a|r ),

(1)

where |a|r captures the number of agents that choose resource r in the allocation a, i.e.
the cardinality of the set {i ∈ N : ai = r}, and f : N → R defines the fractional benefit
awarded to each agent for selecting a given resource in allocation a.4 We will refer to f as
the distribution rule throughout. Note that an agent’s utility function in (1) is consistent
with the local information available as it only depends on the resource that the agent
selected, the number of agents that also selected this resource, as well as the distribution
rule f and relevant resource value vr . We will express such a welfare sharing game by the
tuple G = {N, R, {Ai }i∈N , f, {vr }r∈R } and drop the subscripts on the above sets, e.g.,
denote {vr }r∈R as simply {vr }, for brevity.
The goal of this paper is to derive the distribution rule f that optimizes the performance of the emergent collective behavior. Here, we focus on the concept of pure Nash
equilibrium as a model for this emergent collective behavior [17]. A pure Nash equilibrium, which we will henceforth refer to as just an equilibrium, is defined as an allocation
ane ∈ A such that for all i ∈ N and for all ai ∈ Ai , we have
ne
ne
Ui (ane
i , a−i ) ≥ Ui (ai , a−i ).

In essence, an equilibrium represents an allocation for which no single agent has a unilateral incentive to alter its covering choice given the choices of the other agents. It is
important to highlight that an equilibrium might not exist in a general game G. Nevertheless, when restricting attention to the class of games with utility functions defined in (1),
an equilibrium is guaranteed to exist as the resulting game is known to be a congestion
game [18].5
4

The sets N and R denote the sets of natural and real numbers, respectively.
There is a rich body of literature that provides distributed decision-making mechanisms that ensures
the emergent collective behavior will reach an equilibrium for the class of games considered in this paper
[19, 20, 21, 22, 23]. However, we will not discuss such results due to space considerations.
5

6

We will measure the efficiency of an equilibrium allocation in a game G through two
commonly studied measures, termed price of anarchy and price of stability, defined as
follows:
W (ane )
PoA(G) = min
≤ 1,
ane ∈G W (aopt )
W (ane )
≤ 1,
PoS(G) = max
ane ∈G W (aopt )
where we use the notation ane ∈ G to imply an equilibrium of the game G. In words, the
price of anarchy characterizes the performance of the worst equilibrium of G relative to
the performance of the optimal allocation, while the price of stability focuses on the best
equilibrium in the game G. Such distinction is required as equilibria are guaranteed to
exists for the class of utilities considered in (1), but in general they are not unique. By
definition 0 ≤ PoA(G) ≤ PoS(G) ≤ 1.
Throughout, we require that a system designer commits to a distribution rule without
explicit knowledge of the agent set N , resource set R, action sets {Ai }, and resource
valuations {vr }. Note that once a particular distribution rule f has been chosen, this
distribution rule defines a game for any realization of the parameters. The objective of
the system designer is to provide desirable performance guarantees irrespective of the
realization of these parameter, even if they where chosen by an adversary. To that end,
let Gf denote the family of games induced by a given distribution rule f , i.e., any game
G ∈ Gf is of the above form. We will measure the quality of a distribution rule f by a
worst-case analysis over the set of induced games Gf , which is the natural extension of
the price of anarchy and price of stability defined above, i.e.,
PoA(Gf ) = min PoA(G),

(2)

PoS(Gf ) = min PoS(G).

(3)

G∈Gf

G∈Gf

The price of anarchy PoA(Gf ) for a given distribution rule f provides a bound on the
quality of any equilibrium irrespective of the agent set N , resource set R, action sets
{Ai }, and resource valuations {vr }. The price of stability, on the other hand, provides
similar performance guarantees when restricting attention to the best equilibrium.6
The goal of this paper is to investigate the design of distribution rules that optimize
the metrics introduced in (2) and (3).
6

One motivation for studying the price of stability is the availability of distributed learning rules that
lead the collective behavior to the best equilibrium, e.g., [24, 25, 26].

7

Related work
The field of utility design has been receiving significant research attention due to applicability to multiagent systems [23, 27, 28] and social influence [29]. Utility design focuses on
the design of agent objective functions geared at providing some desired features in the
resulting game, e.g., existence of equilibria, efficiency of equilibria, among others. While
recent work in [30] has identified all design approaches that ensure equilibrium existence
in local utility designs, in general the question of optimizing the efficiency of the resulting
equilibria, i.e., optimizing the price of anarchy, is far less understood. Nonetheless, there
are a few positive results in this domain worth reviewing. The most notable result is
[12] which focuses on the same set covering problem presented in this manuscript. In
[12], the author characterizes the distribution rule f that optimizes the price of anarchy;
however, there is no mention of the accompanying price of stability or the uniqueness
of the prescribed rule. Further, there is no characterization of the price of anarchy for
alternative distribution rules. Different setups where optimizing the price of anarchy has
been explored include concave cost sharing games [31], reverse carpooling games [32],
among others. The bulk of the research regarding optimal utility design has concentrated
on a specific class of objectives, termed budget-balanced objectives, which imposes the
constraint that the sum of the agents’ objectives is equal to the system welfare for every
allocation. With regards to the objective functions considered in (1), the only design that
satisfies this budget-balanced constraint is
1
fes (j) = ,
j

∀j ≥ 1,

(4)

where we use the notation “es” to signify equal share. Within the confines of budgetbalanced agent objective functions, several works have identified the optimality of the
Shapley value objective design with regards to the price of anarchy guarantees [33, 34, 35].7
However, the imposition of this budget-balanced constraint is unwarranted in the context
of multiagent system design and its removal allows for improved performance, as shown
in [12] and in this manuscript.8
7
Informally, the Shapley value objective design extends the equal share design in (4) to more general
settings beyond set covering.
8
The work of [12] demonstrates how to design a distribution rule in order to optimize the efficiency as
measured by the price of anarchy. Building on these results, this manuscript is geared at quantifying the
efficiency as measured by the price of stability, as well as to understand the role of information within
the class of covering problems.

8

An illustrative example
In this section we consider a simple family of covering problems consisting of two agents,
N = {1, 2}, and three resources, R = {r1 , r2 , r3 }, to illustrate the challenges that a
system designer faces when designing a distribution rule f without explicit knowledge of
the action sets A1 and A2 and the resource valuations v1 , v2 , and v3 .
We begin by investigating the efficiency guarantees associated with the unique budgetbalanced distribution rule in (4). Consider one problem instance where A1 = {r1 },
A2 = {r1 , r2 }, and v1 = 2, v2 = 0.99, and v3 = 0. Note that agent 1 is fixed at resource r1
for this instance. The payoff matrix and system welfare for the different allocations are:
Agent 2
r1
r2
1, 1
2, 0.99

Agent 1 r1

Agent 2
r1
r2
2
2.99

Agent 1 r1

Payoff Matrix

System Welfare

In each box of the payoff matrix, the first entry is the payoff to agent 1 and the second
entry is the payoff to agent 2. Note that for this instance, there is a unique equilibrium
(r1 , r1 ) which garners a total welfare of 2. The optimal total welfare is 2.99; hence the price
of anarchy and price of stability satisfy PoA(Gfes ) ≤ 2/2.99 ≈ 0.67 and PoS(Gfes ) ≤ 0.67.
Consider an alternative distribution rule, termed marginal contribution, that is of the
form


fmc (k) =

if k = 1,
otherwise.

1
0

(5)

Note that employing the marginal contribution distribution rule for the problem instance
drawn above induces a unique equilibrium (r1 , r2 ) which is the optimal allocation.
However, consider an alternative problem instance where A1 = {r1 , r2 }, A2 = {r2 , r3 },
and v1 = 1.99, v2 = 2, and v3 = 0.01. The payoff matrix and system welfare for the
different allocations are:
Agent 2

Agent 1

r1
r2

r2
1.99, 2
0, 0

Agent 2

r3
1.99, 0.01
2, 0.01

Agent 1

Payoff Matrix

r1
r2

r2
r3
3.99
2
2
2.01

System Welfare

9

Note that for this instance, there are now two equilibria, namely (r1 , r2 ) and (r2 , r3 ), while
the optimal allocation is (r1 , r2 ). Hence the price of anarchy and price of stability must
satisfy PoA(Gfmc ) ≤ 2.01/3.99 ≈ 0.5 and PoS(Gfmc ) ≤ 1.
These case studies suggest that fmc outperforms fes with regards to the price of stability, while fes outperforms fmc with regards to the price of anarchy. However, whether or
not these conclusion hold more generally for alternative parameters sets is, at this stage,
very much unclear. While specific examples provide upper bounds on the price of stability / price of anarchy, a completely different set of techniques will have to be employed
to provide lower bounds on these efficiency measures. Characterizing both the lower and
upper bounds associated with these efficiency measures is essential to adequately compare
the performance guarantees associated with any two distribution rules.9

Results
In this section we characterize the inherent tension between the price of anarchy and
price of stability as design objectives. We begin our analysis by strengthening the results
in [12] to attain a tight price of anarchy for any distribution rule f . We then proceed
to characterize the achievable price of stability guarantees. We further highlight the
implications on the price of stability associated with requiring a desired price of anarchy.
Finally, we show how to move beyond the price of anarchy / price of stability frontier
given in Theorem 3 if we allow the agents to condition their choice on a higher degree
of system-level information. The proofs of the forthcoming theorems will be presented in
the Supplementary Materials.

A tight price of anarchy
Recall that Gf is the set of set covering games induced by a given distribution rule f .
We now introduce a subset of these games that impose constraints on the maximum
9

A natural question is whether the locality requirement specified in the agents’ utility functions in (1)
is detrimental from a performance perspective. To address this question, suppose that a system designer
was able to directly set each agent’s utility function as the global welfare, i.e., Ui = W , which clearly
violates our locality condition. Observe that, within the last example highlighted above, Ui = W produces
the same equilibria that fmc induces. Hence, the price of anarchy is at best 0.5 for the case when Ui = W .
As we will see in the ensuing section, there are alternative utility designs conforming to (1) that guarantee
a better price of anarchy than 0.5. Hence, while setting Ui = W might seem a natural choice to optimize
the price of anarchy, there are alternative choices that are local and yield far better results.

10

number of agents that could select a single resource. More formally, let Gfk ⊂ Gf , k ≥ 1,
denote the family of games where at most k agents can select any single resource, i.e.
G = {N, R, {Ai }, f, {vr }} ∈ Gfk if
max |a|r ≤ k.

a∈A, r∈R

We will refer to the games Gfk as games with cardinality k..
Our first result strengthens the findings of [12] to obtain a tight price of anarchy for
any distribution rule f over each set of games Gfk , where k ≥ 1.
Theorem 1 Consider any non-increasing distribution rule f and cardinality k ≥ 1. The
price of anarchy associated with the induced family of games Gfk is
PoA(Gfk ) =

1
,
1 + χkf

(6)

where
χkf = max

1≤j≤k−1

{j · f (j) − f (j + 1), (k − 1) · f (k)} .

(7)

Further, the optimal price of anarchy is
max PoA(Gfk ) = 1 −
f

1
1
(k−1)(k−1)!

+

Pk−1 1 ,

(8)

i=1 i!

and the unique distribution rule that achieves this price of anarchy over the induced games
Gfk is, for all 1 ≤ j ≤ k
k
fgar
(j) = (j − 1)!

1
(k−1)(k−1)!
1
(k−1)(k−1)!

+

Pk−1 1 !

+

Pk−1

i=j i!
1
i=1 i!

.

(9)

The importance of Theorem 1 is that it allows us to explicitly compute the price
of anarchy for any given distribution rule. This characterization will be crucial in the
forthcoming section, where we present the trade-off between price of anarchy and price
of stability. Further, this characterization allows us to optimize the price of anarchy
over admissible distribution rules f and thus to obtain (9). We will commonly refer to
k
fgar
as Gairing’s distribution rule conditioned on instances of cardinality k to reflect its
origination in [12].

11

A tight price of stability
In this section we turn our attention to the other performance metric of interest, the price
of stability. Our goal here parallels our objective in the preceding section as we attempt
to derive a tight price of stability for any distribution rule f . The following theorem gives
such a characterization.
Theorem 2 Consider any non-increasing distribution rule f and cardinality k ≥ 1. The
price of stability associated with the induced family of games Gfk is


1
k
PoS(Gf ) = min
.
(10)
1≤j≤k
1 + (j − 1) · f (j)
Further, the optimal price of stability is
max PoS(Gfk ) = 1,
f

(11)

and the unique distribution rule that achieves this price of stability over the induced games
Gfk is the marginal contribution distribution rule fmc defined in (5).
k
Figure 1 illustrates the unique distribution rule fgar
that optimizes the price of anarchy
given in Theorem 1 and the unique distribution rule fmc that optimizes the price of

stability given in Theorem 2.

A trade-off between the anarchy and stability
The previous two subsections highlight how the structure of f impacts both the price of
anarchy and price of stability guarantees. In this section we seek to identify the compatibility (or lack thereof) of these two measures of efficiency. That is, how do requirements
on the price of anarchy impact the attainable price of stability? The following theorem
provides an answer to this question.
Theorem 3 Consider any cardinality k ≥ 1 and desired price of anarchy α satisfying
0 ≤ α ≤ maxf PoA(Gfk ) as defined in (8).
(i) For any non-increasing distribution rule f , if PoA(Gfk ) ≥ α, then the price of stability satisfies10
PoS(Gfk ) ≤ Z k (α) ,
10

The expression of Z k (α) is given in (26) in the Supplementary Materials.

12

(12)

1

fgar
fmc

0.8
0.6
f (j)

0.4
0.2
0

1

2

3

4

5

6

7

8

9 10

k
j fmc (j) fgar
f (j)
1
1
1
2
0
0.418
3
0
0.254
4
0
0.180
5
0
0.139
6
0
0.113
7
0
0.095
8
0
0.082
9
0
0.072
10
0
0.065

j
Figure 1: Optimal distribution rules. This figure illustrates the unique distribution
k
that optimizes the price of anarchy given in Theorem 1 and the unique distrirule fgar
bution rule fmc that optimizes the price of stability given in Theorem 2; k = 10. The
corresponding values are presented in the table.
where Z k (α) is non-increasing in α, Z k (α) = 1 for all α ≤ 0.5, and
lim Z k (1 − 1/e) = 1 − 1/e.

k→∞

(ii) The bound in (12) is tight, i.e., maxf :PoA(Gfk )≥α PoS(Gfk ) = Z k (α).
The results of Theorem 3 are illustrated in Figure 2 where we highlight the plausible
price of anarchy / price of stability region. In particular, Theorem 3-(i) establishes that
there does not exist a distribution rule f that attains a price of stability and price of
anarchy in the red region of the figure. Hence, there is an inherent tension between
these two measures of efficiency as improving the performance of the worst equilibria
necessarily comes at the expense of the best equilibria, and vice versa. The expression of
Z k (α) defines this trade-off. The second claim of Theorem 3 guarantees that the bound
obtained in (12) is tight, i.e., there are distribution rules that achieve price of anarchy
and price of stability guarantees that lie exactly on the boundary of the red region.

Adding Information
The previous section highlights a fundamental tension between the price of stability and
price of anarchy for the given covering problem when restricted to local agent objective
13

1
not achievable

0.8

Z(α)

0.6

(1 − 1e , 1 − 1e )

PoS

0.4
0.2
0

0

0.2

0.4

0.6

0.8

1

PoA
Figure 2: Tradeoff between anarchy and stability. The figure provides an illustration of the inherent trade-off between the price of anarchy and price of stability. For
simplicity, we define Z(α) = limk→∞ Z k (α) and illustrate this trade-off in the case of large
k. First, note that the grey region is not achievable since 0 ≤ PoA(Gfk ) ≤ PoS(Gfk ) ≤ 1 by
definition. Theorem 3 demonstrates that the red region is also not achievable. That is,
there does not exist a distribution rule with joint price of anarchy and price of stability
guarantees in the red region. For example, if α ≤ 1/2, then a price of stability of 1 is
attainable while meeting this price of anarchy demand. However, if α = 1 − 1/e, then a
price of stability of 1 is no longer attainable. In fact, the best attainable price of stability
is now also 1 − 1/e.

functions of the form (1). In this section, we challenge the role of locality in these fundamental trade-offs. That is, we show how to move beyond the price of anarchy / price of
stability frontier given in Theorem 3 if we allow the agents to condition their choice on a
higher degree of system-level information.
With this goal in mind, we introduce a minimal and easily attainable piece of systemlevel information that can permit the realization of decision-making rules with efficiency
guarantees beyond this frontier. To that end, for each allocation a ∈ A we define the
information flow graph (V, E) where each node of the graph represents an agent and we
14

Agent i
1
2
3
4
5

Ni (a)
{2, 3, 4}
{3, 4}
{2, 4}
{2, 3}
∅

Qi (a)
A1 ∪ A2 ∪ A3 ∪ A4
A2 ∪ A 3 ∪ A4
A2 ∪ A 3 ∪ A4
A2 ∪ A 3 ∪ A 4
A5

Figure 3: Example of graph (V, E). The sets Ni (a) and Qi (a) are enumerated for
each agent in the table on the right. Observe that the graph (V, E) as well as the sets
Ni (a) and Qi (a) are allocation dependent.
construct a directed edge i → j if ai ∈ Aj for i 6= j (no self loops). Based on this
allocation-dependent graph, we define for each agent i the set Ni (a) ⊆ N consisting of all
the agents that can reach i through a path in the graph (V, E). Similarly, for each agent
i we define
Qi (a) = ∪j∈Ni (a) Aj ∪ Ai ,

(13)

which consists of the union of Ai and all the sets of other agents that can reach i through
a path in the graph. An example is shown in Figure 3. Lastly, building upon this graph
we define the following two quantities:
Vi (a) =
xi (a) =

max vr ,

(14)

max vr .

(15)

r∈Ai \a−i

r∈Qi (a)\a

The term Vi (a) captures the highest valued resource in agent i’s choice set Ai that is not
covered by any agent. If the set Ai \ a−i is empty, we set Vi (a) = 0. Similarly, the term
xi (a) captures the highest-valued resource in the enlarged set Qi (a) not currently covered
by any other agent. If the set Qi (a) \ a is empty, we set xi (a) = 0.
We are now ready to specify the information based game. As before, we have a
set of agents N and each agent has an action set Ai ⊆ R. Here, we consider a statebased distribution rule that toggles between the two extreme optimal distribution rules:
Gairing’s rule and the marginal contribution rule. More formally, the distribution rule for
agent i is now of the form
(
fmc (|a|r ) if Vi (a) ≥ xi (a),
fik (ai = r, a−i ) =
(16)
k
fgar
(|a|r ) otherwise,
15

and the corresponding utilities are given by Ui (ai = r, a−i ) = vr · fik (a), as we allow the
system-level information xi (a) and Vi (a) to prescribe which distribution rule each agent
k
applies. We denote with fsb
= {fik }i∈N the collection of distribution rules in (16) and
informally refer to it as to the state-based distribution rule.11
k
The next theorem demonstrates how fsb
attains performance guarantees beyond the

price of stability / price of anarchy frontier established in Theorem 3.
k
Theorem 4 Consider any cardinality k ≥ 1 and let fsb
= {fik }, where fik is defined

in (16). First, an equilibrium is guaranteed to exist in any game G ∈ Gfkk . Furthermore,
sb

the price of anarchy and price of stability associated with the induced family of games Gfkk
sb
is
PoS(Gfkk ) =1,
sb

PoA(Gfkk ) = max PoA(Gfk ).
sb

f

We remark on Theorem 4 for the case when k → ∞ for ease of exposition. Note that
for this case, a consequence of attaining a price of anarchy of 1−1/e was a price of stability
also of 1 − 1/e and this was achieved using Gairing’s distribution rule in (9). Using the
state-based rule given in (16), a system designer can achieve the optimal price of anarchy
without any consequences for the price of stability. Hence, the identified piece of systemlevel information was crucial for moving beyond the inherited performance limitations by
adhering to our notion of local information. Whether alternative forms of system-level
information could move us beyond these guarantees, or achieve these guarantees with less
information, is an open research question.

Conclusions
How should a system operator design a networked architecture? The answer to this question is non-trivial and involves weighing the advantages and disadvantages associated
with different design choices. In this paper we highlight one novel trade-off pertaining to
the price of anarchy and price of stability in set covering problems with local information. Further, we demonstrate how a system designer can move beyond these limitations
by equipping the agents with additional information about the system. Fully realizing
11

We express the distribution rule as fik (a) instead of merely fik (xi (a), Vi (a)) for brevity.

16

the potential of multiagent systems requires to pursue a more formal understanding of
the inherent limitations and performance trade-offs associated with networked architectures. While this paper focused purely on two performance measures, other metrics
of interest include convergence rates, robustness to adversaries, fairness, among others. In each of these settings, it is imperative that a system operator fully understands
the role of information within these trade-offs. Only then, will a system operator be
able to effectively balance the potential performance gains with the communication costs
associated with propagating additional information through the system.

References
[1] M. J. B. Krieger, J.-B. Billeter, L. Keller, Ant-like task allocation and recruitment
in cooperative robots, Nature 406, 992–995 (2000).
[2] B. P. Gerkey, M. J. Mataric, A formal analysis and taxonomy of task allocation in
multi-robot systems, The International Journal of Robotics Research 23, 939–954
(2004).
[3] A. S. L. El Yasmine, B. A. Ghani, D. Trentesaux, B. Bouziane, Supply Chain Management Using Multi-Agent Systems in the Agri-Food Industry (Springer, 2014), pp.
145–155.
[4] D. Vallejo, P. Remagnino, D. N. Monekosso, L. Jiménez, C. González, A Multi-agent
Architecture for Multi-robot Surveillance (Springer, 2009), pp. 266–278.
[5] K. Alexis, G. Nikolakopoulos, A. Tzes, L. Dritsas, Coordination of Helicopter UAVs
for Aerial Forest-Fire Surveillance (Springer, 2009), pp. 169–193.
[6] S. Martinez, J. Cortes, F. Bullo, Motion coordination with distributed information,
Control Systems Magazine 27, 75–88 (2007).
[7] F. Bullo, J. Cortés, S. Martı́nez, Distributed Control of Robotic Networks (Princeton
University Press, 2009).
[8] J. Marden, IEEE Transactions on Control of Network Systems , (2016). Available at
http://ieeexplore.ieee.org/document/7451235. (paper published online before
print).
17

[9] J. R. Marden, A. Wierman, Distributed welfare games, Operations Research 61,
155–168 (2013).
[10] E. Anshelevich, et al., The price of stability for network design with fair cost allocation, in Proceedings of the 45th Annual IEEE Symposium on Foundations of
Computer Science (2004), pp. 295–304.
[11] E. Koutsoupias, C. Papadimitriou, Worst-Case Equilibria (Springer, 1999), pp. 404–
413.
[12] M. Gairing, Covering Games: Approximation through Non-cooperation (Springer,
2009), pp. 184–195.
[13] G. Nemhauser, L. Wolsey, M. Fisher, An analysis of approximations for maximizing
submodular set functions – I, Mathematical Programming 14, 265–294 (1978).
[14] G. Nemhauser, L. Wolsey, M. Fisher, An analysis of approximations for maximizing
submodular set functions – II (Springer), pp. 73–87.
[15] U. Feige, J. Vondrak, Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e, in Proceedings of the 47th Annual IEEE Symposium on
Foundations of Computer Science (FOCS’06) (2006), pp. 667–676.
[16] A. Krause, C. Guestrin, Near-optimal observation selection using submodular functions, in Proceedings of the 22nd Conference on Artifical Intelligence (2007).
[17] J. F. Nash, Equilibrium points in n-person games, Proceedings of the National
Academy of Sciences 36, 48–49 (1950).
[18] D. Monderer, L. S. Shapley, Potential games, Games and Economic Behavior 14,
124 – 143 (1996).
[19] H. P. Young, Individual Strategy and Social Structure: An Evolutionary Theory of
Institutions (Princeton University Press, 1998).
[20] H. P. Young, Strategic Learning and its Limits (Oxford University Press, 2005).
[21] D. Fudenberg, D. Levine, The Theory of Learning in Games (MIT Press, 1998).

18

[22] J. R. Marden, G. Arslan, J. S. Shamma, Joint strategy fictitious play with inertia
for potential games, IEEE Transactions on Automatic Control 54, 208–220 (2009).
[23] J. Marden, J. Shamma, Handbook of Game Theory Vol. 4 (Elsevier, 2014), pp. 861–
899.
[24] J. R. Marden, J. S. Shamma, Revisiting log-linear learning: Asynchrony, completeness and a payoff-based implementation, Games and Economic Behavior 75, 788–808
(2012).
[25] L. Blume, The statistical mechanics of strategic interaction, Games and Economic
Behavior 5, 387–424 (1993).
[26] L. Blume, The Economy as an evolving complex system II (Addison-Wesley, 1997),
pp. 425–460.
[27] J. R. Marden, G. Arslan, J. S. Shamma, Connections between cooperative control
and potential games, IEEE Transactions on Systems, Man and Cybernetics. Part B:
Cybernetics 39, 1393–1407 (2009).
[28] D. Paccagnan, J. R. Marden, The risks and rewards of conditioning noncooperative
designs to additional information, in Proceedings of the 55th IEEE Allerton Conference on Communication, Control, and Computing (2017).
[29] P. N. Brown, J. R. Marden, Studies on robust social influence mechanisms: Incentives
for efficient network routing in uncertain settings, IEEE Control Systems 37, 98–115
(2017).
[30] R. Gopalakrishnan, J. R. Marden, A. Wierman, Potential games are necessary to ensure pure nash equilibria in cost sharing games, Mathematics of Operations Research
39, 1252–1296 (2014).
[31] J. R. Marden, M. Philips, Optimizing the price of anarchy in concave cost sharing
games, in Proceedings of the 2017 American Control Conference (2017), pp. 5237–
5242.
[32] J. R. Marden, M. Effros, The price of selfishness in network coding, IEEE Transactions on Information Theory 58, 2349–2361 (2012).
19

[33] P. von Falkenhausen, T. Harks, Optimal cost sharing for resource selection games,
Mathematics of Operations Research 38, 184–208 (2013).
[34] P. von Falkenhausen, T. Harks, Optimal cost sharing for capacitated facility location
games, European Journal of Operations Research 239, 187–198 (2014).
[35] H.-L. Chen, T. Roughgarden, G. Valiant, Designing network protocols for good equilibria, SIAM Journal on Computing 39, 1799–1832 (2010).

Supplementary Materials
Proof of Theorem 1
The distribution rule maximizing the price of anarchy and the corresponding optimal
value of (8) are derived in [12] by means of a different approach. Thus, in the following
we only show the tight bound of (6).
Proof: For any non increasing distribution rule, [12] proves that the price of anarchy
satisfies PoA(Gfk ) ≥

1
1+χkf

. We will show that PoA(Gfk ) ≤

1
1+χkf

holds too, which will

complete the proof. To do so, note that by definition
χkf = max {j · f (j) − f (j + 1), (k − 1) · f (k)}.
1≤j≤k−1

Hence, we can distinguish two cases. For each of them we will construct an instance of
covering game that achieves PoA(Gfk ) =

1
,
1+χkf

thus completing the proof.

i) χkf = j · f (j) − f (j + 1) for some 1 ≤ j ≤ k − 1.
First, suppose f (j) > f (j + 1) and define γ = f (j + 1)/f (j) < 1. Consider the
instance given in Figure S1, where there are j agents at each of the m + 1 levels
(m > 0). Each agent is represented by a solid line and the circles at either end
of the line indicate the choices available to that agent. In particular, in Level 0
there are j agents and j + 1 resources of which j valued at γ 0 f (j) and a single one
valued at γ 0 . At each subsequent level k > 0, there are j agents and j resources
of which j − 1 valued at γ k f (j) and a single one valued at γ k . Further, at each
level k > 0 one of the agents can choose between the common element at level k or
the common at level k − 1. The equilibrium allocation ane consists of all the agents

20

0

f (j)

0

f (j)

Level 0

1

f (j)

1

f (j)

f (j)

0

f (j)

m

f (j)

Level m

m

f (j)

0

0

...

Level 1

m

1

1

m

f (j)

f (j)

=

f (j+1)
f (j)

Figure S1: First instance used in case i).

selecting the common resource to their right in Figure S1. This produces a welfare
m+1
of W (ane ) = 1 + γ + · · · + γ m = 1−γ
, which in the limit of m → ∞ reduces to
1−γ
W∞ (ane ) =

1
.
1−γ

The optimal allocation aopt covers all resources, except one of those valued γ m f (j),
yielding a total welfare of W (aopt ) = W (ane ) + W (ane )(j − 1)f (j) + f (j)(1 − γ m ),
which in the limit of m → ∞ reduces to
W∞ (aopt ) =W∞ (ane )(1 + (j − 1)f (j)) + f (j)
=W∞ (ane )(1 + jf (j) − f (j + 1))
=W∞ (ane )(1 + χkf ) ,
from which the desired result follows:

W∞ (ane )
W∞ (aopt )

=

1
.
1+χkf

Now, suppose f (j) = f (j + 1). Consider the instance given in Figure S2, consisting
of j agents and j + 1 resources, one of them valued at 1 and j − 1 valued at f (j).
One equilibrium allocation ane consists of all the agents selecting the resource to
their right, producing a welfare of W (ane ) = 1. On the other hand, the optimum
yields W (aopt ) = (j − 1)f (j) + 1 = (jf (j) − f (j + 1) + 1) = χkf + 1, and hence
W (ane )
1
= 1+χ
k.
W (aopt )
f

21

0

f (j)

0

f (j)

1

m

f (j)

f (j)

=

f (j)

f (j)

1

f (j)

f (j)

Figure S2: Second instance used in case i).

ii) χkf = (k − 1)f (k). The second instance discussed in the previous case applies here
as well, with j = k. This completes the proof.


Proof of Theorem 2
The distribution rule maximizing the price of stability and the corresponding optimal
value of (11) are trivial to obtain, once the result in (10) is proven. Before proceeding
with showing the latter, we observe that we can restrict our attention to games G ∈ Gfk
where there is an optimal allocation that is disjoint, i.e., there is an optimal allocation aopt
such that aopt
6= aopt
for any i 6= j. The following claim, stated without proof, formalizes
i
j
this observation.
Claim 1 Let Ḡfk ⊆ Gfk be the set of games where each game G ∈ Ḡfk has an optimal
allocation that is disjoint. The price of stability and price of anarchy satisfy
PoA(Ḡfk ) = PoA(Gfk ),
PoS(Ḡfk ) = PoS(Gfk ).
Throughout the remainder of the proof, we will concentrate on games that possess
22

f

an optimal allocation that is disjoint. We will continue to denote the game set as Gfk as
opposed to Ḡfk for ease of presentation.
We will prove the above price of stability result through a series of intermediate claims.
A central piece of the forthcoming analysis is the focus on a particular sequence of allocations a0 , a1 , . . . , am derived from a series of unilateral deviations of players switching
from their choice in the equilibrium allocation to their choice in the optimal allocation.
We begin by observing that any game G in the class Gfk is a congestion game, and thus is
a potential game as introduced in [18], with a potential function φ : A → R of the form12
φ(a) =

|a|r
XX

vr · f (j).

(17)

r∈R j=1

It is well-known that an equilibrium is guaranteed to exist in any potential game [18],
and one such equilibrium is the allocation that optimizes the potential function φ, i.e.,
ane ∈ arg maxa∈A φ(a). Focusing on this specific equilibrium, we consider a sequence of
k−1
allocations taking the form a0 = ane and ak = (aopt
i(k) , a−i(k) ) for all k ∈ {1, . . . , m} where

i(k) is the deviating player in the k-th profile. The selection of the deviating players
I = {i(1), . . . , i(m)} is chosen according to the following rules:
(i) Let i(1) ∈ N be any arbitrary player.
opt
ne
(ii) For each k ≥ 1, if aopt
/ ane then the sequence is terminated.
i(k) = ai (1) or ai(k) ∈

(iii) Otherwise, let i(k + 1) be any agent in the set {j ∈ N : akj = aopt
i(k) } and repeat.
opt
Claim 2 Define Q = ∪i∈I ane
i and Q̄ = ∪i∈I ai . Then
X
X
X
Ui (ane ) ≥
vr f (|ane |r ) +
vr .
i∈I

r∈Q∩Q̄

(18)

r∈Q̄\Q

Proof: We begin with two observations on the above sequence of allocations: (a) the
sequence of allocations can continue at most n steps due to the disjointness of aopt and
opt
(b) if the sequence continues, it must be that for player i(k+1) ane
i(k+1) = ai(k) . Observation

(b) ensures us that
m−1
X

Ui(k+1) (ak ) − Ui(k) (ak ) = 0.

k=1
12

A proof of this can be found in [18], where the potential function φ is also defined.

23

(19)

Accordingly, we have that
φ(a0 ) − φ(am ) =
=

m−1
X
k=0
m−1
X

φ(ak ) − φ(ak+1 )
Ui(k+1) (ak ) − Ui(k+1) (ak+1 )

k=0
0

m

0

m

= Ui(1) (a ) − Ui(m) (a ) +

m−1
X

Ui(k+1) (ak ) − Ui(k) (ak )

k=1

= Ui(1) (a ) − Ui(m) (a ) ≥ 0 .
The first and third equalities follow by rearranging the terms. The second equality can
be shown using the definition of φ as in (17); the last equality follows by (19). The
inequality derives from the fact that a0 = ane optimizes the potential function. Thanks
to observation (b), one can show that
opt
Q \ Q̄ = ane
i(1) \ ai(m)

ne
and Q̄ \ Q = aopt
i(m) \ ai(1) .

opt
opt
ne
If Q \ Q̄ 6= ∅, it must be that ane
i(1) 6= ai(m) so that Q \ Q̄ = ai(1) and Q̄ \ Q = ai(m) . Using
opt
opt
ane
/ ane and thus the resource aopt
i(1) 6= ai(m) in condition (ii), tells us that ai(m) ∈
i(m) is not

chosen by anyone else in the allocation am . Thus, when Q \ Q̄ 6= ∅,
X
X
Ui(1) (a0 ) − Ui(m) (am ) =
vr f (|ane |r ) −
vr ≥ 0.
r∈Q\Q̄

(20)

r∈Q̄\Q

When Q \ Q̄ = ∅, also Q̄ \ Q = ∅ and thus the previous inequality still holds. Rearranging
P
the terms and adding r∈Q∩Q̄ vr f (|ane |r ) to each side gives us
X
X
X
vr f (|ane |r ) ≥
vr f (|ane |r ) +
vr .
(21)
r∈Q

r∈Q∩Q̄

r∈Q̄\Q

Finally note that
X
i∈I

Ui (ane ) ≥

X

vr f (|ane |r )

r∈Q

which together with (21) completes the proof.



Our second claim shows that there exist a collection of disjoint sequences that covers
all players in N . We will express a sequence merely by the deviating player set I with
the understanding that this set uniquely determines the sequence of allocations.
24

Claim 3 There exists a collection of deviating players I 1 , . . . , I p chosen according the
process described above such that ∪k I k = N and I j ∩ I k = ∅ for any j 6= k.
Proof: Suppose I 1 , I 2 , . . . , I k represent the first k sequences of deviating players. Further
assume that they are all disjoint. Choose some player i ∈ N \ ∪k I k to start the (k + 1)th sequence. If no such player exists, we are done. Otherwise, construct the sequence
according to the process depicted above. If the sequence terminates without selecting a
player in ∪k I k , then repeat this process to generate the (k + 2)-th sequence. Otherwise,
let ik+1 (j), j ≥ 2, denote the first player in the (k + 1)-th sequence contained in the set
∪k I k . Since aopt
6= aopt
(for i 6= j), this player must be contained in the set ∪k ik (1), i.e.,
i
j
the first player in a previous sequence. Suppose this player is i` (1), where ` ∈ {1, . . . , k}.
If this is the case, replace the `-th sequence with {ik+1 (1), . . . , ik+1 (j − 1), I ` } which is a
valid sequence and disjoint from the others. Then repeat the process above to choose the
(k + 1)-th sequence. Note that this process can continue at most n-steps and will always
result in a collection of disjoint sequences that cover all players in N . This completes the
proof.



In the following we complete the proof of Theorem 2, by means of Claims 2 and 3.
Proof: We being showing a lower bound on the price of stability. Let I 1 , . . . , I p denote
a collection of deviating players that satisfies Claim 3. Further, let Qk and Q̄k be defined
as above for each sequence k = 1, . . . , p. Using the result (18) from Claim 2, we have
X

ne

Ui (a ) =

p
X
X

Ui (ane )

k=1 i∈I k

i∈N

≥

p
X

X


k=1

=




vr f (|ane |r ) +

r∈Qk ∩Q̄k

X

X

vr f (|ane |r ) +

r∈aopt ∩ane

vr 

r∈Q̄k \Qk

X

vr ,

r∈aopt \ane

where the above equality follows from the fact that Q̄i ∩ Q̄j = ∅ for any i 6= j which is
due to the disjointness of aopt . Using the definition of Ui (ane ), we have
X
X
X
vr |ane |r f (|ane |r ) +
vr (|ane |r − 1) f (|ane |r ) ≥
r∈ane ∩aopt

r∈ane \aopt

r∈aopt \ane

Define γ = maxj≤n (j − 1)f (j). Working with the above expression we have
X
X
X
vr (γ + 1) +
vr γ ≥
vr ,
r∈ane \aopt

r∈ane ∩aopt

25

r∈aopt \ane

vr .

which gives us that
(γ + 1)W (ane ) ≥ W (aopt )
which completes the lower bound.
We will now provide an accompanying upper bound on the price of stability. To that
end, consider a family of examples parameterized by a coefficient j ∈ {1, . . . , k}. For each
j, the game consists of j agents and (j +1)-resources R = {r0 , r1 , . . . , rj } where the values
of the resources are vr0 = 1 and vr1 = · · · = vrj = f (j) − ε where ε > 0 is an arbitrarily
small constant, and the action set of each agent i ∈ {1, . . . , j} is Ai = {r0 , ri }. The unique
equilibrium is of the form ane = (r0 , . . . , r0 ) as every agent selects resource r0 and the total
welfare is W (ane ) = 1. The optimal allocation is of the form aopt = (r0 , r2 , . . . , rj ) which
generates a total welfare of W (aopt ) = 1 + (j − 1)(f (j) − ε). Performing a worst case
analysis over ε and j gives


1
PoS(Gf ) ≤ min
1≤j≤k
1 + (j − 1) · f (j)
which completes the proof.



Proof of Theorem 3
Observe that χkf defined in (7) can be equivalently characterized as the solution to the
the following optimization problem
χkf = min x
s. t j · f (j) − f (j + 1) ≤ x,

1 ≤ j ≤ k − 1,

(k − 1) · f (k) ≤ x.
This allows us to state the following corollary, which will be useful to prove Theorem 3.
Corollary 1 Let Fαk , α ∈ (0, 1), denote the family of distribution rules that guarantee a
price of anarchy of at least α in games with cardinality k ≥ 1, i.e.,
Fαk = {f : PoA(Gfk ) ≥ α}.
Then, the set Fαk is uniquely defined by the set of distribution rules f that satisfy the
following k-linear equations,
1
− 1,
α
1
(k − 1)f (k) ≤ − 1.
α

j · f (j) − f (j + 1) ≤

26

∀j ≤ k − 1,

Finally, let us define
PoS(G k ; α) = max PoS(Gfk )
k
f ∈Fα

(22)

as the best achievable price of stability given that the price of anarchy is guaranteed to
exceed α, where α ∈ (0, 1).
We will now state an enriched version of Theorem 3 using the notation just introduced,
as this allows for a more precise proof.
Theorem 5 Let k ≥ 1. The function PoS(G k ; α) satisfies the following:
i) For any α ≤ 1/2, PoS(G k ; α) = 1.
ii) For any α satisfying

1
2

< α ≤ maxf PoA(Gfk ),
PoS(G k ; α) =

1
,
1 + ξαk

where
ξαk = max (j − 1)(j − 1)! 1 −
j≤k



!
X
j−1
1
1
−1
.
α
i!
i=1

(23)

(24)

iii) Lastly, if α = maxf PoA(Gfk ) then
PoS(G k ; α) = max PoA(Gfk ),
f

(25)

and limk→∞ PoS(G k ; α) = 1 − 1e .
Thus, the function Z k (α) introduced in Theorem 3 takes the form
(
1
if α ≤ 12
Z k (α) =
1
1 .
if
α
>
k
2
1+ξ

(26)

α

Proof: i) Consider the marginal contribution distribution rule fmc , defined in (5). It is
straightforward to verify that χkfmc = 1 and hence fmc ∈ Fαk for any α ≤ 1/2. Further, it
is well-known that PoS(Gfkmc ) = 1, see [23]. This completes the first part of the proof.
ii) We shift our attention to the price of stability. From Theorem 2 and (22) we have


1
k
.
(27)
PoS(G ; α) = max min
k j≤k
1 + (j − 1) · f (j)
f ∈Fα
27

The optimization problem in (27) is equivalent to
min max (j − 1) · f (j)
f
j≤k


1
s.t. j · f (j) −
− 1 ≤ f (j + 1),
α


1
(k − 1)f (k) ≤
−1 .
α

∀j ≤ k − 1,

We find an optimal solution by first solving for the distribution rule that satisfies the k −1
linear inequalities with equality, followed by verifying that the resulting distribution rule
is non increasing. Such distribution rule can be computed recursively, and is of the form
(
! )

X
j−1
1
1
f (j) = max (j − 1)! 1 −
−1
,0 .
α
i!
i=1
Using Theorem 2 on such distribution rule, gives the desired result in (23).
iii) The final result can be proven as follows: replace α in (24) with the optimal price
of anarchy of (8), i.e., set
α=1−

1
1
(k−1)(k−1)!

+

Pk−1 1 .
i=1 i!

After some manipulation, ξαk in (24) becomes
ξαk = (1 − α) =

1
1
(k−1)(k−1)!

Thanks to (23), the price of stability reads as
Pk−1
1
+
i=1
(k−1)(k−1)!
PoS(G k ; α) =
Pk−1
1
+ i=0
(k−1)(k−1)!

+

1
i!
1
i!

Pk−1 1 .
i=1 i!

= max PoA(Gfk ) ,
f

proving the claim in (25). Taking the limit k → ∞ in the previous expression, gives the
final result.


Proof of Theorem 4
Proof of PoS result
We begin our proof with a lemma that identifies a structure about the state based distribution rule {fik }.
28

Lemma 1 Let a be any allocation. Then for each agent i ∈ N , one of the following two
statements is true.
- Ui (a0i = r, a−i ) = vr · fmc (|a−i | + 1), ∀a0i ∈ Ai ; or
- Ui (a0i = r, a−i ) = vr · fgar (|a−i | + 1), ∀a0i ∈ Ai .
Informally, this lemma states that for a given allocation a, the state based distribution
rule will either evaluate every resource at the marginal contribution distribution or every
resource at the Gairing distribution rule for a given agent i.
Proof: Let a be any allocation and i be any agent. Extend the definition of xi (a) in (15)
as
yi (a) =
zi (a) =

max
r∈(Qi (a)\a)∩Ai

max
r∈(Qi (a)\a)\Ai

vr ,

(28)

vr ,

(29)

and note that xi (a) = max{yi (a), zi (a)}. First observe that for any a0i ∈ Ai : (i) yi (a) ≤
Vi (a); (ii) zi (a) = zi (a0i , a−i ); and (iii) Vi (a) = Vi (a0i , a−i ). Accordingly, xi (a) > Vi (a) if and
only if xi (a) = zi (a). Consequently, xi (a) > Vi (a) if and only if xi (a0i , a−i ) > Vi (a0i , a−i )
which completes the proof.



We will now prove that an equilibrium exists and the price of stability is 1. In particular, we will show that the optimal allocation aopt is in fact an equilibrium.
Proof: Let aopt be an optimal allocation. We begin by showing that Vi (aopt ) ≥ xi (aopt )
for all i ∈ N . Suppose this was not the case, and there exists an agent i such that
Vi (aopt ) < xi (aopt ). This implies that there exists a resource r ∈ Qi (aopt ) \ aopt such that
vr > vr̃ = maxr0 ∈Ai :|aopt |=0 vr0 . By definition of Qi (a) and Ni (a) there exists a sequence
−i

of players {i0 , i1 , . . . , im } such that aopt
ik ∈ Aik−1 for all k ≥ 1, and r ∈ Aim . Hence,
consider a new allocation where aik = aopt
ik+1 for all k ∈ {0, . . . , m − 1} and aim = r,
where aj = aopt
for all other agents j ∈
/ {i0 , i1 , . . . , im }. The welfare of this allocation
j
is W (a) ≥ W (aopt ) + vr − vr̃ > W (aopt ), which contradicts the optimality of aopt . This
means that every agent will be using the marginal cost distribution rule to evaluate its
utility in the allocation aopt .
Now, suppose aopt is not an equilibrium for sake of contradiction. This means, that
opt
there exists an agent i with an action ai ∈ A such that Ui (ai , aopt
). Since
−i ) > Ui (a

29

agents are using the marginal contribution distribution rule, which follows from Vi (aopt ) ≥
xi (aopt ), we have
opt
opt
W (ai , aopt
) − Ui (aopt ) + Ui (ai , aopt
),
−i ) = W (a
−i ) > W (a

which contradicts the optimality of aopt . This completes the proof.



Informal discussion and proof of PoA result
Consider a game G = (N, R, {Ai }, {fik }, {vr }) with cardinality bounded by k. Let ane be
any equilibrium of the game G. A crucial part of the forthcoming analysis will center on
a new game G0 derived from the original game G and the equilibrium ane , i.e.,
(G, ane ) −→ G0 .
This new game G0 possesses the identical player set, resource set, and valuations of the
resources as the game G. The difference between the games are (i) the action sets and (ii)
k
, as opposed to the state-based
the new game G0 employs the Gairing distribution rule, fgar
k
distribution rule fsb
. Informally, the proof proceeds in the following two steps:

– Step 1: We prove that the equilibrium ane of G is also an equilibrium of G0 . Since the
player set, resource set, and valuations of the resources are unchanged we have that
W (ane ; G0 ) = W (ane ; G),
where we write the notation W (ane ; G0 ) to mean the welfare accrued at the allocation ane
in the game G0 .
0

– Step 2: We show that the optimal allocation aopt in the new game G0 is at least as
good as the optimal allocation in the original game G0 , i.e.,
0

W (aopt ; G0 ) ≥ W (aopt ; G).
Combining the results from Step 1 and Step 2 give us
W (ane ; G)
W (ane ; G0 )
≥
≥ PoA(Gfkgar
k ),
0
opt
opt
0
W (a ; G)
W (a ; G )
k
where the last inequality follows from Theorem 1 since G0 employs fgar
.

30

Construction of game G0 :
We will now provide the construction of the new game G0 from the game G and the
equilibrium ane . We begin with some notation that we will use to construct the new
agents’ action sets in the game G0 . For each i ∈ N , let ri = ane
i and define
k
k
Hi = {r ∈ Ai : vri · fgar
(|ane |ri ) < vr · fgar
(1 + |ane
−i |r )},

(30)

to be the set of resources that will give a strictly better payoff to agent i if the agent was
k
k
to use fgar
instead of fsb
. Further, denote

I = {i ∈ N : Hi 6= ∅},

(31)

k
as the set of agents that would move from the equilibrium ane if they were to use fgar
k
instead of fsb
. Finally, for each agent i ∈ I, let

Bi = {r0 ∈ Qi (ane ) : |ane |r0 = 0} ,

(32)

i.e. the enlarged set of resources of (13) that are not chosen by anyone at equilibrium.
We are now ready to construct the new game G0 . As noted above, the agent set,
resource set, and resource valuations are identical to those in G. The new action set of
each agent i in game G0 is defined as
(
(Ai \Hi ) ∪ Bi ∪ ∅
if i ∈ I ,
A0i =
Ai
otherwise .
k
. We denote this game G0
Lastly, the utility functions of the agents are derived using fgar
k
by the tuple G0 = (N, R, {A0i }, fgar
, {vr }).

Formal Proof of Step 1:
Proof: In the first part of the proof, we will establish that the equilibrium allocation ane
of game G is also an equilibrium allocation of game G0 . By definition of the action sets
0
{A0i }, we know that ane
i ∈ Ai for all agents i ∈ N . It remains to show that for any agent

i∈N
0
0
0
ne
0
0
ne
Ui (ane
i , a−i ; G ) ≥ Ui (ai , a−i ; G ), ∀ai ∈ Ai ,

(33)

where we use the notation Ui (a; G0 ) to denote the utility of agent i for allocation a in the
game G0 .
31

Based on the above definition of the action sets {A0i }, we only need to concentrate our
attention on agents i ∈ I with choices a0i ∈ Bi , as (33) follows immediately in the other
cases. Since ane is an equilibrium of game G, then by Lemma 1 we know that each agent
i ∈ I employs the marginal contribution distribution rule everywhere. Accordingly, we
have
ne
ne
ne
Ui (ane
i , a−i ; G) = maxne vr = Vi (a ) ≥ xi (a ),
r∈Ai \a−i

(34)

where the first equality follows from the equilibrium conditions coupled with the use of
the marginal contribution distribution rule and the inequality follows from the use of the
marginal contribution distribution rule and (16).
ne
We will conclude the proof by a case study on the potential values of Ui (ane
i , a−i ; G).

For brevity in the forthcoming arguments we let r = ane
i .
ne
ne
– Case (i): Suppose Ui (ane
i , a−i ; G) = 0. In this case, we have that xi (a ) = 0 from
ne
0
(34) which implies that any resource r0 ∈ Bi has value vr0 = 0. Hence, Ui (ane
i , a−i ; G ) =
0
Ui (r0 , ane
−i ; G ) = 0 and we are done.
ne
– Case (ii): Suppose Ui (ane
i , a−i ; G) > 0. Based on the definition of the marginal cost
distribution rule, this implies that |ane |r = 1, and hence
k
Ui (ane ; G) = vr fmc (|ane |r ) = vr fgar
(|ane |r ) = Ui (ane ; G0 ),
k
(1) = 1. Hence, Ui (ane ; G0 ) = vr . For any
which follows from the fact that fmc (1) = fgar

r0 ∈ Bi , we have
0
k
ne
ne
Ui (r0 , ane
i ; G ) = vr0 fgar (1 + |a−i |r0 ) = vr0 ≤ xi (a ),

where the last inequality follows for the definition of xi (ane ). Combining with (34) gives
us
ne
0
0 ne
0
Ui (ane
i , a−i ; G ) ≥ Ui (r , a−i ; G ),

which completes the proof.



Formal Proof of Step 2:
We begin with a lemma that highlights a structure associated with the action sets {A0i }
in the new constructed game G0 .

32

Lemma 2 If r ∈ A0i \ Ai for some agent i ∈ N and resource r ∈ R, then there exists an
0
agent j 6= i such that ane
j = r and consequently r ∈ Aj .

Proof: Suppose r ∈ A0i \ Ai for some agent i ∈ N and resource r ∈ R. Then, r ∈ Hi by
definition of the set A0i . By Lemma 1, each agent must either be a marginal contribution
agent, i.e., uses fmc at all resources, or a Gairing agent, i.e., uses fgar at all resources.
Since, i ∈ I and ane is an equilibrium, agent i must be a marginal contribution agent, i.e.,
ne
ne
ne
Ui (ane
i = r̃, a−i ) = vr̃ · fmc (|a |r̃ ) ≥ vr · fmc (|a−i |r + 1),

where the inequality follows from the equilibrium conditions. Suppose by contradiction
that |ane
−i |r = 0. In this case we have
ne
vr · fmc (|ane
−i |r + 1) = vr · fgar (|a−i |r + 1).

which follows from the fact that f mc (1) = f gar (1) = 1. Since fgar (k) ≥ fmc (k) for all
k ≥ 1, this implies
vr̃ · fgar (|ane |r̃ ) ≥ vr̃ · fmc (|ane |r̃ ) ≥ vr · fgar (|ane
−i |r + 1).
Hence, r ∈
/ Hi leading to the contradiction. This completes the proof.



We exploit the result of Lemma 2 to prove Step 2.
Proof: We conclude the proof by constructing an allocation a ∈ A0 that satisfies W (a; G0 ) =
W (aopt ; G) where aopt ∈ arg maxa∈A W (a; G). We begin with an initial allocation a where
for each agent i ∈ N
(
aopt
i
a=
∅

if aopt
∈ A0i ,
i
else ,

That is, we assign each agent the agent’s optimal allocation choice if it is available to
them in the new action set A0i . If all agents received their optimal choice, then the proof
is complete.
If this is not the case, then there will be a set of uncovered resources U(a) = {r ∈
aopt : |a|r = 0} which we denote by U(a) = {r1 , . . . , rm }. We will now argue that we can
construct a new allocation a0 that covers one additional resource from the set U(a), i.e.,
|U(a0 )| = |U(a)| − 1 and a ⊆ a0 , where we denote with |U(a)| the cardinality of U(a).
To that end, consider any uncovered resource r0 ∈ U(a). By definition, there exists an
agent i0 ∈ N such that aopt
/ A0i0 . Consequently, we have that r0 ∈ Hi0 and
i0 = r0 but r0 ∈
33

ne
by Lemma 2 we know that there exists an agent i1 6= i0 such that ane
i1 = r0 . Since ai1 = r0

we also have that r0 ∈ A0i1 by definition. We now analyze the following three cases:
– Case 1: Suppose ai1 = ∅. Then define a new allocation a0i1 = r0 and a0j = aj for all
j 6= i1 , and we are done.
– Case 2: Suppose ai1 = r1 and |ane |r1 = 0, meaning that there are no agents at the
resource r1 in the equilibrium allocation. Then by definition r1 ∈ Bi0 and r1 ∈ A0i0 .
Define the allocation a0i0 = r1 , a0i1 = r0 , and a0j = aj for all j 6= i0 , i1 and we are done.
– Case 3: Suppose ai1 = r1 and |ane |r1 > 0, meaning that there are agents at the resource
r1 in the equilibrium allocation. Select any agent i2 such that ane
i 2 = r1 .
(i) If ai2 = ∅, then consider the allocation a0i1 = r0 , a0i2 = r1 and a0j = aj for all j 6= i1 , i2
and we are done.
(ii) Otherwise, if ai2 = r2 , then let a0i1 = r0 , a0i2 = r1 , and repeat Case 2 or Case
3 depending on whether |ane |r2 = 0 or |ane |r2 > 0. Note that Case 3-(ii) can be
repeated at most n iterations until an alternative case that terminates is reached.
To see this, note that each time an agent is given a new choice in this process, i.e.,
ai → a0i 6= ai , the agent’s new choice is the agent’s equilibrium choice, i.e., a0i = ane
i .
Therefore, once an agent is assigned a new choice, the agent will never be reassigned
in this process.
Starting from a as defined above, the above process results in a new allocation a0 that
satisfies |U(a0 )| = |U(a)|−1 and a ⊆ a0 . As with the allocation a, the allocation a0 satisfies
maxr |a0 |r = 1 and a0 ⊆ aopt . If a0 = aopt , we are done. Otherwise, we can repeat the
process depicted above to generate a new allocation a00 such that |U(a00 )| = |U(a0 )| − 1 as
nowhere in the process did we rely on the fact that ai = aopt
i . Repeating these arguments
recursively provides the result.



34

