Fair division of indivisible items between two players: design parameters for Contested Pile methods

摘要

Contested Pile methods are two-phase procedures for the fair allocation of indivisible items to two players. In the Generation Phase, items over which the players' preferences differ widely enough are allocated. "Contested" items are placed in the Contested Pile, which is then allocated in the Splitting Phase. Each phase can be carried out using several different techniques; we perform a comprehensive analysis of the resulting design variants using a computational model. The properties of fairness and efficiency, generally achieved in the Generation Phase, must be traded off against robustness to manipulation. We find that the recently developed Undercut procedure for the Splitting Phase outperforms alternative methods in both fairness and efficiency. In general, procedures that keep the Contested Pile relatively small and incorporate the Undercut procedure score well in both fairness and efficiency, but are prone to manipulation.