Section 4 and Section 5 brought all this machinery together and established
the existence and Lax stability of this new family of general relativistic
shock waves, and in doing so, provided a mechanism for exhibiting an
accelerated expansion whilst removing the central singularity from the static
isothermal sphere.

Given that it is possible to rigorously demonstrate the existence of a
Friedmann-static pure radiation shock wave, the obvious follow-up question is
whether it is possible to rigorously demonstrate the existence of the full
two-parameter family of Friedmann-static shock waves, with $\sigma$ included
in this parameter count. For a certain range of values of $\sigma$ and
$\bar{\sigma}$ there is every reason to expect this to be possible.

######  Conjecture 1.

For $0<\bar{\sigma}\leq\sigma\leq\frac{1}{3}$, there exists an $a>0$ such that
FLRW$(0,\sigma,a)$ can be matched to TOV$(\bar{\sigma})$ to form a general
relativistic shock wave.

The resolution of this conjecture is one avenue of future research. The
continuous dependence of the solution trajectories on the parameters means
that existence is all but guaranteed for
$\bar{\sigma},\sigma\approx\frac{1}{3}$ and $\bar{\sigma}\approx H(\sigma)$.
Moreover, the existence proof in the pure radiation case is readily modified
to demonstrate existence for any fixed pair
$0<\bar{\sigma}\leq\sigma\leq\frac{1}{3}$. The difficulty arises when
generalising the proof from fixed parameter values to two-dimensional
parameter spaces, since conservative estimates need to be satisfied for all
values of $\sigma$ and $\bar{\sigma}$ in such spaces. It is likely to be
possible to construct such a proof by patching together many subproofs
demonstrating existence in small two-dimensional parameter spaces, although
this method may be rather tedious.

Another avenue of future research is in regard to the possible cosmological
applications of Friedmann-static shock waves. It is shown in Section 3 that
the Friedmann-static pure radiation shock wave yields an acceleration
parameter value of $a\approx 2.58$. For reference, the acceleration parameter
that would be expected in the Radiation Dominated Epoch would likely satisfy
$a\approx 1$. However, the discussions of [9] and [10] imply that Friedmann-
static shock waves have shock fronts that lie within the Hubble radius, so
these shock waves are not viable cosmological models in the Radiation
Dominated Epoch. As mentioned in the introduction, Smoller and Temple
demonstrate in [9] that it is possible to construct a general relativistic
shock wave, with a shock surface beyond the Hubble radius, by modelling the
entire Universe as a finite mass explosion within the Schwarzschild radius of
a time-reversed black hole. However, this is only completed for an explicitly
known flat FLRW spacetime on the interior and not for a pure radiation
equation of state each side of the shock surface.

The possibility remains to construct a general relativistic pure radiation
shock wave with a shock surface beyond the Hubble radius and determine the
resulting rate of expansion. If after transition into the Matter Dominated
Epoch the predicted rate of expansion lies within current estimates, then this
mechanism offers a mathematically independent derivation for the cosmic
acceleration observed today without a cosmological constant, and thus, without
dark energy.

## Acknowledgements

This research would not have been possible without the patience, guidance and
endless encouragement of my doctoral advisor, Distinguished Professor Blake
Temple, so thank you Blake.

I would also like to extend my thanks to Distinguished Professor Craig Tracy
for partially funding this research from his NSF grant: _Integrable Structure
of Interacting Particle Systems_. This funding helped extend my doctoral
studies at UC Davis by two further years, providing invaluable time for the
completion of this research.

## References

  * [1] Michael Cahill and Abraham Taub.  Spherically Symmetric Similarity Solutions of the Einstein Field Equations for a Perfect Fluid.  Communications in Mathematical Physics, 21(1):1–40, 1971.
  * [2] Bernard Carr and Alan Coley.  Complete Classification of Spherically Symmetric Self-Similar Perfect Fluid Solutions.  Physical Review D, 62(4):044023, 2000.
  * [3] Bernard Carr and Amos Yahil.  Self-Similar Perturbations of a Friedmann Universe.  The Astrophysical Journal, 360:330–342, 1990.
  * [4] Peter Lax.  Hyperbolic Systems of Conservation Laws II.  Communications on Pure and Applied Mathematics, 10(4):537–566, 1957\.
  * [5] Joel Smoller.  Shock Waves and Reaction-Diffusion Equations, Second Edition.  Springer, 1994.
  * [6] Joel Smoller and Blake Temple.  Shock-Wave Solutions of the Einstein Equations: The Oppenheimer-Snyder Model of Gravitational Collapse Extended to the Case of Non-Zero Pressure.  Archive for Rational Mechanics and Analysis, 128(3):249–297, 1994\.
  * [7] Joel Smoller and Blake Temple.  Astrophysical Shock-Wave Solutions of the Einstein Equations.  Physical Review D, 51(6):2733–2743, 1995.
  * [8] Joel Smoller and Blake Temple.  Shock-Wave Cosmology Inside a Black Hole.  Proceedings of the National Academy of Sciences, 100(20):11216–11218, 2003.
  * [9] Joel Smoller and Blake Temple.  Cosmology, Black Holes and Shock Waves Beyond the Hubble Length.  Methods and Applications of Analysis, 11(1):77–132, 2004.
  * [10] Joel Smoller and Blake Temple.  General Relativistic Self-Similar Waves that Induce an Anomalous Acceleration into the Standard Model of Cosmology.  Memoirs of the American Mathematical Society, 218(1025), 2012.
  * [11] Joel Smoller, Blake Temple, and Zeke Vogler.  An Instability of the Standard Model of Cosmology Creates the Anomalous Acceleration Without Dark Energy.  Proceedings of the Royal Society A, 473(2207):20160887, 2017.


# Cooperation in Threshold Public Projects with Binary Actions111A short
version of this paper is accepted by IJCAI’21. Yiling Chen and Fang-Yi Yu are
supported by the National Science Foundation under grants IIS 2007887

Yiling Chen Harvard University<EMAIL_ADDRESS>Biaoshuai Tao John
Hopcroft Center for Computer Science, Shanghai Jiao Tong University
<EMAIL_ADDRESS>Fang-Yi Yu Harvard University<EMAIL_ADDRESS>
###### Abstract

When can cooperation arise from self-interested decisions in public goods
games? And how can we help agents to act cooperatively? We examine these
classical questions in a _pivotal participation game_ , a variant of public
good games, where heterogeneous agents make binary participation decisions on
contributing their endowments, and the public project succeeds when it has
enough contributions.

We prove it is NP-complete to decide the existence of a cooperative Nash
equilibrium such that the project succeeds. We also identify two natural
special scenarios where this decision problem is tractable. We then propose
two algorithms to help cooperation in the game. Our first algorithm adds an
external investment to the public project, and our second algorithm uses
matching funds. We show that the cost to induce a cooperative Nash equilibrium
is near-optimal for both algorithms. Finally, the cost of matching funds can
always be smaller than the cost of adding an external investment. Intuitively,
matching funds provide a greater incentive for cooperation than adding an
external investment does.

##  1 Introduction

Consider a town that seeks donations of collectibles from its residents with
the goal to open a public museum if enough collectibles are received, or
countries deciding whether to participate in an environmental agreement (e.g.
Kyoto Protocol) [15, 8, 2] to collectively reduce greenhouse gas emission.
These settings have the nature of public goods games—the non-exclusiveness of
a public good may lead to free ride but the success of the project requires a
certain level of participation. Can cooperative behavior arise from self-
interested decisions to lead to success in the project? How can we help agents
to act cooperatively?

We propose a variant of public goods games, _pivotal participation game_ , to
answer these two classic questions. Each agent has an endowment and decides
whether to contribute to a public project. If the total contribution is enough
for the project to succeed, everyone regardless of their contribution receives
rewards from the project.

Our pivotal participation game has two characteristics. First, participants
make binary decisions on participation (contributing their endowment or not).
This allows us to capture the indivisibility of contributions in collectible
donation and participation agreement. Restriction to binary actions is also
suitable for other public goods domains such as vaccination [5], adoption of
innovations [7], public health insurance [10], or even practicing social
distancing [6]. Second, participants have heterogeneous endowments and
rewards. Many well-studied public goods games are symmetric among agents:
agents have symmetric endowments [21, 19] and the reward is uniformly
distributed among agents [20] or only depends on the number of contributing
agents [11, 12]. In our setting, agents’ endowments (value of collectibles,
cost of reducing greenhouse gas emissions) are heterogeneous, and their reward
from the project’s success (values of visiting museum or benefits from clean
air) can also be different.

We first prove that it is NP-complete to decide whether there exists a Nash
equilibrium such that the project succeeds (Theorem 3.5). This result suggests
large groups may struggle to cooperate in public projects, which is supported
in the literature. [18] Then we show that successful cooperation is always
possible in two natural scenarios: 1) agents’ endowments are small or the
reward levels are large enough in Section 3.1.1 and 2) the minimal successful
cooperation has the same number of agents in Section 3.1.2

Then we develop algorithms to help achieving cooperation. We consider two
natural interventions: The algorithms can 1) add an external investment
$\delta$ to the public project in Section 4.1, or 2) commit to a matching fund
so that for every $1$ value of investment from agents, the algorithms add
$\rho$ to the project in Section 4.2. Both interventions are common in
practice. [1, 14] We want to minimize the additional cost due to those
interventions. We first show that it is NP-hard to approximate the optimal
cost under both interventions to within any finite multiplicative factors.
Then, we design two algorithms with near-optimal cost in the additive sense.
(Theorem 4.5 and 4.13) Finally, we compare these two interventions and prove
that matching funds can promote cooperation with no more cost than adding an
external investment can. (Proposition 4.9) This provides a theoretical
explanation for the efficacy of matching funds in the field. [13]

