論文の概要: Maximizing $p$-Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types

• arxiv url: http://arxiv.org/abs/2610.04417v1
• Date: Sat, 03 Oct 2026 10:13:22 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-06 20:54:37.52636
• Title: Maximizing $p$-Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types
• Title（参考訳）: 高倍率設定における$p$平均社会福祉の最大化:エージェントタイプとアイテムタイプ
• Abstract要約: p$平均の福祉目的は、不可分品の割り当てに関する古典的な社会福祉基準を統一するものである。 問題は2つのアイテムタイプしか持たない$mathsfNP$-hardであることを示す。 また,p$平均社会福祉の最大化は,1つのエージェントタイプと非制限項目タイプのNPハードが強いことを示す。
• 参考スコア（独自算出の注目度）: 1.6028753486612484
• License:
• Abstract: The $p$-mean welfare objective unifies several classical social welfare criteria for the allocation of indivisible goods. We study its maximization under additive nonnegative utilities when item and agent multiplicities are encoded in binary. For every fixed finite rational $p<1$, $p\neq0$, we show that the problem is $\mathsf{NP}$-hard with only two item types. Nash welfare ($p=0$) and egalitarian welfare ($p=-\infty$) are NP-hard with three item types. These results hold both for computing an optimal allocation and for rational-threshold decision, and the utilities and threshold can be required to be positive integers. We also show that maximizing $p$-mean social welfare is strongly NP-hard with one agent type and an unrestricted number of item types, for every fixed finite rational $p<1$ and for $p=-\infty$. A quantitative gap in this reduction rules out an FPTAS in the latter setting unless $\mathsf{P}=\mathsf{NP}$. On the positive side, for a fixed number of item types and an arbitrary number of agent types, we give an FPTAS for every fixed $p\in\mathbb Q\cup\{-\infty\}$. Its running time is polynomial in the compact input length and in $1/\varepsilon$, and it returns a compressed allocation. For a fixed number of agent types and an unrestricted number of item types, we give a PTAS for every fixed finite rational $p<1$, also in the fully compact model. We further give explicit compact-model proofs of the classical exact allocation algorithms for one item type, and for egalitarian welfare with two item types. These results essentially settle the complexity and approximability of $p$-mean welfare maximization with few item types and/or few agent types, leaving only the exact complexity of Nash welfare maximization with two item types unresolved in the small-item-type classification.
• Abstract（参考訳）: p$平均の福祉目的は、不可分品の割り当てに関する古典的な社会福祉基準を統一するものである。 アイテムとエージェントの乗算がバイナリでエンコードされるとき、加法的非負の効用の下でその最大化について検討する。 すべての固定有限有理数 $p<1$, $p\neq0$ に対して、問題は 2 つの項目型しか持たない $\mathsf{NP}$-hard であることを示す。 ナッシュ福祉(p=0$)と平等福祉(p=-\infty$)は3つの項目からなるNPハードである。 これらの結果は最適割当計算と有理閾値決定の両方に当てはまり、ユーティリティと閾値は正の整数でなければならない。 また、固定有限有理数$p<1$ および$p=-\infty$ に対して、p$平均社会福祉の最大化は1つのエージェントタイプと非制限数のアイテムタイプと強くNPハードであることを示す。 この還元の量的ギャップは、$\mathsf{P}=\mathsf{NP}$でない限り、後者の設定でFPTASを除外する。 正の面において、一定数のアイテムタイプと任意の数のエージェントタイプに対して、固定された$p\in\mathbb Q\cup\{-\infty\}$に対して FPTASを与える。 その実行時間はコンパクトな入力長と1/\varepsilon$の多項式であり、圧縮されたアロケーションを返す。 固定数のエージェントタイプと非制限数のアイテムタイプに対して、完全コンパクトモデルにおいてもすべての固定有限有理数$p<1$に対してPTASを与える。 さらに,古典的厳密割当アルゴリズムを1項目タイプで明示したコンパクトモデル証明と,2項目タイプの平等福祉について述べる。 これらの結果は,小項目の分類では未解決の2項目の Nash 福祉の最大化の複雑さと近似性を,少数の項目タイプおよび/または少数のエージェントタイプで解決する。

関連論文リスト

• Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations [5.242861402876323]
  我々は、平等主義的福祉を最大化する不可分な項目の割り当てを計算することの課題について検討する。 本結果は,3次評価を伴う最大最小割当の計算複雑性の完全な図式を提供する。
  論文  参考訳（メタデータ） (2026-10-04T14:04:02Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• An Efficient Computational Framework for Discrete Fuzzy Numbers Based on Total Orders [41.99844472131922]
  我々は、$textitpos$関数を計算するために、合計(許容可能な)順序の構造を利用するアルゴリズムを導入する。 提案手法は、下層の鎖の大きさの2乗である$mathcalO(n2 m log n)$の複雑さを実現する。 その結果、この定式化は計算コストを大幅に削減することを示した。
  論文  参考訳（メタデータ） (2025-11-21T09:35:07Z)
• Computational Hardness of Reinforcement Learning with Partial $q^π$-Realizability [1.6328866317851185]
  本稿では, 線形関数近似系における強化学習の計算複雑性を部分的に$qpi$-realizability と呼ぶ。 この設定で$epsilon$-optimal Policyを学習することは、計算的に困難であることを示す。 我々の結果は$q*$-realizability(英語版)を反映し、$Pi$が最適ポリシーを超えて拡張された場合でも計算困難が持続することを示す。
  論文  参考訳（メタデータ） (2025-10-24T01:18:49Z)
• Arbitrary-Threshold Fully Homomorphic Encryption with Lower Complexity [8.228450733641122]
  我々はtextitapproximate secret sharing (ApproxSS) と呼ばれる新しいプリミティブを開発する。 任意閾値(ATh)-ApproxSS特性上におけるAThFHEの正当性と安全性を実証する。 ATASSESは3.83タイム= -- 15.4タイム=ベースライン以上のスピードアップを実現している。
  論文  参考訳（メタデータ） (2025-01-20T02:46:08Z)
• Resource Allocation under the Latin Square Constraint [3.8028747063484585]
  我々は、$n$のラウンドで$n$のエージェント間で$n$の分割不可能なアイテムを割り当てる問題を提起する。 この制約は、各エージェントがラウンド毎に1つ以上のアイテムを受信し、各アイテムを最大1回受信することを保証します。 スケジューリング、リソース管理、実験的設計のような現実世界のアプリケーションは、アロケーションにおける公平性やバランス性を満たすためにラテン四角い制約を必要とする。
  論文  参考訳（メタデータ） (2025-01-11T10:53:48Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。 我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)

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

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