Author: Yu Xiang Brian Chen

So far in our lectures, our understanding of Nash Equilibrium is the solution(s) which are the best responses to all other rational players, where no one can gain by unilaterally changing their response. This makes sense when we take a look at how game theory is applied to simple games – either rock paper scissors, prisoner’s dilemma, and so on. However, life is often far more complex and nuanced than our simple games can model – there are consequences, costs and requirements associated with each decision, and the outcome must be weighed against these costs. It’s not as simple as a win, or lose, and the cost of choosing different responses must factor into how we evaluate the best response to any situation. It is this belief that drove Basilio Gentile, Dario Paccagnan, Bolutife Ogunsula, and John Lygeros – postdoctoral researchers at ETH Zürich – to develop a new model of equilibriums, which factor in the cost of changing actions, which they call the Inertial Nash Equilibrium.

The authors of the paper published in October 2019, titled “The Nash Equilibrium with Inertia in Population Games” describe that applying an inertial model to population games helps generate new understandings of how actors respond to a set of choices. Specifically, they mention that in real life, a set of consequences – monetary, physical, specific limitations, etc. place a “cost” on response changes by the actors. The key insight that they provide for this is the fact that:

“introducing such costs leads to a larger set of equilibria that is in general not convex, even if the set of Nash equilibria without switching costs is so.”

– pg 1, Gentile et al.

I chose this paper because I think it provides a novel idea regarding how we can model population games using game theory concepts. The paper provides numerous examples on how weighted and inertial models of these games lead to interesting analysis – particularly how ride-sharing (Uber, Lyft) drivers disperse themselves throughout metropolitan cities as a function of other drivers (basic Nash Equilibrium), but also as a function of average ride distance, gas cost, speed limits, and more (inertia, getting from one location to the next for ‘better’ ridership incurs cost to the driver, which plays a factor in their decision to stay put).

I found this article particularly interesting due to how it relates well to the content we cover in class pertaining to games, mixed-responses, pure responses, and Nash Equilibriums. We cover a lot of examples of the applications of Social Information Networks and network analysis, so I figured that sharing some of the applications of augmented Nash equilibriums could be interesting too. By introducing the concept of inertia and cost to moves, actors have additional considerations regarding what a Best response may be, which influences what unilateral moves make sense for them to consider. For interested readers that want to learn more about how this affects various topics, particularly ridesharing, please feel free to read the full paper here: https://arxiv.org/pdf/1910.00220.pdf

Reference:

Basilio, G. (2019, October 1). The Nash Equilibrium with Inertia in Population Games. Retrieved November 6, 2019, from https://arxiv.org/pdf/1910.00220.pdf.

Hey everyone.

Today I want to discuss an interesting new study that came out recently involving the usage of social networks as a tool to group datasets for machine learning models. A paper named The Power of Communities: A Text Classification Model with Automated Labeling Process Using Network Community Detection published by Minjun Kim and Hiroki Sayama on September 25^th, 2019 highlights a useful application of network logic and analysis as it relates to training machine learning text classification models.

If anyone has worked in data science before, you’ll understand the enormous amount of time that is spent on ETL – extract, transform, and load. On top of that, the data needs to be labelled and feature engineered to be able to extract useful insights from it. These two researchers describe how supervised and semi-supervised data are often associated with pre-defined keywords or data which impacts classification. The other clustering algorithms, such as k-means relies biases towards words which repeatedly appear in different contexts, biasing the model and introducing unnecessary ambiguity. The paper explains Kim and Sayama’s methods on how to apply a network community detection algorithm in grouping the preprocessed sentences into different communities and trying to extract insights from that.

Particularly interesting, is that the method for network detection in their paper is the Louvain modularity algorithm for network community detection. This algorithm is based on evaluating density of network links. This relates well to our class discussions on strong and weak ties, as the Louvain algorithm measures modularity as a value between (-1, 1) of the density of links inside communities compared to links between communities. This Louvain method actually relates to the Girvan-Newman algorithm as it was based on that algorithm, instead introducing an aspect of heuristic analysis and local optimization on top of the original algorithm.

I found this topic interesting because it showcases the various applications of network theory. By vectorizing sentences, we can discern mathematical properties that relate sentences semantically with each other and draw out communities without using natural language processing. This application is especially interesting as it shows a concrete application of community detection as we saw in class, and how it relates to cutting-edge modern academia research. For anyone interested, I have included a diagram of the communities as detected in the paper by Kim and Sayama below.

Citation:

Kim, M., & Sayama, H. (2019, September 25). The Power of Communities: A Text Classification Model with Automated Labeling Process Using Network Community Detection. Retrieved September 30, 2019,  from https://arxiv.org/abs/1909.11706v1.

Needham, M. (n.d.). 6.1. The Louvain algorithm. Retrieved September 30, 2019, from        https://neo4j.com/docs/graph-algorithms/current/algorithms/louvain/.