Fair division of the commons

A group of agents controls a common budget or owns some common resources. The agents need to decide how to divide this budget across various projects, or to distribute the resources among themselves. Each agent has their own preferences about the best use of the resources. We study ways in which the agents can make these decisions in a fair manner. By fairness, we will mean that for every group member, a proportional part of the common budget is spent in accordance with the member's interests. We will also be interested to take into account the interests of subgroups, and when appropriate aim to avoid envy between group members. We consider several settings in this thesis, capturing different types of potential uses of the common budget. For example, we distinguish between projects that come with a fixed cost (and can be either fully funded or not at all), and projects that can flexibly scale with the amount of funding received. We also distinguish between uses that potentially benefit several or all group members (public goods) or uses that benefit only one agent (private goods). For each scenario we consider, we formalise what we might mean by a "fair" outcome, and then design decision rules that guarantee fairness. Where possible, we additionally aim for rules that make Pareto-efficient use of the common budget. Unfortunately, many of our rules can be exploited by strategic agents who misreport their preferences. In these cases, we prove impossibility theorems which imply that no fair decision rule can be resistant to such strategic manipulation. These impossibility theorems are proved using a computer-aided technique based on SAT solvers, which allows us to obtain computer-generated but human-readable proofs. Further, we consider the computational complexity of the decision rules we consider. In most cases, they can be evaluated using efficient algorithms. In other cases, there are NP-completeness results, but we can show that efficient algorithms exist that work when preferences are well-behaved, in the sense of exhibiting underlying structure.