論文の概要: Sparse Probabilistic Coalition Structure Generation: Bayesian Greedy Pursuit and $\ell_1$ Relaxations

• arxiv url: http://arxiv.org/abs/2601.00329v1
• Date: Thu, 01 Jan 2026 12:50:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-05 15:04:33.380946
• Title: Sparse Probabilistic Coalition Structure Generation: Bayesian Greedy Pursuit and $\ell_1$ Relaxations
• Title（参考訳）: Sparse Probabilistic Coalition Structure Generation: Bayesian Greedy Pursuit and $\ell_1$ Relaxations
• Authors: Angshul Majumdar,
• Abstract要約: 連立構造生成(CSG)は、連立価値が与えられていないが、エピソード的な観察から学ばなければならない。 我々は,各エピソードを疎線形回帰問題としてモデル化し,実現されたペイオフ (Y_t) は少数の連立貢献の雑音の多い線形結合である。 これにより、まず(T)エピソードからスパース値関数を推定し、推論された連立集合上でCSGソルバを実行する確率的CSGフレームワークが得られる。
• 参考スコア（独自算出の注目度）: 11.62669179647184
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study coalition structure generation (CSG) when coalition values are not given but must be learned from episodic observations. We model each episode as a sparse linear regression problem, where the realised payoff \(Y_t\) is a noisy linear combination of a small number of coalition contributions. This yields a probabilistic CSG framework in which the planner first estimates a sparse value function from \(T\) episodes, then runs a CSG solver on the inferred coalition set. We analyse two estimation schemes. The first, Bayesian Greedy Coalition Pursuit (BGCP), is a greedy procedure that mimics orthogonal matching pursuit. Under a coherence condition and a minimum signal assumption, BGCP recovers the true set of profitable coalitions with high probability once \(T \gtrsim K \log m\), and hence yields welfare-optimal structures. The second scheme uses an \(\ell_1\)-penalised estimator; under a restricted eigenvalue condition, we derive \(\ell_1\) and prediction error bounds and translate them into welfare gap guarantees. We compare both methods to probabilistic baselines and identify regimes where sparse probabilistic CSG is superior, as well as dense regimes where classical least-squares approaches are competitive.
• Abstract（参考訳）: 連立構造生成(CSG)は、連立価値が与えられていないが、エピソード的な観察から学ばなければならない。 我々は各エピソードを疎線形回帰問題としてモデル化し、実現されたペイオフ \(Y_t\) は、少数の連立貢献の雑音の多い線形結合である。 これにより確率的CSGフレームワークが得られ、まずプランナーは、まず \(T\) エピソードからスパース値関数を推定し、次に推論された連立集合上でCSGソルバを実行する。 私たちは2つの見積スキームを分析します。 最初のBayesian Greedy Coalition Pursuit (BGCP)は、直交的マッチングを模倣する欲求的な手続きである。 コヒーレンス条件と最小信号仮定の下で、BGCPは高い確率で有益な連立の真の集合を回復する(T \gtrsim K \log m\)。 第二のスキームは \(\ell_1\)-penalized estimator を用いており、制限された固有値条件の下では、 \(\ell_1\) と予測誤差境界を導出し、それらを福祉ギャップ保証に変換する。 確率的ベースラインと疎確率的CSGが優れているレジームと、古典的最小二乗アプローチが競合する高密度レジームを比較した。

関連論文リスト

• Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities [51.320599504997745]
  統計物理学からの予測では、ブロックモデル(SBM)におけるコミュニティの回復は、上述の時間で可能であり、上述のケステンスティグム(KS)しきい値のみである。 Chinら(2025)は、最近、スパース体制では、非バックトラック経路を数えることにより、KS閾値以下でコミュニティの回復が可能であることを証明した。
  論文  参考訳（メタデータ） (2025-09-19T09:53:56Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Convergence Rates of Constrained Expected Improvement [11.79168261900291]
  制約付き予測改善法(CEI)は、制約付きブラックボックス最適化のための一般的なCBO法である。 我々は,CEIの収束速度を,その単純な後悔の上界を解析して検討した。 ガウス過程から$f$ と $c$ がサンプリングされると仮定すると、CEI は高い確率で同じ収束率が得られることを示す。
  論文  参考訳（メタデータ） (2025-05-16T14:44:13Z)
• $\varepsilon$-fractional Core Stability in Hedonic Games [13.576268908412338]
  ヘドニックゲーム(Hedonic Games、HG)は、戦略エージェントの連携をモデル化するためのフレームワークである。 我々は、全ての可能な連立の少なくとも$varepsilon$-fractionがコアブロックを形成することができるような、$varepsilon$-fractional core-stabilityの概念を提案する。 具体的には、$varepsilon$-fractional core-stable partitionを返却する効率的なアルゴリズムを設計し、$varepsilon$はエージェント数を指数関数的に減少させる。
  論文  参考訳（メタデータ） (2023-11-18T15:30:29Z)
• QuACS: Variational Quantum Algorithm for Coalition Structure Generation in Induced Subgraph Games [0.0]
  我々は、ISGにおける結合構造生成のための新しいハイブリッド量子古典アルゴリズムを提案する。 提案アルゴリズムは既存の近似古典解法よりも$mathcalO(n2)$,予測近似比$92%$で優れていることを示す。 量子ビットの数は大幅に少なく、既存の量子解と比較して中規模の問題の実験が可能である。
  論文  参考訳（メタデータ） (2023-04-14T16:01:27Z)
• GCS-Q: Quantum Graph Coalition Structure Generation [0.0]
  本稿では、連立構造生成における誘導サブグラフゲーム(ISG)のための新しい量子支援ソリューションGCS-Qを提案する。 我々はGCS-Qが、現在最も優れた古典的ソルバを、n2$の順で実行し、予想最悪の近似比が標準ベンチマークデータセットで93%の順で上回っていることを示す。
  論文  参考訳（メタデータ） (2022-12-21T21:22:06Z)
• Will My Robot Achieve My Goals? Predicting the Probability that an MDP Policy Reaches a User-Specified Behavior Target [56.99669411766284]
  自律的なシステムがタスクを実行する場合、ユーザの目標を達成する確率のキャリブレーションされた見積もりを維持する必要がある。 本稿では,ユーザの目標が目標間隔として指定される設定について検討する。 我々は、共形予測を反転させて確率推定を計算する。
  論文  参考訳（メタデータ） (2022-11-29T18:41:20Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)

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

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