RI: Small: The Surprising Power of Sequential Fair Allocation Mechanisms
RI:小:顺序公平分配机制的惊人力量
基本信息
- 批准号:2327057
- 负责人:
- 金额:$ 59.98万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2023
- 资助国家:美国
- 起止时间:2023-09-15 至 2026-08-31
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
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.
研究小组将分析没有钱的市场中资源分配的算法,也就是说,寻找用于用于法律或道德原因不允许使用货币的域名的机制。例如,大学不会向出价最高的人出售课程席位,学术同行评审系统也不根据定价机制分配审阅者。在这种情况下,用于分配资源的集中式分配机制。要实用,这些机制需要快速且适应能力。此外,他们必须确保有效分配资源(物品将转交给那些将从中受益最多的人(个人和团体不会获得不成比例的福利或不公平的杂务)。研究团队将研究一个简单而有吸引力的范式:顺序分配机制。在顺序分配机制中,用户依次采取行动(例如,选择一个未分配的项目,或从其他人那里窃取项目),直到满足某些所需条件(例如,所有项目都已分配)。研究团队将表明,尽管结构简单,但顺序分配机制实际上可以用于许多现实世界中的问题,同时提供公平和效率保证。研究团队将研究顺序机制提供的保证类型以及我们可以将其应用于的域类型。研究团队将与OpenReview合作,OpenReview是一个学术同行审查平台,学术会议组织者以及大学管理,以测试和实施其发现。资源的大规模分配是多代理系统设计中的关键问题。研究人员已经开发了越来越复杂的算法框架,以确保算法产生既公平又有效的结果。但是,这些算法的复杂性通常排除了它们的实际实施,因此很难适应特定问题领域的需求。为了解决这种缺点,而不是复杂的算法框架,提倡顺序算法技术的建议倡导既易于实施和理解。该提案研究了顺序分配机制及其应用的理论基础。研究团队将表明,顺序方法提供了显着的计算加速,并通过仔细的分析可以保证公平和效率。对于一般代理偏好,众所周知,实现公平和有效的分配在计算上是棘手的。因此,研究人员团队将专注于特定的代理偏好类别,并特别关注子估值。自然出现在各种经济领域中;但是,它们的结构属性使我们能够依靠基本组合技术,例如矩阵优化和图理论。 该提案将在OpenReview平台中使用最新的实现来调查选择序列。该提案还将研究顺序的项目转移机制(称为洋基交换机制),并在实用领域(例如课程分配)具有强大的公平性和效率保证。 最后,该提案将研究一个广泛的顺序框架,该框架处理更复杂的估值类别,包括杂务的公平分配(例如工作转移)。通过该提案开发的技术在各种资源分配领域中都有广泛的应用,例如,会议论文审阅者分配,工作转移分配和课程分配系统。该奖项反映了NSF的法定任务,并被认为是值得通过基金会的知识分子优点和更广泛的审查标准通过评估来通过评估来支持的。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Yair Zick其他文献
Context-Aware Fusion for Continuous Biometric Authentication
用于连续生物识别身份验证的上下文感知融合
- DOI:
10.1109/icb2018.2018.00043 - 发表时间:
2018 - 期刊:
- 影响因子:0
- 作者:
Divya Sivasankaran;M. Ragab;T. Sim;Yair Zick - 通讯作者:
Yair Zick
I Will Have Order! Optimizing Orders for Fair Reviewer Assignment
我会订购!
- DOI:
- 发表时间:
2021 - 期刊:
- 影响因子:0
- 作者:
Justin Payan;Yair Zick - 通讯作者:
Yair Zick
A General Framework for Fair Allocation with Matroid Rank Valuations
拟阵排名估值公平分配的通用框架
- DOI:
10.48550/arxiv.2208.07311 - 发表时间:
2022 - 期刊:
- 影响因子:0
- 作者:
V. Viswanathan;Yair Zick - 通讯作者:
Yair Zick
Dividing Good and Better Items Among Agents with Submodular Valuations
在具有子模估值的代理之间分配好的和更好的项目
- DOI:
10.48550/arxiv.2302.03087 - 发表时间:
2023 - 期刊:
- 影响因子:0
- 作者:
Cyrus Cousins;V. Viswanathan;Yair Zick - 通讯作者:
Yair Zick
Finding Fair and E � cient Allocations for Matroid Rank Valuations
为拟阵排名估值寻找公平有效的分配
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
Nawal Benabbou;Mithun Chakraborty;Ayumi Igarashi;Yair Zick - 通讯作者:
Yair Zick
Yair Zick的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
相似国自然基金
靶向Treg-FOXP3小分子抑制剂的筛选及其在肺癌免疫治疗中的作用和机制研究
- 批准号:32370966
- 批准年份:2023
- 资助金额:50 万元
- 项目类别:面上项目
化学小分子激活YAP诱导染色质可塑性促进心脏祖细胞重编程的表观遗传机制研究
- 批准号:82304478
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
靶向小胶质细胞的仿生甘草酸纳米颗粒构建及作用机制研究:脓毒症相关性脑病的治疗新策略
- 批准号:82302422
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
HMGB1/TLR4/Cathepsin B途径介导的小胶质细胞焦亡在新生大鼠缺氧缺血脑病中的作用与机制
- 批准号:82371712
- 批准年份:2023
- 资助金额:49 万元
- 项目类别:面上项目
小分子无半胱氨酸蛋白调控生防真菌杀虫活性的作用与机理
- 批准号:32372613
- 批准年份:2023
- 资助金额:50 万元
- 项目类别:面上项目
相似海外基金
CSR: Small: Leveraging Physical Side-Channels for Good
CSR:小:利用物理侧通道做好事
- 批准号:
2312089 - 财政年份:2024
- 资助金额:
$ 59.98万 - 项目类别:
Standard Grant
NeTS: Small: NSF-DST: Modernizing Underground Mining Operations with Millimeter-Wave Imaging and Networking
NeTS:小型:NSF-DST:利用毫米波成像和网络实现地下采矿作业现代化
- 批准号:
2342833 - 财政年份:2024
- 资助金额:
$ 59.98万 - 项目类别:
Standard Grant
CPS: Small: NSF-DST: Autonomous Operations of Multi-UAV Uncrewed Aerial Systems using Onboard Sensing to Monitor and Track Natural Disaster Events
CPS:小型:NSF-DST:使用机载传感监测和跟踪自然灾害事件的多无人机无人航空系统自主操作
- 批准号:
2343062 - 财政年份:2024
- 资助金额:
$ 59.98万 - 项目类别:
Standard Grant
Collaborative Research: FET: Small: Reservoir Computing with Ion-Channel-Based Memristors
合作研究:FET:小型:基于离子通道忆阻器的储层计算
- 批准号:
2403559 - 财政年份:2024
- 资助金额:
$ 59.98万 - 项目类别:
Standard Grant
政治参加の縮小期における政治的平等と政治資金
政治参与下降时期的政治平等与政治资本
- 批准号:
24KJ2165 - 财政年份:2024
- 资助金额:
$ 59.98万 - 项目类别:
Grant-in-Aid for JSPS Fellows