Cooperation in Threshold Public Projects with Binary Actions

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) [Kaul et al., 1999; Finus, 2002; Battaglini and Harstad, 2016] to collectively reduce greenhouse gas emission. These settings have the nature of public goods games-the nonexclusiveness 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?

∗A full version of this paper is available at: https://arxiv.org/abs/ 2105.08572.

†Yiling Chen and Fang-Yi Yu are supported by the National Science Foundation under grants IIS 2007887.

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 [Brito et al., 1991], adoption of innovations [Dybvig and Spatt, 1983], public health insurance [Goldstein and Pauly, 1976], or even practicing social distancing [Cato et al., 2020]. Second, participants have heterogeneous endowments and rewards. Many well-studied public goods games are symmetric among agents: agents have symmetric endowments [Van de Kragt et al., 1983; Palfrey and Rosenthal, 1984] and the reward is uniformly distributed among agents [Rapoport, 1988] or only depends on the number of contributing agents [Hirshleifer, 1983; Jackson, 2010]. 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 show that successful cooperation is always possible when informally agents' endowments are small or the reward levels are large enough (Theorem 6). However, in general, we prove that it is NP-complete to decide whether there exists a Nash equilibrium such that the project succeeds (Theorem 5). This result suggests large groups may struggle to cooperate in public projects, which is supported in the literature. [Olson, 2009]

Then we develop algorithms to help achieving cooperation. We consider two natural interventions: The algorithms can 1) add an external investment δ to the public project, or 2) commit to a matching fund so that for every 1 value of investment from agents, the algorithms add ρ to the project. Both interventions are common in practice. [Baker II et al., 2009; Karlan and List, 2020] We want to minimize the additional cost due to those interventions. We first show that it is NPhard 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 13 and 19) 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 16) This provides a theoretical explanation for the efficacy of matching funds in the field. [Karlan and List, 2007]

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 [Palfrey and Rosenthal, 1984] 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 [Bramoull´e et al., 2007]. For this category, recent works also consider the computational complexity of finding equilibria and design algorithms to help cooperation [Yu et al., 2020; Kempe et al., 2020]. 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 τ ∈ R≥0 for success. Each agent i ∈ [n] has an indivisible endowment that has an equivalent value of ei ∈ R≥0, and she can decide whether to participate by contributing all her endowment or free ride, ai ∈ {0, 1}. Thus, agents' strategy profile can be denoted by S := {i : ai = 1} ⊆ [n] which is the set of agents who participate. Let e(S) := ∑j∈S ej be the total value of contributions made by agents in S. The project succeeds if e(S) ≥ τ. When the project succeeds, each agent's reward depends on her reward level 0 < mi < 1. Specifically, given a strategy profile S, agent i's utility is

We use (⃗e, ⃗m, τ) to denote a pivotal participation game instance, where ⃗e = (e1, . . . , en) encodes each agent's endowment and ⃗m = (m1, . . . ,mn) 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 ∈ S, Ui(S) ≥ Ui(S \ {i}). If i /∈ S, Ui(S) ≥ Ui(S ∪ {i}). A strategy profile S is a cooperative Nash equilibrium if it is a Nash equilibrium and the project succeeds, e(S) ≥ τ .

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 ̸= i : aj = 1} be other agents' action. If agent i's action does not affect whether the project succeeds, Ui(S-i ∪{i})- Ui(S-i) ≤ -ei +miei < 0. That is, agent i will invest only if her investment can change the project from unsuccessful to successful, e(S-i) < τ ≤ e(S-i) + ei. However, the following example shows this is just a necessary condition.

Example 1. Let ⃗e = (2, 2, 2, 9), ⃗m = (0.2, 0.2, 0.2, 0.5), and τ = 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 15m4 = 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 ei and reward level mi are.

Proposition 2. Given the other agents' actions S-i, agent i's best response is participating if and only if

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

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), Ui(S-i ∪ {i}) - Ui(S-i) ≤ -ei +miei < 0. Thus, agent i's best response is not participating. Finally, if Eqn. (3) does not hold,

