Conference proceeding
A Truthful Cardinal Mechanism for One-Sided Matching
PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), pp.2096-2113
01 Jan 2020
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 v(i,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 v(i,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.
Metrics
3 Record Views
Details
- Title
- A Truthful Cardinal Mechanism for One-Sided Matching
- Creators
- Rediet Abebe - Harvard UniversityRichard Cole - NYU, Courant Inst, New York, NY 10003 USAVasilis Gkatzelis - Drexel UniversityJason D. Hartline - Northwestern Univ, Comp Sci Dept, Evanston, IL 60208 USAACM
- Publication Details
- PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), pp.2096-2113
- Conference
- THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), 31st
- Publisher
- Assoc Computing Machinery
- Number of pages
- 18
- Grant note
- CCF-1618502; CCF-1527568; CCF-1909538; CCF-1755955 / NSF; National Science Foundation (NSF) Facebook; Facebook Inc
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Identifiers
- 991021868729504721
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Computer Science, Theory & Methods