##### Related works.

Our work considers the computational issue of searching Nash equilibria of
public goods games, and designs algorithms to help cooperation. Our model
falls in the category of threshold public goods with binary actions. However,
for most of the existing models in this category, computational issue has
seldom been considered and successful cooperation can be found efficiently.
One pioneering work [19] considers participation games where agents have
homogeneous unit endowment. Thus, participation by any subset of sufficient
number of agents is an equilibrium. Rapoport [1988] and Bolle [2014] consider
that agents’ rewards only depend on whether the project succeeds or not, while
ours also depends on the project’s total value of contributions. As a result,
successful cooperation can be computed efficiently in their games. Another
important category of public goods games is network public goods game [4]. For
this category, recent works also consider the computational complexity of
finding equilibria and design algorithms to help cooperation [22, 16].
However, the main interest of their games are network structures instead of
heterogeneity of agents’ endowments and reward levels.

##  2 Model

We consider the _pivotal participation game_ where agents have heterogeneous
endowment and binary actions deciding whether to invest all her endowment or
none. Formally, a group of $n$ agents wants to fund a project which has a
_threshold_ $\tau\in\mathbb{R}_{\geq 0}$ for success. Each agent $i\in[n]$ has
an indivisible _endowment_ that has an equivalent value of
$e_{i}\in\mathbb{R}_{\geq 0}$, and she can decide whether to participate by
contributing all her endowment or free ride, $a_{i}\in\\{0,1\\}$. Thus,
agents’ strategy profile can be denoted by $S:=\\{i:a_{i}=1\\}\subseteq[n]$
which is the set of agents who participate. Let $e(S):=\sum_{j\in S}e_{j}$ be
the total value of contributions made by agents in $S$. The project succeeds
if $e(S)\geq\tau$. When the project succeeds, each agent’s reward depends on
her _reward level_ $0<m_{i}<1$. Specifically, given a strategy profile $S$,
agent $i$’s utility is

$U_{i}(S)=e_{i}\mathbf{1}[i\notin
S]+m_{i}e(S)\mathbf{1}\left[e(S)\geq\tau\right].$ (1)

We use $(\vec{e},\vec{m},\tau)$ to denote a pivotal participation game
instance, where $\vec{e}=(e_{1},\ldots,e_{n})$ encodes each agent’s endowment
and $\vec{m}=(m_{1},\ldots,m_{n})$ encodes each agent’s reward level. A
strategy profile $S$ is a _Nash equilibrium_ if no one would unilaterally
deviate: If $i$ invests, i.e., $i\in S$, $U_{i}(S)\geq
U_{i}(S\setminus\\{i\\})$. If $i\notin S$, $U_{i}(S)\geq U_{i}(S\cup\\{i\\})$.
A strategy profile $S$ is a _cooperative Nash equilibrium_ if it is a Nash
equilibrium and the project succeeds, $e(S)\geq\tau$.

##  3 Best Response and Nash Equilibria

First note that, fixing other agents’ actions, an agent $i$ will free ride if
the project succeeds without her investment or cannot succeed with her
investment. To see this, let $S_{-i}=\\{j\neq i:a_{j}=1\\}$ be other agents’
action. If agent $i$’s action does not affect whether the project succeeds,
$U_{i}(S_{-i}\cup\\{i\\})-U_{i}(S_{-i})\leq-e_{i}+m_{i}e_{i}<0$. That is,
agent $i$ will invest only if her investment can change the project from
unsuccessful to successful, $e(S_{-i})<\tau\leq e(S_{-i})+e_{i}$. However, the
following example shows this is just a necessary condition.

######  Example 3.1.

Let $\vec{e}=(2,2,2,9)$, $\vec{m}=(0.2,0.2,0.2,0.5)$, and $\tau=10$. The
project’s success requires agent $4$ to participate. However, agent $4$ will
not participate, because even if everyone participates, the total investment
is $15$ and agent $4$’s reward is at most $15m_{4}=7.5$ which is smaller than
her endowment $9$.

The above example shows that even with enough endowments the agents cannot
cooperate due to their heterogeneity.

The following proposition shows that the best response depends on not only
whether the project succeeds but also how large her endowment $e_{i}$ and
reward level $m_{i}$ are.

######  Proposition 3.2.

Given the other agents’ actions $S_{-i}$, agent $i$’s best response is
participating if and only if

$\displaystyle e(S_{-i})<\tau\leq e(S_{-i})+e_{i},\text{ and}$ (2)
$\displaystyle\frac{1-m_{i}}{m_{i}}e_{i}\leq e(S_{-i}).$ (3)

###### Proof.

If both (2) and (3) are true,

$\displaystyle U_{i}(S_{-i}\cup\\{i\\})$ $\displaystyle=$ $\displaystyle
m_{i}e(S_{-i}\cup\\{i\\})\mathbf{1}[e(S_{-i}\cup\\{i\\})\geq\tau]$ (by Eqn.
(1)) $\displaystyle=$ $\displaystyle m_{i}e(S_{-i}\cup\\{i\\})$ (by the second
part of Eqn. (2)) $\displaystyle=$ $\displaystyle m_{i}e(S_{-i})+m_{i}e_{i}$
$\displaystyle\geq$ $\displaystyle(1-m_{i})e_{i}+m_{i}e_{i}$ (by Eqn. (3))
$\displaystyle=$ $\displaystyle U_{i}(S_{-i})$ (by Eqn. (2))

Therefore, agent $i$’s best response is participating.

Conversely, suppose Eqn. (2) does not hold. Agent $i$’s action does not affect
whether the project succeeds. By Eqn. (1),
$U_{i}(S_{-i}\cup\\{i\\})-U_{i}(S_{-i})\leq-e_{i}+m_{i}e_{i}<0$. Thus, agent
$i$’s best response is not participating. Finally, if Eqn. (3) does not hold,

$\displaystyle U_{i}(S_{-i}\cup\\{i\\})\leq$ $\displaystyle
m_{i}e(S_{-i})+m_{i}e_{i}$ (may not succeed) $\displaystyle<$
$\displaystyle(1-m_{i})e_{i}+m_{i}e_{i}$ (Eqn. (3) is false) $\displaystyle=$
$\displaystyle U_{i}(S_{-i}),$

so agent $i$’s best response is not participating. This completes the proof. ∎

With Proposition 3.2, we can show that an agent will not participate if her
endowment is very large.

######  Corollary 3.3.

If $e_{i}\geq\tau$, agent $i$ will not participate.

###### Proof.

Suppose $e_{i}\geq\tau$ and agent $i$ participates. Other agent will free ride
because the project already succeeds. However, agent $i$ does not want to
participate by himself/herself, because $m_{i}<1$. ∎

###  3.1 Nash Equilibria

By Proposition 3.2, we have the following characterization of a successful
cooperation $S$ which is a Nash equilibrium that makes the project successful.

######  Proposition 3.4.

Given a pivotal game $(\vec{e},\vec{m},\tau)$, $S$ is a cooperative Nash
equilibrium if and only if for all $i\in S$

$\max\left\\{\tau,\frac{e_{i}}{m_{i}}\right\\}\leq e(S)<\tau+e_{i}.$ (4)

Figure 1 shows that social assortment can emerge when agents’ endowments are
heterogeneous. Agents with large endowments do not cooperate with small
endowment agents and form a Nash equilibrium.

Figure 1: Let $\tau=12$. There are $15$ agents whose reward level is $0.35$.
$10$ agents have endowment $2$ and the other agents have endowment $5$. With
Proposition 3.4, for an agent with endowment $2$ to invest, the sum of
investment need to be between $\max\\{12,2/0.35\\}=12$ and $12+2=14$ which is
represented as a blue bar in the figure. However, when the endowment is $5$,
the total investment needs to be between $14.3$ and $17$ which is represented
as a red bar.
There are several possible cooperation. Any collection of $6$ agents with
endowment $2$ is one (yellow region), and any collection of $3$ agents with
endowment $5$ is another (grey region). However, by Proposition 3.4, there
does not exist a cooperative Nash equilibrium where both agents with
endowments $2$ and $5$ invest.

Further, we show that deciding if there is a cooperative Nash equilibrium is
NP-complete. This implies that searching such an cooperation among a large
group of agents is computationally difficult.

######  Theorem 3.5.

Deciding if a pivotal participation game $(\vec{e},\vec{m},\tau)$ has a
cooperative Nash equilibrium is NP-complete.

###### Proof.

This decision problem is clearly in NP: the set of agents $S\neq\emptyset$
that invest can be served as a certificate, and Proposition 3.4 can decide if
$S$ is a Nash equilibrium in polynomial time. It remains to show that the
problem is NP-hard.

We reduce the problem from a well-known NP-complete problem, the partition
problem [9]: given a set $\mathcal{S}$ of $2T$ positive integers
$c_{1},\ldots,c_{2T}$, decide if there exists a subset $\mathcal{T}$ of $T$
integers whose sum is exactly $\frac{1}{2}\sum_{i=1}^{2T}c_{i}$. We assume
without loss of generality that $c_{1}\leq\cdots\leq c_{2T}$.

