11institutetext: UNSW Sydney, Australia
11email<EMAIL_ADDRESS>22institutetext: Data61 CSIRO

# Participatory Funding Coordination:
Model, Axioms and Rules

Haris Aziz 1122 Aditya Ganguly 11

###### Abstract

We present a new model of collective decision making that captures important
crowd-funding and donor coordination scenarios. In the setting, there is a set
of projects (each with its own cost) and a set of agents (that have their
budgets as well as preferences over the projects). An outcome is a set of
projects that are funded along with the specific contributions made by the
agents. For the model, we identify meaningful axioms that capture concerns
including fairness, efficiency, and participation incentives. We then propose
desirable rules for the model and study, which sets of axioms can be satisfied
simultaneously. An experimental study indicates the relative performance of
different rules as well as the price of enforcing fairness axioms.

##  1 Introduction

Consider a scenario in which a group of house-mates want to pitch in money to
buy some common items for the house but not every item is of interest or use
to everyone. Each of the items (e.g. TV, video game console, music system,
etc.) has its price. Each resident would like to have as many items purchased
that are useful to her. She may have concerns about whether she is getting
enough value for the contribution she makes. It is a scenario that is
encountered regularly in numerous shared houses or apartments.

As a second scenario, hundreds of donors want to fund charitable projects.
Each of the projects (e.g. building a well, enabling a surgery, funding a
scholarship, etc.) has a cost requirement. Donors care about coordinating
their donations in a way to fund commonly useful projects and they care about
the amount of money that is used towards projects that they approve. How to
coordinate the funding in a principled and effective way is a fundamental
problem in crowdfunding and donor coordination. The model that we propose is
especially suitable for coordinating donoations from alumni at our university.

Both of the settings above are coordination problems in which agents
contribute money and they have preferences over the social outcomes. A
collective outcome specifies which projects are funded and how much agents are
charged.

### Contributions.

We propose a formal model that we refer to as _Participatory Funding
Coordination (PFC)_ that captures many important donor coordination scenarios.
In this model, agents have an upper budget limit. They want as many of their
approved projects funded. We lay the groundwork for work on the model by
formulating new axioms for the model. The logical relations between the axioms
are established and the following question is studied: which sets of axioms
are simultaneously achievable. We propose and study rules for the problems
that are inspired by welfarist concerns but satisfy participation constraints.
In addition to an axiomatic study of the rules, we also undertake an
experimental comparison of the rules. The experiment sheds light on the impact
that various fairness or participation constraints can have on the social
welfare. This impact has been referred to as the price of fairness in other
contexts. In particular, we investigate the effects of enforcing fairness
properties on instances that model real-world applications of PFC, including
crowdfunding.

##  2 Related Work

Our model generally falls under the umbrella of a collective decision making
setting in which agents’ donations and preferences are aggregated to make
funding decisions. It is a concrete model within the broad agenda of achieving
effective altruism (MacAskill, 2015, 2017, Peters, 2019).

The model we propose is related to the discrete participatory budgeting model
(Aziz and Shah, 2020, Aziz et al., 2018, Goel et al., 2019, Fain et al., 2016,
Talmon and Faliszewski, 2019). In discrete participatory budgeting, agents do
not make personal donations towards the projects. They only express
preferences over which projects should be funded. We present several axioms
that are only meaningful for our model and not for discrete participatory
budgeting. Algorithms for discrete participatory budgeting cannot directly be
applied to our setting because they do not take into account individual
rationality type requirements.

Another related setting is multi-winner voting (Elkind et al., 2017). Multi-
winner voting can be viewed as a restricted version of discrete participatory
budgeting. The Participatory Funding Coordination (PFC) setting differs from
multi-winner voting in some key respects: in our model, each project (winner)
has an associated cost, and we select projects subject to a knapsack
constraint as opposed to having a fixed number of winners.

Our PFC model relies on approval ballots in order to elicit agents’
preferences. Dichotomous preferences have been considered in several important
setting including committee voting (Lackner and Skowron, 2019, Aziz et al.,
2017) and discrete participatory budgeting (Aziz et al., 2018, Fluschnik et
al., 2019).

Another related model that takes into account the contributions of agents was
studied by Brandl et al. (2020). Just like in our model, an agent’s utilities
are based on how much money is spent on projects approved by the agent.
However, their model does not have any costs and agents can spread their money
over projects in any way. Our model has significant differences from the model
of (Brandl et al., 2019, 2020): (1) in our setting, the projects are
indivisible and have a minimum cost to complete, (2) agents may not be charged
the full amount of their budgets. The combination of these features leads to
challenges in even defining simple individual rationality requirements.
Furthermore, it creates difficulties in finding polynomial-time algorithms for
some natural aggregation rules (utilitarian, egalitarian, Nash product, etc.).
Our model is more appropriate for coordinating donations where projects have
short-term deadlines and a target level of funding which must be reached for
the project to be successfully completed. We show that the same welfarist
rules that satisfy some desirable properties in the model (Brandl et al.,
2019, 2020), fail to do so in our model. Just as the work of Brandl et al.
(2019, 2020), Buterin et al. (2019) consider donor coordination for the
divisible model in which the projects do not have costs and agents do not have
budget limits. They also assume quasi-linear utilities whereas we model
charitable donors who are not interested in profit but want their money being
used as effectively as possible towards causes that matter to them.

The features of our PFC model enable the model to translate smoothly to a
number of natural settings. Crowdfunding, in particular, is a scenario in
which we would like to capitalise upon commonalities in donors’ charitable
preferences (Corazzini et al., 2015). Furthermore, crowdfunding projects (e.g.
building a well, funding a scholarship, etc.) often have provision points (see
e.g. (Agrawal et al., 2013, Chandra et al., 2016, Damle et al., 2019)), and it
can be critical for these targets to be met (for example, a project to raise
funds for a crowdfunding recipient to pay for a medical procedure would have
to raise a minimum amount of money to be successful, otherwise all donations
are effectively wasted).

Crowdfunding projects have been discussed in a broader context with various
economic factors and incentive issues presented (Agrawal et al., 2013).
Bagnoli and Lipman (1989) discuss additional fairness and economic
considerations for the related topic of the division of public goods. The
discrete model that we explore, where projects have finite caps, has potential
to coordinate donors and increase the effectiveness of a crowdfunding system.

##  3 Participatory Funding Coordination

A _Participatory Funding Coordination (PFC)_ setting is a tuple $(N,C,A,b,w)$
where $N$ is the set of agents/voters, $C$ is the set of projects (also
generally referred to as candidates). The function
$w:C\rightarrow\mathbb{R^{+}}$ specifies the cost $w(c)$ of each project $c\in
C$. The function $b:N\rightarrow\mathbb{R^{+}}$ specifies the budget $b_{i}$
of each agent $i\in C$. The budget $b_{i}$ can be viewed as the maximum amount
of money that agent $i$ is willing to spend. For any set of agents $S\subseteq
N$, we will denote $\sum_{i\in S}b_{i}$ by $b(S)$. The approval profile
$A=(A_{1},\ldots,A_{n})$ specifies for each agent, her set of acceptable
projects $A_{i}$. An _outcome_ is a pair $(S,x)$ where $S\subseteq C$ is the
set of funded projects and $x$ is a vector of payments that specify for each
$i\in N$, the payment $x_{i}$ that is charged from agent $i$. We will restrict
our attention to feasible outcomes in which $x_{i}\leq b_{i}$ for all $i\in N$
and only those projects get financial contributions that receive their
required amount. Also, note that the projects that are funded are only those
that receive the entirety of their price in payments from the agents. For any
given PFC instance, a mechanism $F$ returns an outcome. We will denote the set
of projects selected by $F$ as $F_{C}$ and the payments by $F_{x}$.111PFC can
also be viewed as a matching problem in which the money of agents is matched
to projects. For any outcome $(S,x)$, since $x_{i}\leq b_{i}$, the money
$b_{i}-x_{i}$ can either be kept by the agent $i$ or it can be viewed as going
into some common pool. The main focus of our problem is to fund a maximal set
of projects while satisfying participation constraints.

