Author: Yufei Cui

It is well known that after struggling through first year at UofT, students are then granted admission to their preferred Program of Study (POSt) only if they pass certain criterion.

At UTSG, the top X% of students are admitted to the CS POSt. This means the students are directly competing with each other for the limited spots in the program. At UTSC, students with a cumulative GPA greater than 3.0 (~ 75%) will be admitted to the POSt. Comparatively, this means that students at UTSC gets admitted into the CS POSt independently of each other.

Let us first consider a fictitious simple model that can represent the UTSG CS POSt admission game. Suppose that there’s only one space available for the CS program and Alice, Bob, and Charlie are the last contenders to be considered. If each of the three of them decide to study, then they each have a 33.3% chance of making it to the program. However, they could also choose to sabotage another student. Suppose that Alice and Bob are enemies, if Alice decides to sabotage Bob, then Bob’s admission likelihood would decrease to 10%, and Alice’s likelihood raises to 40% (this implies Charlie’s likelihood gets raised to 50% and it makes sense since Alice didn’t spend time to study for her exams!). If Alice and Bob both decide to sabotage each other, then they will split the 50% that’s left over (Charlie again has 50% chance) which gives them 25% each.

UTSG POSt Game

	Study	Sabotage
Study	33.3%, 33.3%	10%, 40%
Sabotage	40%, 10%	25%, 25%

Given the set up, it is easy to apply the game theory analysis to this game. As a student, you can either choose to study or sabotage student such that you gain some advantage over the other. Here it is clear that regardless of what the other student does, sabotaging will yield a higher score. Thus, sabotaging is actually the dominant strategy for both Alice and Bob. If we suppose that Alice and Bob are logical enemies and they follow the rules of game theory, then they would adopt to their dominant strategy. This is clearly a ridiculous outcome, as it would make more sense for students to sabotage each other than to study!

Now let us consider the following fictitious UTSC CS POSt admission game. Where the admission likelihood of any student is independent of other students.

UTSC POSt Game

	Study	Sabotage
Study	80%, 80%	50%, 60%
Sabotage	60%, 50%	30%, 30%

The difference at UTSC is that sabotaging other does not increase your chance of being admitted to the POSt. On the contrary, since you’re not studying, then you actually lower your chance. Again, applying game theory analysis to this game, the dominant strategy for both Alice and Bob would be to study. This should be the expected behavior of students at a University.

To summarize, I argue that the UTSC CS POSt method is one that is better than UTSG’s in terms of what is the expected outcome from their respective students. On one hand, the UTSG POSt creates a “zero-sum thinking” environment where students think that in order to achieve success, others must suffer. While at UTSC, students will more likely to work, study, and help each other to improve their own chances of getting accepted, and during that process also elevate their peers.

Resources:

https://en.wikipedia.org/wiki/Zero-sum_game
https://en.wikipedia.org/wiki/Zero-sum_thinking
https://journals.sagepub.com/doi/10.1177/0022022115572226
https://atrium.lib.uoguelph.ca/xmlui/handle/10214/10034

Suppose a wildfire starts in a forest (like in the Amazon rainforest) and you have a limited amount of resources to fight the fire as it spreads throughout the forest. What is the best strategy you should deploy so that you can maximize the number of trees you save before the fire is distinguished?

This is the so-called Fire Fighter Problem, it has been discovered since 1995 and is still studied and experimented till today. It’s easy to see that we can transform the description of this problem into a network where

• nodes = trees in the forest
• edges = exists if a tree is next to another
• S = the sources of the fire
• Strategy = the way in which “firefighters” are deployed to fight the fire

and the goal would be to save the largest set of trees in the forest.

A keen student might attempt to solve this optimization problem with techniques we learn(ed) in CSCB63 and CSCC73. However, it turns out that the Fire Fighter Problem is a NP-hard problem, which means that we have not yet figured out an efficient solution that can deterministically solve every instance of this problem (without proving P=NP first!).

In my opinion, this result actually have a huge significance in our lives. If we refer to our classmate Sol and Jayden‘s blog posts — Sol investigated on the disease spreading network and Jayden on the computer virus network. Both of their problems can be seen as analogous to the Fire Fighter Problem. This implies that it is mathematically hard to come up with a very efficient algorithm to vaccinate people in a network or come up with a protocol to prevent a large network (maybe a SCC in the web) from being infected by a virus or malware.

From Netflix’s “Inside Bill’s Brain” documentary, Bill Gates talked about how it was extremely difficult to exterminate Polio in Africa as figuring out an efficient vaccination strategy was hard. Although this is unfortunate, it is not surprising from our insight of the Fire Fighter Problem and further confirms our intuition on this family of problems.

In summary, we see how we can describe a real world problem into one that involves networks, and by understanding from mathematical results, we can infer how difficult it is to implement a strategy in a real world system.

References:

• https://www.mathstat.dal.ca/~cduffy/DuffyMSc.pdf
• https://slideplayer.com/slide/4290990/
• https://www.gatesfoundation.org/what-we-do/global-development/polio