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

职业：AF：通过竞争均衡实现公平分配的新算法基础

• 批准号: 1942321
• 负责人: Jugal Garg
• 金额: $ 50.51万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-02-01 至 2025-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1942321&HistoricalAwards=false
• 关键词: CAREER; AF; New; Algorithmic; Foundations

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.

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

项目成果

Fair and Efficient Allocations under Subadditive Valuations

次加性估值下的公平高效配置

• 发表时间: 2021
• 期刊: The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21
• 作者: Chaudhury, Bhaskar Ray;Garg, Jugal;Mehta, Ruta
• 通讯作者: Mehta, Ruta

EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number

EFX：一种更简单的方法和通过 Rainbow Cycle Number 提供的（几乎）最佳保证

• DOI: 10.1145/3580507.3597799
• 发表时间: 2023
• 期刊: ACM
• 作者: Akrami, Hannaneh;Alon, Noga;Chaudhury, Bhaskar Ray;Garg, Jugal;Mehlhorn, Kurt;Mehta, Ruta
• 通讯作者: Mehta, Ruta

Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness

家务劳动的竞争均衡：组合算法和硬度

• DOI: 10.1145/3490486.3538255
• 发表时间: 2022
• 期刊: EC '22: Proceedings of the 23rd ACM Conference on Economics and Computation
• 作者: Chaudhury, Bhaskar Ray;Garg, Jugal;McGlaughlin, Peter;Mehta, Ruta
• 通讯作者: Mehta, Ruta

Fair and Efficient Allocations of Chores under Bivalued Preferences

双值偏好下公平高效的家务分配

• DOI: 10.1609/aaai.v36i5.20436
• 发表时间: 2022
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Garg, Jugal;Murhekar, Aniket;Qin, John
• 通讯作者: Qin, John

Fair Division of Indivisible Goods for a Class of Concave Valuations

一类凹估值的不可分割商品的公平划分

• DOI: 10.1613/jair.1.12911
• 发表时间: 2022
• 期刊: Journal of Artificial Intelligence Research
• 影响因子: 5
• 作者: Chaudhury, Bhaskar Ray;Cheung, Yun Kuen;Garg, Jugal;Garg, Naveen;Hoefer, Martin;Mehlhorn, Kurt
• 通讯作者: Mehlhorn, Kurt