Recently dominant sets, a generalization of the notion of the maximal clique to edge-weighted graphs, have proven to be an effective tool for unsupervised learning and have found applications in different domains. Although, they were initially established using optimization and graph theory concepts, recent work has shown fascinating connections with evolutionary game theory, that leads to the clustering game framework. However, considering size of today's data sets, existing methods need to be modified in order to handle massive data. Hence, in this research work, first we address the limitations of the clustering game framework for large data sets theoretically. We propose a new important question for the clustering community ``How can a cluster of a subset of a dataset be a cluster of the entire dataset?''. We show that, this problem is a coNP-hard problem in a clustering game framework. Thus, we modify the definition of a cluster from a stable concept to a non-stable but optimal one (Nash equilibrium). By experiments we show that this relaxation does not change the qualities of the clusters practically. Following this alteration and the fact that equilibriums are generally compact subsets of vertices, we design an effective strategy to find equilibriums representing well distributed clusters. After finding such equilibriums, a linear game theoretic relation is proposed to assign vertices to the clusters and partition the graph. However, the method inherits a space complexity issue, that is the similarities between every pair of objects are required which proves practically intractable for large data sets. To overcome this limitation, after establishing necessary theoretical tools for a special type of graphs that we call vertex-repeated graphs, we propose the scalable clustering game framework. This approach divides a data set into disjoint tractable size chunks. Then, the exact clusters of the entire data are approximated by the clusters of the chunks. In fact, the exact equilibriums of the entire graph is approximated by the equilibriums of the subsets of the graph. We show theorems that enable significantly improved time complexity for the model. The applications include, but are not limited to, the maximum weight clique problem, large data clustering and image segmentation. Experiments have been done on random graphs and the DIMACS benchmark for the maximum weight clique problem and on magnetic resonance images (MRI) of the human brain consisting of about 4 million examples for large data clustering. Also, on the Berkeley Segmentation Dataset, the proposed method achieves results comparable to the state of the art, providing a parallel framework for image segmentation and without any training phase. The results show the effectiveness and efficiency of our approach. In another part of this research work, we generalize the clustering game method to cluster uncertain data where the similarities between the data points are not exactly known, that leads to the uncertain clustering game framework. Here, contrary to the ensemble clustering approaches, where the results of different similarity matrices are combined, we focus on the average utilities of an uncertain game. We show that the game theoretical solutions provide stable clusters even in the presence of severe uncertainties. In addition, based on this framework, we propose a novel concept in uncertain data clustering so that every subset of objects can have a ''cluster degree''. Extensive experiments on real world data sets, as well as on the Berkeley image segmentation dataset, confirm the performance of the proposed method. And finally, instead of dividing a graph into chunks to make the clustering scalable, we study the effect of the spectral sparsification method based on sampling by effective resistance on the clustering outputs. Through experimental and theoretical observations, we show that the clustering results obtained from sparsified graphs are very similar to the results of the original non-sparsified graphs. The rand index is always at about 0.9 to 0.99 in our experiments even when lots of sparsification is done.

Vaccination has been used to control the spread of infectious diseases for centuries with widespread success. Deterministic models studying the spread of infectious disease often use the assumption of mass vaccination; however, these models do not allow for the inclusion of human behaviour. Since current vaccination campaigns are voluntary in nature, it is important to extend the study of infectious disease models to include the effects of human behaviour. To model the effects of vaccination behaviour on the spread of influenza, we examine a series of models in which individuals vaccinate according to memory or individual decision-making processes based upon self-interest. Allowing individuals to vaccinate proportionally to an exponentially decaying memory function of disease prevalence, we demonstrate the existence of a Hopf bifurcation for short memory spans. Using a game-theoretic influenza model, we determine that lowering the perceived vaccine risk may be insufficient to increase coverage to established target levels. Utilizing evolutionary game theory, we examine models with imitation dynamics both with and without a decaying memory function and show that, under certain conditions, periodic dynamics occur without seasonal forcing. Our results suggest that maintaining diseases at low prevalence with voluntary vaccination campaigns could lead to subsequent epidemics following the free-rider dilemma and that future research in disease control reliant on individual-based decision-making need to include the effects of human behaviour.

