論文の概要: Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions

• arxiv url: http://arxiv.org/abs/2602.14321v1
• Date: Sun, 15 Feb 2026 22:05:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-17 16:22:49.953108
• Title: Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions
• Title（参考訳）: 重なりうる重なりを持つナッシュ安定結合構造のオフライン学習
• Authors: Saar Cohen,
• Abstract要約: 連合の形成は、その好みに基づいて連立を結成する利己的なエージェントの戦略的協力に関するものである。 連立は不一致であり、実際には成立しないかもしれない選好が完全に知られているとしばしば仮定される。 部分的な情報の下で重なる可能性のある連立による連立形成の新しいモデルを提案する。
• 参考スコア（独自算出の注目度）: 7.310043452300736
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Coalition formation concerns strategic collaborations of selfish agents that form coalitions based on their preferences. It is often assumed that coalitions are disjoint and preferences are fully known, which may not hold in practice. In this paper, we thus present a new model of coalition formation with possibly overlapping coalitions under partial information, where selfish agents may be part of multiple coalitions simultaneously and their full preferences are initially unknown. Instead, information about past interactions and associated utility feedback is stored in a fixed offline dataset, and we aim to efficiently infer the agents' preferences from this dataset. We analyze the impact of diverse dataset information constraints by studying two types of utility feedback that can be stored in the dataset: agent- and coalition-level utility feedback. For both feedback models, we identify assumptions under which the dataset covers sufficient information for an offline learning algorithm to infer preferences and use them to recover a partition that is (approximately) Nash stable, in which no agent can improve her utility by unilaterally deviating. Our additional goal is devising algorithms with low sample complexity, requiring only a small dataset to obtain a desired approximation to Nash stability. Under agent-level feedback, we provide a sample-efficient algorithm proven to obtain an approximately Nash stable partition under a sufficient and necessary assumption on the information covered by the dataset. However, under coalition-level feedback, we show that only under a stricter assumption is sufficient for sample-efficient learning. Still, in multiple cases, our algorithms' sample complexity bounds have optimality guarantees up to logarithmic factors. Finally, extensive experiments show that our algorithm converges to a low approximation level to Nash stability across diverse settings.
• Abstract（参考訳）: 連合の形成は、その好みに基づいて連立を結成する利己的なエージェントの戦略的協力に関するものである。 連立は不一致であり、実際には成立しないかもしれない選好が完全に知られているとしばしば仮定される。 そこで,本稿では,複数の連立に同時に参加し,その全選好が不明な自己中心的な連立組織形成モデルを提案する。 代わりに、過去のインタラクションや関連するユーティリティフィードバックに関する情報は、固定されたオフラインデータセットに格納され、このデータセットからエージェントの好みを効率的に推測することを目的としています。 我々は、データセットに格納できる2種類のユーティリティフィードバック(エージェントレベルと連立レベルのユーティリティフィードバック)を研究することで、多様なデータセット情報制約の影響を分析する。 両方のフィードバックモデルに対して、データセットが選好を推測するオフライン学習アルゴリズムの十分な情報をカバーしている仮定を特定し、(ほぼ) Nash の安定なパーティションを復元する。 我々の新たなゴールは、サンプルの複雑さが低いアルゴリズムを考案し、Nashの安定性に対する望ましい近似を得るためには、小さなデータセットしか必要としないことです。 エージェントレベルのフィードバックの下で、データセットがカバーする情報について十分な仮定と必要な仮定の下で、およそナッシュの安定なパーティションが得られることが証明されたサンプル効率のアルゴリズムを提供する。 しかし、連立レベルのフィードバックの下では、より厳密な仮定の下でのみ、サンプル効率の学習に十分であることを示す。 それでも、複数の場合において、我々のアルゴリズムのサンプル複雑性境界は対数的因子の最適性を保証する。 最後に、広範囲な実験により、我々のアルゴリズムは様々な設定にわたってナッシュ安定性に低い近似レベルに収束することを示した。

関連論文リスト

