Collaborative Research: RI: Medium: Transparent Fair Division of Indivisible Items

About This Grant

Fair division deals with the distribution of resources and tasks among different parties, e.g., individuals, firms, nations, or autonomous agents, with the goal of achieving fairness and economic efficiency. Fairness has increasingly become crucial in distributing precious and scarce medical equipment, and its absence has exacerbated healthcare issues during the COVID-19 global pandemic. A wide variety of real-world applications such as scheduling, dispute resolution, healthcare management, and refugee settlement assume complete knowledge about allocation decisions, which gives rise to negative computational and impossibility results. The existing approaches to mitigate these challenges, in turn, impose a high cost on transparency. The broad goal of this project is to provide theoretical and algorithmic solutions for fair allocation of indivisible items in practical, large-scale settings, as a broad contribution to the grand scheme of artificial intelligence (AI) and economics for social good. This research will offer a novel and promising perspective for developing practical and transparent fair solutions while providing a systematic investigation on the perceived fairness of allocation mechanisms that are applicable to societies at large. This project will integrate and develop algorithmic solutions for transparent fair division in a publicly available software system with the goal of extending its reach--and in general promoting fairness and transparency--to a broad national and international audience. This project will develop a new framework for achieving fairness and efficiency in the allocation of indivisible resources with minimum cost on transparency. Specifically, it will make progress in four interconnected dimensions: 1) Tradeoffs between transparency, fairness, and efficiency, that aim at analyzing the compatibility of the properties and devising algorithmic solutions when allocating indivisible items, 2) Strategic aspects of fair division, that investigates agents' behavior and strategies under transparency requirements, 3) Domain restriction, that focuses on developing tractable solutions by circumventing the impossibility results in achieving compatible solutions, and 4) Bads and mixtures, that extend the transparency and fairness framework to include desirable (goods) and undesirable items (bads). Furthermore, this research plans to close the current gap between theoretical foundations of fairness and the perception of fairness through a series of comprehensive empirical evaluations. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.