論文の概要: From Matching with Diversity Constraints to Matching with Regional
Quotas
- arxiv url: http://arxiv.org/abs/2002.06748v1
- Date: Mon, 17 Feb 2020 02:51:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-31 13:12:22.571028
- Title: From Matching with Diversity Constraints to Matching with Regional
Quotas
- Title(参考訳): 多様性制約とのマッチングから地域基準とのマッチングへ
- Authors: Haris Aziz, Serge Gaspers, Zhaohong Sun, Toby Walsh
- Abstract要約: 分布制約に適合する2つの重要な公理の間の公式な関係を示す。
1)に対する実現可能かつ安定な結果が存在するかどうかを確認することはNP完全であることを示す。
病院医師と地域基準との整合性に関するさらなる発展が,学校選択と多様性の両立につながると結論づける。
- 参考スコア(独自算出の注目度): 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.
- Abstract(参考訳): ここ数年、複雑な分布制約を考慮した新しいマッチングモデルがいくつか提案され研究されている。
関連する仕事の行は,(1)学生が(おそらく重複する)タイプを持つような多様性制約のある学校選択と,(2)地域的基準が課される病院と医師のマッチングである。
本稿では,(1) のインスタンスを (2) のインスタンスに変換する多項式時間還元と,それに対応するマッチングの実現性と安定性について述べる。
この削減は,分布的制約に適合する2つの重要な作業列間の形式的接続を提供する。
次に、その削減を2つの方法で適用する。
まず,(1)に対する実現可能かつ安定な結果が存在するかどうかを確認することはNP完全であることを示す。
その結果, これらのNP完全性は, 設定 (2) まで続くことがわかった。
これを踏まえて,文献に提示された結果のいくつかを統一するのに役立つ。
第二に、(2) の正の結果が得られた場合、(1) の正の結果が対応する。
以上の結果の1つとして, 病院と医師の地域的クォータとのマッチングの公理的, アルゴリズム的側面のさらなる発展が, 学校選択の多様性の制約に対応する結果をもたらすことを示唆した。
関連論文リスト
- Diversify & Conquer: Outcome-directed Curriculum RL via
Out-of-Distribution Disagreement [30.21954044028645]
強化学習(Reinforcement Learning, RL)は、エージェントがドメイン知識にアクセスせずに探索すべき非情報探索問題の課題に直面することが多い。
本研究は、D2C(Diversify for Disagreement & Conquer)と呼ばれるカリキュラムRLの新しいアプローチを提案する。
従来のカリキュラム学習法とは異なり、D2Cは望ましい結果のごくわずかの例しか必要とせず、どんな環境でも機能する。
論文 参考訳(メタデータ) (2023-10-30T04:12:19Z) - On Pitfalls of Test-Time Adaptation [82.8392232222119]
TTA(Test-Time Adaptation)は、分散シフトの下で堅牢性に取り組むための有望なアプローチとして登場した。
TTABは,10の最先端アルゴリズム,多種多様な分散シフト,および2つの評価プロトコルを含むテスト時間適応ベンチマークである。
論文 参考訳(メタデータ) (2023-06-06T09:35:29Z) - Doubly Constrained Fair Clustering [11.11449872883085]
Group Fairness (GF) と Diversity in Center Selection (DS) は、クラスタリングにおける最も顕著な人口統計学的表現フェアネスの概念である。
1つの制約 (GF または DS のみ) に対して定数近似アルゴリズムが与えられた場合、両方の制約を同時に満たす定数近似解が得られることを示す。
GF と DS は、他の距離に基づくフェアネスの概念の集合と相容れないことを示す。
論文 参考訳(メタデータ) (2023-05-31T01:04:55Z) - Efficient Alternating Minimization Solvers for Wyner Multi-View
Unsupervised Learning [0.0]
本稿では,計算効率のよい解法の開発を可能にする2つの新しい定式化法を提案する。
提案した解法は, 計算効率, 理論的収束保証, ビュー数による局所最小値複雑性, 最先端技術と比較して, 例外的な精度を提供する。
論文 参考訳(メタデータ) (2023-03-28T10:17:51Z) - Boosting device-independent cryptography with tripartite nonlocality [0.0]
デバイス非依存(DI)プロトコルは、2つ以上のパーティがベルの不等式をテストすると、非局所的な相関を観測することで、プライベートランダム性を証明する。
本稿では,DICKAプロトコルとDIREプロトコルを多部間ベルの不等式テストに基づいて検討する。
DICKAとDIREプロトコルは,三部構成のベルの不等式を用いた場合,二部構成のプロトコルよりも優れることを示す。
論文 参考訳(メタデータ) (2022-09-26T16:35:03Z) - Optimal Adaptive Strategies for Sequential Quantum Hypothesis Testing [87.17253904965372]
適応的および非適応的戦略を用いた2つの量子状態間の逐次仮説テストについて検討する。
両状態間の相対エントロピーの測定により,これらの誤差は指数関数的に減少することを示した。
論文 参考訳(メタデータ) (2021-04-30T00:52:48Z) - Partition-Guided GANs [63.980473635585234]
私たちは、スペースを小さな領域に分割し、それぞれがよりシンプルな分布を持ち、各パーティションごとに異なるジェネレータを訓練するパーティションーを設計します。
これはラベルを必要とせずに教師なしの方法で実行される。
各種標準ベンチマーク実験の結果,提案手法が近年の手法を上回っていることがわかった。
論文 参考訳(メタデータ) (2021-04-02T00:06:53Z) - Off-policy Evaluation in Infinite-Horizon Reinforcement Learning with
Latent Confounders [62.54431888432302]
無限水平エルゴードマルコフ決定過程におけるOPE問題について考察する。
我々は、状態と行動の潜在変数モデルのみを考慮すれば、政策値が政治外のデータから特定できることを示す。
論文 参考訳(メタデータ) (2020-07-27T22:19:01Z) - The empirical duality gap of constrained statistical learning [115.23598260228587]
本研究では,制約付き統計学習問題(制約なし版)について,ほぼ全ての現代情報処理のコアとなる研究を行った。
本稿では, 有限次元パラメータ化, サンプル平均, 双対性理論を利用して, 無限次元, 未知分布, 制約を克服する制約付き統計問題に取り組むことを提案する。
フェアラーニングアプリケーションにおいて,この制約付き定式化の有効性と有用性を示す。
論文 参考訳(メタデータ) (2020-02-12T19:12:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。