发帖
雷达卡
摘要翻译：
经典Hylland-Zeckhauser方案的Arrow-Debreu推广--本文称之为ADHZ--具有自然的应用，但也有不承认均衡的实例。通过引入近似，我们定义了$\epsilon$-近似ADHZ模型，并给出了以下结果。*线性效用函数下平衡的存在性。证明了该平衡点满足Pareto最优性、近似无嫉妒性和近似弱核稳定性。*对于二分的，更一般的是双值的，效用的情况下，一个$ε-近似ADHZ平衡的组合多项式时间算法。*ADHZ的一个例子，具有二分效用和一个强连接的需求图，它不承认均衡。Hosseini和Vazirani提出了（大量的）基于Nash讨价还价的匹配市场模型，因为计算HZ的均衡可能是非常困难的，也因为将HZ扩展到更一般的效用函数是困难的，所以Hosseini和Vazirani提出了（大量的）基于Nash讨价还价的匹配市场模型。对于它们的线性Arrow-Debreu-Nash讨价还价单边匹配市场(1LAD)模型的二分效用情形，我们给出了一个组合的强多项式时间算法，并证明了该算法允许有理凸规划。
---
英文标题：
《One-Sided Matching Markets with Endowments: Equilibria and Algorithms》
---
作者：
Jugal Garg, Thorben Tr\"obst, Vijay V. Vazirani
---
最新提交年份：
2021
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Computer Science and Game Theory 计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Economics 经济学
二级分类：Theoretical Economics 理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--
---
英文摘要：
The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme for a one-sided matching market -- called ADHZ in this paper -- has natural applications but has instances which do not admit equilibria. By introducing approximation, we define the $\epsilon$-approximate ADHZ model, and we give the following results. * Existence of equilibrium under linear utility functions. We prove that the equilibrium satisfies Pareto optimality, approximate envy-freeness, and approximate weak core stability. * A combinatorial polynomial-time algorithm for an $\epsilon$-approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities. * An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium. Since computing an equilibrium for HZ is likely to be highly intractable and because of the difficulty of extending HZ to more general utility functions, Hosseini and Vazirani proposed (a rich collection of) Nash-bargaining-based matching market models. For the dichotomous-utilities case of their model linear Arrow-Debreu Nash bargaining one-sided matching market (1LAD), we give a combinatorial, strongly polynomial-time algorithm and show that it admits a rational convex program.
---
PDF链接：
https://arxiv.org/pdf/2009.10320
京公网安备 11010802022788号
