Donor coordination

Donor coordination is a problem in social choice. There are several donors, each of whom wants to donate some money. Each donor supports a different set of targets. The goal is to distribute the total donated amount among the various targets in a way that respects the donors' preferences.

As an example, consider a town with three recreational facilities that require funding: theater, chess club, and basketball field. There are two donors: Alice and George, each of whom wants to donate 3000. Alice wants to donate to indoor activities (theater or chess), whereas George prefers to donate to competitive activities (chess or basketball). Suppose further that the donors consider the facilities substitute goods, so that the utility of a donor is the sum of money distributed to a facility he likes. Consider the following possible distributions:

In the uncoordinated distribution, Alice gives 1500 to each indoor activity, while George gives 1500 to each competitive activity. The resulting distribution is 1500, 3000, 1500. Each donor has a utility of 4500.

In contrast, if they coordinate, they can contribute everything to the chess club, so the distribution becomes 0, 6000, 0. Now, each donor has a utility of 6000, so this distribution Pareto-dominates the previous one.

Alternatively, one can assume that the donors consider the facilities complementary goods, so that the utility of a donor is the minimum amount of money distributed to a facility he likes. In this case, the uncoordinated distribution 1500,3000,1500 gives both donors utility 1500; the distribution 0,6000,0 gives both donors utility 0; but there is an even better distribution:

If the donations are divided equally, the distribution becomes 2000,2000,2000. Now, each donor has a utility of 2000.

In both cases, coordination can improve the efficiency of the allocation.

Donor coordination is a variant of participatory budgeting, in which the budget is donated by the voters themselves, rather than given by the government. Since the donations are voluntary, it is important that the coordination algorithm ensures that each voter weakly gains from participating in the algorithm, i.e., the amount contributed to projects he approves of is weakly higher when he participates than when he does not.

Donor coordination has been studied in several settings, which can be broadly categorized into divisible and indivisible:

In divisible donor coordination, each target can receive and use any amount of funding (as in the opening example). In this setting, targets are often called charities.
In indivisible donor coordination, each target has a pre-determind cost, and it can be either fully funded, or not funded at all. In this setting, targets are often called projects.

Divisible targets[edit]

Donor coordination with divisible targets is similar to the problem of fractional social choice, except that in the latter, the "budget" is fixed in advance (e.g. time, probability, or government funds), and not donated voluntarily by the agents.

Additive binary utilities[edit]

Brandl, Brandt, Peters and Stricker^[1] study donor coordination with additive binary (dichotomous) preferences, represented by approval ballots. Formally, for each donor i there is a set of approved charities denoted by A_i, and i's utility from a distribution d is the total amount of money distributed to charities in A_i: $u_{i}(d)=\sum _{x\in A_{i}}d_{x}$ .

They analyze several rules. They are exemplified below for a setting with 4 targets (a,b,c,d) and 5 donors who contribute 1 each, and whose approval sets are ac, ad, bc, bd, a.

The uncoordinated rule just divides the contribution of each agent i among the charities liked by i. So the funding distribution is 2,1,1,1 and the utilities of the five agents are 3,3,2,2,2. This mechanism is implementable and individually-rational, but not efficient: the outcome is dominated, for example, by the distribution 3,2,0,0, where the utilities are 3,3,2,2,3.
The Nash product rule finds a budget-allocation maximizing the product of utilities. It is Pareto efficient, implementable and individually-rational. However, it is not Strategyproof nor resource-monotonic.
The Constrained-utilitarian rule finds a budget-allocation maximizing the sum of utilities from the set of all implementable rules. It is implementable, individually-rational, strategyproof and resource-monotonic. However, it is not Pareto-efficient.
They present a new rule. Their rule is fair, resource-monotonic and efficient.

They also prove a strong impossibility result: there is no PB rule that satisfies the following three properties: strategyproofness, efficiency, and positivity (- at least one approved project of each agent receives a positive amount). The proof reasons about 386 preference profiles and was obtained with the help of a SAT solver.

Additive general utilities[edit]

Brandl, Brandt, Greger, Peters, Stricker, Suksompong^[2] study donor coordination assuming donors have additive but non-binary utilities. Formally, for each donor i and charity x, there is a value v_i,x, and i's utility from a distribution d is: $u_{i}(d)=\sum _{x\in A_{i}}v_{i,x}d_{x}$ .

They prove that the Nash product rule incentivizes donors to contribute their entire budget, even when attractive outside options are available. while spending each donor’s contribution only on projects the donor finds acceptable. The Nash rule is also efficient. On the down side, it is not strategyproof, and violates simple monotonicity conditions (even in the binary case).

Leontief utilities[edit]

Brandt, Greger, Segal-Halevi, Suksompong^[3] study donor coordination assuming donors have Leontief utilities. This is motivated by funding charities, where it is reasonable that donors want to maximize the minimum amount given to a charity they approve. More generally, for each donor i and charity j, there is a value v_i,j, and i's utility from a distribution d is:

$u_{i}(d)=\min _{x\in A_{i}}d_{x}/v_{i,x}$ .

They define a rule called the Equilibrium Distribution Rule (EDR), which finds a pure-strategy Nash equilibrium in a game in which the donors' strategies are the possible decompositions of their donations. They prove that there always exists a unique pure Nash equilibrium, and it can be found efficiently using convex programming, by maximizing the Nash social welfare (a sum of logarithms of agents' utilities, weighted by their donations). EDR is Pareto-efficient, group-strategyproof, and satisfies several other monotonicity properties.