We suppose that an agent’s preferences are _approval-based_. For any set of
funded projects $S$, any agent $i$’s utility is

$u_{i}(S)=\sum_{c\in S\cap A_{i}}w(c).$

That is, an agent cares about how many dollars are _usefully_ used on his/her
approved projects. Our preferences domain is similar to the one used by Brandl
et al. (2020) who considered a continuous model in which projects do not have
target costs. In their model, agents also care about how much money is used
for their liked projects.

######  Example 1.

The following is an instance of a PFC problem with 5 agents and 6 projects.
The costs of the projects is stated next to the project name. The budget of
each agent is mentioned in front of the agent name. The plus sign indicates
the approval of an agent for a project.

|  | A (7) | B (6) | C (1) | D (1) | E (8) | F (7)
---|---|---|---|---|---|---|---
| Budget |  |  |  |  |  |
Agent 1 | 3 | + |  | + |  | + |
Agent 2 | 3 | + |  |  | + | + |
Agent 3 | 3 |  | + | + |  |  | +
Agent 4 | 2 |  | + |  | + |  | +
Agent 5 | 1 | + |  |  |  | + |

Table 1: Example of an PFC instance.

##  4 Axiom design

In this section, we design axioms for outcomes of the PFC setting. We consider
an outcome $(S,x)$. For any axiom $\mathbf{Ax}$ for outcomes, we say that a
mechanism satisfies $\mathbf{Ax}$ if it always returns an outcome that
satisfies $\mathbf{Ax}$.

We first present three axioms for our setting that are based on the principle
of participation:

  * •

Minimal Return (MR): each agent’s utility is at least much as the money put in
by the agent: $u_{i}(S)\geq x_{i}$. In other words, the societal decision is
as good for each agent $i$ as $i$’s best use of the money $x_{i}$ that she is
asked to contribute. We will use this as a minimal condition for all feasible
outcomes.222One can strengthen MR to a stronger version in which
$u_{i}(S,x)>x_{i}$ for each $i\in N$.

  * •

Implementability (IMP) : There exists a payment function $y:N\times
C\rightarrow\mathbb{R}^{+}\cup\\{0\\}$ such that $\sum_{c\in C}y(i,c)=x_{i}$
for all $i\in N$ and $\sum_{i\in N}y(i,c)\in\\{0,w(c)\\}$ and there exists no
$i\in N$ and $c\notin A_{i}$ such that $y(i,c)>0$. IMP captures the
requirement that an agent’s contribution should only be used on projects that
are approved by the agent.

  * •

Individual Rationality (IR): the utility of an agent is at least as much as an
agent can get by funding alone: $u_{i}(S)\geq\max_{S^{\prime}\subseteq
A_{i},w(S^{\prime})\leq b_{i}}(w(S^{\prime})).$ Note that IR is easily
achieved if the project costs are high enough: if for $i\in N$ and $c\in C$,
$w(c)>b_{i}$, then every outcome is IR.

We note that MR is specified with respect to the amount $x_{i}$ charged to the
agent. It can be viewed as a participation property: an agent would only want
to participate in the market if she gets at least as much utility as the money
she spent. We will show IMP is stronger than MR. IMP can also be viewed as a
fairness property: agents are made to coordinate but they only spend their
money on the projects they like.

######  Remark 1.

If there is an IMP outcome where a set of projects are funded, then there is
also an IMP outcome where any subset of these projects are funded. In order to
find an IMP outcome for any subset, simply take the original outcome and set
the payments of agents to projects that are being “de-funded” to zero.

Next, we present axioms that are based on the idea of efficiency.

  * •

Exhaustive (EXH): There exists no set $N^{\prime}\subseteq N$ and project
$c\in C\setminus S$ such that $c\in\cap_{i\in N^{\prime}}A_{i}\cap(C\setminus
A)$ such that $w(c)\leq\sum_{i\in N^{\prime}}(b_{i}-x_{i})$. In words, agents
in $N^{\prime}$ cannot pool in their unspent money and fund another project
liked by all of them.

  * •

Pareto optimality (PO)-X: An outcome $(S,x)$ is Pareto optimal within the set
of outcomes satisfying property X if there exists no $(S^{\prime},x^{\prime})$
satisfying X such that $u_{i}(S^{\prime})\geq u_{i}(S)$ for all $i\in N$ and
$u_{i}(S^{\prime})>u_{i}(S)$ for some $i\in N$. Note that Pareto optimality is
a property of the set of funded projects $S$ irrespective of the payments.

    * –

PO is Pareto optimal among the set of all outcomes.

    * –

PO-IMP: PO among the set of IMP outcomes.

    * –

PO-MR: PO among the set of MR outcomes.

  * •

Payment constrained Pareto optimality (PO-Pay): An outcome is PO-Pay if it is
not Pareto dominated by any outcome of at most the same price. Formally, there
exists no $(S^{\prime},x^{\prime})$ such that $\sum_{i\in
N}x_{i}^{\prime}\leq\sum_{i\in N}x_{i}$, $u_{i}(S^{\prime})\geq u_{i}(S)$ for
all $i\in N$ and $u_{i}(S^{\prime})>u_{i}(S)$ for some $i\in N$.

  * •

Weak Payment constrained Pareto optimality (weak PO-Pay): An outcome is weakly
PO-Pay if it is not Pareto dominated by any outcome of at most the same price.
Formally, there exists no $(S^{\prime},x^{\prime})$ such that
$x_{i}^{\prime}\leq x_{i}$ and $u_{i}(S^{\prime})\geq u_{i}(S)$ for all $i\in
N$ and $u_{i}(S^{\prime})>u_{i}(S)$ for some $i\in N$.

A concept that can be viewed in terms of participation, efficiency, and
fairness is the adaptation of the principle of core stability for our setting.

  * •

Core stability (CORE): There exists no set of agents who can pool in their
budget and each gets a strictly better outcome. In other words, an outcome
$(S)$ is CORE if for every subset of agents $N^{\prime}\subseteq N$, for every
subset of projects $C^{\prime}\subseteq C$ such that
$w(C^{\prime})\leq\sum_{i\in N^{\prime}}b_{i}$, the following holds for some
agent $i\in N^{\prime}$: $u_{i}(S)\geq w(C^{\prime}\cap A_{i}).$

We describe a basic fairness axiom for outcomes and rules based on the idea of
proportionality.

  * •

Proportionality (PROP): Suppose a set of agents $N^{\prime}\subseteq N$ _only_
approve of a set of projects $C^{\prime}\subseteq C$ such that $\sum_{i\in
N^{\prime}}b_{i}\geq w(C^{\prime})$. In that case, all the projects in
$C^{\prime}$ are selected.

Finally, we consider an axiom that is defined for mechanisms rather than
outcomes. We say that a mechanism satisfies strategyproofness if there exists
no instance under which some agent has an incentive to misreport her
preference relation.

We conclude this section with some remarks on computation. The following
proposition follows via a reduction from the Subset Sum problem.

######  Proposition 1.

Even for one agent, computing an IR, PO, PO-MR, or PO-IMP outcome if NP-hard.

###### Proof.

Consider the Subset Sum problem in which there is a set of items
$M=\\{1,\ldots,m\\}$ with corresponding weights $w_{1},\ldots,w_{m}$, and a
real value $W$. The problem is to find a subset $S$ with maximum weight
$\sum_{j\in S}w_{j}$ such that $\sum_{j\in S}w_{j}\leq W$. The problem is
well-known to be NP-hard. We reduce it our setting for a single agent by
taking an item for each project that our agent approves of, and choosing the
item weights to be the corresponding project costs. Then any set of projects
$S$ satisfies the axioms in the proposition if and only if the corresponding
set of items is the solution to the Subset Sum problem. ∎

