Proceedings Article | 19 May 2005
KEYWORDS: Algorithm development, Computer simulations, Oxygen, Analytical research, Genetics, Social network analysis, Algorithms, Tumor growth modeling, Defense and security
Computer simulation is used to research phenomena ranging from the structure of the space-time continuum
to population genetics and future combat.1-3 Multi-agent simulations in particular are now commonplace in
many fields.4, 5 By modeling populations whose complex behavior emerges from individual interactions, these
simulations help to answer questions about effects where closed form solutions are difficult to solve or impossible
to derive.6 To be useful, simulations must accurately model the relevant aspects of the underlying domain.
In multi-agent simulation, this means that the modeling must include both the agents and their relationships.
Typically, each agent can be modeled as a set of attributes drawn from various distributions (e.g., height, morale,
intelligence and so forth). Though these can interact - for example, agent height is related to agent weight - they
are usually independent. Modeling relations between agents, on the other hand, adds a new layer of complexity,
and tools from graph theory and social network analysis are finding increasing application.7, 8 Recognizing the
role and proper use of these techniques, however, remains the subject of ongoing research.
We recently encountered these complexities while building large scale social simulations.9-11 One of these,
the Hats Simulator, is designed to be a lightweight proxy for intelligence analysis problems. Hats models a
“society in a box” consisting of many simple agents, called hats. Hats gets its name from the classic spaghetti
western, in which the heroes and villains are known by the color of the hats they wear. The Hats society also has
its heroes and villains, but the challenge is to identify which color hat they should be wearing based on how they
behave. There are three types of hats: benign hats, known terrorists, and covert terrorists. Covert terrorists look
just like benign hats but act like terrorists. Population structure can make covert hat identification significantly
more difficult. Investigators using the Hats Simulator must be able to control population parameters, and
population generation must be fast enough to support studies that vary these parameters. This paper reports
our experiences developing algorithms to generate populations whose structure is dependent on experimenter
controlled parameters.
In the next section, we outline the general problem of population generation and the details of building
populations for the Hats Simulator. This is followed by a brief description of our initial, brute force algorithm
(section 3). It was sufficient for small populations, but scaled horribly. We realized that the Law of Large
Numbers would allow randomized methods to generate large populations that satisfied our constraints within
acceptable bounds (section 5). It was while developing this algorithm that we discovered the connection between
our population generation problem and recent results from the theory of random bipartite graphs (section 4).
Finally, section 6 examines the properties and performance of our randomized algorithm. Though we will describe
our results in terms of the Hats Simulator, these methods apply to any modeling situation in which populations
of agents share multiple, overlapping structures, each of which is independent from the others. Our hope is that
our experience will benefit others facing the task of generating large populations that require similar overlapping
group structure.
