{'fraction_non_alphanumeric': 0.03720616136604817, 'fraction_numerical': 0.009036241438080845, 'mean_word_length': 4.361724137931034, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Coordinating Monetary Contributions in Participatory Budgeting

We formalize a framework for coordinating the funding of projects and sharing the costs among agents with quasi-linear utility functions and individual budgets. Our model contains the classical discrete participatory budgeting model as a special case, while capturing other well-motivated problems. We propose several important axioms and objectives and study how well they can be simultaneously satisfied. One of our main results is that whereas welfare maximization admits an FPTAS, welfare maximization subject to a well-motivated and very weak participation requirement leads to a strong inapproximability result. We show that this result is bypassed if we consider some natural restricted valuations or when we take an average-case heuristic approach.


INTRODUCTION
Participatory budgeting (PB) is an exciting grassroots democratic paradigm in which members of a community collectively decide on which relevant public projects should be funded (see, e.g., [4,25,27]). The funding decisions take into account the preferences and valuations of the members.
The positive influence of PB is apparent in the many implementations across the globe at the country, city and community level. For example, a PB scheme in the Govanhill area of Glasgow, Scotland empowered local residents to direct funds towards imperative projects like addiction family support groups, a community justice partnership, and refurbishment of locally significant public baths. 1 In the 2014-15 New York City PB process, 51,000 people voted to fund $32 million of neighbourhood improvements. 2 As both examples demonstrate, efficient use of public funds and a significant improvement in community member involvement are two of the foremost advantages of PB processes around the world.
In the above examples, and in fact all implementations of PB that we are aware of, the process relies upon a central authority to determine and provide a budget to fund projects. In practice, this requirement impedes certain collectives which may have an interest in initiating a PB process from doing so due to the lack of institutional structure required to pool resources a priori. For example, several neighbouring municipalities may wish to collaborate on funding infrastructure projects which can benefit residents from multiple communities simultaneously. On a smaller scale, a group of friends may need to decide which furnishings and appliances to buy for their shared apartment. Or, a number of organisations co-hosting an event may need to agree upon a list of speakers, each of which charge their own fee. In each of these cases, while PB seems a natural process of arriving at a mutually beneficial outcome, the classical discrete PB model is insufficient.
We are thus motivated to build a general PB model in which funding is provided by participating agents rather than by a central authority. In the PB model, it is typical to assume that agents' utilities only depend on their valuations for the bundle of projects selected and are indifferent toward the amount of the budget used. While this is appropriate in the classical discrete PB model because the agents do not necessarily believe leftover budget will benefit them, this is not the case in our setting since agents can use their leftover funds directly. For this reason, we model agents who care how much they spend (i.e. quasi-linear utilities).
In summary, we consider a flexible and general framework for PB in which (i) agents can have their own budgets and money from their budget can be directed to fund desirable projects and (ii) agents care both about which projects are funded, 3 and how much monetary contribution they make due to quasi-linear utilities. We point out that our framework captures the classical discrete PB model without the above features in the following way: an artificial altruistic agent can be introduced who provides money equivalent to the central budget and is happy to fund as many projects as needed.
Taking cues from what we see as the key successes of PB implementations, we primarily focus on the efficiency of the outcome while ensuring each involved agent benefits from the community pooling and is thus incentivized to participate in the process. Towards this, we study the possibility of achieving optimal utilitarian welfare alongside the very basic participation notion, namely weak participation, that guarantees positive utility to all of the agents involved.
Contributions. Our first contribution is a meaningful model of collective decision making that unifies or connects various problems and models including participatory budgeting, cost sharing problems, and crowd-sourcing. The model can also be viewed as a bridge between voting problems and mechanism design with money.
We lay the groundwork for axiomatic research for the problem by formalizing meaningful axioms that capture efficiency and participation incentives. In particular, to capture a PB program which is both useful and sustainable, we focus our study on mechanisms which guarantee that every agent benefits from participation.
We show that whereas welfare maximization admits a fully polynomial-time approximation scheme (FPTAS), welfare maximization subject to this well-motivated and very weak participation requirement leads to a strong inapproximability result (Theorem 3). We then turn to more restricted cases and (i) show that even for the case with identical project costs, the same participation requirement results in an inapproximability despite there being an exact, polynomial-time algorithm for welfare maximization; and (ii) present a polynomial-time algorithm for the same objectives for the natural class of valuations called symmetric valuations. Finally, we demonstrate through simulations that average-case performance of the greedy approach achieves close to optimal welfare when subjected to our participation requirement. We summarize our result in the following table.

RELATED WORK
Discrete Participatory Budgeting. As mentioned, the model we formalize has some connections with discrete participatory budgeting models [2-4, 13, 15, 18, 26] in which agents do not have their own budgets and contributions.
Benade et al. [5] and Lu and Boutilier [21] study various aspects of preference elicitation in PB. These models are more general than multi-winner voting [12]. The special case of our model with identical project costs has some connections to multi-winner elections with a variable number of winners, with increased generality due to individual budgets and quasi-linear utilities [19].
Hershkowitz et al. [16] considered a PB setting in which PB is done at a city level but with each district having its own budget and preferences. When districts are viewed as agents, the model is closely related to our model although we focus on different axioms and utility assumptions.  [10,22]. Specifically, it can be equated to CSM with non-rivalrous projects, i.e. each project has a fixed cost [24,29]. The focus is on designing truthful and efficient mechanisms for sharing the cost of availing a certain service or project among the members. The agents do not have budget restrictions. Other research considers truthful mechanisms for combinatorial cost sharing across multiple projects [6,11]. Birmpas et al. [6] focused on symmetric submodular valuations and provided an Iterative Ascending Cost Sharing Mechanism (IACSM) which runs in polynomial time, satisfies weak group strategyproofness, and is -approximate to social cost. 4 The social cost considered is equivalent to the quasi-linear utility that we consider in our setting. Despite the similarities, these works focus on agents without budget restrictions.
Utility-based PB bears resemblance to certain civic crowdfunding models [9,30,31]. However, these papers consider neither budget constraints nor the multiple project case. In this line of work, the goal is to analyze what happens at equilibrium when the agents are strategic, as opposed to our own goal of determining a welfare maximizing subset of projects to fund provided budget constraints. We also introduce a natural intuitive criterion -weak participation -to be satisfied. 4 = 1 + 1 2 + · · · + 1 .

MODEL
In this work, we assume multiple projects and agent-specific budgets. We also assume both the budgets and valuations are public information. The setting, more formally, has the following components.
An instance of a PB process contains a set of participating agents = [ ] and a set of projects, = [ ]. Each project has associated cost and we denote C = ( ) ∈ . Each agent has valuation : 2 → R ≥0 and a budget which is the maximum amount they are willing to contribute. We denote v = ( ) ∈ and b = ( ) ∈ . We assume to be monotonic, that is ( ) ≤ ( ), ⊆ ⊆ . The valuation towards a single project , i.e., ({ }) is denoted by for ease. Without loss of generality, we may assume that the projects included are such that their overall valuation is higher than the cost. Formally, We will consider some important restrictions on valuations of agents. Agents are said to have additive valuations when ( ) = ∈ , ⊆ . For all of the paper except for the subsection on symmetric valuations, we will assume additive valuations. Our key computational results hold for the natural restriction of additive valuations.
In summary, a participatory budgeting instance given by = ⟨ , , v, b, C⟩, ∈ ℐ where ℐ denotes the space of all possible instances. Any mechanism ℳ takes this instance and computes the outcome ℳ ( ) = ( , x  Table 2. An example with 3 projects and 3 agents. EXAMPLE 1. Three neighboring towns have performed cost-benefit analyses for three proposed projects to be covered by the remainder of their annual budget, namely an auditorium for large events, a homeless shelter, and a community swimming pool. The town budgets, the project costs, and the town valuations for each project are given in Table 2. While Town A and Town B have the funds to pay for the pool on their own, they each only value it at its cost and will receive zero utility from doing so. Furthermore, no town has the required budget to fund either of the other two projects on its own. Now observe that, together, the three towns have just enough funds to build the shelter and the pool, the result of which will be a strictly positive utility for each of the three towns. Lastly, we point out that, while the towns could instead coordinate to fund the auditorium and the sum of their values will strictly exceed the cost, Town B will be required to pay at least 2, but its valuation for the auditorium is only 1 and it will thus receive negative utility.
Example 1 shows the usefulness of our framework in the traditional setting of PB -the allocation of government budgets. The following example shows that our framework has broader appeal and can serve any group with common interests that lacks the institutional structure required for a common budget.

EXAMPLE 2.
A group of friends move into a shared house and want to buy various items for their home for communal use. They have drafted a list of items that various members of the household would be interested in sharing, such as a TV for the living room, an espresso machine for the kitchen, and a pool table for the lounge. Because no single friend necessarily values any of the items enough to buy it on their own, they decide to initiate a PB process. The outcome will be (i) a bundle of items to buy for the house and (ii) a quantity to be paid by each friend to cover the costs of the items.
Each friend will receive utility equal to their valuation for the items selected less their required payment.

DESIRABLE AXIOMS
In this section we define properties we would like any mechanism to satisfy. These properties are related to participation incentives and efficiency.

Budget Balanced
We define a weakly budget balanced mechanism as one that always satisfies the basic feasibility criterion that the sum of collected payments is at least the cost of the selected projects.

Participation
We now turn our attention to properties that incentivize agents to participate in the mechanism. Weak Participation (WP) ensures that each agent obtains non-negative utility from the mechanism.
We note that WP is a minimal requirement and considerably weaker than Individual Rationality (IR), which ensures that the utility of each agent obtained from the mechanism is more than the maximum utility it can obtain solely with its In other words, whereas IR captures maximizing individual profit, WP ensures that no agent is making a loss. Whereas not funding any project gives a WP outcome, computing an IR outcome is NP-hard. Hence, to ensure there is incentive to participate, we will focus on desirable outcomes within the space of WP outcomes. The following lemma points out that the satisfaction of WP and WBB by a set of projects can be captured by a single inequality.

LEMMA 1. A set of projects ⊆ can be funded in a WBB and WP manner if and only if
The set of project is WP if ≤ ( ), ∀ , and thus ∈ ≤ ∈ ≤ ∈ ( ). Hence if set of projects satisfies both WBB and WP then ∈ ≤ ∈ min( , ( )).

Efficiency
We measure the efficiency of the outcome with respect to the utilitarian welfare, i.e. the sum of utilities. This definition of efficiency is common in the cost sharing literature [14,23]. Since we model quasi-linear utility for each agent, the utilitarian social welfare (which we refer to simply as social welfare) is given by The utilitarian welfare optimal (UWO) outcome is the social welfare maximizing outcome which is feasible, i.e. can be afforded by the sum of individual budgets. We define UWO-WP to represent the welfare-optimal outcome among those which ensure WP and WBB.
REMARK 1. For any outcome ( , ) which is WBB, there is an outcome which is BB, maintains WP, and achieves weakly greater social welfare.
To see why Remark 1 is true, consider for any WBB outcome an alternative outcome with the same project selection, but with some set of agents' payments decreased such that the outcome is BB. By Remark 1 and our objectives stated in Definitions 3 and 4, we can restrict our attention to outcomes which are BB ( ∈ = ∈ ) and refer to social welfare from now on as the following: In the next section, we prove inapproximability of the UWO-WP objective.

WELFARE MAXIMIZATION SUBJECT TO WEAK PARTICIPATION
In this section, we first show the hardness of finding the welfare-optimal subset subject to budget constraints i.e. UWO.
Next, we show that finding the welfare-optimal subset with the additional constraint of WP, i.e. UWO-WP is not only NP-hard but also inapproximable. Our inapproximability result is striking: the problem of finding UWO admits an FPTAS but after imposing the very simple and weak requirement of WP, the same problem does not admit any polynomial approximation guarantees, even in the setting with only two agents.

UWO
We first make some remarks on the problem of welfare maximization subject to budget restrictions, that is that of finding an outcome that satisfies UWO (Definition 3). The formulation for this problem is formally given by, The problem is NP-hard even for additive valuations as it can be reduced from the NP-complete KNAPSACK problem. Similar to KNAPSACK, although finding UWO is NP-hard it can be approximated to any specified degree, i.e., it has a fully polynomial time approximation scheme (FPTAS) [20].
Despite the positive approximation results, approximation guarantees to UWO may be possible only with huge costs to certain agents who incur large disutility. We now show that it is not possible to achieve an outcome which is both UWO and WP. PROPOSITION 1. It is impossible to design a mechanism ℳ that satisfies both WP and UWO.
PROOF. Consider an instance with two agents and a single project with cost 1 = 1. The valuations are 11 = 2 and 21 = 0, with budgets being 1 = 0 and 2 = 1. Observe that the UWO outcome is to fund the project. However, this cannot be done in a WP manner since the only agent with nonzero budget does not attribute any value to the project. □

UWO-WP
Given the impossibility result stated in Proposition 1, we are interested in finding solutions which are welfare optimal amongst those which satisfy WP, i.e. that are UWO-WP (Definition 4), for additive valuations.
Next we study the complexity of computing a UWO-WP allocation. The decision version of UWO-WP is to determine whether a set of projects ⊆ exists such that it is WP, WBB, and SW( ) ≥ , where is an input parameter to the problem. THEOREM 1. Finding UWO-WP allocation for additive valuations is NP-hard, even for one agent.
PROOF. We reduce the problem from the NP-complete KNAPSACK problem: given items with weights 1 , · · · , and values 1 , · · · , , capacity and value , does there exist a subset ⊆ {1, · · · , } such that ∈ ≤ and ∈ ≥ ? Given an instance of the KNAPSACK problem, we build an instance of the UWO-WP problem with a single agent as follows: • The set of projects is the set of items. Each project has cost = . The budget of the agent is .
• The value of each project to the agent is = + .
Observe that WP is satisfied by construction. Furthermore, we can see that the social welfare obtained by choosing a set of projects is exactly equal to the value of choosing set of items in the knapsack problem i.e, SW( ) = ∈ − = ∈ . Also note that the WBB condition is satisfied if and only if the capacity constraint is satisfied. It follows that a solution with value at least exists in the Knapsack problem if and only if there exists a set of projects whose social welfare in the corresponding UWO-WP instance is at least . The NP-hardness follows immediately. □

Inapproximability of UWO-WP
As finding UWO-WP is NP-hard even for a single agent, we look for an approximation algorithm. Unlike the problem of finding UWO, which admits an FPTAS, we next show that UWO-WP does not admit any bounded polynomial approximation guarantees.
As a step towards understanding why the problem is inapproximable let us consider the following illustrative example which demonstrates the necessity of coordination among agents in order to attain high social welfare.  Table 3. An instance with = 3 and = 5 where the agents must coordinate in order to attain high welfare EXAMPLE 3 (A NECESSITY FOR COORDINATION). Observe that in the example given in Table 3, agents 1 and 2 maximize their utility by funding projects 4 and 5, respectively, which can be funded in a WP manner. Agents 1 and 2 maximize their utility individually but no leftover budget remains to fund other projects.
However, note that = {1, 2, 3} can be funded in a WP and WBB manner and achieves ( ) = . Hence, agents 1 and 2 must sacrifice their own utilities in a coordinated manner in order to obtain high welfare. Furthermore, since H can be arbitrarily high, any algorithm which hopes to give a good approximation of UWO-WP should be able to find such a coordination if one exists. projects. Let ( ) be the social welfare obtained from the UWO-WP solution to instance . We know that ( ) ≤ ∈ ( ). We now create a new instance by adding an agent 0 and a project 0 to such that: • 00 = (2 ( + 1, + 1)) ∈ ( ), budget 0 = 0 We denote the transformed instance as . It has + 1 agents and + 1 projects. Note that the transformation is polynomial time as ( , ) is polynomial-time computable. The modified instance creates a large gap in the social welfare depending on the cost of project 0 (which can be used to retrieve information about MaxPE) as seen in Figure 1. This gap in turn is used show the approximation hardness.
Consider now a polynomial time algorithm Alg for UWO-WP with -approximation guarantee, that is We now claim that MaxPE( ) ≥ accepts (i.e., dollars can be extracted from agents in while satisfying WBB and WP) if and only if SW(Alg( )) ≥ 2 ∈ ( ). The forward direction follows since if dollars can be extracted from agents in then project 0 can be afforded. Hence, ( ) ≥ (2 ( + 1, + 1) ∈ ( ) since there is a solution that satisfies WBB and WP which also funds project zero. Thus combining with inequality (4) we see that SW(Alg( )) ≥ 2 ∈ ( ).
As for the backward direction, first observe that if SW(Alg( )) ≥ 2 ∈ ( ) then 0 ∈ Alg( ). To see this, suppose on the contrary 0 ∉ Alg( ). Then, SW(Alg( )) ≤ ( ) ≤ ∈ ( ), leading to a contradiction. Thus, we have 0 ∈ Alg( ), which implies that the agents in must be able to pay for project 0 in a WP and WBB manner. This is due to the fact that agent 0 cannot contribute any money towards funding project 0 since she has budget equal to zero, and agents PROOF. We give a reduction from the NP-complete PARTITION problem: given integers 1 , · · · , , the problem asks if there exists a subset such that ∈ = 1 2 ∈ ? For ease of notation, we denote = 1 2 ∈ . Given any instance of the partition problem, we construct an instance of MaxPE ≥ with a single agent such that The MaxPE ≥ decision problem for this instance is then If there exists a set * such that ∈ * = , then the corresponding MaxPE ≥ instance is a Yes instance. This holds since min , ∑︁ On the other hand, if for any ⊆ {1, · · · , } we have ∈ ≠ , then the corresponding instance of MaxPE ≥ is a No instance. This can be seen by the following observation:   Even though UWO admits an FPTAS, with the inclusion of the simple and intuitive constraint of WP, we obtain the above strong inapproximability results.

Identical Costs
We consider a well-motivated special case where all projects have identical costs. This special case is meaningful in several scenarios, for example in the case where agents must decide the number and locations of units of some type of infrastructure such as public toilets. In this case, each project may have the same cost but their different locations mean that agents differ in their proximity and thus their valuations will likely reflect this. Alternatively, a group of consultants forming a partnership may wish to choose a set of analysts to hire, but have varying available funds and preferences which depend on the alignment of a candidate's background with their own expertise.
More formally, in this setting we have = ∀ ∈ . We assume = 1 for simplicity since we can scale the costs uniformly. We first note that the UWO allocation in the identical costs setting is computable in polynomial time.
Specifically, we can compute UWO by sorting the projects according to their social welfare (the sum of agent valuations minus cost) and greedily selecting them until there is no remaining project with non-negative social welfare or until no budget remains.

Inapproximability of UWO-WP
Given UWO is polynomial time computable in the identical costs setting, and the same problem is NP-hard in the general setting, we may take this as an encouraging sign that a tractable algorithm for UWO-WP may exist in our restricted setting. However, as we will show, UWO-WP does not admit any polynomial approximation guarantees, even in this restricted setting. Our argument follows similarly to that used in the general setting. Intuitively, to be able to afford any single project in our setting, we must be able to identify a subset of projects that extracts a single dollar when such a subset exists. Thus we begin by defining the decision version of the MaxPE problem with = 1 (MaxPE ≥ 1), which in this setting becomes: It is NP-hard to decide MaxPE ≥ 1, even with identical budgets.
PROOF. We give a reduction from the NP-complete Exact Cover by 3-Sets (X3C) problem: given a set = { 1 , . . . , 3 } (with cardinality a multiple of 3) and a family of 3-element subsets (triples) of , the problem asks if there is a subfamily ′ ⊆ such that every element in is contained in exactly one triple of ′ . Given any instance of X3C, we construct an instance of MaxPE ≥ 1 such that we have: • an agent ∈ for each ∈ , each with identical budget of = 1 3 + 1 • a project ∈ for each triple ∈ • agent valuations = 1 3 + 1 if ∈ and 0 otherwise. The MaxPE ≥ 1 decision problem becomes Note that an agent ∈ contributes 0 to the above summation if a bundle does not contain any project for which ∈ and they contribute exactly 1 3 + 1 otherwise. Thus, the maximum this summation can evaluate to is · ( 1 3 + 1 ) = 3 + 1. If there exists a subfamily ′ ⊆ such that every element in is contained in exactly one triple of ′ , then the corresponding MaxPE ≥ 1 instance is a Yes instance. To see this, consider = { : ∈ ′ }. Note that | | = 3 since this is the number of triples required to cover a set of size . By the transformation, each agent attributes non-zero value to exactly one project in . Thus, the MaxPE expression becomes · ( 1 3 + 1 ) − 3 = 1. In the other direction, if the MaxPE ≥ 1 instance is a Yes instance, let be a bundle for which the excess payment extraction is weakly greater than 1. First note that ∈ = 3 + 1 so | | ≤ 3 + 1 by WBB. However, if | | = 3 + 1, is valued by exactly 3 agents, the MaxPE expression is upper bounded by 3 · | |( 1 Thus, | | = 3 . Consider the subfamily ′ = { : ∈ }. We wish to show ′ constitutes an exact cover of . If it does not, it either does not cover or it contains two subsets which are not disjoint. In the former case, there is an element ∈ which is not contained in any triple in ′ which means there is an agent in the MaxPE ≥ 1 instance whose total valuation is 0. This means the MaxPE expression is upper bounded by ( − 1)( 1 3 + 1 ) − 3 = 2/3 − 1/ < 1, which is a contradiction. In the latter case, there exist , ∈ ′ such that ∩ ≠ ∅, which means there exists an agent in the corresponding MaxPE ≥ 1 instance with non-zero valuations for both and . Because there are exactly 3 agents with non-zero valuations for each of the /3 projects in , this means there must be some agent who has zero valuation for every project in and we reach a contradiction. Therefore, ′ constitutes an exact cover of and the X3C instance is a Yes instance. □ With the preceding lemma, the following inapproximability result follows from an analogous argument to that used in the proof of Theorem 3 and the justification of Remark 4.

Symmetric Valuations
Given that finding UWO-WP for additive valuations is inapproximable, we analyze the simpler valuation domain of Symmetric valuations are standard restrictions in the mechanism design literature. For example, Hoefer and Kesselheim [17] use symmetric valuations to capture "a spectrum auction of equally sized channels which all offer very similar conditions." Other research has investigated cost sharing mechanisms for symmetric valuations [6].
THEOREM 5. For symmetric valuations, Algorithm 1 finds UWO-WP in polynomial time.
PROOF. As outlined in Algorithm 1, we assume the projects are ordered by increasing cost. We denote the set of projects {1, ..., } by [ ] for simplicity of notation. Let * be the solution to the UWO-WP problem with ℓ = | * |, and

EXPERIMENTS
We know that UWO-WP is not just hard but inapproximable for general additive valuations. The inapproximability arises from certain pathological cases where some agents have very high valuations for projects they cannot afford alone. In this section, we use synthetic simulations to understand how well a simple greedy algorithm approximates UWO-WP welfare for various natural families of instances.
The PB instances we use in our synthetic simulations are of the three following types: (1) For uniform instances, we sample agent valuations from a Uniform distribution, (2) For normal instances, we uniformly sample a mean and variance for each project to define a Normal distribution from which all agents' valuations are drawn for that project. That is, for each ∈ , we sample ∼ [0, 1] and ∼ [0, 0.5], and draw ∼ ( , ), shifting to ensure positive valuations.
(3) For bernoulli instances, for each project , we first uniformly sample a probability, ∼ [0, 1], and a constant, ∼ [0, 1]. We then draw agents' valuations from a Bernoulli distribution with this probability and multiply the result by the constant, i.e. ∼ · Bernoulli( ).
For all instances, project costs are sampled uniformly, ∼ [0.75 · , ]. By ensuring costs are close to the sum of agents' valuations for each project, we make WP more difficult to satisfy and avoid trivial instances. The total budget is set to half of the total of project costs and individual budgets are fractions of this overall budget, drawn uniformly at random and normalized to sum to 1. The uniform instance family captures a setting where agents' valuations are perfectly random and not correlated with one another. Since this is not the case in most realistic settings, we use the normal instance type to capture scenarios in which there is a degree of consensus amongst all agents on the value of each project. Lastly, we study the bernoulli instance type, which captures approval-based utilities, a modeling assumption well-studied in PB [3,26].
For each combination of instance family, = {5, 10}, and ranging from 10 to 1600, we generate 10,000 synthetic instances. We find UWO-WP welfare using brute force search as our baseline. In the algorithm we henceforth refer to as , we sort the projects in descending order of bang per buck, i.e. welfare obtained per cost. We pick a new project in this order, provided it does not violate WP or WBB, and continue in this fashion until no such project remains.
For each instance, we find the ratio between the welfare obtained by and that of the UWO-WP allocation, i.e.,

SW( )
SW(UWO-WP) . The results are reported in Figure 2 for each value of and , where the solid line is the median welfare ratio across all 10,000 instances and the shaded region below outlines the 10 ℎ percentile welfare ratio across the same instances. Figure 2 shows that obtains optimal welfare (i.e. UWO-WP) in at least 50% of instances for each instance type and number of agents and projects. The shaded region of the charts shows that the 10 ℎ percentile performance of drops significantly below the optimum for normal instances with = 5 and bernoulli instances with = 10. Nevertheless, even for these instances, we point out that achieves at least 70% of optimal welfare in 90% of instances. Altogether, we observe that the algorithm achieves close-to-optimal performance in the vast majority of a wide variety of instances with reasonable input assumptions. Such performance from an algorithm as unsophisticated as comes as a notable surprise given our strong inapproximability results.

CONCLUSION
In this paper, we laid the groundwork for an important and general PB framework. We focused on welfare maximization subject to minimal participation axioms that agents would expect the mechanism to satisfy and proved a number of hardness and inapproximability results, as well as positive results in certain restricted cases. Future work can consider other restricted cases and pursue other objectives within our framework. In recent work on PB, there has been progress made on formalizing fairness axioms. It will also be interesting to consider meaningful fairness axioms for our setting.