Two Player Fair Division Problem withUncertainty

摘要

This paper analyses the territory fair division, problem initially posed by Hugo Steinhaus [1], by studying the solutions given by different algorithms on a large generated set of inputs for two players. Main algorithm used is Adjusted Winner, developed by S. Brams and A. Taylor [2]. We compare it to combinatorial enumeration and some algorithms proposed for experimentation by authors. Additionally we define measures to characterize the initial task and game theoretic measures to select the best solution. Moreover we extend the problem by allowing uncertainties in the players' value representation of items to be divided, based on the example of territorial division. For uncertainty management we use the belief system from Dempster-Shafer Theory [3].