We construct a pivotal participation game instance $(\vec{e},\vec{m},\tau)$ as
follows. Let $M=100\sum_{i=1}^{2T}c_{i}$ and $N=100MT$. The instance contains
$n=2T+2$ agents, with $e_{i}=N+M+2c_{i}$ for $i=1,\ldots,2T$, and
$e_{2T+1}=N+1$ and $e_{2T+2}=N$. It is straightforward to see that
$e_{2T+2}<e_{2T+1}<e_{1}\leq\cdots\leq e_{2T}$. The parameter $\tau$ is set to
$\tau=1+e_{2T+1}+\frac{1}{2}\sum_{i=1}^{2T}e_{i}=\frac{1}{2}\sum_{i=1}^{2T}2c_{i}+(N+M)T+N+2$.
Finally, $\vec{m}$ is set to the followings: for each $i=1,\ldots,n$,
$m_{i}=\frac{e_{i}}{\tau+e_{2T+2}-1}$. For each $i=1,\ldots,n$, we have
$\max\\{\frac{e_{i}}{m_{i}},\tau\\}=\tau+e_{2T+2}-1=\frac{1}{2}\sum_{i=1}^{2T}2c_{i}+(N+M)T+2N+1$,
which must be a lower bound to $e(S)$ by Proposition 3.4.

Suppose the partition instance is a YES instance, and let $\mathcal{T}$ be the
subset of $T$ integers such that
$\sum_{i\in\mathcal{T}}c_{i}=\frac{1}{2}\sum_{i=1}^{2T}c_{i}$. By slightly
abuse of the notation, let $\mathcal{T}$ be the subset of the first $2T$
agents that corresponds to the set of $T$ selected integers. We show that
$S=\mathcal{T}\cup\\{2T+1,2T+2\\}$ is a valid Nash equilibrium. To see this,
the total investment is
$e(S)=2\cdot\left(\sum_{i\in\mathcal{T}}c_{i}\right)+(M+N)T+2N+1=2\cdot\left(\frac{1}{2}\sum_{i=1}^{2T}c_{i}\right)+(M+N)T+2N+1=\tau+e_{2T+2}-1=\max\\{\tau,\frac{e_{i}}{m_{i}}\\}$
for each $i=1,\ldots,n$. Moreover, for each $i=1,\ldots,n$, by noticing that
$e_{2T+2}\leq e_{i}$, we have $e(S)\leq\tau+e_{i}-1<\tau+e_{i}$. By
Proposition 3.4, $S$ is a Nash equilibrium.

Suppose the partition instance is a NO instance. We aim to show that the only
Nash equilibrium is $S=\emptyset$. To derive a contradiction, suppose
$S\neq\emptyset$ is a Nash equilibrium, and we consider two cases: $2T+2\in S$
and $2T+2\notin S$.

Suppose $2T+2\in S$. By Proposition 3.4, we must have
$\frac{e_{2T+2}}{m_{2T+2}}=\tau+e_{2T+2}-1\leq e(S)<\tau+e_{2T+2}$. Since all
$e_{i}$’s are integers, this implies $e(S)=\tau+e_{2T+2}-1$, and it must be
that $\sum_{i\in
S\setminus\\{2T+2\\}}e_{i}=\tau-1=e_{2T+1}+\frac{1}{2}\sum_{i=1}^{2T}e_{i}$.
By our construction, each of $e_{1},\ldots,e_{2T}$ is an even number, while
$e_{2T+1}$ is an odd number. Thus, $e_{2T+1}+\frac{1}{2}\sum_{i=1}^{2T}e_{i}$
is an odd number (note that $\sum_{i=1}^{2T}e_{i}$ is a multiple of $4$). By
the parity of the equation, we must have $2T+1\in S$. This implies $\sum_{i\in
S\setminus\\{2T+1,2T+2\\}}e_{i}=\frac{1}{2}\sum_{i=1}^{2T}e_{i}$. Let
$\mathcal{T}=S\setminus\\{2T+1,2T+2\\}$. We have
$\sum_{i\in\mathcal{T}}e_{i}=\frac{1}{2}\sum_{i=1}^{2T}e_{i}$.

Next, it is easy to see that $|\mathcal{T}|=T$. If $|\mathcal{T}|<T$,
$\sum_{i\in\mathcal{T}}e_{i}\leq(M+N)(T-1)+\sum_{i\in\mathcal{T}}2c_{i}<(M+N)(T-1)+\frac{1}{50}M<(M+N)T<\frac{1}{2}\sum_{i=1}^{2T}e_{i}$.
If $|\mathcal{T}|>T$,
$\sum_{i\in\mathcal{T}}e_{i}>(M+N)(T+1)>(M+N)T+\frac{1}{50}M>\frac{1}{2}\sum_{i=1}^{2T}e_{i}$.

Knowing that $|\mathcal{T}|=T$, by canceling the $(M+N)$ terms on both sides
of the equation $\sum_{i\in\mathcal{T}}e_{i}=\frac{1}{2}\sum_{i=1}^{2T}e_{i}$
and then divide the both sides by $2$, we have
$\sum_{i\in\mathcal{T}}c_{i}=\frac{1}{2}\sum_{i=1}^{2T}c_{i}$, which
contradicts to that the partition instance is a NO instance.

It remains to derive a contradiction for the case $2T+2\notin S$. Firstly, we
show that $|S|\geq T+2$. If $|S|\leq T+1$, we have $e(S)=\sum_{i\in
S}e_{i}<(N+M)(T+1)+\frac{1}{50}M+1<(M+N)T+1.1N<\tau+e_{2T+2}-1=\frac{e_{i}}{m_{i}}$,
which implies $S$ cannot be a Nash equilibrium by Proposition 3.4.

Having shown that $|S|\geq T+2$, we discuss two sub-cases: $2T+1\notin S$ and
$2T+1\in S$. For the first sub-case $2T+1\notin S$, since $e_{i}>M+N$ for all
$i=1,\ldots,2T$, we have $e(S)=\sum_{i\in S}e_{i}>(T+2)(M+N)$. On the other
hand, for each $i=1,\ldots,2T$, we have
$\tau+e_{i}=\frac{1}{2}\sum_{i=1}^{2T}2c_{i}+(M+N)T+N+2+(M+N)+c_{i}<(M+N)(T+1)+N+\frac{1}{25}M+2<(M+N)(T+2)$.
Therefore, $e(S)>\tau+e_{i}$ for each $i=1,\ldots,2T$. Since
$S\subseteq\\{1,\ldots,2T\\}$, $S$ cannot be a Nash equilibrium by Proposition
3.4.

Consider the second sub-case $2T+1\in S$. There are at least $T+1$ agents in
$\\{1,\ldots,2T\\}$, so $e(S)\geq(M+N)(T+1)+N+1=(M+N)T+2N+M+1$. On the other
hand,
$\tau+e_{2T+1}=\frac{1}{2}\sum_{i=1}^{2T}2c_{i}+(M+N)T+2N+3<(M+N)T+2N+M<e(S)$.
By Proposition 3.4, $S$ cannot be a Nash equilibrium, and we derive a
contradiction again.

We have derive contradictions for all possible cases for $S\neq\emptyset$.
Therefore, the only Nash equilibrium is $S=\emptyset$ when the partition
instance is a NO instance. We conclude the theorem. ∎

Although deciding the existence of cooperative equilibria is NP-complete, we
will see two special scenarios where this decision problem is tractable.

####  3.1.1 Low Endowment-to-Reward Ratio

In the following theorem, we show that a cooperative Nash equilibrium always
exists and can be computed efficiently when the ratio of endowment to reward
level is smaller than $\tau$ for each agents (as long as the sum of all
agents’ endowments exceeds $\tau$). Intuitively, our result shows that
cooperation becomes easy, if agents’ endowments are small or the reward level
are large enough, in contrast to Example 3.1.

######  Theorem 3.6.

Given a pivotal participation game $(\vec{e},\vec{m},\tau)$, if
$e_{i}/m_{i}\leq\tau$ for all $i$, there exists a successful cooperation if
and only if $\sum_{i=1}^{n}e_{i}\geq\tau$. Moreover, we can find a cooperative
Nash equilibrium $S$ in polynomial time.

We will show that every minimal subset of agents $S$ (defined below) is a Nash
equilibrium.

######  Definition 3.7.

Given a pivotal participation game $(\vec{e},\vec{m},\tau)$, a subset of
agents $S$ is _minimal_ if

  1. 1.

$e(S)\geq\tau$, and

  2. 2.

for any $j\in S$, $e(S\setminus\\{j\\})<\tau$.

######  Proposition 3.8.

Given a pivotal participation game $(\vec{e},\vec{m},\tau)$, if
$e_{i}/m_{i}\leq\tau$ for all $i$, every minimal subset of agents $S$ is a
Nash equilibrium.

###### Proof.

We prove this by showing that every minimal subset of agents $S$ satisfies
Eqn. (4) in Proposition 3.4. Given an arbitrarily minimal subset of agents
$S$, since $e_{i}/\tau\leq m_{i}$, the left part of (4) holds due to 1 of
Definition 3.7. Suppose the right part of (4) fails for some agent $j\in S$.
We have $e(S)\geq\tau+e_{j}$, which implies $e(S\setminus\\{j\\})\geq\tau$,
which contradicts to 2 of Definition 3.7. Thus, the right part of (4) also
holds for any $i\in S$. ∎

Finally, Theorem 3.6 can be shown by constructing a minimal subset of agents
$S$.

###### Proof of Theorem 3.6.

Suppose $\sum_{i=1}^{n}e_{i}\geq\tau$. The following simple algorithm finds a
minimal subset of agents $S$: initialize $S=\emptyset$; iteratively add an
arbitrary agent $i$ to $S$, and terminate the algorithm when $e(S)\geq\tau$.
The algorithm will terminates with $e(S)\geq\tau$ since
$\sum_{i=1}^{n}e_{i}\geq\tau$. It is easy to see that the algorithm finds a
minimal subset of agents $S$, and by Proposition 3.8, $S$ is a Nash
equilibrium.