Note that IMP is a property of an outcome not a set of projects. We say that a
set of projects $S$ is IMP if there exists a feasible vector of charges to
agents $x$ such that the outcome $(S,x)$ is IMP. The propoerty IMP can be
tested in polynomial time via reduction to network flows.

######  Proposition 2.

For a given set of projects $S$, checking whether there exists a vector of
charges $x$ such that $(S,x)$ is implementable can be done in polynomial time.

Similarly, we can also check whether a particular outcome $(S,x)$ is
implementable with a variation of the above linear program, where the upper
bound on the sum of payments for each agent is $x_{i}$ instead of $b_{i}$.

##  5 Axioms: Compatibility and Logical Relations

In this section, we study the compatibility and relations between the axioms
formulated.

######  Remark 2.

Note that IR and MR are incomparable. Any outcome in which an agent does not
pay any money trivially satisfies MR. However, it may not satisfy IR. On the
other hand, an IR outcome may not be MR. Consider the case in which an agent’s
utility is at least as high as by funding alone. However, the agent may have
been asked to pay more than the utility she gets which violates MR.

Next, we point out that that PO-Pay is equivalent to weak PO-Pay.

######  Proposition 3.

PO-Pay is equivalent to weak PO-Pay.

###### Proof.

Suppose an outcome $(S,x)$ is not weakly PO-Pay. Then, it is trivially not PO-
Pay. Now suppose $(S,x)$ is not PO-Pay. Then, there exists another outcome
$(S^{\prime},x^{\prime})$ such that $\sum_{i\in N}x_{i}^{\prime}\leq\sum_{i\in
N}x_{i}$, $u_{i}(S^{\prime})\geq u_{i}(S)$ for all $i\in N$ and
$u_{i}(S^{\prime})>u_{i}(S)$ for some $i\in N$. Note that $S^{\prime}$ can be
funded with total amount $\sum_{i\in N}x_{i}^{\prime}$ irrespective of who
paid what. So $S^{\prime}$ is still affordable if $x_{i}^{\prime}\leq x_{i}$.
∎

The next proposition establishes further logical relations between the axioms.

######  Proposition 4.

The following logical relations hold between the properties.

  1. 1.

IMP implies MR.

  2. 2.

PO implies PO-Pay.

  3. 3.

PO-$X$ implies PO-$Y$ if $Y$ implies $X$.

  4. 4.

PO-IMP implies EXH.

  5. 5.

PO-IR implies EXH.

  6. 6.

CORE implies IR.

  7. 7.

The combination of PO-IMP and IMP imply PROP.

Next, we show that MR is compatible with PO-Pay.

######  Proposition 5.

Suppose an outcome is MR and there is no other MR outcome that Pareto
dominates it. Then, it is PO-Pay.

###### Proof.

Suppose the outcome $(S,x)$ is MR and PO constrained to MR. We claim that
$(S,x)$ is PO-Pay. Suppose it is not PO-Pay. Then there exists another outcome
$(S^{\prime},x^{\prime})$ such that $\sum_{i\in N}x_{i}^{\prime}\leq\sum_{i\in
N}x_{i}$, $u_{i}(S^{\prime})\geq u_{i}(S)$ for all $i\in N$ and
$u_{i}(S^{\prime})>u_{i}(S)$ for some $i\in N$. Note that $S^{\prime}$ is
afforadable with total amount $\sum_{i\in N}x_{i}^{\prime}$ irrespective of
who paid what. So $S^{\prime}$ is still affordable if $x_{i}^{\prime}\leq
x_{i}$. Therefore, we can assume that $x_{i}^{\prime}\leq x_{i}$ for all $i\in
N$. Note that since $S^{\prime}$ Pareto dominates $S$ and since $(S,x)$ is MR,
$u_{i}(S^{\prime})\geq u_{i}(S)\geq x_{i}\geq x_{i}^{\prime}$ for all $i\in
N$. Hence $(S^{\prime},x^{\prime})$ also satisfies MR. Since
$(S^{\prime},x^{\prime})$ is MR and since $S$ Pareto dominates $S^{\prime}$,
it contradicts the fact that $(S,x)$ PO constrained to MR. ∎

######  Proposition 6.

There always exists an outcome that satisfies IMP, IR, PO-IMP and hence also
MR and EXH.

###### Proof.

Existence of an outcome that satisfies IMP, IR, PO-IMP: For each $i\in N$
compute $(S_{i},y_{i})$ that is an IR outcome. This can be computed by finding
a maximum total weight set of projects that has weight at most $b_{i}$. Then
consider the outcome $(\bigcup_{i\in N}S_{i},(y_{1},\ldots,y_{n}))$. In such
an outcome, we also keep track of which agent contributed to which project.
Note that if $c\in S_{i}$, then $i$ contributed $w(c)$ to that project. Note
that $w(\bigcup_{i\in N}S_{i})\geq\sum_{i\in N}y_{i}$. If $w(\bigcup_{i\in
N}S_{i})>\sum_{i\in N}y_{i}$, we need to return $w(\bigcup_{i\in
N}S_{i})-\sum_{i\in N}y_{i}$, back to the agents to ensure that no more money
is charged than needed to pay for $\bigcup_{i\in N}S_{i}$. We return the money
as follows. Recall that we know the amount paid by each agent to each project,
i.e., agent $i$ paid $w(c)$ to project $c$ if and only if $c\in S_{i}$. Some
projects may have received more money than needed. For each project $c$’s
surplus, we uniformly allocate it among the agents who paid for it. Suppose
the outcome satisfying IMP, IR and EXH does not satisfy PO-IMP. Then there
exists another outcome that satisfies IMP that Pareto dominates the outcome.
Such a Pareto improvement still satisfies IR because the utility of each agent
is at least as high. ∎

Note that PO-Pay and IMP are both satisfied by an empty outcome with zero
charges. PO-IMP and IMP are easily satisfied by computing a PO outcome from
the set of IMP outcomes. PO-Pay and PO-IMP are easily satisfied by computing a
PO outcome which may not necessarily satisfy IMP.

######  Proposition 7.

There always exists an outcome that satisfies MR, IR, PO-MR and hence also
EXH.

###### Proof.

Existence of an outcome that satisfies MR, IR, PO-MR: From the proof of part
(i), we know that an IMP and IR outcome always exists. Also, from Proposition
4 we know that every IMP outcome is MR, so there always exists an MR and IR
outcome. Now suppose the outcome satisfying MR and IR does not satisfy PO-MR.
Then there exists another outcome satisfying MR that Pareto dominates the
original outcome, which is still IR. There cannot exist an infinite number of
Pareto improvements because the budgets of the agents are finite. Hence we can
reach a PO-MR outcome that is also IR and MR. ∎

We note that if no agent can individually fund a project, then every outcome
is IR. In crowdfunding settings in which projects have large costs, the IR
requirement is often easily satisfied.

##  6 Aggregation Rules

In this section, we take a direct welfarist view to formalize rules that
maximize some notion of welfare. We consider three notions of welfare:
utilitarian, egalitarian, and Nash welfare; and we define the following rules.

  * •

UTIL: define the utilitarian welfare derived from an outcome $(S,x)$ as
$\sum_{i\in N}u_{i}(S).$ Then, UTIL returns an outcome that maximises the
utilitarian welfare.

  * •

EGAL: given some output $(S,x)$, write the sequence of agents’ utilities from
that outcome as $u(S)=(u_{i}(S))_{i\in N}$, where $u$ is sorted in non-
decreasing order. Then, EGAL returns an outcome $(S,x)$ such that $u(S)$ is
lexicographically maximal among the outcomes.

  * •

