Game-theoretic Analysis of Effort Allocation of Contributors to Public Projects

1 Introduction

Often, we jointly work together on public projects. This ranges from small projects involving a few contributors (e.g., a medium sized feature request on GitHub) to massive projects involving several nations (e.g., International Space Station). Each contributor can allocate his/her available effort (e.g., time) to the set of projects and determines the utility trade-off between reward (e.g., satisfaction) and cost (e.g., how fatiguing it is to allocate effort) per project. Joint projects can succeed or fail for many reasons: shifting requirements, management inexperience, etc., [McConnell, 1996]. One common pivotal point that many projects have is that there is a minimal threshold or amount of work that must be completed before the project succeeds. This can apply to public projects, e.g., in software development [McConnell, 1996]

∗Corresponding author

and "Get Big Fast" type businesses [Spolsky, 2004]. The common thread is that a given project provides little to no utility until it is completed in its entirety. Project failure is not uncommon and contributors continue to exert effort in projects which may not succeed [McConnell, 1996]. This behavior seems irrational on its face, but effort allocation behavior among contributors to such projects is complex. To judge the rationality of a contributor's decision to allocate effort to a particular set of projects, these questions must be explored:

(Modeling) How would strategic contributors behave if a project's success depended solely on total contribution meeting a threshold? How would strategic contributors allocate effort to a given available set of projects with such requirements? (Computation) What are the corresponding (Nash) equilibrium computation questions and results?

Our goal in this paper is to address the above questions, theoretically and computationally, through game-theoretic models and analysis focusing on strategic interactions of strategic and rational contributors for public project contributions.

Our Contribution. To address the modeling and computational questions, we first introduce a game-theoretic Effort Allocation model of Contributors to Public Projects (EACPP) where a set D of contributors determines the number of discrete units of effort (e.g., hours) to allocate to a set P of available projects with contribution threshold requirements. Each contributor i ∈ D gains utility for each project j ∈ P depending on i's effort allocation for project j, aij; i's intrinsic value of j, vij; i's skill related to j, sij; the cost for i of each unit of effort contributed to j, cij; j's contribution threshold, tj; and most importantly, the effort allocation of other strategic contributors. Given the EACPP model, our interest is the Nash equilibrium (NE) computational questions, and the measurement for the efficiency of NEs. We first show-via novel reduction from partition problems-that the following are NP-complete, even in the restricted settings where each contributor has a single unit of effort to allocate to projects, skill is project-independent (i.e., sij = si), and effort is costless (i.e., cij = 0): (1) determining the existence of a NE, (2) determining the existence of a NE with at least k successful projects, (3) determining the existence of a NE with social welfare of at least V , and (4) determining the existence of a NE with a fixed effort allocation of contributors.

We then consider further restrictions on the model parameters. First, for the restricted settings where vij = vi or vij = vj under certain threshold and skill configurations, we show that a NE always exists and can be computed in polynomial time using an ordered sequential response algorithm (see Theorems 3 and 4). Second, when there are constant number of projects, we can find all NEs in pseudo-polynomial time in terms of the number n of contributors and parameter r := maxj∈P (1 + ∑i∈D sij) (see Theorem 5).

We consider a planner's problem of obtaining optimal outcomes that maximize either (i) the social welfare (i.e., the sum of the utilities of the contributors) or (ii) the number of successful projects by allocating effort of contributors to projects. We show that the corresponding optimization problems are NP-hard (see Theorem 6). We investigate the efficiency of NEs by examining the price of anarchy (PoA) [Koutsoupias and Papadimitriou, 1999; Roughgarden, 2005], which is defined as the ratio between the optimal solution and the worst NE, and the price of stability (PoS) which is defined as the ratio between the optimal solution and the best NE [Anshelevich et al., 2008] (See Section 5.) We show that they can be unbounded for both objectives, and identify the restricted settings where they are bounded or even equal to one.

1.1 RelatedWork

