facebook Understanding Game Theory | Russian Math Tutors

Write For Us

We are constantly looking for writers and contributors to help us create great content for our blog visitors.

Fun Tasks

Understanding Game Theory and Conflicts of Interest in Hall’s Marriage Theorem

2023-11-01 |    0

Flower Girl

Would you like to book private or group online lessons?

Private Lessons | Group Lessons
In our study of game theory, we've learned that not all competitors are out to harm us. Sometimes, people can be happy without making others unhappy. When this happens, we call these games 'non-antagonistic.' Think of Odysseus sailing through a storm. While we might see the storm as an enemy or think that Poseidon wants to harm Odysseus, in reality, the storm has no intention of harming the sailor. If something goes wrong, it's often the captain's fault for making a bad decision (like the Titanic's captain not seeing the iceberg).


This idea also applies to how people interact with nature. We use the term 'game with nature' in game theory when our 'opponent' doesn't want to harm us. Nature can be our opponent, like the sea, insects, animals, air, or outer space. It can also be others, like classmates, friends, parents, or business partners. Think of big companies like Google or Amazon. They have thousands of employees who work together every day. If these people were always fighting with each other, they'd waste their energy on pointless conflicts instead of helping the company grow. That's why we try to avoid conflicts in society. Societies with many conflicts tend to have problems with science, medicine, and education. So, before you argue with a friend over $5, think about whether you can work together to make $500. We call this the 'system effect,' and it's a big part of what makes large companies successful. In games, when a group of players comes together, we call it a 'coalition.'


A great example of how coalitions work is shown in the movie 'A Beautiful Mind,' which tells the story of John Nash, a famous mathematician and game theorist. Nash and his friends are at a dance and see a group of girls. At first, they think about asking the same girl to dance, but Nash thinks it's not the best strategy. Many math problems are inspired by the relationships between men and women, like the classic problem of a princess and her suitors.


Here's another problem that's a lot like that one. We have young men, John (J), Alex (A), Peter (P), and young women, Mary (M), Sophia (S), and Victoria (V). John and Alex both like Mary and Sophia, and Peter likes Mary and Victoria. We can draw the situation like this:




Question: Can all the young men marry the women they like? Here's one way to do it (but there's another solution; try to find it):


Now, let's say there's another young man, Robert (R), who also likes Sophia:


Can the young men all marry the women they like this time? No, they can't! The reason is simple. There's a group of three young men (John, Alex, and Robert) who all like two girls (Mary and Sophia). So, no matter how we arrange the marriages, one of these three guys won't get the girl he wants.


The idea we used here is called the 'pigeonhole principle.' In this case, we found a group of three guys where the pigeonhole principle applies because they like fewer than three girls. But what if the pigeonhole principle always worked for all our groups of guys? In other words, every group of guys, no matter how many of them there are (N), likes at least N girls in total. In that case, we can ensure all the guys get the girls they like. This is called Hall's Marriage Theorem. It tells us when to avoid conflicts of interest among competitors by finding matches that work.


Learn more about Hall's Marriage Theorem and many other mathematical concepts in our classes on Graph Theory and Probability.


Flower Girl

Would you like to book private or group online lessons?

Private Lessons | Group Lessons