NASH: maximises the Nash welfare derived from an output $(S,x)$, i.e.
$\prod_{i\in N}\left(u_{i}(S)\right).$

######  Proposition 8.

UTIL, EGAL, and NASH satisfy PO and hence PO-MR, PO-IMP, PO-Pay, and EXH.

One notes that the rules UTIL, EGAL, and NASH do not satisfy minimal
guarantees such as MR. The reason is that an agent may donate her budget to a
widely approved project even though she may not approve any of such projects.
Given that the existing aggregation rules do not provide us with guarantees
that the outcomes they produce will satisfy our axioms, we can instead define
rules such that optimize social welfare within certain subsets of feasible
outcomes. For a property X, we can define UTIL-X, EGAL-X, and NASH-X as rules
that maximise the utilitarian, egalitarian and Nash welfare respectively among
only those outcomes that satisfy property X. Next, we analyse the properties
satisfied by rules EGAL/UTIL/NASH constrained to the set of MR or IMP
outcomes. In the continuous model introduced by Brandl et al. (2020), there is
no need to consider the rule NASH-IMP, as the NASH rule in the case where
projects can be funded to an arbitrary degree (given there is sufficient
budget) already satisfies IMP.

Before we study the axiomatic properties, we note that most meaningful axioms
and rules are NP-hard to achieve or compute. The following proposition follows
from Proposition 1.

######  Proposition 9.

Even for one agent, computing an UTIL, UTIL-MR, UTIL-MR, EGAL, EGAL-MR, EGAL-
IMP, NASH, NASH-MR, NASH-IMP outcome is NP-hard.

Similarly, the following proposition follows from Proposition 5.

######  Proposition 10.

UTIL-MR, EGAL-MR, and NASH-MR satisfy PO-Pay.

From Proposition 5, it follows that UTIL-MR, EGAL-MR, and NASH-MR satisfy PO-
Pay. In contrast, we show that UTIL-IMP, EGAL-IMP, and NASH-IMP do not satisfy
PO-Pay. In order to show this, we prove that it is possible in some instances
for the set of jointly IMP and PO-IMP outcomes to be disjoint from the set of
PO-Pay outcomes.

######  Proposition 11.

UTIL-IMP, EGAL-IMP and NASH-IMP do not satisfy PO-Pay. In fact it is possible
that no IMP and PO-IMP outcome satisfies PO-Pay.

###### Proof.

Consider the following instance in Table 2.

|  | A (7) | B (4) | C (3) | D (7) | E (7)
---|---|---|---|---|---|---
| Budget |  |  |  |  |
Agent 1 | 4 |  | + |  |  | +
Agent 2 | 1 | + |  |  |  | +
Agent 3 | 1 | + |  |  |  | +
Agent 4 | 5 | + |  |  | + |
Agent 5 | 3 |  |  | + | + |
Table 2: Example instance for proof of UTIL/EGAL/NASH-IMP not satisfying PO-
Pay.

######  Claim.

Observe that no implementable outcome can fund project $E$ since it is too
expensive to be funded solely by its supporters.

######  Claim.

Any implementable outcome funds a subset of the following project sets:
$\\{A,B,C\\},\\{B,D\\}$. Note that for an implementable outcome, if $D$ is
funded, then only $B$ can also be funded (there is not enough money for agents
who approve of $A$ or $C$ to fund these projects after funding $D$).

| A,B,C | B,D | D,E (not IMP)
---|---|---|---
Agent 1 | 4 | 4 | 7
Agent 2 | 7 | 0 | 7
Agent 3 | 7 | 0 | 7
Agent 4 | 7 | 7 | 7
Agent 5 | 3 | 7 | 7
Table 3: Utilities provided to each agent by outcomes that fund the project
sets $\\{A,B,C\\},\\{B,D\\}$ and $\\{D,E\\}$.

Note that when we are looking for the optimal outcome under a certain rule, we
can ignore those project sets that are subsets of other project sets. Then,
from Table 3, we see that the unique UTIL-IMP, EGAL-IMP and NASH-IMP outcome
is the outcome that funds $\\{A,B,C\\}$ where each agent sends all their money
to the only project of those three that they approve of. But clearly, this
outcome is Pareto dominated by any outcome that funds $\\{D,E\\}$, which has
the same total cost. Thus we have shown that UTIL-IMP, EGAL-IMP and NASH-IMP
do not satisfy PO-Pay in general. In fact the set of IMP and PO-IMP outcomes
can be disjoint from the set of PO-Pay outcomes. ∎

The most striking aspect of Proposition 11 is that in the continuous domain
without project costs, NASH-IMP is equivalent to NASH and the rule satisfies
Pareto optimality and hence PO-Pay. In our context, NASH-IMP fails to satisfy
PO-Pay.

We also considered the issue of strategyproofness and found examples that show
that none of the UTIL/EGAL/NASH rules are strategyproof whether they are
unconstrained or constrained to MR or IMP outcomes. In contrast, there are
several natural rules such as UTIL that are strategyproof in the continuous
setting as well in the multi-winner voting setting.

######  Proposition 12.

UTIL, UTIL-MR, UTIL-IMP, NASH, NASH-MR and NASH-IMP are not strategyproof.

###### Proof.

Consider the instance given in Table 16. Note that we only include project $Z$
for the purpose of making the NASH welfare of outcomes non-zero. Now, observe
that it is impossible to fund all three projects, so our possible candidate
project sets to be funded by the above rules are those where two projects get
funded.

|  | X (10) | Y (4) | Z (9)
---|---|---|---|---
| Budget |  |  |
Agent 1 | 8 |  | + | +
Agent 2 | 1 |  | + | +
Agent 3 | 10 | + | + | +
Table 4: Example instance where rules are not strategyproof. | $\\{X,Y\\}$ | $\\{X,Z\\}$ | $\\{Y,Z\\}$
---|---|---|---
Utilitarian Welfare | 22 | 37 | 39
Nash Welfare | 224 | 1539 | 2197
Table 5: Utilitarian and Nash welfares of certain project sets to be funded.

We check that there is an implementable outcome that funds $\\{Y,Z\\}$, and
find that the outcome where Agents 1 and 2 pay for $Z$ and Agent 3 pays for
$Y$ is implementable. Hence, $\\{Y,Z\\}$ is the result of UTIL, UTIL-MR, UTIL-
IMP, NASH, NASH-MR, NASH-IMP. Note that the utility for Agent 3 is 13.

Now, suppose Agent 3 were to misrepresent her preferences as in Table 18.
Again, according to this new (perceived) instance, it is impossible for all
projects to be funded, so in Table 19 we check the welfares produced by
funding any two of the projects.

|  | X (10) | Y (4) | Z (9)
---|---|---|---|---
| Budget |  |  |
Agent 1 | 8 |  | + | +
Agent 2 | 1 |  | + | +
Agent 3 | 10 | + |  | +
Table 6: Instance where Agent 3 is misrepresenting her preferences. | $\\{X,Y\\}$ | $\\{X,Z\\}$ | $\\{Y,Z\\}$
---|---|---|---
UTIL | 18 | 37 | 35
NASH | 160 | 1539 | 1521
Table 7: Perceived welfares of certain project sets to be funded if Agent 3
misrepresents her preferences.

Since $\\{X,Z\\}$ can be funded by an implementable outcome where Agents 1 and
2 paying for $Z$ and Agent 3 paying for $X$, $\\{X,Z\\}$ is the result of
UTIL, UTIL-MR, UTIL-IMP, NASH, NASH-MR, NASH-IMP. With this outcome, Agent 3
sees her utility rise to 19.

Then, by misrepresenting her preferences, Agent 3 can cause the choice of the
aforementioned rules to change from funding $\\{Y,Z\\}$ to funding
$\\{X,Z\\}$, hence increasing her own utility. Therefore, UTIL, UTIL-MR, UTIL-
IMP, NASH, NASH-MR and NASH-IMP are not strategyproof.

