論文の概要: On Fairness and Stability in Two-Sided Matchings
- arxiv url: http://arxiv.org/abs/2111.10885v1
- Date: Sun, 21 Nov 2021 19:46:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-07 06:26:11.959190
- Title: On Fairness and Stability in Two-Sided Matchings
- Title（参考訳）: 二次元マッチングの公平性と安定性について
- Authors: Gili Karni, Guy N. Rothblum, Gal Yona
- Abstract要約: 個人に関する重要な決定を行うか、影響を及ぼすアルゴリズムが、保護されたグループを差別する結果を生み出すのではないかという懸念が高まっている。
エージェントのセットが2つあり、各エージェントは他のセットよりも好みがある。
病院の選好を公平に設定することで,Gale-Shapleyアルゴリズムが極めて不公平な結果をもたらすことを示す。
- 参考スコア（独自算出の注目度）: 12.495879803239802
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: There are growing concerns that algorithms, which increasingly make or
influence important decisions pertaining to individuals, might produce outcomes
that discriminate against protected groups. We study such fairness concerns in
the context of a two-sided market, where there are two sets of agents, and each
agent has preferences over the other set. The goal is producing a matching
between the sets. This setting has been the focus of a rich body of work. The
seminal work of Gale and Shapley formulated a stability desideratum, and showed
that a stable matching always exists and can be found efficiently. We study
this question through the lens of metric-based fairness notions (Dwork et al.,
Kim et al.). We formulate appropriate definitions of fairness and stability in
the presence of a similarity metric, and ask: does a fair and stable matching
always exist? Can such a matching be found in polynomial time? Our
contributions are as follows: (1) Composition failures for classical
algorithms: We show that composing the Gale-Shapley algorithm with fair
hospital preferences can produce blatantly unfair outcomes. (2) New algorithms
for finding fair and stable matchings: Our main technical contributions are
efficient new algorithms for finding fair and stable matchings when: (i) the
hospitals' preferences are fair, and (ii) the fairness metric satisfies a
strong "proto-metric" condition: the distance between every two doctors is
either zero or one. In particular, these algorithms also show that, in this
setting, fairness and stability are compatible. (3) Barriers for finding fair
and stable matchings in the general case: We show that if the hospital
preferences can be unfair, or if the metric fails to satisfy the proto-metric
condition, then no algorithm in a natural class can find a fair and stable
matching. The natural class includes the classical Gale-Shapley algorithms and
our new algorithms.
- Abstract（参考訳）: 個人に関する重要な決定を行うか、影響を及ぼすアルゴリズムが、保護されたグループを差別する結果を生み出すのではないかという懸念が高まっている。
2つのエージェントセットがあり、それぞれのエージェントがもう1つのエージェントセットよりも好みを持っている2つのサイドマーケットの文脈において、このような公平性に関する懸念について検討する。
ゴールはセット間のマッチングを生成します。
この設定は、リッチな仕事の焦点となっている。
Gale と Shapley のセミナルな研究は安定性のデシドラタムを定式化し、安定なマッチングが常に存在することを示した。
この問題は計量に基づく公正の概念(Dwork et al., Kim et al.)のレンズを通して研究する。
我々は、類似度計量の存在下での公正性と安定性の適切な定義を定式化し、次のように問う。
そのようなマッチングは多項式時間で見つかるか?
1) 古典的アルゴリズムにおける構成障害: 公平な病院選好を伴うGalle-Shapleyアルゴリズムを構成することで, 極めて不公平な結果が得られることを示す。
2)公平で安定したマッチングを見つけるための新しいアルゴリズム:我々の主な技術的貢献は、公正で安定したマッチングを見つけるための効率的な新しいアルゴリズムです。
(i)病院の好みは公平で、
(ii) フェアネス計量は強い「プロトメトリック」条件を満たす: 2人の医師間の距離は0か1である。
特に、これらのアルゴリズムは、この設定では公平性と安定性が相容れないことを示す。
3) 一般の場合における公平で安定したマッチングを見つけるための障壁: 病院の選好が不公平になり得るか、または計量が原計量条件を満たせなかった場合、自然クラスのアルゴリズムは公平で安定したマッチングを見つけることができない。
自然クラスには古典的なgale-shapleyアルゴリズムと新しいアルゴリズムが含まれています。
関連論文リスト
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
両面のマッチング市場は、市場の片側からの参加者が好みに応じて反対側からの参加者と一致しなければならない、一連の問題を記述している。
我々は安定解の構造を利用して、安定解を見つける可能性を改善するアルゴリズムを考案する。
論文 参考訳（メタデータ） (2024-10-06T06:47:53Z) - What's Distributive Justice Got to Do with It? Rethinking Algorithmic Fairness from the Perspective of Approximate Justice [1.8434042562191815]
不完全な意思決定システムという文脈では、個人間での利益/利益の理想的な分配がどのようなものになるかだけを気にすべきではない、と私たちは主張する。
このためには、アルゴリズムフェアネス研究者として、分配的正義を見極め、公正性基準を使用する方法を再考する必要がある。
論文 参考訳（メタデータ） (2024-07-17T11:13:23Z) - Bipartite Ranking Fairness through a Model Agnostic Ordering Adjustment [54.179859639868646]
本稿では,二部類ランキングにおける公平性を実現するためのモデルに依存しない後処理フレームワークxOrderを提案する。
xOrderは、教師なしおよび教師なしの公正度メトリックを含む、さまざまな分類モデルとランキングフェアネスメトリクスと互換性がある。
提案アルゴリズムを,4つのベンチマークデータセットと2つの実世界の患者電子健康記録リポジトリ上で評価した。
論文 参考訳（メタデータ） (2023-07-27T07:42:44Z) - Proportional Fairness in Obnoxious Facility Location [70.64736616610202]
この問題に対して,距離に基づく比例フェアネスの概念の階層構造を提案する。
決定論的かつランダムなメカニズムを考察し、比例フェアネスの価格に関する厳密な境界を計算する。
モデルの拡張が2つあることを示す。
論文 参考訳（メタデータ） (2023-01-11T07:30:35Z) - Counterfactual Fairness Is Basically Demographic Parity [0.0]
公正な意思決定は、倫理的に機械学習アルゴリズムを社会的設定で実装する上で重要である。
また, 対実的公正性を満たすアルゴリズムが, 人口統計学的平等を満足することを示す。
我々は、保護グループ内の個人の秩序を維持するという具体的な公正目標を定式化する。
論文 参考訳（メタデータ） (2022-08-07T23:38:59Z) - Optimal Algorithms for Decentralized Stochastic Variational Inequalities [113.43047601775453]
この作業は、ますます重要になるが十分に理解されていない分散的な設定に集中する。
通信と局所的な繰り返しの両方の下位境界を示し、これらの下位境界に一致する最適なアルゴリズムを構築する。
我々のアルゴリズムは、分散化されたケースだけでなく、決定論的で非分散的な文献でも利用できる。
論文 参考訳（メタデータ） (2022-02-06T13:14:02Z) - Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。
私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
論文 参考訳（メタデータ） (2021-08-19T17:59:28Z) - Metric-Free Individual Fairness with Cooperative Contextual Bandits [17.985752744098267]
グループフェアネスは、グループ内の一部の個人に対して不公平であるように、異なるグループが同様に扱われるべきである。
個々の公正性は、問題固有の類似度指標に依存するため、まだ検討されていない。
本研究では,メトリックフリーな個人フェアネスと協調的文脈帯域幅アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-11-13T03:10:35Z) - Beyond Individual and Group Fairness [90.4666341812857]
本稿では,不公平な不公平な苦情に導かれる公平さの新しいデータ駆動モデルを提案する。
我々のモデルは、複数のフェアネス基準をサポートし、それらの潜在的な不整合を考慮に入れている。
論文 参考訳（メタデータ） (2020-08-21T14:14:44Z) - Towards Model-Agnostic Post-Hoc Adjustment for Balancing Ranking
Fairness and Algorithm Utility [54.179859639868646]
Bipartiteランキングは、ラベル付きデータから正の個人よりも上位の個人をランク付けするスコアリング機能を学ぶことを目的としている。
学習したスコアリング機能が、異なる保護グループ間で体系的な格差を引き起こすのではないかという懸念が高まっている。
本稿では、二部構成のランキングシナリオにおいて、それらのバランスをとるためのモデル後処理フレームワークを提案する。
論文 参考訳（メタデータ） (2020-06-15T10:08:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。