Below, we compare EACPP and our contributions to related work and highlight the key differences in several areas.

Project Games. The most related problem to EAPCC is project games [Bil`o et al., 2019] where each player selects a single project. Any project selected by at least one player is realized and the reward for the project is divided among contributing players. Similar to EACPP, players have skill (called weight) and reward is split proportionally based on contribution. The key difference from EACPP is that there is no threshold. One can view their model as a special case of ours under several restrictions on the model parameters, including zero threshold and cost for each project. Throughout

the paper, we will elaborate the implication of their results.

Contests. There is a line of research where a set of contestants competes in a set of contests [DiPalantino and Vojnovic, 2009; Bernerg˚ard and W¨arneryd, 2017; Morgan et al., 2017; Azmat and M¨oller, 2009; Azmat and M¨oller, 2017; Chan et al., 2020; Xu et al., 2019]. In such settings, each contestant selects (a subset of) contests and/or determines the amount of effort to compete for prizes. In these settings, each contest is typically modeled using single contest semantics such as a Tullock contest, all pay-auction, and their variants (e.g., see [Dechenaux et al., 2015; Konrad, 2009]). However, these models do not consider threshold requirement for each contest, and the contest's success is not measured in terms of overall contributions of the contestants.

Congestion Games. In a congestion game (see e.g., [Rosenthal, 1973; Fotakis, 2015; Kontogiannis and Spirakis, 2005; Monderer and Shapley, 1996; Mavronicolas et al., 2007; Kleinberg and Oren, 2011]), there is a set of resources and a set of players. Each player's action set consists of some subsets of the resources. The player's goal is to select an action that minimizes the sum of the delay of each selected resource in the selected action where the delay is defined to be some increasing function of the number of players that selected the resource. Our EACPP is different from congestion games and their variations mainly in that there is a threshold for each resource/project and positive utility can only be obtained if there are sufficient contributions to the resource/project.

Networked Public Goods/Crowdfunding Games. Recent related works (see e.g., [Yu et al., 2020; Komarovsky et al., 2015; Kempe et al., 2020; Arieli et al., 2018]) consider networked public goods games where each individual makes a binary decision to contribute to a public good project. An individual decision depends on (a function that maps) the number of other individuals in the individual's social network and the cost of contribution. Different from EACPP, public goods games and their variants consider only a single project with no threshold requirement or/and individual project model parameters related to values and effort contributions.

2 Game-theoretic Effort AllocationModels

In this section, we present a game-theoretic Effort Allocation model of Contributors to Public Projects (EACPP). In an EACPP game-theoretic model, we have a set D = {1, ..., n} of n contributors and a set P = {1, ...,m} of m projects indexing using i and j, respectively.

Contributors. Each contributor i ∈ D allocates his/her (discrete) units of effort hi (e.g., work hours) among the set of public projects. Thus, the set of i's actions is Ai = {ai ∈ {0, 1, ..., hi}m | ∑mj=1 aij = hi} where, given an allocation vector ai ∈ Ai, aij specifies the units of effort allocated to project j ∈ P. We let A = ∏ni=1 Ai be the joint-action set of effort allocation vectors. Contributor i's contribution depends on both the allocated effort and personal skills on the projects. Skill can be viewed as the efficiency of converting effort into contribution (e.g., an experienced software developer is more efficient than a novice). For each i ∈ D, let the integer sij ≥ 0 be i's skill for project j. Given allocation vector ai ∈ Ai, i's contribution to j is aijsij, representing the impact of i's skill on the effort they allocated to j. For each i ∈ D, there is a (per-unit effort) cost cij for each project j ∈ P such that the total cost of j to i under ai is defined by aijcij. Finally, there is an overall personal (satisfaction) value vij ≥ 0 contributor i has for project j if j is successful. Projects. Each project j ∈ P has a contribution threshold tj ≥ 0 where the project is successful when the total contribution to j by all contributors exceeds the threshold. Given joint-action a ∈ A, the total contribution on project j is TCj(a) = ∑ni=1 aijsij. A project j succeeds if and only if TCj(a) > 0 and TCj(a) ≥ tj .

Utilities. Given an action profile a ∈ A, a reward for contributor i ∈ D for project j ∈ P is defined to be

As motivated from existing literature (e.g., project games [Bil`o et al., 2019] and Tullock contests [Dechenaux et al., 2015; Konrad, 2009]), we consider a simple proportional rule to divide utility among contributors according to contribution made. This allows us to model many complex motivations, such as the prestige of being listed as a top contributor to a popular project or differential allocation of reward based on the proportion of work done. If i contributes additional work beyond tj then i receives a larger proportion of the project, but the value of the project is not increased. The utility of contributor i ∈ D is defined to be ui(a) = ∑mj=1 rij(a) which is the sum of the rewards over the projects.