∎

Similarly, the following also holds.

######  Proposition 13.

EGAL, EGAL-MR and EGAL-IMP are not strategyproof.

Table 8 shows the axioms that are satisfied by restricting the aggregation
rules to optimising within the space of MR or IMP outcomes.

| UTIL-MR | EGAL-MR | NASH-MR | UTIL-IMP | EGAL-IMP | NASH-IMP |
---|---|---|---|---|---|---|---
MR | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
IMP | – | – | – | ✓ | ✓ | ✓ |
PROP | – | – | – | ✓ | ✓ | ✓ |
IR | – | – | – | – | – | – |
PO | – | – | – | – | – | – |
PO-MR | ✓ | ✓ | ✓ | – | – | – |
PO-IMP | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
PO-Pay | ✓ | ✓ | ✓ | – | – | – |
EXH | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
CORE | – | – | – | – | – | – |
SP | – | – | – | – | – | – |

Table 8: Properties satisfied by UTIL-MR, EGAL-MR, NASH-MR, UTIL-IMP, EGAL-IMP
and NASH-IMP.

##  7 Experiment

In addition to the axiomatic study of the welfare-based rules, we undertake a
simulation-based experiment to gauge the performance of different rules with
respect to utilitarian and egalitarian welfare. Our study shows the impact of
fairness axioms such as MR and IMP on welfare.

We generate random samples of profiles in order to simulate two potential
real-world applications of PFC.

  1. 1.

Share-house setting: In this example, we can imagine a group of house-mates
pooling their resources to fund communal items for their house. We operate
under the following assumptions:

     * •

Number of agents from 3-6: this represents a reasonable number of house-mates
in a share-house.

     * •

Number of projects from 5-12: projects may include buying items such as
tables, chairs, sofas, televisions, lights, kitchen appliances, washing
machines, dryers, etc.

     * •

Agent budgets from 300-600 and project costs from 50-1000. We base these costs
on typical rent and furniture costs in Australia as well as costs of the above
items in first and second-hand retailers. We expect that each agent brings
some money to the communal budget, and would spend around one or two weeks’
worth of rent on one-time communal expenses.

  2. 2.

Crowdfunding setting: In this example, we imagine a relatively small number of
expensive projects to be funded, and a large number of philanthropic donors,
and make the following assumptions.

     * •

Number of agents from 20-50: A review of crowdfunding websites such as
Kickstarter and GoFundMe shows that the most promoted projects are typically
funded by thousands of donors, and smaller projects can attract tens of
donors. For the purposes of our simulation, we use between 20-50 donors, which
is still relatively large to the number of available projects.

     * •

Number of projects from 3-8: In crowdfunding, there are far more projects
available than a donor actually sees. However, we can estimate that in a
browsing session, a donor might view the top 3-8 promoted projects.

     * •

Agent budgets from 0-400 and project costs from 1000-10000: Projects in real-
life crowdfunding can have vastly varying costs. For our simulation, we want
for the agents with all their money combined to be able to afford some, but
not all of the available projects in order to create instances that are not
trivially resolved by funding all or none of the projects.

Imposing MR on a rule seems to have a significant impact on both utilitarian
and egalitarian welfare on average. Of course, since IMP implies MR, we expect
that imposing IMP as a constraint will have an even greater cost on welfare,
but from our experiment, this cost is a relatively small increase on the the
cost of imposing MR. It is worth noting that in worst-case scenarios, it is
always possible that there are no non-trivial outcomes that satisfy the
constraints, and so there is a risk that a rule subject to a constraint could
produce an outcome that gives all agents zero utility.

When considering average performance, rules are more resilient to the
imposition of fairness constraints for instances that simulate crowdfunding
scenarios compared to share-house scenarios. When the number of agents is
large and the number of projects is small, and project costs are large
compared to agent budgets, it seems to be easier to achieve fairness
properties.

We typically expect the NASH rule to be a compromise between UTIL and EGAL.
This manifests in the results, where the performance losses for NASH with
respect to utilitarian welfare are considerably less than those for EGAL.
Likewise, NASH loses considerably less with respect to egalitarian welfare
than UTIL.

##  8 Conclusions

We proposed a concrete model for coordinating funding for projects. A formal
approach is important to understand the fairness, participation, and
efficiency requirements a system designer may pursue. We present a detailed
taxonomy of such requirements and clarify their properties and relations. We
also analyse natural welfarist rules both axiomatically and experimentally.
Our model is not just a rich setting to study collective decision making. We
feel that the approaches considered in the paper go beyond academic study and
can be incorporated in portals that aggregate funding for charitable projects.
We envisage future work on online versions of the problem.

In practical applications of PFC, it is important to balance welfare demands
with fairness conditions. Our experiment investigated the cost of fairness
when imposing MR or IMP on UTIL, EGAL and NASH rules over instances that model
crowdfunding and share-house scenarios. We find that imposing MR alone
significantly reduces welfare on average, but imposing IMP as well produces a
relatively small additional cost on welfare. The costs of imposing any
fairness condition are much more pronounced on instances that model a share-
house setting than a crowdfunding setting, suggesting that for a large number
of agents and large project costs, fairness conditions are more easily met.

## References

  * Agrawal et al. (2013) A. Agrawal, C. Catalini, and A. Goldfarb.  Some Simple Economics of Crowdfunding.  In _Innovation Policy and the Economy, Volume 14_ , NBER Chapters, pages 63–97. National Bureau of Economic Research, Inc, June 2013.
  * Aziz and Shah (2020) H. Aziz and N. Shah.  Participatory budgeting: Models and approaches.  In T. Rudas and P. Gábor, editors, _Pathways between Social Science and Computational Social Science: Theories, Methods and Interpretations_. Springer, 2020.
  * Aziz et al. (2017) H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh.  Justified representation in approval-based committee voting.  _Social Choice and Welfare_ , pages 461–485, 2017.
  * Aziz et al. (2018) H. Aziz, B. E. Lee, and N. Talmon.  Proportionally representative participatory budgeting: Axioms and algorithms.  In _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018_ , pages 23–31, 2018.
  * Bagnoli and Lipman (1989) M. Bagnoli and B. L. Lipman.  Provision of Public Goods: Fully Implementing the Core through Private Contributions.  _The Review of Economic Studies_ , 56(4):583–601, 10 1989.
  * Brandl et al. (2019) F. Brandl, F. Brandt, D. Peters, C. Stricker, and W. Suksompong.  Donor coordination: Collective distribution of individual contributions.  In _GAIW (Games, Agents and Incentives Workshops)_ , 2019.
  * Brandl et al. (2020) F. Brandl, F. Brandt, D. Peters, C. Stricker, and W. Suksompong.  Funding public projects: A case for the nash product rule.  Working paper, 2020.
  * Buterin et al. (2019) V. Buterin, Z. Hitzig, and E. G. Weyl.  A Flexible Design for Funding Public Goods.  _Management Science_ , 65(11):5171–5187, 2019\.
  * Chandra et al. (2016) P. Chandra, S. Gujar, and Y. Narahari.  Crowdfunding public projects with provision point: A prediction market approach.  In _Proc. of the 22nd European Conference on Artificial Intelligence (ECAI)_ , pages 778–786, 2016.
  * Corazzini et al. (2015) L. Corazzini, C. Cotton, and P. Valbonesi.  Donor coordination in project funding: Evidence from a threshold public goods experiment.  _Journal of Public Economics_ , 128(1):16–29, 2015.
  * Damle et al. (2019) S. Damle, M. Hussain Moti, P. Chandra, and S. Gujar.  Civic crowdfunding for agents with negative valuations and agents with asymmetric beliefs.  In _Proc. of the 28th IJCAI_ , pages 208–214, 2019.
  * Elkind et al. (2017) E. Elkind, P. Faliszewski, P. Skowron, and A. Slinko.  Properties of multiwinner voting rules.  _Social Choice and Welfare_ , 2017.
  * Fain et al. (2016) B. Fain, A. Goel, and K. Munagala.  The core of the participatory budgeting problem.  In _Proceedings of the 12th International Conference on Web and Internet Economics (WINE ’16)_ , pages 384–399, 2016.
  * Fluschnik et al. (2019) T. Fluschnik, P. Skowron, M. Triphaus, and K. Wilker.  Fair knapsack.  In _Proc. of the 33rd AAAI Conference_ , 2019.
  * Goel et al. (2019) A. Goel, Anilesh K. K., S. Sakshuwong, and T. Aitamurto.  Knapsack voting for participatory budgeting.  _ACM Transactions on Economics and Computation (TEAC)_ , 7(2):8:1–8:27, 2019.  ISSN 2167-8375.
  * Lackner and Skowron (2019) M. Lackner and P. Skowron.  A quantitative analysis of multi-winner rules.  In _Proc. of the 28th IJCAI_ , pages 407–413, 2019.
  * MacAskill (2015) W. MacAskill.  _Doing Good Better: How Effective Altruism Can Help You Make a Difference_.  Avery, 2015.
  * MacAskill (2017) William MacAskill.  Effective altruism: Introduction.  _Essays in Philosophy_ , 18(1), 2017.
  * Peters (2019) D. Peters.  _Economic Design for Effective Altruism_ , pages 381–388.  2019\.  URL https://app.dimensions.ai/details/publication/pub.1122621382.
  * Talmon and Faliszewski (2019) N. Talmon and P. Faliszewski.  A framework for approval-based budgeting methods.  In _Proc. of the 33rd AAAI Conference_ , 2019.

