Categories
Uncategorized

Prisoner’s Dilemma in the Virtual world

                In class, the prisoner’s dilemma was brought up to get an idea of how dominant strategy works. The prisoner’s dilemma has been shown to pop up in the real world, for example in arm races between countries and the overfishing problem; it’s easy to see why even though there is an optimal solution for both parties, the net result is one where both parties do worse. However, this issue is not just isolated in reality and I realized that similar social dilemma often arises in video games, specifically in multiplayer games.

                The main reasons why many people play video games is to have fun, for the competition, or a little bit of both. However, even if you enjoy playing a game for fun rather than for competition, more often than not you will find winning much more enjoyable than losing. In many games, the most fun way to play will not be the most reliable to obtain a victory. This leads players to a dilemma in which they have to decide which strategy to pick that will counter the strategy picked by the opposing team. While competitive strategy can still be just as enjoyable as non-competitive strategies, there are times in games where the best strategy does not result in a fun time.

                Online multiplayer game developers have the job of having to constantly patch a game even if there are no visible bugs. This is due to the fact that a multiplayer game that stays consistent and unchanged will grow stale and slowly lose its player base. To remedy this problem, developers will add new content to the game and make small adjustments that can change the meta in small or big ways. Unfortunately, sometimes the changes in the meta of the game are big and result in a less fun meta whether or not the developer intended for this. For example, “in the early days of StarCraft, a strategy called “Zerg rushing” emerged where at the beginning of the match players would quickly build lots of cheap Zerg units to overwhelm opponents before defenses could be constructed” (Madigan 2010). Before developer patches, this was the dominant and most used strategy of the game, even if it was not fun to play as or to play against. The prisoner dilemma perfectly explains why players kept using this strategy even though it was not every enjoyable.

Example of a Zerg rush
Zerg rush pay off matrix

From the matrix above, one can see why Zerg rushing became so common. The dominant strategy for both sides is to Zerg rush and is a strategy that is strictly better than all other options, regardless of what other players do. While a game where neither player Zerg rushes would be ideal, if one player chooses not to Zerg rush, the other player will have more incentive to Zerg rush since they would have more enjoyment dominating the game than they would in a normal match. As a result, both players Zerg rush and the games are unsatisfying to play.

                Another issue that comes from developers patching a game and adding new content is the inevitable bugs that come along with that content. Sometimes these bugs and glitches will be small and not usually have much impact on the game, but there are times when exploiting these bugs is a legitimate strategy that results in a more likely victory. For instance, “some players of the online first-person shooter Modern Warfare 2 discovered what became known as “the javelin glitch.” Someone, somewhere, somehow figured out that through a bizarre sequence of button presses you could glitch the game so that when you died in multiplayer you would self destruct and murder everyone within 30 feet, often resulting in a net gain in points” (Madigan 2010). Modern Warfare players end up in a similar dynamic as the Zerg rush problem where they have to decide which strategy will result in a more positive outcome.

Example of Javelin Glitch
Javelin Glitch pay off matrix

                Once again, even though not exploiting the glitch would result in fair play that is optimal for both parties, instead the more common route was mayhem where all players exploited this glitch. This was so common in fact that Infinity Ward had to rush out a patch to stop it from being exploited any further. Using the same logic as the prisoner’s dilemma we can see that the dominant strategy for all players would be to glitch. The players would rather have a broken match than be dominated by opposing players.

                In conclusion, the prisoner’s dilemma and game theory allow for a better understanding of social dilemmas in not just the real world, but also the virtual world. I believe that game developers at the very least can use this information to prevent players from having to be put in future dilemmas, such as by banning players that exploit bugs so that the pay off matrix  will result in a dominant strategy that is fun for all players.

Sources:

Madigan, J., Says. (2013, July 30). The Glitcher’s Dilemma: Social Dilemmas in Games. Retrieved November 18, 2020, from https://www.psychologyofgames.com/2010/03/279/

Categories
Uncategorized

Analyzing Film Release Times Using Game Theory

No matter how high quality a film is, if it is not marketed properly or released at a right time, it may get hit by low sales. Many things can influence the release date of a film. Genre of a film is one of the most important things that affects its release time as people are used to certain types of movies in certain seasons. That is why we usually get blockbuster action movies in Summer, critically acclaimed dramas in Fall, scary and horror movies closer to Halloween and comedy/holiday theme movies closer to new year holidays. However, genre of a film is not the only thing that greatly has an influence on the release date. Publishers also try their best to make sure they release their films farther apart from each other so that they do not have to compete with each other in box office revenues. That is the reason researchers from Shanghai University of Finance and Economics, decided to explore the idea of using Game Theory in order to see if they can maximize the revenues of multiple studios competing with each other for release time slots and whether or not there exists a pure Nash equilibrium for such scenarios.