Objectives. We quantify the quality of an action profile a ∈ A by considering two objectives, namely, the social welfare (SW) objective and the projects successful (PS) objective: (1) SW(a) = ∑i∈D ui(a) is the total utility of all contributors, and (2) PS(a) = ∑j∈P 1[TCj(a) ≥ tj ∧TCj(a) > 0] is the number of successful projects, where 1[·] is an indicator function. The planner wants to find optimal solutions that maximizes the objectives. We let aoptsw ∈ argmaxa∈A SW(a) and aoptps ∈ argmaxa∈A PS(a) be the optimal solutions that maximize the SW and PS objectives, respectively.

Given an EACPP instance I = (D, P, {cij}, {sij}, {vij}, {hi}, {tj}) (indices omitted), our goal is to compute a (pure-strategy) Nash equilibrium (NE).

Definition 1. A joint-effort allocation vector a ∈ A is a (pure-strategy) Nash equilibrium (NE) if and only if ui(ai, a-i) ≥ ui(¯ai, a-i) for any ¯ai ∈ Ai and each i ∈ D.

Unfortunately, a NE might not always exist in an arbitrary EACPP. Below we provide an example.

Example 1. Consider an instance I = (D, P, {cij}, {sij}, {vij}, {hi}, {tj}) where D = {1, 2}, P = {1, 2}, cij = 0, vij = v, hi = 1 for all i ∈ D, j ∈ P, s1j = s1, s2j = s2, and tj = s1 for all j ∈ D for s1 > s2. In such a setting, contributor 1 alone is enough to make the projects successful whereas contributor 2 cannot. Contributor 2 always prefers to select the same project as contributor 1, and contributor 1 would always prefer to work on any one of the projects independently. It is easy to see that there is no NE.

We note that our model can be further generalized and extended to cases where (a) the total contribution TCj can be an arbitrarily non-decreasing function and (b) the proportional contribution term in the reward function rij can be any contest success function. However, as we will see in the next section, the computational questions related to NE are already NP-complete for various instances of our model.

We also remark that EACPP captures simultaneous strategic interactions of the contributors when they make effort allocation decisions at the same time in the complete information setting. It would be interesting to extend the models further to (a) consider sequential interactions where contributors determine effort allocation over time and/or (b) incomplete information where the model parameters (e.g., values, skills, and costs) are drawn from some distributions.

3 Complexity of Computing a NE in EACPP

In this section, we consider the complexity questions related to the existence of a NE in EACPP. In particular, we show that the following questions are all NP-complete in EACPP:

1. Is there a NE?
2. Is there a NE where at least k projects are successful?
3. Is there a NE that obtains a social welfare of at least V ?
4. Is there a NE that is consistent with a fixed assignment?

All the computational questions are NP-complete even in the case where cij = 0, sij = si, and hi = 1 for all i ∈ D and j ∈ P (i.e., each contributor has a cost of zero for each project with skill independent of the projects and can only select a single project). Our reductions use the known NPcomplete Partition Problem (PP) [Garey and Johnson, 1979]:

