26 January 2017, Computational Social Choice Seminar, Sebastian Schneckenburger

Abstract:

In multiagent resource allocation (MARA), the task of finding a 'fair allocation' is computationally difficult in general. In particular the determination of allocations that are fair in terms of utilitarian or Nash social welfare are NP-hard problems. The same holds true for minimising inequality between the utility levels enjoyed by the individual agents. To avoid the centralised resolution of these hard problems, we analyse the use of a distributed method, where new allocations emerge as the result of a sequence of local deals between groups of agents agreeing on an exchange of some of the items in their possession. We show that it is possible to design distributed systems that provide theoretical guarantees for optimal outcomes in all considered settings, but also that there are significant computational hurdles to be overcome in practice: large numbers of potentially highly complex deals may be required under the distributed approach.

The first part of the talk will be about the MARA-framework and the distributed approach for utilitarian/Nash social welfare. The second part will be about inequality indices, and in particular the Atkinson index as a working example. We show that the idea of the distributed approach can be adapted to this setting; nevertheless, some additional hurdles arise. The results are interesting from a methodological point of view, since we use a novel derivation from basic calculus, while much work in MARA relies on combinatorial arguments. (Joint work with Britta Dorn and Ulle Endriss.)