論文の概要: $\varepsilon$-fractional Core Stability in Hedonic Games
- arxiv url: http://arxiv.org/abs/2311.11101v2
- Date: Sun, 14 Jan 2024 13:51:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-18 00:49:37.448219
- Title: $\varepsilon$-fractional Core Stability in Hedonic Games
- Title(参考訳): ヘドニックゲームにおける$\varepsilon$-fractional core stability
- Authors: Simone Fioravanti, Michele Flammini, Bojana Kodric and Giovanna
Varricchio
- Abstract要約: ヘドニックゲーム(Hedonic Games、HG)は、戦略エージェントの連携をモデル化するためのフレームワークである。
我々は、全ての可能な連立の少なくとも$varepsilon$-fractionがコアブロックを形成することができるような、$varepsilon$-fractional core-stabilityの概念を提案する。
具体的には、$varepsilon$-fractional core-stable partitionを返却する効率的なアルゴリズムを設計し、$varepsilon$はエージェント数を指数関数的に減少させる。
- 参考スコア(独自算出の注目度): 13.576268908412338
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Hedonic Games (HGs) are a classical framework modeling coalition formation of
strategic agents guided by their individual preferences. According to these
preferences, it is desirable that a coalition structure (i.e. a partition of
agents into coalitions) satisfies some form of stability. The most well-known
and natural of such notions is arguably core-stability. Informally, a partition
is core-stable if no subset of agents would like to deviate by regrouping in a
so-called core-blocking coalition. Unfortunately, core-stable partitions seldom
exist and even when they do, it is often computationally intractable to find
one. To circumvent these problems, we propose the notion of
$\varepsilon$-fractional core-stability, where at most an
$\varepsilon$-fraction of all possible coalitions is allowed to core-block. It
turns out that such a relaxation may guarantee both existence and
polynomial-time computation. Specifically, we design efficient algorithms
returning an $\varepsilon$-fractional core-stable partition, with $\varepsilon$
exponentially decreasing in the number of agents, for two fundamental classes
of HGs: Simple Fractional and Anonymous. From a probabilistic point of view,
being the definition of $\varepsilon$-fractional core equivalent to requiring
that uniformly sampled coalitions core-block with probability lower than
$\varepsilon$, we further extend the definition to handle more complex sampling
distributions. Along this line, when valuations have to be learned from samples
in a PAC-learning fashion, we give positive and negative results on which
distributions allow the efficient computation of outcomes that are
$\varepsilon$-fractional core-stable with arbitrarily high confidence.
- Abstract(参考訳): ヘドニックゲーム(Hedonic Games, HGs)は、古典的なフレームワークモデリングによる戦略エージェントの連立組織である。
これらの選好によれば、連立構造(すなわち、エージェントを連立に分割する)がある種の安定性を満たすことが望ましい。
そのような概念の最もよく知られた自然は、間違いなく核安定性である。
非公式に、エージェントのサブセットがいわゆるcore-blocking coalitionで再グループ化することを望まない場合、パーティションはcore-stableである。
残念なことに、コア安定なパーティションは滅多に存在せず、たとえそうであっても、そのパーティションを見つけることは計算的に困難であることが多い。
これらの問題を回避するために、我々は$\varepsilon$-fractional core-stabilityという概念を提案する。
このような緩和は、存在と多項式時間計算の両方を保証する可能性がある。
具体的には,HG の基本クラスである Simple Fractional と Anonymous の2つに対して,$\varepsilon$-fractional core-stable partition と $\varepsilon$ を指数関数的に減少させる効率的なアルゴリズムを設計する。
確率論的な観点では、$\varepsilon$-fractional coreの定義は、$\varepsilon$よりも低い確率で一様にサンプリングされた結合コアブロックを要求するのと同値であるので、より複雑なサンプリング分布を扱うために定義をさらに拡張する。
この線に沿って、PAC学習方式でサンプルから評価を学習する必要がある場合、任意の信頼性を持つ$\varepsilon$-fractional core-stableという結果の効率的な計算を可能にする分布について、正および負の結果を与える。
関連論文リスト
- Learning the Expected Core of Strictly Convex Stochastic Cooperative
Games [18.746089166690144]
信用割当問題としても知られるリワード割当は、経済学、工学、機械学習において重要なトピックである。
本稿では,報酬関数を未知の分布を持つランダム変数として特徴付ける協調ゲームにおける安定なアロケーション学習問題を考察する。
論文 参考訳(メタデータ) (2024-02-10T23:49:49Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳(メタデータ) (2023-09-25T17:54:19Z) - Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
論文 参考訳(メタデータ) (2023-02-27T16:34:21Z) - Nystr\"om $M$-Hilbert-Schmidt Independence Criterion [0.0]
カーネルをユビキタスにする主な特徴は、 (i) 設計された領域の数、 (ii) カーネルに関連する関数クラスのヒルベルト構造、 (iii) 情報を失うことなく確率分布を表現する能力である。
我々は、Mge 2$のケースを処理し、その一貫性を証明し、その適用性を実証する代替のNystr"omベースのHSIC推定器を提案する。
論文 参考訳(メタデータ) (2023-02-20T11:51:58Z) - Robust Estimation under the Wasserstein Distance [28.792608997509376]
出力分布から外周質量が$varepsilon$を除去できる新しい外周ローバストワッサーシュタイン距離$mathsfW_pvarepsilon$を導入する。
我々は,$mathsfW_pvarepsilon$で最小距離推定を行うことで,最小限のロバスト推定リスクが得られることを示した。
論文 参考訳(メタデータ) (2023-02-02T17:20:25Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳(メタデータ) (2022-08-19T18:00:34Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳(メタデータ) (2021-10-24T04:03:00Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳(メタデータ) (2020-06-11T14:25:02Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。