論文の概要: Maximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-like Graphs

• arxiv url: http://arxiv.org/abs/2310.05139v1
• Date: Sun, 8 Oct 2023 12:18:08 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-12 12:15:36.953106
• Title: Maximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-like Graphs
• Title（参考訳）: 木状グラフ上のフラクショナル・ヘドニックゲームにおける実用的・平等的福祉の最大化
• Authors: Tesshu Hanaka, Airi Ikeyama, Hirotaka Ono
• Abstract要約: 本稿では,木状グラフ上の分数的ヘドニックゲームにおける福祉最大化分割を計算するための(擬)ポリノミカル時間アルゴリズムを提案する。 P$neq$NPという仮定の下では、擬ポリノミアル時間可解性が最良であることを示す硬度結果が提供される。
• 参考スコア（独自算出の注目度）: 2.348041867134616
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fractional hedonic games are coalition formation games where a player's utility is determined by the average value they assign to the members of their coalition. These games are a variation of graph hedonic games, which are a class of coalition formation games that can be succinctly represented. Due to their applicability in network clustering and their relationship to graph hedonic games, fractional hedonic games have been extensively studied from various perspectives. However, finding welfare-maximizing partitions in fractional hedonic games is a challenging task due to the nonlinearity of utilities. In fact, it has been proven to be NP-hard and can be solved in polynomial time only for a limited number of graph classes, such as trees. This paper presents (pseudo)polynomial-time algorithms to compute welfare-maximizing partitions in fractional hedonic games on tree-like graphs. We consider two types of social welfare measures: utilitarian and egalitarian. Tree-like graphs refer to graphs with bounded treewidth and block graphs. A hardness result is provided, demonstrating that the pseudopolynomial-time solvability is the best possible under the assumption P$\neq$NP.
• Abstract（参考訳）: フラクショナル・ヘドニック・ゲーム(英: Fractional Hedonic game)は、プレイヤーの効用が彼らの連合のメンバーに割り当てる平均値によって決定される連立ゲームである。 これらのゲームはグラフヘドニックゲーム(英語版)の変種であり、簡潔に表現できる連立形成ゲームの一類である。 ネットワーククラスタリングの適用性やグラフヘドニックゲームとの関係から、分数ヘドニックゲームは様々な観点から広く研究されてきた。 しかし、分数的ヘドニックゲームにおける福祉最大化パーティションの発見は、ユーティリティの非線形性のために難しい課題である。 実際、NPハードであることが証明されており、木のような限られた数のグラフクラスに対してのみ多項式時間で解ける。 本稿では,木様グラフ上の分数ヘドニックゲームにおける福祉最大化パーティションを計算するために,pseudo多項時間アルゴリズムを提案する。 我々は、実用主義と平等主義の2つの社会福祉対策を考える。 木のようなグラフは、有界木幅グラフとブロックグラフを持つグラフを指す。 P$\neq$NP という仮定の下では、擬ポリノミアル時間可解性が最良であることを示す硬度結果が提供される。

関連論文リスト

• Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
  グラフニューラルネットワークを用いてパリティゲームの勝利領域を決定するための不完全時間的アプローチを提案する。 これは、データセットの60%の勝利領域を正しく決定し、残りの領域で小さなエラーしか発生しない。
  論文  参考訳（メタデータ） (2022-10-18T15:10:25Z)
• CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning [65.1042892570989]
  自己教師付きグラフ類似性学習のためのコントラストグラフマッチングネットワーク(CGMN)を提案する。 我々は,効率的なノード表現学習のために,クロスビューインタラクションとクロスグラフインタラクションという2つの戦略を用いる。 我々はノード表現をグラフ類似性計算のためのプール演算によりグラフレベル表現に変換する。
  論文  参考訳（メタデータ） (2022-05-30T13:20:26Z)
