論文の概要: Single-Peaked Jump Schelling Games
- arxiv url: http://arxiv.org/abs/2302.12107v1
- Date: Thu, 23 Feb 2023 15:46:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-24 14:39:12.692023
- Title: Single-Peaked Jump Schelling Games
- Title（参考訳）: シングルピークジャンプスケジューリングゲーム
- Authors: Tobias Friedrich, Pascal Lenzner, Louise Molitor, Lars Seifert
- Abstract要約: 本研究では,単一話者のユーティリティ機能を持つエージェントを用いたジャンプスケジューリングゲームについて検討する。
実用機能におけるピーク位置とは無関係に応答サイクルの改善が可能であることを示す。
また、高積分の有益な状態の計算がNP完全であることも示している。
- 参考スコア（独自算出の注目度）: 12.940151684804958
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Schelling games model the wide-spread phenomenon of residential segregation
in metropolitan areas from a game-theoretic point of view. In these games
agents of different types each strategically select a node on a given graph
that models the residential area to maximize their individual utility. The
latter solely depends on the types of the agents on neighboring nodes and it
has been a standard assumption to consider utility functions that are monotone
in the number of same-type neighbors. This simplifying assumption has recently
been challenged since sociological poll results suggest that real-world agents
actually favor diverse neighborhoods.
We contribute to the recent endeavor of investigating residential segregation
models with realistic agent behavior by studying Jump Schelling Games with
agents having a single-peaked utility function. In such games, there are empty
nodes in the graph and agents can strategically jump to such nodes to improve
their utility. We investigate the existence of equilibria and show that they
exist under specific conditions. Contrasting this, we prove that even on simple
topologies like paths or rings such stable states are not guaranteed to exist.
Regarding the game dynamics, we show that improving response cycles exist
independently of the position of the peak in the utility function. Moreover, we
show high almost tight bounds on the Price of Anarchy and the Price of
Stability with respect to the recently proposed degree of integration, which
counts the number of agents with a diverse neighborhood and which serves as a
proxy for measuring the segregation strength. Last but not least, we show that
computing a beneficial state with high integration is NP-complete and, as a
novel conceptual contribution, we also show that it is NP-hard to decide if an
equilibrium state can be found via improving response dynamics starting from a
given initial state.
- Abstract（参考訳）: 計画ゲームは、ゲーム理論の観点から、大都市圏における住宅分離の広帯域現象をモデル化する。
これらのゲームでは、異なるタイプのエージェントがそれぞれのグラフ上のノードを戦略的に選択し、それぞれのユーティリティを最大化するために住宅エリアをモデル化する。
後者は隣接ノード上のエージェントのタイプのみに依存しており、同じタイプの隣接ノードの数で単調であるユーティリティ関数を考えるのが標準的な仮定である。
この単純な仮定は、社会学的調査の結果、実世界のエージェントが実際には多様な近隣を好んでいると示唆されて以来、近年疑問視されている。
本研究は,単発効用関数を有するエージェントによるジャンプシェリングゲームの研究を通じて,現実的なエージェント行動を伴う住宅分離モデルの検討の最近の取り組みに寄与する。
このようなゲームでは、グラフには空のノードがあり、エージェントはそのようなノードに戦略的にジャンプしてそれらのユーティリティを改善することができる。
平衡の存在を調査し, 特定の条件下での存在を示す。
これとは対照的に、パスや環のような単純な位相でさえ、そのような安定状態が存在することは保証されない。
ゲームダイナミクスについては,応答サイクルの改善が実用機能におけるピーク位置とは独立に存在することを示す。
さらに、最近提案された統合の度合いに関して、アナーキーの価格と安定の価格にほぼ密接な境界が示され、多様な地区を持つエージェントの数を数え、分離強度を測るプロキシとして機能する。
最後に、高積分による有益状態の計算がNP完全であることを示し、新しい概念的寄与として、与えられた初期状態から始まる応答ダイナミクスの改善によって平衡状態が発見できるかどうかをNP完全であることが示される。
関連論文リスト
- A Generalisation of Voter Model: Influential Nodes and Convergence Properties [5.4327243200369555]
我々は有権者モデルの一般化を紹介し,研究する。
そこで本研究では,いくつかのラウンド後に期待されるブルーノード数を最大化するために,種子のブルーノードを選択する問題について検討する。
実世界のグラフデータおよび合成グラフデータに関する実験により,提案アルゴリズムが他のアルゴリズムより優れていることを示す。
論文 参考訳（メタデータ） (2024-11-07T09:38:42Z) - Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularization [12.612009339150504]
本研究は,マルチエージェント強化学習におけるエントロピー規則化独立自然政策勾配(NPG)アルゴリズムに焦点を当てる。
十分なエントロピー正則化の下では、この系の力学は線形速度で量子応答平衡(QRE)に収束することを示す。
論文 参考訳（メタデータ） (2024-05-04T22:48:53Z) - Exploiting hidden structures in non-convex games for convergence to Nash
equilibrium [62.88214569402201]
現代の機械学習アプリケーションは、非協調的なナッシュリリアとして定式化することができる。
決定論的環境と決定論的環境の両方に明確な収束保証を提供する。
論文 参考訳（メタデータ） (2023-12-27T15:21:25Z) - Schelling Games with Continuous Types [3.5232085374661284]
50年前、Schelling氏はエレガントなエージェントベースの方法で住宅分離を説明するランドマークモデルを提案した。
我々は、政治的左翼スペクトルにおける家計収入や地位などの非分類的属性による差別に焦点を当てる。
我々は平衡の存在と計算について研究し、アナーキーと安定性の価格に関するバウンダリを提供する。
論文 参考訳（メタデータ） (2023-05-11T14:13:14Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。
ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。
本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
論文 参考訳（メタデータ） (2022-11-29T05:16:41Z) - Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
グラフを幾何学グラフとみなす: ノードは基礎となる計量空間からランダムにサンプリングされ、その距離が指定された近傍半径以下であれば任意のノードが接続される。
ソーシャルネットワークでは、コミュニティは密集したサンプル領域としてモデル化でき、ハブはより大きな近傍半径を持つノードとしてモデル化できる。
我々は,未知のサンプリング密度を自己監督的に推定する手法を開発した。
論文 参考訳（メタデータ） (2022-10-15T08:01:08Z) - From Gradient Flow on Population Loss to Learning with Stochastic
Gradient Descent [50.4531316289086]
SGD(Gradient Descent)は、大規模非ルートモデルの学習方法である。
集団損失のGFが収束すると仮定して、総合的な条件 SGD が収束する。
我々は、凸損失のような古典的な設定だけでなく、Retrieval Matrix sq-rootのようなより複雑な問題に対してもGD/SGDを統一的に解析する。
論文 参考訳（メタデータ） (2022-10-13T03:55:04Z) - Gradient play in stochastic games: stationary points, convergence, and
sample complexity [6.97785632069611]
ゲーム用グラデーションプレイアルゴリズム(SG)の性能について検討する。
この設定では、ナッシュ均衡(NE)と1次定常ポリシーが等価であることを示す。
マルコフポテンシャルゲームと呼ばれるSGのサブクラスに対して、サンプルベース強化学習アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-01T03:03:45Z) - Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。
本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
論文 参考訳（メタデータ） (2021-02-23T05:11:07Z) - Latent Bandits Revisited [55.88616813182679]
潜伏盗賊問題は、学習エージェントが未知の離散潜伏状態に条件付けられた腕の報酬分布を知知する問題である。
本稿では, 上位信頼境界(UCB)とトンプソンサンプリング(Thompson sample)の両方に基づいて, この設定のための一般的なアルゴリズムを提案する。
我々はアルゴリズムの統一的な理論的解析を行い、遅延状態の数がアクションよりも小さい場合、古典的なバンディットポリシーよりも後悔度が低い。
論文 参考訳（メタデータ） (2020-06-15T19:24:02Z) - Analytic Properties of Trackable Weak Models [2.204918347869259]
強連結トラックブル弱モデルにおける隠れ状態の推測の可能性に関する新しい結果を示す。
弱いモデルは、そのような仮説の最悪のケース数が列長のエントロピーとして増加すると追跡可能であると言われる。
強連結な追跡可能モデルにおける仮説の数は定数で有界であることを示し、この定数に対する表現を与える。
論文 参考訳（メタデータ） (2020-01-08T15:54:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。