Improving Welfare in One-Sided Matchings using Simple Threshold Queries
Authors: Thomas Ma, Vijay Menon, Kate Larson
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 some desirable matching property, while also achieving a good approximation to the optimal welfare among all matchings satisfying that property. Overall, our results show how we can improve welfare by even non-adaptively asking agents for just one bit of extra information per object. [...] Theorem 1. Let X denote one of the properties in the set {Pareto-optimal, rank-maximal, max-cardinality rankmaximal, and fair}. Let A be a deterministic ordinal algorithm that always produces a matching that satisfies property X. If there are n agents with unit-sum valuation functions, then L(A) Ω(n2). If there are n agents with unit-range valuation functions then L(A) Ω(n). Moreover, these bounds are asymptotically tight. |
| Researcher Affiliation | Academia | Thomas Ma1 , Vijay Menon2 , Kate Larson2 1Department of Computer Science, University of Toronto 2David R. Cheriton School of Computer Science, University of Waterloo thomas.ma@mail.utoronto.ca, {vijay.menon, kate.larson}@uwaterloo.ca |
| Pseudocode | Yes | Algorithm 1 Welfare Optimal Priority-p Matching [...] Algorithm 2 [...] Algorithm 3 [...] Algorithm 4 |
| Open Source Code | No | The paper is theoretical and does not mention releasing open-source code for the described methodology or provide links to any code repositories. |
| Open Datasets | No | The paper is theoretical and does not report on experiments conducted using a specific dataset. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware; thus, no hardware specifications are provided. |
| Software Dependencies | No | The paper describes algorithms theoretically but does not mention any specific software dependencies or versions required for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical and describes algorithms and proofs; it does not include details about an experimental setup, hyperparameters, or system-level training settings. |