• Arkhipov's theorem, graph minors, and linear system nonlocal games [0.0]
  本稿では,2色グラフの入射系を基礎とするグラフ入射ゲームの解群について検討する。 アルキポフの定理は、連結グラフのグラフ入射ゲームが完全量子戦略を持つことは、それが完全古典的戦略を持つか、あるいはグラフが非平面的であることを言う。 我々はアルキポフの定理を拡張し、連結な2色グラフのグラフ入射ゲームに対して、解群のすべての商閉性は禁じられたマイナーな性質を持つことを示した。
  論文  参考訳（メタデータ） (2022-05-10T03:21:38Z)
• Approximating Nash Equilibrium in Random Graphical Games [3.42658286826597]
  マルチエージェントゲームにおけるナッシュ均衡は、ゲーム理論とコンピュータ科学のインターフェイスにおける長年の課題である。 確率の高い辺密度のポリ(k, 1/epsilon, ln(N))$より大きいランダムグラフ上で、ポリマトリクスゲームのエプシロン近似ナッシュ平衡を計算するための準ポリリノミカル時間近似スキーム(QPTAS)を提供する。 同じランタイムで、エプシロン近似ナッシュ均衡を計算することができ、エプシロン近似はゲームのナッシュ均衡の最大社会福祉を達成できる。
  論文  参考訳（メタデータ） (2021-12-07T01:40:20Z)
• Learning Graphon Mean Field Games and Approximate Nash Equilibria [33.77849245250632]
  本稿では,弱い相互作用を持つグラノン平均場ゲームに対して,離散時間による新たな定式化を提案する。 理論的には、グラノン平均場解の広範かつ厳密な存在と近似特性を与える。 我々は,多くのエージェントを持つ非実現不可能な大密度グラフゲームにおいて,可塑性近似ナッシュ平衡を得ることに成功した。
  論文  参考訳（メタデータ） (2021-11-29T16:16:11Z)
• Edge but not Least: Cross-View Graph Pooling [76.71497833616024]
  本稿では,重要なグラフ構造情報を活用するために,クロスビューグラフプーリング(Co-Pooling)手法を提案する。 クロスビュー相互作用、エッジビュープーリング、ノードビュープーリングにより、相互にシームレスに強化され、より情報的なグラフレベルの表現が学習される。
  論文  参考訳（メタデータ） (2021-09-24T08:01:23Z)
• Factorizable Graph Convolutional Networks [90.59836684458905]
  本稿では,グラフに符号化された相互に絡み合った関係を明示的に解消する新しいグラフ畳み込みネットワーク(GCN)を提案する。 FactorGCNは単純なグラフを入力として取り、それをいくつかの分解グラフに分解する。 提案したFacterGCNは,合成および実世界のデータセットに対して質的かつ定量的に評価する。
  論文  参考訳（メタデータ） (2020-10-12T03:01:40Z)
• Grale: Designing Networks for Graph Learning [68.23038997141381]
  我々は,数十億のノードを持つグラフのグラフ設計問題に対処するために,スケーラブルなGraleを提案する。 グレールは、(潜在的に弱い)類似性の異なる測度を融合して、そのノード間の高いタスク固有のホモフィリーを示すグラフを作成する。 Googleでは、数千億のノードを持つデータセットや、数十兆の潜在的なエッジを含む、20以上の異なる産業環境にGraleをデプロイしています。
  論文  参考訳（メタデータ） (2020-07-23T13:25:36Z)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  グラフ構造オブジェクト間のグラフ類似性を計算するためのマルチレベルグラフマッチングネットワーク(MGMN)フレームワークを提案する。 標準ベンチマークデータセットの欠如を補うため、グラフグラフ分類とグラフグラフ回帰タスクの両方のためのデータセットセットを作成し、収集した。 総合的な実験により、MGMNはグラフグラフ分類とグラフグラフ回帰タスクの両方において、最先端のベースラインモデルより一貫して優れていることが示された。
  論文  参考訳（メタデータ） (2020-07-08T19:48:19Z)
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version [27.544219236164764]
  グラフ畳み込みネットワーク(GCN)はグラフ表現学習において広く使われている手法である。 サンプルグラフの埋め込みに基づいて異なるランダムグラフモデルを区別するGCNのパワーについて検討する。
  論文  参考訳（メタデータ） (2020-02-13T17:58:42Z)

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

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