論文の概要: Approximate Proportionality in Online Fair Division
- arxiv url: http://arxiv.org/abs/2508.03253v1
- Date: Tue, 05 Aug 2025 09:31:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-06 18:18:55.887041
- Title: Approximate Proportionality in Online Fair Division
- Title（参考訳）: オンラインフェア部門における近似比例
- Authors: Davin Choo, Winston Fu, Derek Khu, Tzeh Yuan Neoh, Tze-Yang Poon, Nicholas Teh,
- Abstract要約: 我々は、近似性が未解決のままである比例性の自然な緩和である1つの善(PROP1)に比例性に焦点を当てる。
3つの自然なグリージーアルゴリズムは、適応的敵に対して、一般にPROP1に対する正の近似を保証できないことを示す。
本稿では,最大項目値の予測を行う際に,PROP1に対するロバストな近似比を求めるアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 4.200214709723945
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the online fair division problem, where indivisible goods arrive sequentially and must be allocated immediately and irrevocably to agents. Prior work has established strong impossibility results for approximating classic fairness notions, such as envy-freeness and maximin share fairness, in this setting. In contrast, we focus on proportionality up to one good (PROP1), a natural relaxation of proportionality whose approximability remains unresolved. We begin by showing that three natural greedy algorithms fail to guarantee any positive approximation to PROP1 in general, against an adaptive adversary. This is surprising because greedy algorithms are commonly used in fair division and a natural greedy algorithm is known to be able to achieve PROP1 under additional information assumptions. This hardness result motivates the study of non-adaptive adversaries and the use of side-information, in the spirit of learning-augmented algorithms. For non-adaptive adversaries, we show that the simple uniformly random allocation can achieve a meaningful PROP1 approximation with high probability. Meanwhile, we present an algorithm that obtain robust approximation ratios against PROP1 when given predictions of the maximum item value (MIV). Interestingly, we also show that stronger fairness notions such as EF1, MMS, and PROPX remain inapproximable even with perfect MIV predictions.
- Abstract（参考訳）: 我々は、不特定商品が順次到着し、即時かつ不当にエージェントに割り当てなければならないオンラインフェアディビジョン問題を調査する。
以前の研究は、この設定において、エンビーフリーネスや最大シェアフェアネスのような古典的フェアネスの概念を近似するための強い不可能な結果を確立してきた。
対照的に、近似性は未解決のままであるような比例性の自然な緩和である1つの善(PROP1)まで比例性に焦点を当てる。
まず、3つの自然な欲求アルゴリズムが、適応的敵に対して、一般にはPROP1に対する正の近似を保証できないことを示す。
これは、greedyアルゴリズムがフェアディビジョンで一般的に使われており、自然なgreedyアルゴリズムが追加の情報仮定の下でPROP1を達成できることが知られているため、驚くべきことである。
この硬さの結果は、学習強化アルゴリズムの精神において、非適応的敵の研究と側情報の利用を動機付けている。
非適応的逆数に対して、単純な一様ランダムなアロケーションは高い確率で有意なPROP1近似を実現することができることを示す。
一方,最大項目値(MIV)の予測を行う際に,PROP1に対するロバストな近似比を求めるアルゴリズムを提案する。
興味深いことに、EF1, MMS, PROPX のような強い公平性の概念は、完全な MIV 予測でも適用不可能であることも示している。
関連論文リスト
- Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。
過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。
報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
論文 参考訳（メタデータ） (2024-05-26T05:38:50Z) - Rethinking Algorithmic Fairness for Human-AI Collaboration [29.334511328067777]
アルゴリズムフェアネスに対する既存のアプローチは、人間の意思決定者がアルゴリズムに完全に従えば、公平な結果を確保することを目的としている。
我々は、独立して公平で、コンプライアンスが不当に公正で、人間のポリシーよりも正確であるアルゴリズムレコメンデーションを設計することは不可能であることを示した。
論文 参考訳（メタデータ） (2023-10-05T16:21:42Z) - Fairness in Matching under Uncertainty [78.39459690570531]
アルゴリズム的な二面市場は、こうした設定における公平性の問題に注意を向けている。
我々は、利益の不確実性を尊重する両面の市場設定において、個々人の公正性の概念を公理化する。
そこで我々は,配当よりも公平なユーティリティ最大化分布を求めるために,線形プログラミングフレームワークを設計する。
論文 参考訳（メタデータ） (2023-02-08T00:30:32Z) - Metrizing Fairness [5.323439381187456]
本研究では,2つの集団集団の個人に有意な影響を及ぼす教師付き学習問題について検討した。
我々は、統計パリティ(SP)のような群フェアネス基準に関して公正な予測子を求める。
本稿では,厳密なSP制約が保証される条件を特定し,予測精度を向上させる。
論文 参考訳（メタデータ） (2022-05-30T12:28:10Z) - Fair Bayes-Optimal Classifiers Under Predictive Parity [33.648053823193855]
本稿では、異なる保護群間での正の予測から、成功の確率を等しくする必要がある予測パリティについて考察する。
本研究では,FairBayes-DPPと呼ばれるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-15T04:58:10Z) - Domain Adaptation meets Individual Fairness. And they get along [48.95808607591299]
アルゴリズムフェアネスの介入は、機械学習モデルが分散シフトを克服するのに役立つことを示す。
特に,個人フェアネス(IF)の適切な概念を強制することで,MLモデルの分布外精度が向上することを示す。
論文 参考訳（メタデータ） (2022-05-01T16:19:55Z) - Learning fair representation with a parametric integral probability
metric [2.544539499281093]
公正表現(LFR)を学習するための新しい逆学習手法を提案する。
本稿では,表現の公平さと表現の最上部に構築された予測モデルの公正さの理論的関係を導出する。
提案するLFRアルゴリズムは計算的に軽量で安定であり,最終予測モデルは他のLFRアルゴリズムよりも優れている。
論文 参考訳（メタデータ） (2022-02-07T05:02:23Z) - Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
暗黙のフィードバックから学ぶことは、一流問題の難しい性質のために困難です。
ほとんどの従来の方法は、一級問題に対処するためにペアワイズランキングアプローチとネガティブサンプラーを使用します。
本論文では,ポイントワイズと同等の収束速度を実現する学習対ランクアプローチを提案する。
論文 参考訳（メタデータ） (2021-05-11T03:38:16Z) - Amortized Conditional Normalized Maximum Likelihood: Reliable Out of
Distribution Uncertainty Estimation [99.92568326314667]
本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。
提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。
我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
論文 参考訳（メタデータ） (2020-11-05T08:04:34Z) - Selective Classification via One-Sided Prediction [54.05407231648068]
片側予測(OSP)に基づく緩和は、実際に関係する高目標精度体制において、ほぼ最適カバレッジが得られるSCスキームをもたらす。
理論的には,SCとOSPのバウンダリ一般化を導出し,その手法が小さな誤差レベルでのカバレッジにおいて,技術手法の状態を強く上回ることを示す。
論文 参考訳（メタデータ） (2020-10-15T16:14:27Z) - Achieving Proportionality up to the Maximin Item with Indivisible Goods [14.002498730240902]
我々は、分割不可能な商品をかなり配置する問題を研究し、古典的公平性の概念である比例性に焦点をあてる。
最近の研究で、比例性(PROPx)の近似バージョンでさえ、小さなインスタンスでも達成できないことが証明されている。
最大5つのエージェントが付加価値を持つ場合において、この概念を満たすアロケーションにどのように到達するかを示す。
論文 参考訳（メタデータ） (2020-09-20T19:21:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。