[pt] O papel das agências de rating de crédito no mercado de capitais tem evoluído ao longo dos últimos anos, passando de um provedor de informação aos agentes financeiros a um quase-regulador do mercado. Em princípio, supõe-se que as avaliações concedidas pelas agências de rating são imparciais e, consequentemente, indicadoras de qualidade de crédito dos mais diversos instrumentos financeiros. Porém, deve ser observado que à medida que esses instrumentos disponíveis no mercado foram se tornando mais complexos, o valor agregado das avaliações das agências diminuiu consideravelmente. A fim de analisar o problema da imparcialidade das agências de rating, conforme proposto por Hirth (2014), fez-se uso da estrutura espacial em comparação à solução analítica apresentada como condição de equilíbrio para o jogo evolucionário, com população well-mixed. Sendo assim, para a modelagem do problema apresentado, foi criado um programa computacional baseado a fim de apresentar uma solução compatível com a literatura sobre Teoria dos Jogos, expandindo seus conceitos e aplicações para uma Estrutura de Jogos Espaciais. Por fim, foi desenvolvida uma extensão ao programa, a qual, dentro do meu melhor conhecimento, representa uma inovação à literatura ao estender as abordagens de Chan et al. (2013), Hauert (2004) e Zhong et al. (2006), considerando a Estrutura de Jogos Espaciais, para o conceito de duas populações. A partir dos casos estudados, pode-se concluir que a população ser well-mixed ou estar disposta ao longo de um grid espacial não implica em diferenças significativas nos resultados para os mesmos valores dos parâmetros. / [en] The role of the credit rating agencies in the capital market has evolved in the last years, turning from a data provider to financial agents into a market quasi-regulator . Primarily, it is supposed that the evaluations provided by the rating agencies are impartial and, consequently, indicative of credit quality of a wide range of financial instruments. Nevertheless, it is important to note that as these instruments available in the market became more complex, the aggregate value of evaluations of agencies decrease considerably. In order to analyze the rating agencies impartiality issues, as proposed by Hirth (2014), this study uses the spatial structure in comparison to the analytical solution presented as equilibrium condition to the evolutionary game, with well-mixed population. Therefore, in order to model the presented problem, this study presents a computational program that aims to present a solution that matches the Game Theory literature, expanding its concepts and applications to a Spatial Games Structure. Finally, we created an extension of the program, which, in my best knowledge, is an innovation to the literature since it extends the approaches of Chan et al. (2013), Hauert (2004) e Zhong et al. (2006), regarding the Spatial Games Structure, to the concept of two populations. From the studied cases, we concluded that the fact of the population being well-mixed or disposed in a spatial grid does not imply differences of significance in the results to the same parameters values.

Satisficing game theory is an alternative to traditional non-cooperative game theory which offers increased flexibility in modeling players' social interactions. However, satisficing players with conflicting attitudes may implement dysfunctional behaviors, leading to poor performance. In this thesis, we present two attempts to "bridge the gap" between satisficing and non-cooperative game theory. First, we present an evolutionary method by which players adapt their attitudes to increase raw payoff, allowing players to overcome dysfunction. We extend the Nash equilibrium concept to satisficing games, showing that the evolutionary method presented leads the players toward an equilibrium in their attitudes. Second, we introduce the conditional utility functions of satisficing theory into an otherwise traditional non-cooperative framework. While the conditional structure allows increased social flexibility in the players' behaviors, players maximize individual utility in the traditional sense, allowing us to apply the Nash equilibrium. We find that, by adjusting players' attitudes, we may alter the Nash equilibria that result.

Thesis advisor: Katherine McAuliffe / Thesis advisor: Angela Johnston / Human cooperation is unparalleled in the natural world and is a defining feature of human social life—it shapes nearly every social interaction we experience, from geopolitical conflict, to collective bargaining, to team collaboration. However, cooperation also presents a challenge—it is often personally costly or risky to cooperate. How are humans able to overcome these costs and risks in favor of the interest of the group? To address this question, it is important to investigate the cognitive abilities that allow us to successfully cooperate with others. One important ability for cooperation is mentalizing—the ability to represent other agents’ beliefs, knowledge, desires, and intentions. The ability to think about other agents’ minds in order to predict how they will behave (e.g., whether they will cooperate or free-ride) is an important component of our own cooperative behavior, particularly in the context of coordination—a type of cooperative interaction where cooperation is mutually beneficial but risky. I test the idea that our ability to represent the beliefs of others plays a critical role in successful cooperation. Studies 1 and 2 examine one cognitive ability for representing others’ knowledge—common knowledge—that underlies cooperation by reducing uncertainty about others’ cooperative behavior. Studies 3 and 4 investigate how we make inferences about others’ beliefs from how they behave and how that influences our own cooperative behavior in the context of social norms. Studies 2 and 4 take a developmental approach to investigate how early emerging mentalizing is for cooperative behavior to better understand how foundational it is in social cognition. Altogether, the results of these studies suggest that the ability to represent other agents’ beliefs in order to predict their behavior plays a fundamental role in supporting successful cooperation. / Thesis (PhD) — Boston College, 2023. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Psychology.

