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

• General Frameworks for Conditional Two-Sample Testing [3.3317825075368908]
  We study the problem of conditional two-sample testing, which aims to determine whether two populations have the same distribution after accounting for confounding factors. This problem commonly arises in various applications, such as domain adaptation and algorithmic fairness. We introduce two general frameworks that implicitly or explicitly target specific classes of distributions for their validity and power.
  arXiv  Detail & Related papers  (2024-10-22T02:27:32Z)
• Accounting for Missing Covariates in Heterogeneous Treatment Estimation [17.09751619857397]
  We introduce a novel partial identification strategy based on ideas from ecological inference. We show that our framework can produce bounds that are much tighter than would otherwise be possible.
  arXiv  Detail & Related papers  (2024-10-21T05:47:07Z)
• Temporal Fair Division of Indivisible Items [61.235172150247614]
  We study a fair division model where indivisible items arrive sequentially, and must be allocated immediately and irrevocably. Previous work on online fair division has shown impossibility results in achieving approximate envy-freeness under these constraints. We aim to ensure that the cumulative allocation at each round satisfies approximate temporal envy-freeness up to one item (TEF1)
  arXiv  Detail & Related papers  (2024-10-18T16:43:36Z)
• Strength of statistical evidence for genuine tripartite nonlocality [0.0]
  Recent advancements in network nonlocality have led to the concept of local operations and shared randomness-based genuine multipartite nonlocality (LOSR-GMNL) This paper focuses on a tripartite scenario where the goal is to exhibit correlations impossible in a network where each two-party subset shares bipartite resources and every party has access to unlimited shared randomness.
  arXiv  Detail & Related papers  (2024-07-28T21:12:52Z)
• 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.