With binary-Leontief utilities, EDR is also egalitarian for projects and for agents (subject to decomposability), can be found efficiently using linear programming, and attained at the limit of a best-response sequence.

Quasilinear utilities[edit]

Buterin, Hitzig and Weyl^[4] present a mechanism in which donors invest money to create public goods. They assume that agents have quasilinear utilities, so without coordination, there will be under-provision of public goods due to the free-rider problem.

They suggest a mechanism called Quadratic Finance, inspired by quadratic voting. The amount received by each project x is $\left(\sum _{i}{\sqrt {c_{i,x}}}\right)^{2}$ , where c_i,x is the contribution of agent i to project x. They show that, in the standard model (selfish, independent, private values, quasilinear utilities), this mechanism yields the utilitarian-optimal provision of public goods.

Other ways to encourage public goods provision are:

Voting to select which projects will be implemented. This system does not let people indicate how much they support a specific project.
Matching funds and tax deductions. These practices aim to amplify the effects of small contributions and increase the diversity of potential contributors. But the matching ratio is often set arbitrarily. In contrast, QF attains the same effects in an optimal way.

They present variations and extensions of QF. They explain how it can be used to campaign finance reform, funding open source software, news media finance, charitable giving, and urban public projects.

Indivisible targets[edit]

Donor coordination with indivisible targets is similar to combinatorial participatory budgeting, except that in the latter, the budget is fixed in advance and not contributed voluntarily by the agents.

Funding by donations only[edit]

Aziz and Ganguly^[5] study a variant on indivisible participatory budgeting in which there is no exogeneous budget. There is a list of potential projects, each with its own cost. Each agent approves a subset of the projects, and provides an upper bound on the amount of money he can donate. The utility of each agent equals the amount of money spent on projects he approves (i.e., cost-satisfaction). The rule should specify (1) Which projects are funded? (2) How much money each donor pays? Note that, because the projects are indivisible, probably most donors will pay less than their upper bound.

They study three axioms related to encouraging participation:

Minimal Return: each donor's utility is at least as high as the money he pays (no one loses from participating).
Implementability: it is possible to decompose the budget allocation such each donor's donation is given only to projects he approves. Implementability implies Minimal Return.
Individual Rationality: each donor's utility is at least as high as the maximum possible utility the donor could get by donaing alone.

Three axioms related to efficiency:

Exhaustiveness: no set of agents can pool their unused donations and fund a project approved by all of them.
Pareto-optimality among all allocations, or among implementable or minimal-return allocations.
Payment-constrained Pareto-optimality: the allocation is not Pareto-dominated by any other allocation of at most the same price.

Two axioms related to fairness:

Weak core stability: no group of agents can pool their budgets and get an outcome strictly better to all group members.
Proportionality: if a group of agents N all approve only the same set of projects P, and the cost of P is at most the total donation by agents of N, then all projects in P are funded.

Finally, they study strategyproofness. They study which axioms are satisfied by three welfare-maximization rules: utilitarian, egalitarian (leximin) and Nash-product; they also study their computational complexity. They also conduct experiments for studying the price of fairness - how much fairness properties effect the social welfare - in instances that model two real-life donor coordination scenarios: share-house setting, and crowdfunding setting.

Aziz, Gujar, Padala, Suzuki and Vollen^[6]^[7] extend the above study to agents with cardinal ballots and quasilinear utilities. They show that welfare maximization admits an FPTAS, but welfare maximization subject to a natural and weak participation requirement is strongly inapproximable.

Combining donations and government funds: Donation No Harm[edit]

Chen, Lackner and Maly^[8] study an extension of indivisible participatory budgeting in which there is both exogeneous budget and potential donations. Each voter can, besides voting for projects, also donate to specific projects of his choice. The donations of each project are deducted from its cost before the PB rule is activated. Their aim is to guarantee that rich donors do not use their donations to have an unfairly large influence on the total budget. Formally, they define a condition called "Donation-No-Harm", which requires that the utility of each agent when there are donations is at least as high as his utility without donations. They also study monotonicity properties specific to the setting with donations. They assume cardinal utilities. They also assume that projects belong to possibly-overlapping categories, with upper and lower quotas on each category.

They study 8 rules: 4 based on global optimization and 4 based on greedy optimization. They consider three ways to adapt these rules to the setting with donations:

First, reduce the cost of each project by the total amount donated to it; then, run the PB rule on the reduced costs. With this adaptation, all 8 rules violate Donation-No-Harm.
First, run the rule without the donations; then, run the rule again, with the savings due to the donations as the new budget. With this adaptation, all 8 rules satisfy Donation-No-Harm.
First, run the rule without the donations; then, find a bundle with a maximum social welfare among all bundles that donate the outcome of the first stage. With this adaptation, too, all 8 rules satisfy Donation-No-Harm.

Besides Donation No Harm, they also study three monotonicity axioms: Donation-project-monotonicity, Donation-welfare-monotonicity, and Donation-voter-monotonicity. They also study two computational problems related to this setting:

Deciding whether a given bundle is selected by some rule: this problem is coNP-hard for the 4 global optimization rules, but in P for the 4 greedy rules.
Deciding whether a given voter can spend a given amount of money in a way that will increase his utility. The problem is sigma2P-complete for the 4 global optimization rules, and NP-complete for the 4 greedy rules.