Satiation in Fisher Markets and Approximation of Nash Social Welfare
Satiation in Fisher Markets and Approximation of Nash Social Welfare
复制标题
水产市场的饱和度和纳什社会福利的近似
DOI：
10.1287/moor.2019.0129
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
K. Mehlhorn
中科院分区：
文献类型：
--
作者：
J. Garg;M. Hoefer;K. Mehlhorn
本文研究了线性Fisher市场的饱和性。在这些市场中，卖方有收益限制，买方有效用限制。除了在经济学中的应用，它们出现在最大化纳什社会福利的背景下，当分配不可分割的项目给代理人。与具有收益限制或效用限制的市场相反，具有这两种限制的市场以前没有被研究过。它们有着本质上不同的性质。一般来说，竞争均衡的存在性是不能保证的。我们确定了市场的一个自然属性（称为货币清算），这意味着存在。我们表明，一组平衡并不总是凸的，回答了文献中提出的一个问题。我们设计了一个FPTAS来计算近似平衡，并证明计算精确平衡的问题在于复杂性类连续局部搜索（[公式：见文本];即，多项式局部搜索（[Formula：see text]）和有向图上的多项式奇偶参数（[Formula：see text]）的交集。对于一个常数的买家或货物，我们给出了一个多项式时间算法来计算一个精确的平衡。我们展示了如何（近似）均衡可以四舍五入，并提供了第一个常数因子近似算法（因子为2.404），以最大限度地提高纳什社会福利时，代理人有上限的线性（也称为非线性添加剂）估值。最后，我们显着提高了[公式：见正文]的加法赋值的近似难度。资助：J. Garg由国家科学基金会资助[Grant CCF-1942321（CAREER）]。M.霍费尔得到了德国研究共同体的支持[赠款Ho 3831/5-1、Ho 3831/6-1和Ho 3831/7-1]。
We study linear Fisher markets with satiation. In these markets, sellers have earning limits, and buyers have utility limits. Beyond applications in economics, they arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not guaranteed. We identify a natural property of markets (termed money clearing) that implies existence. We show that the set of equilibria is not always convex, answering a question posed in the literature. We design an FPTAS to compute an approximate equilibrium and prove that the problem of computing an exact equilibrium lies in the complexity class continuous local search ([Formula: see text]; i.e., the intersection of polynomial local search ([Formula: see text]) and polynomial parity arguments on directed graphs ([Formula: see text])). For a constant number of buyers or goods, we give a polynomial-time algorithm to compute an exact equilibrium. We show how (approximate) equilibria can be rounded and provide the first constant-factor approximation algorithm (with a factor of 2.404) for maximizing Nash social welfare when agents have capped linear (also known as budget-additive) valuations. Finally, we significantly improve the approximation hardness for additive valuations to [Formula: see text]. Funding: J. Garg was supported by the National Science Foundation [Grant CCF-1942321 (CAREER)]. M. Hoefer was supported by Deutsche Forschungsgemeinschaft [Grants Ho 3831/5-1, Ho 3831/6-1, and Ho 3831/7-1].
登录
查看更多内容
DOI：
10.1145/3313276.3316340
发表时间：
2018-09
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
J. Garg;László A. Végh
通讯作者：
J. Garg;László A. Végh
一类凹估值的不可分割商品的公平划分
影响因子：
5
作者：
Chaudhury, Bhaskar Ray;Cheung, Yun Kuen;Garg, Jugal;Garg, Naveen;Hoefer, Martin;Mehlhorn, Kurt
通讯作者：
Mehlhorn, Kurt
渔市的收入和效用限制
影响因子：
1.2
作者：
Bei, Xiaohui;Garg, Jugal;Hoefer, Martin;Mehlhorn, Kurt
通讯作者：
Mehlhorn, Kurt
论不可分割物品的公平分割
影响因子：
--
作者：
Chaudhury, Bhaskar Ray;Cheung, Yun Kuen;Garg, Jugal;Garg, Naveen;Hoefer, Martin;Mehlhorn, Kurt
通讯作者：
Mehlhorn, Kurt