so agent i's best response is not participating. This completes the proof.

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

Proof. Suppose ei ≥ τ 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 mi < 1.

3.1 Nash Equilibria

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

Proposition 4. Given a pivotal game (⃗e, ⃗m, τ), S is a cooperative Nash equilibrium if and only if for all i ∈ S

We show 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 5. Deciding if a pivotal participation game (⃗e, ⃗m, τ ) has a cooperative Nash equilibrium is NP-complete.

Proof. This decision problem is clearly in NP: the set of agents S ̸= ∅ that invest can be served as a certificate, and Proposition 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 [Garey and Johnson, 1979]: given a set S of 2T positive integers c1, . . . , c2T , decide if there exists a subset T of T integers whose sum is exactly 12 ∑2T i=1 ci. We assume without loss of generality that c1 ≤ · · · ≤ c2T .

We construct a pivotal participation game instance (⃗e, ⃗m, τ) as follows. Let M = 100 ∑2T i=1 ci and N = 100MT. The instance contains n = 2T + 2 agents, with ei = N +M + 2ci for i = 1, . . . , 2T , and e2T+1 = N + 1 and e2T+2 = N. It is straightforward to see that e2T+2 < e2T+1 < e1 ≤ · · · ≤ e2T . The parameter τ is set to τ = 1 + e2T+1 + 1 2 ∑2T i=1 ei = 12 ∑2T i=1 2ci +(N +M)T +N +2. Finally, ⃗m is set to the followings: for each i = 1, . . . , n, mi = ei τ+e2T+2-1 . For each i = 1, . . . , n, we have max{ ei mi , τ} = τ +e2T+2 -1 = 12 ∑2T i=1 2ci + (N +M)T + 2N + 1, which must be a lower bound to e(S) by Proposition 4.

Suppose the partition instance is a YES instance, and let T be the subset of T integers such that ∑i∈T ci = 12 ∑2T i=1 ci. By slightly abuse of the notation, let T be the subset of the first 2T agents that corresponds to the set of T selected integers. We show that S = T ∪ {2T + 1, 2T + 2} is a valid Nash equilibrium. To see this, the total investment is e(S) = 2 · (∑i∈T ci ) + (M +N)T + 2N + 1 = 2 · ( 1 2 ∑2T i=1 ci) + (M +N)T + 2N + 1 = τ + e2T+2 - 1 = max{τ, ei mi } for each i = 1, . . . , n. Moreover, for each i = 1, . . . , n, by noticing that e2T+2 ≤ ei, we have e(S) ≤ τ + ei - 1 < τ + ei. By Proposition 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 = ∅. To derive a contradiction, suppose S ̸= ∅ is a Nash equilibrium, and we consider two cases: 2T + 2 ∈ S and 2T + 2 /∈ S.

Suppose 2T + 2 ∈ S. By Proposition 4, we must have e2T +2 m2T+2 = τ + e2T+2 - 1 ≤ e(S) < τ + e2T+2. Since all ei's are integers, this implies e(S) = τ + e2T+2 - 1, and it must be that ∑i∈S\{2T+2} ei = τ -1 = e2T+1 + 1 2 ∑2T i=1 ei.

By our construction, each of e1, . . . , e2T is an even number, while e2T+1 is an odd number. Thus, e2T+1 + 12 ∑2T i=1 ei is an odd number (note that ∑2T i=1 ei is a multiple of 4). By the parity of the equation, we must have 2T + 1 ∈ S. This implies ∑i∈S\{2T+1,2T+2} ei = 12 ∑2T i=1 ei. Let T = S \ {2T + 1, 2T + 2}. We have ∑i∈T ei = 1 2 ∑2T i=1 ei.