In their model, they used n players (film publishers), who are selfish and always trying to maximize their revenue. They decide the release date of the film and only have one film to publish. They used a utility function u_i(a, delta) which defines the number of audience who watches player i’s film.

In the function above, a is the action profile. There are M available time slots and a_i is in M. delta_i is the popularity degree of the film i. C_j is the set of players who chose the time slot j. The demand of the audience in j-th time slot is denoted by d_j.

Using the function above, they are able to calculate the utility (revenue) a player earns in each time slot and are able to create a payoff matrix based on the actions each player chooses. After creating the payoff matrix, the researchers then had to prove that a pure Nash equilibrium exists in the matrix. In order to do that they created a set s that defines the strategy profiles of all the players. s_i is the strategy profile of player i, s_-i is the strategy profile of all players except i.

Proving the equation above means that, there is a strategy s^* that no player can increase its utility by changing its release time slot. Therefore, there exists a Nash equilibrium.

Using the utility function and the payoff matrix created by the utility function they were able to prove the above equation which led to this theorem:

“In the attraction competition game, there always exists a pure Nash equilibrium. If players choose the release time greedily in the decreasing order of the popularity degree, the reached schedule is a Nash equilibrium.”

As we saw in the example above, Game Theory can be used to analyze many real life decisions which can lead to better decision making and profit to parties that use it efficiently.

References:

https://arxiv.org/abs/1910.13095

Categories
Uncategorized

Information Cascades and Community Cooperation

Communities. When most people think about them, we usually think of a group of people that have strong ties to one another. They trust each other and, more importantly, are willing to cooperate with one another to achieve a goal. But being the evil little gremlin I am, I wondered to myself, how strong are these communities actually? What would it take to completely demolish a community’s willingness to cooperate with one another? And then I stumbled upon an article titled “Information Cascades and the Collapse of Cooperation” by Tang et al., I was instantly intrigued and felt the need to write about it. I wanted to gain insight into community dynamics and see empirical evaluations of the process of being a newcomer to a community. I also wanted to witness the effects bad actors in a community can have in a quantified manner. I felt that such information could help me grasp the importance of various mechanisms of communities such as moderators, especially in the realm of online forums.

I’ll quickly give a rundown of Yang et al.’s study. Given an underlying social network, each node is classified either as a cooperator or a defector. As time passes, a new node is introduced, and they connect to a node in the network, which they call a “role-model”. Ideally new nodes would want to connect to cooperators and avoid defectors. When the new node is making their decision, they have access to public and private information. The public information is simply the degree of nodes in the network and the private information is a sample taken from one of two Gaussian distributions, one for cooperators and another for defectors.

I’ll quickly describe some important variables used in the study. Cooperators distribute a benefit of b value to its neighbours for a cost c. There is also a variable denoted as δ (the “selection strength”), which is basically the degree to which a node will consider its payoff when choosing to connect to a role-model. The higher δ, the more likely it will connect to role-models that provide a larger payoff. p is a weight between 0 and 1 which defines how heavily public information should be considered when deciding whether to connect to a role-model; q is defined similarly for private information. Finally, there is the notion of P-cascades and N-cascades which are information cascades that form when there is a conflict between private and public information. P-cascades are cascades that are created when the private information of newcomers indicate they should connect to a role model, but instead they follow public information and don’t connect. Similarly, N-cascades are cascades where private information of newcomers indicate they shouldn’t connect to a role model, but instead follow public information and connect.

In terms of content relating to CSCC46, the study tackles the concepts of game theory and information cascades. Yang et al. utilized game theory (specifically evolutionary game theory) by treating connections between nodes as a game where the payoffs are based on a pre-defined benefit and cost variable.

Figure 1: Payoff matrix for game between node and its neighbours. Assume b > c > 0.

Information cascades are a concept in CSCC46 that this study directly addresses when it comes to the role-models newcomers choose. If public and private information about whether a node should connect to a role-model conflict, newcomers may make the wrong decision when choosing to connect/reject a node. If a series of wrong decisions are made, this can cause successive newcomers to simply follow the crowd and make the same mistake, leading to a P-cascade or N-cascade.

What I found interesting about this study is how they allowed public and private information to be weighed differently. This sort of mimics how people in the real world might behave in this kind of scenario. You may have people who are more comfortable going along with the crowd, thus they will value public information more heavily. Likewise, someone who is more independent may have more confidence in their own private information and thus will weigh it more heavily. On a related note, in the study, Yang et al. discovered that public information had significant effects on the underlying social network, even if it was in limited amounts.

