'Large' Games and their Multiple Applications

by Andrzej Wieczorek

A recent project at the Institute of Computer Science of the Polish Academy of Sciences looked at games and models with infinitely many participants, constructed in a manner allowing for practical applications.

'Large' games include finitely many types of infinite populations whose members have the same characteristics (strategy sets and preferences over possible outcomes), and finitely many large players ('atoms'). The reported studies concern:

• theoretical foundations, including a definition of a 'large' game and results on the existence, properties and procedures (static or dynamic) for finding the equilibria of a game
• applications of the former to models of labour markets, household economies, the global economy, spatial allocation of species, general elections and road traffic, and
• computer packages to search for equilibria in selected models.

Mathematical game theory deals with the modelling of various schemes, which describe the actions - and their consequences - of several decision subjects (eg single persons, teams and societies, but also animals, their populations or even automatons and specialised computer programs). Game theory analyses such schemes, with special attention paid to situations arising after a choice by the respective subjects regarding their actions. Some of these situations are called equilibria; in these situations there is no decision subject who, knowing that the situation has taken place, is able to find out that a different previous action would have made him better off.

The decision subjects are usually called players (or sometimes coalitions). Players choose their strategies, and a choice of strategies by all players leads to a concrete situation; various situations are evaluated, in a (possibly) different manner, by the players. Mathematically, such evaluations are done by means of preference relations or utility functions.

Classical game theory, the roots of which are usually associated with the names of John von Neumann and John Nash, has dealt with games with finitely many players, as is usually the case in real-world situations.

However, the number of decision subjects in the real world is so large that in many extended decision schemes it does not make much sense to take into account the precise characteristics of each subject involved; rather it makes sense to introduce a procedure of aggregation (of the description of the subjects' characteristics) in a manner allowing for efficient analysis, eg by means of appropriately constructed computer programs. Mathematical ways of constructing such aggregation (especially when the influence of individual actions on the overall outcome is negligible) are based upon the assumption that the number of decision subjects is infinite and one can observe only a distribution of their strategy choice, rather than any actual choice made by an individual.

The first mathematical models of decision schemes with infinitely many participants were created in the 1960s. These models tended to be fairly general, and knowledge of the characteristics of all participants was generally assumed. Their advantage, implied by generality, is the possibility of deeper understanding of the case being modelled, usually economic and social phenomena; however, due to the amount of data necessary (including the characteristics of each individual), it is difficult to apply such models directly to specific 'everyday' problems.

Various games and models with infinitely many participants, constructed in a manner allowing for practical applications, are being studied at the Institute of Computer Science of the Polish Academy of Sciences. This work falls within the scope of research projects sponsored by the Polish Council for Scientific Research (KBN). Games and models of this kind, usually referred to as 'large', take into account the activity of a number of types (obviously finite in real applications) of infinite populations, and a number of 'large' players (also called 'atoms'), whose decisions have a significant influence on the final outcome of a game. It is also assumed that all players in a given population have the same characteristics and therefore the same strategy sets and preferences over the set of final outcomes, also depending on their individual choice of strategy.

The theoretical part of the research included the construction of a 'large' game, formulation of the concepts of equilibria and other solutions (which in some sense are optimal), a study of conditions implying the existence of equilibria and their properties, and algorithms for finding such optimal solutions.

In choosing practical applications for study, we looked at those for which the occurrence of a large number of decision makers is typical (in some cases 'atoms' are also present). These included:

• labour markets
• household economies
• the global economy
• spatial allocation of species
• general elections
• transportation networks.

For instance, in the model of spatial allocation of species, two special cases have been studied in detail - a single population model and a two-population 'predator-prey' model. Members of each population choose their habitation (which is a point in a given set on the plane). Individual preferences depend on the distance of the chosen habitation from an 'ideal' reference point and also on the parameters of distribution of one's own (and the other) population. The obtained theorems guarantee the existence of equilibria and give a characterisation of the set of all equilibria. Under some assumptions, equilibria are given by distributions on circles (one or two, depending on the number of populations) with given radii and centres in the 'ideal' point; the mean of those distributions being simply the 'ideal' point.

Computer packages have been constructed to find equilibria in the models of household economies and the spatial allocation of species. Finally, it is worth noting that attacking and efficiently solving the problems of game theory with large databases (as well as their applications) is closely related to the increased power of contemporary computers and to the creation of new computation techniques.

Please contact:
Andrzej Wieczorek, Institute of Computer Science, Polish Academy of Sciences
E-mail: Andrzej.Wieczorekipipan.waw.pl