12 June 2009, Computational Social Choice Seminar, Ulle Endriss
The first part of this talk will be a review of some of the formal criteria for measuring economic inequality that have been developed in the welfare economics literature. These include the Lorenz curve, the Gini index, and the Robin Hood index. In a slight departure from the usual presentation of this kind of material, I will define these concepts in the context of a model of fair division with indivisible goods. This gives rise to the combinatorial optimisation problem of computing an allocation that reduces inequality with respect to an initial allocation and a chosen inequality measure. In the second part of the talk, I shall discuss the computational complexity of various aspects of this problem and sketch an algorithm for solving it using integer programming.