Partition Problem (PP) Given a set X = {x1, ..., xn} of n distinct positive integers, is there a partition of X to X1 and X2 such that ∑x∈X1 x = ∑x∈X2 x?

Theorem 1. It is NP-complete to determine whether there is a NE in EACPP.

Proof. This problem is in NP, because we can verify whether a given profile a ∈ A is a NE in polynomial time by checking for m- 1 deviations for each of the n contributors.

To prove our claim, we reduce from PP. Consider an instance of PP with X = {x1, ..., xn} of n positive (unique) integers such that x1 > x2 > ... > xn (with the total sum divisible by 2), we reduce it to an instance of EACPP I = (D, P, {cij}, {sij}, {vij}, {hi}, {tj}) via the following:

• Let m = n + 2 be the number of projects;
• Let n be the number of contributors;
• Let hi = 1 for each i ∈ D;
• Let sij = xi and cij = 0 for each i ∈ D and j ∈ P;
• For each j ∈ P \ {1, 2}, let xn-1 > tj > xn be some threshold and t1 = t2 = T = ∑x∈X x 2 ;
• For each i ∈ D \ {n} and j ∈ P \ {1, 2}, vij = vi > 0 and vi1 = vi2 such that vi1 sij T > vi > vi1 sij T +0.5 ;
• For n and j ∈ P \ {1, 2}, vnj = vn > 0 and vn1 = vn2 such that vn1 snj 2T > vn.

The next to last parameter settings ensure that contributor i ∈ D \ {n} always prefers either project 1 or project 2 when the projects are successful with exactly T total contribution and, otherwise, one of the other projects (3, ..., m) without any other contributors. The last setting ensures that n prefers either project 1 or 2 as long the projects are successful.

PP solution =⇒ NE. It is not hard to see that if there is partition of X into X1 and X2 with the same sum T, then we have a NE. In particular, for i with skill xi ∈ Xl for all j for some l = 1, 2, then ail = 1 and aik = 0 for each other project k. It is easy to check that for i ∈ D, i has no incentive to deviate (see the last two items listed).

NE =⇒ PP solution. Suppose there is a NE. We argue that, in any NE, n must either select successful project 1 or project 2. If this is not the case, then n must select one of the {3, ...,m} projects. If there are other contributors in {3, ...,m}, it must be the case they are all in different projects and n will select one of them as a best response, say the project with i because each project j requires threshold tj > xn, which cannot be competed by n alone. However, i will deviate to another project without any contributor (which always exists since there are n other projects).

If there are no other contributors in {3, ...,m}, it must be the case that all of them are in either project 1 or project 2, but this cannot be a NE, since the threshold of each project is T and n is not in project 1 or 2. As a result, the projects must have threshold greater or less than T. In either case, this cannot be a NE as the contributors will deviate (by construction).

In order to sustain a NE where n is in project 1 or project 2, at least one of the projects has to be successful with exactly T total contribution (including xn). The remaining contributors are either together in project 1 or 2 or in different projects of {3, ...,m}. It follows that one can construct a solution of PP by letting X1 be the set of positive integers with xi corresponding to ail = 1 for l(= 1 or 2) project(s) with exactly T contribution with xn. The remaining positive integers/contributors will be in X2 which has the same sum as X1 by construction.

Theorem 2. It is NP-complete to determine whether there is a NE with at least k successful projects in EACPP, determine whether there is a NE with social welfare at least V , or determining the existence of a NE with a fixed effort allocation of contributors. 1

We remark that positive results can be achieved in some more restricted settings. When hi = 1, cij = 0, sij = si, vij = vj, tj = 0, a NE can be computed in polynomial time [Bil`o et al., 2019; Fotakis et al., 2002]. In addition, when hi = 1, cij = 0, vij = v, tj = 0, the better response dynamics always converges to a NE [Bil`o et al., 2019].

4 Algorithms for Computing NE in EACPP