##  Appendix 0.A Remaining Proofs

Proof of Proposition 1

###### Proof.

Consider the Subset Sum problem in which there is a set of items
$M=\\{1,\ldots,m\\}$ with corresponding weights $w_{1},\ldots,w_{m}$, and a
real values $W$. The problem is a subset $S$ with maximum weight $\sum_{j\in
S}w_{j}$ such that $\sum_{j\in S}w_{j}\leq W$. The problem is well-known to be
NP-hard. We reduce it our setting by taking a project for each corresponding
item and project weight for each item weight. Then any set of projects $S$
satisfies the axioms in the proposition if and only if the corresponding set
of items $S$ is the solution to the Subset problem. ∎

Proof of Proposition 2

###### Proof.

In order to check whether a given set of projects $W$ is implementable, we
just need to check whether the following linear program has a feasible
solution or not. The following can also be checked via network flows.

$\displaystyle x_{i,j}=0$ $\displaystyle\text{ for all }i\in N,j\in[m]\text{
s.t. }p_{j}\notin A_{i}$ $\displaystyle\sum_{i\in N}x_{i,j}=w(p_{j})$
$\displaystyle\text{ for all }p_{j}\in W$ $\displaystyle\sum_{i\in
N}x_{i,j}=0$ $\displaystyle\text{ for all }p_{j}\notin W$
$\displaystyle\sum_{j\in C}x_{i,j}\leq b_{i}$ $\displaystyle\text{ for all
}i\in N$ $\displaystyle x_{i,j}\geq 0$ $\displaystyle\text{ for all }i\in
N,j\in[m]$

∎

Proof of Proposition 3

###### Proof.

Suppose an outcome $(S,x)$ is not weakly PO-pay. Then, it is trivially not PO-
pay. Now suppose $(S,x)$ is not PO-pay. Then, there exists another outcome
$(S^{\prime},x^{\prime})$ such that $\sum_{i\in N}x_{i}^{\prime}\leq\sum_{i\in
N}x_{i}$, $u_{i}(S^{\prime})\geq u_{i}(S)$ for all $i\in N$ and
$u_{i}(S^{\prime})>u_{i}(S)$ for some $i\in N$. Note that the $S^{\prime}$ is
afforadable with total amount $\sum_{i\in N}x_{i}^{\prime}$ irrespective of
who paid what. So $S^{\prime}$ is still affordable if $x_{i}^{\prime}\leq
x_{i}$. ∎

Proof of Proposition 4

###### Proof.

We distinguish between the cases.

  1. 1.

IMP implies MR: Suppose an outcome $(S,x)$ satisfies IMP. Then there exists a
set of vectors $\\{\bm{y}_{c}\\}_{c\in S}$ where $\bm{y}_{c}$ is a vector of
payments from each agent to project $c$ such that $\sum_{c\in S}\bm{y}_{c}=x$
and $y_{c,i}=0$ if $c\notin A_{i}$. Examining any row $i$ of the vector $x$,
which denotes the money charged from agent $i$, we see that $x_{i}=\sum_{c\in
S}\bm{y}_{c,i}$. But since $y_{c,i}=0$ if $c\notin A_{i}$, we have
$x_{i}=\sum_{c\in S\cap A_{i}}y_{ij}$. Now,

$u_{i}(S)=\sum_{c\in S\cap A_{i}}w(c)=\sum_{c\in S\cap A_{i}}\sum_{j\in
N}y_{c,j}\geq\sum_{c\in S\cap A_{i}}y_{c,i}=x_{i}.$

Hence, $(S,x)$ satisfies MR.

  2. 2.

PO implies PO-Pay: Suppose an outcome is PO. Then, it is not Pareto dominated
by any other outcome. Hence, it is not Pareto dominated by any outcome of
lesser total cost, and so it is PO-Pay.

  3. 3.

PO-$X$ implies PO-$Y$ if $Y$ implies $X$: Suppose some condition $Y$ implies
another condition $X$. Now, suppose some outcome $(S,x)$ is PO-$X$. Then,
$(S,x)$ is not Pareto dominated by any outcome that satisfies $X$. Since $Y$
implies $X$, the set of all outcomes satisfying $Y$ is a subset of the set of
all outcomes satisfying $Y$. Thus, $(S,x)$ is not Pareto dominated by any
outcome that satisfies $Y$, and so $(S,x)$ is PO-$Y$.

  4. 4.

PO-IMP implies EXH: Suppose for a contradiction that $(S,x)$ is an outcome
that satisfies PO-IMP but not EXH. Let an implementable payment function for
this outcome be $y:N\times C\rightarrow\mathbb{R}^{+}\cup\\{0\\}$. Since this
outcome is not exhaustive, there is a set of agents $N^{\prime}$ who can pool
together their unspent money to fund another commonly-liked project
$c^{\prime}$. We can construct a new outcome
$(S\cup\\{c^{\prime}\\},x^{\prime})$ with a payment function
$y^{\prime}:N\times C\rightarrow\mathbb{R}^{+}\cup\\{0\\}$ such that for all
agents $i\in N$ and projects $c\in S$, $y^{\prime}(i,c)=y(i,c)$, and for all
agents $j\in N^{\prime}$, $y^{\prime}(j,c^{\prime})=\delta_{j}$, where
$\delta_{j}$ is the contribution of each agent $j\in N^{\prime}$ to the new
project $c^{\prime}$. Note that $(S\cup\\{c^{\prime}\\},x^{\prime})$ is
implementable since its payment function has agents only funding projects they
approve of. Now, $(S\cup\\{c^{\prime}\\},x^{\prime})$ Pareto dominates $(S,x)$
which is a contradiction since $(S,x)$ is PO-IMP. Therefore, any PO-IMP
outcome must satisfy EXH.

  5. 5.

