20 February 2009, Computational Social Choice Seminar, Bart de Keijzer
There exist a lot of situations where we have to allocate resources to agents in a way that is considered fair. In this talk, we concern ourselves with the complexity of computing such allocations. I will introduce some notions of fairness, and talk about the complexity of finding fair resource allocations under various constraints. In particular, I will discuss some new non-straightforward complexity results that were previously conjectured but had up until now not been found. I have written down their proofs in: http://arxiv.org/abs/0810.0532v2.