An Equivalence Between Fair Division and Wagering Mechanisms

Rupert Freeman and Jens Witkowski contributed equally to the manuscript. The authors thank Vasilis Gkatzelis, Mirko Kremer, Jochen Schlapp, and the anonymous reviewers for helpful feedback. This work was completed in part while Rupert Freeman and David M. Pennock worked for Microsoft Research. This paper is a significantly extended version of Freeman et al. (2019). This full paper contains the following contributions that do not appear in the preliminary version. First, it establishes a formal connection between normality, a property considered in the wagering literature, and envy-freeness, a notion of fairness in the fair division literature (Theorem 3). Second, CSRs, a class of mechanisms originally developed in the wagering literature are shown to characterize all incentive-compatible and non-wasteful fair division mechanisms for two agents, subject to two mild technical conditions (Lemma 1). Leveraging this characterization, Section 5 casts known fair division mechanisms into this scoring rule framework and presents improved bounds on the approximation to optimal utilitarian welfare that any fair division mechanism can achieve (Corollary 2). Finally, Section 6 contains new and significantly expanded simulations comparing all known incentive-compatible mechanisms.