PO-IR implies EXH: Suppose for a contradiction that $(S,\textbf{x})$ is an
outcome that satisfies PO-IR but not EXH. Then there is a set of agents
$N^{\prime}$ who can pool together their unspent money to fund another
commonly-liked project $c^{\prime}$. Since no agent’s utility decreases by
funding this project, a new outcome
$(S\cup\\{c^{\prime}\\},\textbf{x}^{\prime})$ is still IR, where
$\textbf{x}^{\prime}$ is any valid vector of payments. Also note that this
$(S\cup\\{c^{\prime}\\},\textbf{x}^{\prime})$ Pareto dominates
$(S,\textbf{x})$ since no agent’s utility decreases and at least one agent’s
utility increases. This is a contradiction as $(S,\textbf{x})$ is PO-IR by our
initial assumption. Hence, any PO-IR outcome is EXH.

  6. 6.

Suppose an outcome $(S,x)$ is CORE. Then for every subset of agents
$N^{\prime}\subseteq N$, for every subset of projects $C^{\prime}\subseteq C$
such that $w(C^{\prime})\leq\sum_{i\in N^{\prime}}b_{i}$, for some agent $i\in
N^{\prime}$ $u_{i}(S)\geq w(C^{\prime}\cap A_{i}).$ Now consider the case
where $|N^{\prime}|=1$, i.e. $N^{\prime}$ is a subset of one agent. We now
have that for every agent $i$, for all $C^{\prime}\subseteq C$ such that
$w(C^{\prime})\leq b_{i}$, $u_{i}(S)\geq w(C^{\prime}\cap A_{i}).$
Equivalently, for every agent $i$, $u_{i}(S)\geq\max_{S^{\prime}\subseteq
A_{i},w(S^{\prime})\leq b_{i}}(w(S^{\prime}))$ and so $(S,x)$ is IR.

  7. 7.

The combination of PO-IMP and IMP imply PROP. Suppose an outcome does not
satisfy PROP. Then this means that there is set of agents $N^{\prime}\subseteq
N$ _only_ approve of a set of projects $C^{\prime}\subseteq C$ such that
$\sum_{i\in N^{\prime}}b_{i}\geq w(C^{\prime})$ but not all projects in
$C^{\prime}$ are selected. Then one of the two cases occurs: (1) either the
money of agents in $N^{\prime}$ is used for projects not approved by them
which violates IMP (2) the agents in $N^{\prime}$ can pool in unspent money to
fund an additional project in $C^{\prime}$ that is not funded, which means
that the outcome is not PO-IMP.

∎

Proof of Proposition 13

###### Proof.

Consider the instance given in Table 20. Due the total budget constraint, at
most two of the projects can be funded, so we check the egalitarian welfare
derived by funding any two projects in Table 21.

|  | X (3) | Y (2) | Z (1)
---|---|---|---|---
| Budget |  |  |
Agent 1 | 1 |  | + | +
Agent 2 | 1 |  | + | +
Agent 3 | 3 | + | + |
Table 9: Example instance where EGAL rules are not strategyproof. | $\\{X,Y\\}$ | $\\{X,Z\\}$ | $\\{Y,Z\\}$
---|---|---|---
Egalitarian Welfare | (2, 2, 5) | (1, 1, 3) | (2, 3, 3)
Table 10: Egalitarian welfares of certain project sets to be funded.

Observe that it is possible for an implementable outcome to fund $\\{Y,Z\\}$
by having Agents 1 and 2 pay for them, and so $\\{Y,Z\\}$ is funded by each of
the above rules. Then, the utility for Agent 3 is 2.

Now, suppose Agent 3 misrepresents her preferences to suppress the fact that
she approves of project $Y$. The new perceived instance is shown in Table 22
and again, we compute the egalitarian welfare produced by funding any two
projects in Table 23.

|  | X (3) | Y (2) | Z (1)
---|---|---|---|---
| Budget |  |  |
Agent 1 | 1 |  | + | +
Agent 2 | 1 |  | + | +
Agent 3 | 3 | + |  |
Table 11: Example instance where rules are not strategyproof. | $\\{X,Y\\}$ | $\\{X,Z\\}$ | $\\{Y,Z\\}$
---|---|---|---
Egalitarian Welfare | (2, 2, 3) | (1, 1, 3) | (0, 3, 3)
Table 12: Egalitarian welfares of certain project sets to be funded.

Note that there is an implementable outcome that funds $\\{X,Y\\}$, where
Agent 3 pays for $X$ and Agents 1 and 2 pay for $Y$. Hence, $\\{X,Y\\}$ is
funded by each of the rules. The new utility for Agent 3 is 3.

Thus, by misrepresenting her preferences, Agent 3 is able to increase the
utility she receives when egalitarian rules are used. Therefore, EGAL, EGAL-MR
and EGAL-IMP are not strategyproof.

∎

##  Appendix 0.B Experiments

The results of the experiments are depicted in Figures 8, 8, 8, 8, 8, 8, 8,
and 8.

Figure 1: Average performance of rules with respect to utilitarian welfare in
share-house simulations as a percentage of the maximum achievable utilitarian
welfare. Figure 2: Average performance of rules with respect to utilitarian
welfare in crowdfunding simulations as a percentage of the maximum achievable
utilitarian welfare.

Figure 3: Worst-case performance of rules with respect to utilitarian welfare
in share-house simulations as a percentage of the maximum achievable
utilitarian welfare. Figure 4: Worst-case performance of rules with respect to
utilitarian welfare in crowdfunding simulations as a percentage of the maximum
achievable utilitarian welfare.

Figure 5: Average performance of rules with respect to egalitarian welfare in
share-house simulations as a percentage of the maximum achievable egalitarian
welfare. Figure 6: Average performance of rules with respect to egalitarian
welfare in crowdfunding simulations as a percentage of the maximum achievable
egalitarian welfare.

Figure 7: Worst-case performance of rules with respect to egalitarian welfare
in share-house simulations as a percentage of the maximum achievable
egalitarian welfare. Figure 8: Worst-case performance of rules with respect to
egalitarian welfare in crowdfunding simulations as a percentage of the maximum
achievable egalitarian welfare.

##  Appendix 0.C Additional Propositions

######  Proposition 14.

UTIL, EGAL and NASH satisfy PO.

###### Proof.

Suppose there was an outcome that was Pareto dominant over the outcome
returned by any of these rules. Then, it would also have a strictly greater
utilitarian/egalitarian/Nash welfare to this outcome, which is a
contradiction. ∎

######  Proposition 15.

UTIL and NASH do not satisfy MR (or IMP by corollary) or IR (or CORE by
corollary).

###### Proof.

For the profile in Table 14, UTIL and NASH would require that only project $X$
is funded by using all of both agents’ money. But then, Agent 2 could have
left the mechanism and derived better utility on her own (IR). Also, her
return is less than her contribution, so UTIL does not satisfy MR.

|  | X (20) | Y (10)
---|---|---|---
| Budget |  |
Agent 1 | 10 | + |
Agent 2 | 10 |  | +
Table 13: Example profile where UTIL and NASH outcomes do not satisfy MR.

∎

######  Proposition 16.

EGAL does not satisfy MR (or IMP by corollary).

###### Proof.

For the profile in Table 14, the maximally egalitarian output is to implement
both projects. However, in this case, Agent 1 is charged $25$ but receives a
utility of 20, so this outcome does not satisfy MR.

|  | X (20) | Y (10)
---|---|---|---
| Budget |  |
Agent 1 | 25 | + |
Agent 2 | 5 |  | +
Table 14: Example profile where EGAL outcomes do not satisfy MR.

∎

######  Proposition 17.

EGAL does not satisfy IR.

###### Proof.

In the below example, given the total budget, the choice is to implement
either $X$ or $Y$ or neither. The egalitarian outcome with be to implement
$Y$, but then, by leaving the system, Agent 1 could pay for $X$ herself and
get a better outcome.

|  | X (20) | Y (10)
---|---|---|---
| Budget |  |
Agent 1 | 20 | + | +
Agent 2 | 5 |  | +

∎

######  Proposition 18.