In Section 3, we have shown that determining the existence of a NE is NP-complete in instances I = (D, P, {cij}, {sij}, {vij}, {hi}, {tj}) where each i ∈ D can only select one project (i.e., hi = 1), has zero-cost for all projects (i.e., cij = 0 for all j), and has skill independent of the projects (i.e., sij = si for all j). In this section, we investigate EACPP where we can compute NE efficiently.

4.1 A Polynomial-Time Algorithm

The hardness results suggest that in order to derive an efficient algorithm for computing a NE, one must place further restrictions on the value vij and tj in addition to the parameter settings in the hardness proofs. Our following result shows that if each project can be successfully completed by any player working alone using a single effort allocation and vij are restricted (i.e., vij = vi or vij = vj), then a NE always exists and can be computed via ordered sequential response (Algorithm 1). Algorithm 1 starts by ordering the contributors subject to some parameter, and lets each contributor, under the same ordering, sequentially select a best response. After all contributors have selected actions, it returns a NE.

Theorem 3. Let I = (D, P, {cij}, {sij}, {vij}, {hi}, {tj}) be an EACPP instance where (1) hi = 1, (2) cij = 0, and (3) sij = si such that s1 ≥ ... ≥ sn for all i, j. Algorithm 1 returns a NE for the following settings in polynomial time:

1 Omitted proofs can be found in the supplementary material at: https://digitalcommons.unl.edu/cseconfwork/332/

Algorithm 1: Ordered Sequential Response

Input: I = (D, P, {cij}, {sij}, {vij}, {hi}, {tj}) Output: A NE profile a ∈ A 1 Let a = 0 # Set a to be a set of zero vectors. 2 Order contributors via parameter: D = {1, ..., n} 3 for i = 1, ..., n do 4 Let BRi(a-i) = argmaxa′i∈Ai ui(a′i , a-i) 5 Select ¯ai ∈ BRi(a-i), set ai = ¯ai 6 #Note: if vij = 0; ∀j ∈ P, select ¯ai with a project with the lowest total contribution 7 end

with contributor's ordering induced by skills s1 ≥ ... ≥ sn.

Proof. We first consider the setting of (a) where vij = vj, s1 ≥ s2... ≥ sn, and tj ≤ sn for all i, j. Let i be the ith contributor in the algorithm. For simplicity, we let a(0) = 0, ..., a(n) be the action profile of Algorithm 1 after each iteration. We now show that, via induction, after (line 5) setting ai = ¯ai such that aij = 1 and aik = 0, ∀k ̸= j, ¯ai ∈ BRi(a-i), no other contributor i′ = 1, ..., i - 1 would deviate. The basic case is straightforward when i = 1. Now we assume it is true up until i - 1. There are two possible cases we need to consider. If ai′ j ̸= aij, we have that

where ai′ k = 1, k ̸= j, and w ̸= k. The inequality continues to hold for a(i) as the only difference is on the j project (with the addition of i) and TCj(a(i) ) is nondecreasing.

for any w ̸= j and i′ . Thus, for any i′ , we can show that i′ has no incentive to deviate from j by dividing si > 0 and multiplying si′ > 0 from the above inequality. We can use a similar argument as above for part (b).

In the above setting, we consider cases where tj ≤ sn for each project j. The threshold effectively does not exist because every player can overcome it. A natural question is whether we can identify instances where tj > sn for which we can compute NE efficiently. We can answer this question affirmatively if the contributors have the same skill level (i.e., sij = s) and the vij are restricted (i.e., vij = vi or vij = vj).

Theorem 4. Let I = (D, P, {cij}, {sij}, {vij}, {hi}, {tj}) be an EACPP instance where (1) hi = 1, (2) cij = 0, and (3) sij = s for all i, j. One can compute a NE for the following settings in polynomial time:

(b) vij = vi for all i, j.

