Date of Degree

9-2020

Document Type

Dissertation

Degree Name

Ph.D.

Program

Computer Science

Advisor

Shweta Jain

Committee Members

Rohit Parikh

Feng Gu

Delaram Kahrobaei

Subject Categories

Applied Statistics | Other Computer Sciences | Other Mathematics

Keywords

Game, evolutionary, dynamics, best response, networks

Abstract

Game theory is a wide ranging research area; that has attracted researchers from various fields. Scientists have been using game theory to understand the evolution of cooperation in complex networks. However, there is limited research that considers the structure and connectivity patterns in networks, which create heterogeneity among nodes. For example, due to the complex ways most networks are formed, it is common to have some highly “social” nodes, while others are highly isolated. This heterogeneity is measured through metrics referred to as “centrality” of nodes. Thus, the more “social” nodes tend to also have higher centrality.

In this thesis, two 2-player games are used to understand properties of several types of graph structures. In particular, how information would travel if people had the tendency to follow friends/connections with higher influences than themselves. Simulation framework is created and experiments are done with Stag Hunt and Hawk Dove games in Torus, Grid, Random, Watts Strogatz, Barabasi-Albert, and a Facebook friendship datasets. The game is played in multiple rounds or until the steady state is reached. After each round, each player may independently decide to change their strategy. This change in strategy is determined using best response dynamics, given the player’s payoff relative to their neighbors, in the previous round. This is also known as evolutionary dynamics or diffusion. In this thesis, a new method is introduced in which players use a Fermi like function to use relative centrality as a factor in choosing their strategy for the subsequent round of the game. This model considers the centrality of each node related to the whole population. Evolution of strategies under various measures of centrality is observed. This approach helps us understand how information flows through the network when nodes in the network are “influenced” by their neighbors’ centrality (and hence power) in the network.

By comparing these two strategy update rules, some similarities as well as differences, in relation to the speed of convergence, the point of convergence, and the final steady state is encountered . In some networks, in order to reach a steady state in the Stag Hunt game with centrality based rule, more Stags are necessary for the stags to dominate the network at steady state. It was also very apparent that centrality is affecting the time it takes to reach steady state. This is a sign of how some centrality measures affect the dynamics of the whole population. These results have allowed us to delve deeply into understanding the social impact of decision making and what occurs as a direct result of that social impact on a population thereafter.

This work is embargoed and will be available for download on Thursday, September 30, 2021

Graduate Center users:
To read this work, log in to your GC ILL account and place a thesis request.

Non-GC Users:
See the GC’s lending policies to learn more.

Share

COinS