Suppose $\sum_{i=1}^{n}e_{i}<\tau$. The left part of (4) in Proposition 3.4
will always fail. Therefore, there does not exist a cooperative Nash
equilibrium. ∎

####  3.1.2 Balanced Instances

We consider another special case where the success of the project always
requires the same number of agents, and show that the problem of deciding if a
cooperative Nash equilibrium exists can be solved in polynomial time.

######  Definition 3.9.

A pivotal participation game instance $(\vec{e},\vec{m},\tau)$ is _balanced_
if all the minimal subsets of agents (see Definition 3.7) have the same
cardinality.

For a typical natural example of balanced instances, we can have agents’
endowments being approximately the same, say, agents’ endowments are
approximately $N$. The instance is balanced as long as $\tau$ is not around
any $bN$ for some integer $b\in\mathbb{Z}^{+}$. For example, if agents’
endowments are approximately $N$ and $\tau=3.5N$, the success of the project
always needs exactly $4$ agents’ endowments.

######  Theorem 3.10.

Deciding the existence of a cooperative Nash equilibrium is in P for balanced
pivotal participation game instances.

Algorithm 1 Decide the existence of cooperative Nash equilibrium for balanced
instances

Input: a balanced pivotal participation game instance $(\vec{e},\vec{m},\tau)$
Output: a set of investing agents $S$, or $S=\emptyset$ (no cooperative Nash
equilibrium)

1: compute $l_{i}=\max\\{\tau,\frac{e_{i}}{m_{i}}\\}$ for each $i\in[n]$

2: let $m$ be the cardinality of a minimal subset of agents

3: sort the agents such that $e_{1}\geq e_{2}\geq\cdots\geq e_{n}$

4: initialize $S=\\{1,\ldots,m\\}$ and $T=\\{m+1,\ldots,n\\}$

5: while there exists $i\in S$ with $l_{i}>e(S)$ do

6: if $T=\emptyset$ then

7: return $S=\emptyset$

8: end if

9: remove $i$ from $S$

10: add the first element $j$ of $T$ to $S$

11: remove $j$ from $T$

12: end while

13: return $S$

Firstly, Algorithm 1 runs in polynomial time. To see this, the while-loop is
executed at most $n-m$ times, as each iteration of the while-loop removes one
element from the set $T$, which initially has cardinality $n-m$.

To show the correctness of the algorithm, we consider the two cases regarding
if Line 13 is reached. Suppose Line 13 is reached. We know that $|S|=m$ (as
the cardinality of $S$ is never changed throughout the while-loop) and
$l_{i}\leq e(S)$ for all $i\in S$. Thus, the left inequality of Eqn. (4) in
Proposition 3.4 is satisfied for all $i\in S$. Suppose the right inequality
$e(S)<\tau+e_{i}$ fails for some $i\in S$, we have $e(S)\geq\tau+e_{i}$ and
$e(S\setminus\\{i\\})\geq\tau$, so $S$ is not minimal, which contradicts to
the balanced assumption. Thus, the right inequality is also satisfied for all
$i\in S$, and $S$ is a Nash equilibrium.

Suppose Line 13 is never reached, and the algorithm terminates at Line 7. We
prove that each element $i$ removed from $S$ can never be a part of a Nash
equilibrium. This can be proved by induction.

Consider the first iteration of the while-loop. If $i\in S$ satisfies
$l_{i}>e(S)$, for any set $S^{\prime}$ of $m$ agents, we have
$e(S^{\prime})\leq e(S)<l_{i}$ since $S$ contains the $m$ agents with the
largest endowments by Line 3. Therefore, any $S^{\prime}$ with $i\in
S^{\prime}$ will violate Eqn. (4), so $i$ cannot be a part of any Nash
equilibrium.

For the inductive step, suppose each of the previously removed elements cannot
be a part of a Nash equilibrium. At the current iteration of the while-loop,
we know that a Nash equilibrium must be a subset of $S\cup T$, and $S$ is a
subset of $m$ agents having largest endowments. By the same arguments, if
$i\in S$ satisfies $l_{i}>e(S)$, for any set $S^{\prime}\subseteq S\cup T$ of
$m$ agents, we have $e(S^{\prime})\leq e(S)<l_{i}$ since $S$ contains the $m$
agents with the largest endowments. Therefore, any $S^{\prime}$ with $i\in
S^{\prime}$ will violate Eqn. (4), so $i$ cannot be a part of any Nash
equilibrium.

By the time Line 7 is reached, we have removed $n-m+1$ agents each of which
cannot be a part of a Nash equilibrium. The remaining $m-1$ agents cannot form
a Nash equilibrium by the balanced assumption. Thus, we know that a
cooperative Nash equilibrium does not exist.

##  4 Interventions

Here we consider two possible interventions to promote agents to cooperate. We
can _add an external investment_ or _commit to a matching fund_. We call an
intervention _valid_ if there is a cooperative Nash equilibrium after the the
intervention. In both interventions, We want to find a valid intervention that
minimizes the additional cost.

We first show that it is NP-hard to approximate the optimal cost within any
finite factor under both interventions (Theorem 4.3). Then, we design two
algorithms (Algorithms 2 and 3) which take parameters of the game
$(\vec{e},\vec{m},\tau)$ and output a valid intervention. We show the cost of
each algorithm’s intervention is close to the optimal with small additive
errors (Theorems 4.5 and 4.13). Finally, we compare these two interventions
and prove that matching fund is more powerful than adding an external
investment in Proposition 4.9.

###  4.1 External Investment

In this section, we consider mechanisms that add investment $\delta$ to the
public project in addition to agents’ investment. Thus, agent $i$’s utility,
$U_{i}(S)$ becomes

$e_{i}\mathbf{1}[i\notin
S]+m_{i}(e(S)+\delta)\mathbf{1}\left[e(S)+\delta\geq\tau\right].$ (5)

By a similar analysis, we can show the following proposition similar to
Proposition 3.4. We leave the details to the readers.

######  Proposition 4.1.

Given a pivotal participation game instance $(\vec{e},\vec{m},\tau)$ with
external investment $\delta$, $S$ is a cooperative Nash equilibrium if and
only if for all $i\in S$

$\max\left\\{\tau,\frac{e_{i}}{m_{i}}\right\\}\leq e(S)+\delta<\tau+e_{i}.$
(6)

Thereafter, we will assume $\tau+e_{i}>\frac{e_{i}}{m_{i}}$ for each agent
$i$, for otherwise, $i$ will never be a part of a cooperative Nash equilibrium
by Proposition 4.1, and we can remove $i$ from consideration.

We say a solution $(S,\delta)$ is _valid_ if $S$ is a Nash equilibrium under
external investment $\delta$. The following theorem shows that the optimal
solution to this minimization problem always exists.

######  Theorem 4.2.

Given a pivotal participation game $(\vec{e},\vec{m},\tau)$, let
$\Delta\subseteq[0,\infty)$ be the set of all valid external investment
$\delta$. We have $\inf\Delta\in\Delta$.

###### Proof.

Firstly, we have $\Delta\neq\emptyset$. Since we have assumed
$\tau+e_{i}>\frac{e_{i}}{m_{i}}$ for every $i$,
$(S=\\{1\\},\delta=\max\\{\tau,\frac{e_{1}}{m_{1}}\\}-e_{1})$ is always a
valid solution.

Given a subset of agents $S$, let $\Delta(S)$ be the set of all possible
values $\delta$ such that $S$ is a Nash equilibrium under external investment
$\delta$. Set $\Delta(\emptyset)=\emptyset$. Since the power set of $[n]$ is
finite, it is easy to prove that

$\inf\Delta=\min_{S:S\subseteq[n],\Delta(S)\neq\emptyset}\inf\Delta(S).$

It suffices to show that either $\inf\Delta(S)\in\Delta(S)$ or
$\Delta(S)=\emptyset$ for each $S$. We consider a fixed $S\neq\emptyset$ from
now on.

For each $i\in[n]$, let $l_{i}=\max\\{\tau,e_{i}/m_{i}\\}$ and
$u_{i}=\tau+e_{i}$.

If $\max_{i\in S}l_{i}\geq\min_{i\in S}u_{i}$ or $e(S)\geq\min_{i\in S}u_{i}$,
we know immediately $\Delta(S)=\emptyset$ by Proposition 4.1. Suppose
$\max_{i\in S}l_{i}<\min_{i\in S}u_{i}$ and $e(S)<\min_{i\in S}u_{i}$ from now
on.

If $\max_{i\in S}l_{i}\leq e(S)<\min_{i\in S}u_{i}$, by Proposition 4.1,
$\delta=0$ makes $S$ a Nash equilibrium, and $\inf\Delta(S)=0\in\Delta(S)$. If
$e(S)<\max_{i\in S}l_{i}$, it is easy to see that $\delta=\max_{i\in
S}l_{i}-e(S)$ is the minimum $\delta$ to make $S$ a Nash equilibrium, and
$\inf\Delta(S)=\max_{i\in S}l_{i}-e(S)\in\Delta(S)$. ∎

Firstly, Theorem 3.5 straightforwardly implies that the problem is NP-hard to
approximate to any finite multiplicative factor.

######  Theorem 4.3.