Proof (Sketch). Assume w.l.o.g. t1 ≤ ... ≤ tm. If every project requires at least two contributors (i.e, tj > s for each j), then setting the action of each contributor to a project (say j) is a NE as no contributor can unilaterally deviate to obtain a better utility. As such, we assume that there is a project, say k from the threshold ordering, that can be achieved by a single contributor (this can be verified in polynomial time). It follows that each project 1, ..., k can be achieved by a single contributor. Applying Algorithm 1 to current settings for setting (a) or (b), we obtain a NE by ordering the contributors arbitrarily, which can be proved using Theorem 3.

4.2 A Pseudo-Polynomial Algorithm

In general, we can use a standard enumeration approach to determine the existence of a NE, which would result in a running time of O(nmn+1 ) that is exponential in the number of contributors. It turns out that we can derive an improved enumeration algorithm with a polynomial runningtime in the number of contributors and a natural model parameter r := maxj∈P (1 + ∑i∈D sij), when the number of projects is bounded (and recall that sij is an integer). The assumption that m is bounded is natural, because in reality the planner often faces a small number of projects but a large number of contributors. We now give the pseudo-polynomial time algorithm when hi = 1 and m is a constant.

Theorem 5. When hi = 1 and the number of projects m is a constant, there exists a pseudo-polynomial algorithm that returns all NE in O(rm(nmrm + nm2 )).

Proof. We say vector q = (q1, ..., qm) is a potential-sum configuration, if qj ∈ {0, 1, . . . , r - 1} for any j ∈ P . Let Q be the set of all of such configurations. Clearly, |Q| = rm. The entry of a configuration corresponds to the total contribution on a project (i.e., qj = c means that project j receives a total contribution of c.). Note that for every a ∈ A there exists a q ∈ Q such that TCj(a) = qj . Therefore by checking every q ∈ Q for the existence of a NE, every possible strategy profile is checked. 2 We note that, to check if a solution is a NE, it suffices to rely on the information of the corresponding configuration. Our algorithm consists of the following two steps: for every configuration q = (q1, ..., qm) ∈ Q,

Step 1: Compute the set of best-response strategies/projects bi ⊆ P for the given q and each contributor i ∈ D. More specifically, we define and compute

Let b = (b1, . . . , bn) be the profile of best-response projects. Step 2: Given the profile b, we check if b can induce the potential-sum configuration q, that is, there exist an action profile a, such that for any i ∈ D, j ∈ P, (1) aij = 1 if and only if j ∈ bi, and (2) TCj(a) = qj.

The correctness is clear: if the answer in Step 2 is "yes", then configuration q gives a NE; if the answer is "no" for all q ∈ Q, then there is no NE. Next, we analyze the time complexity. For each of the rm = |Q| configurations, the time for Step 1 is at most O(nm2 ) as we need to compare each project with m - 1 other projects for each contributor.

2 The mapping of a to q is neither one-to-one nor onto.

Step 2 can be done efficiently using dynamic programming where (1) one can first order the contributor 1, ..., n and (2) create a binary table Ti(q) ∈ {0, 1} for each q ∈ Q of size rm for each contributor i. Defining T0(0) = 1 (with entry of zero otherwise), Ti(q) = 1 if only if there exists Ti-1(¯q) = 1 such that q = ¯q + ek ∗ sik for some project k ∈ bi where ek is a binary vector of size m of all zero except the kth entry. Table Ti can simply be constructed by looking at all the 1's ¯q entries of Ti-1 and add sik to each entry for each k ∈ bi. Because there are at most rm configurations, and each of the n contributors have at most m choices/projects for contributing to the configurations, the time for this step is at most O(nmrm). To verify whether a given q can be achieved, one can check if Tn(q) = 1 and the corresponding NE can be constructed via a standard backtracking procedure in dynamic programming. 3 The total time to check a given potential-sum q is O(nmrm + nm2 ). Yielding O(rm(nmrm + nm2 )) to check all q ∈ Q, which is polynomial in n and r, when m is a constant for each configuration.