Cooperation in joint enterprises poses a social dilemma. How can altruistic behavior be sustained if selfish alternatives provide a higher payoff? This social dilemma can be overcome by the threat of sanctions. But a sanctioning system is itself a public good and poses a second-order social dilemma. In this paper, we show by means of deterministic and stochastic evolutionary game theory that imitation-driven evolution can lead to the emergence of cooperation based on punishment, provided the participation in the joint enterprise is not compulsory. This surprising result - cooperation can be enforced if participation is voluntary - holds even in the case of 'strong altruism', when the benefits of a player's contribution are reaped by the other participants only. (authors' abstract)

Existe um interesse crescente do mercado por aplicações de multimídia em streaming via rede. Particularmente, as aplicações de live streaming que utilizam a tecnologia de redes P2P para a disseminação de conteúdo têm sido alvo de grande atenção. Aplicações como PPLive e PPStream provam que as aplicações de live streaming em redes P2P são uma realidade com relação à tecnologia atual. Os sistemas de live streaming fornecem um serviço de multicast no nível de aplicação para transmissões ao vivo na Internet. Essas aplicações de live streaming, quando executadas em redes P2P, têm potencial para serem altamente robustas, escaláveis e adaptativas devido à redundância e não dependência de recursos particulares dentre os nodos participantes. Porém, para fazer uso de todas as vantagens disponíveis, a aplicação deve contornar alguns desafios: i) manter a qualidade de playback mesmo com a inerente dinamicidade das redes P2P; ii) impedir que nodos incorretos escondam ações maliciosas atrás do anonimato que existe em P2P; iii) manter a taxa de upload dos nodos participantes da aplicação em um nível aceitável. A taxa de upload dos nodos é muito importante porque a aplicação de live streaming em P2P é uma aplicação cooperativa. Desta forma, esperase que todo novo usuário ajude a aplicação retransmitindo pacotes para outros usuários, mantendo, desta forma, a capacidade global de upload do sistema. Infelizmente, manter a cooperação em live streaming não é uma tarefa trivial, visto que cada nodo enfrenta o dilema social do interesse próprio (individualmente é melhor explorar a cooperação dos outros usuários sem reciprocidade) versus a cooperação para com o grupo. A principal contribuição deste trabalho consiste na apresentação de um modelo matemático baseado em Teoria dos Jogos Evolucionários, cujo objetivo é ajudar a compreender as aplicações de live streaming em redes P2P e os fatores que influenciam o seu correto funcionamento. Como contribuição secundária, este trabalho fornece uma análise estatística do comportamento do download e upload observado nestas aplicações. A análise estatística mostra que existe um decaimento da variância temporal de download e upload nas aplicações de live streaming, e que tal decaimento segue uma lei de potência. Os resultados evolucionários do modelo indicam que, se a queda do índice de satisfação dos usuários com a taxa de download for suave, e se a redução da satisfação devido ao custo de upload for insignificante, então existe um ambiente propício para que a cooperação entre os nodos cresça. De forma inversa, se a queda do índice de satisfação dos usuários com a taxa de download for abrupta, e a redução da satisfação devido ao custo de upload for significativa, então existe um ambiente propício para proliferação de nodos oportunistas. A realização e descrição desta pesquisa é composta de quatro etapas principais: i) a delimitação do cenário de live streaming e a definição do jogo para modelagem; ii) a definição do conjunto de estratégias e da função de utilidade; iii) a criação do modelo; iv) a análise do modelo e a apresentação dos resultados de simulação. A análise do modelo abrange três fases: i) análise estatística e comparação das características de download e upload dos dois simuladores utilizados; ii) avaliação do modelo de Teoria dos Jogos Evolucionários através de simulações; e iii) análise dos resultados evolucionários gerados pelo simulador de Teoria dos Jogos Evolucionários. / There is a growing interest in the market for networked multimedia applications. Live streaming applications that use the technology of P2P networks for distribution of live content have specially been the subject of great attention. Applications such as PPLive and PPStrem demonstrate that P2P live streaming applications are already possible with our present technology. Live streaming systems provide a multicast service in the application level for live broadcasts to users through the Internet. These systems executing in P2P networks have the potential to be highly robust, scalable and adaptive due to the characteristics of these scenarios. However, to take advantage of these potential properties, they must overcome some challenges: i) to maintain the playback quality even with the inherent dynamics of P2P networks; ii) to prevent that incorrect peers hide malicious behavior behind their anonymity; iii) to maintain the upload contribution of peers at acceptable levels. The upload contribution of peers is highly important because live streaming applications are cooperative applications. Therefore, every new user must help the application forwarding packets to other users, thereby maintaining the global upload capacity of the system. Unfortunately, the maintenance of cooperation in live streaming system is not a trivial task, since each node faces the social dilemma of self-interest (individually is always better to explore the cooperation of other users without reciprocity) versus cooperation to the group. The main contribution of this dissertation is the presentation of a mathematical model based on Evolutionary Game Theory, whose goal is to help understanding live streaming P2P applications and the factors that influence their correct operation. As a secondary contribution, this work provides a statistical analysis of download and upload behaviors of peers in live streaming P2P systems. The statistical analysis indicates that there is a decay in the download and upload variances, and that this decay follows a power law. The evolutionary results of the model indicate that, if the satisfaction of users with the download rate is smooth, and the reduction of satisfaction due to the upload cost is negligible, then there is a favorable environment for the growth of cooperation. Conversely, if the satisfaction of users with the download rate is abrupt, and the reduction of satisfaction due to the upload cost is significant, then there is a favorable environment to the proliferation of opportunistic nodes. The realization and description of this research is composed of four main steps: i) the definition of the live streaming scenario and the definition of the game to model this scenario; ii) the definition of the strategy set and of the utility function; iii) the suggestion of a model; iv) the analysis of the proposed model and the presentation of obtained results. The model analysis comprehends three phases: i) the statistical analysis and the comparison of the characteristics of download and upload of the two simulators used in this work; ii) the evaluation of the Evolutionary Game Theory model through simulation; and iii) the analysis of the results generated by the Evolutionary Game Theory simulator.

