論文の概要: Online Fair Division with Budget Constraints

• arxiv url: http://arxiv.org/abs/2607.23310v1
• Date: Sat, 25 Jul 2026 17:53:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-28 22:34:15.058309
• Title: Online Fair Division with Budget Constraints
• Title（参考訳）: 予算制約のあるオンラインフェアディビジョン
• Abstract要約: 一般化された割当予算制約の下で離散公正分割のオンライン版について検討する。 まず、付加的な構造がなければ、決定論的オンラインアルゴリズムが固定的な近似を保証できないことを示す。 次に,有意な保証を回復する構造条件として,有界密度の拡散を同定する。
• 参考スコア（独自算出の注目度）: 20.176419497210585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient's bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees.
• Abstract（参考訳）: 一般化された割当予算制約の下で離散公正分割のオンライン版について検討する。 商品は一度に1つずつ到着し、すべての割り当てられていない商品を保有する実行可能なエージェントや慈善団体に不当に割り当てられなければならないが、公平性はすべての受信者のバンドルの予算可能なサブセットに対してのみ評価される。 まず、追加構造がなければ、決定論的オンラインアルゴリズムは、高度に対称な例であっても、実現可能なエンビーフリー性に対する固定近似を保証できないことを示す。 次に、有意な保証を復元し、任意のアイテムサイズに対する近似アルゴリズムを取得し、共通の評価と十分な小物の下で、これらの保証が最適な決定論的フロンティアに強化されることを示す構造条件として、有界密度の拡散を識別する。 さらに、オンラインアルゴリズムがフェアネスベンチマークよりも若干大きな予算を許容し、達成可能な保証の改善を特徴付けるリソース拡張について研究する。 最後に,共同価値の型予測,完全予測下での一貫性の証明,予測誤差に対する堅牢性,および値とサイズとの差分予測が不十分であることを示す。

関連論文リスト

• The Limits of AI-Driven Allocation: Optimal Screening under Aleatoric Uncertainty [16.186900569675114]
  スクリーニングとアルゴリズム的ターゲティングを2段階のアロケーションフレームワークで最適に組み合わせる方法を示す。 最適戦略は、アルゴリズム割り当ての限界において、最もリスクの高いユニットを直接ターゲットとしながら、ユニットをスクリーニングする。 コロンビアにおける所得に基づく社会保護プログラムと人道的マイニングの応用について,我々の枠組みを解説する。
  論文  参考訳（メタデータ） (2026-05-08T16:38:58Z)
• Robust and Consistent Ski Rental with Distributional Advice [13.811651343801579]
  スキーレンタル問題は不確実性の下でのオンライン意思決定の標準モデルである。 本稿では,未知品質の分布的アドバイスを決定論的アルゴリズムとランダム化アルゴリズムの両方に統合するフレームワークを提案する。 我々のフレームワークは、既存の点予測ベースラインよりも一貫性を著しく向上し、かつ、同等の堅牢性を維持していることを示す。
  論文  参考訳（メタデータ） (2026-03-31T04:04:21Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COINは、統計的に有効な閾値を校正し、質問毎に1つの生成された回答をフィルタリングする不確実性保護選択フレームワークである。 COINはキャリブレーションセット上で経験的誤差率を推定し、信頼区間法を適用して真誤差率に高い確率上界を確立する。 リスク管理におけるCOINの堅牢性,許容回答を維持するための強いテストタイムパワー,キャリブレーションデータによる予測効率を実証する。
  論文  参考訳（メタデータ） (2025-06-25T07:04:49Z)
• Online Fair Division with Additional Information [7.435063833417366]
  オンライン環境では,特定不可能な商品をエージェントにかなり割り当てる問題について検討する。 我々は、将来の商品に関する情報の入手が、公平なアロケーションの存在と近似性にどのように影響するかを問う。 既知結果よりも高い公平性を保証するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-05-30T12:06:16Z)
• SConU: Selective Conformal Uncertainty in Large Language Models [59.25881667640868]
  SconU(Selective Conformal Uncertainity)と呼ばれる新しいアプローチを提案する。 我々は,特定の管理可能なリスクレベルで設定されたキャリブレーションの不確実性分布から,与えられたサンプルが逸脱するかどうかを決定するのに役立つ2つの共形p値を開発する。 我々のアプローチは、単一ドメインと学際的コンテキストの両方にわたる誤発見率の厳密な管理を促進するだけでなく、予測の効率を高める。
  論文  参考訳（メタデータ） (2025-04-19T03:01:45Z)
• End-to-End Conformal Calibration for Optimization Under Uncertainty [32.844953018302874]
  本稿では,条件最適化のための不確実性推定を学習するためのエンドツーエンドフレームワークを開発する。 さらに,部分凸ニューラルネットワークを用いた任意の凸不確実性集合の表現を提案する。 我々のアプローチは2段階最適化によって一貫して改善される。
  論文  参考訳（メタデータ） (2024-09-30T17:38:27Z)
• Calibrated Probabilistic Forecasts for Arbitrary Sequences [58.54729945445505]
  実際のデータストリームは、分散シフトやフィードバックループ、敵アクターによって予測不可能に変化する可能性がある。 データがどのように進化するかに関わらず、有効な不確実性推定を保証するための予測フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-27T21:46:42Z)
• Adjusting Regression Models for Conditional Uncertainty Calibration [46.69079637538012]
  本稿では,分割共形予測手法を適用して条件付きカバレッジを改善するために,回帰関数を訓練する新しいアルゴリズムを提案する。 本研究では,条件付きカバレッジと名目付きカバレッジ率の差分を求める上限を確立し,この上限値を制御するためのエンドツーエンドアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-26T01:55:45Z)
• Probabilistic Conformal Prediction with Approximate Conditional Validity [81.30551968980143]
  本研究では,共形手法の柔軟性と条件分布の推定を組み合わせ,予測セットを生成する手法を開発した。 我々の手法は、条件付きカバレッジの観点から既存の手法よりも一貫して優れています。
  論文  参考訳（メタデータ） (2024-07-01T20:44:48Z)
• Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
  本稿では,複数のエージェントが環境を探索し,その経験を中央サーバを通じて伝達する分散強化学習環境について考察する。 エージェントの$alpha$-fractionは敵対的であり、任意の偽情報を報告することができる。 我々は、これらの対立エージェントの存在下で、マルコフ決定プロセスの根底にある準最適政策を特定することを模索する。
  論文  参考訳（メタデータ） (2022-06-01T00:44:53Z)
• Fair Classification with Adversarial Perturbations [35.030329189029246]
  本研究は,学習サンプルの任意の$eta$-fractionを選択でき,保護属性を任意に摂動することができるような,万能な逆境の存在下での公平な分類について検討する。 我々の主な貢献は、精度と公正性に関する証明可能な保証を伴うこの逆条件で公平な分類法を学ぶための最適化フレームワークである。 我々は、自然な仮説クラスに対する我々のフレームワークの保証のほぼ正当性を証明している: どのアルゴリズムもはるかに精度が良く、より良い公正性を持つアルゴリズムは、より低い精度でなければならない。
  論文  参考訳（メタデータ） (2021-06-10T17:56:59Z)

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

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