Given a pivotal participation game instance $(\vec{e},\vec{m},\tau)$, letting
$\delta^{\ast}\geq 0$ be the minimum valid external investment, for any $F>0$
that may depend on $(\vec{e},\vec{m},\tau)$, it is NP-hard to approximate
$\delta^{\ast}$ to within factor $F$.

###### Proof.

Theorem 3.5 implies that it is NP-complete to decide if $\delta^{\ast}=0$.
This theorem concludes immediately. ∎

Fortunately, this minimization problem has an additive term approximation
algorithm, with the additive term being the maximum endowments among the
agents: $e=\max_{i:1\leq i\leq n}\\{e_{i}\\}$. The algorithm is described in
Algorithm 2.

Algorithm 2 Approximation algorithm for pivotal participation game with
external investment

Input: a pivotal participation game instance $(\vec{e},\vec{m},\tau)$
Output: a set of agent $S$ that invest; the amount of external investment
$\delta$

1: for each $i\in[n]$, let $u_{i}=\tau+e_{i}$ and
$l_{i}=\max\\{\tau,\frac{e_{i}}{m_{i}}\\}$

2: sort agents such that $l_{1}\leq l_{2}\leq\cdots\leq l_{n}$

3: for $i=1,\ldots,n$ do

4: initialize $S_{i}=\emptyset$

5: let $K_{i}=\\{k\in[n]:l_{k}\leq l_{i}<u_{k}\\}$

6: sort agents in $K_{i}$ so that $e_{k_{1}}\geq e_{k_{2}}\geq\cdots\geq
e_{k_{|K_{i}|}}$

7: for $j=1,\ldots,|K_{i}|$ do

8: if $e(S_{i}\cup\\{k_{j}\\})>l_{i}$ then

9: break

10: end if

11: update $S_{i}=S_{i}\cup\\{k_{j}\\}$

12: end for

13: set $\delta_{i}=l_{i}-e(S_{i})$

14: end for

15: find $i^{o}=\operatorname*{arg\,min}_{i}\delta_{i}$

16: return $(S_{i^{o}},\delta_{i^{o}})$

The algorithm works as follows. It considers $n$ possible values
$l_{1},\ldots,l_{n}$ for $e(S)+\delta$. For each possibility
$e(S)+\delta=l_{i}$, it iteratively adds an agent $k$ with $l_{k}\leq
l_{i}<u_{k}$ to $S$ until either no more agent can be added (when the for-loop
at Line 7 terminates without reaching Line 9) or $e(S)\leq l_{i}$ cannot be
maintained (when the for-loop at Line 7 exits at Line 9). The algorithm finds
a solution for $e(S)+\delta=l_{i}$ by setting $\delta=l_{i}-e(S)$ for $S$
found by the above step. Finally, the algorithm compares the $n$ solutions and
output the optimal one. It is straightforward to check that the algorithm runs
in polynomial time.

######  Remark 4.4.

Our algorithm has a desirable fairness property: “richer people contributes
first”. [17] In each of the $n$ solutions the algorithm outputs, Line 6 of the
algorithm guarantees that agents with larger endowments invest first, whenever
possible. The larger the index $i$ is, the better the solution
$(S_{i},\delta_{i})$ preserves this property. In particular, for $i=n$,
$(S_{n},\delta_{n})$ strictly preserves this property (by Line 5 and the fact
that $u_{k}$ is larger whenever $e_{k}$ is larger). When implementing
Algorithm 2, we can compare the $n$ solutions and trade off between the
investment $\delta$ and the said fairness property.

######  Theorem 4.5.

Given a pivotal participation game $(\vec{e},\vec{m},\tau)$, letting
$\delta^{\ast}\geq 0$ be the minimum valid external investment and
$e=\max_{i:1\leq i\leq n}\\{e_{i}\\}$, Algorithm 2 finds a solution
$(S,\delta)$ with $\delta\leq\max\\{e,\delta^{\ast}\\}$.

###### Proof.

We first show that the solution output by Algorithm 2 is valid. We show that
the solution $(S_{i},\delta_{i})$ found in each iteration of the for-loop is
valid. We have $e(S_{i})+\delta_{i}=l_{i}$ and each $k\in S_{i}$ satisfies
$l_{k}\leq l_{i}<u_{k}$ (guaranteed by Line 13 and 5 of the algorithm),
Proposition 4.1 implies that $S_{i}$ is a Nash equilibrium. It remains to
prove the approximation guarantee $\delta\leq\max\\{e,\delta^{\ast}\\}$.

Suppose agents are ordered such that $l_{1}\leq\cdots\leq l_{n}$. Let
$(S,\delta)$ be the solution output by the algorithm. Let $(S_{i},\delta_{i})$
be the solution output at $i$-th iteration of the for-loop at Line 3. Let
$(S^{\ast},\delta^{\ast})$ be the optimal solution.

Firstly, if the inner for-loop at Line 7 exits at Line 9 for certain iteration
$i$ of the for-loop at Line 3, then $\delta<e$, in which case the
approximation guarantee is proved. To see this, Line 8 and 13 ensure that
$\delta_{i}=l_{i}-e(S_{i})<e_{k_{j}}\leq e$. Since the final solution output
by the algorithm is no worse than $(S_{i},\delta_{i})$, we have
$\delta\leq\delta_{i}<e$. From now on, we assume that the “break” statement at
Line 9 has never been executed for all iterations.

Next, we consider the optimal solution $(S^{\ast},\delta^{\ast})$. Let
$i^{\dagger}$ be the agent with the largest index such that
$e(S^{\ast})+\delta^{\ast}\geq l_{i^{\dagger}}$. We show that each $j\in
S^{\ast}$ satisfies $l_{j}\leq l_{i^{\dagger}}<u_{j}$. Suppose there exists
$j\in S^{\ast}$ with $l_{j}>l_{i^{\dagger}}$. We first know $i^{\dagger}<n$.
By Proposition 4.1, we must have $e(S^{\ast})+\delta^{\ast}\geq l_{j}\geq
l_{i^{\dagger}+1}$ to make the solution valid. However, this contradicts to
our assumption that $i^{\dagger}$ is the agent with the largest index
satisfying $e(S^{\ast})+\delta^{\ast}\geq l_{i^{\dagger}}$. Suppose there
exists $j\in S^{\ast}$ with $u_{j}\leq l_{i^{\dagger}}$. Since we assumed
$l_{i^{\dagger}}\leq e(S^{\ast})+\delta^{\ast}$, Proposition 4.1 implies that
$(S^{\ast},\delta^{\ast})$ should not have been valid.

In addition, our assumption that the “break” statement at Line 9 has never
been executed implies that $e(S^{\ast})+\delta^{\ast}=l_{i^{\dagger}}$.
Suppose otherwise $e(S^{\ast})+\delta^{\ast}>l_{i^{\dagger}}$. We have
$\delta^{\ast}=0$, for otherwise we can always decrease the value of
$\delta^{\ast}$ while maintaining $e(S^{\ast})+\delta^{\ast}\geq
l_{i^{\dagger}}$, which contradicts to that $\delta^{\ast}$ is optimal. As a
result, $e(S^{\ast})+\delta^{\ast}>l_{i^{\dagger}}$ implies
$e(S^{\ast})>l_{i^{\dagger}}$. Since we have proved that each $j\in S^{\ast}$
satisfies $l_{j}\leq l_{i^{\dagger}}<u_{j}$, at iteration $i^{\dagger}$ of our
algorithm, we must have $S^{\ast}\subseteq K_{i^{\dagger}}$. Therefore,
$e(K_{i^{\dagger}})\geq e(S^{\ast})>l_{i^{\dagger}}$, the “break” statement
will be executed before all the $|K_{i^{\dagger}}|$ agents are added to
$S_{i^{\dagger}}$, which contradicts to our assumption.

Finally, we have proved that $e(S^{\ast})+\delta^{\ast}=l_{i^{\dagger}}$, and
we also have $S^{\ast}\subseteq K_{i^{\dagger}}$ at iteration $i^{\dagger}$ of
our algorithm. Since the “break” statement has not been executed, we have
$S_{i^{\dagger}}=K_{i^{\dagger}}$, and
$\delta_{i^{\dagger}}=l_{i^{\dagger}}-e(S_{i^{\dagger}})\leq
l_{i^{\dagger}}-e(S^{\ast})=\delta^{\ast}$. Therefore, the solution output at
$i^{\dagger}$-th iteration of our algorithm is already optimal, and the final
output of our algorithm is no worse than this. ∎

Finally, we provide an examples showing that adding an external investment can
sometime hurt cooperation.

######  Example 4.6 (Harm of adding an external investment).

Let $\tau=9$, $\vec{e}=(4,4,4)$ and $\vec{m}=(4/11,4/11,4/11)$.
$S=\\{1,2,3\\}$ is a cooperative Nash equilibrium. However, if we add an
external endowment $\delta=2$, there is no cooperative Nash equilibrium by
Proposition 4.1.

###  4.2 Matching Funds

In this section, we consider another intervention—matching funds. The
mechanism can commit to a rate $\rho\geq 0$, and increase the investment from
$e(S)$ to $(1+\rho)e(S)$. Thus, agent $i$’s utility $U_{i}(S)$ becomes

$e_{i}\mathbf{1}[i\notin
S]+m_{i}(1+\rho)e(S)\mathbf{1}\left[(1+\rho)e(S)\geq\tau\right].$ (7)

######  Assumption 4.7.

We assume that the rate of matching funds $\rho$ has a budget constraint
$\rho<\bar{\rho}$ where $\bar{\rho}=\frac{1}{\max_{i\in[n]}m_{i}}-1$.

