# Combinatorial Civic Crowdfunding with Budgeted Agents: Welfare Optimality at
Equilibrium and Optimal Deviation ††thanks: To appear in the Proceedings of
the Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI ’23). A
preliminary version of this paper titled “Welfare Optimal Combinatorial Civic
Crowdfunding with Budgeted Agents” also appeared at GAIW@AAMAS ’22.

Sankarshan Damle, Manisha Padala, Sujit Gujar
Machine Learning Lab
International Institute of Information Technology (IIIT), Hyderabad
{sankarshan.damle<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Civic Crowdfunding (CC) uses the “power of the crowd” to garner contributions
towards public projects. As these projects are non-excludable, agents may
prefer to “free-ride,” resulting in the project not being funded. For single
project CC, researchers propose to provide refunds to incentivize agents to
contribute, thereby guaranteeing the project’s funding. These funding
guarantees are applicable only when agents have an unlimited budget. This work
focuses on a combinatorial setting, where multiple projects are available for
CC and agents have a limited budget. We study certain specific conditions
where funding can be guaranteed. Further, funding the optimal social welfare
subset of projects is desirable when every available project cannot be funded
due to budget restrictions. We prove the impossibility of achieving optimal
welfare at equilibrium for any monotone refund scheme. We then study different
heuristics that the agents can use to contribute to the projects in practice.
Through simulations, we demonstrate the heuristics’ performance as the
average-case trade-off between welfare obtained and agent utility.

_K_ eywords Civic Crowdfunding $\cdot$ Nash Equilibrium $\cdot$ Social Welfare

##  1 Introduction

Local communities often find it beneficial to elicit contributions from their
members for _public_ good projects. E.g., the construction of markets,
playgrounds, and libraries, among others [1]. These goods provide the local
community with social amenities, generating social welfare. This process of
generating funds from members towards community services is referred to as
_Civic Crowdfunding_ (CC). CC is instrumental in changing the interaction
between local governments and communities. It empowers citizens by allowing
participation in the design and planning of public good projects [2]. Such
democratization of public projects has led CC to become an active area of
research [3, 4, 5, 6, 7, 8]. Moreover, introduction of web-based CC platforms
[9, 10] has added to its popularity.

As depicted in Figure 1, typically, multiple projects are simultaneously
available for CC. We refer to CC for multiple projects as _combinatorial_ CC.
Formally, CC comprises strategic agents who observe their valuations for the
available public projects. Each project has a known target cost and deadline.
Each agent contributes to the available projects as per its valuations and
within its _budget_. The agent valuations are such that the overall sum is
greater than the project’s target cost, i.e., there is enough valuation
(interest) for the project’s funding. A project is _funded_ when the agents’
total contribution meets the target cost within the deadline. When funded,
each agent obtains a quasi-linear utility equivalent to its valuation for the
project minus its contribution. In turn, the community generates social
welfare – the difference in the project’s total valuation and cost.

##### Free-riding.

The primary challenge in CC is due to the non-excludability of the public
projects. That is, the citizens can avail a project’s benefit without
contributing to its funding. Consequently, strategic agents may free-ride and
merely wait for others to fund the project. When the majority decides to free-
ride, the project remains unfunded despite sufficient interest in its funding
[11]. To persuade strategic agents to contribute, researchers propose to
provide additional incentives to them in the form of _refunds_.

Figure 1: Example instance of Combinatorial Civic Crowdfunding (CC) [10].

##### Refunds.

Zubrickas [12] presents PPR, Provision Point Mechanism with Refunds, which
employs the first such refund scheme. PPR assumes that a _central planner_
keeps some refund budget aside. If the project is not funded, the planner
returns the agent’s contribution and an additional refund proportional to the
agent’s contribution. The refund scheme incentivizes the agents to increase
their contribution to obtain a greater refund. The characteristic of the
resulting game is that the public project is funded at equilibrium. However,
PPR and subsequent works ([13] and references cited therein) assume that
agents have an unlimited individual budget; in reality, the agents may have a
limited budget. To this end, we aim to determine the funding guarantees for a
subset of public projects that maximize social welfare within the available
budget.

### Our Approach and Contributions

This paper lays the theoretical foundation for combinatorial CC with budgeted
agents. Table 1 presents the overview of our results, described in detail
next.

Budget Surplus (BS). We first study the seemingly straightforward case of
_Budget Surplus_ , i.e., the overall budget across the agents is more than the
projects’ total cost. For this, it is welfare optimal to fund all the
projects. Despite the surplus budget, we show that the projects’ funding
cannot be guaranteed at equilibrium (Theorem 2 and Corollary 1).

Subset Feasibility (SF). We observe that the budget distribution among the
agents plays a significant role in deciding the funding status of the
projects. Conditioning on the budget distribution, we introduce _Subset
Feasibility_ of a given subset of projects. We prove that Subset Feasibility
coupled with Budget Surplus guarantees funding of every available project at
equilibrium (Theorem 3), thereby generating the maximum possible social
welfare.

Budget Deficit (BD). Trivially, in the case of _Budget Deficit_ – when there
is no Budget Surplus – one can only fund a subset of projects. It may be
desirable that such a subset is welfare-maximizing within the budget. We refer
to the funding of the socially welfare optimal subset at equilibrium as
_socially efficient equilibrium_. For this case, we present the following
results.

First, we show that, in general, achieving socially efficient equilibrium is
impossible for any refund scheme (Example 1). Next, we prove that even with
the stronger assumption of Subset Feasibility, it is still impossible to
achieve socially efficient equilibrium (Theorem 4). Specifically, we prove
that strategic deviations may exist for agents such that the optimal welfare
subset remains unfunded. We then show that it is NP-Hard for an agent to find
its optimal deviation, given the contributions of all the other agents
(Theorem 6 and Corollary 2). Due to Theorem 4 and hardness of optimal
deviation (Theorem 6), we construct five heuristics for the agent’s
contributions and empirically study their social welfare and agent utility
through simulations (Section 6).

Property Socially Efficient Equilibrium Budget Surplus ✗ (Corollary 1) Budget
Surplus + Subset Feasibility ✓ (Theorem 3) Budget Deficit + Subset Feasibility
✗ (Theorem 4)

Table 1: Overview of our theoretical results.

##  2 Related Work

Several works study the effect of agents’ contribution to public projects [6,
14, 15, 16]. One way of modelling agent contribution is using _Cost Sharing
Mechanisms_ (CSMs) in CC [17]. More concretely, CSMs focus on sharing the cost
among the strategic agents to ensure that an efficient set of projects are
funded [17, 18, 19, 20, 21]. The authors in [6, 22] model CSMs for non-
excludable public projects and provide agent contributions that ensure
specific desirable properties, e.g., individual rationality and strategy-
proofness. However, these works do not guarantee funding at equilibrium since
agents are strategic and CSMs do not offer refunds.

In another line of work, funding of public projects is modeled as
_Participatory Budgeting_ (PB) [23]. Brandl et al. [16] study a model without
targets costs and without quasi-linear utilities, applicable for making
donations to long-term projects. Generally, in the PB literature, the utility
of an agent is determined by the number of projects funded or the costs of the
projects (e.g., [24, 25]), whereas in CC, it is the difference between the
agent’s valuation and contribution. Aziz et al. [26] consider a PB model with
budget constraints and quasi-linear utilities when the project is funded. The
authors prove the impossibility of finding an approximation to welfare optimal
funded subset of projects which also ensure weak participation, i.e., positive
utility to all agents. However, they do not assume strategic agents.

For excludable public projects, Soundy et al. [15] focus on effort allocation
by strategic agents towards the project’s completion. Contrarily, we focus on
funding guarantees of non-excludable public projects with strategic agents.

##### CC with Refunds.

In the seminal work, Bagnoli and Lipman [27] present Provision Point Mechanism
(PPM) for single project CC, without refunds. Consequently, PPM consists of
several inefficient equilibria [27, 28]. Agents may also free-ride since the
projects are non-excludable [11]. To overcome such limitations, Zubrickas [12]
presents PPR, a novel mechanism that offers refunds proportional to
contributions. Based on the attractive properties of PPR, other works propose
different refund schemes for different agent models and strategy space [13,
29, 30, 31]. However, these works only focus on a single project with agents
having unlimited budgets.

Among recent works, Padala et al. [32] attempt to learn equilibrium
contributions when agents have a limited budget in combinatorial CC using
Reinforcement Learning. However, the work does not provide any funding
guarantees – welfare or otherwise – for the projects.

Chen et al. [14] analyze the existence of cooperative Nash Equilibrium for
funding a single public project using ‘external investments.’ Their work
considers agents to have binary contributions, unlike our setting, where agent
contributions are in $\mathbb{R}_{+}$. Moreover, in their utility structure,
agents receive a fixed fraction of the total contribution when the project is
funded; otherwise, their contribution is returned. That is, they do not model
agent valuations.

We remark that while our work is motivated by the existing CC literature, it
remains fundamentally different. To the best of our knowledge, we are the
first to study the funding guarantees for combinatorial CC with budgeted
agents. We also focus on an agent’s equilibrium behavior and study the
hardness of the optimal strategy for the agents.

##  3 Preliminaries

This section presents our CC model and important definitions. We also
summarize PPR for the single project case.

###  3.1 Combinatorial CC Model

Let $P=\\{1,\ldots,p\\}$ be the set of projects to be crowdfunded with target
costs $T=\\{T_{1},\ldots,T_{p}\\}$. Let $N=\\{1,\ldots,n\\}$ denote the set of
agents interested in contributing to all projects. We consider a limited
budget for each agent $\gamma=(\gamma_{1},\ldots,\gamma_{n})$. Each agent $i$
has a private valuation for the project $j$, denoted by $\theta_{ij}\geq 0$.
We consider additive valuations, i.e., an agent $i$ has a value of $\sum_{j\in
M}\theta_{ij}$ for a funded subset $M\subseteq P$. Let
$\vartheta_{j}=\sum_{i\in N}\theta_{ij}$ denote the total valuation in the
system for the project $j$. An agent $i$ contributes $x_{ij}\in\mathbb{R}_{+}$
to project $j$, s.t., $\sum_{j\in P}x_{ij}\leq\gamma_{i}$. The total
contribution towards a project $j$ is denoted by $C_{j}=\sum_{i\in N}x_{ij}$.
The project is funded if $C_{j}\geq T_{j}$ by the deadline, and each agent
gets the funded utility of $\theta_{ij}-x_{ij}$. If the project is unfunded
$(C_{j}<T_{j})$, the agents are returned their contributions $x_{ij}$ and in
some mechanisms, additional refunds, as defined later.

##### Welfare Optimal.

Ideally, when there is limited budget, it may be desirable to fund welfare
optimal subset defined as follows. Note that, the welfare obtained from
project $j$ if funded is $\vartheta_{j}-T_{j}$ and zero otherwise [33,
34]111All the results presented in this paper also hold if
$P^{\star}\in\underset{M\subseteq P}{\mbox{arg max}}\sum_{j\in
M}\vartheta_{j}~{}\mbox{s.t.}~{}\sum_{j\in M}T_{j}\leq\sum_{i\in
N}\gamma_{i}.$ .

######  Definition 1 (Welfare Optimal).

A set of projects $P^{\star}\subseteq P$ is welfare optimal if it maximizes
social welfare under the available budget, i.e.,

$P^{\star}\in\underset{M\subseteq P}{\mbox{arg max}}\sum_{j\in
M}\left(\vartheta_{j}-T_{j}\right)~{}\mbox{s.t.}~{}\sum_{j\in
M}T_{j}\leq\sum_{i\in N}\gamma_{i}.$ (1)

We make the following observations based on Definition 1.

  * •

Finding $P^{\star}$ requires public knowledge of $\vartheta$s, $T$s and the
value $\sum_{i\in N}\gamma_{i}$. Contrary to the PB or CSM literature, the
aggregate valuation $\vartheta$ is assumed to be public knowledge in the CC
literature [12, 29]. Similarly, we also assume that the overall budget in the
system $\sum_{i\in N}\gamma_{i}$ is public knowledge. This may be done by
deriving the overall budget by aggregating citizen interest [35, 36].

  * •

Computing $P^{\star}$ is NP-Hard as it can be trivially reduced from the
KNAPSACK problem. However, note that our primary results focus on
$P^{\star}$’s funding guarantees at equilibrium (and not actually computing
it). Moreover, computing $P^{\star}$ may also not be a deal breaker as the
number of simultaneous projects available will not be arbitrarily large. One
may also employ FPTAS [37].

##### Refund Scheme.

We define the refund scheme for each project $j\in P$ as
$R_{j}(B_{j},x_{ij},C_{j}):\mathbb{R}_{+}^{3}\rightarrow\mathbb{R}_{+}$ s.t.
$r_{ij}=R_{j}(B_{j},x_{ij},C_{j})$ is agent $i$’s refund share for
contributing $x_{ij}$ to project $j$. The overall budget for the refund bonus
$B_{j}>0$ is public knowledge. Typically, if a project is unfunded, the agents
receive $r_{ij}$, and zero refund otherwise. The total refunds distributed for
project $j$ can be such that $\sum_{i\in N}r_{ij}=B_{j}$ (e.g., [12]) or
$\sum_{i\in N}r_{ij}<B_{j}$ (e.g., [29, 13]). Throughout the paper, we assume
that $\sum_{i\in N}r_{ij}=B_{j}~{}\forall j$.

The CC literature also assumes that $R$ is anonymous, i.e., refund share is
independent of agent identity. Further, consider the following condition for a
refund scheme, assuming $R$ is differentiable w.r.t. $x$.

######  Condition 1 (Contribution Monotonicity (CM) [13]).

A refund scheme $R(x;\cdot)$ satisfies Contribution Monotonicity (CM) if it is
strictly monotonically increasing with respect to the contribution $x$, i.e.,
$\frac{\partial R(x;\cdot)}{\partial x}>0.$

###  3.2 Agent Utilities and Important Definitions

Let $\mathcal{M}_{CC}=\left\langle P,N,\gamma,T,(\vartheta_{j})_{j\in
P},(R_{j})_{j\in P},(B_{j})_{j\in P}\right\rangle$ define a general
combinatorial CC game. In this, the overall agent utility can be defined as.

######  Definition 2 (Agent Utility).

Given an instance of $\mathcal{M}_{CC}$, with agents having valuations
$[\theta_{ij}]$ and contributions $[x_{ij}]$, the utility of an agent $i$ for
each project $j\in P$ is given by
$\sigma_{ij}(\theta_{ij},x_{ij},r_{ij},C_{j},T_{j}):\mathbb{R}_{+}^{5}\rightarrow\mathbb{R}$

$\sigma_{ij}(\cdot)=\mathbbm{1}_{C_{j}\geq
T_{j}}\cdot\underbrace{(\theta_{ij}-x_{ij})}_{\text{Funded utility
$\sigma_{ij}^{F}$}}+~{}\mathbbm{1}_{C_{j}<T_{j}}\cdot\underbrace{r_{ij}}_{\text{Unfunded
utility $\sigma_{ij}^{U}$}}$

where $\mathbbm{1}_{X}$ is an indicator variable, such that
$\mathbbm{1}_{X}=1$ if $X$ is true and zero otherwise.

An agent $i$’s utility for project $j$ is either
$\sigma_{ij}^{F}=\theta_{ij}-x_{ij}$ when $j$ is funded, and
$\sigma_{ij}^{U}=r_{ij}$ otherwise. Let $U_{i}(\cdot)$ denote the total
utility an agent $i$ derives, i.e., $U_{i}(\cdot)=\sum_{j\in P}\sigma_{ij}$.
This incentive structure induces a game among the agents. As the agents are
strategic, each agent aims to provide contributions that maximizes its
utility. As such, we focus on contributions which follow pure strategy Nash
equilibrium.

######  Definition 3 (Pure Strategy Nash Equilibrium (PSNE)).

A contribution profile $(x_{i1}^{*},\ldots,x_{ip}^{*})_{i\in N}$ is said to be
Pure Strategy Nash equilibrium (PSNE) if, $\forall i\in N$,

$\sum_{j\in P}\sigma_{ij}(x_{ij}^{*},x_{-ij}^{*};\cdot)\geq\sum_{j\in
P}\sigma_{ij}(x_{ij},x_{-ij}^{*};\cdot),\ \ \forall x_{ij}.$

where $x_{-ij}^{*}$ is the contribution of all agents except agent $i$.

Efficacy of PSNE Contributions. PSNE is the standard choice of solution
concept in CC literature [12, 13, 29, 30]. Zubrickas [12] shows that for an
appropriate refund bonus (see Eq. 3), their PSNE strategies are the unique
equilibrium of the mechanism. Moreover, Cason and Zubrickas [38] empirically
validate the effectiveness of these PSNE strategies using real-world
experiments.

Given the contributions $[x_{ij}^{*}]$, we can compute the set of the projects
that are funded and unfunded at equilibrium. Throughout the paper, we refer to
the funding of $P^{\star}$ at equilibrium as _socially efficient equilibrium_.
We next define budget surplus.

######  Definition 4 (Budget Surplus (BS)).

There is enough overall budget to fund each project $j\in P$, i.e.,
$\sum_{i\in N}\gamma_{i}\geq\sum_{j\in P}T_{j}$.

We refer to the scenario $\sum_{i\in N}\gamma_{i}<\sum_{j\in P}T_{j}$ as
Budget Deficit (BD). In CC literature, it is also natural to assume that
$\vartheta_{j}>T_{j},\forall j\in P$ [12]. That is, there is sufficient
interest in each available project’s funding. Hence, when there is surplus
budget, it is optimal to fund all the projects, i.e., $P^{\star}=P$.

Further, we assume that agents do not have any additional information about
the funding of the public projects. This assumption implies that their belief
towards the projects’ funding is symmetric. This is a standard assumption in
CC literature [12, 13].

Figure 2: Utility vs. Contribution for agent $i$ for project $j$.

###  3.3 Single Project Civic Crowdfunding

##### Provision Point Mechanism with Refunds (PPR)

. For single project CC, i.e., $P=\\{1\\}$, Zubrickas [12] proposes PPR which
employs the following refund scheme $\forall i\in N$,

$r^{PPR}_{i1}={R}^{PPR}(x_{i1},B_{1},C_{1})=\left(\frac{x_{i1}}{C_{1}}\right)B_{1}.$
(2)

Each agent $i$’s equilibrium contributions are defined such that its funded
utility is greater than or equal to its unfunded utility, i.e.,
$\theta_{i1}-x_{i1}^{*}\geq r^{PPR}_{i1}$. We depict such a situation with
Figure 2. The author shows that the project is funded at equilibrium222In
other words, the introduction of refunds results in the funding of the public
project being the unique Nash equilibrium of the game when
$\vartheta_{1}>T_{1}$. That is, “bad” Nash equilibria where the project is not
funded are filtered out. when $\vartheta_{1}>T_{1}$, and that it is PSNE for
each agent $i$ to contribute $x_{i1}^{*}$ or the amount left to fund the
project, whichever is minimum. More formally,

######  Theorem 1 ([12]).

In PPR, with $\vartheta_{1}>T_{1}$ and $B_{1}>0$, the set of PSNEs are
$\\{x_{i1}^{*}~{}|~{}x_{i1}^{*}\leq\bar{x}_{i1},~{}\forall i;C_{1}=T_{1}\\}$
if $B_{1}\leq\vartheta_{1}-T_{1}$, where
$\bar{x}_{i1}=\frac{T_{1}}{B_{1}+T_{1}}\theta_{i1}$. Otherwise, the set is
empty.

We have $\bar{x}_{i1}=\frac{T_{1}}{B_{1}+T_{1}}\theta_{i1}$ as the upper-bound
of the equilibrium contribution, $\forall i\in N$. In PPR, the PSNE strategies
in Theorem 1 are the unique equilibrium of the game when,

$B_{1}=\vartheta_{1}-T_{1}\implies\sum_{i\in N}\bar{x}_{i1}=T_{1}.$ (3)

##### Funding Guarantees.

For single project CC, Damle et al. [13] show that the project is funded at
equilibrium for any refund scheme that satisfies Condition 1. Trivially, one
may observe that the refund scheme in PPR, i.e.,
${r}^{PPR}_{i1}=\left(\frac{x_{i1}}{C_{1}}\right)B_{1}$, $\forall i$, also
satisfies Condition 1. Damle et al. [13] propose other refund schemes which
satisfy Condition 1 and are exponential or polynomial in $x$. We remark that
our results hold for any refund scheme satisfying Condition 1.

##  4 Funding Guarantees for Combinatorial CC under Budget Surplus

For CC under Budget Surplus (Def. 4) sufficient overall budget exists to fund
all the projects. Theorem 2 shows that despite the sufficient budget, projects
may not get funded as the set of equilibrium contributions for an agent may
not exist. Unlike Theorem 1, agents may not have well-defined contributions
satisfying PSNE. The non-existence results due to the uneven distribution of
budget among the agents. Hence, agents with higher budgets exploit the
mechanism to obtain higher refunds while ensuring the projects remain
unfunded.

######  Theorem 2.

Given $(R_{j})_{j\in P}$ which satisfy Condition 1, there are Budget Surplus
(Def. 4) game instances of $\mathcal{M}_{CC}$ with
$B_{j}=\vartheta_{j}-T_{j},\forall j$ such that there is no equilibrium. That
is, the set of equilibrium contributions may be empty.

###### Proof.

Consider $P$ projects and $N$ agents s.t. Def. 4 is satisfied, i.e.,
$\sum_{i\in N}\gamma_{i}\geq\sum_{j\in P}T_{j}$. We can easily construct game
instances where there exists non-empty $N_{1}\subset N$ s.t. $\sum_{i\in
N_{1}}\gamma_{i}<\min_{j}T_{j}$. To satisfy Budget Surplus (Def. 4),
$N_{2}=N\setminus N_{1}$ must have enough budget so that the agents in
$N_{1}+N_{2}$ can fund all the projects.

Each agent $i$ receives a funded utility $\sigma_{ij}^{F}=\theta_{ij}-x_{ij}$
for contributing $x_{ij}$ towards project $j$. That is, as
$x_{ij}\uparrow\implies\sigma_{ij}^{F}\downarrow$. The agent may also receive
an unfunded utility of $\sigma_{ij}^{U}=r_{ij}=R_{j}(x_{ij},B_{j},\cdot)$ for
project $j$. Since $R_{j}$ is monotonically increasing (Condition 1),
$x_{ij}\uparrow\implies\sigma_{ij}^{U}\uparrow$. We depict this scenario with
Figure 2. Observe that $\sigma_{ij}^{U}$ and $\sigma_{ij}^{F}$ intersect at
the upper-bound of the equilibrium contribution, $\bar{x}_{ij}$ (Theorem 1),
where $\sigma_{ij}^{F}=\sigma_{ij}^{U}$. For any $x_{ij}>\bar{x}_{ij}$,
$\sigma_{ij}^{U}>\sigma_{ij}^{F}$. The rest of the proof (see Appendix A.1)
shows that $~{}\exists i\in N_{2}$ s.t. $\hat{x}_{ij}>\bar{x}_{ij}$ which in
turn is not possible at equilibrium due to discontinuous utility structure at
$\bar{x}_{ij}$. ∎

Observe that if any project $j$ is funded at equilibrium then the equilibrium
set $(x_{i1}^{*},\ldots,x_{ip}^{*})_{i\in N}$ can not be empty, contradicting
Theorem 2. Corollary 1 captures this observation.

######  Corollary 1.

Given $(R_{j})_{j\in P}$ satisfying CM (Condition 1), there are game instances
of $\mathcal{M}_{CC}$ s.t. even with Budget Surplus (Def. 4), no project in
$P$ may be funded at equilibrium.

With Corollary 1, we prove that Budget Surplus is not sufficient to fund every
project at equilibrium. To this end, we next identify the sufficient condition
to ensure the funding of every project, under Budget Surplus.

### Subset Feasibility

With $N_{1}$ and $N_{2}$ in Theorem 2’s proof, we assume a specific
distribution on agents’ budget. To resolve this, we introduce _Subset
Feasibility_ which assumes a restriction on each agent’s budget distribution.
Informally, if each agent $i$ has enough budget to contribute $\bar{x}_{ij}$
(see Figure 2) for $j\in M$, $M\subseteq P$, then Subset Feasibility is
satisfied for $M$. Formally,

######  Definition 5 (Subset Feasibility for $M$ (SFM)).

Given an instance of $\mathcal{M}_{CC}$ with $(R_{j})_{j\in P}$ satisfying
Condition 1, SFM, $M\subseteq P$, is satisfied if, $\forall i\in N$ we have
$\gamma_{i}\geq\sum_{j\in M}\bar{x}_{ij}$. Here,
$\theta_{ij}-\bar{x}_{ij}=R_{j}(\bar{x}_{ij},B_{j},\cdot)$ (refer Figure 2).

######  Claim 1.

Given any $(R_{j})_{j\in P}$ whose equilibrium contributions satisfy
$\sum_{i}\bar{x}_{ij}\geq T_{j}$, we have SFP $\implies$ BS.

Claim 1 follows from trivial manipulation (see Appendix A.2). Similarly, we
have BS $\centernot\implies$ SFP. From Claim 1, it is welfare optimal to fund
every available project under $SF_{P}$. Theorem 3 indeed proves that under SFP
each project $j\in P$ gets funded at equilibrium, thereby generating optimal
social welfare. The formal proof is available in Appendix A.3.

######  Theorem 3.

Given $\mathcal{M}_{CC}$ and $(R_{j})_{j\in P}$ satisfying CM (Condition 1)
such that $SF_{P}$ is satisfied, at equilibrium all the projects are funded,
i.e., $C_{j}=T_{j},~{}\forall j\in P$ if
$B_{j}\leq\vartheta_{j}-T_{j},~{}\forall j\in P$. Further, the set of PSNEs
are:
$\left\\{(x_{ij}^{*})_{j\in
P}~{}|~{}\sigma_{ij}^{F}(x_{ij}^{*};\cdot)\geq\sigma_{ij}^{U}(x_{ij}^{*};\cdot),\forall
j\in P,~{}\forall i\in N\right\\}$.

Theorem 3 implies that, under SFP, the socially efficient equilibrium (with
$P^{\star}=P$) is achieved. Intuitively, under SFP combinatorial CC collapses
to simultaneous single projects; and thus, we can provide closed-form
equilibrium contributions. However, SFP is a strong assumption and, in
general, may not be satisfied. In fact, the weaker notion of Budget Surplus
itself may not always apply. Therefore, we next study combinatorial CC with
Budget Deficit.

##  5 Impossibility of Achieving Socially Efficient Equilibrium for
Combinatorial CC under Budget Deficit

We now focus on the scenario when there is _Budget Deficit_ , i.e.,
$\sum_{i\in N}\gamma_{i}<\sum_{j\in P}T_{j}$. In this scenario, only a subset
of projects can be funded. Unfortunately, identifying the subset of projects
funded at equilibrium is challenging. In CC, the agents decide which projects
to contribute to based on their private valuations and available refund. This
circular dependence of the equilibrium contributions and the set of funded
projects make providing analytical guarantees challenging on the funded set.
To analyze agents’ equilibrium behavior and funding guarantees, we fix our
focus on the subset of projects that maximize social welfare, i.e.,
$P^{\star}$ (Def. 1).

In this section, we first show that funding $P^{\star}\subset P$ at
equilibrium is, in general, not possible for any $R(\cdot)$ satisfying
Condition 1. Second, we prove that even with the stronger assumption of Subset
Feasibility of the optimal welfare set, i.e., SF${}_{P^{\star}}$, we may not
achieve socially efficient equilibrium due to agents’ strategic deviations.
Last, we show that computing an agent $i^{\prime}$’s optimal deviation, given
the contributions of the other agents $N\setminus\\{i^{\prime}\\}$, is NP-
Hard.

###  5.1 Welfare Optimality at Equilibrium

Consider the following example instance.

######  Example 1.

Let $P=\\{1,2\\}$ and $N=\\{1,2\\}$. Let
$\gamma_{1}=1,\gamma_{2}=0,\theta_{11}=1,\theta_{12}=2\mbox{~{}and~{}}\theta_{22}=1$
with $\theta_{21}=10$.

In Example 1, the maximum funded utility agent 1 can receive from project 1 is
$0$ and unfunded utility $r_{11}<\theta_{11}=1$. On the other hand, the agent
obtains a utility of $1$ when contributing to project 2. Hence at equilibrium,
project 2 gets funded, although it is welfare optimal to fund project 1. Thus,
socially efficient equilibrium is not achieved.

nameProcedure

Algorithm 1 Instance with $P=N=\\{1,2\\}$ and fixed $R(\cdot)$

1:procedure GenerateValues($R(\cdot)$)

2: $T_{1}\leftarrow\mathbb{R}_{+}$

3: Choose $\theta_{11}$ s.t. $\bar{x}_{11}<T_{1}<\theta_{11}$ based on
$R_{1}(\cdot)$

4: Choose $\theta_{21}$ s.t. $\bar{x}_{21}:=T_{1}-\bar{x}_{11}$

5: Set $T_{2}=\bar{x}_{21}$, $\theta_{12}=0$ and choose $\theta_{22}$ s.t.

6: $\theta_{21}<\theta_{22}<\theta_{11}+\theta_{21}-x_{11}^{*}$
$\triangleright$ $P^{\star}=\\{1\\}$

7: Set $\gamma_{1}:=\bar{x}_{11}$ and $\gamma_{2}:=\bar{x}_{21}$
$\triangleright$ Satisfying SF${}_{P^{\star}}$

8: return $\theta$’s, $\gamma$’s, and $T$’s $\triangleright$ s.t. Agent 2
deviates

9:end procedure

Example 1 is one pathological case where the agent with high valuation has
zero budget, leading to sub-optimal outcome at equilibrium. Hence, we next
strengthen the assumption on the budgets of the agents. Let $P^{\star}$ be the
non-trivial welfare optimal subset and we assume that Subset Feasibility is
satisfied for $P^{\star}$, i.e., SF${}_{P^{\star}}$. Recall that with
SF${}_{P^{\star}}$, we assume that every agent has enough budget to contribute
$\bar{x}_{ij}$ in $P^{\star}$. Theorem 4 shows that despite this strong
assumption, achieving socially efficient equilibrium may not be possible.

######  Theorem 4.

Given an instance of $\mathcal{M}_{CC}$, a unique non-trivial
$P^{\star}\subset P$ may not be funded at equilibrium even with Subset
Feasibility for $P^{\star}$, SF${}_{P^{\star}}$, for any set of $(R_{j})_{j\in
P}$ satisfying Condition 1.

###### Proof.

We provide a proof by construction for $n=2$ and $p=2$ where one of the agents
has an incentive to deviate when $P^{\star}$ is funded. Procedure 1 presents
the steps to construct the instance. We first select the target cost of the
project $1$, i.e. $T_{1}\in\mathbb{R}_{+}$. Given $(R_{j})_{j\in P}$ under
Condition 1, we can always find an $\bar{x}_{11}$ for agent $1$. At
$\bar{x}_{11}$, funded utility is equal to unfunded utility (Figure 2).
Trivially, $\bar{x}_{11}<\theta_{11}$. The rest of the proof shows that the
construction defined in Procedure 1 is always possible for any refund scheme
satisfying Condition 1 (see Appendix A.4). ∎

###  5.2 CCC with Budget Deficit: Optimal Strategy

Theorem 4 implies that $P^{*}$ may not be funded at equilibrium even when
$P^{*}$ satisfies Subset Feasibility. In other words, w.l.o.g., an agent
$i^{\prime}$ may have an incentive to deviate from any strategy that funds
$P^{*}$. Motivated by such a deviation, we now address the question: _Given
the total contribution by $N\setminus\\{i^{\prime}\\}$ agents towards each
project $j$, can the agent $i^{\prime}$ compute its optimal strategy?_ We
answer this question by (i) showing that such an optimal strategy may not
exist if an agent’s contribution space is continuous, i.e.,
$x\in\mathbb{R}_{+}$, and (ii) if contributions are discretized, then
computing the optimal strategy is NP-Hard.

MIP-CC: Mixed Integer Program for CC. We first describe the general
optimization for an agent $i^{\prime}$ to compute its optimal strategy (i.e.,
contribution). Assume that the agents $\in N\setminus\\{i^{\prime}\\}$ have
contributed denoted by $C_{j-i^{\prime}}$. For agent $i^{\prime}$’s optimal
strategy, we need to maximize its utility given
$T_{j}-C_{j-i^{\prime}},~{}\forall j\in P$ and other variables such as the
refund scheme $R_{j}$ and bonus budget $B_{j}$. Figure 3 presents the formal
MIP, namely _MIP-CC_ , which follows directly from agent $i^{\prime}$ utility
(Def. 2).

$\displaystyle\max_{(x_{i^{\prime}j})_{j\in P}}\sum_{j\in
P}z_{i^{\prime}j}\cdot(\theta_{i^{\prime}j}-x_{i^{\prime}j})+(1-z_{i^{\prime}j})\cdot
R(x_{i^{\prime}j},\cdot)$ s.t. $\displaystyle\sum_{j\in
P}x_{i^{\prime}j}\leq\gamma_{i^{\prime}}$ // Budget Constraint $\displaystyle
x_{i^{\prime}j}\leq T_{j}-C_{j-i^{\prime}},\forall j$ // Remaining
Contribution
$\displaystyle\begin{rcases}(x_{i^{\prime}j}-T_{j}+C_{j-i^{\prime}})\cdot
z_{i^{\prime}j}\geq 0,\forall j\\\
x_{i^{\prime}j}-T_{j}+C_{j-i^{\prime}}<z_{i^{\prime}j},\forall j\\\
z_{i^{\prime}j}\in\\{0,1\\},\forall j\end{rcases}$ // Defining Indicator
Variable

Figure 3: MIP-CC: Mixed Integer Program to calculate Agent $i^{\prime}$’s
optimal strategy given the contributions of the remaining agents
$N\setminus\\{i^{\prime}\\}$.

##### MIP-CC: Optimal Strategy May Not Exist.

We now show that MIP-CC (Figure 3) may not always admit well-defined
contributions.

######  Example 2.

Let $P=\\{1,2,3\\}$ and $N=\\{1,2\\}$ s.t. both agents are _identical_ , i.e.,
each $i\in N$ has the same value $\theta$ for each $j\in P$ and
$\gamma_{1}=\gamma_{2}$. Additionally $~{}\forall j\in P$, $T_{j}=T$ and
$B_{j}=\vartheta-T,$. Let the agents have budget s.t.
$\gamma_{i}=\bar{x}_{i1}~{}\forall i\in N$, where $\bar{x}_{i1}$ is the upper
bound equilibrium contribution for the single project case (see Figure 2).

######  Theorem 5.

Given an instance of $\mathcal{M}_{CC}$ and for any set of $(R_{j})_{j\in P}$
satisfying Condition 1, an agent $i^{\prime}$’s optimal strategy may not
exist.

###### Proof.

We use proof by construction. In Appendix A.5, we show that for Example 2,
given agent 1’s contribution we can create an instance of $\mathcal{M}_{CC}$
s.t. the set of indicator variable $z$s in MIP-CC can be either
$z_{1}=\\{1,0,0\\}$ or $z_{2}=\\{0,0,0\\}$. Then, we show that agent 2’s
utility becomes $\theta-\gamma_{2}$ for $z_{1}$ with strategy
$(\gamma_{2},0,0)$ and $2B+R(\gamma_{2}-\epsilon)$ for $z_{2}$ with strategy
$(\gamma_{2}-\epsilon,\epsilon/2,\epsilon/2)$ where $\epsilon\leq 0$. As
$\epsilon\downarrow$, agent 2’s utility for $z_{2}$ increases. But for
$\epsilon=0$, only $z_{1}$ is possible and agent 2 receives the utility
$\theta-\gamma_{2}$ (strictly less than utility for $z_{2}$). Due to this
_discontinuity_ in the utilities, no optimal $\epsilon$ exists, i.e., optimal
strategy does not exist. ∎

MIP-CC-D. In order to overcome the above non-existence, we discretize the
contribution space. More concretely, an agent $i$ can contribute
$\kappa\cdot\delta$ where $\kappa\in\mathbb{N}^{+}$ and $\delta$ the smallest
unit of contribution. With this restriction on an agent’s contribution, the
search space in MIP-CC (Figure 3) becomes discrete and finite. Consequently,
agent $i^{\prime}$’s optimal strategy always exist. To distinguish MIP-CC with
a discrete contribution space, we refer to it as _MIP-CC-D_.

####  5.2.1 MIP-CC-D: Finding Optimal Strategy is NP-Hard.

We now show that solving MIP-CC for discrete contributions (i.e., MIP-CC-D) is
NP-hard.

######  Theorem 6.

Given an instance of $\mathcal{M}_{CC}$ with discrete contributions and for
any set of $(R_{j})_{j\in P}$ satisfying Condition 1, computing optimal
strategy for agent $i^{\prime}$, given the contributions of
$N\setminus\\{i^{\prime}\\}$, is NP-Hard.

###### Proof.

We divide the proof into two parts. In Part A, we design a MIP tuned for a
specific case of combinatorial CC comprising identical projects with a refund
scheme satisfying $\sum_{j}R(x_{j},\cdot)=R(\sum_{j}x_{j},\cdot)$. We prove
that the MIP is NP-Hard by reducing it from KNAPSACK. Then, in Part B, we show
that this MIP reduces to MIP-CC-D. That is, any solution to MIP-CC-D can be
used to determine a solution to MIP in polynomial time, implying that MIP-CC-D
is also NP-Hard. The formal proof is available in Appendix A.6. ∎

The following corollary follows from Theorem 6. We defer the proof to Appendix
A.7.

######  Corollary 2.

Given an instance of $\mathcal{M}_{CC}$ with discrete contributions and for
any set of $(R_{j})_{j\in P}$ satisfying Condition 1, if all agents except
$i^{\prime}$, $N\setminus\\{i^{\prime}\\}$, follow a specific strategy that
funds $P^{\star}\subset P$, then computing the optimal deviation for agent
$i^{\prime}$ is NP-Hard.

##  6 Experiments

Motivation. Theorem 4 proves that the optimal subset $P^{\star}$ may not be
funded at equilibrium due to agents’ strategic deviations. However, computing
an agent’s optimal deviation is also NP-Hard (Corollary 2). These observations
highlight that computing closed-form equilibrium strategies in Budget Deficit
Combinatorial CC, similar to Theorem 1 and Theorem 3, for agents is
challenging. Given this challenge and the hardness of strategic deviations,
agents may employ heuristics to increase utility [39, 40]. We next propose
five heuristics for agents to employ in practice and study their impact on
agent utilities and the welfare generated.

###  6.1 Heuristics and Performance Measures

##### Heuristics.

Given the conflict between agent utilities and $P^{\star}$’s funding (Theorem
4), we propose the following heuristics for agent $i\in N$, for each project
$j\in P$, to employ in practice and observe their utility vs. welfare trade-
off.

  1. 1.

_Symmetric_ : $x_{ij}=\min(\theta_{ij},\gamma_{i}/m)$

  2. 2.

_Weighted_ : $x_{ij}=\left(\frac{\theta_{ij}}{\sum_{k\in
P}\theta_{ik}}\right)\gamma_{i}$

  3. 3.

_Greedy- $\theta$_: Greedily contribute $x_{ij}=\bar{x}_{ij}$ in descending
order of the projects sorted by $\theta_{ij},\forall j$

  4. 4.

_Greedy- $\vartheta$_: Greedily contribute $x_{ij}=\bar{x}_{ij}^{*}$ in
descending order of the projects sorted by
$\frac{\vartheta_{j}}{T_{j}},\forall j$

  5. 5.

_OptWelfare_ : $x_{ij}=\bar{x}_{ij}$, $\forall j\in P^{\star}$ and evenly
distribute the remaining budget across $P\setminus P^{\star}$

Agents contribute the minimum amount of what is specified by the five
heuristics and the amount left to fund the project. We consider OptWelfare as
the baseline (preferred) heuristic since it generates optimal welfare, i.e.,
funds $P^{\star}$.

##### Performance Measures.

To study the welfare vs. agent utility trade-off, we consider the following
performance measures: (i) _Normalized Social Welfare_ (SWN) – Ratio of the
welfare obtained and the welfare from $P^{\star}$ and (ii) _Normalized Agent
Utility_ (AUN) – Ratio of the agent utility obtained w.r.t. to the utility
when each agent has enough budget to play its PPR contribution $\forall~{}j\in
P$ (see Theorem 1).

We compare the heuristics when $\alpha\in(0,1]$ fraction of the total agents
_deviate_ , i.e., choose heuristic $\in$ {Symmetric, Weighted,
Greedy-$\theta$, Greedy-$\vartheta$}. The remaining $1-\alpha$ fraction of
agents use the baseline OptWelfare.

Figure 4: Empirical SWN and AUN for $\theta_{ij}\sim\mathbf{U}[0,10]$ Figure
5: AUN for $\alpha$ fraction of Agents Deviating vs. $1-\alpha$ fraction Non-
deviating

###  6.2 Simulation Setup and Results

##### Setup.

We simulate the combinatorial CC game with $n=100$, and $p=10$ and PPR refund
scheme (Eq. 2).333The experimental trends presented remain same for different
$(n,p)$ pairs, such as $(50,10)$, $(500,10)$, and $(500,20)$. We sample
$\theta_{ij}$s, for each $i\in N$ and $j\in P$, using (i) Uniform
Distribution, i.e., $\theta_{ij}\sim\mathbf{U}[0,10]$, and (ii) Exponential
Distribution, i.e., $\theta_{ij}\sim$ Exp($\lambda=1.5$). Here, $\lambda$ is
the rate parameter. When $\theta\sim\mathbf{U}[0,10]$, we get agents whose
per-project valuations differ significantly. For
$\theta\sim\mbox{Exp}(\lambda=1.5$), the agents have approximately similar
per-project valuations.

We ensure $\vartheta_{j}>T_{j}$ and $B_{j}\in(0,\vartheta_{j}-T_{j}]$ for each
project $j$ and that the properties Budget Deficit and Subset Feasibility for
$P^{\star}$ are satisfied. We run each simulation across $100$k instances and
observe the average SWN and AUN for each of the five heuristics. We depict our
observations with Figures 4 and 5 when $\theta_{ij}\sim\mathbf{U}[0,10]$. The
results for $\theta_{ij}\sim$ Exp($\lambda=1.5$) are presented in Appendix C.

##### Average SWN and AUN.

Figure 4 depicts the results when $\theta_{ij}\sim\mathbf{U}[0,10]$. We make
three main observations. First, deviating from the baseline heuristic
(OptWelfare) is helpful only when few agents deviate, i.e., for smaller values
of $\alpha$. Despite such a deviation, we observe that the corresponding
decrease in social welfare is marginal. On the other hand, the increase in
$\alpha$ reduces the amount of the contributions, and the projects remain
unfunded, reducing the social welfare and the agent utilities. Second,
deviating from OptWelfare always increases the average agent utility – at the
cost to the overall welfare. Third, Greedy-$\vartheta$ almost mimics
OptWelfare, for both SWN and AUN.

##### AUN for Deviating vs. Non-deviating Agents.

In Figure 5, we compare the average utility for the agents who deviate versus
those who do not. We let $\alpha=0.2$ fraction of the agents deviate and
follow the other four heuristics. From Figure 5, we observe that upon
deviating to Symmetric, Weighted or Greedy-$\theta$, the $\alpha=0.2$ fraction
of agents obtain higher AUN (red grid bars) compared to the remaining non-
deviating agents who do not deviate (green grid bars). In contrast,
Greedy-$\vartheta$ shows non-deviation to be beneficial. Since
Greedy-$\vartheta$ performs close to OptWelfare, the AUN for deviation remains
low compared to OptWelfare. Crucially, the deviation is not majorly helpful
when many agents deviate. When $\alpha=0.5$, we see comparable average AUN for
agents who deviate and those who do not (blue lined vs. magenta lined bars,
respectively). While deviating to Greedy-$\vartheta$ remains non-beneficial.

##### Discussion and Future Work.

From Figures 4 and 5, we see that Greedy-$\vartheta$ performs similar to
OptWelfare (which funds $P^{\star}$). Thus, as the number of projects $p$
increases, to maximize social welfare, it may be beneficial for the agents to
adopt Greedy-$\vartheta$ instead of deriving sophisticated strategies based on
$P^{\star}$ (since computing $P^{\star}$ is NP-Hard).

Generally, it is challenging to determine PSNE contributions for combinatorial
CC with budgeted agents. We propose four heuristics and study their welfare
and agent utility trade-off. Future work can explore other heuristics that
achieve better trade-offs and welfare guarantees. One can also study
strategies that perform better on average such as Bayesian Nash Equilibrium.
From the experiments, we observe that deviating from OptWelfare may increase
agent utility. Thus, one can explore strategies such as $\epsilon$-Nash
Equilibrium, which approximates a worst-case $\epsilon$ increase in utility
with unilateral deviation. Approximate strategies may also be desirable since
finding optimal deviation is NP-Hard. However, the approximation must provide
a desirable trade-off between agent utility and welfare.

##  7 Conclusion

This paper focuses on the funding guarantees of the projects in combinatorial
CC. Based on the overall budget, we categorize combinatorial CC into (i)
Budget Surplus and (ii) Budget Deficit. First, we prove that Budget Surplus is
insufficient to guarantee projects’ funding at equilibrium. Introducing the
stronger criteria of Subset Feasibility guarantees the projects’ funding at
equilibrium under Budget Surplus. However, for Budget Deficit, we prove that
the optimal welfare subset’s funding can not be guaranteed at equilibrium
despite Subset Feasibility. Next, we show that computing an agent’s optimal
strategy (and consequently, its optimal deviation), given the contributions of
the other agents, is NP-Hard. Lastly, we propose specific heuristics and
observe the empirical trade-off between agent utility and social welfare.

## References

  * London [2021] Mayor London.  The impact of community crowdfunding, 2021.  URL https://www.london.gov.uk/what-we-do/regeneration/funding-opportunities/make-london/impact-community-crowdfunding.
  * Van Montfort et al. [2021] Kees Van Montfort, Vinitha Siebers, and Frank Jan De Graaf.  Civic crowdfunding in local governments: Variables for success in the netherlands?  _Journal of Risk and Financial Management_ , 14(1):8, 2021.
  * Diederich et al. [2016] Johannes Diederich, Timo Goeschl, and Israel Waichman.  Group size and the (in) efficiency of pure public good provision.  _European Economic Review_ , 85:272–287, 2016.
  * Goodspeed [2017] Robert Goodspeed.  Community and urban places in a digital world.  _Digital World. City & Community_, 16(1):9–15, 2017.
  * Chandra et al. [2017] Praphul Chandra, Sujit Gujar, and Yadati Narahari.  Referral-embedded provision point mechanisms for crowdfunding of public projects.  In _AAMAS_ , pages 642–650, 2017.
  * Wang et al. [2021] Guanhua Wang, Runqi Guo, Yuko Sakurai, Muhammad Ali Babar, and Mingyu Guo.  Mechanism design for public projects via neural networks.  In _AAMAS_ , pages 1380––1388, 2021.
  * Yan and Chen [2021] Xiang Yan and Yiling Chen.  Optimal crowdfunding design.  In _AAMAS_ , pages 1704–1706, 2021.
  * Cason et al. [2021] Timothy N Cason, Alex Tabarrok, and Robertas Zubrickas.  Early refund bonuses increase successful crowdfunding.  _Games and Economic Behavior_ , 2021.
  * Kickstarter [2022] Kickstarter.  Kickstarter — Wikipedia, the free encyclopedia.  https://en.wikipedia.org/w/index.php?title=Kickstarter, 2022.
  * Spacehive [2022] Spacehive.  Spacehive - crowdfunding for local projects.  https://www.spacehive.com/, 2022.
  * Stroup [2000] Richard L Stroup.  Free riders and collective action revisited.  In _Public Choice Essays in Honor of a Maverick Scholar: Gordon Tullock_ , pages 137–150. Springer, 2000.
  * Zubrickas [2014] Robertas Zubrickas.  The provision point mechanism with refund bonuses.  _Journal of Public Economics_ , 120:231–234, 2014.
  * Damle et al. [2021] Sankarshan Damle, Moin Hussain Moti, Sujit Gujar, and Praphul Chandra.  Designing refund bonus schemes for provision point mechanism in civic crowdfunding.  In _PRICAI_ , page 18–32, 2021.
  * Chen et al. [2021] Yiling Chen, Biaoshuai Tao, and Fang-Yi Yu.  Cooperation in threshold public projects with binary actions.  In _IJCAI_ , pages 104–110, 2021.
  * Soundy et al. [2021] Jared Soundy, Chenhao Wang, Clay Stevens, and Hau Chan.  Game-theoretic analysis of effort allocation of contributors to public projects.  In _IJCAI_ , pages 405–411, 2021.
  * Brandl et al. [2022] Florian Brandl, Felix Brandt, Matthias Greger, Dominik Peters, Christian Stricker, and Warut Suksompong.  Funding public projects: A case for the nash product rule.  _Journal of Mathematical Economics_ , 99:102585, 2022.
  * Moulin [1994] Hervé Moulin.  Serial cost-sharing of excludable public goods.  _The Review of Economic Studies_ , 61(2):305–325, 1994.
  * Moulin and Shenker [2001] Hervé Moulin and Scott Shenker.  Strategyproof sharing of submodular costs: budget balance versus efficiency.  _Economic Theory_ , 18(3):511–533, 2001.
  * Dobzinski et al. [2018] Shahar Dobzinski, Aranyak Mehta, Tim Roughgarden, and Mukund Sundararajan.  Is shapley cost sharing optimal?  _Games and Economic Behavior_ , 108:130–138, 2018.  ISSN 0899-8256.  doi: https://doi.org/10.1016/j.geb.2017.03.008.  URL https://www.sciencedirect.com/science/article/pii/S0899825617300520.
  * Dobzinski and Ovadia [2017] Shahar Dobzinski and Shahar Ovadia.  Combinatorial cost sharing.  In _ACM EC_ , pages 387–404, 2017.
  * Birmpas et al. [2019] Georgios Birmpas, Evangelos Markakis, and Guido Schäfer.  Cost sharing over combinatorial domains: Complement-free cost functions and beyond.  In _ESA_ , pages 1–17, 2019.
  * Ohseto [2000] Shinji Ohseto.  Characterizations of strategy-proof mechanisms for excludable versus nonexcludable public projects.  _Games and Economic Behavior_ , 32(1):51–66, 2000\.
  * Aziz and Shah [2021] Haris Aziz and Nisarg Shah.  Participatory budgeting: Models and approaches.  In _Pathways Between Social Science and Computational Social Science_ , pages 215–236. Springer, 2021.
  * Aziz and Ganguly [2021] Haris Aziz and Aditya Ganguly.  Participatory funding coordination: Model, axioms and rules.  In _Algorithmic Decision Theory (ADT)_ , pages 409–423, 2021.
  * Sreedurga et al. [2022] Gogulapati Sreedurga, Mayank Ratan Bhardwaj, and Y Narahari.  Maxmin participatory budgeting.  _arXiv preprint arXiv:2204.13923_ , 2022.
  * Aziz et al. [2022] Haris Aziz, Sujit Gujar, Manisha Padala, Mashbat Suzuki, and Jeremy Vollen.  Coordinating monetary contributions in participatory budgeting.  _arXiv preprint arXiv:2206.05966_ , 2022.
  * Bagnoli and Lipman [1989] Mark Bagnoli and Barton L Lipman.  Provision of public goods: Fully implementing the core through private contributions.  _The Review of Economic Studies_ , 56(4):583–601, 1989.
  * Healy [2006] Paul J Healy.  Learning dynamics for mechanism design: An experimental comparison of public goods mechanisms.  _Journal of Economic Theory_ , 129(1):114–149, 2006.
  * Chandra et al. [2016] Praphul Chandra, Sujit Gujar, and Y Narahari.  Crowdfunding public projects with provision point: A prediction market approach.  In _ECAI_ , pages 778–786, 2016.
  * Damle et al. [2019a] Sankarshan Damle, Moin Hussain Moti, Praphul Chandra, and Sujit Gujar.  Civic crowdfunding for agents with negative valuations and agents with asymmetric beliefs.  In _IJCAI_ , pages 208–214, 2019a.
  * Damle et al. [2019b] Sankarshan Damle, Moin Hussain Moti, Praphul Chandra, and Sujit Gujar.  Aggregating citizen preferences for public projects through civic crowdfunding.  In _AAMAS_ , pages 1919–1921, 2019b.
  * Padala et al. [2021] Manisha Padala, Sankarshan Damle, and Sujit Gujar.  Learning equilibrium contributions in multi-project civic crowdfunding.  In _WI-IAT_ , pages 368––375, 2021.
  * Börgers and Krahmer [2015] Tilman Börgers and Daniel Krahmer.  _An introduction to the theory of mechanism design_.  Oxford University Press, USA, 2015.
  * Chakrabarty and Swamy [2014] Deeparnab Chakrabarty and Chaitanya Swamy.  Welfare maximization and truthfulness in mechanism design with ordinal preferences.  In _Proceedings of the 5th conference on Innovations in Theoretical Computer Science_ , pages 105–120, 2014.
  * Alegre [2020] Porto Alegre.  Case study 2-porto alegre, brazil: participatory approaches in budgeting and public expenditure management, 2020.
  * HudExchange [2022] HudExchange.  Participatory budgeting.  https://www.hudexchange.info/programs/participatory-budgeting/, 2022\.
  * Lawler [1977] Eugene L Lawler.  Fast approximation algorithms for knapsack problems.  In _18th Annual Symposium on Foundations of Computer Science (sfcs 1977)_ , pages 206–213. IEEE, 1977.
  * Cason and Zubrickas [2017] Timothy N Cason and Robertas Zubrickas.  Enhancing fundraising with refund bonuses.  _Games and Economic Behavior_ , 101:218–233, 2017.
  * Zou et al. [2010] James Zou, Sujit Gujar, and David Parkes.  Tolerable manipulability in dynamic assignment without money.  In _AAAI_ , pages 947–952, 2010.
  * Lubin and Parkes [2012] Benjamin Lubin and David C Parkes.  Approximate strategyproofness.  _Current Science_ , pages 1021–1032, 2012.

##  Appendix A Proofs

This section presents the formal proofs for the results covered in the main
paper.

###  A.1 Proof of Theorem 2

######  Theorem.

Given $(R_{j})_{j\in P}$ which satisfy Condition 1, there are Budget Surplus
(Def. 4) game instances of $\mathcal{M}_{CC}$ with
$B_{j}=\vartheta_{j}-T_{j},\forall j$ such that there is no equilibrium. That
is, the set of equilibrium contributions may be empty.

###### Proof.

Consider the set of $P$ projects and $N$ agents s.t. Def. 4 is satisfied,
i.e., $\sum_{i\in N}\gamma_{i}\geq\sum_{j\in P}T_{j}$. Denote $N_{1}\subset N$
as the set of agents whose overall budget is such that even if they contribute
their entire budget none of the project gets funded.444E.g., There exists an
agent with budget less than $\min_{j}T_{j}$. Also note that, we do not assume
$N_{1}$ to be unique.  This implies $\sum_{i\in
N_{1}}\gamma_{i}<\min_{j}T_{j}$. The remaining set of agents $N_{2}=N\setminus
N_{1}$ must have enough budget to fund all the projects (from Def. 4).

Note that, each agent $i$ receives a funded utility
$\sigma_{ij}^{F}=\theta_{ij}-x_{ij}$ for contributing $x_{ij}$ towards project
$j$. That is, the funded utility decreases with the increase in contribution.
The agent may also receive an unfunded utility of
$r_{ij}=R_{j}(x_{ij},B_{j},\cdot)$ for project $j$. Since $R_{j}$ is
monotonically increasing (Condition 1), increasing the contribution increases
the refund. We depict this scenario with Figure 2. Observe that the plot
between funded and unfunded utility w.r.t. contributions meet at the upper-
bound of the equilibrium contribution $\bar{x}_{ij}$ (as defined in Theorem
1), where funded utility is equal to the unfunded. For any contribution
$x_{ij}>\bar{x}_{ij}$, the agent receives a greater unfunded utility.

Consider a scenario where the agents in $N_{1}$ do not have sufficient budget
and thus contribute less than $\bar{x}_{ij}$. Let $C^{\prime}=\sum_{i\in
N_{1}}\left(\sum_{j\in P}x_{ij}\right)$. Now, we have $x_{r}=\sum_{j\in
P}T_{j}-C^{\prime}$ as the remaining amount to fund the set $P$. In order to
fund $P$, the remaining agents in $N_{2}$ may need to contribute
$\hat{x}_{ij}>\bar{x}_{ij}$ where $i\in N_{2}$ (refer Figure 2). At
$\hat{x}_{ij}$, the unfunded utility is more. Hence, the agents contribute
$x_{ij}=\bar{x}_{ij}-\epsilon$, s.t. $\epsilon\to 0$ and $\epsilon>0$, i.e.,
the contributions are not well-defined. ∎

###  A.2 Proof of Claim 1

######  Claim.

Given any $(R_{j})_{j\in P}$ whose equilibrium contributions satisfy
$\sum_{i}\bar{x}_{ij}\geq T_{j}$, we have SFP $\implies$ BS.

###### Proof.

From the definition of SFP, $\gamma_{i}\geq\sum_{j\in
P}\bar{x}_{ij},~{}\forall i\in N$. As $\sum_{i}\bar{x}_{ij}\geq T_{j}$, we
have $\sum_{i}\gamma_{i}\geq\sum_{j\in P}\sum_{i}\bar{x}_{ij}\geq\sum_{j\in
M}T_{j}$, i.e., Budget Surplus is also satisfied. ∎

###  A.3 Proof of Theorem 3

######  Theorem.

Given $\mathcal{M}_{CC}$ and $(R_{j})_{j\in P}$ satisfying CM (Condition 1)
such that $SF_{P}$ is satisfied, at equilibrium all the projects are funded,
i.e., $C_{j}=T_{j},~{}\forall j\in P$ if
$B_{j}\leq\vartheta_{j}-T_{j},~{}\forall j\in P$. Further, the set of PSNEs
are:
$\left\\{(x_{ij}^{*})_{j\in
P}~{}|~{}\sigma_{ij}^{F}(x_{ij}^{*};\cdot)\geq\sigma_{ij}^{U}(x_{ij}^{*};\cdot),\forall
j\in P,~{}\forall i\in N\right\\}$.

###### Proof.

For a given refund scheme $R_{j}$ and corresponding $\bar{x}_{ij}$, each agent
$i$’s budget $\gamma_{i}$ satisfies, using SFP, $\gamma_{i}\geq\sum_{j\in
P}\bar{x}_{ij}$. Let each agent $i$’s final contribution
$x_{ij}^{*}\leq\bar{x}_{ij}$; where
$\sigma_{ij}^{F}(\bar{x}_{ij})=\sigma_{ij}^{U}(\bar{x}_{ij})$. Since
$\sum_{i\in N}\bar{x}_{ij}\geq T_{j}$, the project gets funded, and each agent
obtains a utility of
$\sigma_{ij}(x_{ij}^{*},x_{-ij}^{*};\cdot)=\theta_{ij}-x_{ij}^{*}$.

W.l.o.g., let us assume that agent $n$ contributes
$x_{nj}^{*}=T_{j}-\sum_{i\in N\setminus\\{n\\}}x_{ij}^{*}\leq\bar{x}_{nj}$
s.t. $\sum_{i\in N}x_{ij}^{*}=T_{j}$. Then $\forall j\in P$, we can construct
the following two deviations for $i$:

  1. 1.

$\hat{x}_{ij}<x_{ij}^{*}$. For any $\hat{x}_{ij}$ less than $x_{ij}^{*}$, the
project $j$ is not funded and
$R_{j}(\hat{x}_{ij})=\sigma_{ij}(\hat{x}_{ij},x_{-ij}^{*};\cdot)<\sigma_{ij}(x_{ij}^{*},x_{-ij}^{*};\cdot)$.

  2. 2.

$\hat{x}_{ij}>x_{ij}^{*}$. For any $\hat{x}_{ij}>x_{ij}^{*}$, the project is
funded but the funded utility reduces, i.e.,
$\sigma_{ij}(\hat{x}_{ij},x_{-ij}^{*};\cdot)=\theta_{ij}-\hat{x}_{ij}<\sigma_{ij}(x_{ij}^{*},x_{-ij}^{*};\cdot)=\theta_{ij}-x_{ij}^{*}$.

In both the cases, we obtain the following,

$\sigma_{ij}(x_{ij}^{*},x_{-ij}^{*};\cdot)\geq\sigma_{ij}(\hat{x}_{ij},x_{-ij}^{*};\cdot),\forall\hat{x}_{ij},\forall
j.$

Therefore,

$\sum_{j\in P}\sigma_{ij}(x_{ij}^{*},x_{-ij}^{*};\cdot)\geq\sum_{j\in
P}\sigma_{ij}(\hat{x}_{ij},x_{-ij}^{*};\cdot),\forall\hat{x}_{ij}$

From Def. 3, $x_{ij}^{*}$ are PSNE and every project gets funded. ∎

###  A.4 Proof of Theorem 4

######  Theorem.

Given an instance of $\mathcal{M}_{CC}$, a unique non-trivial
$P^{\star}\subset P$ may not be funded at equilibrium even with Subset
Feasibility for $P^{\star}$, SF${}_{P^{\star}}$, for any set of $(R_{j})_{j\in
P}$ satisfying Condition 1.

###### Proof.

We provide a proof by construction for $n=2$ and $p=2$ where one of the agents
has an incentive to deviate when $P^{\star}$ is funded. Procedure 1 presents
the general steps to construct the instance. Informally, we first select the
target cost of the project $1$, i.e. $T_{1}$, to be any positive real value.
Given $(R_{j})_{j\in P}$ under Condition 1, we can always find an
$\bar{x}_{11}$ for agent $1$. At $\bar{x}_{11}$, funded utility is equal to
unfunded utility (refer Figure 2). Trivially, $\bar{x}_{11}<\theta_{11}$. We
now prove that the construction defined in Procedure 1 is always possible.

Line 3. We select $\theta_{11}$ such that $x_{11}^{*}<T_{1}<\theta_{11}$. We
are required to prove that such a $\theta_{11}$ will always exist. When
$\theta_{11}=T_{1}$, it must be true that, $x_{11}^{*}<\theta_{11}=T_{1}$. If
$x_{11}^{*}=T_{1}$ then $R(x_{11}^{*})=0$ (i.e., funded utility equals
unfunded utility), since $R(0)=0$ by construct, contradicting Condition 1.
Hence $x_{11}^{*}<T_{1}$, when $\theta_{11}=T_{1}$. As $x_{11}^{*}$ is
continuous w.r.t. $\theta_{11}$, we can always chose $\theta_{11}>T_{1}$ s.t.
$x_{11}^{*}<T_{1}$.

Line 4. We choose $\theta_{21}$ s.t., $x_{21}^{*}=T_{1}-x_{11}^{*}$. It is
possible since $T_{1}-x_{11}^{*}>0$.

Line 5. We let $T_{2}=x_{21}^{*}$ and $\theta_{12}=0$. Then, select
$\theta_{22}<\theta_{11}+\theta_{21}-x_{11}^{*}$. Observe that, we can always
select $\theta_{22}>\theta_{21}$ since $\theta_{11}-x_{11}^{*}>0$.

Given the above, and the values $T_{2}=T_{1}-x_{11}^{*}$ and $\theta_{12}=0$;
we arrive at $\theta_{11}+\theta_{21}-T_{1}>\theta_{12}+\theta_{22}-T_{2}$.
Hence, $P^{\star}=\\{1\\}$, i.e., the welfare optimal subset is $\\{1\\}$ and
is unique.

Line 6. To ensure $SF_{P^{\star}}$, i.e., Subset Feasibility of $P^{\star}$,
we set $\gamma_{1}=x_{11}^{*}$ and $\gamma_{2}=x_{12}^{*}$. Note that,
$\gamma_{1}+\gamma_{2}=T_{1}<T_{1}+T_{2}$, Budget Deficit is also satisfied.
Thus, Procedure 1 returns valid instance, say $\mathcal{M}^{\prime}$, of
$\mathcal{M}_{CC}$.

Next, note that, in $\mathcal{M}^{\prime}$, agent 1 contributes $\bar{x}_{11}$
and agent 2 must contribute $\bar{x}_{21}$ to fund project 1 and to achieve
socially efficient equilibrium. If agent 2 does not deviate, it will receive
an utility $\sigma_{2}=\theta_{21}-\bar{x}_{21}$. However, let agent 2
unilaterally deviate and contribute $\bar{x}_{21}$ to project 2. As
$T_{2}=\bar{x}_{21}$, project 2 gets funded and agent 2 obtains a utility of
$\sigma^{\prime}_{2}=\theta_{22}-\bar{x}_{21}$. From Line 5 in Procedure 1, we
know that $\sigma^{\prime}_{2}>\sigma_{2}$, hence agent 2 will deviate,
implying $P^{\star}=\\{1\\}$ is not funded at equilibrium for the
$\mathcal{M}^{\prime}$ game. ∎

###  A.5 Proof of Theorem 5

######  Theorem.

Given an instance of $\mathcal{M}_{CC}$ and for any set of $(R_{j})_{j\in P}$
satisfying Condition 1, an agent $i^{\prime}$’s optimal strategy may not
exist.

###### Proof.

From Example 2, let agent 1 contribute its entire budget to project 1, i.e.,
$T_{1}-C_{1}=\bar{x}_{11}$ and $C_{2}=0$. Now we solve MIP-CC for agent 2.
Since $\gamma_{i}=\bar{x}_{i1},~{}\forall i$ and
$T_{j}=\bar{x}_{1j}+\bar{x}_{2j},~{}\forall j$ (see Eq. 3), the overall budget
is enough to fund only a single project. That is, as agent 1 has contributed
to project 1, agent 2 can (at best) fund only project 1. So the set of
indicator variable $z$s in MIP-CC can be either $z_{1}=\\{1,0,0\\}$ or
$z_{2}=\\{0,0,0\\}$.

Computing Optimal Strategy. We have the following cases:

  * $\bullet$

$z=\\{1,0,0\\}$: This is possible when agent 2 contributes $x_{21}=\gamma_{2}$
to project 1, resulting in project $1$’s funding. The utility agent 2 gets is
$\theta-\bar{x}_{21}$.

  * $\bullet$

$z=\\{0,0,0\\}$: Agent 2 may opt to contribute in all the 3 projects in order
to grab the maximum refund. As the refund shares from $R_{j}(\cdot)$ sum
exactly to $B_{j}$, agent 2 can grab the entire bonus from projects 2 and 3 by
contributing any arbitrary positive value, $\epsilon>0$. However, agent 2 must
contribute $\epsilon$ less in project 1 since, $\gamma_{2}=\bar{x}_{21}$.
Hence, project 1 becomes unfunded. For optimal strategy, agent 2 must maximize
the refund from project 1, i.e.,
$\underset{x_{21}}{\max}~{}R_{1}(x_{21},\cdot)~{}\mbox{s.t.~{}}x_{21}<T_{1}-C_{1}$.
Therefore, $x_{21}$ is not well-defined as $R_{1}(x_{21},\cdot)$ satisfies CM.
So the overall utility by deviating for agent 2 becomes
$2B+R(x_{21}-\epsilon,\cdot)$ where an optimal $\epsilon$ is not defined.

∎

###  A.6 Proof of Theorem 6

######  Theorem.

Given an instance of $\mathcal{M}_{CC}$ with discrete contributions and for
any set of $(R_{j})_{j\in P}$ satisfying Condition 1, computing optimal
strategy for agent $i^{\prime}$, given the contributions of
$N\setminus\\{i^{\prime}\\}$, is NP-Hard.

###### Proof.

For completeness, we first re-write MIP-CC-D (see Figure 3) for discrete
contributions. Let $D=\\{\kappa\cdot\delta~{}|~{}\kappa\in\mathbb{N}\\}$
denote the discrete contribution set where $\delta$ is the smallest unit of
contribution. Now, the following optimization defines MIP-CC-D for agent
$i^{\prime}$ without the sub-script “$i^{\prime}$". Note that, Eq. A1 is
merely the optimization presented in Figure 3 with the added constraint on the
contribution set.

$\displaystyle\begin{rcases}\max_{(x_{j})_{j\in P}}&\sum_{j\in
P}z_{j}\cdot(\theta_{j}-x_{j})+(1-z_{j})\cdot R(x_{j},\cdot)\\\
\mbox{{s.t.}}&\sum_{j\in P}x_{j}\leq\gamma\\\ &x_{j}\leq
T_{j}-C_{j-i^{\prime}},\forall j\\\ &(x_{j}-T_{j}+C_{j-i^{\prime}})\cdot
z_{j}\geq 0,\ \forall j\\\ &x_{j}-T_{j}+C_{j-i^{\prime}}<z_{j},\forall j\\\
&z_{j}\in\\{0,1\\},x_{j}\in D,\forall j\end{rcases}$ (A1)

We first construct an optimization problem MIP, which we show is equivalent to
the KNAPSACK problem in Part A. In Part B, we show that the MIP reduces to
MIP-CC-D implying MIP-CC-D is also NP-Hard.

####  A.6.1 Part A: Designing MIP (Eq. A2)

For our proof, we consider a refund scheme $R_{j}(\cdot)=R(\cdot)$ and bonus
budget $B_{j}=B$ which is the same for each project $j$. $R(\cdot)$ satisfies
CM (Condition 1) such that the refund share satisfies
$\sum_{j}R(x_{j},\cdot)=R(\sum_{j}x_{j},\cdot)$. 555An example of such a
refund scheme can be $R(\cdot)=\frac{x\cdot B_{\min}}{\vartheta_{\max}}$ where
$B_{\min}=\min_{j}(\vartheta_{j}-T_{j})$ and
$\vartheta_{\max}=\max_{j}\vartheta_{j}$. Now we define the MIP as follows.

$\displaystyle\begin{rcases}&\max_{z=(z_{1},\ldots,z_{p})}\sum_{j\in
P}z_{j}(\theta_{j}-r_{j})+R(\gamma-\sum_{j\in P}z_{j}r_{j},\cdot)\\\
\textbf{s.t.:}&\sum_{j}z_{j}r_{j}\leq\gamma\mbox{~{}and~{}}z_{j}\in\\{0,1\\}\end{rcases}$
(A2)

We now prove that the MIP defined in Eq. A2 is NP-Hard. The MIP can be re-
written as,

$\displaystyle\max_{z=(z_{1},\ldots,z_{p})}$ $\displaystyle\sum_{j\in
P}z_{j}(\theta_{j}-r_{j})+R(\gamma-\sum_{j\in P}z_{j}r_{j},\cdot)$
$\displaystyle=\max_{z=(z_{1},\ldots,z_{p})}$ $\displaystyle\sum_{j\in
P}z_{j}(\theta_{j}-r_{j})-\sum_{j\in P}z_{j}R(r_{j})+R(\gamma)$
$\displaystyle\quad\left(\text{By}\
\sum_{j}R(x_{j},\cdot)=R(\sum_{j}x_{j},\cdot),\ z_{j}\in\\{0,1\\}.\right)$
$\displaystyle=\max_{z=(z_{1},\ldots,z_{p})}$ $\displaystyle\sum_{j\in
P}z_{j}(\theta_{j}-r_{j}-R(r_{j}))+R(\gamma)$
$\displaystyle=\max_{z=(z_{1},\ldots,z_{p})}$ $\displaystyle\sum_{j\in
P}z_{j}(\theta_{j}-r_{j}-R(r_{j}))$

We reduce the MIP problem from the NP-complete $\operatorname{KNAPSACK}$
problem: given $m$ items with weights $w_{1},\cdots,w_{m}$ and value
$s_{1},\cdots,s_{m}$, capacity $B$ and value $V$, does there exist a subset
$Q\subseteq\\{1,\cdots,m\\}$ such that $\sum_{j\in Q}w_{j}\leq B$ and
$\sum_{j\in Q}s_{j}\geq V$? Given an instance of the $\operatorname{KNAPSACK}$
problem, we build an instance of the above MIP as follows:

  * $\bullet$

The set of projects is the set of items. The amount left for funding the
project is $r_{j}=w_{j}$. The budget of the agent $i^{\prime}$ is $\gamma=B$.

  * $\bullet$

The value of each project to the agent is, $\theta_{j}-r_{j}-R(r_{j})=s_{j}$,
i.e., $\theta_{j}-R(r_{j})=s_{j}+w_{j}$.

We can see that the utility obtained by choosing a set of projects
$Q=\\{j|z_{j}=1\\}$ is exactly equal to the value of choosing set of items $Q$
in the KNAPSACK problem i.e, $\sum_{j\in
Q}\theta_{j}-r_{j}-R(r_{j})=\sum_{j\in Q}s_{j}$. Also note that the budget
constraint is satisfied if and only if the capacity constraint is satisfied.
It follows that a solution with value at least $V$ exists in the KNAPSACK
problem if and only if there exists a set of projects whose social welfare in
the above instance is at least $V$.

Thus, we reduce MIP from KNAPSACK implying MIP is NP-Hard. ∎

We next show that MIP in Eq. A2 also reduces to MIP-CC-D.

####  A.6.2 Part B: Reducing MIP to MIP-CC-D

Before we show the reduction, we define the following handy notations for the
objectives of MIP-CC-D and MIP.

$\displaystyle F(z,x)$ $\displaystyle=\sum_{j\in
P}z_{j}\cdot(\theta_{j}-x_{j})+\sum_{j\in P}(1-z_{j})\cdot R(x_{j},\cdot)$
“MIP-CC-D” $\displaystyle G(z)$ $\displaystyle=\sum_{j\in
P}z_{j}\cdot(\theta_{j}-r_{j})+R(\gamma-\sum_{j\in P}z_{j}r_{j},\cdot)$ “MIP
in Eq. A2”

Further let, $(Z^{F},X^{F})$ denote the tuple of feasible solutions to MIP-
CC-D and $Z^{G}$ denote the set of feasible solutions to MIP.

Given an instance of MIP we construct an instance of MIP-CC-D using the
following conditions,

  * P1.

For each project $j$, we have $R_{j}(\cdot)=R(\cdot)$ s.t.
$\sum_{j}R(x_{j},\cdot)=R(\sum_{j}x_{j},\cdot)$.

  * P2.

Let the remaining contribution be $C_{j-i^{\prime}}=T_{j}-r_{j},~{}\forall
j\in P$.

Using P1 and P2, we now show that any $(z^{*},x^{*})\in OPT_{MIP-CC-D}$
implies that $z^{*}\in OPT_{MIP}$.

######  Claim I.

For the specific setting defined by P1-P2 and given $(Z^{F},X^{F})$ and
$Z^{G}$ as the tuple of feasible solutions to MIP-CC-D and MIP in Eq. A2,
respectively, we have $Z^{G}\subseteq Z^{F}$.

###### Proof.

For the proof, we show that given any solution $z\in Z^{G}$, we can also
construct a solution $(z,x)\in(Z^{F},X^{F})$. That is, given $z$, we can
construct $x$ as follows. Let $x_{j}=r_{j}$ if $z_{j}=1$ and $x_{j}=0$ if
$z_{j}=0$.

We now have to show that $x$’s construction does not break feasibility of a
solution in MIP-CC-D. Observe that, from Eq. A1,

  * •

Trivially, we have $\sum_{j}x_{j}=\sum_{j}z_{j}r_{j}\leq\gamma$ and $x_{j}\leq
r_{j}=T_{j}-C_{j-i^{\prime}}$. That is, the budget constraint and project’s
funding conditions are satisfied.

  * •

If $z_{j}=0$, then both $(x_{j}-T_{j}+C_{j-i^{\prime}})\cdot z_{j}\geq 0$ and
$x_{j}-T_{j}+C_{j-i^{\prime}}<z_{j}$ hold.

  * •

Likewise, if $z_{j}=1$ then both $(x_{j}-T_{j}+C_{j-i^{\prime}})\cdot
z_{j}\geq 0$ and $x_{j}-T_{j}+C_{j-i^{\prime}}<z_{j}$ hold.

Hence for every $z\in Z^{G}$ we can construct $(z,x)$ s.t.,
$(z,{x})\in(Z^{F},X^{F})$. Hence every solution that is feasible for MIP is
also feasible for MIP-CC-D. ∎

With this, consider the following claim.

######  Claim II.

For the specific setting defined by P1-P2 and any fixed $z\in Z^{F}$, let
$\hat{x}_{j}^{z}=r_{j}$ where $z_{j}=1$ and $r_{j}=T_{j}-C_{j-i^{\prime}}$ and
$\sum_{j}\hat{x}^{z}=\gamma$. Then $\exists\hat{x}^{z}\in X^{F}$, such that
$F(z,\hat{x}^{z})\geq F(z,x)$, $\forall x\in X^{F}$.

###### Proof.

Given a fixed $(z,x)\in(Z^{F},X^{F})$, observe that,

$\displaystyle F(z,x)$ $\displaystyle=\sum_{j\in
P}z_{j}\cdot(\theta_{j}-x_{j})+\sum_{j\in P}(1-z_{j})\cdot R(x_{j},\cdot)$
$\displaystyle=\sum_{j\in P}z_{j}(\theta_{j}-x_{j})+R(\sum_{j\in
P}(1-z_{j})x_{j},\cdot)\qquad\left(\text{As}\
\sum_{k}R(x_{k},\cdot)=R(\sum_{k}x_{k},\cdot)\right)$
$\displaystyle=\sum_{j\in P}z_{j}(\theta_{j}-x_{j})+R(\sum_{j\in
P}x_{j}-\sum_{j\in P}z_{j}x_{j},\cdot)$ $\displaystyle\leq\sum_{j\in
P}z_{j}(\theta_{j}-x_{j})+R(\gamma-\sum_{j\in
P}z_{j}x_{j},\cdot)\qquad\left(\text{As}\ \sum_{j}x_{j}\leq\gamma\ \text{and}\
R\ \text{satisfies CM}\right)$ $\displaystyle\leq\sum_{j\in
P}z_{j}(\theta_{j}-r_{j})+R(\gamma-\sum_{j}z_{j}x_{j},\cdot)\qquad\left(\text{From~{}Eq.~{}}\ref{eq::opt_mip},\
x_{j}<r_{j}\implies z_{j}=0\right)$ $\displaystyle=\sum_{j\in
P}z_{j}(\theta_{j}-r_{j})+R(\gamma-\sum_{j\in
P}z_{j}r_{j},\cdot)=F(z,\hat{x}^{z}).$

Hence, $F(z,\hat{x}^{z})=\sum_{j\in
P}z_{j}(\theta_{j}-r_{j})+R(\gamma-\sum_{j}z_{j}r_{j},\cdot)\geq F(z,x)$ where
$\hat{x}_{j}^{z}=r_{j}$ if $z_{j}=1$ and $\sum_{j}\hat{x}_{j}^{z}=\gamma$.

To conclude the proof, we now show that the contribution set is also feasible.
To this end, observe that from the claim statement we have
$\sum_{j}\hat{x}^{z}=\gamma$. Further, since for each $z_{j}=1$, we have by
construction $\hat{x}^{z}_{j}=r_{j}\leq T_{j}-C_{j-i^{\prime}}$ and for each
$z_{j}=0$ we have $\hat{x}^{z}_{j}<r_{k}$, the second feasibility condition is
also met. ∎

We can trivially observe that $G(z)=F(z,\hat{x}^{z})$ where
$\hat{x}_{j}^{z}=r_{j}$ if $z_{j}=1$ and $\sum_{j}\hat{x}_{j}^{z}=\gamma$. Let
$(z^{*},x^{*})\in OPT_{MIP-CC-D}$, then $F(z^{*},x^{*})\geq
F(z^{*},\hat{x}^{z^{*}})$ and from Claim II, $F(z^{*},\hat{x}^{z^{*}})\geq
F(z^{*},x^{*})$, hence $x^{*}=\hat{x}^{z^{*}}$. That is,

$G(z^{*})=F(z^{*},x^{*})=\max_{z\in Z^{F}}F(z,\hat{x}^{z^{*}})=\max_{z\in
Z^{F}}G(z).$

Given that (i) the feasibility set of MIP is a subset of the feasibility set
of MIP-CC-D and (ii) $z^{*}$ is also feasible to MIP since
$\sum_{j}x_{j}^{*}\leq\gamma$ and $x_{j}^{*}\leq r_{j},\ \forall j$, we have
$\sum_{j}z_{j}^{*}r_{j}\leq\gamma$. Hence $z^{*}$ is also optimal to MIP.

In summary, Part B shows that MIP in Eq. A2 reduces to MIP-CC-D. That is, any
solution to MIP-CC-D can be used to determine a solution to MIP in Eq. A2.
Hence, MIP-CC-D is also NP-Hard.

###  A.7 Proof of Corollary 2

######  Corollary 1.

Given an instance of $\mathcal{M}_{CC}$ with discrete contributions and for
any set of $(R_{j})_{j\in P}$ satisfying Condition 1, if all agents except
$i^{\prime}$, $N\setminus\\{i^{\prime}\\}$, follow a specific strategy that
funds $P^{\star}\subset P$, then computing the optimal deviation for agent
$i^{\prime}$ is NP-Hard.

###### Proof.

Let $N\setminus\\{i^{\prime}\\}$ agents follow a specific strategy and
contribute to the projects s.t. $P^{\star}$ is not funded. For any such
strategy, given $N\setminus\\{i^{\prime}\\}$ contributions, agent
$i^{\prime}$’s optimal deviation is again given by MIP-CC-D. Hence NP-Hardness
follows directly from Theorem 6. ∎

##  Appendix B Illustration of Procedure 1 for PPR

To further clarify the impossibility presented in Theorem 4, we demonstrate
Procedure 1 when $(R_{j})_{j\in P}$ is the PPR refund scheme (Eq. 2). As
required, consider a setting with $P=\\{1,2\\}$ and $N=\\{1,2\\}$. Let
$T_{1}=10$ and $B_{1}=1$. We choose $\theta_{11}=10.9$ which implies
$\bar{x}_{11}=9.91$ using Theorem 1. That is,
$\bar{x}_{11}<T_{1}<\theta_{11}$. Now, fix
$\bar{x}_{21}=T_{1}-\bar{x}_{11}=0.99$. This also implies $T_{2}=0.99$. The
upper bound on the equilibrium contribution, $\bar{x}_{21}=0.99$, is possible
for the value $\theta_{21}=1.089$. Select $\theta_{22}=1.9$, to get
$\theta_{22}>\theta_{21}$. This also implies $P^{\star}=\\{1\\}$, i.e.,
$\theta_{11}+\theta_{21}-T_{1}=1.989$ and
$\theta_{12}+\theta_{22}-T_{2}=0.91$. Despite this, agent 2 will deviate since
$\theta_{22}-T_{2}>\theta_{21}-\bar{x}_{21}$.

##  Appendix C Exponential Distribution

Figure 6: Empirical SWN and AUN for $\theta_{ij}\sim\mbox{Exp}(\lambda=1.5)$

We now provide the results when agents sample their valuations using the
Exponential distribution, i.e., for each agent $i$ and for the project $j$,
let $\theta_{ij}\sim\mathbf{Exp}(\lambda=1.5)$. Here, $\lambda$ is the rate
parameter. Figure 6 depicts the empirical Normalized Social Welfare (SWN) and
Normalized Agent Utility (AUN).

Despite the difference in sampling $\theta$s, we observe that the overall
trend in AUN and SWN is the same as that reported for the Uniform case (in the
main paper). That is, agent deviation is helpful only for smaller $\alpha$s.
And that such a deviation results in only a marginal decrease in the overall
welfare obtained.

These results further suggest that agents may prefer the strategy
Greedy-$\vartheta$ as the number of projects increases. One can also study the
notion of $\epsilon$-Nash Equilibrium for these cases and provide theoretical
bounds on the tolerance $\epsilon$ vis-a-vis the social welfare.