The Trade Network Game Laboratory:
Demonstration Software
Combining Game Theory with Matching Theory
TNGLab Overview
As carefully explained in
Ref. [1],
below, the Trade Network Game (TNG) is a framework
for studying the endogenous formation and evolution of trade networks among strategically interacting
traders (Buyers, Sellers, and Dealers) operating under variously specified market protocols.
The TNG blends and extends standard matching theory and sequential game theory in that each trader
must jointly determine over time both whom to seek trades with (partner selection) and how to behave
in any trade interactions that take place (strategy selection).
More precisely, in the TNG, successive generations of resource-constrained traders choose and refuse
trade partners on the basis of continually updated expected utility.
This partner-seeking process requires the traders to talk back and forth with
each other at event-triggered times.
Once trade partners are determined, the partners engage in bilateral trade interactions modeled as
2-person games. The traders use genetic algorithm learning to evolve
their trading strategies over time based on outcomes from their past trade interactions.
The TNG permits the resulting trade outcomes to be
studied at four different levels: trader attributes (endogenous evolution of
personality types); trade network formation (who is trading with whom, and
with what regularity); expressed trade behavior (cooperative,
predacious,...); and individual and social welfare measures (market
efficiency, market power, individual utility levels,...).
Each TNG trader in a bilateral trade can either play C (cooperate) or D (defect). The TNG
GUI Settings Screen permits the user to specify arbitrary payoffs for the four situations a trader
could find himself in as a result of a bilateral trade: CC (Both Cooperate); DD (Both Defect); DC (Temptation, i.e. the trader defects against a cooperating partner); and CD (Sucker, i.e. the trader is cooperating but his partner defects against him).
Thus, the user can specify any two-player game to represent bilateral trade (stage-game play) for the TNG.
These two-player games include Prisoner's Dilemma, Dead Lock, Chicken, Stag-Hunt, and Battle of the Sexes. For definitions and analysis of these two-player games, see
Ref. [2],
below.
At the start of each TNG experiment, each TNG trader is assigned a totally random
strategy for engaging in iterated bilateral trades an indefinite number of times.
The trader types then separately evolve their trade strategies over time using genetic algorithm
(GA) learning. In particular, Buyer strategies are updated
via a GA applied to the population of Buyers, Seller strategies are updated via a second GA
applied to the population of Sellers, and Dealer strategies are updated via a third GA applied to the
population of Dealers.
The TNG is divided into a total of GMax generations. Each generation, in turn, is divided into a total of IMax trade cycles. During each trade cycle, the TNG traders engage in three activities: matching (determination of trade partners); bilateral trades (game interactions); and updating (revision of expected utility assessments associated with potential trade partners).
At the end of each generation (i.e. at the end of each trade loop consisting of IMax trade cycles), the TNG traders use GA learning to update their trade strategies based on the net payoffs they accrued during this generation. The Total Net Payoff (TNP) earned by a trader during any generation G includes the sum of all of his trade payoffs (positive and negative) plus the sum of all of his (non-positive) refusal payoffs. A trader suffers a refusal payoff R any time one of his trade offers is refused by another trader; the non-positive level of the refusal payoff R is set by the user in the TNGLab GUI Settings Screen. The utility (or fitness) of each TNG trader in any generation G is measured by his average payoff per trade cycle, i.e., by TNP/IMax.
The TNG has been implemented in C++ with the support of
SimBioSys, a C++ class framework for general evolutionary simulations.
TNG/SimBioSys has further been incorporated into a modular extensible
computational laboratory, referred to as the TNGLab, which is targeted for
the Microsoft Windows desktop. The TNGLab has an easily operated GUI
that can be used to run TNG experiments for research and
teaching purposes. A description of all of the parameters whose values can be set by users via the TNGLab GUI Settings Screen is given in
Ref. [3],
below.
Trade network formation, trader behaviors, and trader welfare outcomes for each TNGLab run can be visualized during the run by means of run-time network animations and run-time chart and data table displays available through Results, Chart, and Animation Screens at the TNGLab GUI.
The run-time network animations make use of an underlying spring/coil physics to visualize trader interactions over time.
Roughly summarized, non-transient interactions between a pair of traders A and B are visualized by means of a line connecting A and B. Dashed lines denote intermittent interactions, and solid lines denote persistent (continual) interactions. Moreover, the length of the line connecting A and B at any given time is inversely related to the frequency of their past transactions. These simple rules permit beautiful run-time visualizations of intricate trade network formations.
Detailed outputs for each TNGLab run are also
automatically recorded and saved in a file called tng.out.
This file should be in the TNGLab directory automatically created during
installation, with default location under "Program Files."
One thing that users have to be careful about is that the output file tng.out is overwritten with each new run. Consequently, in order to save the output in tng.out from a particular run, the contents of tng.out
must be copied over into a differently named file.
The remaining sections of this TNGLab Home Page provide: (a) annotated pointers to
sites where the TNGLab (with automatic installation program) and TNG/SimBioSys (source code)
can be obtained as open-source freeware under the terms of an artistic license agreement; (b) annotated pointers to TNGLab Manuals and Tutorials; and (c) annotated pointers to research that has been conducted
using the TNGLab and TNG/SimBioSys.
Overview References:
[1] David McFadzean, Deron Stewart, and Leigh Tesfatsion, "A
Computational Laboratory for Evolutionary Trade Networks"
(pdf,508KB),
IEEE Transactions on Evolutionary Computation, Volume 5, Number 5, October
2001.
- Note: This article constitutes the main manual for the TNGLab.
[2] Leigh Tesfatsion, "Game Theory: Basic Concepts and Terminology"
(pdf,317KB)
[3] Leigh Tesfatsion, "TNGLab Parameter Guide"
(pdf,19KB).
- Note: This guide gives explanations
and illustrative settings for the TNGLab parameter values that can be entered by
users on the Settings Screen accessible through the TNGLab Graphical
User Interface (GUI). The admissible range of values for each TNGLab parameter
is also indicated.
TNGLab Demo/Developer Software Downloads
-
Software Release Disclaimer:
- All software provided below is unsupported and provided as-is, without
warranty of any kind. It is
released as open-source freeware by the copyright holders (D. McFadzean, D. Stewart, and
L. Tesfatsion) under the terms of the
Artistic License Agreement.
-
Possible Need for OCX File:
- Occasionally people attempting to install the TNG Lab on a local computer have reported receiving an error message saying they are missing a file called "comdlg32.ocx". If you find you need this file, a copy can be downloaded
here (137KB).
You should put this file in the following local computer directory: c:\windows\system32\
- TNGLab: A Computational Laboratory for Evolutionary Trade Networks (C++/Visual Basic)
The Trade Network Game Laboratory (TNGLab) is a
computational laboratory for exploring the evolution of trade networks among
strategically interacting buyers, sellers, and dealers through run-time
network animation, chart, and table displays. It is targeted for running
on a Microsoft Windows desktop pc. A TNGLab manual providing a
detailed presentation, motivation, and illustration of the TNGLab's
capabilities is provided in an article (cited/linked above) by D. McFadzean, D.
Stewart, and L. Tesfatsion titled "A Computational Laboratory for
Evolutionary Trade Networks."
An automatic installation program for Version
2000b of the TNGLab has been released as freeware by David McFadzean, Deron
Stewart, and Leigh Tesfatsion (the copyright holders) in a zip file
tlab00b.zip (2.6MB)
under the terms of the
Artistic License Agreement.
An accompanying
readme file
provides instructions regarding the downloading, unzipping, automatic installation, and running of the TNGLab on a MS Windows desktop pc.
- Complete TNGLab Development Software (C++/Visual Basic)
For those interested in modification/extension and recompilation of the TNGLab,
a zip file including complete TNGLab development software has been released as freeware
here (zip file,9.6MB)
by David McFadzean, Deron Stewart, and Leigh Tesfatsion (the copyright holders) under the terms of the
Artistic License Agreement.
More precisely, the TNGLab consists of four layers: (1) SymBioSys C++ class library;
(2) TNG derived C++ classes; (3) Microsoft components layer; and (4) the TNGLab GUI
(Visual Basic Shell). Source code for
all four layers is included in this zip file.
- TNG/SimBioSys: A C++ Framework for Studying the Formation and Evolution of Trade Networks
The Trade Network Game (TNG) has been implemented in C++ by David McFadzean and Leigh Tesfatsion with the support of the SimBioSys class framework; see below for a separate description of SimBioSys. A manual for this TNG/SimBioSys implementation is provided in David McFadzean and Leigh Tesfatsion, "A C++ Platform for the Evolution of Trade Networks"
(pdf,233KB),
Computational Economics 14 (1999), 109-134.
The published article is available from
SpringerLink.
Complete source code and executable files for TNG/SimBioSys
(Version 105c) have been released by David McFadzean and Leigh Tesfatsion (the copyright holders) as freeware in a zip file
tng105c.zip (139KB)
under the terms of the
Artistic License Agreement.
A text file of
instructions
for downloading, unzipping, and running TNG/SimBioSys (Version 105c) is also available. Modifications made to the online TNG/SimBioSys program, as indicated by changed version numbers, are explained in a
version record file.
- SimBioSys: A C++ Framework for Agent-Based Evolutionary Simulations
SimBioSys is a C++ class framework developed by David McFadzean (Master's Thesis,
University of Calgary, 1995) for general agent-based evolutionary simulations
in both biology and the social sciences. SimBioSys is designed to support
simulations comprising the following four features:
- A world defining the virtual environment where the
simulation occurs;
- Populations of autonomous agents inhabiting the
world;
- Programs driving the behavior of the agents;
- Genetic mechanisms emulating natural selection
which act on the agents' programs.
The
Master's Thesis
and a
source code zip file (33KB)
for the entire SimBioSys class framework have been released by David McFadzean
(the copyright holder) as freeware
under the terms of the
Artistic License Agreement.
TNGLab Manuals and Tutorials
- David McFadzean, Deron Stewart, and Leigh
Tesfatsion, "A Computational Laboratory for Evolutionary Trade
Networks"
(pdf,508KB),
IEEE Transactions on Evolutionary Computation, Vol. 5,
No. 5, October 2001, pp. 546-560.
The published article is also available at
IEEE Xplore.
- Abstract: This article constitutes the main
TNGLab Manual. It presents, motivates, and illustrates
the use of the TNGLab for the investigation of evolutionary
trade network formation among strategically interacting buyers, sellers, and
dealers. The modular and extensible architecture of the
TNGLab is explained in detail, together with the Settings, Results, Chart, and
Network Animation Screens that are accessible to users through the TNGLab
Graphical User Interface (GUI). The logical progression of the TNGLab is
concreted illustrated in terms of a labor market application.
- For detailed explanations and illustrative settings for the TNGLab parameter values
that can be entered by the user on the TNGLab GUI Settings Screen, see the
TNGLab Parameter Guide (pdf,19KB).
- David McFadzean and Leigh Tesfatsion, "An Agent-Based Computational
Model for the Evolution of Trade Networks"
(pdf,143KB),
pp. 73-83 in P. Angeline, R.
Reynolds, J. McDonnell, and R. Eberhart (eds.), Evolutionary Programming
VI, Proceedings of the Sixth International Conference on Evolutionary
Programming, Springer-Verlag, Berlin, 1997.
- Abstract: This proceedings paper presents a brief overview of the C++ source
code used to implement the Trade Network Game (TNG), a framework for studying
the formation and evolution of trade networks from an agent-based
perspective. A more detailed discussion of this C++ source code is given in
the following paper.
- David McFadzean and Leigh Tesfatsion, "A C++ Platform for the
Evolution of Trade Networks"
(pdf,233KB)],
Computational Economics 14 (1999), pp. 109-134.
The published article is available from
SpringerLink.
- Abstract: This study provides a detailed discussion of the C++ implementation
of the Trade Network Game (TNG), a computational framework for studying the
formation and evolution of trade networks in buyer-seller markets modeled as
decentralized systems of autonomous interacting agents. The source code for
this C++ implementation of the TNG is available online as freeware (see
below).
- TNGLab/ACE: Online Tutorials
The TNGLab is an example of an
Agent-based Computational Economics (ACE)
model. ACE is the computational modeling of economic processes (including whole economies) as open-ended dynamic systems of interacting agents.
I presented a two-part tutorial on ACE and the TNGLab at the James Franck Institute, U of Chicago, October
27-28, 2003. Links to updated versions of these tutorials are provided below.
- TUTORIAL ONE: ACE Approach to Market Modeling
(SlideSet,pdf,262KB).
Topics covered include: Complexity of real-world decentralized market processes; Illustrative two-sector hash-and-beans decentralized market economy; ACE approach to the modeling of real-world decentralized market economies.
- TUTORIAL TWO: ACE Computational Laboratories
(SlideSet,pdf,349KB).
Topics covered include: Agent-Oriented Programming (AOP) vs. Object-Oriented Programming (OOP); TNGLab: An ACE computational laboratory for the study of network formation among buyers, dealers, and sellers; Pointers to ACE software, toolkits, and computational laboratories.
TNGLab Research Articles
- Mark Pingle and Leigh Tesfatsion, "Evolution of Worker-Employer
Networks and Behaviors Under Alternative Non-Employment Benefits: An
Agent-Based Computational Study"
[
(paper,pdf,209KB),
(slides,pdf,87KB)],
pp. 253-284 in Anna Nagurney (ed.),
Innovations in Financial and Economic Networks, Edward Elgar
Publishers, 2003.
- Abstract: This study uses agent-based computational
experiments to examine the effects of a non-employment payoff on network
formation and work-site behaviors among workers and employers participating
in a sequential employment game with incomplete contracts. Workers either
direct work offers to preferred employers or choose unemployment and receive
the non-employment payoff. Subject to capacity limitations, employers either
accept work offers from preferred workers or remain vacant and receive the
non-employment payoff. Matched workers and employers participate in a risky
employment relationship modeled as a prisoner's dilemma game. Increases in
the non-employment payoff result in higher average unemployment and vacancy
rates while at the same time encouraging cooperation among the worker and
employers who do form matches. Taking both utility benefits and program
costs into account, the highest efficiency is achieved with a moderate
non-employment payoff level. A zero payoff encourages too much shirking on
the work-site, while a high payoff results in too high a risk of lost
earnings due to coordination failure.
- Leigh Tesfatsion, "Concentration, Capacity, and Market Power in an
Evolutionary Labor Market"
(pdf,336KB),
pages 1033-1040 in Evolution at Work for
the New Millenium, Proceedings of the 2000 Congress on Evolutionary
Computation, Volume II, IEEE, Inc., N.J., 2000, pp. 1033-1040.
The published article is available at
IEEE Xplore.
- Abstract: This conference paper provides a summary
overview of the detailed experimental findings reported in the following
JEDC (2001) study.
- Leigh Tesfatsion, "Structure, Behavior, and Market Power in an
Evolutionary Labor Market with Adaptive Search"
(pdf,295KB),
Journal of Economic
Dynamics and Control 25 (2001), pp. 419-457.
The published article is also available from
Science Direct.
- Abstract: This study uses an agent-based computational
labor market framework to undertake a systematic experimental investigation
of the relationship between market structure and market power. Market
structure is measured in terms of job capacity (total potential job openings
to total potential work offers) and job concentration (total number of
workers to total number of employers). For each tested market structure,
workers and employers repeatedly seek preferred worksite partners based on
continually updated expected utility, engage in efficiency-wage worksite
interactions modelled as prisoner's dilemma games, and evolve their worksite
behaviors over time. A key finding is the presence of strong learning and
network effects. Each tested market structure maps into a "spectral"
distribution of observed interaction networks exhibiting one dominant
attractor (frequent network pattern) with one or two weaker attractors (less
frequent network patterns). Market structure is strongly predictive for the
relative market power of workers and employers across all network
attractors, but the magnitudes of the market power levels attained by
workers and employers vary widely across the network attractors.
- Leigh Tesfatsion, "Hysteresis in an Evolutionary Labor Market with
Adaptive Search"
(pdf,222KB),
pp. 189-210 in S.-H. Chen (ed.), Evolutionary
Computation in Economics and Finance, Physica-Verlag Heidelberg, New
York, 2002.
- Abstract: This study undertakes a systematic experimental
investigation of hysteresis (path dependency) in an agent-based computational
labor market framework. It is shown that capacity asymmetries between work
suppliers and employers can result in two distinct hysteresis effects,
network and behavioral, when work suppliers and employers interact
strategically and evolve their worksite behaviors over time. These
hysteresis effects result in persistent heterogeneity in earnings and
employment histories across agents who have no observable structural
differences. At a more global level, these hysteresis effects are shown to
result in a one-to-many mapping between treatment factors and experimental
outcomes. These hysteresis effects may help to explain why excess earnings
heterogeneity is commonly observed in real-world labor markets.
- Leigh Tesfatsion, "Preferential Partner Selection in Evolutionary
Labor Markets: A Study in Agent-Based Computational Economics"
(pdf,153KB),
pp. 15-24 in V. W. Porto, N. Saravanan, D. Waagen, and A. E. Eiben (eds.),
Evolutionary Programming VII, Proceedings of the Seventh Annual
Conference on Evolutionary Programming, Springer-Verlag, Berlin, 1998.
- Abstract: This study develops a computational labor market
framework for studying the formation and evolution of contractual networks
between workers and employers. Resource-constrained workers and employers
choose and refuse contractual partners on the basis of continually updated
expected utility, engage in risky worksite interactions modelled as
two-person "efficiency-wage" prisoner's dilemma games, and evolve their
work-site strategies over time on the basis of past worksite earnings.
Illustrative computational experiments are reported and interpreted.
- Leigh Tesfatsion, "Gale Shapley Matching in an Evolutionary Trade
Network Game"
(pdf,230KB),
Economic Report 43, Iowa State University, April 1998; Revised May 1998.
- Abstract: This study investigates the performance of
Gale-Shapley matching in an evolutionary market context. Computational
experiments are reported for an evolutionary match-and-play trade network
game in which resource-constrainted traders repeatedly choose and refuse
trade partners in accordance with Gale-Shapley matching, participate in risky
trades modelled as two-person prisoner's dilemma games, and evolve their
trade behavior over time. Particular attention is focused on correlations
between ax ante market structure and the formation of trade networks, and
between trade network formation and the types of social welfare outcomes that
these trade networks support.
- Leigh Tesfatsion, "A Trade Network Game with Endogenous Partner
Selection"
(pdf,392KB),
pp. 249-269 in H. M. Amman, B. Rustem, and A. B. Whinston
(eds.), Computational Approaches to Economic Problems, Kluwer Academic
Publishers, 1997.
- Abstract: This study develops a Trade Network Game (TNG)
framework for studying the interplay between evolutionary game dynamics and
preferential partner selection in buyer-seller markets. The TNG consists of
successive generations of resource-constrained traders who choose and refuse
trade partners on the basis of continually updated expected payoffs, engage
in risky trades modelled as two-person games, and evolve their trade
strategies over time. Preliminary computer experiments are reported which
suggest that the standard optimality properties used to judge the
desirability of matching mechanisms in static market contexts may be
inadequate measures of optimality from an evolutionary perspective.
- Leigh Tesfatsion, "How Economists Can Get Alife"
(pdf,298KB),
pp. 533-564 in W. Brian Arthur, Steven Durlauf, and David Lane (eds.), The Economy as an
Evolving Complex System, II, Santa Fe Institute Studies in the Sciences
of Complexity, Volume XXVII, Addison-Wesley, 1997.
- Abstract: This study presents a summary overview of
the basic artificial life (alife) paradigm, stressing aspects especially
relevant for the study of decentralized market economies. In particular,
recent work on a Trade Network Game (TNG) framework combining evolutionary
game play with endogenous partner selection is used to illustrate how the
alife paradigm might be specialized to economics. Analytical and simulation
work is reported to show how the TNG is currently being used to study the
evolutionary implications of alternative market structures at three different
levels: individual trade behavior; trade network formation; and social
welfare.
Related Research on IPD with Partner Choice and Refusal
- E. Ann Stanley, Dan Ashlock, and Leigh Tesfatsion (1994), "Iterated Prisoner's Dilemma with Choice and Refusal of Partners"
(pdf,3.5MB),
pp. 131-175, in C. Langton (ed.), Artificial Life III, Volume XVII, Santa Fe Institute
Studies in the Sciences of Complexity, Addison-Wesley.
- Abstract: "This article extends the traditional iterated prisoner's dilemma (IPD) with round-robin partner matching by permitting players to choose and refuse partners in each iteration on the basis of continually updated expected payoffs. Comparative computer experiments are reported that indicate the introduction of partner choice and refusal accelerates the emergence of mutual cooperation in the IPD relative to round-robin partner matching. Moreover, in contrast to findings for round-robin partner matching (in which the average payoffs of the players tend to be either clustered around the mutual cooperation payoff or widely scattered), the average payoff scores of the players with choice and refusal of partners tend to cluster into two or more distinct narrow bands.
Preliminary analytical and computational sensitivity studies are also reported for several key parameters."
- Dan Ashlock, Mark D. Smucker, E. A. Stanley, and Leigh Tesfatsion (1996), "Preferential Partner Selection in an Evolutionary Study of Prisoner's Dilemma"
(pdf,2.5MB),
BioSystems 37, No. 1-2, pp. 99-125.
The published article is also available from
Science Direct.
- Abstract: This study reports on extensive computer experiments for the `Iterated Prisoner's Dilemma with Choice and Refusal of Partners (IPD/CR)' framework developed by Stanley, Ashlock, and Tesfatsion (Artificial Life III, 1994). For example, it is shown that the introduction of choice and refusal tends to enhance the emergence of cooperation in IPD games in comparison to either random or
round-robin partner selection. In addition, with choice and refusal of partners, the fitness values of the players tend to cluster fairly tightly into a small number of narrow regions. Within any one fitness region, however, the players consist of genetically diverse players with interaction patterns peculiarly adapted to the choice and refusal mechanism. Detailed
sensitivity studies are also reported with respect to key parameters such as the learning algorithm `memory weight,' the `minimum' tolerance level' below which game offers are refused, and the `refusal payoff' incurred by a player whenever one of his game offers is refused.
- Mark D. Smucker, E. Ann Stanley, and Dan Ashlock (1994), "Analyzing Social Network Structures in the Iterated Prisoner's Dilemma with Choice and Refusal"
(pdf,429KB),
Technical Report 1259, Computer Sciences Department, University
of Wisconsin, December.
- Abstract: This study exams one particular case of the Iterated Prisoner's Dilemma with Choice and Refusal of Partners (IPD/CR) framework developed by Stanley, Ashlock, and Tesfatsion (Artificial Life III, 1994). It documents the social network methods used to identify population
behaviors found within this complex adaptive system. In contrast to the
standard homogeneous population of nice cooperators, metastable populations
of mixed strategies are found within this environment. The social networks
of interesting populations and their evolution are examined.
- Esther Hauk (2001), "Leaving the Prison: Permitting Partner Choice and
Refusal in Prisoner's Dilemma Games," Computational Economics 18,
No. 1, August, 65-87.
- Abstract: This study proposes a simple rule of thumb
regarding how to choose one's game partner that allows economic agents who
care about the future to learn to cooperate in the iterated prisoner's
dilemma. This rule of thumb uses partner selection strategically to reward
cooperative behavior and teach defectors a lesson. This reward and
punishment scheme leads to higher payoffs of non-exploitive strategies and
slowly converts defectors, who are attracted by the higher payoffs, into
non-exploitive types. Simulations show that the convergence to stable
cooperative behavior is rather fast.
Copyright © Leigh Tesfatsion. All Rights Reserved.
