Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness
Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness
复制标题
家务劳动的竞争均衡：组合算法和硬度
DOI：
10.1145/3490486.3538255
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Mehta, Ruta
中科院分区：
文献类型：
--
作者：
Chaudhury, Bhaskar Ray;Garg, Jugal;McGlaughlin, Peter;Mehta, Ruta
我们研究的计算复杂性，找到一个竞争性的均衡（CE）的家务时，代理有线性偏好。CE是用于在代理之间分配一组项目的最优选机制之一。等收入CE（CEEI）、Fisher和Arrow-Debreu（交换）是研究分配问题的基本经济模型，其中CEEI是Fisher的特例，Fisher是交换的特例。当物品是商品（给定效用）时，即使在交换模型中，CE集也是凸的，这有助于所有这些模型的几个组合多项式时间算法（从Devanur，Papadimitriou，Saberi和Vazirani的开创性工作开始[2]）。与此形成鲜明对比的是，当项目是杂务（给出负效用）时，即使在CEEI模型中，CE集也是已知的非凸和不连通的。此外，没有组合算法或硬度结果已知这些模型。在本文中，我们给出了两个主要结果CE与家务：
We study the computational complexity of finding a competitive equilibrium (CE) with chores when agents have linear preferences. CE is one of the most preferred mechanisms for allocating a set of items among agents. CE with equal incomes (CEEI), Fisher, and Arrow-Debreu (exchange) are the fundamental economic models to study allocation problems, where CEEI is a special case of Fisher and Fisher is a special case of exchange. When the items are goods (giving utility), the CE set is convex even in the exchange model, facilitating several combinatorial polynomial-time algorithms (starting with the seminal work of Devanur, Papadimitriou, Saberi and Vazirani [2]) for all of these models. In sharp contrast, when the items are chores (giving disutility), the CE set is known to be non-convex and disconnected even in the CEEI model. Further, no combinatorial algorithms or hardness results are known for these models. In this paper, we give two main results for CE with chores:
登录
查看更多内容
DOI：
10.2139/ssrn.2914241
发表时间：
2017-02
期刊：
National Research University Higher School of Economics Research Paper Series
影响因子：
--
作者：
Anna Bogomolnaia;H. Moulin;Fedor Sandomirskiy;E. Yanovskaya
通讯作者：
Anna Bogomolnaia;H. Moulin;Fedor Sandomirskiy;E. Yanovskaya
DOI：
10.1287/moor.2023.1361
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Simina Brânzei;Fedor Sandomirskiy
通讯作者：
Fedor Sandomirskiy
一类可分离凸目标最小成本流问题的强多项式算法
DOI：
--
发表时间：
2011
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
László A. Végh
通讯作者：
László A. Végh
混合甘露的竞争性分配
DOI：
10.1137/1.9781611976465.85
发表时间：
2021
期刊：
ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
--
作者：
Bhaskar Ray Chaudhury, Jugal Garg
通讯作者：
Bhaskar Ray Chaudhury, Jugal Garg
使用混合甘露计算竞争均衡
DOI：
--
发表时间：
2020
期刊：
AAMAS Conference proceedings
影响因子：
--
作者：
Garg, Jugal;McGlaughlin, Peter
通讯作者：
McGlaughlin, Peter