5 Inefficiency of Nash Equilibria in EACPP

In this section, we consider the inefficiency, measured with respect to the planner's objective, induced by the strategic behavior of contributors. To measure such an inefficiency, we invoke the notion of the price of anarchy (PoA) [Koutsoupias and Papadimitriou, 1999] which is the ratio between the optimal "centralized" efficiency and the worst-case NE's efficiency. Also, we consider the price of stability (PoS) [Anshelevich et al., 2008], which is the ratio between the optimal efficiency and the best NE's efficiency.

The following result shows that computing optimal solutions is NP-hard for either maximizing the social welfare, or maximizing the successful projects.

Theorem 6. It is NP-hard to find an optimal solution that maximizes social welfare, or to find an optimal solution that maximizes the number of successful projects, even if hi = 1, cij = 0, vij = v.

Proof (Sketch). For the social welfare objective, we can reduce from the PP problem where we are given a set of n integers and a target T. The constructed EACPP instance consists of two projects with threshold T, where each of the n contributors can only select one project with value of T , and has skill si (corresponding to the integer) and zero cost for each project. One can obtain a social welfare no less than 2T if and only if there is a solution to the PP problem.

For the project successful objective, we can reduce from the 3-Partition Problem (3PP), which given a set of 3n positive integers, seeks a partition into n subsets of size 3 such that their sums are equal. It is easy to show that there is a solution to the 3-PP instance if and only if there is a solution of a constructed EACPP instance where all projects succeed.

3 If multiple NE correspond to the same q, then there is one path from Tn(q) to T0(0) for each NE.

In contrast, we remark that, for a more constrained setting where hi = 1, cij = 0, vij = vj, tj = 0, maximizing social welfare can be done in polynomial time [Bil`o et al., 2019].

Next, we consider PoA and PoS which is defined to be P oAsw = max a∈NE SW (aoptsw ) SW(a) , PoSsw = min a∈NE SW (aoptsw ) SW(a) , and similarly for PoAps and PoSps , where NE ⊆ A is the set of all NEs. Clearly, PoS ≤ PoA. Notice that we focus only on the instances in which NE exists. 4 The following results show that the PoS can be unbounded for either objective.

Theorem 7. PoSps is unbounded, even if hi = 1 and sij = s. PoSsw is also unbounded, even if hi = 1, sij = s, cij = 0.

Proof. We first consider PoSps . Consider the instance I = (D, P, {sij}, {cij}, {vij}, {tj}) where |D| = 2, |P| = 2, sij = 1, vi1 = 0, ci1 = 0, ci2 = 1 for i ∈ D, j ∈ P. The values for project 2 are v12 = 0, v22 = 3. The thresholds are t1 = 3, t2 = 2. Note that project 1 can never be completed and project 2 can only be completed when a12 = a22 = 1. Agent 1 will never choose project 2 because it has a cost c12 = 1 and a value v12 = 0, while the cost of project 1 is c11 = 0. Agent 2 will choose project 2 only if the threshold is reached. Therefore, the only NE is a11 = a21 = 1 where 0 projects are completed. However, the optimal solution is a12 = a22 = 1 where 1 project is completed.

Next, we consider PoSsw . Consider an instance I = (D, P, {sij}, {vij}, {tj}) where |D| = |P | = 2, t1 = 0, t2 = 2, hi = 1, sij = 1 and cij = 0 for any i ∈ D, j ∈ P. For contributor 1, v11 = 1, v12 = 0, and for contributor 2, v21 = 1, v22 = L, where L is a sufficiently large number. We show that, there is a NE with a11 = a21 = 1, which has a social welfare 2. Clearly contributor 1 has no incentive to deviate because it has positive value only for project 1. For contributor 2, the utility is 1, and if it deviates to project 2, then the utility decreases to 0. Moreover, noting that the only way for both contributors having positive utility is a11 = a21 = 1, this is the unique NE. However, the optimal solution is that both contributors select project 2 (i.e., a12 = a22 = 1), and the optimal social welfare is L. The ratio between the optimal social welfare and the social welfare in the NE is L2 , which tends to∞when L→∞. Thus, PoSsw is unbounded.

Despite the negative results above, we are able to identify instances in which the PoA is bounded for both objectives. For the social welfare objective, [Bil`o et al., 2019] proved that, when hi = 1, tj = 0, cij = 0, vij = v, it always has PoSsw = PoAsw = 1; and if the condition vij = v is relaxed to vij = vj, then it always has P oAsw (n, m) ≤ 1 + min{n,m}-1 n . Further, for the successful project objective, we have the following results.

