論文の概要: Algorithmic Stability in Fair Allocation of Indivisible Goods Among Two Agents

• arxiv url: http://arxiv.org/abs/2007.15203v2
• Date: Mon, 12 Jul 2021 15:58:27 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-05 14:51:58.154325
• Title: Algorithmic Stability in Fair Allocation of Indivisible Goods Among Two Agents
• Title（参考訳）: エージェント間の不特定商品の公平配置におけるアルゴリズム的安定性
• Authors: Vijay Menon and Kate Larson
• Abstract要約: 正当性の概念や近似効率の弱さとともに、正確な安定性を達成することは不可能であることを示す。 本稿では,安定性,すなわち近似安定性と弱近似安定性の2つの緩和法を提案する。 本稿では、ペアワイズ最大値の割り当てに関する一般的な特徴付けを行い、それを用いてほぼ安定なアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 8.66798555194688
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many allocation problems in multiagent systems rely on agents specifying cardinal preferences. However, allocation mechanisms can be sensitive to small perturbations in cardinal preferences, thus causing agents who make ``small" or ``innocuous" mistakes while reporting their preferences to experience a large change in their utility for the final outcome. To address this, we introduce a notion of algorithmic stability and study it in the context of fair and efficient allocations of indivisible goods among two agents. We show that it is impossible to achieve exact stability along with even a weak notion of fairness and even approximate efficiency. As a result, we propose two relaxations to stability, namely, approximate-stability and weak-approximate-stability, and show how existing algorithms in the fair division literature that guarantee fair and efficient outcomes perform poorly with respect to these relaxations. This leads us to explore the possibility of designing new algorithms that are more stable. Towards this end, we present a general characterization result for pairwise maximin share allocations, and in turn use it to design an algorithm that is approximately-stable and guarantees a pairwise maximin share and Pareto optimal allocation for two agents. Finally, we present a simple framework that can be used to modify existing fair and efficient algorithms in order to ensure that they also achieve weak-approximate-stability.
• Abstract（参考訳）: マルチエージェントシステムにおける多くの割り当て問題は、基数選好を指定するエージェントに依存する。 しかし、割り当て機構は基数選好の小さな摂動に敏感であり、その結果、``small" または ``無害" の誤りを犯すエージェントが、最終結果のためにユーティリティに大きな変化を経験する傾向を報告してしまう。 そこで本研究では,2つのエージェント間の不分別商品の公平かつ効率的な配分という文脈で,アルゴリズム安定性の概念を導入する。 公正性の弱い概念や近似効率さえも、正確な安定性を達成することは不可能であることを示す。 その結果、安定に対する2つの緩和、すなわち近似安定性と弱近似安定性を提案し、公平かつ効率的な結果を保証するフェア分割文献における既存のアルゴリズムが、これらの緩和に対してどのようにうまく機能するかを示す。 これにより、我々はより安定した新しいアルゴリズムを設計する可能性を探ることになる。 この目的に向けて、ペアワイズ最大値の割り当てに関する一般的な特徴付け結果を示し、それを用いてほぼ安定なアルゴリズムを設計し、2つのエージェントに対してペアワイズ最大値とパレート最適値を保証する。 最後に,既存の公平かつ効率的なアルゴリズムを改良して,弱近似安定性を実現するための簡単なフレームワークを提案する。

関連論文リスト

• Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
  両面のマッチング市場は、市場の片側からの参加者が好みに応じて反対側からの参加者と一致しなければならない、一連の問題を記述している。 我々は安定解の構造を利用して、安定解を見つける可能性を改善するアルゴリズムを考案する。
  論文  参考訳（メタデータ） (2024-10-06T06:47:53Z)
• Understanding Fairness Surrogate Functions in Algorithmic Fairness [21.555040357521907]
  フェアネスの定義とフェアネスのサロゲート関数の間には、サロゲートとフェアネスのギャップがあることが示される。 我々は、不公平を緩和するギャップを反復的に減少させる「バランスド・サロゲート」という、新規で一般的なアルゴリズムを精査する。
  論文  参考訳（メタデータ） (2023-10-17T12:40:53Z)
• Federated Distributionally Robust Optimization with Non-Convex Objectives: Algorithm and Analysis [24.64654924173679]
  Asynchronous Single-looP alternatIve gRadient projEction という非同期分散アルゴリズムを提案する。 新しい不確実性集合、すなわち制約付きD-ノルムの不確実性集合は、以前の分布を利用し、強靭性の度合いを柔軟に制御するために開発される。 実世界のデータセットに関する実証研究は、提案手法が高速収束を達成できるだけでなく、悪意のある攻撃だけでなく、データに対する堅牢性も維持できることを示した。
  論文  参考訳（メタデータ） (2023-07-25T01:56:57Z)
• Group Fairness with Uncertainty in Sensitive Attributes [34.608332397776245]
  公正な予測モデルは、ハイテイクなアプリケーションにおける少数派グループに対する偏見のある決定を緩和するために不可欠である。 本稿では, 感度特性の不確実性にも拘わらず, フェアネスの目標レベルを達成するブートストラップに基づくアルゴリズムを提案する。 本アルゴリズムは離散的属性と連続的属性の両方に適用可能であり,実世界の分類や回帰作業に有効である。
  論文  参考訳（メタデータ） (2023-02-16T04:33:00Z)
• Fairness in Matching under Uncertainty [78.39459690570531]
  アルゴリズム的な二面市場は、こうした設定における公平性の問題に注意を向けている。 我々は、利益の不確実性を尊重する両面の市場設定において、個々人の公正性の概念を公理化する。 そこで我々は,配当よりも公平なユーティリティ最大化分布を求めるために,線形プログラミングフレームワークを設計する。
  論文  参考訳（メタデータ） (2023-02-08T00:30:32Z)
• Practical Approaches for Fair Learning with Multitype and Multivariate Sensitive Attributes [70.6326967720747]
  現実世界に展開された機械学習アルゴリズムが不公平さや意図しない社会的結果をもたらすことはないことを保証することが重要である。 本稿では,カーネルHilbert Spacesの相互共分散演算子上に構築されたフェアネス尺度であるFairCOCCOを紹介する。 実世界のデータセットにおける予測能力と公正性のバランスをとる上で、最先端技術に対する一貫した改善を実証的に示す。
  論文  参考訳（メタデータ） (2022-11-11T11:28:46Z)
• Distributed Distributionally Robust Optimization with Non-Convex Objectives [24.64654924173679]
  Asynchronous Single-looP alternatIve gRadient projEction という非同期分散アルゴリズムを提案する。 新しい不確実性集合、すなわち制約付きD-ノルムの不確実性集合は、以前の分布を利用し、強靭性の度合いを柔軟に制御するために開発される。 実世界のデータセットに関する実証研究は、提案手法が高速収束を達成できるだけでなく、悪意のある攻撃だけでなく、データに対する堅牢性も維持できることを示した。
  論文  参考訳（メタデータ） (2022-10-14T07:39:13Z)
• 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)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• Beyond Individual and Group Fairness [90.4666341812857]
  本稿では,不公平な不公平な苦情に導かれる公平さの新しいデータ駆動モデルを提案する。 我々のモデルは、複数のフェアネス基準をサポートし、それらの潜在的な不整合を考慮に入れている。
  論文  参考訳（メタデータ） (2020-08-21T14:14:44Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。