Population generation for large-scale simulation

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.