UTIL-IMP, EGAL-IMP and NASH-IMP do not satisfy PO-MR.

###### Proof.

In Table 15, the only implementable outcomes are those in which no projects
are funded or Agents 1 and 2 pay for project $X$. But the outcome where all
three projects are funded by all agents spending all of their money satisfies
MR and Pareto dominates any of the implementable outcomes.

|  | X (10) | Y (12)
---|---|---|---
| Budget |  |
Agent 1 | 10 | + |
Agent 2 | 10 | + |
Agent 3 | 2 |  | +
Table 15: Example profile where UTIL-IMP, EGAL-IMP and NASH-IMP outcomes do
not satisfy PO-MR.

∎

######  Proposition 19.

UTIL-MR and NASH-MR do not satisfy IMP.

###### Proof.

Consider the example below. UTIL-MR and NASH-MR will require that both
projects are funded. However, at least one of Agents 1 and 2 must give some
money to project $Y$, as Agent 3 cannot afford it by herself. Thus, this
outcome is not implementable.

|  | X (30) | Y (10)
---|---|---|---
| Budget |  |
Agent 1 | 20 | + |
Agent 2 | 20 | + |
Agent 3 | 5 |  | +

∎

######  Proposition 20.

UTIL-MR and UTIL-IMP do not satisfy IR (or CORE by corollary).

###### Proof.

Consider the example below. The overall (unique) utilitarian outcome is
achieved by funding projects $Y$ and $Z$ with $x_{1}=4$ and $x_{2}=11$.
Observe that this is an implementable outcome, and so this would be the result
of UTIL-MR and UTIL-IMP. However, if Agent 1 left the system, she could have
individually funded projects $W$ and $X$ which would have returned to her a
greater utility. Therefore, this outcome does not satisfy IR.

|  | W (3) | X (3) | Y (5) | Z (10)
---|---|---|---|---|---
| Budget |  |  |  |
Agent 1 | 6 | + | + | + |
Agent 2 | 11 |  |  | + | +

∎

######  Proposition 21.

NASH-MR, MASH-IMP, EGAL-MR and EGAL-IMP do not satisfy IR (or CORE by
corollary).

###### Proof.

From the example above, we see that any egalitarian distribution also will
fund only projects $Y$ and $Z$. For this output to be implementable (and also
satisfy MR), we have $x_{1}=4$ and $x_{2}=11$ or $x_{1}=5$ and $x_{2}=10$. In
either case, we have seen from above that this outcome will not satisfy IR. ∎

  * •

NASH-MR and NASH-IMP do not satisfy IR (or CORE by corollary): Same argument
as above.

######  Proposition 22.

UTIL, UTIL-MR, UTIL-IMP, NASH, NASH-MR and NASH-IMP are not strategyproof.

###### Proof.

Consider the instance given in Table 16. Note that we only include project $Z$
for the purpose of making the NASH welfare of outcomes non-zero. Now, observe
that it is impossible to fund all three projects, so our possible candidate
project sets to be funded by the above rules are those where two projects get
funded.

|  | X (10) | Y (4) | Z (9)
---|---|---|---|---
| Budget |  |  |
Agent 1 | 8 |  | + | +
Agent 2 | 1 |  | + | +
Agent 3 | 10 | + | + | +
Table 16: Example instance where rules are not strategyproof. | $\\{X,Y\\}$ | $\\{X,Z\\}$ | $\\{Y,Z\\}$
---|---|---|---
Utilitarian Welfare | 22 | 37 | 39
Nash Welfare | 224 | 1539 | 2197
Table 17: Utilitarian and Nash welfares of certain project sets to be funded.

We check that there is an implementable outcome that funds $\\{Y,Z\\}$, and
find that the outcome where Agents 1 and 2 pay for $Z$ and Agent 3 pays for
$Y$ is implementable. Hence, $\\{Y,Z\\}$ is the result of UTIL, UTIL-MR, UTIL-
IMP, NASH, NASH-MR, NASH-IMP. Note that the utility for Agent 3 is 13.

Now, suppose Agent 3 were to misrepresent her preferences as in Table 18.
Again, according to this new (perceived) instance, it is impossible for all
projects to be funded, so in Table 19 we check the welfares produced by
funding any two of the projects.

|  | X (10) | Y (4) | Z (9)
---|---|---|---|---
| Budget |  |  |
Agent 1 | 8 |  | + | +
Agent 2 | 1 |  | + | +
Agent 3 | 10 | + |  | +
Table 18: Instance where Agent 3 is misrepresenting her preferences. | $\\{X,Y\\}$ | $\\{X,Z\\}$ | $\\{Y,Z\\}$
---|---|---|---
UTIL | 18 | 37 | 35
NASH | 160 | 1539 | 1521
Table 19: Perceived welfares of certain project sets to be funded if Agent 3
misrepresents her preferences.

Since $\\{X,Z\\}$ can be funded by an implementable outcome where Agents 1 and
2 paying for $Z$ and Agent 3 paying for $X$, $\\{X,Z\\}$ is the result of
UTIL, UTIL-MR, UTIL-IMP, NASH, NASH-MR, NASH-IMP. With this outcome, Agent 3
sees her utility rise to 19.

Then, by misrepresenting her preferences, Agent 3 can cause the choice of the
aforementioned rules to change from funding $\\{Y,Z\\}$ to funding
$\\{X,Z\\}$, hence increasing her own utility. Therefore, UTIL, UTIL-MR, UTIL-
IMP, NASH, NASH-MR and NASH-IMP are not strategyproof.

∎

######  Proposition 23.

EGAL, EGAL-MR and EGAL-IMP are not strategyproof.

###### Proof.

Consider the instance given in Table 20. Due the total budget constraint, at
most two of the projects can be funded, so we check the egalitarian welfare
derived by funding any two projects in Table 21.

|  | X (3) | Y (2) | Z (1)
---|---|---|---|---
| Budget |  |  |
Agent 1 | 1 |  | + | +
Agent 2 | 1 |  | + | +
Agent 3 | 3 | + | + |
Table 20: Example instance where EGAL rules are not strategyproof. | $\\{X,Y\\}$ | $\\{X,Z\\}$ | $\\{Y,Z\\}$
---|---|---|---
Egalitarian Welfare | (2, 2, 5) | (1, 1, 3) | (2, 3, 3)
Table 21: Egalitarian welfares of certain project sets to be funded.

Observe that it is possible for an implementable outcome to fund $\\{Y,Z\\}$
by having Agents 1 and 2 pay for them, and so $\\{Y,Z\\}$ is funded by each of
the above rules. Then, the utility for Agent 3 is 2.

Now, suppose Agent 3 misrepresents her preferences to suppress the fact that
she approves of project $Y$. The new perceived instance is shown in Table 22
and again, we compute the egalitarian welfare produced by funding any two
projects in Table 23.

|  | X (3) | Y (2) | Z (1)
---|---|---|---|---
| Budget |  |  |
Agent 1 | 1 |  | + | +
Agent 2 | 1 |  | + | +
Agent 3 | 3 | + |  |
Table 22: Example instance where rules are not strategyproof. | $\\{X,Y\\}$ | $\\{X,Z\\}$ | $\\{Y,Z\\}$
---|---|---|---
Egalitarian Welfare | (2, 2, 3) | (1, 1, 3) | (0, 3, 3)
Table 23: Egalitarian welfares of certain project sets to be funded.

Note that there is an implementable outcome that funds $\\{X,Y\\}$, where
Agent 3 pays for $X$ and Agents 1 and 2 pay for $Y$. Hence, $\\{X,Y\\}$ is
funded by each of the rules. The new utility for Agent 3 is 3.

Thus, by misrepresenting her preferences, Agent 3 is able to increase the
utility she receives when egalitarian rules are used. Therefore, EGAL, EGAL-MR
and EGAL-IMP are not strategyproof.

∎