論文の概要: Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems

• arxiv url: http://arxiv.org/abs/2410.02589v1
• Date: Thu, 3 Oct 2024 15:32:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-04 02:22:08.453385
• Title: Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems
• Title（参考訳）: Max-Cutとその他の組合せ最適化問題におけるマクシミンフェアネスの期待
• Authors: Jad Salem, Reuben Tate, Stephan Eidenbenz,
• Abstract要約: 最適マクシミン・フェア解は、非マクシミン・フェア最適解によって有界であることを示す。 本稿では、Max-Cutの特別事例を用いて、最大公正性の定義と実装の課題を実証する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Maximin fairness is the ideal that the worst-off group (or individual) should be treated as well as possible. Literature on maximin fairness in various decision-making settings has grown in recent years, but theoretical results are sparse. In this paper, we explore the challenges inherent to maximin fairness in combinatorial optimization. We begin by showing that (1) optimal maximin-fair solutions are bounded by non-maximin-fair optimal solutions, and (2) stochastic maximin-fair solutions exceed their deterministic counterparts in expectation for a broad class of combinatorial optimization problems. In the remainder of the paper, we use the special case of Max-Cut to demonstrate challenges in defining and implementing maximin fairness.
• Abstract（参考訳）: 最大公平性(英: Maximin fairness)とは、最悪の集団(または個人)を可能な限り扱うことである。 近年, 意思決定環境におけるマキシミンの公平性に関する文献が増えているが, 理論的結果は少ない。 本稿では,組合せ最適化における最大公平性に固有の課題について検討する。 まず,(1) 最適最大値解は非最大値解で有界であり,(2) 確率最大値解は幅広い組合せ最適化問題のクラスを期待する決定論的解を超えていることを示す。 論文の残りの部分では、Max-Cut の特別なケースを用いて、最大公平性の定義と実装の課題を実証する。

関連論文リスト

• Multi-Objective Bayesian Optimization with Active Preference Learning [18.066263838953223]
  本稿では,多目的最適化 (MOO) 問題において最も望ましい解を特定するためのベイズ最適化 (BO) 手法を提案する。 また、意思決定者(DM)との相互作用コストを最小限に抑えるため、選好推定のためのアクティブラーニング戦略を提案する。
  論文  参考訳（メタデータ） (2023-11-22T15:24:36Z)
• Optimization on Pareto sets: On a theory of multi-objective optimization [7.907376287850398]
  多目的最適化では、単一の決定ベクトルは、多くの目的間のトレードオフのバランスをとる必要がある。 我々は,制約セットの最適化を目標とする,より現実的に重要な最適化問題を考える。
  論文  参考訳（メタデータ） (2023-08-04T05:55:52Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。 エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。 提案手法は(線形速度で)大域的最適値に収束することが示されている。
  論文  参考訳（メタデータ） (2022-06-03T16:26:38Z)
• Efficient Algorithms for Extreme Bandits [20.68824391770909]
  我々は,学習者が最大の報酬を集めようとするマルチアーマッド・バンディットの変種であるExtreme Bandit問題に貢献する。 まず、報酬分布の尾部における軽度の仮定の下で、i.d確率変数の最大値の濃度について検討する。 次に,より適応性の高いQoMax-SDAアルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2022-03-21T11:09:34Z)
• Max-Min Grouped Bandits [48.62520520818357]
  マルチアームバンディット問題であるmax-min grouped banditsを導入する。 ゴールは、最悪の腕が最高の平均報酬を持つグループを見つけることです。 この問題はレコメンデーションシステムのようなアプリケーションには関心がある。
  論文  参考訳（メタデータ） (2021-11-17T01:59:15Z)
• Bayesian Optimization for Min Max Optimization [77.60508571062958]
  そこで我々は,最適化すべき関数が事前に分かっていないような設定でMin Max Optimizationを実行するアルゴリズムを提案する。 我々は,改善を期待する2つの獲得機能とガウス過程の上部信頼境界を拡張した。 これらの取得機能は、ベンチマーク設定よりも高速に収束する、より良いソリューションを可能にすることを示す。
  論文  参考訳（メタデータ） (2021-07-29T06:49:34Z)
• Maxmin-Fair Ranking: Individual Fairness under Group-Fairness Constraints [11.3077234652777]
  グループフェアの制約を課す際に生じる個人不公平の量を最小限に抑えることを目的としたランキングにおける公平性の新たな問題について検討する。 提案手法は, ランダム化を用いて, 最悪の個人が期待する満足度を最大化する分布最大化理論に根ざしている。
  論文  参考訳（メタデータ） (2021-06-16T09:27:12Z)
• Preference learning along multiple criteria: A game-theoretic perspective [97.94912276610002]
  我々は、ブラックウェルの接近性からインスピレーションを得て、フォン・ノイマンの勝者の概念をマルチ基準設定に一般化する。 本フレームワークは,基準間の選好の非線形集約を可能にし,多目的最適化から線形化に基づくアプローチを一般化する。 凸最適化問題の解法として,マルチ基準問題インスタンスのブラックウェルの勝者が計算可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-05T03:23:11Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。 このアプローチは多くの実装と最適化の課題をもたらします。 提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
  論文  参考訳（メタデータ） (2021-03-18T14:26:26Z)
• Are we Forgetting about Compositional Optimisers in Bayesian Optimisation? [66.39551991177542]
  本稿では,グローバル最適化のためのサンプル手法を提案する。 この中、重要なパフォーマンス決定の自明さは、取得機能を最大化することです。 3958実験における機能最適化手法の実証的利点を強調する。
  論文  参考訳（メタデータ） (2020-12-15T12:18:38Z)

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

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