From Matching with Diversity Constraints to Matching with Regional
Quotas
- URL: http://arxiv.org/abs/2002.06748v1
- Date: Mon, 17 Feb 2020 02:51:46 GMT
- Title: From Matching with Diversity Constraints to Matching with Regional
Quotas
- Authors: Haris Aziz, Serge Gaspers, Zhaohong Sun, Toby Walsh
- Abstract summary: We present a formal connection between two important axioms on matching with distributional constraints.
We show that it is NP-complete to check whether a feasible and stable outcome for (1) exists.
We conclude that further developments on aspects of hospital-doctor matching with regional quotas will result in corresponding school choice with diversity.
- Score: 51.33676030875284
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the past few years, several new matching models have been proposed and
studied that take into account complex distributional constraints. Relevant
lines of work include (1) school choice with diversity constraints where
students have (possibly overlapping) types and (2) hospital-doctor matching
where various regional quotas are imposed. In this paper, we present a
polynomial-time reduction to transform an instance of (1) to an instance of (2)
and we show how the feasibility and stability of corresponding matchings are
preserved under the reduction. Our reduction provides a formal connection
between two important strands of work on matching with distributional
constraints. We then apply the reduction in two ways. Firstly, we show that it
is NP-complete to check whether a feasible and stable outcome for (1) exists.
Due to our reduction, these NP-completeness results carry over to setting (2).
In view of this, we help unify some of the results that have been presented in
the literature. Secondly, if we have positive results for (2), then we have
corresponding results for (1). One key conclusion of our results is that
further developments on axiomatic and algorithmic aspects of hospital-doctor
matching with regional quotas will result in corresponding results for school
choice with diversity constraints.
Related papers
- Diversify & Conquer: Outcome-directed Curriculum RL via
Out-of-Distribution Disagreement [30.21954044028645]
Reinforcement learning (RL) often faces the challenges of uninformed search problems where the agent should explore without access to the domain knowledge.
This work proposes a new approach for curriculum RL called Diversify for Disagreement & Conquer (D2C)
Unlike previous curriculum learning methods, D2C requires only a few examples of desired outcomes and works in any environment.
arXiv Detail & Related papers (2023-10-30T04:12:19Z) - On Pitfalls of Test-Time Adaptation [82.8392232222119]
Test-Time Adaptation (TTA) has emerged as a promising approach for tackling the robustness challenge under distribution shifts.
We present TTAB, a test-time adaptation benchmark that encompasses ten state-of-the-art algorithms, a diverse array of distribution shifts, and two evaluation protocols.
arXiv Detail & Related papers (2023-06-06T09:35:29Z) - Doubly Constrained Fair Clustering [11.11449872883085]
Group Fairness (GF) and Diversity in Center Selection (DS) are two most prominent demographic representation fairness notions in clustering.
We show that given a constant approximation algorithm for one constraint (GF or DS only) we can obtain a constant approximation solution that satisfies both constraints simultaneously.
We show that both GF and DS are incompatible with a collection of other distance-based fairness notions.
arXiv Detail & Related papers (2023-05-31T01:04:55Z) - Efficient Alternating Minimization Solvers for Wyner Multi-View
Unsupervised Learning [0.0]
We propose two novel formulations that enable the development of computational efficient solvers based the alternating principle.
The proposed solvers offer computational efficiency, theoretical convergence guarantees, local minima complexity with the number of views, and exceptional accuracy as compared with the state-of-the-art techniques.
arXiv Detail & Related papers (2023-03-28T10:17:51Z) - Boosting device-independent cryptography with tripartite nonlocality [0.0]
Device-independent (DI) protocols certify private randomness by observing nonlocal correlations when two or more parties test a Bell inequality.
Here, we consider tripartite DICKA and DIRE protocols based on testing multipartite Bell inequalities.
We show that DICKA and DIRE protocols employing tripartite Bell inequalities can significantly outperform their bipartite counterparts.
arXiv Detail & Related papers (2022-09-26T16:35:03Z) - Optimal Adaptive Strategies for Sequential Quantum Hypothesis Testing [87.17253904965372]
We consider sequential hypothesis testing between two quantum states using adaptive and non-adaptive strategies.
We show that these errors decrease exponentially with decay rates given by the measured relative entropies between the two states.
arXiv Detail & Related papers (2021-04-30T00:52:48Z) - Partition-Guided GANs [63.980473635585234]
We design a partitioner that breaks the space into smaller regions, each having a simpler distribution, and training a different generator for each partition.
This is done in an unsupervised manner without requiring any labels.
Experimental results on various standard benchmarks show that the proposed unsupervised model outperforms several recent methods.
arXiv Detail & Related papers (2021-04-02T00:06:53Z) - Off-policy Evaluation in Infinite-Horizon Reinforcement Learning with
Latent Confounders [62.54431888432302]
We study an OPE problem in an infinite-horizon, ergodic Markov decision process with unobserved confounders.
We show how, given only a latent variable model for states and actions, policy value can be identified from off-policy data.
arXiv Detail & Related papers (2020-07-27T22:19:01Z) - The empirical duality gap of constrained statistical learning [115.23598260228587]
We study the study of constrained statistical learning problems, the unconstrained version of which are at the core of virtually all modern information processing.
We propose to tackle the constrained statistical problem overcoming its infinite dimensionality, unknown distributions, and constraints by leveraging finite dimensional parameterizations, sample averages, and duality theory.
We demonstrate the effectiveness and usefulness of this constrained formulation in a fair learning application.
arXiv Detail & Related papers (2020-02-12T19:12:29Z)
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.