Suppose two players wish to divide a finite set of indivisible items, over which each distributes a specified number of points. Assuming the utility of a player’s bundle is the sum of the points it assigns to the items it contains, we analyze what divisions are fair. We show that if there is an envy-free (EF) allocation of the items, two other desirable properties—Pareto-optimality (PO) and Maximinality (MM)—can also be satisfied, rendering these three properties compatible. But there may be no (...) EF division, in which case some division must satisfy a modification of Bentham’s (1789/2017) “greatest satisfaction of the greatest number” property, called maximum Nash welfare (MNW), that satisfies PO. However, an MNF division may be neither MM nor EFX, which is a weaker form of EF. We conjecture that there is always an EFX allocation that satisfies MM, ensuring that an allocation is maximin, precisely the property that Rawls (1971/1999) championed. We discuss four broader philosophical implications of our more technical analysis. (shrink)

This article combines Social Choice Theory with Discrete Optimization. We assume that individuals have preferences over edges of a graph that need to be aggregated. The goal is to find a socially “best” spanning tree in the graph. As ranking all spanning trees is becoming infeasible even for small numbers of vertices and/or edges of a graph, our interest lies in finding algorithms that determine a socially “best” spanning tree in a simple manner. This problem is closely related to the (...) minimum (or maximum) spanning tree problem in Discrete Optimization. Our main result shows that for the various underlying ranking rules on the set of spanning trees discussed in this article, the sets of “best” spanning trees coincide. Moreover, a greedy algorithm based on a transitive group ranking on the set of edges will always provide such a “best” spanning tree. (shrink)

This paper provides a distance based analysis of the Borda rule with respect to Condorcet’s criterion. It shows that the minimal Condorcet consistency present in the Borda rule, whenever a Condorcet winner (the alternative that wins against every other alternative in a pairwise contest) exists, disappears in the case of voting cycles. First, it is shown that for certain preference profiles the Borda winner is furthest from being a Condorcet winner. Second, it is shown that there exist preference profiles for (...) which the Borda winner is closest from being a Condorcet loser (the alternative that loses against every other alternative in a pairwise contest). (shrink)