This assumption ensures $(1+\rho)m_{i}<1$ for each agent $i$. To justify this
assumption, the total reward level $\sum_{i}m_{i}$ can be seen as the return
on investment of the public project, and is around $1$ in practice, so each
agent’s reward level is much less than $1$, e.g., $1/n$. The rate of matching
fund $\rho$ is often a small constant (e.g., 1-to-1, 2-to-1, and 3-to-1). This
makes $m_{i}(1+\rho)$ significantly less than $1$. Secondly, the behavior of
an agent with $m_{i}(1+\rho)\geq 1$ is fundamentally and unnaturally different
from an agent in a normal public goods game: from Eqn. (7) and some simple
calculations, this agent will always invest as long as the project is
successful, even if the project can succeed without him/her!

Similar to Proposition 3.4 and 4.1 we have the following characterization of
cooperative Nash equilibrium. The details are left to the readers.

######  Proposition 4.8.

Given a pivotal participation game instance $(\vec{e},\vec{m},\tau)$ with
matching funds $\rho<\bar{\rho}$, $S$ is a cooperative Nash equilibrium if and
only if for all $i\in S$

$\max\left\\{\tau,\frac{e_{i}}{m_{i}}\right\\}\leq(1+\rho)e(S)<\tau+(1+\rho)e_{i}.$
(8)

We also have a minimization problem here. The objective of this problem can be
either formulated by the rate $\rho$ or the cost $\rho\cdot e(S)$ where $S$ is
a cooperative Nash equilibrium under (7). We say a solution $(S,\rho)$ is
valid if $S$ is a Nash equilibrium under the rate of matching funds $\rho$.

First, we want to compare the power of these two interventions. The following
result shows that, for any valid external investment $\delta$, there is a
valid matching funds with some $\rho$ that has less or equal cost.
Intuitively, this shows that matching funds is more powerful than adding
external investment.

######  Proposition 4.9.

For all $(\vec{e},\vec{m},\tau)$, for any valid solution $(S,\delta)$ where
the external investment $\delta$ is not prohibitively large
$\delta<\bar{\rho}\cdot e(S)$, $S$ is also a cooperative Nash equilibrium with
matching funds $\rho=\delta/e(S)$. Moreover, the cost of matching funds
$\rho\cdot e(S)$ is exactly $\delta$.

###### Proof.

If adding external $\delta$ endowment makes cooperation successful, setting
$\rho=\delta/e(S)$, $S$ is also a successful cooperation because of
Proposition 4.8 and $\tau+e_{i}\leq\tau+(1+\rho)e_{i}$ for all $i\in S$.
Moreover, the cost $\rho\cdot e(S)$ is $\delta$ when agents in $S$ cooperate.
∎

Moreover, there indeed exist games such that the cost of matching fund is
strictly less than the cost of external fund. For example, consider $\tau=11$,
$\vec{e}=(3,3,3)$ and $\vec{m}=(0.2,0.2,0.2)$. Because the reward levels are
too small such that $\frac{e_{i}}{m_{i}}=15>\tau+e_{i}$, no agent will invest
by Proposition 4.1. Thus, the minimal valid external investment is
$\delta=11$. However, for matching fund, if we set $\rho=2/3$, $S=\\{1,2,3\\}$
becomes a cooperative equilibrium and the cost is $9\cdot 2/3=6$ which is less
than the optimal external fund $11$.

The following theorem shows that the solution with optimal rate and the
solution with optimal cost always exist, as long as a cooperation is possible.

######  Theorem 4.10.

Given a pivotal participation game $(\vec{e},\vec{m},\tau)$, let
$\Delta\subseteq[0,\infty)$ be the set of all valid rates of matching funds
$\rho$. Suppose $\Delta\neq\emptyset$. We have $\inf\Delta\in\Delta$.
Moreover, there exists a valid solution $(S^{\ast},\rho^{\ast})$ such that
$\rho^{\ast}\cdot e(S^{\ast})\leq\rho\cdot e(S)$ for all possible solutions
$(S,\rho)$.

###### Proof.

Suppose $\Delta\neq\emptyset$. Given a subset of agents $S$, let $\Delta(S)$
be the set of all possible values $\rho$ such that $S$ is a Nash equilibrium
under the rate of matching funds $\rho$. Set $\Delta(\emptyset)=\emptyset$.
Since the power set of $[n]$ is finite, it is easy to prove that

$\inf\Delta=\min_{S:S\subseteq[n],\Delta(S)\neq\emptyset}\inf\Delta(S).$

To show $\inf\Delta\in\Delta$, it suffices to show that either
$\inf\Delta(S)\in\Delta(S)$ or $\Delta(S)=\emptyset$ for each $S$. We consider
a fixed $S\neq\emptyset$ from now on.

For each $i\in[n]$, let $l_{i}=\max\\{\tau,e_{i}/m_{i}\\}$ and
$u_{i}(\rho)=\tau+(1+\rho)e_{i}$.

If $e(S)\geq\min_{i\in S}u_{i}(0)$, we have $\Delta(S)=\emptyset$. To see
this, suppose $e(S)\geq u_{i}(0)$ for agent $i\in S$. For any $\rho\geq 0$, we
have

$\displaystyle(1+\rho)e(S)$ $\displaystyle\geq e(S)+\rho\cdot e_{i}$ (since
$i\in S$) $\displaystyle\geq u_{i}(0)+\rho\cdot e_{i}=u_{i}(\rho),$

and Proposition 4.8 implies that $S$ cannot be a Nash equilibrium. If
$\min_{i\in S}u_{i}(0)>e(S)\geq\max_{i\in S}l_{i}$, we know $\rho=0$ makes $S$
a Nash equilibrium, and $\inf\Delta(S)=0\in\Delta(S)$. Suppose
$e(S)<\min_{i\in S}u_{i}(0)$ and $e(S)<\max_{i\in S}l_{i}$ from now on.

Firstly, Proposition 4.8 implies that each $\rho\in\Delta(S)$ must satisfy
$(1+\rho)e(S)\geq\max_{i\in S}l_{i}$, which is $\rho\geq\frac{\max_{i\in
S}l_{i}}{e(S)}-1$. Let $\rho^{-}=\frac{\max_{i\in S}l_{i}}{e(S)}-1$ be this
lower bound of $\Delta(S)$. If $\rho^{-}\geq\bar{\rho}$, we know
$\Delta(S)=\emptyset$ immediately, so suppose otherwise. If
$(1+\rho^{-})e(S)<\min_{i\in S}u_{i}(\rho^{-})$, we know
$\inf\Delta(S)=\rho^{-}\in\Delta(S)$ by Proposition 4.8. If
$(1+\rho^{-})e(S)\geq\min_{i\in S}u_{i}(\rho^{-})$, then
$\Delta(S)=\emptyset$. To see this, suppose there exists $\rho\in\Delta(S)$.
Let $\rho^{\prime}=\rho-\rho^{-}$, and $\rho^{\prime}\geq 0$ since $\rho^{-}$
is a lower bound. Let $i\in S$ be an agent such that $(1+\rho^{-})e(S)\geq
u_{i}(\rho^{-})$. We have

$\displaystyle(1+\rho)e(S)$ $\displaystyle=(1+\rho^{-})e(S)+\rho^{\prime}e(S)$
$\displaystyle\geq u_{i}(\rho^{-})+\rho^{\prime}e(S)$ $\displaystyle\geq
u_{i}(\rho^{-})+\rho^{\prime}e_{i}$ (since $i\in S$ and $\rho^{\prime}\geq 0$)
$\displaystyle=u_{i}(\rho),$

contradicting to $\rho\in\Delta(S)$. We conclude $\inf\Delta\in\Delta$.

The fact $\inf\Delta(S)\in\Delta(S)$ (for all $S$ with
$\Delta(S)\neq\emptyset$) shown just now also implies the existence of
$(S^{\ast},\rho^{\ast})$ in the theorem. Take

$S^{\ast}=\operatorname*{arg\,min}_{S:S\subseteq[n],\Delta(S)\neq\emptyset}\left(\inf\Delta(S)\right)\cdot
e(S),$

and $\rho^{\ast}=\inf\Delta(S^{\ast})$. We have
$\rho^{\ast}\in\Delta(S^{\ast})\subseteq\Delta$. In addition, for any valid
solution $(S,\rho)$, we have $\rho\cdot e(S)\geq(\inf\Delta(S))\cdot
e(S)\geq\rho^{\ast}\cdot e(S^{\ast})$. ∎

Again, Theorem 3.5 straightforwardly implies that the problem is NP-hard to
approximate to any finite multiplicative factor for both objectives (the rate
$\rho$ and the cost $\rho\cdot e(S)$).

######  Theorem 4.11.

Given a pivotal participation game instance $(\vec{e},\vec{m},\tau)$, letting
$\rho^{\ast}\geq 0$ be the minimum rate for a valid solution
$(S^{\ast},\rho^{\ast})$ and $\rho^{\dagger}\geq 0$ be the rate for a valid
solution $(S^{\dagger},\rho^{\dagger})$ that minimizes the cost $\rho\cdot
e(S)$, for any $F>0$ that may depend on $(\vec{e},\vec{m},\tau)$, it is NP-
hard to approximate $\rho^{\ast}$ or $\rho^{\dagger}\cdot e(S^{\dagger})$ to
within factor $F$.

###### Proof.

Theorem 3.5 implies that it is NP-complete to decide if there is a valid
solution $(S,\rho)$ with $\rho=0$. This theorem concludes immediately. ∎

