Tag: game theory

GAMES MODELS

As we talked about in the previous module, a game within game theory is any situation involving interdependency between adaptive agents.

Games are fundamentally different from decisions made in a context with only one adaptive agent. To illustrate this point, think of the difference between the decisions of a bricklayer and those of a business person. When the bricklayer decides how he might go about building a house he does not expect the bricks and mortar to fight back. We could call this a neutral environment.

But when the business person tries to enter a new market, they must take note of the actions and of the other actors in that market in order to best understand the viable options available to them.

A situation that depends only on the actions of one actor is best understood as one of decision theory not so much game theory.

Like the business person, all players engaged in a game must recognize their interaction with other intelligent and purposeful agents. Their own choices must allow both for conflict and for possibilities for cooperation. So a game really tries to capture this dynamic where autonomous agents that have their own goals are interdependent in effecting some joint outcome.

A game has three major components: players, strategies, and payoffs.

• A player is a decision maker in a game.
• A strategy is a specification of a decision for each possible situation in which a player may find themselves.
• A payoff is a reward or loss that players experience when all the players follow their respective strategies.

GAME REPRESENTATION

Games are represented in either a matrix form or as a tree graph.

• The matrix form models a game without time involved where players must choose their strategies simultaneously.
• A tree graph model involves time as an element allowing for choices to be made in a sequential process over a course of time, thus forming a tree-like representation that captures the choices made by agents at each stage in the game.

The matrix model is the most common method for representing a game and is called in game theory normal-form representation. The normal-form representation to a game associates the players with the axes to the matrix, with each column or row along the axis corresponding to one unique strategy for the player.

Where the players’ different strategies interact in the matrix, a value is placed to represent the associated payoffs for each player if those given strategies are played.

In simultaneous games, the players don’t have to move at the same time. The only restriction is that no players can know the other players’ decisions when they make their own choice.

The normal form is a condensed form of the game, stripped of all features but the possible options of each player and their payoffs during one iteration of the game. This makes it more convenient to analyze.

A game where choices are made sequentially over time is represented as a decision tree graph that branches out with each iteration of the game as time goes forward and players have to make choices. An example of this extensive form of game would be chess where players move in a sequential process with each move of one player creating a multiplicity for possible new moves of the other as they branch out into the future.

Players engaged in a sequential game then have to look ahead and reason back as each player tries to figure out how the other players will respond to his current move, how he will respond in turn, and so on. The player anticipates where his initial decisions will ultimately lead and uses this information to calculate his current best choice.

INFORMATION

Agents within a game are making their choices based on the information available to them. Thus we can identify information as a second important factor in the makeup of the game.

In any given game agents can have complete information meaning each player has knowledge of the payoffs and possible strategies of other players, or incomplete information referring to situations in which the payoffs and strategies of other players are not completely known.

An example of a game of perfect information would be one that is called the ultimatum game where one player receives a sum of money and proposes how to divide the sum with the other player. The second player chooses to either accept or reject this proposal. If the second player accepts, the money is split according to the proposal. If the second player rejects, neither player receives any money. In this game, all information is available to all players.

In contrast many real world games involve imperfect information. For example, prisoner dilemma games only make sense if given imperfect information where you are choosing without knowing how the other has chosen.

Information plays an important role in real-world games and it can work as an advantage or disadvantage to the players. When one player knows something that others do not, sometimes the player will wish to conceal this. For example in playing poker, and at other times they will want to reveal it, for example, companies offering guarantees for their products is a display of the information that they have that their product is not going to break down soon, and they want customers to know this information.

SYMMETRY

This reveals also how games can be asymmetrical. Meaning the payoffs to individuals for the different possible actions may not be the same. If the identities of the players can be changed without changing the payoff to the strategies, then a game is symmetric.

Many of the commonly studied 2 × 2 games are symmetric.

Games of coordination are typically symmetrical. Take for example the case of people choosing the sides of the road upon which to drive. In a simplified example, assume that two drivers meet on a narrow dirt road. Both have to swerve in order to avoid a head-on collision. If both execute the same swerving maneuver they will manage to pass each other, but if they choose differing maneuvers they will collide. In the payoff matrix successful passing is represented by a payoff of 10, and a collision by a payoff of 0 and we can see how the payoff to each player are symmetrical.

ZERO-SUM / NON-ZERO-SUM

Games are played over some mutually desired resource, what we are defining as value within that game. For example, countries go to war over territory, businesses compete for market share, creatures for the resources within an ecosystem, political parties for decision making power, athletes for prizes and prestige etc.

In all of these situations, there is some shared conception of what agents value and some interdependence in how that value is distributed out depending on the actions of the agents.

