%Paper: ewp-game/9501002
%From: "Leigh Tesfatsion" <S1.TES@ISUMVS.IASTATE.EDU>
%Date: Wed, 18 Jan 95 11:56:14 CST
%Date (revised): Fri, 20 Jan 95 19:54:50 CST


% Below are LaTeX files for the introductory section and references
% for:  "Preferential Partner Selection in an Evolutionary Study of
% Prisoner's Dilemma," by D.  Ashlock, M.  Smucker, E.  Ann Stanley,
% and L. Tesfatsion.  A complete  copy  of this paper can by obtained
% in three ways:
%
% editor comment: 9501002p.ps.Z is available here
%
% (1) in hardcopy form from L. Tesfatsion (tesfatsi@iastate.edu);
% (2) Archive  retrieval  from  adap-org@xyz.lanl.gov, where it is
%     posted  as  Paper  No.   9412001  [a  28  page  UUencoded
%     gzip's Postscript file, 1.8Mb uncompressed]. Mail to
%     nlin-sys@xyz.lanl.gov  with subject "get announce"
%     for information on usage;
% (3) via WWW at
%     http://www.cs.wisc.edu/~smucker/ipd-cr/ipd-cr.html.
%
\documentstyle[12pt]{article}
\pagestyle{plain}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}
\setlength{\headheight}{0in}
\setlength{\parindent}{20pt}
\setlength{\headsep}{0in}
\setlength{\topmargin}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}

\begin{document}

\setlength{\baselineskip}{13pt}
                                                 \begin{flushright}
                              {\bf ISU Economic Report No.~35, 1994}\\
                                         {\bf to appear in BioSystems}
                              \end{flushright}
