Improving Welfare in One-Sided Matchings using Simple Threshold Queries

Improving Welfare in One-Sided Matchings using Simple Threshold Queries

Thomas Ma, Vijay Menon, Kate Larson

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 321-327. https://doi.org/10.24963/ijcai.2021/45

We study one-sided matching problems where each agent must be assigned at most one object. In this classic problem it is often assumed that agents specify only ordinal preferences over objects and the goal is to return a matching that satisfies some desirable property such as Pareto optimality or rank-maximality. However, agents may have cardinal utilities describing their preference intensities and ignoring this can result in welfare loss. We investigate how to elicit additional cardinal information from agents using simple threshold queries and use it in turn to design algorithms that return a matching satisfying a desirable matching property, while also achieving a good approximation to the optimal welfare among all matchings satisfying that property. Overall, our results show how one can improve welfare by even non-adaptively asking agents for just one bit of extra information per object.
Keywords:
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Resource Allocation