Non-cooperative games on networks
Date
2013-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: There are many examples of cooperation in action in society and in nature. In some cases
cooperation leads to the increase of the overall welfare of those involved, and in other cases
cooperation may be to the detriment of the larger society. The presence of cooperation seems
natural if there is a direct bene t to individuals who choose to cooperate. However, in examples
of cooperation this bene t is not always immediately obvious. The so called prisoner's
dilemma is often used as an analogy to study cooperation and tease out the factors that lead
to cooperation.
In classical game theory, each player is assumed to be rational and hence typically seeks to
select his strategy in such a way as to maximise his own expected pay-o . In the case of the
classical prisoner's dilemma, this causes both players to defect. In evolutionary game theory,
on the other hand, it is assumed that players have limited knowledge of the game and only
bounded rationality. Games in evolutionary game theory are repeated in rounds and players are
a orded the opportunity to adapt and learn as this repetition occurs. Past studies have revealed
that cooperation may be a viable strategy if the prisoner's dilemma is placed in an evolutionary
context, where the evolutionary tness of a strategy is directly related to the pay-o achieved
by the player adopting the strategy. One of the mechanisms that promote the persistence of
cooperation in the evolutionary prisoner's dilemma is structured interaction between players.
A mathematical framework for representing the evolutionary prisoner's dilemma (ESPD) is developed
in this thesis. The mathematical framework is used to undertake an analytical approach
(i.e. avoiding the use of simulation) towards investigating the dynamics of the ESPD with a
path, cycle, plane grid or toroidal grid as underlying graph. The objective of this investigation
is to determine the likelihood of the emergence of persistent cooperation between players. The
ESPD on a path or a cycle admits two fundamentally di erent parameter regions; large values
of the temptation-to-defect parameter are not capable of inducing persistent cooperation, while
small values of this parameter allow for the possibility of persistent cooperation. It is found that
the likelihood of cooperation increases towards certainty as the order of the underlying graph
increases if the underlying graph is a path or cycle.
The state space of the ESPD with a plane or toroidal grid graph as underlying graph grows
very quickly as a function of the graph order. The automorphism classes of game states are
enumerated to determine exactly how fast the size of the state space of the game grows as a
function of the order of the underlying graph. Finally, the dynamics of the ESPD is investigated
for a grid graph as underlying graph (in cases where the state space is small enough) by means
of constructing the corresponding state graphs of the ESPD.
AFRIKAANSE OPSOMMING: Daar is baie voorbeelde van samewerking in the gemeenskap en in die natuur. In sommige gevalle lei samewerking tot 'n toename in die algehele welvaart van die betrokkenes, terwyl samewerking in ander gevalle tot nadeel van die bre er gemeenskap mag wees. Die voorkoms van samewerking blyk natuurlik te wees indien daar 'n direkte voordeel vir die individue is wat kies om saam te werk. In voorbeelde van samewerking is s o 'n voordeel egter nie altyd voor-diehand- liggend nie. Die sogenaamde prisoniersdilemma word dikwels as voorbeeld in die studie van samewerking gebruik om die faktore wat na samewerking lei, te ontbloot. In klassieke speleteorie word daar aangeneem dat elke speler rasioneel is en dus poog om sy spelstrategie op s o 'n manier te kies dat sy eie verwagte uitbetaling gemaksimeer word. In die geval van die klassieke prisoniersdilemma veroorsaak dit dat beide spelers mekaar verraai. In evolusion^ere speleteorie, daarenteen, word daar slegs aangeneem dat elke speler oor beperkte kennis van die spel en begrensde rasionaliteit beskik. Spele in evolusion^ere speleteorie word in rondtes herhaal en spelers word die geleentheid gebied om gedurende hierdie herhalingsproses aan te pas en te leer. Vorige studies het getoon dat samewerking 'n lewensvatbare strategie is indien die prisoniersdilemma in 'n evolusion^ere konteks gespeel word, waar die evolusion^ere ksheid van 'n strategie direk afhang van die uitbetaling van 'n speler wat die strategie volg. Een van die meganismes wat volhoubare samewerking in die evolusion^ere prisoniersdilemma voortbring, is gestruktureerde interaksie tussen spelers. 'n Wiskundige raamwerk word vir die voorstelling van die evolusion^ere prisoniersdilemma in hierdie tesis ontwikkel. Hierdie wiskundige raamwerk word gebruik om 'n analitiese studie (met ander woorde sonder die gebruik van simulasie) van die dinamika van die prisoniersdilemma op 'n pad, siklus, rooster in die vlak, of rooster op die torus as onderliggende gra ek van stapel te stuur. Die doel van hierdie studie is om die waarskynlikheid vir die ontstaan van volhoubare samewerking tussen spelers te bepaal. Die prisoniersdilemma op 'n pad of siklus as onderliggende gra ek het twee fundamenteel verskillende parametergebiede tot gevolg; groot waardes van die versoeking-om-te-verraai parameter lei nie tot volhoubare samewerking nie, terwyl volhoubare samewerking wel vir klein waardes van hierdie parameter moontlik is. Daar word gevind dat die kans vir volhoubare samewerking toeneem tot sekerheid namate die orde van die onderliggende gra ek groei. Die toestandsruimte van die prisoniersdilemma met 'n rooster in die vlak of 'n rooster op die torus as onderliggende gra ek groei baie vinnig as 'n funksie van die orde van die gra ek. Die outomor smeklasse van die speltoestande word getel met die doel om te bepaal presies hoe vinnig die toestandsruimte van die spel as 'n funksie van die orde van die onderliggende gra ek groei. Die dinamika van die prisoniersdilemma met 'n rooster in die vlak of 'n rooster op die torus as onderliggende gra ek word laastens deur middel van konstruksies van die ooreenstemmende toestandsgra eke ondersoek (in gevalle waar die toestandsruimte klein genoeg is).
AFRIKAANSE OPSOMMING: Daar is baie voorbeelde van samewerking in the gemeenskap en in die natuur. In sommige gevalle lei samewerking tot 'n toename in die algehele welvaart van die betrokkenes, terwyl samewerking in ander gevalle tot nadeel van die bre er gemeenskap mag wees. Die voorkoms van samewerking blyk natuurlik te wees indien daar 'n direkte voordeel vir die individue is wat kies om saam te werk. In voorbeelde van samewerking is s o 'n voordeel egter nie altyd voor-diehand- liggend nie. Die sogenaamde prisoniersdilemma word dikwels as voorbeeld in die studie van samewerking gebruik om die faktore wat na samewerking lei, te ontbloot. In klassieke speleteorie word daar aangeneem dat elke speler rasioneel is en dus poog om sy spelstrategie op s o 'n manier te kies dat sy eie verwagte uitbetaling gemaksimeer word. In die geval van die klassieke prisoniersdilemma veroorsaak dit dat beide spelers mekaar verraai. In evolusion^ere speleteorie, daarenteen, word daar slegs aangeneem dat elke speler oor beperkte kennis van die spel en begrensde rasionaliteit beskik. Spele in evolusion^ere speleteorie word in rondtes herhaal en spelers word die geleentheid gebied om gedurende hierdie herhalingsproses aan te pas en te leer. Vorige studies het getoon dat samewerking 'n lewensvatbare strategie is indien die prisoniersdilemma in 'n evolusion^ere konteks gespeel word, waar die evolusion^ere ksheid van 'n strategie direk afhang van die uitbetaling van 'n speler wat die strategie volg. Een van die meganismes wat volhoubare samewerking in die evolusion^ere prisoniersdilemma voortbring, is gestruktureerde interaksie tussen spelers. 'n Wiskundige raamwerk word vir die voorstelling van die evolusion^ere prisoniersdilemma in hierdie tesis ontwikkel. Hierdie wiskundige raamwerk word gebruik om 'n analitiese studie (met ander woorde sonder die gebruik van simulasie) van die dinamika van die prisoniersdilemma op 'n pad, siklus, rooster in die vlak, of rooster op die torus as onderliggende gra ek van stapel te stuur. Die doel van hierdie studie is om die waarskynlikheid vir die ontstaan van volhoubare samewerking tussen spelers te bepaal. Die prisoniersdilemma op 'n pad of siklus as onderliggende gra ek het twee fundamenteel verskillende parametergebiede tot gevolg; groot waardes van die versoeking-om-te-verraai parameter lei nie tot volhoubare samewerking nie, terwyl volhoubare samewerking wel vir klein waardes van hierdie parameter moontlik is. Daar word gevind dat die kans vir volhoubare samewerking toeneem tot sekerheid namate die orde van die onderliggende gra ek groei. Die toestandsruimte van die prisoniersdilemma met 'n rooster in die vlak of 'n rooster op die torus as onderliggende gra ek groei baie vinnig as 'n funksie van die orde van die gra ek. Die outomor smeklasse van die speltoestande word getel met die doel om te bepaal presies hoe vinnig die toestandsruimte van die spel as 'n funksie van die orde van die onderliggende gra ek groei. Die dinamika van die prisoniersdilemma met 'n rooster in die vlak of 'n rooster op die torus as onderliggende gra ek word laastens deur middel van konstruksies van die ooreenstemmende toestandsgra eke ondersoek (in gevalle waar die toestandsruimte klein genoeg is).
Description
Thesis (MSc)--Stellenbosch University, 2013.
Keywords
Prisoner's dilemma, Evolutionary game theory, Asymptotic analysis, Dissertations -- Logistics, Theses -- Logistics, Dissertations -- Operations research, Theses -- Operations research, Game theory, Prisoner's dilemma game, Cooperativeness