Next, it is easy to see that |T | = T . If |T | < T , ∑i∈T ei ≤ (M+N)(T -1)+ ∑i∈T 2ci < (M+N)(T -1)+ 1 50 M < (M + N)T < 1 2 ∑2T i=1 ei. If |T | > T, ∑i∈T ei > (M + N)(T + 1) > (M +N)T + 1 50 M > 12 ∑2T i=1 ei.

Knowing that |T | = T, by canceling the (M +N) terms on both sides of the equation ∑i∈T ei = 1 2 ∑2T i=1 ei and then divide the both sides by 2, we have ∑i∈T ci = 12 ∑2T i=1 ci, which contradicts to that the partition instance is a NO instance.

It remains to derive a contradiction for the case 2T+2 /∈ S. Firstly, we show that |S| ≥ T + 2. If |S| ≤ T + 1, we have e(S) = ∑i∈S ei < (N +M)(T + 1) + 1 50 M + 1 < (M + N)T + 1.1N < τ + e2T+2 - 1 = ei mi , which implies S cannot be a Nash equilibrium by Proposition 4.

Having shown that |S| ≥ T +2, we discuss two sub-cases: 2T+1 /∈ S and 2T+1 ∈ S. For the first sub-case 2T+1 /∈ S, since ei > M +N for all i = 1, . . . , 2T, we have e(S) = ∑i∈S ei > (T + 2)(M +N). On the other hand, for each i = 1, . . . , 2T , we have τ +ei = 12 ∑2T i=1 2ci + (M +N)T + N +2+(M+N)+ci < (M+N)(T +1)+N + 1 25 M + 2 < (M +N)(T + 2). Therefore, e(S) > τ + ei for each i = 1, . . . , 2T . Since S ⊆ {1, . . . , 2T}, S cannot be a Nash equilibrium by Proposition 4.

Consider the second sub-case 2T + 1 ∈ S. There are at least T + 1 agents in {1, . . . , 2T}, so e(S) ≥ (M +N)(T + 1) + N + 1 = (M + N)T + 2N + M + 1. On the other hand, τ + e2T+1 = 1 2 ∑2T i=1 2ci + (M + N)T + 2N + 3 < (M + N)T + 2N + M < e(S). By Proposition 4, S cannot be a Nash equilibrium, and we derive a contradiction again.

We have derive contradictions for all possible cases for S ̸= ∅. Therefore, the only Nash equilibrium is S = ∅ when the partition instance is a NO instance. We conclude the theorem.

While cooperative equilibria need not in general exist (Example 1) and are hard to compute (Theorem 5), 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 τ for each agents (as long as the sum of all agents' endowments exceeds τ). Intuitively, our result shows that cooperation becomes easy, if agents' endowments are small or the reward level are large enough, in contrast to Example 1.

Theorem 6. Given a pivotal participation game (⃗e, ⃗m, τ), if ei/mi ≤ τ for all i, there exists a successful cooperation if and only if ∑ni=1 ei ≥ τ . 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 7. Given a pivotal participation game (⃗e, ⃗m, τ), a subset of agents S is minimal if 1) e(S) ≥ τ, and 2) for any j ∈ S, e(S \ {j}) < τ .

Proposition 8. Given a pivotal participation game (⃗e, ⃗m, τ), if ei/mi ≤ τ 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 4. Given an arbitrarily minimal subset of agents S, since ei/τ ≤ mi, the left part of (4) holds due to 1) of Definition 7. Suppose the right part of (4) fails for some agent j ∈ S. We have e(S) ≥ τ+ej , which implies e(S \ {j}) ≥ τ, which contradicts to 2) of Definition 7. Thus, the right part of (4) also holds for any i ∈ S.

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

Proof of Theorem 6. Suppose ∑ni=1 ei ≥ τ. The following simple algorithm finds a minimal subset of agents S: initialize S = ∅; iteratively add an arbitrary agent i to S, and terminate the algorithm when e(S) ≥ τ . The algorithm will terminates with e(S) ≥ τ since ∑ni=1 ei ≥ τ. It is easy to see that the algorithm finds a minimal subset of agents S, and by Proposition 8, S is a Nash equilibrium.

