Papers

Motivated by fair division applications, we study a fair connected graph partitioning problem, in which an undirected graph with m nodes must be divided between n agents such that each agent receives a connected subgraph and the partition is fair. We study approximate versions of two fairness criteria: \alpha-proportionality requires that each agent receive a subgraph with at least (1/\alpha)*m/n nodes, and \alpha-balancedness requires that the ratio between the sizes of the largest and smallest subgraphs be at most \alpha. Unfortunately, there exist simple examples in which no partition is reasonably proportional or balanced. To circumvent this, we introduce the idea of charity. We show that by "donating" just n-1 nodes, we can guarantee the existence of 2-proportional and almost 2-balanced partitions (and find them in polynomial time), and that this result is almost tight. More generally, we chart the tradeoff between the size of charity and the approximation of proportionality or balancedness we can guarantee.

poster session 5 @ blue 6, poster session 8 @ blue 6, oral session 8 @ blue 6, poster session 5, poster session 8, oral session 8

Making decisions by aggregating the opinions of a collection of agents is a question of interest to a broad array of researchers, from ensemble learning theorists to political scientists designing democratic institutions. Herein, we investigate the optimal number of agents needed to make a decision over a binary issue under a majority rule. We take an \emph{epistemic} view where the group decides on a binary issue with one ground truth ``correct'' outcome. Each one of $n$ voters votes correctly with a fixed probability, known as their competence level, which is drawn from a distribution $\mathcal{D}$. After sampling the competence levels, we choose a number of agents to represent the group. After sampling their votes, the correct outcome is chosen as long as more than half of the representatives chose this option. Assuming that we can identify the best experts, i.e., those with the highest competence, to form an \emph{epistemic congress} we find that the optimal congress size should be linear in the population size. This result is striking because it holds even when allowing the top representatives to be accurate with arbitrarily high probabilities. We then analyze real world data, observing that the actual sizes of congresses are much smaller than the optimal size our theoretical results suggest. We conclude by investigating under what conditions congresses of sub-optimal sizes would still outperform direct democracy, in which all voters vote. We find that a small congress would outperform direct democracy if the rate at which the societal bias towards the ground truth decreases with the population size fast enough, and we quantify the speed needed for constant and polynomial congress sizes.

poster session 5 @ blue 6, poster session 8 @ blue 6, oral session 8 @ blue 6, poster session 5, poster session 8, oral session 8

The existence of EFX allocations of goods is a major open problem in fair division, even for additive valuations. The current state of the art is that no setting where EFX allocations are impossible is known, and yet, existence results are known only for very restricted settings, such as: (i) agents with identical valuations, (ii) 2 agents, and (iii) 3 agents with additive valuations. It is also known that EFX exists if one can leave n-1 items unallocated, where n is the number of agents. We develop new techniques that allow us to push the boundaries of the enigmatic EFX problem beyond these known results, and (arguably) to simplify proofs of earlier results. Our main result is that every setting with 4 additive agents admits an EFX allocation that leaves at most a single item unallocated. Beyond our main result, we introduce a new class of valuations, termed nice cancelable, which includes additive, unit-demand, budget-additive and multiplicative valuations, among others. Using our new techniques, we show that both our results and previous results for additive valuations extend to nice cancelable valuations.

poster session 5 @ blue 6, poster session 8 @ blue 6, oral session 8 @ blue 6, poster session 5, poster session 8, oral session 8