Figure 2: Graphs showing levels of cooperation at varying decision thresholds 𝜏 for three selection strengths δ. The left column of graphs is for the scenario where private information is weighed more than public information. The right column is the opposite in that regard. Each row corresponds to corresponds to different benefit to cost ratios. Note: the last row should be “b/c=10/8”.

Notice in Figure 2, private info generally has a high degree of cooperation which lasts for higher decision thresholds, as shown by the left side. Meanwhile on the right side, cooperation values were lower when public information was being considered more. These findings could be an approximate answer to the question I proposed at the beginning of this blog. If a group of individuals were to distort public information, even just little bit, it could take a serious toll on how communities cooperate and function as a whole. Subsequently, this provides a basis for why community moderators seem so important. They can control community dissidents and prevent public information from being absurdly polluted.

While this study was only an approximation, it gives a rough idea why cooperation is so fragile within communities. If others were to build upon this research and perhaps obtain real-world data on this subject, a mitigating factor can be discovered for the reasons behind such fragility. Not only would this make communities more resilient to collapses in cooperation, but it could also point towards a solution the actual cause of these collapses, stopping them once and for all.

References

Yang, G., Csikász-Nagy, A., Waites, W. et al. Information Cascades and the Collapse of Cooperation. Sci Rep 10, 8004 (2020). https://doi.org/10.1038/s41598-020-64800-z

https://www.nature.com/articles/s41598-020-64800-z

Categories
Uncategorized

Using Network Analysis to Better Understand Virtual Communities in MMORPGs

MMORPGs are one the most popular and interesting genres in the video game industry. World of Warcraft, Black Desert Online and Destiny have been prominent examples of this genre for years. One the most unique features of MMORPGs are the virtual communities, most of the time referred to as Clans, that are created due to the nature of this genre, which promotes completing missions and quests with other players. One thing that has been interesting to me about these communities, are the characteristics and personalities of them and how they differ from each other. How do they recruit players and communicate with each other? Fortunately for us, there have been a research done by Markus Schatten and Bogdan Okreša Ðuri ́c from University of Zagreb about this exact subject by using analytical techniques and graph theories we are learning in CSCC46.

In this study, they observed and collected data from players, which were mostly students from three countries, for one month. After data collection, they used social network analysis (SNA) techniques to find patterns of organizational behavior among successful players.

The analysis of their data found multiple interesting player behaviors. For example, players usually describe their relationship with other players using characteristics like, Friend, Enemy and Blacklist. Another finding showed that communities are usually created among people who have the same interests. For example, players who try to complete the same mission, acquire the same items or have similar goals usually tend to group together. Analyzing chats and communications also showed that people who are on the same or similar real-life geographical locations, tend to use in game chat and whisper functionalities with each other more than others.

This study shows that analyzing player behaviors in games, specially player to player behaviors, can show many interesting facts which can be very useful to game developers to better optimize and design their games for their audience. It can also help scientists better understand how people communicate and interact with each other in virtual worlds.

Source:

https://bib.irb.hr/datoteka/796277.Proceedings_IEEE_9828a037.pdf

Categories
Uncategorized

Analyzing Game Tags on Steam using Community Detection

Ever since I was young, playing video games was one of my favorite hobbies and it still is today. Over the years I have spent with this hobby, I have played various games that spanned a wide array of genres and have seen certain games come in and out of relevancy over time. And as I observed these patterns, I noticed I was asking myself “What games are currently popular? Why did certain games become relevant/irrelevant?”. As such, I wanted to see how applications of network analysis could help me in my quest to gain a larger perspective of the gaming community.

Luckily, Xiaozhou Li and Boyang Zhang of Tampere University have responded to my desire with their January 2020 study “A Preliminary Network Analysis on Steam Game Tags: Another Way of Understanding Game Genres”. In their study, they examined the largest PC gaming platform known as Steam and their user-defined tagging system. The gist of the system is that users can assign tags that they feel represent a game the best (for example, some might tag the game “Call of Duty” as an “Action” and “Shooter” game) and frequently applied tags will become featured categories for that game. Li and Zhang analyzed this tagging system by building a network of game tags, creating an edge between tags if they both were applied to a game. They then performed community detection to see how tags grouped up into communities and labeled the communities based on highest centrality nodes within each community, as shown by Figure 1.