But the question is whether the total value distributed out to all agents remains constant irrespective of their actions or can it grow or decrease depending on their capacity to cooperate.

Constant-sum games are games in which the sum of the players’ payoffs sum to the same number. These games are games of pure competition of the type “my gain is your loss”.

Zero-sum games are a special case of constant-sum games, in which choices by players can neither increase nor decrease the available resources. In zero-sum games, the total benefit to all players in the game, for every combination of strategies, always adds to zero.

One can see this in the game paper, rock, scissors or in most sporting events.

In zero-sum games, the relationship between the agents’ payoffs are negatively correlated, which is called negative interdependence, meaning individuals can only achieve their goal via the failure of another agent and this creates an attractor towards competition, there is no incentive to cooperate and thus these games are called strictly competitive as competition is always the best strategy.

Non-constant games or non-zero sum games are those in which the total value to be distributed can increase or decrease depending on the degree of cooperation between actors.

For example, through the members of a business working together they can create more value than working separately, thus the whole payoff gets bigger. Equally, the total payoff may get smaller through conflict, like in an arms race between two gangs in a city.

In non-zero sum games, the outcome for agents is positively correlated, if one gets more the other will too if one gets less the other will too. With non-zero sum games, we can get positive interdependence between the agents, meaning members of a group come to share common goals and perceive that working together is individually and collectively beneficial, and success depends on the participation of all the members leading to cooperation.

COOPERATIVE / NON-COOPERATIVE

A cooperative game is one in which there can be cooperation between the players and they have the same cost.

So cooperative games are an example of non-zero sum games. This is because in cooperative games, either every player wins or loses.

Cooperation may be achieved through a number of different possibilities. It may be built into the dynamics of the game as would be the case with a positive-sum game where payoffs are positively correlated. In such a case the innate structure of the game creates an attractor towards cooperation because it is both in the interest of the individuals and the whole organization.

A good example of this are the mutually beneficial gains from trade in goods and services between nations. If businesses or countries can find terms of trade in which both parties benefit then specialization and trade can lead to an overall improvement in the economic welfare of both countries, with both sides seeing it as in their interest to cooperate in this organization, because of the extra value that is being generated.

Equally, cooperation may be achieved by external enforcement by some authoritative third party such as governments and contract law. Where we cooperate in a transaction because the third party is ensuring that it is in our interests to do so by creating punishments or rewards.

Likewise, cooperation may be achieved through peer-to-peer interaction and feedback mechanisms as will talk about in future videos.

A non-cooperative game is one where an element of competition exists and there are limited mechanisms for creating institutions for cooperation. This may be because of the inherent nature of the game we are playing. That is to say, it is a zero-sum game which is strictly competitive and thus cooperation will add no value.

Noncooperation may be a function of isolation, lack of communication and interaction with which to build up the trust that enables cooperation.

We see this within modern societies, as these societies have grown in size they have transited from communal cooperative systems based on the frequent interaction of members to requiring formal third parties to ensure cooperation because of the anonymity and lack of interaction between members of large societies.

Lastly, there may simply be a lack of formal institutions to support cooperation between members. An example of this might be what we call a failed state where the government’s authority is insufficiently strong to impose sanctions and thus can not work as the supporting institutional framework for cooperation.

SUMMARY

In this video we have looked at some of the basic features to games, we talked about the two basic forms for representation, that of the normal form in a matrix model and that of the extensive form as a tree graph that unfolds over time.

We talked about the important role of information, where games may be defined as having imperfect or perfect information and how agents may use information to their advantage.

We talked about symmetrical and asymmetrical payoffs in games. We briefly looked at zero sum games and non-zero sum games where the payoffs can get larger given cooperation.

Finally we talked about the distinction between a cooperative and non-cooperative game and some of the factors that create these different types of games which we will be discussing further throughout the course.

GAME THEORY OVERVIEW

We live in a world that exhibits extraordinary levels of order and organization on all levels from the smallest molecules, to human social organizations to the entire universe. We might say that it is the job of the enterprise of science to try and understand this extraordinary order and organization that we see in the world around us. And in many ways, we have been very successful in the past few hundred years in making progress in this project. We understand the workings of the atom, the structure of DNA, we understand the origins of the universe, how galaxies form and the precise elliptical orbit of the Earth around the Sun.

But what all these systems that we have been so good at describing and predicting the behavior of have in common is that they are inert. That is, they do not have any degree of autonomous adaptive capacity.

Here we can make a fundamental distinction between those systems that are composed of inert elements and those that are composed of adaptive elements.

Because these inert systems that are studied in physics and chemistry do not have adaptive capacity we can describe them through a single global rule. We can write equations about how elements will react when combined or how the solar system will change over time according to a set of differential equations in a deterministic fashion.

