CAREER: AF: New Algorithmic Foundations for Fair Division through Competitive Equilibrium

公平分配是一个古老的问题，如何在几个代理之间公平而有效地分配一组(稀缺的)资源。它自然而然地出现在广泛的现实生活环境中，如争端解决、课程/学校席位、计算资源管理、机场交通管理和频谱分配。竞争均衡是经济学中研究市场的一个核心解概念，由于其显著的公平和效率属性，它也是解决公平分配问题的最受欢迎的机制之一，即使后者可能不涉及金钱。随着互联网的出现和计算系统对现代生活方方面面的影响，公平分配的应用程序得到了极大的增长，基于实用程序模型、分配限制和新的公平概念的变体过多。由此产生的均衡问题需要复杂的约束和概括，以至于过去几十年为市场开发的大多数工具和技术似乎都不适用，因此相应的公平分配问题仍然没有得到解决。这个项目旨在探索这些基本的开放问题中的许多。该项目将支持和吸引来自不同背景的本科生和研究生，并将调查结果整合到调查员教授的多门课程中。与市场不同，在公平分配问题中，物品既是好的(例如，蛋糕)，也是坏的(例如，家务)，分配需要满足额外的限制，例如，学生被分配到一所学校。该项目的主要研究重点是了解(I)商品和劣质、(Ii)受限分配、(Iii)可分和不可分项目及其各种组合的竞争均衡的结构和计算复杂性。提出的挑战不仅在公平分配方面具有根本重要性，而且在均衡计算、机制设计以及连续和离散优化方面也具有重要意义。这个项目的工作将为这些不同领域的问题带来重要的算法和复杂性理论见解。所开发的技术将有助于关于近似、非凸优化、数学规划、调度和拍卖理论的新兴文献，并将为进一步探索开辟新的途径。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Fair division is the age-old problem of allocating a set of (scarce) resources among several agents in a fair and efficient way. It arises naturally in a wide range of real-life settings such as dispute resolution, seats in courses/schools, computing-resources management, airport-traffic management, and spectrum allocation. Competitive equilibrium is a central solution concept in economics to study markets, and due to its remarkable fairness and efficiency properties, it is also one of the most preferred mechanisms for solving fair-division problems even though there may be no money involved in the latter case. With the advent of the Internet and the influence of computing systems on all parts of modern life, applications of fair division have grown immensely with a plethora of variants based on utility models, allocation constraints, and new fairness notions. The resulting equilibrium problems require complex constraints and generalizations so that most of the tools and techniques developed for markets in the last several decades do not seem to be applicable, and hence the corresponding fair-division problems remain unresolved. This project aims to explore many of these fundamental open questions. The project will support and engage both undergraduate and graduate students from diverse backgrounds and integrate the findings into multiple courses the investigator teaches.Unlike markets, in fair-division problems items are both goods (e.g., cake) and bads (e.g., chores), and allocation needs to satisfy additional constraints, e.g., students are assigned to exactly one school. The main research thrust of the project is to understand the structure and computational complexity of competitive equilibrium of (i) goods and bads, (ii) constrained allocation, (iii) divisible and indivisible items, and their various combinations. The challenges posed are of fundamental importance not only in fair division but also in equilibrium computation, mechanism design, and continuous and discrete optimization. Work on this project will bring significant algorithmic and complexity-theoretic insights into problems from these diverse areas. The techniques developed will contribute to the burgeoning literature on approximation, non-convex optimization, mathematical programming, scheduling, and auction theory, and will open up new avenues for further exploration.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.