Monday, September 27, 2010

Your Ways Are Numbered

Have been thinking lately about simulating how cultural values change in a population.1

The general approach I was considering was an agent-based model where each agent's "values" are represented by a set of n real numbers in [0,1]: basically each dimension is like one of those survey questions that's a statement like "everyone should have access to clean drinking water," with answers ranging from "strongly disagree" to "strongly agree," and "neutral" in the middle (0.5).

And when two agents had a lot in common with one another values-wise (i.e., were nearby in n-dimensional space), then they would be more likely to move closer together. So starting with a randomly generated population, you'd see different subgroups start to coalesce into one or more distinct cultures with shared values (and eventually reducing to a single consensus culture if the simulation ran long enough).

Which as I poked around looked a lot like what was done in this 1997 paper (PDF) by Robert Axelrod (nullus), The Dissemination (nullus) of Culture. He puts his agents on a grid and only lets them potentially interact with grid neighbors. It's neat.

Here's a Python implementation, with visualization in PyGame (I inverted Axelrod's color coding so more similar sites are connected by darker lines, which strikes me as more intuitive):

import random

import pygame
from pygame.locals import *

class Simulation:

    WIDTH = 640
    HEIGHT = 480

    LINE = 4

    DRAW_FRAMES = 1000

    def __init__(self, dimensions):
        self.dimensions = dimensions
        self.grid_size = min(self.WIDTH/(self.dimensions[0] + 1),
                             self.HEIGHT/(self.dimensions[1] + 1))
        self.bg_rect = pygame.Rect(max(0, (self.WIDTH - (self.dimensions[0] + 1) * self.grid_size) / 2),
                                   max(0, (self.HEIGHT - (self.dimensions[1] + 1) * self.grid_size) / 2),
                                   (self.dimensions[0] + 1) * self.grid_size,
                                   (self.dimensions[1] + 1) * self.grid_size)

        self.sites = [[[random.randint(1,10) for i in range(5)]
                       for y in range(self.dimensions[1])]
                      for x in range(self.dimensions[0])]

    def background(self, screen):
        screen.fill((255,255,255), self.bg_rect)

    def similarity(self, p1, p2):
        return sum(c1 == c2 for c1, c2 in zip(p1, p2))/float(len(p1))

    def color(self, p1, p2):
        gray = 255 - int(self.similarity(p1, p2) * 255)
        return (gray, gray, gray)

    def lines(self, screen):
        for x in range(self.dimensions[0]):
            for y in range(self.dimensions[1]):
                start = (self.bg_rect.left + (x+1) * self.grid_size,
                         self.bg_rect.top + (y+1) * self.grid_size)
                if x < self.dimensions[0] - 1:
                    end = (start[0] + self.grid_size, start[1])
                    color = self.color(self.sites[x][y], self.sites[x+1][y])
                    pygame.draw.line(screen, color, start, end, self.LINE)
                if y < self.dimensions[1] - 1:
                    end = (start[0], start[1] + self.grid_size)
                    color = self.color(self.sites[x][y], self.sites[x][y+1])
                    pygame.draw.line(screen, color, start, end, self.LINE)

    def random_site(self):
        return (random.randint(0, len(self.sites)-1),
                random.randint(0, len(self.sites[0])-1))

    def random_neighbor(self, site):
        x,y = site
        neighbors = []
        if x > 0:
            neighbors.append((x-1,y))
        if x < len(self.sites)-1:
            neighbors.append((x+1,y))
        if y > 0:
            neighbors.append((x,y-1))
        if y < len(self.sites[0])-1:
            neighbors.append((x,y+1))
        return random.sample(neighbors, 1)[0]

    def interact(self, active, neighb):
        different = [i for i in range(len(active))
                     if active[i] != neighb[i]]
        if len(different) > 0:
            i = random.sample(different, 1)[0]
            active[i] = neighb[i]

    def try_event(self):
        active = self.random_site()
        neighb = self.random_neighbor(active)
        active_site = self.sites[active[0]][active[1]]
        neighb_site = self.sites[neighb[0]][neighb[1]]
        if random.random() < self.similarity(active_site, neighb_site):
            self.interact(active_site, neighb_site)
    
    def run(self):
        pygame.init()

        screen = pygame.display.set_mode((self.WIDTH,self.HEIGHT), HWSURFACE)
        pygame.display.set_caption('Sites')

        done = False
        n = 0
        while not done:
            for event in pygame.event.get():
                if event.type == QUIT:
                    done = True
                elif event.type == KEYDOWN:
                    if event.key == K_ESCAPE:
                        done = True

            self.try_event()
            n += 1
            if n > self.DRAW_FRAMES:
                
                self.background(screen)
                self.lines(screen)

                pygame.display.flip()
                
                n = 0

if __name__ == '__main__':
    Simulation((10,10)).run()

1 For extremely nerdy reasons.

5 comments:

dr said...

No modeling of contrarians or trendsetters? I think the "final static picture" proves that this is necessary because that doesn't happen in real life (or maybe we are still only a few DRAW_FRAMES into the simulation--I've got a 100x100 going and it hasn't settled down after several minutes).

Also, I see your Dwarf Fortress and raise you a Minecraft.

tps12 said...

If we just let our world run long enough then eventually everyone will agree that evolution is real, Han shot first, *BSD is dying, &c.

But yeah, just as a first step nothing in there says anything about psychology. It would be cool to have values that reinforce or interfere with one another or feed back into the interaction calculation itself (like an "individualism vs. conformity" dimension).

dr said...

Oh yeah, I didn't even consider self-reference/feedback.

Also, adding and removing dimensions (e.g. "can set time on VCR" or "rides a horse"). If this model's behavior depends on dimension, that could be key.

Also also, I think I liked your original non-gridded idea better. But the visualization is a little harder.

tps12 said...

Yeah, the grid should be replaced by a general undirected graph with edges weighted to represent the opportunity of connected agents to interact (so an agent might be more likely to be influenced by a coworker than a neighbor).

Or actually, each agent should have its own set of edge weights based on certain dimensions (a very community-minded agent could be more easily swayed by a neighbor).

dr said...

Defining edge weights by dimension values is pretty brill. My "neighbors" value is close to 0 but my "internet" value is .98.

Also, we could harvest energy from these simulated humans, but we have to watch for any that escape and discover the real world. Particularly the prophesied One.