\vspace*{4mm}
\setlength{\baselineskip}{22pt}
                             \begin{center}
          {\Large {\bf Preferential Partner Selection in an\\
                    Evolutionary Study of Prisoner's Dilemma}} \\
\vspace*{12mm}

 {\bf Dan Ashlock}$^{\dag}${\bf, Mark D.~Smucker}$^{\S}${\bf, E.~Ann
Stanley}$^{\dag}${\bf, and Leigh Tesfatsion}$^{*\dag}$

\vspace *{4mm}
\end{center}
\setlength{\baselineskip}{13pt}

$^{\dag}$ Department of Mathematics, 400 Carver, and $^*$ Department of
Economics,
375 Heady Hall,
Iowa State University, Ames, Iowa 50011-1070,

$^{\S}$ Department of  Computer Sciences, 1210 West Dayton Street,
University of Wisconsin-Madison, Madison, Wisconsin 53706.

\vspace*{5mm}
\begin{center}
                         {\bf Abstract} \\
                            \end{center}


     Partner selection is an important process in many social
interactions, permitting individuals to decrease the risks
associated with cooperation.  In large populations, defectors may
escape punishment by roving from partner to partner, but defectors
in smaller populations risk social isolation.  We investigate these
possibilities for an evolutionary prisoner's dilemma in which agents
use expected payoffs to choose and refuse partners.  In comparison
to random or round-robin partner matching, we find that the average
payoffs attained with preferential partner selection tend to be more
narrowly confined to a few isolated payoff regions.  Most ecologies
evolve to essentially full cooperative behavior, but when agents
are intolerant of defections, or when the costs of refusal and
social isolation are small, we also see the emergence of
wallflower ecologies in which all agents are socially isolated.
In between these two extremes, we see the emergence of ecologies
whose agents tend to engage in a small number of defections followed
by cooperation thereafter.  The latter ecologies exhibit a plethora
of interesting social interaction patterns.
\vspace*{6mm}

\noindent {\bf Keywords:} Evolutionary Game; Iterated Prisoner's Dilemma;
Partner Choice and Refusal; Artificial Life; Genetic Algorithm;
Finite Automata.

\vspace*{3mm}
\begin{center}
{\bf INTRODUCTION\/}
\end{center}

Following the path-breaking work of
Axelrod~\cite{Axelrod84a,Axelrod87a,Axelrod88a}, the Iterated
Prisoner's Dilemma (IPD) is now commonly used by researchers to
explore the potential emergence of mutually cooperative behavior
among non-altruistic agents.  See, for example,
Miller~\cite{Miller89a} and Lindgren and
Nordahl~\cite{Lindgren94a}.  These studies have shown that mutually
cooperative behavior tends to emerge if the number of game
iterations is either uncertain or infinite, the frequency of
mutually cooperative play in initial game iterations is sufficiently
high, and the perceived probability of future interactions with any
given current opponent is sufficiently large.

     Most studies of IPD assume that individual players have no
control over which opponents they play.  Players are matched as game
partners either randomly or by means of a deterministic mechanism
such as round-robin or grid neighborhood play.  In real-life
situations, however, agents are not always prisoners who have no
alternative but to play their assigned PD games.  Instead, social
interactions are often characterized by the preferential choice and
refusal of partners.  In what ways, then, might the introduction of
preferential partner selection change the nature of the IPD?

     Previous research suggests that, depending upon the precise
population structure, the decision rules used for partner selection,
and the penalties imposed for rejected offers and for deciding not
to play, cooperators or defectors may benefit from preferential
partner selection.  For example, Kitcher~\cite{Kitcher92a} and
Schuessler~\cite{Schuessler89a} show that the option of refusing to
play previously defecting players can increase the fitness of
cooperative players and allow them to invade defecting populations.
Orbell and Dawes~\cite{Orbell93a} argue that it is to the benefit
of society as a whole to evolve social structures that allow
individuals to opt out of games. Their experiments indicate that
humans who are themselves cooperatively inclined tend to be more
optimistic about the cooperative intentions of other players and
hence to play more games.  In Eshel and
Cavalli-Sforza~\cite{Eshel82a}, beneficial assortative mixing may
occur either because agents playing the same strategy are more
likely to encounter each other, or because agents playing
cooperative strategies actively select each other.

     The ability to actively seek out known cooperators as partners
also provides an incentive for agents to be reliably cooperative, so
that they will be chosen as partners, and this potentially increases
the incidence of cooperation in a society~\cite{Tullock85}.
Hirshleifer and Rasmussen~\cite{Hirshleifer89a} find that group
ostracism can permit cooperative agents to protect themselves from
defectors.  On the other hand, Dugatkin~\cite{Dugatkin91a} shows
that the ability to choose partners in large populations divided
into isolated patches may permit roving defectors to move from one
patch to the next, avoiding ostracism while taking advantage of each
patch in turn.

     Finally, the introduction of preferential partner selection
results in social networks of interacting players.  Who chooses
whom, and why, affects who does well, and this in turn affects the
outcomes of the overall game. Questions about social network
formation are key to understanding societies. How do groups form?
What roles do highly connected individuals play?  Social networks
are also interesting because they are pathways for the transmission
of diseases, information, and cultural traits.

     In a previous paper~\cite{Stanley94a}, we studied an IPD choice
and refusal mechanism that combines active choice of potential game
partners with the ability to refuse play with those judged to be
intolerable.  Players use continually updated expected payoffs to
assess the relative desirability of potential partners.  This use of
expected payoffs is meant to capture the idea that players attempt
to select partners rationally, using some degree of anticipation,
even though they do not know their partners' strategies and payoffs.
Our choice and refusal mechanism is thus more flexible and general
than many of the mechanisms studied by previous researchers,
although it does not currently allow for the information exchange
between players assumed by Kitcher.  Also, we considered a single
small population, so that defectors cannot rove from one isolated
population to the next, as in Dugatkin~\cite{Dugatkin91a}, but
instead risk eventual ostracism.

    In particular, we studied how the ability both to choose and to
refuse potential game partners affects interactions among a small
set of simple IPD strategies, and we used a five-player population
to illustrate the formation of social networks.  We also conducted a
number of evolutionary simulations.  The interaction dynamics in
both our analytical and simulation studies were seen to be complex,
even for small populations.  Choice is used by all players to home
in quickly on those who will cooperate with them.  This permits nice
players to interact with each other, but also allows predatory
individuals to locate and form long term relationships with victims
within the limit of occasional defection tolerated by the refusal
mechanism.  On the other hand, refusal ensures that very nasty
players do poorly, since repeatedly defecting players are typically
ostracized as other players increasingly refuse their offers.
Indeed, wallflower populations sometimes emerged in which all
players defected until they became solitary, neither making nor
accepting game offers from other players.  Overall, however, we
observed cooperation to emerge much more quickly and frequently with
choice and refusal of partners than with round-robin matching.

     In this paper we present a variety of new analytical and
simulation findings on the evolutionary IPD with choice and refusal
of partners, or evolutionary IPD/CR for short.  We first review in
Section 2 the basic structure and implementation of the evolutionary
IPD/CR.  In particular, we discuss the finite state machines used to
represent players' IPD strategies as well as the genetic algorithm
used to evolve the player population from an initial,
randomly-chosen population.

     Players in our co-evolutionary framework cannot necessarily
jump from a defecting mode of behavior to a cooperative one.  In
particular, the genetic material available in our initial population
constrains its future evolution.  This path dependence turns out to
be particularly important for the interpretation of the IPD/CR
simulation studies reported in the present paper, since we work with
relatively small populations of thirty players.  Section 3 thus
undertakes an analytical characterization of the distribution of
behaviors in the initial player population.  In particular, it is
shown that a uniformly distributed selection of genetic structures
for these players implies a nonuniform selection of their IPD
strategies, one that is highly biased towards simple strategies.

     In the final two sections we detail a series of simulation
studies that have been conducted to explore the sensitivity of
evolutionary IPD/CR outcomes to changes in key parameters.  In
particular, we first describe one-parameter and two-parameter
sensitivity studies for the parameters characterizing the choice and
refusal mechanism.  We then report on experiments conducted to test
the sensitivity of outcomes to changes in the potential complexity
of players' IPD strategies, as measured by the number of states in
their finite state machine representations.  Also, we briefly
summarize preliminary studies in which two key parameters
characterizing the choice and refusal mechanism are incorporated
into the genetic structure of each player and allowed to evolve over
time.  Finally, we discuss the sensitivity of the behavioral
diversity of our populations to changes in the implementation of the
genetic algorithm used to evolve our player populations.


\vspace{4mm}
                    \begin{thebibliography}{10}

\setlength{\baselineskip}{15pt}

\bibitem{Axelrod84a}
R.~Axelrod (1984) {\em The Evolution of Cooperation}, Basic Books.

\bibitem{Axelrod87a}
R.~Axelrod (1987) ``The Evolution of Strategies in the Iterated Prisoner's
Dilemma,'' In: {\em Genetic Algorithms and Simulated Annealing}, L.  Davis
(ed.), Morgan Kaufmann.

\bibitem{Axelrod88a} R.~Axelrod \& D.~Dion (1988)
``The Further Evolution of Cooperation,'' {\em Science}, Vol. 242, pp.
1385--1390.

\bibitem{Dugatkin91a} L.~A. Dugatkin \& D.~S.
Wilson (1991) ``Rover: A Strategy for Exploiting Cooperators in a Patchy
Environment,'' {\em The American Naturalist}, Vol. 138, pp. 687--701.

\bibitem{Eshel82a} I.~Eshel \& L.~L.
Cavalli-Sforza (1982) ``Assortment of Encounters and Evolution of
Cooperativeness,'' {\em Proceedings of the National Academy of Sciences,
U.S.A}, Vol. 79, pp. 1331--1335.

\bibitem{Goldberg89a} D.~E. Goldberg (1989) {\em {G}enetic
{A}lgorithms in Search, Optimization, and Machine Learning}, Addison-Wesley.

\bibitem{Hirshleifer89a}
D.~Hirshleifer \& E.~Rasmusen (1989)
``Cooperation in a Repeated Prisoners' Dilemma with Ostracism,''
{\em Journal of Economic Behavior and Organization}, Vol. 12, pp. 87--106.

\bibitem{Holland92a}
J.~Holland (1992)
{\em Adaptation in Natural and Artificial Systems},
MIT Press.

\bibitem{Kitcher92a} P.~Kitcher (1992) ``Evolution of Altruism in Repeated
Optional Games,'' Working Paper, Department of Philosophy, University of
California at San Diego.

\bibitem{Lindgren91a} K.~Lindgren (1991) ``Evolutionary Phenomena in Simple
Dynamics,'' In: {\em Artificial Life II}, D. Farmer, C. Langton, S.
Rasmussen, \& C. Taylor (eds.), SFI Studies in the Sciences of Complexity,
Proc. Vol. 10, Addison-Wesley, pp. 1--18.

\bibitem{Lindgren94a} K.~Lindgren \& M.~G. Nordahl (1994) ``Artificial Food
Webs,'' In: {\em Artificial Life III}, C.~G. Langton (ed.), SFI Studies in
the Sciences of Complexity, Proc. Vol. 17, Addison-Wesley, pp. 73--103.

\bibitem{Marimon92a} R.~Marimon, E.~McGrattan, \& T.~Sargent (1990) ``Money
as a Medium of Exchange in an Economy with Artificially Intelligent Agents,''
{\em Journal of Economic Dynamics and Control}, Vol. 14, pp. 329-373.

\bibitem{Miller89a} J.~H. Miller (1989) ``The Coevolution of Automata in the
Repeated Prisoner's Dilemma,'' A Working Paper from the SFI Economics
Research Program 89-003, Santa Fe Institute and Carnegie-Mellon University.

\bibitem{Orbell93a} J.~M. Orbell \& R.~M. Dawes (1993) ``Social Welfare,
Cooperator's Advantage, and the Option of Not Playing the Game,'' to appear
in the {\em American Sociological Review}.

\bibitem{Schuessler89a} R.~Schuessler (1989) ``Exit Threats and Cooperation
Under Anonymity,'' {\em Journal of Conflict Resolution}, Vol. 33, pp.
728--749.

\bibitem{Smucker94a} M.~D. Smucker, E.~A. Stanley, \& D.~Ashlock (1994)
``Analyzing Social Network Structures in the Iterated Prisoner's Dilemma with
Choice and Refusal,'' Technical Report No. 1259, Computer Science Department,
University of Wisconsin at Madison, December 1994.

\bibitem{Stanley94a} E.~A. Stanley, D.~Ashlock, \& L.~Tesfatsion
(1994) ``Iterated Prisoner's Dilemma with Choice and Refusal of Partners,''
In: {\em Artificial Life III}, C.~G. Langton (ed.), SFI Studies in the
Sciences of Complexity, Proc. Vol. 17, Addison-Wesley, pp. 131--176.

\bibitem{Tesfatsion79a} L.~Tesfatsion (1979) ``Direct Updating of
Intertemporal Criterion Functions for a Class of Adaptive Control Problems,''
{\em IEEE Transactions on Systems, Man, and Cybernetics}, Vol. SMC-9, pp.
143--151.

\bibitem{Tesfatsion94a} L.~Tesfatsion (1994) ``A Trade Coalition Game with
Preferential Partner Selection.'' Economics Working paper, October.

\bibitem{Tullock85} G.~Tullock (1985) ``{A}dam {S}mith and the Prisoner's
Dilemma,'' {\em The Quarterly Journal of Economics}, Vol. 100, pp.
1073--1081.

\end{thebibliography}


\end{document}