論文の概要: PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations

• arxiv url: http://arxiv.org/abs/2610.19690v1
• Date: Wed, 14 Oct 2026 07:11:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.998896
• Title: PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations
• Title（参考訳）: 付加的評価による連続遠心無切削のPPAD完全性
• Abstract要約: 完全連続な$varepsilon$-envy-free cakeアロケーションがPPAD完全であることを証明する。 任意の固定整数 $cge1$ に対して、経路上の可分な商品の割当 EF$c$ を計算することは PPAD 完全である。
• 参考スコア（独自算出の注目度）: 3.217992121350522
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that computing a complete contiguous $\varepsilon$-envy-free cake allocation is PPAD-complete for normalized rational piecewise-constant additive valuations. The hardness holds even when $\varepsilon$ is given in unary, and even when every density takes only two values, which are the same for all agents, and is piecewise constant with at most six breakpoints. As a consequence, computing an exact contiguous envy-free allocation is also PPAD-complete, and the hardness holds under the same restrictions on the densities. Our key ingredient is to assign prices to the pieces so that, in every approximately envy-free allocation, all prices are nearly equal, regardless of how the pieces are assigned to the agents. We further show that, for every fixed integer $c\ge1$, computing a contiguous EF$c$ allocation of indivisible goods on a path is PPAD-complete for additive valuations, and the hardness holds even for binary valuations in which each good is valued by exactly one agent and all agents value the same number of goods.
• Abstract（参考訳）: 完全連続な$\varepsilon$-envy-free cakeアロケーションがPPAD完全であることを示す。 この硬さは、一意に$\varepsilon$が与えられるときや、すべての密度が2つの値しか持たないときでも維持される。 結果として、厳密なエンビーフリーアロケーションの計算もPPAD完全であり、その硬さは密度に同じ制限を受ける。 我々のキーとなる要素は、各小片に価格を割り当てることであり、各小片がエージェントにどのように割り当てられているかに関わらず、ほぼ同じ価格になる。 さらに、任意の固定整数 $c\ge1$ に対して、経路上の可分な商品の割当 EF$c$ がPPAD完全であることを示す。

関連論文リスト

• Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations [5.242861402876323]
  我々は、平等主義的福祉を最大化する不可分な項目の割り当てを計算することの課題について検討する。 本結果は,3次評価を伴う最大最小割当の計算複雑性の完全な図式を提供する。
  論文  参考訳（メタデータ） (2026-10-04T14:04:02Z)
• Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure [50.58119214447535]
  マスク付き生成モデルは並列トークン予測を提供するが、正確な並列サンプリングはトークンを考慮しなければならない。 本研究は,発見を含む全評価がシーケンス長$N$のサブ線形であるかどうかを考察する。 本研究では, 森林構造を隠蔽した離散分布を, 固定された近似条件オラクルを通してアクセスする。
  論文  参考訳（メタデータ） (2026-09-29T15:39:50Z)
• The entanglement of purification is not additive [0.0]
  2012年、チェンとウィンターは、単数分数$f = 1/200$の2ビットワーナー状態は反例であると主張した。 この状態に対して、$W$, $E_Pinfty(W) le 0.9663ldots 97/100 E_P(W)$ という厳密な証明を与える。
  論文  参考訳（メタデータ） (2026-08-25T16:27:24Z)
• Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates [1.2891210250935148]
  我々は,境界遷移をサポートするMPPに対して,証明書を搬送するサブクワッドラティックな方法を提案する。 近似アレスト近傍指数は、正確に制限された演算子によって更新されたペアを選択する。 ローカルインデックスの品質だけでは、グローバルエラーを制御できない。
  論文  参考訳（メタデータ） (2026-08-07T03:32:40Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
  オンラインフェアディビジョン(オンラインフェアディビジョン)では,商品が一度に1つずつ到着し,定額のエージェントが配置されている。 善が現れると、各エージェントの持つ値が明らかになり、エージェントの1つに即時かつ不可逆的に割り当てられなければならない。 我々は、よく知られた公平性の概念に関して、最悪の場合の保証を得る方法を示す。
  論文  参考訳（メタデータ） (2025-05-28T09:48:16Z)
• Resource Allocation under the Latin Square Constraint [3.8028747063484585]
  我々は、$n$のラウンドで$n$のエージェント間で$n$の分割不可能なアイテムを割り当てる問題を提起する。 この制約は、各エージェントがラウンド毎に1つ以上のアイテムを受信し、各アイテムを最大1回受信することを保証します。 スケジューリング、リソース管理、実験的設計のような現実世界のアプリケーションは、アロケーションにおける公平性やバランス性を満たすためにラテン四角い制約を必要とする。
  論文  参考訳（メタデータ） (2025-01-11T10:53:48Z)
• (Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna [10.933894827834825]
  エージェントの集合に分割不可能な項目の集合を公平かつ効率的に割り当てることの課題について検討する。 公平性の概念として、エンビーフリーネスと比例性の最も強い緩和性を考える。
  論文  参考訳（メタデータ） (2022-02-06T01:29:50Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)

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

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