论文标题
使用简单的阈值查询以单面匹配改善福利
Improving Welfare in One-sided Matching using Simple Threshold Queries
论文作者
论文摘要
我们研究了单方面的匹配问题，其中$ n $ agents比$ m $对象具有偏好，并且每个对象都需要将它们分配给最多一个对象。在此类问题上的大多数工作都假定代理人只有有序偏好，通常目标是计算满足经济效率概念的匹配。但是，实际上，代理可能具有一些偏好强度或枢机主教公用事业，例如，表明它们比另一个对象更喜欢对象，而不考虑这些对象可能会导致福利损失。虽然一种潜在地解释这些信息的方法是直接向代理询问这些信息，但这种启发过程在认知要求上是要求的。因此，我们专注于使用简单的阈值查询来了解有关他们的主要偏好的更多信息，该查询询问代理是否重视一个大于一定价值的对象，然后使用它来提出算法，这些算法会产生一种匹配的算法，对于特定的经济概念$ x $，满足$ x $，并且可以满足所有满足$ x $ $ x $的最佳福利。我们专注于几种经济效率的概念，并研究适应性和非自适应算法。总体而言，我们的结果表明，即使是非适应性的，每个对象的额外信息也可以通过非适应性地向代理人提出一点点信息来提高福利。
We study one-sided matching problems where $n$ agents have preferences over $m$ objects and each of them need to be assigned to at most one object. Most work on such problems assume that the agents only have ordinal preferences and usually the goal in them is to compute a matching that satisfies some notion of economic efficiency. However, in reality, agents may have some preference intensities or cardinal utilities that, e.g., indicate that they like an object much more than another object, and not taking these into account can result in a loss in welfare. While one way to potentially account for these is to directly ask the agents for this information, such an elicitation process is cognitively demanding. Therefore, we focus on learning more about their cardinal preferences using simple threshold queries which ask an agent if they value an object greater than a certain value, and use this in turn to come up with algorithms that produce a matching that, for a particular economic notion $X$, satisfies $X$ and also achieves a good approximation to the optimal welfare among all matchings that satisfy $X$. We focus on several notions of economic efficiency, and look at both adaptive and non-adaptive algorithms. Overall, our results show how one can improve welfare by even non-adaptively asking the agents for just one bit of extra information per object.