Suppose ∑ni=1 ei < τ . The left part of (4) in Proposition 4 will always fail. Therefore, there does not exist a cooperative Nash equilibrium.

In the full version of this paper, 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.

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 11). Then, we design two algorithms (Algorithms 1 and 2) which take parameters of the game (⃗e, ⃗m, τ) and output a valid intervention. We show that the cost of each algorithm's intervention is close to the optimal with small additive errors (Theorems 13 and 19). Finally, we compare these two interventions and prove that matching fund is more powerful than adding an external investment in Proposition 16.

4.1 External Investment

In this section, we consider mechanisms that add investment δ to the public project in addition to agents' investment. Thus, agent i's utility, Ui(S) becomes

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

Proposition 9. Given a pivotal participation game instance (⃗e, ⃗m, τ) with external investment δ, S is a cooperative Nash equilibrium if and only if for all i ∈ S

Thereafter, we will assume τ + ei > ei mi for each agent i, for otherwise, i will never be a part of a cooperative Nash equilibrium by Proposition 9, and we can remove i from consideration.

We say a solution (S, δ) is valid if S is a Nash equilibrium under external investment δ. The following theorem shows that the optimal solution to this minimization problem always exists. We defer the proof to the full version.

Theorem 10. Given a pivotal participation game (⃗e, ⃗m, τ), let ∆ ⊆ [0,∞) be the set of all valid external investment δ. We have inf ∆ ∈ ∆.

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

Theorem 11. Given a pivotal participation game instance (⃗e, ⃗m, τ), letting δ∗ ≥ 0 be the minimum valid external investment, for any F > 0 that may depend on (⃗e, ⃗m, τ), it is NP-hard to approximate δ∗ to within factor F .

Proof. Theorem 5 implies that it is NP-complete to decide if δ∗ = 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 = maxi:1≤i≤n{ei}. The algorithm is described in Algorithm 1.

The algorithm works as follows. It considers n possible values l1, . . . , ln for e(S)+δ. For each possibility e(S)+δ = li, it iteratively adds an agent k with lk ≤ li < uk 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) ≤ li cannot be maintained (when the for-loop at Line 7 exits at Line 9). The algorithm finds a solution for e(S) + δ = li by setting δ = li - 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 12. Our algorithm has a desirable fairness property: "richer people contribute first" [List and Price, 2009]. 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 (Si, δi) preserves this property. In particular, for i = n, (Sn, δn) strictly preserves this property (by Line 5 and the fact that uk is larger whenever ek is larger). When implementing Algorithm 1, we can compare the n solutions and trade off between the investment δ and the said fairness property.

Algorithm 1 Approximation algorithm for pivotal participation game with external investment

Input: a pivotal participation game instance (⃗e, ⃗m, τ) Output: a set of agent S that invest; the amount of external investment δ

1: for each i ∈ [n], let ui = τ + ei and li =max{τ, ei mi } 2: sort agents such that l1 ≤ l2 ≤ · · · ≤ ln 3: for i = 1, . . . , n do 4: initialize Si = ∅ 5: let Ki = {k ∈ [n] : lk ≤ li < uk} 6: sort agents in Ki so that ek1 ≥ ek2 ≥ · · · ≥ ek|Ki| 7: for j = 1, . . . , |Ki| do 8: if e(Si ∪ {kj}) > li then 9: break 10: end if 11: update Si = Si ∪ {kj} 12: end for 13: set δi = li - e(Si) 14: end for 15: find io = argmini δi 16: return (Sio, δio)

Proof. We first show that the solution output by Algorithm 1 is valid. We show that the solution (Si, δi) found in each iteration of the for-loop is valid. We have e(Si)+δi = li and each k ∈ Si satisfies lk ≤ li < uk (guaranteed by Line 13 and 5 of the algorithm), Proposition 9 implies that Si is a Nash equilibrium. It remains to prove the approximation guarantee δ ≤ max{e, δ∗ }.

