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

Rensselaer Polytechnic Institute, Troy NY

Investigators

Abstract

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.