Stochastic Schelling
The stochastic Schelling model of agents moving between blocks, which segregates above beta = 2.
- Name:
stochastic_schelling - Field:
social/segregation - Formalism: agent-based model
- References: Grauwin et al. 2009; Jensen 2023
Factory
@register_model(
field='social/segregation',
tags=('segregation', 'agents', 'grid', 'stochastic'),
references=('Grauwin et al. 2009', 'Jensen 2023'),
defaults={'until': 50},
)
def stochastic_schelling(
width: int = 20,
height: int = 20,
*,
side: int = 5,
density: float = 0.5,
beta: float = 3.0,
altruism: float = 0.5,
slope: float = -4.0 / 3.0,
intercept: float = 1.0,
random_state: int | np.random.Generator | None = 0,
) -> System:
"""Return the stochastic Schelling model of agents moving between blocks, which segregates above `beta = 2`.
Args:
width:
The number of columns, a multiple of the block side.
height:
The number of rows, a multiple of the block side.
side:
The side of a square block in cells.
density:
The share of cells with an agent.
beta:
The inverse temperature of the moves.
altruism:
The weight of the change of the global utility.
slope:
The slope of the utility in the block density.
intercept:
The intercept of the utility.
random_state:
The seed or generator of the initial cells.
Returns:
system:
The model, with the group `dwellers`.
Examples:
>>> from skcomplex.models.social.segregation import stochastic_schelling
>>> stochastic_schelling(8, 8, side=4, random_state=0).elements[0].check().prepare().size_
32
"""
rng = np.random.default_rng(random_state)
size = int(width * height * density)
cells = rng.permutation(width * height)[:size]
locations = [(int(cell % width), int(cell // width)) for cell in cells]
blocks = [BlockMovesInteraction._block_of(location, side, width // side) for location in locations]
dwellers = GroupElement(
'dwellers',
element=DwellerElement,
size=size,
values={
'block': np.array(blocks, dtype=float),
'beta': beta,
'altruism': altruism,
'slope': slope,
'intercept': intercept,
},
location=locations,
)
moves = BlockMovesInteraction('moves', target='dwellers', width=width, height=height, side=side, phase=PHASE)
block = MapInteraction(
'block',
target='dwellers',
state='block',
function=moves.get_block,
schedule='member',
form='agent',
phase=PHASE,
)
return System(
elements=[dwellers],
interactions=[moves, block],
space=LatticeSpace((width, height), boundary='fixed', capacity=1),
time=DiscreteTime(schedule=PhasesScheduleSpec([PhaseSpec(PHASE, activation='visits', groups=('dwellers',))])),
)
Components
class DwellerElement(Element):
"""Agent of the stochastic Schelling model, whose utility `a * rho + b` depends on the density of its block.
Args:
label:
The label of the agent or group.
visual:
How the agent is drawn, or `None` for `default_visual_`.
block:
The index of the agent's block, which `stochastic_schelling` sets after every move.
beta:
The inverse temperature of the moves.
altruism:
The weight of the change of the global utility against the agent's own utility.
slope:
The slope `a` of the utility in the block density.
intercept:
The intercept `b` of the utility.
Examples:
>>> from skcomplex.core.elements import GroupElement
>>> from skcomplex.models.social.segregation import DwellerElement
>>> group = GroupElement('dwellers', element=DwellerElement, size=10, values={'beta': 3.0})
>>> group.label, group.element.__name__, group.size
('dwellers', 'DwellerElement', 10)
"""
def __init__(
self,
label: str,
visual: VisualSpec | None = None,
*,
block: Annotated[float, StateSpec(domain=NN)] = 0.0,
beta: Annotated[float, ParameterSpec(domain=RealSet.closed_open(0, oo))] = 3.0,
altruism: Annotated[float, ParameterSpec(domain=RealSet.closed_open(0, oo))] = 0.5,
slope: Annotated[float, ParameterSpec()] = -4.0 / 3.0,
intercept: Annotated[float, ParameterSpec()] = 1.0,
) -> None:
super().__init__(label, visual=visual)
self.block = block
self.beta = beta
self.altruism = altruism
self.slope = slope
self.intercept = intercept
@classmethod
def _get_view(cls) -> type[DwellerView]:
"""Return the class of the views of the agents, whose attributes are the states and parameters."""
return DwellerView
class BlockMovesInteraction(MovementInteraction):
"""Moves of the stochastic Schelling model, from an agent's cell to a random empty cell of another block.
A visited agent proposes to move to a random empty cell of the grid, and stays when the cell lies in its own block.
With block densities `rho_i` before and `rho_f'` after the move, the proposal is accepted with probability
`1 / (1 + exp(beta * dU))`, where `dU = (1 - altruism) * (u(rho_f') - u(rho_i)) + altruism * dU_global` and
`dU_global` is the change of `M * sum_q rho_q u(rho_q)` over the blocks of `M` cells. The densities are the counts
of the block states of the group. In `stochastic_schelling`, a phase of visits draws as many agents with
replacement as there are agents every step, and a `MapInteraction` sets the block of an agent after its move.
Args:
label:
The label of the interaction.
target:
The path of the group of dwellers.
width:
The number of columns of the grid.
height:
The number of rows of the grid.
side:
The side of a square block in cells, which divides the width and the height.
probability:
The probability that a visited agent proposes a move.
phase:
The phase of the step the moves run in, or `None` for the default phase.
Examples:
>>> from skcomplex.models.social.segregation import BlockMovesInteraction
>>> BlockMovesInteraction('moves', target='dwellers', side=4).check().schedule
'member'
"""
def __init__(
self,
label: str,
*,
target: Annotated[str, RoleSpec()],
width: int = 20,
height: int = 20,
side: int = 5,
probability: float = 1.0,
phase: str | None = None,
) -> None:
super().__init__(
label,
target=target,
step=self._propose,
probability=probability,
accept=self._accept,
schedule='member',
phase=phase,
)
self.width = width
self.height = height
self.side = side
def _propose(self, agent: AgentViewProtocol, model: ModelViewProtocol) -> object:
"""Return a random empty cell of another block than the agent's, or `None` to stay."""
if not isinstance(agent, DwellerView) or not isinstance(model, ModelView):
return None
cell = model.random_empty_cell()
return (
None if BlockMovesInteraction._block_of(cell, self.side, self.width // self.side) == agent.block else cell
)
def _accept(self, agent: AgentViewProtocol, cell: object, model: ModelViewProtocol) -> float:
"""Return the probability `1 / (1 + exp(beta * dU))` of a move of an agent to a cell of another block."""
if not isinstance(agent, DwellerView):
return 0.0
counts = model.composition('target', 'block')
origin, destination = agent.block, float(
BlockMovesInteraction._block_of(cell, self.side, self.width // self.side),
)
cells = self.side**2
before = np.array([counts.get(origin, 0), counts.get(destination, 0)]) / cells
after = before + np.array([-1, 1]) / cells
slope, intercept = agent.slope, agent.intercept
own = slope * (after[1] - before[0])
total = cells * float(
(after * (slope * after + intercept)).sum() - (before * (slope * before + intercept)).sum(),
)
change = (1 - agent.altruism) * own + agent.altruism * total
return float(1 / (1 + np.exp(np.clip(agent.beta * change, -50, 50))))
def get_block(self, agent: AgentViewProtocol, model: ModelViewProtocol) -> float:
"""Return the index of the block that holds the cell of an agent.
Args:
agent:
The dweller.
model:
The model view.
Returns:
block:
The index of the block.
"""
return float(BlockMovesInteraction._block_of(agent.location, self.side, self.width // self.side))
@staticmethod
def _block_of(location: object, side: int, columns: int) -> int:
"""Return the index of the block that holds a cell."""
column, row = (int(item) for item in np.ravel(np.asarray(location)))
return (row // side) * columns + column // side
class MapInteraction(Interaction):
"""Map of a state of discrete time, whose next value is a function, or the state plus it.
In the mode `'replace'` the next value of the state is `f`, and in the mode `'increment'` it is the state plus `f`.
Under the `'synchronous'` schedule every member of a bound group updates at once, from the states at the start of
the step. Under the `'sequential'` schedule the members update one after the other, in their order, and under the
`'random-sequential'` schedule in a new random order every step, each member reading the values the members before
it set. Under the `'member'` schedule of the agent form, every member updates in its own activation, together with
the rules of its element and the other member interactions, in the order the system lists them.
In the `'symbolic'` form, `function(namespace)` returns a symbolic expression, or a vector of them for a vector
state, where `namespace.target` holds the states and parameters of the target, `namespace.sources` the namespaces
of the sources, and `namespace.t` the time, and may hold draws such as `normal('noise')`. In the `'agent'` form,
the target is an agent group and `function(agent, model)` returns the value as a number, or as an array of the
shape of a vector state, so it can read the agent, its neighbours, and the history and storage of the model view.
Args:
label:
The label of the interaction, unique among the parts of its system.
target:
The path of the element or group whose state the map sets.
state:
The name of the state of the target.
function:
The function `f(namespace)` in the symbolic form, or `f(agent, model)` in the agent form.
sources:
The paths of the elements, or members of groups such as `cells[0]`, that the function reads.
mode:
`'replace'` or `'increment'`.
schedule:
`'synchronous'`, `'sequential'`, `'random-sequential'`, or `'member'` for the agent form.
form:
`'symbolic'` for update laws of the states of the target, or `'agent'` for a rule over an agent group.
phase:
The phase of the step the agent form runs in, or `None` for the default phase.
Raises:
ValidationError:
The mode, the schedule, or the form is unknown, the symbolic form has the schedule `'member'`, the
function is not callable, or the agent form returns a value that does not match the state, raised by
`run` of the simulation.
Examples:
>>> from skcomplex.core.elements import Element
>>> from skcomplex.core.interactions import MapInteraction
>>> from skcomplex.core.spaces import DiscreteTime
>>> from skcomplex.core.system import System
>>> from skcomplex.engine.runtime import Simulation
>>> from skcomplex.specs import StateSpec
>>> from typing import Annotated, SupportsFloat
>>> class ValueElement(Element):
... def __init__(self, label, x: Annotated[float, StateSpec()] = 0.5):
... super().__init__(label)
... self.x = x
>>> logistic = MapInteraction(
... 'map', target='value', state='x', function=lambda s: 3 * s.target.x * (1 - s.target.x)
... )
>>> system = System(elements=[ValueElement('value')], interactions=[logistic], time=DiscreteTime())
>>> Simulation(system).check().prepare().run(until=2).trajectory_.values('value.x').tolist()
[0.5, 0.75, 0.5625]
>>> agents = MapInteraction('map', target='walkers', state='x', function=lambda a, m: a.x + 1, form='agent')
>>> type(agents.check().prepare().run(SimpleNamespace()).laws_[0]).__name__
'RuleLaw'
>>> from skcomplex.core.elements import GroupElement
>>> class WeightsElement(Element):
... def __init__(self, label, visual=None, *, w: Annotated[object, StateSpec(vector=True)] = 0.0):
... super().__init__(label, visual=visual)
... self.w = w
>>> group = GroupElement('weights', element=WeightsElement, size=1, values={'w': [1.0, 2.0]})
>>> doubling = MapInteraction(
... 'double', target='weights', state='w', function=lambda a, m: [2 * x for x in a.w], form='agent'
... )
>>> trajectory = Simulation(System(elements=[group], interactions=[doubling])).check().prepare().run(until=2)
>>> trajectory.trajectory_.agents('weights', 2).values['w'].tolist()
[[4.0, 8.0]]
"""
def __init__(
self,
label: str,
*,
target: Annotated[str, RoleSpec()],
state: str,
function: Callable[..., object],
sources: Annotated[Sequence[str], RoleSpec(variadic=True)] = (),
mode: str = 'replace',
schedule: str = 'synchronous',
form: str = 'symbolic',
phase: str | None = None,
) -> None:
super().__init__(label)
self.target = target
self.state = state
self.function = function
self.sources = sources
self.mode = mode
self.schedule = schedule
self.form = form
self.phase = phase
def _check(self) -> None:
"""Raise an error for an unknown mode, schedule, or form, or a function that cannot be called.
Raises:
ValidationError:
The mode, the schedule, or the form is unknown, the symbolic form has the schedule `'member'`, or the
function is not callable.
"""
super()._check()
self._check_variant('mode', self.mode, MODES, (BaseSpec,))
for name, value, variants in (
('schedule', self.schedule, SCHEDULES),
('form', self.form, FORMS),
):
if value not in variants:
error_msg = f'The {name} of map {self.label!r} is {value!r}. Use one of {", ".join(variants)}.'
raise ValidationError(error_msg)
if self.schedule == 'member' and self.form != 'agent':
error_msg = (
f'The map {self.label!r} updates every member in its activation, which only the agent form does.'
)
raise ValidationError(error_msg)
if not callable(self.function):
error_msg = f'The function of map {self.label!r} must be callable, but it is {self.function!r}.'
raise ValidationError(error_msg)
def _apply_mode(self, current: Value, value: Value) -> Value:
"""Return the next value of a state from its current value and the value of the function, by the mode."""
if self.mode == 'increment':
return current + value
if self.mode == 'replace':
return value
raise self._get_variant_error(self.mode, 'mode', '_apply_mode')
def _get_vector(self, agent: AgentViewProtocol, model: ModelViewProtocol) -> Value:
"""Return the next value of a vector state of an agent."""
current = np.asarray(getattr(agent, self.state), dtype=np.float64)
value = np.asarray(self.function(agent, model), dtype=np.float64)
if value.shape != current.shape:
error_msg = (
f'The function of map {self.label!r} returns the shape {value.shape} for the state {self.state!r} of '
f'the shape {current.shape}. Return an array of the shape of the state.'
)
raise ValidationError(error_msg)
return self._apply_mode(current, value)
def _get_value(self, agent: AgentViewProtocol, model: ModelViewProtocol) -> Value:
"""Return the next value of the state of an agent, a number or the array of a vector state."""
if np.ndim(getattr(agent, self.state)) > 0:
return self._get_vector(agent, model)
found = self.function(agent, model)
if not isinstance(found, SupportsFloat):
error_msg = f'The function of map {self.label!r} returns {found!r} for an agent. Return a number.'
raise ValidationError(error_msg)
value = float(found)
return self._apply_mode(float(getattr(agent, self.state)), value)
def _set_value(self, agent: AgentViewProtocol, value: Value) -> None:
"""Set the state of an agent to its next value."""
setattr(agent, self.state, value)
def _update_member(self, agent: AgentViewProtocol, model: ModelViewProtocol) -> None:
"""Set the state of one member to its next value."""
if agent.alive:
self._set_value(agent, self._get_value(agent, model))
def update(self, model: ModelViewProtocol) -> None:
"""Set the state of every agent of the target to its next value, by the schedule.
Args:
model:
The model view of the interaction.
"""
self._update_agents(model, self.schedule, self._get_value, self._set_value)
def _get_order(self) -> object:
"""Return the order of the members of the symbolic form: none, their own order, or a uniform draw."""
if self.schedule == 'synchronous':
return None
if self.schedule == 'sequential':
return SR(0)
return uniform(re.sub(r'\W', '_', f'order_{self.label}'))
def _get_laws(self, namespace: SimpleNamespace) -> list[BasePart]:
"""Return the update of the state to its next value, or the rule of the agent form.
Args:
namespace:
The namespace of the symbols the laws can use, with `namespace.target` and `namespace.sources`.
Returns:
laws:
The update law of the state, or the rule that runs the map of the agents.
"""
if self.form == 'agent' and self.schedule == 'member':
return [RuleLaw(self._update_member, phase=self.phase, members=self._get_role('target'))]
if self.form == 'agent':
return [RuleLaw(self.update, phase=self.phase)]
value = getattr(self._get_member(namespace, 'target'), self.state)
mapped = cast(Value, self.function(namespace))
next_value = self._apply_mode(value, mapped)
return [UpdateLaw(value, next_value, increment=self.mode == 'increment', order=self._get_order())]