RI: Small: The Surprising Power of Sequential Fair Allocation Mechanisms

研究团队将分析在没有资金的市场中进行资源配置的算法，也就是说，寻找在法律或道德原因不允许使用资金的领域进行投资的机制。例如，大学不会将课程席位出售给出价最高的人，学术同行评审系统也不会根据定价机制分配审稿人。在这种情况下，使用集中分配机制来分配资源。为了实用，这些机制需要快速且适应性强。此外，他们必须保证资源的有效分配（物品分配给那些将从中受益最多的人）和公平分配（个人和团体不会获得不成比例的一小部分利益或承担不公平的家务）。研究小组将研究一个简单而有吸引力的范例：顺序分配机制。在顺序分配机制中，用户依次执行操作（例如，获取未分配的项，或从其他人那里窃取项），直到满足所需的条件（例如，所有项都已分配）。研究小组将证明，尽管顺序分配机制结构简单，但它可以实际应用于许多现实问题，同时提供公平和效率保证。研究小组将调查顺序机制提供的保证类型，以及我们可以应用它们的领域类型。该研究团队将与学术同行评议平台OpenReview、学术会议组织者和大学管理部门合作，测试和实施其研究结果。大规模资源分配是多智能体系统设计中的一个关键问题。研究人员开发了越来越复杂的算法框架，以保证算法产生的结果既公平又有效。然而，这些算法的复杂性往往阻碍了它们的实际实现，使它们难以适应特定问题领域的需要。为了解决这一缺点，该提案主张采用易于实现和理解的顺序算法技术，而不是复杂的算法框架。该提案审查了顺序分配机制的理论基础，以及他们的应用。研究小组将证明，顺序方法提供了显著的计算加速，并通过仔细的分析，保证了公平性和效率。对于一般代理偏好，众所周知，实现公平和有效的分配是难以计算的；因此，研究团队将关注具体的代理偏好类别，并特别关注子模块估值。子模函数自然出现在各种经济领域；然而，它们的结构特性允许我们依靠基本的组合技术，如矩阵优化和图论。该提案将研究挑选序列，最近在OpenReview平台上实现。该提案还将研究顺序项目转移机制（称为Yankee Swap机制），在课程分配等实际领域具有很强的公平性和效率保证。最后，该提案将研究一个广泛的顺序框架，以处理更复杂的子模块评估类别，包括公平分配家务（如工作班次）。通过该建议开发的技术在各种资源分配领域中具有广泛的应用，例如，会议论文审稿人分配，工作班次分配和课程分配系统。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The research team will analyze algorithms for resource allocation in markets without money, that is, finding mechanisms for investing in domains where the use of money is not allowed for legal or ethical reasons. For example, universities do not sell course seats to the highest bidder, nor do academic peer review systems assign reviewers based on pricing mechanisms. In such cases, centralized allocation mechanisms are used to distribute resources. To be practical, these mechanisms need to be fast and adaptable. In addition, they must guarantee that resources are distributed effectively (items go to those who will benefit most from them) and fairly (individuals and groups do not receive a disproportionately small share of benefits or take on an unfair number of chores). The research team will investigate a simple and appealing paradigm: sequential allocation mechanisms. In a sequential allocation mechanism, users take actions in turns (for example, taking an unassigned item, or stealing an item from someone else), until some desired condition is met (for example, all items have been assigned). The research team will show that despite their simple structure, sequential allocation mechanisms can be practically used in many real-world problems, while offering fairness and efficiency guarantees. The research team will investigate the types of guarantees that sequential mechanisms offer, and the types of domains we can apply them to. The research team will collaborate with OpenReview, an academic peer reviewing platform, academic conference organizers, and with university administration, to test and implement its findings. Large-scale allocation of resources is a key problem in the design of multi-agent systems. Researchers have developed increasingly complex algorithmic frameworks to guarantee that the algorithms produce outcomes that are both fair and efficient. However, the complexity of these algorithms often precludes their practical implementation and makes them difficult to adapt to the needs of specific problem domains. To address this shortcoming, instead of complex algorithmic frameworks, the proposal advocates for sequential algorithmic techniques that are easy to both implement and understand. The proposal examines the theoretical foundations of sequential allocation mechanisms, as well as their applications. The research team will show that the sequential approach offers a significant computational speedup, and via careful analysis, guarantees both fairness and efficiency. For general agent preferences, it is well-known that achieving both fair and efficient allocations is computationally intractable; therefore, the researcher team will focus on specific agent preference classes, with a particular focus on submodular valuations. Submodular functions naturally arise in a variety of economic domains; however, their structural properties allow us to rely on fundamental combinatorial techniques, such as matroid optimization and graph theory. The proposal will investigate picking sequences, with a recent implementation in the OpenReview platform. The proposal will also study sequential item transfer mechanisms (termed Yankee Swap mechanisms), with strong fairness and efficiency guarantees in practical domains, such as course allocation. Finally, the proposal will study a broad sequential framework that handles more complex submodular valuation classes, including the fair allocation of chores (such as work shifts). The techniques developed through this proposal have broad applications in a variety of resource allocation domains, for example, conference paper reviewer assignment, work shift allocation, and course assignment systems.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.