• FedCanon: Non-Convex Composite Federated Learning with Efficient Proximal Operation on Heterogeneous Data [17.80715992954134]
  複合学習は、追加の正規化用語で機械学習問題を解決するための一般的なフレームワークを提供する。 我々は非滑らかな正規化問題を解くためにFedCanonアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-16T09:28:26Z)
• Preference-Based Multi-Agent Reinforcement Learning: Data Coverage and Algorithmic Techniques [65.55451717632317]
  PbMARL(Preference-based Multi-Agent Reinforcement Learning)について検討する。 一般ゲームにおける嗜好のみのオフラインデータセットからナッシュ平衡を同定する。 以上の結果から,PbMARLの多面的アプローチが示唆された。
  論文  参考訳（メタデータ） (2024-09-01T13:14:41Z)
• The Battleship Approach to the Low Resource Entity Matching Problem [0.0]
  本稿では,エンティティマッチング問題に対する新しいアクティブな学習手法を提案する。 我々は、エンティティマッチングのユニークな特性を利用する選択メカニズムに焦点を当てる。 実験により,提案アルゴリズムは,最先端のアクティブ・ラーニング・ソリューションより低リソース・エンティティ・マッチングに優れることを示した。
  論文  参考訳（メタデータ） (2023-11-27T10:18:17Z)
• Deep Active Ensemble Sampling For Image Classification [8.31483061185317]
  アクティブラーニングフレームワークは、最も有益なデータポイントのラベル付けを積極的に要求することで、データアノテーションのコストを削減することを目的としている。 提案手法には、不確実性に基づく手法、幾何学的手法、不確実性に基づく手法と幾何学的手法の暗黙の組み合わせなどがある。 本稿では, サンプル選択戦略における効率的な探索・探索トレードオフを実現するために, 不確実性に基づくフレームワークと幾何学的フレームワークの両方の最近の進歩を革新的に統合する。 本フレームワークは,(1)正確な後続推定,(2)計算オーバーヘッドと高い精度のトレードオフの2つの利点を提供する。
  論文  参考訳（メタデータ） (2022-10-11T20:20:20Z)
• Federated Offline Reinforcement Learning [55.326673977320574]
  マルチサイトマルコフ決定プロセスモデルを提案する。 我々は,オフラインRLを対象とした最初のフェデレーション最適化アルゴリズムを設計する。 提案アルゴリズムでは,学習ポリシーの準最適性は,データが分散していないような速度に匹敵する,理論的保証を与える。
  論文  参考訳（メタデータ） (2022-06-11T18:03:26Z)
• Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets [101.5329678997916]
  両プレイヤーゼロサムマルコフゲーム(MG)をオフライン環境で研究する。 目標は、事前収集されたデータセットに基づいて、近似的なナッシュ均衡(NE)ポリシーペアを見つけることである。
  論文  参考訳（メタデータ） (2022-02-15T15:39:30Z)
• Controllable Guarantees for Fair Outcomes via Contrastive Information Estimation [32.37031528767224]
  トレーニングデータセットにおけるバイアスの制御は、下流のアプリケーションで異なるグループ間で平等に扱われることを保証するために不可欠である。 対比情報推定器に基づく相互情報によるパリティ制御の効果的な方法を示す。 uci成人および遺産健康データセットに対する我々のアプローチをテストし、このアプローチが所望のパリティ閾値にまたがってより有益な表現を提供することを実証する。
  論文  参考訳（メタデータ） (2021-01-11T18:57:33Z)
• Learning while Respecting Privacy and Robustness to Distributional Uncertainties and Adversarial Data [66.78671826743884]
  分散ロバストな最適化フレームワークはパラメトリックモデルのトレーニングのために検討されている。 目的は、逆操作された入力データに対して頑健なトレーニングモデルを提供することである。 提案されたアルゴリズムは、オーバーヘッドがほとんどない堅牢性を提供する。
  論文  参考訳（メタデータ） (2020-07-07T18:25:25Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)

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

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