Unfortunately, this approach does not work when dealing with systems that are composed of adaptive elements that are non-deterministic in their behavior.

Adaptation gives the elements in the system the capacity to respond in different ways depending on the local information they receive. And the overall organization that forms is in fact not a product of a global rule, like we might have for a chemical reaction. Instead, the result is a product of how these adaptive agents respond to each other.

With these adaptive systems, the overall makeup of the organization is not necessarily defined by a top-down rule, but may emerge out of how the elements adapt and respond to each other locally.

There is no algebraic or differential equation to describe how international politics works, why families fall apart. or the success of a business within a market. The overall workings of these adaptive systems is an emergent phenomenon of local rules and interdependencies.

GAME THEORY

And it is these systems composed of adaptive agents that are interdependent that game theory tries to understand and model.

A game is a system wherein adaptive agents are interdependent in affecting each other and the overall outcome.

Game theory is the mathematical modeling of such systems.

These adaptive systems are pervasive in our world, from cities and traffic to economies, financial markets, social networks, ecosystems, politics, and business.

The central ingredients of these systems is that of agents and interdependency. Without either of these elements, we don’t have a game.

If the elements did not have agency and the capacity for adaptation they would have no choices and we would have a deterministic system.

Likewise, if they were not interdependent then they would not form some combined organization and we would then study them in isolation in which case likewise we would not have a game.

AGENTS

Games are formed out of the interdependencies between adaptive agents.

So what is an adaptive agent? An agent is any entity that has what we call agency. Agency is the capacity to make choices based upon information and act upon those choices autonomously to affect the state of their environment.

Examples of agents include social agents, such as individual human beings, businesses, governments, etc. They may be biological agents such as bacteria, plants, or mammals. They may also be technologies such as robots or algorithms of various kind.

All adaptive systems regulate some process and they are designed to maintain and develop their structure and functioning. For example, plants process light and other nutrients and their adaptive capacity enables them to alter their state so as to intercept more of those resources. The same is true for bacteria and animals, as well as for a basketball team or a business. They all have some conception of value that represents whatever is the resource that they require, whether that is sunlight, fuel, food, money etc.

This creates what we can call a value system. That is to say, whatever structure or process they are trying to develop forms the basis for their conception of value and they use their agency to act and make choices in the world to improve their status with respect to whatever it is they value.

As we can see this concept of value is highly abstract. And as we will discuss in a future module this value system can be very simple or very complex but it forms the foundations to what we are dealing with when talking about adaptive agents and games.

You can’t model a game without understanding what the agents value and the better you understand what they really value and incorporate it into the model the better the model will be.

Thus agents can also be defined by what we call goal oriented behavior. They have some model as to what they value and they take actions to affect their environment in order to achieve more of whatever is defined as value.

GAMES

In game theory, a game is any context within which adaptive agents interact and in so doing become interdependent.

Interdependence means that the values associated with some property of one element become correlated with those of another. In this context, it means that the goal attainment of one agent becomes correlated with the others.

The value or payoff to one agent in the interaction is associated with that of the others.

This gives us a game. Wherein agents have a value system, they can make choices and take actions that affect others and the outcome of those interactions will have a certain payoff for all the agents involved.

A game then being a very abstract model can be applied to many circumstances of interest to researchers. And it has become a mainstream tool within the social sciences of economics, political science and sociology but also in biology and computer science.

The trade negotiations between two nations can be modeled as a game. The interaction of businesses within a market is a game. The different strategies adopted by creatures in an ecosystem can be seen as a game. The interaction between a seller and buyer as they haggle over the price of an item is a form of game. The provision of public goods and the formation of organizations can be seen as games. Likewise, the routing of internet traffic and the interaction between financial algorithms are games.

To quickly take a simple concrete example of a game, let’s think about the current situation with respect to international politics and climate change. In this game, we have all of the world’s countries and all countries will benefit from a stable climate. But it requires them to cooperate and all pay the price of reducing emissions in order to achieve this.

Although this cooperative outcome would be best for all, it is in fact in the interest of any nation state to defect on their commitments as then they would get the benefit of others reducing their pollution without having to pay the cost of reducing their own emissions.

Because in this game it is in the private interests of each to defect, in the absence of some overall coordination mechanism the best strategy for an agent to adopt given only their own cost-benefit analysis, is to defect and thus all will defect and we get the worst outcome for the overall system.

COOPERATION

This game is called the prisoner’s dilemma and it is the classical example given of a game, because it captures in very simplified terms the core dynamic, between cooperation and competition, that is at the heart of almost all situations of interdependence between adaptive agents.