In terms of content related to CSCC46, this study applies the concepts of community detection and PageRank, although the latter has not been discussed yet as of writing this blog. One interesting thing to note is how Li and Zhang performed community detection. They used a method called the “Louvain method” as opposed to the Girvan-Newman algorithm studied in class. Subsequently, the concept of betweenness also appeared in the study; edges with high betweenness connected game tags that usually are not used together. PageRank was used to evaluate the importance of the game tags within the network, much like how PageRank was originally used to rank search query results in search engines.

Figure 1: The resulting communities of tags, split into 4 groups: a) Strategy & Simulation Games, b) Puzzle & Arcade Games, c) RPG Games, d) Shooter Games
Figure 2: A graph showing the connections between the most popular tags.

So why would this information be interesting? Couldn’t you just load up a site like SteamCharts and see what are the top and trending games? Well, yes, you could. But that doesn’t give as broad of an image. The data that Li and Zhang extracted from their study would be useful for game developers as they can see what games people are playing currently. It can provide insight into what kinds of games are currently hot on the market or if there are any genres that are gaining traction. And while the data quality may have been marred by incorrect tagging, it still shows how the wisdom of crowds still provided data that was relatively accurate. Overall, I feel that if this information were frequently updated, publicly available, and covered a broader scope of platforms, it would be an incredibly useful tool for developers and gamers.

References

Li, Xiaozhou & Zhang, Boyang. (2020). A preliminary network analysis on steam game tags: another way of understanding game genres. 65-73. 10.1145/3377290.3377300.

https://www.researchgate.net/publication/339081814_A_preliminary_network_analysis_on_steam_game_tags_another_way_of_understanding_game_genres

https://store.steampowered.com/tag/

Categories
Uncategorized

Using Graphs to Recommend Champions (League of Legends)

In class, we learned about the various uses for graphs and Dijkstra’s algorithm. This made me consider how graphs are used in video games, considering the clear and visible variables that they use, and how much easier it would be to collect data from a game than it would be in real life. Graphs can help find relationships with variables and Dijkstra’s algorithm can be used to find the maximum distance between those variables. One use of these tools relating to video games would be for recommendations. Specifically, I will discuss about champion recommendation in the video game League of Legends.

League of Legends is Multiplayer Online Battle Arena (MOBA) game where two teams of players battle each other with characters called Champions. Players select Champions based on the roles they prefer to take to aid their team in the fight. There is a large inventory of Champions players can choose from. To ensure players try a variety of Champions, the developer of the game may wish to recommend other Champions that may suit the play style of the player. A naïve way to recommend Champions would be to compare the key attributes between the player’s most used Champion and other Champions in the Champion roster, finding one that shares the most features. However, using graph theory, it is possible to generate a network to find recommendations using the player base instead of the Champions themselves.

Suppose a player, who enjoys playing with Champion A, also enjoys playing with Champion B. Then it is very likely other players who enjoy playing Champion A may enjoy playing with Champion B. However, to generate a graph that strongly supports these predictions would require a lot of player data. Luckily, the game has a large player base, reaching 100 million unique monthly players at one point in 2017 (Spezzy 2020).

Typical attribute-based recommendation

By having every Champion in the game be represented as a node and the weighted connection between two Champions be represented by the edges of the graph, we can find a much better representation of champion picks in general. These connections can be found by using the most played champions for every player in a given sample. If two champions appear in the same top five most played champions for a player, it can be concluded that there is a connection between them.

Example of connections per champion (Williams 2020)

While a graph like this would seem useful at first glance, it has its issues stemming from the mechanics of the game. Recommendations from this graph will most likely recommend champions who are in the same role as other champions since players tend to dedicate themselves to playing certain positions. A quick fix to this problem is to find each player’s top three Champions per role instead. We can then use Dijkstra’s algorithm to find champions with minimal distance from each other to give out much better recommendations than we would have with an attribute-based recommendation system.

Recommendation graph that skewed towards champions of the same position (Williams 2020)

In conclusion, graphs and Dijkstra’s algorithm allow for much better champion recommendations by taking advantage of the large amount of data from video games. I believe that this idea could also be extended for other recommendations services by checking what items or choices are chosen by users in common and recommending them to other users.

Sources:

Williams, J. J. (2020, September 20). Graph Networks for Champion Recommendation (League of Legends). Retrieved October 15, 2020, from https://towardsdatascience.com/graph-networks-for-champion-recommendation-league-of-legends-189c8d55f2b

S. (2020, August 03). Did you know? Total League of Legends Player Count – UPDATED 2020. Retrieved October 15, 2020, from https://leaguefeed.net/did-you-know-total-league-of-legends-player-count-updated-2020/