In this talk, we will discuss fair division of indivisible mixed manna (items whose values may be positive, negative, or zero) among agents with additive preferences. In such settings, the existence of fair (approximate envy-free) and efficient allocations is an intriguing open question even for three agents. We will see how fairness --- in terms of a new relaxation of envy-freeness --- and efficiency can always be achieved together. Specifically, our fairness guarantees are in terms of envy-freeness up to k reallocations (EFR-k): An allocation A is said to be EFR-k if there exists a subset R of at most k items such that, for each agent i, we can reassign items from within R and obtain an allocation which is envy-free for i.
Our results advance the understanding of fair and efficient allocation of indivisible mixed manna and rely on a novel application of the Knaster-Kuratowski-Mazurkiewicz (KKM) Theorem in discrete fair division. We utilize weighted welfare maximization, with perturbed valuations, to achieve Pareto efficiency, and overall, our techniques are notably different from existing market-based approaches.
Short Bio:
Aditi is currently a Post-Doctoral Fellow at the Indian Institute of Science, Bangalore, hosted by Prof. Siddharth Barman. She received her PhD from IIT Gandhinagar, advised by Prof. Neeldhara Misra. Her research interests revolve around Computational Social Choice (Fair Division, Voting and Matching problems), Algorithmic Game Theory, and Economics and Computation.
