RI: Small: Algorithmic Mechanism Design for Multi-Type Resource Allocation

RI：Small：多类型资源分配的算法机制设计

• 批准号: 1716333
• 负责人: Lirong Xia
• 金额: $ 37.35万
• 依托单位: Rensselaer Polytechnic Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-08-15 至 2022-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1716333&HistoricalAwards=false
• 关键词: RI; Small; Algorithmic; Mechanism; Design

Allocating indivisible items to multiple agents without monetary transfer is a pressing problem in our society. In many situations, items are categorized into multiple types and each agent must get at least one item per type. Such problems are called multi-type resource allocation (MTRA). For example, MTRA arises in allocating courses to students, allocating computational resources to users in cloud computing, allocating medical resources to patients, as well as in multi-type exchange market and centralized welfare programs that involve multiple sub-programs. Unfortunately, most previous research overlook information regarding resource type, and are thus hindered by three barriers: preference bottleneck, computational bottleneck, and threats of agents' strategic behavior. The project aims at establishing theoretical and algorithmic foundations of mechanism design for MTRA with the help of Artificial Intelligence. The newly designed mechanisms will improve the economic efficiency and computational efficiency of resource allocation in multiagent systems, socio-economics systems, and operations research.In doing so, the researcher will design and evaluate novel graphical languages to address the preference bottleneck; design novel frameworks for discovering new mechanisms, including sequential allocation mechanisms and extensions of the top-trading-cycles mechanism, to address the computational bottleneck; use game theory to analyze and measure agents' strategic behavior; and use high computational complexity to prevent agents' strategic behavior. Outcomes of the research will be integrated into an open-source Online Preference Reporting and Aggregation (OPRA) system, which serves as a platform to bridge theory, practice, and education.

在不进行货币转移的情况下，将不可分割的物品分配给多个代理人是我们社会的一个紧迫问题。在许多情况下，物品被分类为多个类型，每个代理必须在每个类型中至少获得一个物品。这类问题被称为多类型资源分配(MTRA)。例如，MTRA产生于为学生分配课程，为云计算中的用户分配计算资源，为患者分配医疗资源，以及涉及多个子计划的多类型交流市场和集中式福利计划。遗憾的是，以往的研究大多忽略了关于资源类型的信息，因此受到三个障碍的阻碍：偏好瓶颈、计算瓶颈和主体战略行为的威胁。该项目旨在为利用人工智能进行MTRA的机制设计奠定理论和算法基础。新设计的机制将提高多智能体系统、社会经济系统和运筹学中资源分配的经济效率和计算效率。在此过程中，研究人员将设计和评估新的图形语言来解决偏好瓶颈；设计新的框架来发现新机制，包括顺序分配机制和顶部交易周期机制的扩展，以解决计算瓶颈；使用博弈论来分析和衡量代理的战略行为；以及使用高计算复杂性来防止代理的战略行为。研究结果将被整合到一个开放源码的在线偏好报告和汇总(OPRA)系统中，作为沟通理论、实践和教育的平台。

项目成果

Fair Division Through Information Withholding

通过隐瞒信息进行公平划分

• DOI: 10.1609/aaai.v34i02.5573
• 发表时间: 2020
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Hosseini, Hadi;Sikdar, Sujoy;Vaish, Rohit;Wang, Jun;Xia, Lirong
• 通讯作者: Xia, Lirong

Multi resource allocation with partial preferences

• DOI: 10.1016/j.artint.2022.103824
• 发表时间: 2022-11
• 期刊: Artif. Intell.
• 作者: Haibin Wang;Sujoy Sikdar;Xiaoxi Guo;Lirong Xia;Yongzhi Cao;Hanpin Wang

Equitable Allocations of Indivisible Chore

公平分配不可分割的家务活

• 发表时间: 2020
• 期刊: AAMAS Conference proceedings
• 作者: Freeman, Rupert;Sikdar, Sujoy;Vaish, Rohit;Xia, Lirong
• 通讯作者: Xia, Lirong

Probabilistic serial mechanism for multi-type resource allocation

多类型资源分配的概率串行机制

• DOI: 10.1007/s10458-021-09495-w
• 发表时间: 2020-04
• 期刊: Autonomous Agents and Multi-Agent Systems
• 影响因子: 1.9
• 作者: Xiaoxi Guo;Sujoy Sikdar;Haibin Wang;Lirong Xia;Yongzhi Cao;Hanpin Wang
• 通讯作者: Hanpin Wang

Multi-type Resource Allocation with Partial Preferences

• DOI: 10.1609/aaai.v34i02.5603
• 发表时间: 2019-06
• 期刊: ArXiv
• 作者: Haibin Wang;Sujoy Sikdar;Xiaoxi Guo;Lirong Xia;Yongzhi Cao;Hanpin Wang