論文の概要: Online Fair Division of Chores with Upgrade Recourse

• arxiv url: http://arxiv.org/abs/2611.00432v1
• Date: Fri, 30 Oct 2026 22:30:14 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 20:01:40.824727
• Title: Online Fair Division of Chores with Upgrade Recourse
• Title（参考訳）: アップグレード・リコースによる買い物のオンラインフェアディビジョン
• Abstract要約: アップグレード・リコースにおけるn$エージェント間の分別不能な雑用のオンラインフェアディビジョンについて検討する。 ラウンドロビンの簡単な適応は,最大値(2-1/n)$-approximationの最大値(2-1/n)を同時に持つ。
• 参考スコア（独自算出の注目度）: 14.257678537534273
• License:
• Abstract: We study the online fair division of indivisible chores among $n$ agents under upgrade recourse, where earlier assignments may be revised but each chore previously assigned to an agent must be replaced by a distinct chore that she finds no more costly. We show that a simple adaptation of round robin maintains envy-freeness up to one chore (EF1) together with a $(2-1/n)$-approximation of the maximin share (MMS), and that no deterministic algorithm without predictions can do better, even when all agents rank the chores in the same order. This stands in contrast to the allocation of goods, where the optimal MMS factor vanishes as $n$ grows and cannot be achieved together with EF1. Moreover, knowing only the number of chores modulo a period of length $O(n)$ (and nothing about the costs) suffices to improve upon this factor at the final configuration, while the same algorithm retains a factor below $3$ even if this information is wrong. On the other hand, envy-freeness up to any chore (EFX) essentially requires the exact number of chores: uncertainty between two consecutive values already rules out every finite approximation, and even exact knowledge does not allow EFX to be combined with an MMS guarantee better than the trivial factor of $n$.
• Abstract（参考訳）: アップグレード・リコースにおけるn$エージェント間の分別不能な雑用のオンラインフェア・ディビジョンについて検討し、それ以前の割り当てを修正できるが、以前エージェントに割り当てられた各雑用は、コストがかからない別の雑用に置き換えなければならない。 ラウンドロビンの簡単な適応は、最大2-1/nの$-approximation of the maximin Share (MMS)とともに1コレ(EF1)までエンビーフリー性を維持することを示し、全てのエージェントが同じ順序でコレをランク付けしても、予測のない決定論的アルゴリズムは良くないことを示した。 これは商品の割り当てとは対照的であり、最適のMSM因子は$n$が成長してEF1と共に達成できないため消滅する。 さらに、長さが$O(n)$ (およびコストについて何も知らない) の期間を変調するコレの数だけを知ると、最終的な設定でこの係数を改善するのに十分であり、同じアルゴリズムは、たとえこの情報が間違っているとしても、3ドル未満の係数を保持する。 二つの連続する値の間の不確実性は、既にすべての有限近似を規定しており、正確な知識でさえ、EFXが$n$の自明な因子よりも良いMMSと結合することを許さない。

関連論文リスト

• Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation [10.008162829029862]
  繰り返し評価は、狭義の不確実性を証明するためにまだ複製を必要としながら、ベンチマークスコアを正確に推定することができる。 私たちは、その要求を、ハード予算$(M+t)K$の下で、タスク毎に$L$のバイナリパスを持つ$M$タスクの固定グリッド上で特徴付けます。 固定された$L ge 3$と$0 le 1/12$の場合、最悪の純粋なコホート上での最適の期待幅は、すべてのタスクが観測されたときに$_,L([M(t+1)]-1/2)$で、$_,L([M(t+1)]-1/2)である。
  論文  参考訳（メタデータ） (2026-09-24T07:15:07Z)
• Not All Ranks Are Equal: Budget-Aware LoRA Merging Across Tasks [9.421050112988652]
  ローランクアダプタ(LoRA)のマージは、推論時にタスク固有の重みを交換するオーバーヘッドをなくすことを約束する。 この一様予算の仮定が、統合されたLoRAとタスク毎のLoRAのパフォーマンスギャップの主な原因であることを示す。
  論文  参考訳（メタデータ） (2026-09-03T21:10:28Z)
• Scaling Laws for Agent Harnesses via Effective Feedback Compute [53.68149869349268]
  emphEffective Feedback Compute (EFC)は、情報的、有効、非冗長な場合にのみフィードバックを信用し、その後の決定のために保持するトレースレベルのスケーリング座標である。 EFCベースの座標は、生の計算ベースラインよりも失敗率を常に予測する。
  論文  参考訳（メタデータ） (2026-05-28T09:45:47Z)
• Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
  オンラインフェアディビジョン(オンラインフェアディビジョン)では,商品が一度に1つずつ到着し,定額のエージェントが配置されている。 善が現れると、各エージェントの持つ値が明らかになり、エージェントの1つに即時かつ不可逆的に割り当てられなければならない。 我々は、よく知られた公平性の概念に関して、最悪の場合の保証を得る方法を示す。
  論文  参考訳（メタデータ） (2025-05-28T09:48:16Z)
• Why Ask One When You Can Ask $k$? Learning-to-Defer to the Top-$k$ Experts [6.792743621449621]
  我々は、Top-k$ Learning-to-Deferの最初のフレームワークを紹介します。 クエリを$k$のコスト効率の高いエンティティに割り当てる。 また、クエリ毎に最適な専門家数を学ぶ適応型変種であるTop-$k(x)$ Learning-to-Deferを提案する。
  論文  参考訳（メタデータ） (2025-04-17T14:50:40Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。 実現可能な最小二乗の設定において、新しい最上界を創出する。 我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
  論文  参考訳（メタデータ） (2025-04-06T18:39:45Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• Temporal Fair Division of Indivisible Items [61.235172150247614]
  分割不可能なアイテムが順次到着し,即時かつ無効に割り当てられなければならない公平な分割モデルについて検討する。 オンラインフェアディビジョンに関する以前の研究は、これらの制約の下で近似的なうらやみのない結果が得られないことを示してきた。 各ラウンドにおける累積割り当てが1項目までの時間的エンビーフリーネス(TEF1)に近似することを確実にすることを目指している。
  論文  参考訳（メタデータ） (2024-10-18T16:43:36Z)

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

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