論文の概要: $\varepsilon$-fractional Core Stability in Hedonic Games
- arxiv url: http://arxiv.org/abs/2311.11101v1
- Date: Sat, 18 Nov 2023 15:30:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-22 10:14:20.631464
- 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という結果の効率的な計算を可能にする分布について、正および負の結果を与える。
関連論文リスト
- Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees [1.2562458634975162]
既存の方法は典型的には$epsilon$-stochasticの固定点を見つけることを目的としている。
多くの実践的応用において、制約がほぼ確実に満たされることが重要であり、そのような$epsilon$-stochasticの定常点が望ましくない可能性がある。
論文 参考訳（メタデータ） (2024-09-16T00:26:42Z) - Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension [17.485243410774814]
教師付き学習の伝統的なモデルでは、学習者の目標は、あるクラスから最も適した概念の競争的($epsilon$以内)な仮説を出力することである。
学習者が最高の無知としか競合しないスムーズな分析フレームワークを導入する。
時間内に$k$-halfspacesの交点を前向きに学習する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-07-01T04:58:36Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Efficient Certificates of Anti-Concentration Beyond Gaussians [15.709968227246453]
この研究は、反濃縮のための新しい(そしておそらく最も自然な)定式化を提示する。
非ガウス分布の幅広いクラスを保った反集中の正方形証明を検証できる準多項式時間を与える。
提案手法は,意図された応用とは無関係に,正準2乗緩和の反集中と解析のための正準整数プログラムを構築する。
論文 参考訳（メタデータ） (2024-05-23T22:13:44Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Nystr\"om $M$-Hilbert-Schmidt Independence Criterion [0.0]
カーネルをユビキタスにする主な特徴は、 (i) 設計された領域の数、 (ii) カーネルに関連する関数クラスのヒルベルト構造、 (iii) 情報を失うことなく確率分布を表現する能力である。
我々は、Mge 2$のケースを処理し、その一貫性を証明し、その適用性を実証する代替のNystr"omベースのHSIC推定器を提案する。
論文 参考訳（メタデータ） (2023-02-20T11:51:58Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。