Nouvelles approches aux jeux évolutionnaires et processus de décision. La théorie des jeux évolutionnaires (EGT) constitue un cadre simple pour étudier le comportement de populations larges dont les membres sont engagés en interactions stratégiques. Dans la première partie de cette thèse nous proposons une nouvelle approche pour la modélisation de l’ évolution, où le joueur est formé par un ensemble d’individus. Nous considérons toujours des interactions entre individus mais nous supposons qu’ils maximisent le fitness du group auquel ils appartiennent. Nous présentons, dans la deuxième partie du manuscrit, une nouvelle approche dynamique des Markov Decision Evolutionary Games, qui constituent une classe des jeux stochastiques. À différence de l’approche statique standard, en ce travail nous considérons les dynamiques des états individuels et couplée avec les politiques et nous les décrivons à travers des équations différentielles interdépendantes. Dans la troisième partie du manuscrit, nous poursuivons l’étude des jeux stochastiques dynamiques dans un contexte différent, la théorie du contrôle. Nous définissions un système stochastique dynamique contrôlé simultanément par deux joueurs engagés dans un jeu à somme non nulle (et non constante) et nous montrons que le problème stochastique peut être approximé à travers un jeu dynamique déterministe. / Evolutionary Game Theory (EGT) constitutes a simple framework to study the behavior of large populations whose individuals are repeatedly engaged in pairwise strategic interactions. While in standard EGT, the interacting individual is the player, choosing the actions to play in order to maximize its own fitness, in the first part of this dissertation we propose, in the first part of this work, a new approach to model evolution, where the player is supposed to be a whole group. We still consider pairwise interactions among individuals but we assume that they maximize the fitness of the group they belong to, which is thus the actual player of the game. In the second part of this dissertation, we present our new dynamical approach to Markov Decision Evolutionary Games. In contrast with the standard static approach, we study here the local dynamics of individual states and the dynamics intrinsically related to the distribution of policies in the population, describing them by interdependent differential equations. In the third part of the manuscript we pursue the study of stochastic dynamics in a different context, that of control theory. We define a hybrid stochastic dynamical system jointly controlled by two players involved in a non-zero sum game and we prove that the problem can be approximated by an averaged deterministic differential game.

This thesis consists of five papers, presented as separate chapters within three parts: Industrial Organization, Evolutionary Game Theory and Game Theory. The common basis of these parts is research in the field of game theory and more specifically, equilibrium selection in different frameworks. The first part, Industrial Organization, consists of one paper co-authored with Prajit Dutta and Jörgen Weibull. Forward-looking consumers are analysed in a Bertrand framework. It is assumed that if firms can anticipate a price war and act accordingly, so can consumers. The second part, Evolutionary Game Theory, contains three chapters. All models in these papers are based on Young’s (1993, 1998) approach. In Chapter 2, the Saez Marti and Weibull’s (1999) model is generalized from the Nash Demand Game to generic two-player games. In Chapter 3, co-authored with Jens Josephson, a special set of stochastically stable states is introduced, minimal construction, which is the long-run prediction under imitation behavior in normal form games. In Chapter 4, best reply and imitation rules are considered on extensive form games with perfect information. / Diss. Stockholm : Handelshögsk., 2001

