|
Computer Science Seminar Date: Monday, 22 September 2025 Time: 3.30 p.m. Venue: Seminar Hall Fair and Efficient Allocation of Indivisible Goods and Chores Aditi Sethia IISc Bengaluru. 22-09-25 Abstract 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 (approximately 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. Based on a joint work with Siddharth Barman, Vishwa Prakash HV, Mashbat Suzuki Bio: Aditi is a Post-Doctoral Fellow at the Indian Institute of Science, Bangalore, hosted by Prof. Siddharth Barman. She received her Ph.D. in Computer Science and Engineering from IIT Gandhinagar, advised by Prof. Neeldhara Misra. Her research focuses on Computational Social Choice (fair division, matching, and voting problems), Game Theory, and Economics and Computation.
|