In the interdependency between agents there comes to form two different levels to the system: the macro-level, wherein they are all combined and have to work cooperatively to achieve an overall successful outcome, and the micro-level, wherein we have individual agents pursuing their own agendas according to their own cost-benefit analysis.

It is precisely because the rules and dynamics that govern the whole and those that govern the parts are not aligned that we get this core constraint between cooperation and competition.

This is what is called the social dilemma and it can be stated very simply as what is rational for the individual is irrational for the whole.

If you do what is rational according to the rules of the macro-level to achieve cooperation then you will be operating in a way that is irrational to the rules of the micro-level and vice versa.

If either of these dimensions to the system was removed then we would not have this core constraint. If the agents were not interdependent within the whole organization then there would be no macro-level dynamic and the set of parts would be simply governed by the rules of the agents locally.

Equally, if each agent always acted in the interests of the whole without interest for their own cost-benefit analysis, then again we could do away with the rules governing the micro-level and we would simply have one set of rules governing the whole thus there would be no core dynamic of interest, things would be very simple and straightforward. The complexity arises out of the interaction between these two different rule sets and trying to resolve it by aligning the interests of the individuals with those of the whole.

SUMMARY

So we have outlined what game theory is, talking about it as the study of situations of interdependence between adaptive agents and how these interdependencies create the core dynamic of cooperation and competition that is of central interest to many. In the coming videos in this section, we will talk about the different elements involved in games and the different types of games we might encounter.

PREFACE

As we watch the news each day, many of us ask ourselves why people can’t cooperate, work together for economic prosperity and security for all, against war? Why can’t we come together against the degradation of our environment?

But in strong contrast to this, the central question in the study of human evolution is why humans are so extraordinary cooperative as compared with many other creatures. In most primate groups, competition is the norm, but humans form vast complex systems of cooperation.

Humans live out their lives in societies, and the outcomes of those social systems and our individual lives is largely a function of the nature of our interaction with others. A central question of interest across the social sciences, economics, and management is this question of how people interact with each other and the structures of cooperation and conflict that emerge out of these.

Of course, social interaction is a very complex phenomenon. We see people form friendships, trading partners, romantic partnerships, business compete in markets, countries go to war, the list of types of interaction between actors is almost endless.

For thousands of years, we have searched for the answers to why humans cooperate or enter into conflict by looking at the nature of the individuals themselves. But there is another way of posing this question, where we look at the structure of the system wherein agents interact, and ask how does the innate structure of that system create the emergent outcomes?

The study of these systems is called game theory. Game theory is the formal study of situations of interdependence between adaptive agents and the dynamics of cooperation and competition that emerge out of this. These agents may be individual people, groups, social organizations, but they may also be biological creatures, they may be technologies.

The concepts of game theory provide a language to formulate, structure, analyze, and understand strategic interactions between agents of all kind.

Since its advent during the mid 20th-century, game theory has become a mainstream tool for researchers in many areas most notably, economics, management studies, psychology, political science, anthropology, computer science and biology. However, the limitations of classical game theory that developed during the mid 20th century are today well known.

Thus, in this course, we will introduce you to the basics of classical game theory while making explicit the limitations of such models. We will build upon this basic understanding by then introducing you to new developments within the field, such as evolutionary game theory and network game theory that try to expand this core framework.

In the first section, we will take an overview of Game Theory. We will introduce you to the models for representing games, the different elements involved in a game and the various factors that affect the nature and structure of a game being played.

In the second section, we look at Non-cooperative Games. Here you will be introduced to the classical tools of game theory used for studying competitive strategic interaction based around the idea of Nash equilibrium.

We will illustrate the dynamics of such interactions and various formal rules for solving non-cooperative games.

In the third section, we turn our attention to the theme of Cooperation.

We start out with a general discourse on the nature of social cooperation before going on to explore these ideas within a number of popular models, such as the social dilemma, tragedy of the commons, and public goods games. Finally, talking about ways for solving social dilemmas through enabling cooperative structures.

The last section of the course deals with how games play out over time as we look at Evolutionary Game Theory. Here we talk about how game theory has been generalized to whole populations of agents interacting over time through an evolutionary process, to create a constantly changing dynamic as structures of cooperation rise and fall.

Finally, in this section we will talk about the new area of Network Game Theory, that helps to model how games take place within some context that can be understood as a network of interdependencies.

This book is a gentle introduction to game theory and it should be accessible to all. Unlike a more traditional course in game theory, the aim of this book will not be on the formalities of classical game theory and solving for Nash equilibrium, but instead using this modeling framework as a tool for reasoning about the real world dynamics of cooperation and competition.