A truthful cardinal mechanism for one-sided matching

Rediet Abebe, Richard Cole, Vasilis Gkatzelis, Jason D. Hartline

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We revisit the well-studied problem of designing mechanisms for one-sided matching markets, where a set of n agents needs to be matched to a set of n heterogeneous items. Each agent i has a value vi,j for each item j, and these values are private information that the agents may misreport if doing so leads to a preferred outcome. Ensuring that the agents have no incentive to misreport requires a careful design of the matching mechanism, and mechanisms proposed in the literature mitigate this issue by eliciting only the ordinal preferences of the agents, i.e., their ranking of the items from most to least preferred. However, the efficiency guarantees of these mechanisms are based only on weak measures that are oblivious to the underlying values. In this paper we achieve stronger performance guarantees by introducing a mechanism that truthfully elicits the full cardinal preferences of the agents, i.e., all of the vi,j values. We evaluate the performance of this mechanism using the much more demanding Nash bargaining solution as a benchmark, and we prove that our mechanism significantly outperforms all ordinal mechanisms (even non-truthful ones). To prove our approximation bounds, we also study the population monotonicity of the Nash bargaining solution in the context of matching markets, providing both upper and lower bounds which are of independent interest.

Original languageEnglish (US)
Title of host publication31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
EditorsShuchi Chawla
PublisherAssociation for Computing Machinery
Pages2096-2113
Number of pages18
ISBN (Electronic)9781611975994
StatePublished - 2020
Event31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States
Duration: Jan 5 2020Jan 8 2020

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2020-January

Conference

Conference31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
CountryUnited States
CitySalt Lake City
Period1/5/201/8/20

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A truthful cardinal mechanism for one-sided matching'. Together they form a unique fingerprint.

  • Cite this

    Abebe, R., Cole, R., Gkatzelis, V., & Hartline, J. D. (2020). A truthful cardinal mechanism for one-sided matching. In S. Chawla (Ed.), 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 (pp. 2096-2113). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2020-January). Association for Computing Machinery.