TY - GEN

T1 - A truthful cardinal mechanism for one-sided matching

AU - Abebe, Rediet

AU - Cole, Richard

AU - Gkatzelis, Vasilis

AU - Hartline, Jason D.

N1 - Funding Information:
∗Rediet Abebe was supported in part by a Facebook scholarship. Richard Cole was supported in part by NSF grants CCF-1527568 and CCF-1909538. Vasilis Gkatzelis was supported in part by NSF grant CCF-1755955. Jason Hartline was supported by NSF grant CCF-1618502 and part of this work took place while he was visiting Harvard University.
Publisher Copyright:
Copyright © 2020 by SIAM

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85084069707&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85084069707&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85084069707

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2096

EP - 2113

BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

A2 - Chawla, Shuchi

PB - Association for Computing Machinery

T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

Y2 - 5 January 2020 through 8 January 2020

ER -