論文の概要: Individual fairness under Varied Notions of Group Fairness in Bipartite
Matching -- One Framework to Approximate Them Al
- arxiv url: http://arxiv.org/abs/2208.09951v3
- Date: Tue, 6 Jun 2023 13:28:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-07 22:04:36.031463
- Title: Individual fairness under Varied Notions of Group Fairness in Bipartite
Matching -- One Framework to Approximate Them Al
- Title(参考訳): 両部マッチングにおけるグループフェアネスの誤記による個人フェアネス-Them Alを近似するための一枠組み
- Authors: Atasi Panda, Anand Louis, Prajakta Nimbhorkar
- Abstract要約: 我々は,グループや個々人の公正性の制約を満足しつつ,各項目をプラットフォームに割り当てることの問題点を考察する。
複数の最適解が存在するかもしれないが、群フェアマッチングの分布を計算して確率的個人フェアネスを達成することを目的としている。
我々はさらにモデルとアルゴリズムを拡張して、次のフェアネスの概念に対処する: 極小群フェアネス(maxmin group fairness)、そして最も支配的な群の表現を最小化するマインドム群フェアネス( mindom group fairness)。
- 参考スコア(独自算出の注目度): 3.8551072383777596
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of assigning items to platforms while satisfying
group and individual fairness constraints. Each item is associated with certain
groups and has a preference ordering over platforms. Each platform enforces
group fairness by specifying an upper and a lower bound on the number of items
that can be matched to it from each group. Although there may be multiple
optimal solutions that satisfy the group fairness constraints, we aim to
achieve `probabilistic individual fairness' by computing a distribution over
`group fair' matchings such that each item has a reasonable probability of
being matched to one of its top choices. When each item can belong to multiple
groups, the problem of finding a maximum size group-fair matching is NP-hard
even when all the group lower bounds are 0, and there are no individual
fairness constraints. Given a total of $n$ items, we achieve a $O(\Delta \log
n)$ approximation algorithm when an item can belong to at most $\Delta$ groups,
and all the group lower bounds are 0. We also provide two approximation
algorithms in terms of the total number of groups that have items in the
neighborhood of a platform. When each item belongs to a single group, we
provide a polynomial-time algorithm that computes a probabilistic individually
fair distribution over group fair matching. We further extend our model and
algorithms to address the following notions of fairness: `maxmin group
fairness', which maximizes the representation of the worst-off groups, and
`mindom group fairness', which minimizes the representation of the most
dominant groups.
- Abstract(参考訳): 我々は, 個別の公平性制約を満たしながら, プラットフォームにアイテムを割り当てる問題を考える。
それぞれの項目は特定のグループに関連付けられ、プラットフォーム上の優先順序を持つ。
各プラットフォームは、各グループからマッチできるアイテムの数の上限と下限を指定することで、グループフェア性を強制する。
群フェアネス制約を満たす複数の最適解が存在するかもしれないが、我々は「群フェア」マッチングの分布を計算して「確率的個人フェアネス」を達成することを目指している。
各項目が複数の群に属することができるとき、最大サイズのグループフェアマッチングを求める問題は、すべての群の下限が 0 であってもNPハードであり、個々の公正性制約はない。
合計$n$アイテムが与えられたとき、あるアイテムが少なくとも$\Delta$グループに属し、すべての群下限が 0 であるときに、$O(\Delta \log n)$近似アルゴリズムを達成する。
また,プラットフォーム近傍にアイテムを持つグループの総数に関して,近似アルゴリズムを2つ提供している。
各項目が1つのグループに属する場合、確率的に公平な分布を群フェアマッチング上で計算する多項式時間アルゴリズムを提供する。
私たちはさらにモデルとアルゴリズムを拡張して、フェアネスの次の概念に対処します。「最大群フェアネス」は最悪のグループの表現を最大化し、最も支配的なグループの表現を最小化する「ミニドム群フェアネス」です。
関連論文リスト
- Fair Active Ranking from Pairwise Preferences [6.102498508368527]
解離群に属する$n$の項目が与えられたとき、我々のゴールは、我々が提案する公正な目的関数に従って$(epsilon, delta)$-PACF-Rankingを見つけることである。
グループブラインドとグループアウェアの両方のアルゴリズムを提示し,そのサンプルパラメータを解析する。
論文 参考訳(メタデータ) (2024-02-05T18:09:48Z) - Bipartite Ranking Fairness through a Model Agnostic Ordering Adjustment [54.179859639868646]
本稿では,二部類ランキングにおける公平性を実現するためのモデルに依存しない後処理フレームワークxOrderを提案する。
xOrderは、教師なしおよび教師なしの公正度メトリックを含む、さまざまな分類モデルとランキングフェアネスメトリクスと互換性がある。
提案アルゴリズムを,4つのベンチマークデータセットと2つの実世界の患者電子健康記録リポジトリ上で評価した。
論文 参考訳(メタデータ) (2023-07-27T07:42:44Z) - Beyond Submodularity: A Unified Framework of Randomized Set Selection
with Group Fairness Constraints [19.29174615532181]
グループフェアネス制約を組み込んだランダム化サブセット選択のための統一フレームワークを提案する。
我々の問題には、グローバルなユーティリティ関数と、各グループに対するグループユーティリティ関数のセットが含まれる。
我々の目的は、各実現可能な集合の選択確率を指定して、実現可能な部分集合にまたがる分布を生成することである。
論文 参考訳(メタデータ) (2023-04-13T15:02:37Z) - Fair and skill-diverse student group formation via constrained k-way
graph partitioning [65.29889537564455]
本研究は、公正かつ多様な学生グループ形成のための教師なしアルゴリズムを導入する。
学生のスキルセットは、ラプラシア固有写像を用いて、コースマークデータの教師なし次元削減を用いて決定される。
この問題は制約付きグラフ分割問題として定式化され、各グループのスキルセットの多様性が最大化される。
論文 参考訳(メタデータ) (2023-01-12T14:02:49Z) - Enforcing Group Fairness in Algorithmic Decision Making: Utility
Maximization Under Sufficiency [0.0]
本稿では,PPVパリティ,偽脱落率(FOR)パリティ(False Omission rate)パリティ(FOR)パリティ(False Omission rate)パリティ(FOR)パリティ(False Omission rate)パリティ(FOR)パリティ(FOR)パリティ(Sufficiency)について述べる。
グループ固有のしきい値規則はPPVパリティとForパリティに最適であることを示す。
また,フェアネス制約を満たす最適決定規則の解も提供する。
論文 参考訳(メタデータ) (2022-06-05T18:47:34Z) - Fair Labeled Clustering [28.297893914525517]
クラスタリングのダウンストリーム適用と,そのような設定に対してグループフェアネスをどのように確保するかを検討する。
このような問題に対するアルゴリズムを提供し、グループフェアクラスタリングにおけるNPハードのアルゴリズムとは対照的に、効率的な解が可能であることを示す。
また、距離空間における中心位置に関係なく、意思決定者が自由にクラスタにラベルを割り当てることができるような、モチベーションのよい代替設定についても検討する。
論文 参考訳(メタデータ) (2022-05-28T07:07:12Z) - Fair Group-Shared Representations with Normalizing Flows [68.29997072804537]
本研究では,異なるグループに属する個人を1つのグループにマッピングできる公正表現学習アルゴリズムを開発した。
提案手法は,他の公正表現学習アルゴリズムと競合することを示す。
論文 参考訳(メタデータ) (2022-01-17T10:49:49Z) - Focus on the Common Good: Group Distributional Robustness Follows [47.62596240492509]
本稿では,多様なグループ間で共有される特徴の学習を明示的に促進する,新しい,シンプルなアルゴリズムを提案する。
グループDROは、最低の正規化損失を持つグループに焦点を当て、代わりに、他のグループでもより良いパフォーマンスを実現するグループに焦点を当てるが、共有/共通機能を学ぶことにつながる可能性がある。
論文 参考訳(メタデータ) (2021-10-06T09:47:41Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳(メタデータ) (2021-06-04T02:32:26Z) - Fair for All: Best-effort Fairness Guarantees for Classification [11.818794470895837]
群に基づくフェアネスの概念は、既知の群全体のパフォーマンスの絶対測度を等化しようとする。
我々は、クラス $mathcalg$ における各グループ $g$ の保証は、$g$ の最高の分類器のパフォーマンスと関係しているという概念を提案する。
私たちはアルゴリズムを現実世界のデータセットでテストし、パフォーマンスに関する興味深い比較洞察を提供します。
論文 参考訳(メタデータ) (2020-12-18T13:22:14Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳(メタデータ) (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。