Theorem 8. When hi = 1 and cij = 0 for all i ∈ D, j ∈ P , we have PoSps = n.

4 We note that PoAsw or PoSsw typically assume both of the quantities in the fraction to be non-negative. If both quantities are negative, then we can flip the fraction. If the numerator and denominator are positive and negative, respectively, then we say that the PoA is unbounded. When the denominator is zero, we say that the value is one if the numerator is zero, otherwise it is unbounded.

Proof. We first prove PoSps ≤ n. The optimal solution has at most min{m, n} successful projects. Note that we focus on instances in which NE exists. It suffices to prove the existence of a NE with at least one successful project.

If there is a project j ∈ P and contributor i satisfying sij ≥ tj and vij > 0, then every NE must have at least one successful project, otherwise contributor i can deviate to j and obtain a positive utility. So we only need to consider the case where that does not hold. We construct a NE a with at least one successful project as follows. Let j ∗ ∈ P be an arbitrary project that has potential to be successful. For any i ∈ D, set aij ∗ = 1, and set aij = 0 for all j ̸= j ∗ . Clearly, project j ∗ is successful. No contributor has incentive to deviate, because no project can be satisfied by a single contributor who has positive value to this project. Hence, action profile a is a NE with at least one successful project.

Now we prove PoSps ≥ n. Consider an instance I = (D, P, {sij}, {vij}, {tj}) where |D| = |P| = n, tj = 0, sij = 1 for i ∈ D, j ∈ P. For i ∈ D, set vij ∗ = 1 and vij = 0 for all project j ̸= j ∗ . Clearly, the optimal solution that maximizes the number of successful projects is that every project is contributed by a unique contributor, and the number of successful projects is n. However, the unique NE is that all contributors contribute to project j ∗ , where every one has a positive utility, and the number of successful projects is 1. Hence, the PoS is at least n.

6 Conclusion

In this paper, we consider a game-theoretic model of how contributors allocate effort (e.g., time) to contribute to a set of public projects where each project is successful if the total contribution meets or exceeds a predetermined project threshold. We study several computational and efficiency questions associated with pure-strategy Nash equilibria (NE). In particular, we show that the computational problems (i.e., existence of NE with/without required properties) are generally hard, and NE can be very inefficient (i.e., PoS). We note that the major obstacle for obtaining positive results is the existence of minimum threshold, which ensures that no project receiving a total contribution below the threshold can be completed. Compared with Project Games studied in [Bil`o et al., 2019], the threshold version studied in our paper becomes a bit intractable in the sense of both NP-hardness and PoA. However, we show that when we further restrict the model parameters, various computational and efficiency NE questions become tractable and positive, respectively.

Regarding the future directions, many variants of EACPP could be investigated. Non-binary project outcomes could be modeled, and most notably, additional contributions beyond the minimum threshold could increase the quality or probability of success for a project. Other variants, such as public reward in addition to contributors' reward, and individuals' different skills (e.g., programming, project management, marketing) for projects, are also possible. Such variations could be useful in a variety of applications, such as software engineering research [Stevens et al., 2021]. Finally, with some modifications this model would be interesting to study as a cooperative game [Bachrach and Rosenschein, 2008].