Improving Welfare in One-sided Matching using Simple Threshold Queries
- URL: http://arxiv.org/abs/2011.13977v2
- Date: Mon, 12 Jul 2021 14:36:16 GMT
- Title: Improving Welfare in One-sided Matching using Simple Threshold Queries
- Authors: Thomas Ma, Vijay Menon, Kate Larson
- Abstract summary: We study one-sided matching problems where $n$ agents have preferences over $m$ objects.
We focus on learning more about their cardinal preferences using simple threshold queries.
- Score: 9.270928705464193
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study one-sided matching problems where $n$ agents have preferences over
$m$ objects and each of them need to be assigned to at most one object. Most
work on such problems assume that the agents only have ordinal preferences and
usually the goal in them is to compute a matching that satisfies some notion of
economic efficiency. However, in reality, agents may have some preference
intensities or cardinal utilities that, e.g., indicate that they like an object
much more than another object, and not taking these into account can result in
a loss in welfare. While one way to potentially account for these is to
directly ask the agents for this information, such an elicitation process is
cognitively demanding. Therefore, we focus on learning more about their
cardinal preferences using simple threshold queries which ask an agent if they
value an object greater than a certain value, and use this in turn to come up
with algorithms that produce a matching that, for a particular economic notion
$X$, satisfies $X$ and also achieves a good approximation to the optimal
welfare among all matchings that satisfy $X$. We focus on several notions of
economic efficiency, and look at both adaptive and non-adaptive algorithms.
Overall, our results show how one can improve welfare by even non-adaptively
asking the agents for just one bit of extra information per object.
Related papers
- Satisficing Exploration for Deep Reinforcement Learning [26.73584163318647]
In complex environments that approach the vastness and scale of the real world, attaining optimal performance may in fact be an entirely intractable endeavor.
Recent work has leveraged tools from information theory to design agents that deliberately forgo optimal solutions in favor of sufficiently-satisfying or satisficing solutions.
We extend an agent that directly represents uncertainty over the optimal value function allowing it to both bypass the need for model-based planning and to learn satisficing policies.
arXiv Detail & Related papers (2024-07-16T21:28:03Z) - Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
In bandit best-arm identification, an algorithm is tasked with finding the arm with highest mean reward with a specified accuracy as fast as possible.
We study multi-fidelity best-arm identification, in which the can choose to sample an arm at a lower fidelity (less accurate mean estimate) for a lower cost.
Several methods have been proposed for tackling this problem, but their optimality remain elusive, notably due to loose lower bounds on the total cost needed to identify the best arm.
arXiv Detail & Related papers (2024-06-05T08:02:40Z) - Ranking a Set of Objects using Heterogeneous Workers: QUITE an Easy
Problem [54.90613714264689]
We focus on the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of unequal workers.
We propose QUITE, a non-adaptive ranking algorithm that jointly estimates workers' reliabilities and qualities of objects.
arXiv Detail & Related papers (2023-10-03T12:42:13Z) - Experience in Engineering Complex Systems: Active Preference Learning
with Multiple Outcomes and Certainty Levels [1.5257326975704795]
Black-box optimization refers to the problem whose objective function and/or constraint sets are either unknown, inaccessible, or non-existent.
The algorithm so-called Active Preference Learning has been developed to exploit this specific information.
Our approach aims to extend the algorithm in such a way that can exploit further information effectively.
arXiv Detail & Related papers (2023-02-27T15:55:37Z) - Should All Proposals be Treated Equally in Object Detection? [110.27485090952385]
The complexity-precision trade-off of an object detector is a critical problem for resource constrained vision tasks.
It is hypothesized that improved detection efficiency requires a paradigm shift, towards the unequal processing of proposals.
This results in better utilization of available computational budget, enabling higher accuracy for the same FLOPS.
arXiv Detail & Related papers (2022-07-07T18:26:32Z) - A new perspective on classification: optimally allocating limited
resources to uncertain tasks [4.169130102668252]
In credit card fraud detection, for instance, a bank can only assign a small subset of transactions to their fraud investigations team.
We argue that using classification to address task uncertainty is inherently suboptimal as it does not take into account the available capacity.
We present a novel solution using learning to rank by directly optimizing the assignment's expected profit given limited capacity.
arXiv Detail & Related papers (2022-02-09T10:14:45Z) - Consequences of Misaligned AI [12.879600368339393]
This paper argues that we should view the design of reward functions as an interactive and dynamic process.
We show how modifying the setup to allow reward functions that reference the full state or allowing the principal to update the proxy objective over time can lead to higher utility solutions.
arXiv Detail & Related papers (2021-02-07T19:34:04Z) - Necessarily Optimal One-Sided Matchings [49.0517583218216]
We study the classical problem of matching $n$ agents to $n$ objects, where the agents have ranked preferences over the objects.
Instead of asking the agents to report their complete preferences, our goal is to learn a desirable matching from partial preferences.
We design efficient algorithms to check if a given matching is NPO or NRM, and to check whether such a matching exists given top-$k$ partial preferences.
arXiv Detail & Related papers (2020-07-17T16:01:34Z) - Sequential Transfer in Reinforcement Learning with a Generative Model [48.40219742217783]
We show how to reduce the sample complexity for learning new tasks by transferring knowledge from previously-solved ones.
We derive PAC bounds on its sample complexity which clearly demonstrate the benefits of using this kind of prior knowledge.
We empirically verify our theoretical findings in simple simulated domains.
arXiv Detail & Related papers (2020-07-01T19:53:35Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers.
We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
arXiv Detail & Related papers (2020-02-26T16:19:09Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.