Suppose agents are ordered such that l1 ≤ · · · ≤ ln. Let (S, δ) be the solution output by the algorithm. Let (Si, δi) be the solution output at i-th iteration of the for-loop at Line 3. Let (S∗ , δ∗ ) 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 δ < e, in which case the approximation guarantee is proved. To see this, Line 8 and 13 ensure that δi = li - e(Si) < ekj ≤ e. Since the final solution output by the algorithm is no worse than (Si, δi), we have δ ≤ δ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∗ , δ∗ ). Let i† be the agent with the largest index such that e(S∗ ) + δ∗ ≥ li†. We show that each j ∈ S∗ satisfies lj ≤ li† < uj. Suppose there exists j ∈ S∗ with lj > li†. We first know i† < n. By Proposition 9, we must have e(S∗ ) + δ∗ ≥ lj ≥ li†+1 to make the solution valid. However, this contradicts to our assumption that i† is the agent with the largest index satisfying e(S∗ )+δ∗ ≥ li† . Suppose there exists j ∈ S∗ with uj ≤ li† . Since we assumed li† ≤ e(S∗ ) + δ∗ , Proposition 9 implies that (S∗ , δ∗ ) should not have been valid.

In addition, our assumption that the "break" statement at Line 9 has never been executed implies that e(S∗ ) + δ∗ = li†. Suppose otherwise e(S∗ ) + δ∗ > li†. We have δ∗ = 0, for otherwise we can always decrease the value of δ∗ while maintaining e(S∗ ) + δ∗ ≥ li†, which contradicts to that δ∗ is optimal. As a result, e(S∗ ) + δ∗ > li† implies e(S∗ ) > li†. Since we have proved that each j ∈ S∗ satisfies lj ≤ li† < uj , at iteration i† of our algorithm, we must have S∗ ⊆ Ki† . Therefore, e(Ki† ) ≥ e(S∗ ) > li† , the "break" statement will be executed before all the |Ki† | agents are added to Si† , which contradicts to our assumption.

Finally, we have proved that e(S∗ ) + δ∗ = li†, and we also have S∗ ⊆ Ki† at iteration i† of our algorithm. Since the "break" statement has not been executed, we have Si† = Ki† , and δi† = li† - e(Si†) ≤ li† - e(S∗ ) = δ∗ . Therefore, the solution output at i† -th iteration of our algorithm is already optimal, and the final output of our algorithm is no worse than this.

4.2 Matching Funds

In this section, we consider another intervention-matching funds. The mechanism can commit to a rate ρ ≥ 0, and increase the investment from e(S) to (1 + ρ)e(S). Thus, agent i's utility Ui(S) becomes

Assumption 14. We assume that the rate of matching funds ρ has a budget constraint ρ < ¯ ρ where ¯ ρ = 1 maxi∈[n] mi - 1.

This assumption ensures (1 + ρ)mi < 1 for each agent i. To justify this assumption, the total reward level ∑i mi 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 ρ is often a small constant (e.g., 1-to-1, 2-to-1, and 3-to-1). This makes mi(1+ρ) significantly less than 1. Secondly, the behavior of an agent with mi(1+ρ) ≥ 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 4 and 9 we have the following characterization of cooperative Nash equilibrium. The details are left to the readers.

Proposition 15. Given a pivotal participation game instance (⃗e, ⃗m, τ ) with matching funds ρ < ¯ ρ, S is a cooperative Nash equilibrium if and only if for all i ∈ S

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

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

Proposition 16. For all (⃗e, ⃗m, τ), for any valid solution (S, δ) where the external investment δ is not prohibitively large δ < ¯ ρ · e(S), S is also a cooperative Nash equilibrium with matching funds ρ = δ/e(S). Moreover, the cost of matching funds ρ · e(S) is exactly δ.

