Single-Peaked Jump Schelling Games
- URL: http://arxiv.org/abs/2302.12107v1
- Date: Thu, 23 Feb 2023 15:46:26 GMT
- Title: Single-Peaked Jump Schelling Games
- Authors: Tobias Friedrich, Pascal Lenzner, Louise Molitor, Lars Seifert
- Abstract summary: We study Jump Schelling Games with agents having a single-peaked utility function.
We show that improving response cycles exist independently of the position of the peak in the utility function.
We also show that computing a beneficial state with high integration is NP-complete.
- Score: 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.
Related papers
- A Generalisation of Voter Model: Influential Nodes and Convergence Properties [5.4327243200369555]
We introduce and study a generalisation of the voter model.
We study the problem of selecting a set of seeds blue nodes to maximise the expected number of blue nodes after some rounds.
Our experiments on real-world and synthetic graph data demonstrate that the proposed algorithm outperforms other algorithms.
arXiv Detail & Related papers (2024-11-07T09:38:42Z) - Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
We consider the linear causal representation learning setting where we observe a linear mixing of $d$ unknown latent factors.
Recent work has shown that it is possible to recover the latent factors as well as the underlying structural causal model over them.
We provide a surprising identifiability result that it is indeed possible, under some very mild standard assumptions, to identify the set of shifted nodes.
arXiv Detail & Related papers (2024-10-31T15:56:50Z) - Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularization [12.612009339150504]
This work focuses on the entropy-regularized independent natural policy gradient (NPG) algorithm in multi-agent reinforcement learning.
We show that, under sufficient entropy regularization, the dynamics of this system converge at a linear rate to the quantal response equilibrium (QRE)
arXiv Detail & Related papers (2024-05-04T22:48:53Z) - Exploiting hidden structures in non-convex games for convergence to Nash
equilibrium [62.88214569402201]
A wide array of modern machine learning applications can be formulated as non-cooperative Nashlibria.
We provide explicit convergence guarantees for both deterministic and deterministic environments.
arXiv Detail & Related papers (2023-12-27T15:21:25Z) - Schelling Games with Continuous Types [3.5232085374661284]
50 years ago, Schelling proposed a landmark model that explains residential segregation in an elegant agent-based way.
We focus on segregation caused by non-categorical attributes, such as household income or position in a political left-right spectrum.
We study the existence and computation of equilibria and provide bounds on the Price of Anarchy and Stability.
arXiv Detail & Related papers (2023-05-11T14:13:14Z) - Finding mixed-strategy equilibria of continuous-action games without
gradients using randomized policy networks [83.28949556413717]
We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients.
We model players' strategies using artificial neural networks.
This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
arXiv Detail & Related papers (2022-11-29T05:16:41Z) - Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
We consider graphs as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius.
In a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius.
We develop methods to estimate the unknown sampling density in a self-supervised fashion.
arXiv Detail & Related papers (2022-10-15T08:01:08Z) - From Gradient Flow on Population Loss to Learning with Stochastic
Gradient Descent [50.4531316289086]
Gradient Descent (SGD) has been the method of choice for learning large-scale non-root models.
An overarching paper is providing general conditions SGD converges, assuming that GF on the population loss converges.
We provide a unified analysis for GD/SGD not only for classical settings like convex losses, but also for more complex problems including Retrieval Matrix sq-root.
arXiv Detail & Related papers (2022-10-13T03:55:04Z) - Gradient play in stochastic games: stationary points, convergence, and
sample complexity [6.97785632069611]
We study the performance of the gradient play algorithm for games (SGs)
We show that Nash equilibria (NEs) and first-order stationary policies are equivalent in this setting.
For a subclass of SGs called Markov potential games, we design a sample-based reinforcement learning algorithm.
arXiv Detail & Related papers (2021-06-01T03:03:45Z) - Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
It remains vastly open how to learn the Stackelberg equilibrium in general-sum games efficiently from samples.
This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium in two-player turn-based general-sum games.
arXiv Detail & Related papers (2021-02-23T05:11:07Z) - Latent Bandits Revisited [55.88616813182679]
A latent bandit problem is one in which the learning agent knows the arm reward distributions conditioned on an unknown discrete latent state.
We propose general algorithms for this setting, based on both upper confidence bounds (UCBs) and Thompson sampling.
We provide a unified theoretical analysis of our algorithms, which have lower regret than classic bandit policies when the number of latent states is smaller than actions.
arXiv Detail & Related papers (2020-06-15T19:24:02Z) - Analytic Properties of Trackable Weak Models [2.204918347869259]
We present several new results on the feasibility of inferring the hidden states in strongly-connected trackable weak models.
A weak model is said to be trackable if the worst case number of such hypotheses grows as entropy in the sequence length.
We show that the number of hypotheses in strongly-connected trackable models is bounded by a constant and give an expression for this constant.
arXiv Detail & Related papers (2020-01-08T15:54:56Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.