We show that we can achieve additive approximation to both objectives by
adaption of Algorithm 2, under the very mild assumption $\bar{\rho}\geq 1$ in
4.7. It is straightforward to check that Algorithm 3 runs in polynomial time.

Algorithm 3 Approximation algorithm for pivotal participation game with
matching funds

Input: a pivotal participation game instance $(\vec{e},\vec{m},\tau)$
Output: a set of agent $S$ that invest; the rate of matching funds $\rho$

1: for each $i\in[n]$, let $l_{i}=\max\\{\tau,\frac{e_{i}}{m_{i}}\\}$

2: compute $\bar{\rho}=\frac{1}{\max_{i\in[n]}m_{i}}-1$

3: sort agents such that $l_{1}\leq l_{2}\leq\cdots\leq l_{n}$

4: for $i=1,\ldots,n$ do

5: initialize $S_{i}=\emptyset$

6: let $K_{i}=\\{k:l_{k}\leq l_{i}\\}$//different to Algorithm 2 here

7: sort agents in $K_{i}$ so that $e_{k_{1}}\geq e_{k_{2}}\geq\cdots\geq
e_{k_{|K_{i}|}}$

8: for $j=1,\ldots,|K_{i}|$ do

9: if $e(S_{i}\cup\\{k_{j}\\})>l_{i}$ then

10: break

11: end if

12: let $\rho_{\text{temp}}=\frac{l_{i}}{e(S_{i}\cup\\{k_{j}\\})}-1$

13: if $l_{i}\geq\tau+(1+\rho_{\text{temp}})e_{k_{j}}$ then

14: break

15: end if

16: update $S_{i}=S_{i}\cup\\{k_{j}\\}$, $\rho_{i}=\rho_{\text{temp}}$

17: end for

18: end for

19: find $i^{o}=\operatorname*{arg\,min}_{i}\\{\rho_{i}\cdot e(S_{i})\\}$

20: if $\rho_{i^{o}}\geq\bar{\rho}$ then

21: return no solution exists

22: end if

23: return $(S_{i^{o}},\rho_{i^{o}})$

######  Remark 4.12.

The “richer people contribute first” property for Algorithm 2 mentioned in
Remark 4.4 also holds for Algorithm 3.

######  Theorem 4.13.

Given a pivotal participation game $(\vec{e},\vec{m},\tau)$ with
$\bar{\rho}\geq 1$ such that a cooperative Nash equilibrium exists under
certain $\rho\in[0,\bar{\rho})$, letting $(S^{\ast},\rho^{\ast})$ be a valid
solution with minimum cost $\rho^{\ast}\cdot e(S^{\ast})$ and $e=\max_{i:1\leq
i\leq n}\\{e_{i}\\}$, Algorithm 3 finds a collaboration $(S,\rho)$ with cost
upper-bounded by $\rho\cdot e(S)\leq\max\\{e,\rho^{\ast}\cdot e(S^{\ast})\\}$
and rate upper-bounded by $\rho\leq\max\\{1,\rho^{\ast}\\}$.

###### Proof.

We first show that the algorithm always outputs valid solutions. We show this
by showing that the solution $(S_{i},\rho_{i})$ output in each iteration is
valid, as long as $\rho_{i}<\bar{\rho}$ (the solution with
$\rho_{i}\geq\bar{\rho}$ will be filtered through Line 19-22). We first show
that $S_{i}\neq\emptyset$ so that $\rho_{i}$ has been defined (equivalently,
Line 16 has been reached at least once). For the first element $k_{1}\in
K_{i}$ that we attempt to add to $S_{i}$, we have
$e_{k_{1}}<\frac{e_{k_{1}}}{m_{k_{1}}}\leq l_{k_{1}}\leq l_{i}$, so the if-
condition at Line 9 will not be satisfied for the first iteration of the for-
loop at Line 8. Moreover, for the first iteration of the for-loop at Line 8,
we have
$l_{i}=(1+\rho_{\text{temp}})e(\emptyset\cup\\{k_{1}\\})=(1+\rho_{\text{temp}})e_{k_{1}}<\tau+(1+\rho_{\text{temp}})e_{k_{1}}$,
so the if-condition at Line 13 is not satisfied. Thus, Line 16 is reachable
and $S_{i}\neq\emptyset$. Next, we have $(1+\rho_{i})e(S_{i})=l_{i}$ and each
$k\in S_{i}$ satisfies $l_{k}\leq l_{i}$ (guaranteed by Line 6 of the
algorithm), so the left part of Eqn. (8) in Proposition 4.8 is satisfied. The
if-statement at Line 13 ensures that the right part of Eqn. (8) in Proposition
4.8 is satisfied for the last agent $k_{j}$ added to $S_{i}$. Since agents in
$K_{i}$ are ordered with decreasing endowments and the term
$\tau+(1+\rho)e_{i}$ on the right-hand side of Eqn. (8) is increasing in
$e_{i}$, the right part of Eqn. (8) in Proposition 4.8 should be satisfied for
all agents in $S_{i}$. Thus, $S_{i}$ is a Nash equilibrium given rate of
matching funds $\rho_{i}$. It remains to prove the two approximation
guarantees in the theorem.

Suppose agents are ordered such that $l_{1}\leq\cdots\leq l_{n}$. Let
$(S,\delta)$ be the solution output by the algorithm. Let $(S_{i},\delta_{i})$
be the solution output at $i$-th iteration of the for-loop at Line 4. Let
$(S^{\ast},\delta^{\ast})$ be the optimal solution.

First of all, if the “break” statement at Line 10 has ever been executed, we
show that the two approximation guarantees in the theorem are satisfied.
Suppose, at the $i$-th iteration of the for-loop at Line 4, the for-loop at
Line 8 exits at Line 10. We know $e(S_{i}\cup\\{k_{j}\\})>l_{i}$. This means
adding $k_{j}$ to $S_{i}$ would make the total investment more than $l_{i}$.
We have $l_{i}-e(S_{i})<e_{k_{j}}$ and $l_{i}=(1+\rho_{i})e(S_{i})$.
Therefore, $\rho_{i}\cdot e(S_{i})=l_{i}-e(S_{i})<e_{k_{j}}<e$. Moreover,
since each agent in $S_{i}$ has endowment at least $k_{j}$ by Line 7, we have
$\rho_{i}<\frac{e_{k_{j}}}{e(S_{i})}\leq 1\leq\bar{\rho}$. The solution
$(S_{i},\rho_{i})$ will not be filtered at Line 19-22, and both approximation
guarantees, $\rho\cdot e(S)\leq\max\\{e,\rho^{\ast}\cdot e(S^{\ast})\\}$ and
$\rho\leq\max\\{1,\rho^{\ast}\\}$, are satisfied. We will assume the “break”
statement at Line 10 has never been executed from now on.

Next, we consider the optimal solution $(S^{\ast},\rho^{\ast})$. Let
$i^{\dagger}$ be the agent with the largest index such that
$(1+\rho^{\ast})e(S^{\ast})\geq l_{i^{\dagger}}$. Each agent $k\in S^{\ast}$
must have $l_{k}\leq l_{i^{\dagger}}$, for otherwise $i^{\dagger}$ should not
have been the agent with the largest index. Therefore, $S^{\ast}\subseteq
K_{i^{\dagger}}$. The next two paragraphs show that

$(1+\rho^{\ast})e(S^{\ast})=l_{i^{\dagger}}.$

Suppose otherwise $(1+\rho^{\ast})e(S^{\ast})>l_{i^{\dagger}}$. We have
$\rho^{\ast}=0$, for otherwise we can always decrease $\rho^{\ast}$ a little
bit and still guaranteeing $S^{\ast}$ is a Nash equilibrium (notice that we
have $l_{i^{\dagger}}<(1+\rho^{\ast})e(S^{\ast})<\tau+(1+\rho^{\ast})e_{i}$
for each $i\in S^{\ast}$, and all the inequalities are strict). Therefore, we
have $\rho^{\ast}=0$ and $e(S^{\ast})>l_{i^{\dagger}}$ now. By Proposition
4.8, each $i\in e(S^{\ast})$ must satisfy $e(S^{\ast})<\tau+e_{i}$, which
implies $l_{i^{\dagger}}<\tau+e_{i}$.

Let $k_{m}$ be the agent in $S^{\ast}$ with minimum endowment. We have
$l_{i^{\dagger}}<\tau+e_{k_{m}}$. Since we have assumed the “break” statement
at Line 10 has never been executed, the for-loop at Line 8 can either
terminate when all the element of $K_{i^{\dagger}}$ are added to $S$ or exit
at Line 14. Since
$l_{i^{\dagger}}<\tau+e_{k_{m}}\leq\tau+(1+\rho_{\text{temp}})e_{k_{m}}\leq\tau+(1+\rho_{\text{temp}})e_{k_{j}}$
for all $\rho_{\text{temp}}\geq 0$ and all $k_{j}\in K_{i^{\dagger}}$ before
$k_{m}$, we know that the for-loop is still going on by the time $k_{m}$ is
added to $S_{i^{\dagger}}$. Therefore, $S^{\ast}\subseteq S_{i^{\dagger}}$.
However, this would imply $e(S_{i^{\dagger}})\geq
e(S^{\ast})>l_{i^{\dagger}}$, which contradicts to our assumption that the
“break” statement at Line 10 has not been executed. We have proved
$(1+\rho^{\ast})e(S^{\ast})=l_{i^{\dagger}}$.

