Since last month (and my blog post about Hong Kong), the Hong Kong protests have seen a significant increase in the violent tactics from police and protesters. In the past week, the Hong Kong police force tried to siege Hong Kong universities, which is among the top universities of the world; they have shown a bigger willingness to fire real bullets at their citizens; and protesters have resorted to climbing sewers to escape selective prosecution. So, five months in of protests, should the people still be hopeful? By applying the theoretical model of cascades, I argue from a game theory and social networks point of view that the people will not back down from their demands.
One of the protests slogan in the ongoing protests is “Don’t condemn, don’t cut ties” (in Cantonese: 不譴責、不割席). The reason behind this is the more people involved in the movement, the more effective it is. We can use game theory to model this:
Be part of movement
Condemn the protests
Be part of movement
a, a
0,0
Condemn the protests
0,0
b, b
In the above model, the variable a is some positive outcome, while the variable b is some negative outcome. It is clear that if both is part of the movement, there is a greater chance that change can be brought to the city. Meanwhile, if one is part of the movement and one condemns it, it does not help the cause.
Since July, the percentage of people agreeing with the demands have increased drastically. (Left: Independent inquiry into police conduct; Middle: The Chief Executive has the resign; Right: True universal suffrage)
Relating back to the statistics currently, it is clear that the support for the movement is still high – especially people who are under 25. We can explain this through the model of cascades with q>1/2. (We can easily make this assumption. Through votes casted in the last Legislative Council election, pro-democracy lawmakers have won a majority of votes). The cascade, especially in the younger generation can be justified as school is one of the places where influence can be spread very quickly. If n of your friends are in support of the protests – it might be in your interest to also be in support of it.
By this theory, it is expected that the popularity of the demands will continue to increase. If a significant amount of the population is in support, the government will have no choice but to fulfil them – just like a real democracy.
There exists a genre of video games that picks at the brain’s ability to make critical decisions and promotes analytical abilities. Can you guess what it is? In my opinion, nothing makes players “think” more than strategy games. Strategy games, especially ones that utilize entities such as “resources” are an extreme catalyst for players to develop their ability to devise strategies and predict opposing strategies. This is similar to the concept of Game Theory.
This post in specific, I would like to dive deeper into a specific sub-genre that might not be too popular amongst the masses: rogue-like survival games, or more specifically Escape from Tarkov. EFT is a realistic first-person-shooter survival game that encompasses a psudo-rogue-like element to the game. For those who do not know what rogue like means: it is when your character dies, they die forever. What this entails is that your character, and everything they held in possession, is lost forever, which gets us to the main topic: the mentality of players and how they handle gear fear – the fear of losing their gear. EFT, in short, is a game where you enter zones called “raids”, and loot goods around the zone and extract. Should you succeed, you gain everything you looted as payoff, but as mentioned earlier, if you fail and die, everything you picked up as well as what you brought in initially is lost.
Chance to Win
This brings me to the first Game Theory application: What is the best way to ensure victory? For those who are familiar with these types of games, common first thoughts would be to “bring in the best equipment (better guns, better armour) to reduce the chances of losing” which could be represented as such: (Note: EFT is not a 2 player game, but for the sake of this current illustration, it will be dumbed down to 2 players)
As seen in the chart, if these 2 players encounter each other in the raid, the difference in gear can dictate who comes out on top. However what about the profit?
Profit gained
Profit in this case would be calculated by what the winning player gets out of defeating the other. As seen above, if neither player is geared, no one wins anything regardless of who the winner is, where as if a player is not geared and defeats a geared player, their profit would be all the equipment previously owned by the other player. Meanwhile if both players are geared, they would be require to spend some of their resources in order to gain more resources, simplified to a trade off of 50/50. (In case this point is unclear, both players need to spend bullets, and risk damaging their armour, both are the resources players invested in, in order to gain the other’s (better? equally damaged? worse?) equipment.
Taking into account both tables, nash equilibrium exists (U ,L) and more complicatedly (D,R). Since if player 1 decides to wear no gear, Player 2 might consider wearing full gear, for a 99% win chance, however if they win, they gain nothing and in turn actually risks a 1% chance to lose everything. So with the mentality to reduce LOSS, both players will opt to enter raids with no gear. However, in order to gain a profit, with the mentality to reduce RISK, both players will opt to enter raids with full gear.
This interesting balance between Risk and Loss Aversion, is what make Escape From Tarkov a mentally suspensful game that keeps players engrossed and engaged unlike any other game ive seen. There are a bunch of other factors in EFT that can be analysed by Game Theory to which I invite you, to explore and analyse to the best the game has to offer.
Game theory, as we have been studying, is a great way to help you choose the best options when playing any sort of game that fits under the conditions of game theory. However, how could we teach AI this concept in order to help AI understand games better?
Developers have already worked with implementing game theory into a specific type of game AI called “GANs”. These are AI setups that consist of two nerual networks: a generator and a discriminator. The generator creates random game states, and then the discriminator decides whether or not if it could be true.
Generally, these AIs use what is called a “neural network”. These are AIs that develop themselves by mimicking human evolution. You define a reward, as we would as game theory specifies for any given game, and let it go at it. It will compare the reward it achieved between two iterations, and discard the one that scored lower. Using this and giving it plenty of time, it will learn how to play games!
By setting these two neural network setups in a GAN to compete with each other, they will eventually through time end up finding a Nash Equilibrium between each other after a while of competition.
There is a certain AI program that uses this, called Libratus, which was developed to play poker. Libratus managed to defeat several of the top poker players by using game theory!
Furthermore, it is being considered to take these kinds of AI to apply game theory and neural networks to the real world. Although, this could be disastrous if the AI is poor. We must make the utmost caution to make the best AI possible if we are to take this further into the real world!
A neural network learning to play “Mario”
AI is masterful when we teach concepts to it correctly. By teaching it game theory correctly, it is scary how good at games AI can become.
Machine learning is being used in countless different fields for a variety of different purposes. In order to develop the necessary machine learning models for these applications researches need to gather large amounts of data to train and test the model on. As with any other field, there will be malicious attackers who wish to compromise the model. The attacks where the malicious attacker tries to control a portion of the data used to train the model is called a poisoning attack. These malicious data points may hinder the accuracy of the model and prevent the model from properly analyzing the genuine data.
X-axis shows accuracy of the model Y-axis shows % of data removed by defense
Some researchers have decided to use game theory to model the poisoning attacks and they were able to conclude that there is no pure strategy Nash equilibrium for this problem. As seen in the figure above after around 20% of the data is removed the defense does not improve the accuracy of the model, and instead harms the accuracy as the amount removed increases. Instead they found a mixed strategy Nash equilibrium for the attacker which they better protected the model and maintained a higher accuracy.
Y. Ou and R. Samavi, “Mixed Strategy Game Model Against Data Poisoning Attacks,” 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W), Portland, OR, USA, 2019, pp. 39-43.
Cheating – within the scope of a relationship – is never a pleasant experience for either partner. Generally, the victim is left with a broken heart polluted with feelings of sadness, anger, and disappointment while the cheater is either filled with the guilt of hurting their partner or does not care in the slightest. If it’s generally never a pleasant experience for either side, then why do people cheat in the first place? Today, we are going to take a look into a few reasons as to why people cheat as suggested in an article by Theresa DiDonato and build upon these ideas by taking another approach using game theory to see if there is some sort of “payoff” from being unfaithful to your partner.
a meme about cheating from Twitter
Trust is one of the many components to a stable and healthy relationship, as it “is a hallmark feature of committed romantic relationships and is often (not always) tied to confidence that a partner is both romantically and sexually faithful.” (DiDonato, 8 Reasons People Cheat) It has been mentioned in the article that “infidelity can wreak havoc on a relationship” as it can trigger domestic violence, induce negative emotions, and promote poor mental health. If infidelity brings about this level of negativity for both partners in a relationship, then what makes an individual want to cheat to begin with? DiDonato suggests 8 potential reasons/motives for these individuals (note that this list is not exhaustive):
falling out of love – losing feelings for your partner
for variety – wanting to seek other individuals out of boredom with your current partner
feeling neglected – seeking for attention from another person due to your current partner not providing any
situational forces/being in the heat of the moment – certain circumstances that are out of an individual’s control in a certain setting (e.g., drinking a lot of alcohol and dancing at a club)
boosting self-esteem
anger – wanting to get even with your partner if they did something to wrong you
not feeling committed to your partner
personal needs and wanting intimacy
From the list provided above, we will take a closer look at the second bullet (for variety) and the seventh bullet (anger) and examine their “payoffs” based on what the individuals lose/gain from their actions to see what correlation it has to the mentioned reasons. In the second bullet, the individual’s reason for cheating is due to the fact they are bored with their current partner and want to see what other fish are swimming in the sea. In the seventh bullet, the intent the individual has is to get even with their partner and/or assert their dominance over them.
Building off the second bullet, suppose you have a cheater Mary and her partner Pat. In addition, suppose either partner has the choice of cheating or staying faithful to their partner. Let us also assume that Mary’s intent for cheating is out of boredom while Pat has no intent and has strong feelings for Mary. We would then have the following payoff matrix:
If Mary cheats, it doesn’t matter what Pat does since her intent for cheating is due to boredom; Pat gains nothing from Mary’s actions (other than a broken heart) since he still has feelings for Mary. If Mary stays faithful, it would be in Pat’s best interest to also stay faithful considering his feelings for Mary; Mary gains nothing from staying faithful as she will be stuck with the same partner and be bored out of her mind. From this, we can see that the pure strategy Nash equilibria are (Cheat, Cheat) and (Cheat, Stay Faithful). Building off the seventh bullet, suppose we have the same individuals mentioned above. In this instance, let us assume that Mary’s intent for cheating is due to her anger for something Pat did (suppose Pat cheated). Let us also assume that Pat bears the same intent as Mary. We would then have the following payoff matrix:
If Mary cheats, it would be in Pat’s best interest to also cheat given that they’re both angry with each other. If Pat stayed faithful, the only person winning in this situation is Mary. If Mary and Pat stayed faithful, neither individual would gain anything from it since both still have their pent up anger and neither one can get even or assert dominance. The pure strategy Nash equilibrium in this case is (Cheat, Cheat).
In both cases, we can see how the pure strategy Nash equilibria all involve one partner (or both partners) cheating on each other. If we run through the rest of the bullets under specific assumptions with intents/reasons for the cheater, then we will see how the cheater always benefits from the situation.
From what we’ve found in examining the situations, does this mean you should still cheat on your partner? Absolutely not! We all know how bad cheating is and how it can terribly sever relationships not only between the 2 partners, but between mutual friends in their network. Though the payoff may seem like it would be better to cheat, it would be in your best interest to not do such a thing and ruin your own reputation with people. In the end, we know that cheaters never prosper.
Poker has always been considered the quintessential imperfect-information game – imperfect-information meaning that no one player has full knowledge of the other players’ positions. While we as computer scientists have made great strides in developing AI to play perfect-information games, like chess and checkers, it is only recently that we’ve been able to crack the world of imperfect-information.
In 2017, the DeepStack AI was revealed to the world, boasting the ability to beat professional human players at poker’s most-popular variant: Texas hold’em. More specifically, the AI was designed to play the heads-up no-limit variant of Texas hold’em, which essentially means the game had no cap on pot size and was restricted to 2 players. Interestingly, since the game involves 2 players and imperfect-information, it becomes a prime candidate of being analyzed with game theory.
Game theory can help us, for instance, determine how often we should be value-betting vs. bluffing when we’re on a given range.
Let’s break that terminology down a bit. Texas hold’em poker consists of 4 betting rounds, and the actions you take in each round [check, call, raise, fold] can give away how strong your hand could be. The likely range of hands you could be holding based on these actions is known as your range.
Now consider the bet on the river (after all community card have been revealed) in a situation where you’ve pegged your opponent on a very tight range. At this point, you know for sure whether you have the winning or losing hand – but either one could still let you win the pot. If you have the winning hand, you want to value-bet: raising just enough so that your opponent calls and you win the pot. Contrarily, if you have the losing hand, you want to bluff: raising enough to intimidate your opponent into folding, so you still win the pot.
With all this in mind, consider the following scenario:
The pot is sitting at $100
The river card has just been revealed
The opponent has placed you in some range R
You’ve placed your opponent in a very narrow range
Action starts with you
Here, you have 2 ‘games’ to play out, depending on if you’ve determined you hold the winning or losing hand.
This is the game you play if you have the winning hand.
Player B
Call
Fold
Player A
ValueBet
$200
$100
Fold
$0
$0
This is the game you play if you have the losing hand.
Player B
Call
Fold
Player A
Bluff
-$100
$100
Fold
$0
$0
Note that these games only have 1 payoff value. Only Player A’s payoffs are shown in these tables because Player B is playing an entirely different game – this is due to the fact that Action in poker is sequential, not instantaneous. This means that Player B can, and should, react to Player A’s choice before making their own. Player B only has 1 game to play, shown below:
Player A
VB
Bl
Player B
C
-$100
$200
F
$0
$0
Notice how there is no option for Player A to fold; the game above can be played instantaneously (since B does not know whether A value-betted or bluffed), but if A had folded, B would know and would make $100.
Now, since A cannot control which game they are playing, they have to play in such a manner that they maximize their profits regardless of what B plays. Since B only has a choice when A doesn’t fold, A has to determine a ratio to ValueBet:Bluff (folding when needed to maintain this ratio). We can find this ratio by finding q in the Mixed-Nash Equilibrium in B’s game (as seen in lecture).
It turns out the q = 2/3, meaning that A should value-bet twice as often as they bluff if they want B to be indifferent about their choice. We know B will be indifferent because this all occurs when they believe A is in range R, so they have no other info to work with. We can now find the expected payoff for A: if B chooses to call, then A gets 2/3(200) + 1/3(-100) = $100, and if B chooses to fold, then A gets 2/3(100) + 1/3(100) = $100. Therefore, by using game theory, Player A can guarantee a payoff of $100 in range R.
Obviously, this was a very simple and isolated example, and DeepStack employs many more complicated heuristics to produce its results. But, it is insightful to see how just the basics of game theory can be directly applied to better your poker play. GTO [Game Theory Optimized] poker is a growing trend in the scene, and for good reason. After all – if you can’t beat them, join them.
References
Corrigan, Rory. “How You Should Think About Poker (But Probably Don’t).” Upswing Poker, 8 Dec. 2017.
[2] The stable marriage problem is a problem of how to pair off two groups into stable matches.
In an article made available on-line the 13th of September 2019, titled “Incentives and implementation in marriage markets with externalities,” academics María Haydée Fonseca-Mairena and Matteo Triossi discuss the use of Nash Equilibrium to implement stable correspondences in marriage markets with externalities. As in CSCB36H3, the term “marriage market” refers to markets consisting of two non-empty, distinct, and mutually exclusive sets which need to paired off. Examples include: marriages, dance partners, and medical students and medical schools.
A quick review of CSCB36 material: in marriage market algorithms we assume that all parties are acting rationally, and that rational actions must include preferring any pairing over being on your own. Stable matches are matches that are not blocked by a pair. That is, no pair of participants in the market should prefer to be matched together over their assigned match. In CSCB36 we proved that in marriage markets without externalities, the dominant strategy is to be honest about your preferences and to reach out to members of the other group.
[3] In the stable marriage problem without externalities (where other people’s matches don’t matter to you) the dominant strategy is to be honest about your preferences.
Without externalities, honesty and initiative will secure an optimal match. In their article Fonseca-Mairena and Triossi examine the best strategy in marriage markets with externalities.
We all know that some of the algorithms and examples covered in many of our classes work only for simple or specific requirements that do not often occur organically in the real world. Often, in life, marriage markets include externalities – that is, the pairings effect more people than just the two members who have been matched. Consider the examples above; family members and friends likely care about who your spouse is, in dance competitions each pair is interested in who their competitor’s partner is, medical students are likely concerned not only with the school they are accepted to themselves, but also the school that accepts their friends and classmates. When taking externalities into account the concept of a stable matching changes. In marriage markets with externalities, a stable matching M is blocked by an individual if they prefer being alone to the pair they are assigned to in M. A stable matching can also be blocked by a pair if they prefer any matching in which they are paired together over their assigned matches in M.
Fonseca-Mairena and Triossi prove out that in a marriage market with externalities the honest and initiative-taking dominant strategy applied to marriage markets without externalities no longer works. In their article, Fonseca-Mairena and Triossi further prove that Nash equilibrium can be used to implement stable matches in marriage markets with externalities. As a CSCC46 student, I found this article interesting due to its potential applications. As mentioned above, in class we often learn about algorithms or theories that appear to have limited applications in the real world. With our lectures on game theory especially the examples seemed over-simplified and specific. I felt that it was unlikely you would come across such simple examples in real like where there are often many factors to consider. I understand, of course, that the examples were simplistic because the lectures were only introducing us the game theory, and simple examples made our professor’s points more clear. However, the use of Nash equilibrium to create stable matches in marriage markets with externalities suggests countless real world applications. There are the three examples in the introduction to this blog, but also countless others. Many people, from parents, teachers, managers, to administrators of various levels find themselves attempting to create a set of stable pairings for an activity or event. Fonseca-Mairena and Triossi ‘s article provides proof of a simple method for choosing.
RESOURCES:
[1] Fonseca-Mairena, M. H., & Triossi, M. (2019). Incentives and implementation in marriage markets with externalities. Economics Letters, 185 doi:10.1016/j.econlet.2019.108688
The Cuban Missile Crisis began in October 1962 when the Soviet Union (USSR) started placing missile launchers in their allied country, Cuba. The United States, then led by President John F. Kennedy, feared that this would give the USSR the ability to strike the USA with nuclear weapons with little to no warning to launch a retaliation. During this crisis, the 2 global superpowers negotiated and played likely one of the most dangerous and tense applications of game theory in history.
Following the USA discovery of the USSR installing missiles in Cuba, the game theory situation would have been represented in this manner
If the US would have ignored the situation, both powers would be in a neutral standoff with US having missiles in Turkey pointing to the USSR and conversely, the USSR having missiles in Cuba pointing at the US.
If the US chose to escalate the situation by implementing a naval blockade around Cuba to prevent the USSR from sending more materials and finishing construction, the USSR would have had 2 options, back down or continue and find a way to finish installing atomic weapons in Cuba. Had the USSR chosen to continue installing, it would have lead to what we can call the atomic subgame
This is what’s usually referred to as Mutually Assured Destruction (MAD). Both countries assert that as soon as the enemy launches a nuke, they will respond in kind, leading to severe or outright destruction for both countries. We can see that here is a Nash Equilibrium on (-1, -1) and it is in both countries’ best interests to retreat from nuclear war. However, this is not what the US chose to do! Because the US was unwilling to accept a “-1” and allow USSR atomic weapons in Cuba, what the President Kennedy chose to do instead was threatening to use force and attack if the USSR continued to attempt to install weapons in Cuba, ie, a (Gone!, Gone!). This would lead to the game as below
The USSR wasn’t going to back down from Cuba if the USA ignore the threat and the US had already escalated with a naval blockade. We can then see that there is a Nash Equilibrium at (2, -1) and so by the USA choosing to escalate, the best decision from the USSR was to back down. This is what ended up happening as leader Khrushchev of the USSR would announce a full withdrawal from Cuba in the following weeks.
Again, this was only possible because the USA assured that they would have attacked if the USSR maintained weapons in Cuba, otherwise the (Gone, Gone) would have been (-1, -1) instead and the USSR would likely have finished installing weapons and both countries maintained a tense mutually assured destruction standoff
If aliens exist, why haven’t we seen them yet? After all, the universe is vast, and Earth-like planets are abundant. This is the Fermi Paradox, which says that it is a contradiction that while alien life should be plentiful, we have yet to make contact with any of them.
If the universe is so vast, then where are the aliens?
One possible explanation for the Fermi Paradox is the “Dark Forest” theory, which models the vast universe as a “dark forest” and civilizations as “hunters.”
To understand this, the theory requires three axioms to be assumed as true:
Every civilization wants to survive.
Every civilization wants to expand and grow.
Every civilization is either friendly or hostile.
From axiom 1, every civilization would do anything to ensure the survival of their species.
From axiom 2, every civilization advances their technology over time. This also means that civilizations advances their weaponry over time. (A famous example of this is shown in the amazing match cut in the film 2001: A Space Odyssey, shown below.) However, not all species would advance at the same rate, and so some civilizations may be more advanced (and thus powerful) than others.
In the film “2001: A Space Odyssey”, after an ape discovers the use of bones as a weapon, he throws it in the air, which match cuts to a similar scene thousands of years after, to a satellite orbiting Earth, which is holding an atomic bomb.
From axiom 3, every civilization can be categorized as either hostile or friendly. Friendly civilizations would try to form an alliance with other civilizations and join forces in the spirit of collaboration. Hostile civilizations would destroy any civilization it comes across, deeming them as dangers to their own survival.
Suppose civilization A discovers civilization B. Civilization A cannot be sure if Civiliation B is friendly or hostile, but it knows that civilization B has a probability P of being both hostile and more technologically advanced then A. Similarly, if civilization B discovers civilization A, it knows that civilization A has probability Q of being both hostile and more technologically advanced than A.
We can model this situation in a payoff matrix, where either civilization can either destroy or ignore the other.
The payoff matrix for destroying or ignoring other space-faring civilizations.
Since the values of P and Q are unknown for each civilization, the only clear Nash equilibrium here is to (Destroy, Destroy), which means it is better to preemptively destroy rather than risk being destroyed. In essence, the universe is a “dark forest” where every civilization is a hunter trying to keep quiet. If discovered, hunters have only one thing they can do, which is eliminate the others, in order to ensure survival.
The holidays are almost here! There are many things I love about the holidays, but one of them surely is gift-giving. Not everyone feels the same way though. So let’s try to simplify gift giving decisions with some help from game theory. How can we apply what we learned about game theory to gift-giving?
When we buy a gift for someone, it has a cost to us (effort, monetary, or both). And when we receive a gift, we get some enjoyment out of it. This sounds like a game! Let’s consider a pair of friends who are deciding whether or not it’s worth it to get each other a gift. Each friend has two strategies — to buy a gift for their friend, or not.Each friend buys a gift with a cost C, and receives a gift with enjoyment E. Of course, they could also not get a gift for their friend (at no cost), and possibly not receive a gift from their friend (resulting in no enjoyment). We can draw a payoff matrix for this like so.
Friend 2
Give Gift
Not Give Gift
Friend 1
Give Gift
E1 – C1, E2 – C2
-C1, E2
Not Give Gift
E1, -C2
0, 0
Now, let’s assume that E > C (because both friends know what the other likes and they bought the gifts at a discount). You would think that the optimal strategy would be to always want to get each other a gift, but according to this payoff matrix… each friend would be better off with not buying a gift for their friend! Of course, surely you see something wrong about our conclusion. One thing to notice is that not giving a gift can either give us enjoyment (if the other person gives us a gift) or nothing (if the other person doesn’t get us a gift).
However, if we consider this as an iterated game, our strategy has to be different. Because our friend would consider what we did in the previous year when deciding what to do this year. It turns out, that for long-term games, choosing the generous strategy is better than the greedy one outright. This is because gift-givers usually copy whatever their recipient’s response from the previous game. So If I got my friend a gift last year, but they did not give me one… I would not get them one this year! And if I did not get my friend a gift this year, but they got me one, I would try to get them a gift next year (or even immediately). Can you think of other iterated games where we can expect our friend to play our previous strategy (rock paper scissors!)
The optimal strategies for this payoff matrix only work if you spend one Christmas with each other, and never see each other again. It wouldn’t work for someone you would spend multiple holidays with, for years to come. One more thing — if you’re like me, getting a gift for someone in itself is enough to make you happy (I personally enjoy buying gifts for others than receiving one). So it doesn’t matter as much for me if I don’t get something that I like.
If we then consider the joy of giving into our equation, it turns out that buying a gift is always the optimal strategy.
Friend 2
Give Gift
Not Give Gift
Friend 1
Give Gift
J1 + E1 – C1, J2 + E2 – C2
J1 – C1, E2
Not Give Gift
E1, J2 -C2
0, 0
So there you have it! Our payoff matrix is a bit more complicated than usual because we have three variables…
E: the enjoyment you get from receiving a gift.
C: the cost you’ve incurred from buying a gift.
J: the joy you get from giving.
How they compare to one another is totally up to you. In general, if you enjoy gifting (just for the sake of it), then you should probably keep giving. But I know it’s not for everyone! Either way, there are still so many great things about the holidays. Friends, family, and food (I’m sure you can apply game theory to help with many of your holiday decisions)!