Proof. If adding external δ endowment makes cooperation successful, setting ρ = δ/e(S), S is also a successful cooperation because of Proposition 15 and τ + ei ≤ τ + (1 + ρ)ei for all i ∈ S. Moreover, the cost ρ · e(S) is δ when agents in S cooperate.

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. The proof is deferred to the full version of this paper.

Theorem 17. Given a pivotal participation game (⃗e, ⃗m, τ), let ∆ ⊆ [0,∞) be the set of all valid rates of matching funds ρ. Suppose ∆ ̸= ∅. We have inf ∆ ∈ ∆. Moreover, there exists a valid solution (S∗ , ρ∗ ) such that ρ∗ · e(S∗ ) ≤ ρ · e(S) for all possible solutions (S, ρ).

Again, Theorem 5 straightforwardly implies that the problem is NP-hard to approximate to any finite multiplicative factor for both objectives (the rate ρ and the cost ρ·e(S)). Therefore, a theorem similar to Theorem 11 can be concluded. We defer the theorem statement and proof to the full version.

We show that we can achieve additive approximation to both objectives by adaption of Algorithm 1, under the very mild assumption ¯ ρ ≥ 1. It is straightforward to check that Algorithm 2 runs in polynomial time.

Remark 18. The "richer people contribute first" property for Algorithm 1 mentioned in Remark 12 also holds for Algorithm 2.

Theorem 19. Given a pivotal participation game (⃗e, ⃗m, τ) with ¯ ρ ≥ 1 such that a cooperative Nash equilibrium exists under certain ρ ∈ [0, ¯ ρ), letting (S∗ , ρ∗ ) be a valid solution with minimum cost ρ∗ ·e(S∗ ) and e = maxi:1≤i≤n{ei}, Algorithm 2 finds a collaboration (S, ρ) with cost upper-bounded by ρ · e(S) ≤ max{e, ρ∗ · e(S∗ )} and rate upper-bounded by ρ ≤ max{1, ρ∗ }.

Although being more complex, the main ideas of the proof are the same as the proof of Theorem 13. The proof is available in the full version of this paper.

Remark 20. In Theorem 19, we set ρ∗ be the optimal solution in terms of the cost ρ∗ · e(S∗ ). If we consider ρ∗ be the optimal solution in terms of the minimum rate, then Algorithm 2 can still obtain guarantee ρ ≤ max{1, ρ∗ }, with Line 19 modified to "find io = argmini ρi". The proof of this is similar to the proof of Theorem 19.

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 1. The solution with optimal cost is (S = {1, 2, 3}, ρ = 2 3 ) and the solution with optimal rate is (S = {1, 4}, ρ = 7 11 ).

Algorithm 2 Approximation algorithm for pivotal participation game with matching funds

Input: a pivotal participation game instance (⃗e, ⃗m, τ) Output: a set of agent S that invest; the rate of matching funds ρ

1: for each i ∈ [n], let li =max{τ, ei mi } 2: compute ¯ ρ = 1 maxi∈[n] mi - 1 3: sort agents such that l1 ≤ l2 ≤ · · · ≤ ln 4: for i = 1, . . . , n do 5: initialize Si = ∅ 6: let Ki = {k : lk ≤ li} //different to Algorithm 1 here 7: sort agents in Ki so that ek1 ≥ ek2 ≥ · · · ≥ ek|Ki| 8: for j = 1, . . . , |Ki| do 9: if e(Si ∪ {kj}) > li then 10: break 11: end if 12: let ρtemp = li e(Si∪{kj}) - 1 13: if li ≥ τ + (1+ρtemp)ekj then 14: break 15: end if 16: update Si = Si ∪ {kj}, ρi = ρtemp 17: end for 18: end for 19: find io = argmini{ρi · e(Si)} 20: if ρio ≥ ¯ ρ then 21: return no solution exists 22: end if 23: return (Sio, ρio)

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.