論文の概要: Fair Online Resource Allocation

• arxiv url: http://arxiv.org/abs/2606.18679v2
• Date: Thu, 18 Jun 2026 03:25:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-19 13:55:51.809779
• Title: Fair Online Resource Allocation
• Title（参考訳）: オンライン・リソース・アロケーション
• Authors: Christopher En, Yuri Faenza, Andrea Lodi, Gonzalo Muñoz,
• Abstract要約: 本研究では,難民再定住や航空スケジューリングなどの応用を動機とした,公平なオンライン資源配分の課題について検討する。 本稿では,資源制約とリプシッツフェアネス要件を考慮に入れた総合福祉を最大化するモデルを提案する。
• 参考スコア（独自算出の注目度）: 3.949078564650437
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of fair online resource allocation, motivated by applications such as refugee resettlement and airline scheduling, where agents arrive sequentially and must be assigned to facilities with limited capacities. We introduce a model that maximizes the overall welfare subject to resource constraints and a Lipschitz fairness requirement, which ensures that similar agents arriving in the same batch receive similar expected outcomes. We first analyze the offline problem, proving that the value of the optimal fair allocation is at least an $Ω(1/γ)$ fraction of the optimal unfair allocation, where $γ$ is the fairness coefficient, thereby bounding the price of fairness. For the online setting, we propose an algorithm based on dual mirror descent that enforces fairness constraints within batches while estimating optimal dual variables. We prove that this algorithm achieves sublinear regret relative to the optimal offline fluid benchmark. Finally, we validate our theoretical results using real-world data from the Refugee Economies Programme, demonstrating the algorithm's performance and examining the trade-offs between welfare maximization and fairness enforcement.
• Abstract（参考訳）: 本研究では,難民再定住や航空スケジューリングなどの応用を動機とした,公正なオンライン資源配分の問題について検討し,エージェントが順次到着し,限られた能力を有する施設に配属する必要がある。 資源制約による福祉の全体像とリプシッツフェアネス要件を最大化するモデルを導入し,同バッチに同程度のエージェントが同様の期待結果を受け取ることを保証した。 まず、最適フェアアロケーションの値が最適不公平アロケーションの少なくとも$Ω(1/γ)$分であり、そこでは$γ$がフェアネス係数であり、したがってフェアネスの値の境界となることを証明して、オフライン問題を分析する。 オンライン環境では、最適2変数を推定しながら、バッチ内で公正な制約を強制する二重ミラー降下に基づくアルゴリズムを提案する。 このアルゴリズムは, 最適オフライン流体ベンチマークと比較して, サブ線形後悔を実現する。 最後に,Refugee Economies Programmeから得られた実世界のデータを用いて,アルゴリズムの性能を実証し,福祉最大化と公正化のトレードオフを検証した。

関連論文リスト

• Online Generalized-mean Welfare Maximization: Achieving Near-Optimal Regret from Samples [29.8171362564092]
  我々は、不均一な好みを持つ$n$エージェントのうち、連続的に到着する$T$のオンラインフェアアロケーションについて検討した。 純粋欲求アルゴリズム(ミオプティックに福祉最大化積分割当を選択する)が平均的後悔の$widetildeO(1/T)を達成していることを示す。
  論文  参考訳（メタデータ） (2026-02-11T03:16:03Z)
• Fairness Aware Reward Optimization [78.85867531002346]
  本稿では,Fairness Aware Reward Optimization (Faro)を紹介した。Fairness Aware Reward Optimization (Faro)は,階層的平等,等化オッズ,あるいは反実的フェアネス制約の下で報酬モデルを訓練するプロセス内フレームワークである。 LLMアライメントにおける報酬レベルの公平性に関する最初の理論的解析を行った。 Faroはモデルの品質を維持したり改善したりしながら、バイアスや有害な世代を著しく削減します。
  論文  参考訳（メタデータ） (2026-02-08T03:35:49Z)
• Cost Efficient Fairness Audit Under Partial Feedback [14.57835291220813]
  本研究では,ある分類器の公平さを部分的フィードバック下で監査する問題について検討する。 追加ラベル付きデータを取得するための新しいコストモデルを導入する。 我々のアルゴリズムは監査コストの点で自然ベースラインを約50%上回っていることを示す。
  論文  参考訳（メタデータ） (2025-10-04T08:38:03Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• Bridging Jensen Gap for Max-Min Group Fairness Optimization in Recommendation [63.66719748453878]
  グループ・マックスミン・フェアネス(MMF)は、最適化の目的として、フェアネス・アウェア・レコメンダシステム(RS)で一般的に使用される。 本稿では,Jensenギャップを最小化するために2つの最適化手法を利用するFairDualというアルゴリズムを提案する。 理論的解析により、FairDualは、大域的最適解に対するサブ線形収束率を達成できることが示されている。
  論文  参考訳（メタデータ） (2025-02-13T13:33:45Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。 過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。 報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
  論文  参考訳（メタデータ） (2024-05-26T05:38:50Z)
• Fair and Optimal Classification via Post-Processing [10.163721748735801]
  本稿では、分類問題における人口統計学の特質的トレードオフの完全な評価について述べる。 ランダム化および属性認識フェア分類器によって達成可能な最小誤差率は、ワッサーシュタイン・バリセンタ問題の最適値によって与えられることを示す。
  論文  参考訳（メタデータ） (2022-11-03T00:04:04Z)
• Fairer LP-based Online Allocation [13.478067250930101]
  本稿では,リニアプログラム(LP)に基づくオンラインリソース割り当て問題について考察する。 内部点LPソルバを用いて不公平な資源支出を動的に検出するフェアアルゴリズムを提案する。 提案手法は最適化インスタンスの制約としてフェアネス要件を定式化せず,アルゴリズム設計の観点からこの問題に対処する。
  論文  参考訳（メタデータ） (2021-10-27T17:45:20Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。 この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。 目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
  論文  参考訳（メタデータ） (2020-07-01T14:24:58Z)

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

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