Kooperatives Verhalten lässt sich in vielen Bereichen menschlichen Zusammenlebens sowie im gesamten Tierreich beobachten. In evolutionären Modellen wurde gezeigt, dass Netzwerkstrukturen die Kooperation erhöhen können. Empirische Studien versuchten vergeblich diesen Mechanismus auch bei Menschen nachzuweisen. Es scheint, als würden Netzwerke nur dann die Kooperation erhöhen, wenn die Strukturen nicht statisch sind, sondern dynamisch. Das heißt, dass die Individuen die Möglichkeit haben, ihre Partner zu wechseln. Eine wichtige – aber bislang unerforschte – Eigenschaft dynamischer Netzwerke ist jedoch, dass derartige Wechsel von Partnern in der Regel Kosten verursachen, ob in Form von Zeit oder Ressourcen. Kapitel I meiner Arbeit schließt diese Lücke, in dem es sich mit den Effekten von Kosten auf dynamischen Netzwerken befasst. Ich konnte nachweisen, dass Menschen seltener Interaktionen mit Partnern beendeten, wenn die Kontaktaufnahme mit einem neuen Partner mit Kosten verbunden war. Bei sehr hohen Kosten, wurden Partner so selten gewechselt, dass das Netzwerk fast statisch war. Interessanterweise blieb die Kooperation dennoch sehr hoch. Das bedeutet, dass für kooperatives Verhalten entscheidend ist, ob man die Möglichkeit hat, Partner zu wechseln. Im Gegensatz zu bisherigen Annahmen ist es daher nicht wichtig, wie oft tatsächlich Partner gewechselt werden, sondern lediglich ob es die Möglichkeit dazu gibt. In Kapitel II beschäftige ich mich mit optimalem Entscheidungsverhalten. Im sogenannten Judge-Advisor-System geht es darum, dass eine Person, der Judge, eine unbekannte numerische Größe schätzen will. Dazu erhält der Judge eine zweite unabhängige Schätzung als Rat von einer zweiten Person, des Advisor. Schließlich ist die Frage, wie der Judge optimal den Rat verwerten kann um seine Anfangsschätzung zu verbessern. Bisherige Forschung konzentrierte sich hauptsächlich auf zwei mögliche Methoden, (i) das Bilden des Mittelwerts und (ii) das Wählen der besseren Anfangsschätzung. Das Hauptargument für diese einfachen Methoden ist deren häufige Verwendung in bisherigen Experimenten. Allerdings wurden sehr wohl auch andere Gewichtungen beobachtet und daher ist eine gründliche Analyse der optimalen Gewichtung erforderlich. In der vorliegenden Arbeit leitete ich ein normatives Modell her, das beschreibt, unter welchen Bedingungen welche Methode das bestmögliche Ergebnis liefert. Es wurden drei Methoden verglichen: (i) das Bilden des Durchschnitts, (ii) das Wählen der besseren Anfangsschätzung, und (iii) das Bilden eines gewichtetet Mittelwerts, wobei das Gewicht vom Kompetenzunterschied abhängt. Welche Methode optimal ist, hängt davon ab, wie groß der Kompetenzunterschied ist und wie gut er vom Judge erkannt wird. Die Durchschnittbildung ist immer dann vorteilhaft, wenn der Kompetenzunterschied nicht groß ist, oder nur schwer richtig eingeschätzt werden kann. Wenig überraschend lohnt sich das Wählen der besseren Anfangsschätzung, wenn der Kompetenzunterschied hinreichend groß ist, vorausgesetzt es wird tatsächlich die bessere Anfangsschätzung gewählt. Wenn der Kompetenzunterschied vom Judge gut eingeschätzt werden kann, ist eine Entsprechende Gewichtung immer die beste Methode, unabhängig vom tatsächlichen Unterschied. In Übereinstimmung mit bisheriger Forschung wurde auch die Kombination von Durchschnittbildung und Wählen der besseren Anfangsschätzung untersucht. Diese Kombinationsmethode beruht darauf, bei als gering eingeschätztem Kompetenzunterschied den Durchschnitt zu bilden und ansonsten die bessere Anfangsschätzung zu wählen. Interessanterweise schneidet diese Kombinationsmethode sehr schlecht ab, was hauptsächlich daran liegt, dass zu oft die falsche Anfangsschätzung genommen würde. Insgesamt ist das gewichtete Mittel also eine geeignete Methode für einen großen Parameterbereich.