Author: Linda

Within our complex and messy world, we are often faced with the existence of suboptimal realities that seemingly makes no sense.  This article attempts to draw upon Game Theory to provide some theoretical insight into why these realities come to be, and from a simplified model, extrapolate what could be done to change the status quo.

It starts off by defining a concept introduced in class based on the idea of a coordination game.  The article defines coordination game slightly differently, but in essence the idea is that the optimal strategy OVERALL is for players to cooperate and choose the same option.  This provides a somewhat looser definition from lecture, where the optimal strategy for each player is to coordinate with the other. Therefore, the given article classifies the Prisoner’s Dilemma as a coordination game.

Regardless, the idea of a coordination failure still holds:  when players choose an optimal strategy for themselves and based off limited information, it results in a situation that is not the best overall.

The article proceeds to then relate this concept to many unfortunate situations in the professional world, and in life.  For example, it mentions academic journals charging heavily for readership leading to the throttling of the spread of scientific knowledge, or the nuclear arms race that world superpowers willingly participate in; it even alludes to the doping example provided in lecture.  Any casual reader might find it extremely discouraging, faced with such a bleak picture of the world.

However, while there is a level of cold indifference in this type of analysis, Game Theory in it of itself does provide insight into how we can begin to solve such problems at a society level.  The idea being, that from an outsider’s perspective, we can easily see what the better path to take and if we know what others know, it is easier to generate decisions that benefit everyone.

Thus, the article concludes that through large scale communication and the organization of groups, can collective action be taken to push against conventions that are damaging for everyone.   Pro-active coordination, unsurprisingly when taken from the simplified version of the real world that coordination games seek to model, is the key to finding and establishing better equilibrium against challenging circumstances.

Link – Coordination Problems: What It Takes to Change the World

Unsurprisingly, the spread of epidemics and network analysis go hand in hand but this article in particular caught my attention due to its bold and perhaps even controversial application of graph theory to a morbid question:

How many Americans need to die before every American knows one of the dead? 

Adam Rogers – Death Cuts the Degree of Separation Between You and Covid-19

I thought at first that it was a bit of a silly question, one that we really shouldn’t have to ask. But I decided to I give the article a chance: it was the best lead I had relevant to current events.

At first they took a relatively simple approach to the analysis: Take the number of people a person is likely to know on average.  Find the percentage of one death out of that total and multiply that by the entire population.  This depended very heavily on the definition of “number of people a person knows on average” and estimates ranged from 546, 000 all the way to 1.6 million people.

Obviously, that isn’t entirely accurate, but it’s the caveats they introduce afterwards that present interesting subtleties about networks that apply to all sorts of analyses about them.  For instance, the way disease spreads isn’t uniform or random.  In class we’ve already learned that the structure of the graph in it of itself isn’t even close to the inherently random processes that generate a graph like G_np, so it’s not hard to consider that the processes that spread information or illness would depend on the outside context that nodes live in.  Certain cohorts or clusters are far more susceptible to COVID-19 just based on the foci they are involved in or who they are (i.e. older adults or the elderly).  Furthermore, the mutual interaction of clustering and homophily lead to a phenomenon termed in the article as overdispersion, which is a statistical term for greater variance than expected for a particular variable.  This causes the number of people that need to die to go up, because even as the deaths spike, certain communities may remain isolated from the direct effects of the pandemic.

Besides the context, the structure of networks plays a role as well, causing the number of people that need to die to be lower than we expect given the simple analysis above.   Particularly it is the uneven distribution of degree, analogous to the funneling described in Milgram’s experiment related to the fact that certain people have more connections than others.  In this article, it was termed the friendship paradox the idea that your friends probably have more friends than you.  The unfortunate conclusion is however, that people who have a certain “centrality” in the network also have a greater risk of getting sick – and because they know more people, and such a death would mean that the less people overall would need to die before everyone knew someone personally.

Finally however, they bring up that even without all the caveats and extra reasoning about the context of these graphs the theoretical problem we are fundamentally trying to solve is NP-complete.  The problem can be called the Minimum Dominating Set and can be framed as:

“For a given graph, what is the minimum set of nodes such that every node in the graph has at least one neighbor in that set?” 

It is distinct from the “Vertex Cover” problem (which was covered in the CSCC63 Computational Complexity course) where we ask:

“For a given graph, what is the minimum set of nodes such that every edge in the graph has at least one endpoint in that set?” 

Regardless, both are NP complete, as prove by Richard Karp in 1972 (if you’re interested, you can try to prove this using a linear reduction from the set-cover problem, see the the section on computational complexity).  This is to say, of course, that even the simplest version of the problem we proposed cannot be solved in polynomial time, only approximated.

Which perhaps brings me back to my initial thought about this topic.  While its analysis may be intellectually stimulating, and provide an opportunity to ponder tricky problems, it really isn’t the reason why such a question is asked in the first place.  Because in reality, even if we were able to answer such a question efficiently and present the answer to people, it wouldn’t change the very psychological problem that lead to all of this thinking in the first place – that people choose not to listen to the facts and choose not care when it doesn’t affect them personally.  Perhaps, it is not the sheer number of connections, but the weight those connections hold that requires a collective understanding.

A leap of faith, as the author put it.

Or put in other terms, a change of heart.

Source: https://www.wired.com/story/death-cuts-the-degree-of-separation-between-you-and-covid-19/