Proceedings

Improving Welfare in One-Sided Matchings using Simple Threshold Queries

Thomas Ma, Vijay Menon, Kate Larson

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 321-327.

https://doi.org/10.24963/ijcai.2021/45

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

Abstract

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.

Thomas Ma, Vijay Menon, and Kate Larson. 2021. Improving Welfare in One-Sided Matchings using Simple Threshold Queries. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 321–327. https://doi.org/10.24963/ijcai.2021/45
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards