Executive Summary : | Fair division is a centuries-old problem that involves dividing resources among agents with differing preferences. For "divisible" resources, such as land, water, or time, the literature provides guaranteed existence of fair solutions. However, for indivisible resources, exact envy-freeness may not always be achievable. Two main approaches have been proposed in the literature: randomization and approximation. Randomization, prominent in microeconomic theory, makes probabilistic decisions regarding the assignment of indivisible objects and provides "ex-ante" or in-expectation guarantees on fairness. Approximation, prominent in computer science and artificial intelligence, focuses on deterministic algorithms that guarantee approximately fair solutions. However, randomization could return highly unfair solutions, while approximation could systematically discriminate against certain agents due to its deterministic nature. The proposed proposal aims to bridge these two traditionally disjoint approaches in fair division of indivisible resources by exploring the existence and computation of randomized allocations that simultaneously satisfy ex-ante and ex-post fairness guarantees. The research thrust is twofold: exploring best-of-both-worlds guarantees beyond the standard additive valuations model and exploring fair allocation of undesirable resources or chores. The proposal will bring together ideas from theoretical computer science, artificial intelligence, and economic theory, contributing new algorithmic techniques. The research outcomes will contribute significantly to the growing literature on fair division and pave the way for developing practical methods with a tangible real-world impact. |