Finally, we show that our assumption that the “break” statement at Line 10 has
never been executed implies the solution output by our algorithm is optimal.
We first notice that $\rho_{\text{temp}}$ is decreasing after each iteration
of the for-loop at Line 8, because $e(S_{i^{\dagger}})$ is increasing when
more and more elements are added to $S_{i^{\dagger}}$. If we have
$\rho_{\text{temp}}<\rho^{\ast}$ at certain iteration, we have
$\rho_{i^{\dagger}}<\rho^{\ast}$. Since
$(1+\rho_{i^{\dagger}})e(S_{i^{\dagger}})=l_{i^{\dagger}}=(1+\rho^{\ast})e(S^{\ast})$,
this would imply $e(S_{i^{\dagger}})>e(S^{\ast})$, which further implies
$\rho_{i^{\dagger}}\cdot
e(S_{i^{\dagger}})=l_{i^{\dagger}}-e(S_{i^{\dagger}})<l_{i^{\dagger}}-e(S^{\ast})=\rho^{\ast}\cdot
e(S^{\ast})$, contradicting to that $(S^{\ast},\rho^{\ast})$ is optimal.
Therefore, $\rho_{\text{temp}}\geq\rho^{\ast}$ throughout the for-loop at Line
8.

Let $k_{m}$ be the agent in $S^{\ast}$ with minimum endowment again. Since
$l_{i^{\dagger}}<\tau+(1+\rho^{\ast})e_{k_{m}}\leq\tau+(1+\rho_{\text{temp}})e_{k_{m}}$
(otherwise, the optimal solution $(S^{\ast},\rho^{\ast})$ should not have been
valid), we know that the for-loop at Line 8 is still going on by the time
$k_{m}$ is added to $S_{i^{\dagger}}$. As a result, $S^{\ast}\subseteq
S_{i^{\dagger}}$ and $e(S^{\ast})\leq e(S_{i^{\dagger}})$. This implies
$\rho_{i^{\dagger}}\cdot
e(S_{i^{\dagger}})=l_{i^{\dagger}}-e(S_{i^{\dagger}})\leq
l_{i^{\dagger}}-e(S^{\ast})=\rho^{\ast}\cdot e(S^{\ast})$, which further
implies
$\rho_{i^{\dagger}}\leq\rho^{\ast}\cdot\frac{e(S^{\ast})}{e(S_{i^{\dagger}})}\leq\rho^{\ast}$.
Thus, $(S_{i^{\dagger}},\rho_{i^{\dagger}})$ is optimal in terms of both
objectives, and so is the final output $(S,\rho)$ of Algorithm 3. ∎

######  Remark 4.14.

In Theorem 4.13, we set $\rho^{\ast}$ be the optimal solution in terms of the
_cost_ $\rho^{\ast}\cdot e(S^{\ast})$. If we consider $\rho^{\ast}$ be the
optimal solution in terms of the minimum _rate_ , then Algorithm 3 can still
obtain guarantee $\rho\leq\max\\{1,\rho^{\ast}\\}$, with Line 19 modified to
“find $i^{o}=\operatorname*{arg\,min}_{i}\rho_{i}$”. The proof of this is
similar to the proof of Theorem 4.13 and is left to the readers.

However, we note that the optimal solution in terms of the cost is not always
identical to the optimal solution in terms of the rate. Consider Example 3.1.
The solution with optimal cost is $(S=\\{1,2,3\\},\rho=\frac{2}{3})$ and the
solution with optimal rate is $(S=\\{1,4\\},\rho=\frac{7}{11})$.

Similarly to adding an external investment (Example 4.6), matching fund can
also hurt cooperation.

######  Example 4.15 (Harm of matching fund).

Let $\tau=9$, $\vec{e}=(4,4,4)$ and $\vec{m}=(4/11,4/11,4/11)$.
$S=\\{1,2,3\\}$ is a cooperative Nash equilibrium. However, if we use matching
fund with $\rho=1/4$, by Proposition 4.8, there is no cooperative Nash
equilibrium.

##  5 Discussion and Conclusion

In the paper, we study a variant of public goods games, the pivotal
participation game, and examine when cooperation can happen in the game.
First, we show that it is NP-complete to decide the existence of cooperation.
Then we consider two interventions to help agents to cooperate: external
investment and matching fund. We propose two algorithms that can help agents
to cooperate with near minimum cost. Finally, we show that matching fund can
be more powerful than an external investment.

There are several interesting directions for future work. The first is
considering more fine-grained interventions. For instance, we may change each
agent’s endowment or reward level by taxes or subsidies. However, these
interventions require more information, and the objective is not as well-
defined. Alternatively, we can consider the information aspect of the
interventions. In the paper, we know the game’s parameter and want to design
algorithms with reasonable computational complexity. Those parameters may be
unknown and private to agents, and agents may not report them truthfully.
However, we believe the computational issue is fundamental and will also arise
in the unknown parameter setting. Finally, some open problems are related to
our approximation algorithms, e.g., hardness results about additive
approximation for the optimal external investment or matching fund. Our
current construction does not directly extend to these settings.

## References

  * Baker II et al. [2009] Ronald J Baker II, James M Walker, and Arlington W Williams.  Matching contributions and the voluntary provision of a pure public good: Experimental evidence.  _Journal of Economic Behavior & Organization_, 70(1-2):122–134, 2009.
  * Battaglini and Harstad [2016] Marco Battaglini and Bård Harstad.  Participation and duration of environmental agreements.  _Journal of Political Economy_ , 124(1):160–204, 2016.
  * Bolle [2014] Friedel Bolle.  On a class of threshold public goods games: With applications to voting and the kyoto protocol.  Technical report, Discussion Paper, 2014.
  * Bramoullé et al. [2007] Yann Bramoullé, Rachel Kranton, et al.  Public goods in networks.  _Journal of Economic Theory_ , 135(1):478–494, 2007.
  * Brito et al. [1991] Dagobert L Brito, Eytan Sheshinski, and Michael D Intriligator.  Externalities and compulsary vaccinations.  _Journal of Public Economics_ , 45(1):69–90, 1991\.
  * Cato et al. [2020] Susumu Cato, Takashi Iida, Kenji Ishida, Asei Ito, Kenneth Mori McElwain, and Masahiro Shoji.  Social distancing as a public good under the covid-19 pandemic.  _Public health_ , 188:51–53, 2020.
  * Dybvig and Spatt [1983] Philip H. Dybvig and Chester S. Spatt.  Adoption externalities as public goods.  _Journal of Public Economics_ , 20(2):231 – 247, 1983.  ISSN 0047-2727.  doi: https://doi.org/10.1016/0047-2727(83)90012-9.  URL http://www.sciencedirect.com/science/article/pii/0047272783900129.
  * Finus [2002] Michael Finus.  Game theory and international environmental cooperation: any practical application?  _Controlling global warming: Perspectives from economics, game theory and public choice_ , pages 9–104, 2002.
  * Garey and Johnson [1979] Michael R Garey and David S Johnson.  _Computers and intractability_ , volume 174.  freeman San Francisco, 1979.
  * Goldstein and Pauly [1976] Gerald S Goldstein and Mark V Pauly.  Group health insurance as a local public good.  In _The role of health insurance in the health services sector_ , pages 73–114. NBER, 1976.
  * Hirshleifer [1983] Jack Hirshleifer.  From weakest-link to best-shot: The voluntary provision of public goods.  _Public choice_ , 41(3):371–386, 1983.
  * Jackson [2010] Matthew O Jackson.  _Social and economic networks_.  Princeton university press, 2010.
  * Karlan and List [2007] Dean Karlan and John A List.  Does price matter in charitable giving? evidence from a large-scale natural field experiment.  _American Economic Review_ , 97(5):1774–1793, 2007.
  * Karlan and List [2020] Dean Karlan and John A List.  How can bill and melinda gates increase other people’s donations to fund public goods?  _Journal of Public Economics_ , 191:104296, 2020.
  * Kaul et al. [1999] Inge Kaul, I Grungberg, and Marc A Stern.  Global public goods.  _Global public goods_ , 450, 1999.
  * Kempe et al. [2020] David Kempe, Sixie Yu, and Yevgeniy Vorobeychik.  Inducing equilibria in networked public goods games through network structure modification.  _arXiv preprint arXiv:2002.10627_ , 2020.
  * List and Price [2009] John A List and Michael K Price.  The role of social connections in charitable fundraising: Evidence from a natural field experiment.  _Journal of Economic Behavior & Organization_, 69(2):160–169, 2009.
  * Olson [2009] Mancur Olson.  _The Logic of Collective Action: Public Goods and the Theory of Groups, Second Printing with a New Preface and Appendix_ , volume 124.  Harvard University Press, 2009.
  * Palfrey and Rosenthal [1984] Thomas R Palfrey and Howard Rosenthal.  Participation and the provision of discrete public goods: a strategic analysis.  _Journal of public Economics_ , 24(2):171–193, 1984.
  * Rapoport [1988] Amnon Rapoport.  Provision of step-level public goods: Effects of inequality in resources.  _Journal of Personality and Social Psychology_ , 54(3):432, 1988.
  * Van de Kragt et al. [1983] Alphons JC Van de Kragt, John M Orbell, and Robyn M Dawes.  The minimal contributing set as a solution to public goods problems.  _The American political science review_ , pages 112–122, 1983.
  * Yu et al. [2020] Sixie Yu, Kai Zhou, Jeffrey Brantingham, and Yevgeniy Vorobeychik.  Computing equilibria in binary networked public goods games.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(02):2310–2317, Apr. 2020.  doi: 10.1609/aaai.v34i02.5609.  URL https://ojs.aaai.org/index.php/AAAI/article/view/5609.