Earning and Utility Limits in Fisher Markets
Earning and Utility Limits in Fisher Markets
复制标题
渔市的收入和效用限制
DOI：
10.1145/3340234
复制
发表时间：
2019
影响因子：
1.2
通讯作者：
Mehlhorn, Kurt
中科院分区：
文献类型：
--
作者：
Bei, Xiaohui;Garg, Jugal;Hoefer, Martin;Mehlhorn, Kurt
收入极限和效用极限是经典费雪市场模型的新内容。有收入限制的卖主对他们的收入有限制，如果收入超过这个限制，他们就会减少给市场带来的供应。有效用限制的买家对他们想要获得的效用量有一个上限，如果效用超过上限，他们就会降低给市场带来的预算。具有这些属性的市场可以具有具有不同特征的多个均衡。我们分析了具有线性和消费约束效用的市场中的收入限制和效用限制。对于具有收入限制和支出约束效用的市场，我们证明了均衡价格向量形成一个格，并且在非简并市场中购买者的支出是唯一的。我们提供了一种基于尺度的算法来计算时间o （n3）的均衡，其中为智能体的数量，在效用函数的区段上的r≥na界，u为市场表示中的最大整数。我们展示了如何在多项式时间内将任何均衡细化为具有最小价格的均衡或具有最大价格的均衡（如果存在）。此外，我们的算法可用于在多项式时间内获得最大化纳什社会福利的2逼近，在多单位市场中，不可分割的物品有多个副本。对于具有效用限制和线性效用的市场，我们给出了类似的结果——价格向量的晶格结构，非退化市场中分配的唯一性，以及获得具有最小和最大价格的均衡的多项式时间改进过程。我们用相关计算问题的硬度结果来补充这些积极的结果。我们证明了计算一个社会福利最大化的市场均衡是np -困难的，而对于每个购买者和每种商品都有单独的满足点的效用函数的市场均衡是ppad -困难的。
Earning limits and utility limits are novel aspects in the classic Fisher market model. Sellers with earning limits have bounds on their income and lower the supply they bring to the market if income exceeds the limit. Buyers with utility limits have an upper bound on the amount of utility that they want to derive and lower the budget they bring to the market if utility exceeds the limit. Markets with these properties can have multiple equilibria with different characteristics.We analyze earning limits and utility limits in markets with linear and spending-constraint utilities. For markets with earning limits and spending-constraint utilities, we show that equilibrium price vectors form a lattice and the spending of buyers is unique in non-degenerate markets. We provide a scaling-based algorithm to compute an equilibrium in timeO(n3ℓ log (ℓ +nU)), wherenis the number of agents, ℓ ≥na bound on the segments in the utility functions, andUthe largest integer in the market representation. We show how to refine any equilibrium in polynomial time to one with minimal prices or one with maximal prices (if it exists). Moreover, our algorithm can be used to obtain in polynomial time a 2-approximation for maximizing Nash social welfare in multi-unit markets with indivisible items that come in multiple copies.For markets with utility limits and linear utilities, we show similar results—lattice structure of price vectors, uniqueness of allocation in non-degenerate markets, and polynomial-time refinement procedures to obtain equilibria with minimal and maximal prices. We complement these positive results with hardness results for related computational questions. We prove that it is NP-hard to compute a market equilibrium that maximizes social welfare, and it is PPAD-hard to find any market equilibrium with utility functions with separate satiation points for each buyer and each good.
登录
查看更多内容
一类具有覆盖约束的新型组合市场：算法和应用
DOI：
--
发表时间：
2015
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Nikhil R. Devanur;J. Garg;R. Mehta;V. Vazirani;Sadra Yazdanbod
通讯作者：
Sadra Yazdanbod
针对一次性和持续市场问题的快速收敛塔顿算法
DOI：
--
发表时间：
2008
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
R. Cole;L. Fleischer
通讯作者：
L. Fleischer
一类可分离凸目标最小成本流问题的强多项式算法
DOI：
--
发表时间：
2011
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
László A. Végh
通讯作者：
László A. Végh
艾森伯格-盖尔市场：算法和博弈论属性
DOI：
10.1016/j.geb.2008.11.011
发表时间：
2010
期刊：
Games Econ. Behav.
影响因子：
--
作者：
K. Jain;V. Vazirani
通讯作者：
V. Vazirani
具有生产的完美价格歧视市场模型及其有理凸规划
DOI：
10.1287/moor.1110.0517
发表时间：
2011
期刊：
Math. Oper. Res.
影响因子：
--
作者：
G. Goel;V. Vazirani
通讯作者：
V. Vazirani