@adlrocha - On the ubiquity of game theory
Everything in life is a game!
|Alfonso de la Rocha||Jan 10|
Like me, you’ve probably heard about game theory a thousand times. But what’s this all about? Up till a few weeks ago, I myself had only a “shallow” knowledge of what game theory was. But this holiday season I had the chance to read a few papers that used and applied game theory, and I started falling in love with this field. The more I read about it, the more impressed I was by its applicability and ubiquity.
The theory behind the game
Game theory is a fascinating branch of mathematics. I know... maths, but it has tons of applications to fields ranging from economics, social sciences and biological sciences, to telecommunications, computer science and, of course, p2p networks. Game theory is based on the study of mathematical models of the strategic interaction between different participants in a system. The outcome of the system is the result of the individual decisions (and behaviors) of the players in the system. These individual player decisions are generally dependent on each other.
A good example of a “game” (which in reality is actually a game) is the game of chess. If you are playing a game of chess with a friend, whether you win or lose will be dependent on the moves you both make throughout the game. Even more, the decisions you make will influence the future decisions of your opponent, and vice-versa. This is the perfect example of a zero-sum game with two players (you and your friend) in which both of you have the same utility function, winning!
Wait a moment, utility-what? Players in a game are considered rational decision-makers, which drive their decisions according to a utility function whose outcome they try to maximize. In a zero-sum game each participant's gain or loss of utility is exactly balanced by the losses or gains of utility of the other participants. So in our chess example we could think of the utility as something like this:
utility(white) = sum(white player pieces) - sum(black player pieces)
utility(black) = sum(black player pieces) sum(white player pieces)
If you play whites, you will try to maximize your utility at the expense of your friends, and your friend playing blacks will try to do the same. All of your decisions will be influenced by these functions. (I know, I know, we could get picky and say that not all pieces are equally important in chess, but we can easily fix this modelling sum(player’s pieces) as a weighted sum of the pieces, where the weight of each piece depends on its importance in the game). With this simple exercise we have “game theoretically” modeled the game of chess, potentially allowing us to make more informed and “rational” decisions.
Coming back to the formal and mathematical definition of game theory. To be fully defined, a game must specify the following elements: the players of the game, the information and actions available to each player at each decision point, and the payoffs for each outcome (which can be modeled through a utility function). All these elements, along with what is called a solution concept, i.e. a formal rule for predicting how a game will be played, are used to deduce a set of equilibrium strategies for each player such that, when these strategies are employed, no player can profit by unilaterally deviating from their strategy. These equilibrium strategies determine an equilibrium to the game—a stable state in which either one outcome occurs or a set of outcomes occur with known probability.
Don’t be a chicken!
To end this brief introduction on game theory, let’s have a look at other sample game you usually get when learning about game theory: the chicken game. A basic illustration of this game is having two cars on a road, heading directly at one another. Whoever swerves out of the way is deemed a chicken and loses the game (although you kind of get the consequences of none of them swerving 🚑). This game has two players whose behavior can be modelled with the following payoff matrix:
I haven’t introduced it yet, but a payoff matrix is a table in which strategies of one player are listed in rows and those of the other player in columns and the cells show payoffs to each player such that the payoff of the row player is listed first. This is another way of modelling players behavior instead of independently defining the utility function and the possible moves.
If you recall from above, a game finishes when an equilibrium is reached, i.e. a stable state is achieved in which either one outcome occurs or a set of outcomes occur with known probability. The Nash equilibrium in this game is reached with the following strategies: player A continues straight and player B swerves; and player A swerves and player B continues straight. In both scenarios, someone loses but at least someone wins. The Nash equilibrium determines the optimal outcome of a game, when no player has an incentive to deviate from his chosen strategy after considering an opponent's choice. If one of the players sees that the other is swerving the decision is clear, right? (and in case you are wondering, yes, this Nash equilibrium comes from John Nash, the Nobel Prize winner featured in the movie “A Beautiful Mind”).
You loved the chicken game? Another typical game used to teach game theory is the Prisoner's Dilemma. And one last note before we end this introduction, as you may have expected, there are not only zero-sum games. There is a great gamut of game types out there: cooperative/non-cooperative, symmetric/asymmetric, etc. (in case you were wondering).
Game Theory in P2P networks…
I was introduced to game theory through some of the papers I read for my current research which, goes without saying, is related to P2P networks. I’ll try to share a bit more about the specifics of this research in the next few weeks. In the meantime, if you want to start diving deeper into game theory in P2P and distributed system, I highly recommend having a look at some of the papers I’ve read so far (a good way of reading through this list of papers is going from top to bottom):
A Market Protocol for Decentralized Task Allocation: The paper presents a decentralized market protocol for efficiently allocating tasks among agents that are content for scarce resources. Tasks and resources are traded through an auction protocol, which reaches a solution (if one exists) using strictly local knowledge and communication.
Edge-MAP: Auction Markets for Edge Resource Provisioning: The paper considers a scenario where In-Network Computing Providers (INCPs) deploy and lease edge resources while Application Service Providers have the opportunity to rent those resources to meet their application's low latency demands.
Incentive and Service Differentiation in P2P Networks: A Game Theoretic Approach: Authors propose a method for allocating upload bandwidth from one node to different peers based on bids from competing nodes and a perceived "utility score" for each. This solves the free-rider problem in p2p sharing. The solution is fair (more utility to nodes with better reputation scores), churn-tolerant, scalable, Pareto optimal (each node maximizes utility by following the protocol).
On the Efficiency of Sharing Economy Networks: The paper presents a model for a sharing economy network where agents embedded in a graph share their resources. Agents generate a random amount of spare resources that they can exchange with their one-hop neighbors.
Content Pricing in Peer-to-Peer Networks: Proposes a model to obtain "social optimal outcome" among self-interested peers in the production and sharing of content in P2P networks. The paper focuses on tackling the free-riding problem in P2P networks.
Bilateral and Multilateral Exchanges for Peer-Assisted Content Distribution: Presents a formal comparison of peer-to-peer system designs based on bilateral exchange with those that enable multilateral exchange via price-based market mechanisms to match supply and demand.
… and virtually everywhere!
Enough for now! That’s a good bath of game theory knowledge in P2P networks and decentralized systems. But remember that you can find game theoretic models anywhere: in “economics and beyond”, in politics, in biology, in auctions, in negotiations, and in many of our daily basis interactions.
If you are like me, once you are introduced to game theory, you will start trying to model many of your daily observations as games. When asked about his impressive track record, the investor Ray Dalio claims that the key of his success is to treat the economy (and actually everything in life) as a machine, where every action has a consequence. This view of the world already resonated with me when I read Ray Dalio’s “Principles”, but now that I’ve learned a little bit about game theory what I am convinced is that everything in life is not just a machine but a game, and hence can be modeled as such. Can you think of examples of some of your daily interactions that can be modelled as games? Let me know in the comments, but if there is nothing else to add, see you next week!