Computing Equilibrium in Matching Markets
Computing Equilibrium in Matching Markets
复制标题
匹配市场中的计算均衡
DOI：
10.1145/3033274.3085150
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
É. Tardos
中科院分区：
文献类型：
--
作者：
S. Alaei;Pooya Jalaly;É. Tardos
匹配市场的市场均衡为没有金钱的匹配问题和对物品有偏好的代理人提供了一个直观而公平的解决方案。这种匹配市场可以被视为费舍尔市场的一个变体，尽管有相当特殊的代理人偏好。这些偏好可以用分段线性凹(PLC)函数来描述，然而，这些函数是不可分的(由于每个代理只要求一个物品)，不是单调的，并且不满足总的替代性质--物品的价格上涨会导致对物品的需求增加。Devanur和Kannan在FOCS 08中指出，在具有固定数量的产品和一般PLC偏好的市场中，市场出清价格可以在多项式时间内找到。他们还考虑了代理数量固定(而不是物品数量固定)的Fischer市场，并给出了这种情况下的一个多项式时间算法，如果偏好是物品的可分函数，除了是PLC函数。我们的主要结果是在固定数量的不同代理人偏好的匹配市场中找到市场出清价格的多项式时间算法，尽管匹配市场对应的效用是不可分的。对于有固定数量不同商品的市场匹配问题，我们还给出了一个更简单的算法。
Market equilibria of matching markets offer an intuitive and fair solution for matching problems without money with agents who have preferences over the items. Such a matching market can be viewed as a variation of Fisher market, albeit with rather peculiar preferences of agents. These preferences can be described by piece-wise linear concave (PLC) functions, which however, are not separable (due to each agent only asking for one item), are not monotone, and do not satisfy the gross substitute property-- increase in price of an item can result in increased demand for the item. Devanur and Kannan in FOCS 08 showed that market clearing prices can be found in polynomial time in markets with fixed number of items and general PLC preferences. They also consider Fischer markets with fixed number of agents (instead of fixed number of items), and give a polynomial time algorithm for this case if preferences are separable functions of the items, in addition to being PLC functions. Our main result is a polynomial time algorithm for finding market clearing prices in matching markets with fixed number of different agent preferences, despite that the utility corresponding to matching markets is not separable. We also give a simpler algorithm for the case of matching markets with fixed number of different items.