論文の概要: PAC learning and stabilizing Hedonic Games: towards a unifying approach
- arxiv url: http://arxiv.org/abs/2301.13756v1
- Date: Tue, 31 Jan 2023 16:45:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-01 15:42:44.579800
- Title: PAC learning and stabilizing Hedonic Games: towards a unifying approach
- Title（参考訳）: pac学習と安定的ヘドニックゲーム--統一的アプローチに向けて
- Authors: Simone Fioravanti, Michele Flammini, Bojana Kodric and Giovanna
Varricchio
- Abstract要約: ヘドニックゲーム(HG)のPAC学習性とPAC安定化性について検討する。
そこで本研究では,効率的な学習可能性をもたらす2つの条件を同定し,その条件が既知の肯定的な学習可能性の結果をすべて包含する。
安定性の面では、アドホック対向分布の選択の自由がPAC安定性を達成するための最も明白なハードルであることは明らかであるが、それだけではない。
- 参考スコア（独自算出の注目度）: 10.856422132960164
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study PAC learnability and PAC stabilizability of Hedonic Games (HGs),
i.e., efficiently inferring preferences or core-stable partitions from samples.
We first expand the known learnability/stabilizability landscape for some of
the most prominent HGs classes, providing results for Friends and Enemies
Games, Bottom Responsive, and Anonymous HGs. Then, having a broader view in
mind, we attempt to shed light on the structural properties leading to
learnability/stabilizability, or lack thereof, for specific HGs classes. Along
this path, we focus on the fully expressive Hedonic Coalition Nets
representation of HGs. We identify two sets of conditions that lead to
efficient learnability, and which encompass all of the known positive
learnability results. On the side of stability, we reveal that, while the
freedom of choosing an ad hoc adversarial distribution is the most obvious
hurdle to achieving PAC stability, it is not the only one. First, we show a
distribution independent necessary condition for PAC stability. Then, we focus
on $\W$-games, where players have individual preferences over other players and
evaluate coalitions based on the least preferred member. We prove that these
games are PAC stabilizable under the class of bounded distributions, which
assign positive probability mass to all coalitions. Finally, we discuss why
such a result is not easily extendable to other HGs classes even in this
promising scenario. Namely, we establish a purely computational property
necessary for achieving PAC stability.
- Abstract（参考訳）: 本研究では,Hedonic Games (HGs) のPAC学習性およびPAC安定化性について検討した。
我々はまず、最も著名なHGsクラスの学習可能性/安定化の展望を拡張し、Friends and Enemies Games, Bottom Responsive, Anonymous HGsの結果を提供する。
そして、より広い視点を念頭に置いて、特定のHGsクラスに対する学習可能性/安定化性、あるいはその欠如につながる構造的特性について光を当てようと試みる。
この経路に沿って、HGの完全表現型Hedonic Coalition Nets表現に焦点を当てる。
我々は、効率的な学習可能性につながる2つの条件を特定し、既知のポジティブな学習可能性の結果をすべて包含する。
安定性の面では、アドホック対向分布の選択の自由がPAC安定性を達成するための最も明白なハードルであることは明らかであるが、それだけではない。
まず,PAC安定化のための分散独立条件を示す。
次に、プレイヤーが他のプレイヤーよりも個別に好みを持つ$\W$-gamesに焦点を合わせ、最も好まれないメンバーに基づいて連立を評価する。
これらのゲームは、すべての連立に正の確率質量を割り当てる有界分布のクラスの下で、PAC安定化可能であることを証明している。
最後に、このような結果が、この有望なシナリオであっても、他のHGクラスに容易に拡張できない理由について議論する。
すなわち、PAC安定性を達成するのに必要な純粋に計算的性質を確立する。
関連論文リスト
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
両面のマッチング市場は、市場の片側からの参加者が好みに応じて反対側からの参加者と一致しなければならない、一連の問題を記述している。
我々は安定解の構造を利用して、安定解を見つける可能性を改善するアルゴリズムを考案する。
論文 参考訳（メタデータ） (2024-10-06T06:47:53Z) - On the Computability of Robust PAC Learning [9.507869508188266]
本稿では,頑健な計算可能PAC(robust CPAC)学習の問題を紹介する。
このセットアップにおける学習性は,コンポーネントの組み合わせによってもたらされるものではない。
我々はその有限性は必要であるが、堅牢なCPAC学習には不十分であることを証明した。
論文 参考訳（メタデータ） (2024-06-14T16:20:04Z) - Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
本稿では,最近の3つのオープンな質問を解き,CPAC学習可能性の研究に寄与する。
まず,全てのCPAC学習可能なクラスが,サンプルの複雑さで適切なCPAC学習が可能なクラスに含まれることを証明した。
第二に、適切に学習できるが、計算不能に急速に増加するサンプルの複雑さに限り、決定可能な仮説のクラスが存在することを示す。
論文 参考訳（メタデータ） (2023-02-06T02:52:36Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳（メタデータ） (2022-07-25T18:29:16Z) - On Higher Adversarial Susceptibility of Contrastive Self-Supervised
Learning [104.00264962878956]
コントラスト型自己教師学習(CSL)は,画像と映像の分類において,教師あり学習のパフォーマンスに適合するか上回っている。
2つの学習パラダイムによって誘導される表現の性質が似ているかどうかは、いまだに不明である。
我々は,CSL表現空間における単位超球面上のデータ表現の均一分布を,この現象の鍵となる要因として同定する。
CSLトレーニングでモデルロバスト性を改善するのにシンプルだが有効である戦略を考案する。
論文 参考訳（メタデータ） (2022-07-22T03:49:50Z) - Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。
私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
論文 参考訳（メタデータ） (2021-08-19T17:59:28Z) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳（メタデータ） (2021-07-03T23:17:26Z) - Optimality and Stability in Federated Learning: A Game-theoretic
Approach [0.0]
我々は,フェデレーションエージェント(プレーヤ)の平均誤差率によって与えられる最適性の概念を動機付け,定義する。
まず、パラメータ空間のいくつかの領域に対して、すべての安定な配置が最適である(アナーキーの値が 1 に等しい)ことを示す。
しかし、これはすべての設定に当てはまるものではなく、最適よりも高いコストで安定な配置の例が存在する(AnaarchyのPrice of Anarchy larger than 1)。
論文 参考訳（メタデータ） (2021-06-17T15:03:51Z) - Semi-verified PAC Learning from the Crowd [7.594050968868919]
本研究では,クラウドソース型PAC学習におけるしきい値関数の問題点について検討する。
本稿では,Charikar等の半検証モデルを用いて,PACが基礎となる仮説クラスを大量のラベルクエリで学習可能であることを示す。
論文 参考訳（メタデータ） (2021-06-13T20:05:16Z) - Independent Policy Gradient Methods for Competitive Reinforcement
Learning [62.91197073795261]
2つのエージェントによる競争強化学習環境における独立学習アルゴリズムに対するグローバル・非漸近収束保証を得る。
本研究は,両選手がタンデムで政策勾配法を実行すると,学習率を2回ルールに従えば,その政策はゲームの最小均衡に収束することを示す。
論文 参考訳（メタデータ） (2021-01-11T23:20:42Z) - On Singleton Congestion Games with Resilience Against Collusion [0.0]
同一かつコスト関数の増大を伴うシングルトン混雑ゲームのサブクラスについて検討する。
我々の主な貢献は、偏差を弱く改善するための弾力性のある平衡結果の存在を証明する新しいアプローチである。
論文 参考訳（メタデータ） (2020-11-03T15:35:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。