This dissertation focuses on robust coalition formation between selfish agents in a dynamic environment where contracts are unenforceable. Previous research on this topic has covered each different aspect of this problem, but no research successfully addresses these factors in combination. Therefore, a novel approach is required. This dissertation accordingly has three major goals: to develop a theoretical framework that describes how selfish agents should select jobs and partners in a dynamic, contractless environment, to test a strategy based on that framework against existing heuristics in a simulated environment, and to create a learning agent capable of optimally adjusting its coalition formation strategy based on the level of dynamic change found in its environment. Experimental results demonstrate that the Expected Utility (EU) strategy based on the developed theoretical framework performs better than strategies using heuristics to select jobs and partners, and strategies which simulate a centralized “manager”. Future work in this area includes altering the EU strategy from an anytime strategy to a hill-climbing one, as well as further game theoretic explorations of the interactions between different strategies. / text

In the hedonic coalition formation game model Roles Based Hedonic Games (RBHG), agents view teams as compositions of available roles. An agent's utility for a partition is based upon which role she fulfills within the coalition and which additional roles are being fulfilled within the coalition. I consider optimization and stability problems for settings with variable power on the part of the central authority and on the part of the agents. I prove several of these problems to be NP-complete or coNP-complete. I introduce heuristic methods for approximating solutions for a variety of these hard problems. I validate heuristics on real-world data scraped from League of Legends games.

This thesis examines the effects of economic and political turbulence on coalition-formation across 37 EU and OECD democracies. Utilizing the existing potential-coalitions research, it analyzes how increases in turbulence affect common variables predicted to determine which coalitions are chosen of all potential cabinets following an election. These variables drawn from the coalition-formation field are examined using a conditional logit regression model with interaction effects, and results indicate that both political and economic turbulence highly affect the way coalition formation is carried out, although the effects of the two turbulence types vary. During economic turbulence larger coalitions appear to be warranted, although results simultaneously suggest that ideological cohesion is hard to achieve during turbulent times. During political turbulence, instead, results suggest ideologically wide coalitions are more common but that minority cabinets are still more likely to appear. Despite the varying results, this analysis finds support that coalition formation is greatly affected by both economic and political turbulence. While the effects of some coalition-formation variables utilized by previous researchers appear to withstand the addition of turbulence, other effects change greatly when levels of instability are considered.

Doctor of Philosophy / Department of Computing and Information Sciences / Scott A. DeLoach / Coalition formation is a key cooperative behavior of a system of multiple autonomous agents. When the capabilities of individual agents are not su fficient for the improvement of well-being of the individual agents or of the entire system, the agents can bene t by joining forces together in coalitions. Coalition formation is a technique for finding coalitions that are best fi tted to achieve individual or group goals. This is a computationally expensive task because often all combinations of agents have to be considered in order to find the best assignments of agents to coalitions. Previous research has therefore focused mainly on small-scale or otherwise restricted systems. In this thesis we study coalition formation in large-scale multi-agent systems. We propose an approach for coalition formation based on multi-agent simulation. This approach allows us to find coalitions in systems with thousands of agents. It also lets us modify behaviors of individual agents in order to better match a specific coalition formation application. Finally, our approach can consider both social welfare of the multi-agent system and well-being of individual self-interested agents. Power distribution systems are used to deliver electric energy from the transmission system to households. Because of the increased availability of distributed generation using renewable resources, push towards higher use of renewable energy, and increasing use of electric vehicles, the power distribution systems are undergoing signi ficant changes towards active consumers who participate in both supply and demand sides of the electricity market and the underlying power grid. In this thesis we address the ongoing change in power distribution systems by studying how the use of renewable energy can be increased with the help of coalition formation. We propose an approach that lets renewable generators, which face uncertainty in generation prediction, to form coalitions with energy stores, which on the other hand are always able to deliver the committed power. These coalitions help decrease the uncertainty of the power generation of renewable generators, consequently allowing the generators to increase their use of renewable energy while at the same time increasing their pro fits. Energy stores also bene t from participating in coalitions with renewable generators, because they receive payments from the generators for the availability of their power at speci fic time slots. We first study this problem assuming no physical constraints of the underlying power grid. Then we analyze how coalition formation of renewable generators and energy stores in a power grid with physical constraints impacts the state of the grid, and we propose agent behavior that leads to increase in use of renewable energy as well as maintains stability of the grid.

Sistemas multiagentes muitas vezes apresentam características que os aproximam de sociedades de agentes e, como as humanas, possuem normas e organizações com o objetivo de coordenar as interações entre os seus membros. Coalizão é um tipo de estrutura organizacional temporária, montada com objetivos específicos. A teoria dos jogos estuda formalmente o fenômeno coalizional, se detendo em demonstrações de propriedades e características dessa estrutura. A área de sistemas multiagentes, por outro lado, tem mostrado significativo interesse nas estruturas coalizionais como forma de organizar a cooperação entre os agentes, dedicando-se ao desenvolvimento de algoritmos para formação de coalizões. Esse trabalho apresenta um algoritmo de formação de coalizões para compartilhamento de recursos, denominado heurística ganha-ganha. Definimos um modelo que utiliza a abstração de recursos para representar tanto a posse de habilidades e objetos, quanto para representar os objetivos dos agentes. Um jogo de votação k-ponderado é utilizado para implementar o processo decisório de quais coalizões são válidas e o algoritmo testa iterativamente cada vizinhança de um agente na busca de associações vantajosas. Demonstramos que o algoritmo incrementa monotonicamente o bem-estar da sociedade e converge para uma estrutura coalizional. Também mostramos empiricamente que a heurística é eficiente para compartilhamento de recursos em situações de abundância de recursos, montando coalizões em poucas iterações e com uma quantidade grande de agentes. / Multiagent systems frequently show characteristics that come closer to agent societies and, like the humans ones, have norms and organizations in order to coordinate the interactions of its members. Coalition is a type of temporary organizational structure, assembled with specific goals. Game theory formally studies the coalitional phenomenon focusing in the demonstrations of properties and characteristics of this structure. The area of multiagent systems, on the other hand, has devoted significant interest in coalition structures as a way to organize cooperation between its members, and has been dedicated to the development of algorithms for coalition formation. This dissertation presents an algorithm to coalition formation named win-win heuristic. We define a model which uses the abstraction of resources to represent either, the possession of abilities and objects, or to represent the agents target. A k-weight voting game is used to implement the decision process of what coalitions are worth and an iteratively algorithm tests each agent neighborhood in the pursue of better associations. We demonstrate that the algorithm monotonically increases the society welfare and converges to a coalitional structure. We also show empirically that the heuristic is efficient for resource sharing in situations of availability of resources, building coalitions with few iterations and a large amount of agents.

Thesis advisor: Hideo Konishi / My doctoral dissertation consists of three chapters on political economy and public economics. The first chapter discusses the effect of media bias on a voting competition. The second chapter focuses on how residents respond to increasing natural disaster risks in a multi-community framework. The third chapter investigates a coalition formation game with congestion effects. In chapter 1, I present a two-party election model with media noise. The media may provide polarized messages instead of those that explain the parties' actual policies. The rational voter relies on the media as an imperfect information source regarding a party's platform. Given this framework, I show that Downsian policy convergence is not valid. Moreover, when a party's ideology is relatively strong and the media bias is significant, one-sided polarization can occur: the party with more imprecise reports may adopt a more extreme strategy, whereas its opponent is more of a centrist in a perfect Bayesian equilibrium. This occurs when one party is misrepresented more often, causing the voter to think that the other party has more incentive to polarize. Therefore, the voter may favor the highly misrepresented party, which gives that party more room to polarize. I also show that parties never gain from these increasing misrepresentations, and a biased media environment can negatively affect the voter's welfare. My results suggest that the public should pursue a balanced media environment. Global warming and climate change have become increasingly important. In chapter 2, I investigate a local public goods economy using a new element: location-specific risks of disasters. Agents in this economy ``vote with their feet'' by choosing their favorite location as their residential base. In each location, all residents use majority rule to decide the local wealth tax rate and the amount of local public goods provision that can reduce the loss caused by disasters. I show that the equilibrium is wealth stratified if preferences are represented by a homothetic Stone-Geary utility function. Moreover, when disaster risks at a location increase, the population usually moves away from that location and the housing rents consequently decrease. Meanwhile, the housing rents and tax rates increase at the location the residents shift to. Moreover, I use this framework to numerically evaluate two policies: foreign donation and inter-jurisdiction transfer. If developed countries provides subsidies to a location with greater risks in a developing country, wealthier agents in the recipient country may move into the said location and force poorer agents to move out. This effect makes the wealthier the direct beneficiary of the foreign subsidy. Furthermore, I find that the inter-jurisdiction transfer may harm the poorer by rising housing rents. In chapter 3, I consider a coalition-formation problem, in which there is a set of feasible alternatives for each coalition and each player's payoff is affected by the coalition she belongs to and by its chosen alternative. In this chapter, I focus on ``congestion effects'': an agent's payoff goes down as an additional player joins the coalition other things being equal. The equilibrium notion considered is ``stability": a stable allocation (pairs of coalition structure and alternatives chosen by each coalition) is an allocation such that no coalition has an incentive to deviate from it. I find quite robust counterexamples to show that stability may fail to exist even under strong preference conditions such as the intermediate preference property and single peakedness. Nevertheless, I show a sufficient condition for the nonemptiness of stability: congruent-pair solvability. I also provide some results on the ``Nash-like" equilibrium notion. / Thesis (PhD) — Boston College, 2014. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Economics.

The thesis contains three chapters on environmental and natural resource economics and focuses on situations where agents receive private or public information. The first chapter analyses the problem of transboundary fisheries, where harvesting countries behave non-cooperatively. In addition to biological uncertainty, countries may face strategic uncertainty. A country that receives negative assessments about the current level of the fish stock, may become “pessimistic” about the assessment of the other harvesting country, which can ignite “panic-based” overfishing. In such a coordination problem, multiplicity of equilibria is a generic characteristic of the solution. Both strategic uncertainty and equilibrium selection, relatively, have been given less attention in the theoretical literature of common-property natural resources. In this model, in the limit as the harvesting countries observe more and more precise information, rationality ensures the unique “global game” equilibrium, a la Carlsson and van Damme (1993). The improved predictive power of the model helps a potential intergovernmental manager of the stock understand the threshold behaviour of harvesting countries. The global game threshold coincides with the risk-dominance threshold of a precise information model, as if there was no strategic uncertainty, and implies that the countries select the corresponding risk-dominant action for any level of assessment of the stock. Gaining from the risk-dominance equivalence, I derive policy suggestions for the overfishing cost and the property rights in common-property fisheries. The second chapter develops a theoretical framework to examine the role of public information in dynamic self-enforcing international environmental agreements (IEAs) on climate change. The countries choose self-enforcing emission abatement strategies in an infinite-horizon repeated game. In a stochastic model, where the social cost of greenhouse gasses (GHG) is a random variable, a central authority, as an information sender, can control release of information about the unknown state to the countries. In the literature on stochastic IEAs, it is shown that comparison of different scenarios of learning by the countries, depends on ex-ante difference of true social cost of GHG from the prior belief of countries. Here, I try to understand, in a signalling game between the informed sender and the countries, whether the no-learning or imperfect-learning scenarios, can be an equilibrium outcome. It is shown that the equilibrium strategy of the sender, who is constrained to a specific randomisation device and tries to induce an incentive-compatible abatement level which is Pareto superior, leads to full learning of social cost of GHG of symmetric and asymmetric countries. Finally, in the third chapter, I again examine a setting, where a central authority, as an information sender, conducts research on the true social cost of climate change, and releases information to the countries. However, in this chapter, instead of restricting the sender to a specific signalling structure, the sender, who has commitment power, by designing an information mechanism (a set of signals and a probability distribution over them), maximises his payoff, which depends on the mitigation action of countries and the social cost of green-house gases(GHG). The countries, given the information policy (the probability distribution over signals) and the public signal, update their beliefs about the social cost of GHG and take a mitigation action. I derive the optimal information mechanism from the general set of public information mechanisms, in coalition formation games. I show that the coalition size, as a function of beliefs, is an endogenous variable, induced by the information sender. If the sender maximises the expected payoff of either of non-signatories or signatories of the climate treaty, then full revelation is the optimal information policy, while if the sender attempts to reduce the global level of GHG, then optimal information policy leads to imperfect disclosure of the social cost. Furthermore, given any of the specifications of the sender’s payoff, the optimal information policy leads to the socially optimal mitigation and membership outcomes.

Sistemas multiagentes muitas vezes apresentam características que os aproximam de sociedades de agentes e, como as humanas, possuem normas e organizações com o objetivo de coordenar as interações entre os seus membros. Coalizão é um tipo de estrutura organizacional temporária, montada com objetivos específicos. A teoria dos jogos estuda formalmente o fenômeno coalizional, se detendo em demonstrações de propriedades e características dessa estrutura. A área de sistemas multiagentes, por outro lado, tem mostrado significativo interesse nas estruturas coalizionais como forma de organizar a cooperação entre os agentes, dedicando-se ao desenvolvimento de algoritmos para formação de coalizões. Esse trabalho apresenta um algoritmo de formação de coalizões para compartilhamento de recursos, denominado heurística ganha-ganha. Definimos um modelo que utiliza a abstração de recursos para representar tanto a posse de habilidades e objetos, quanto para representar os objetivos dos agentes. Um jogo de votação k-ponderado é utilizado para implementar o processo decisório de quais coalizões são válidas e o algoritmo testa iterativamente cada vizinhança de um agente na busca de associações vantajosas. Demonstramos que o algoritmo incrementa monotonicamente o bem-estar da sociedade e converge para uma estrutura coalizional. Também mostramos empiricamente que a heurística é eficiente para compartilhamento de recursos em situações de abundância de recursos, montando coalizões em poucas iterações e com uma quantidade grande de agentes. / Multiagent systems frequently show characteristics that come closer to agent societies and, like the humans ones, have norms and organizations in order to coordinate the interactions of its members. Coalition is a type of temporary organizational structure, assembled with specific goals. Game theory formally studies the coalitional phenomenon focusing in the demonstrations of properties and characteristics of this structure. The area of multiagent systems, on the other hand, has devoted significant interest in coalition structures as a way to organize cooperation between its members, and has been dedicated to the development of algorithms for coalition formation. This dissertation presents an algorithm to coalition formation named win-win heuristic. We define a model which uses the abstraction of resources to represent either, the possession of abilities and objects, or to represent the agents target. A k-weight voting game is used to implement the decision process of what coalitions are worth and an iteratively algorithm tests each agent neighborhood in the pursue of better associations. We demonstrate that the algorithm monotonically increases the society welfare and converges to a coalitional structure. We also show empirically that the heuristic is efficient for resource sharing in situations of availability of resources, building coalitions with few iterations and a large amount of agents.

En el artículo "NP-completeness in Hedonic Games", identificamos algunas limitaciones significativas de los modelos estándar de juegos cooperativos: A menudo, es imposible alcanzar una organización estable de una sociedad en una cantidad de tiempo razonable. Las implicaciones básicas de estos resultados son las siguientes, Primero, desde un punto de vista positivo, las sociedades están "condenadas" a evolucionar constantemente, más que a alcanzar un estadio de equilibrio en el corto plazo. Segundo, desde una perspectiva normativa, un hipotético organizador de la sociedad debería tomar en consideración las limitaciones prácticas de tiempo a la hora de implementar un orden social estable.Para obtener nuestros resultados, utilizamos el concepto de NP-completitud, que es un modelo bien establecido de complejidad temporal en Ciencias de la Computación. En concreto, nos concentramos en estabilidad grupal y estabilidad individual en juegos hedónicos. Los juegos hedónicos son una clase simple de juegos cooperativos en los que la utilidad de cada individuo viene totalmente determinada por el grupo laboral al que pertenece. Nuestros resultados referentes a la complejidad, expresados en términos de NP-completitud, cubren un amplio espectro de dominios de las preferencias individuales, incluyendo preferencias estrictas, indiferencias en las preferencias o preferencias libres sobre el tamaño de los grupos. Dichos resultados también se cumplen si nos restringimos al caso en el que el tamaño máximo de los grupos es pequeño (dos o tres jugadores)En el artículo "Who is Who in Networks. Wanted: The Key Player" (junto con Antoni Calvó Armengol e Yves Zenou), analizamos un modelo de efectos de grupo en el que los agentes interactúan en un juego de influencias bilaterales. Los juegos no cooperativos con población finita y utilidades linales-cuadráticas, en los cuales cada jugador decide cuánto esfuerzo ejercer, pueden ser interpretados como juegos en red con complementariedades en los pagos, junto con un componente de susitucion global y uniforme, y un efecto de concavidad propia.Para dichos juegos, la acción de cada jugador en un equilibrio de Nash es proporcional a su centralidad de Bonacich en la red de complementariedades, estableciendo así un puente con la literatura de redes sociales. Dicho vínculo entre Bonacich y Nash implica que el equilibrio agregado aumenta con el tamaño y la densidad de la red. También analizamos una política que consiste en seleccionar al jugador clave, ésto es, el jugador que, una vez eliminado del juego, induce un cambio óptimo en la actividad agregada. Proveemos una caracterización geométrica del jugador clave, identificada con una medida de inter-centralidad, la cual toma en cuenta tanto la centralidad de cada jugador como su contribución a la centralidad de los otros.En el artículo "Optimal Targets in Peer Networks" (junto con Antoni Calvó Armengol e Yves Zenou), nos centramos en las consecuencias y limitaciones prácticas que se derivan del modelo de decisiones sobre delincuencia. Las principales metas que aborda el trabajo son las siguientes. Primero, la elección se extiende el concepto de delincuente clave en una red al de grupo clave. En dicha situación se trata de seleccionar de modo óptimo al conjunto de delincuentes a eliminar/neutralizar, dadas las restricciones presupuestarias para aplicar medidas. Dicho problema presenta una inherente complejidad computacional que solo puede salvarse mediante el uso de procedimientos aproximados, "voraces" o probabilísticos. Por otro lado, tratamos el problema del delincuente clave en el contexto de redes dinámicas, en las que, inicialmente, los individuos deciden acerca de su futuro como delincuentes o como ciudadanos que obtienen un salario fijo en el mercado. En dicha situación, la elección del delincuente clave es más compleja, ya que el objetivo de disminuir la delincuencia debe tener en cuenta los efectos en cadena que pueda traer consigo la desaparición de uno o varios delincuentes. Por último, estudiamos la complejidad computacional del problema de elección óptima y explotamos la propiedad de submodularidad de la intercentralidad de grupo, lo cual nos permite acotar el error relativo de la aproximación basada en un algoritmo voraz. / The aim of this thesis work is to contribute to the analysis of the interaction of agents in social networks and groups.In the chapter "NP-completeness in Hedonic Games", we identify some significant limitations in standard models of cooperation in games: It is often impossible to achieve a stable organization of a society in a reasonable amount of time. The main implications of these results are the following. First, from a positive point of view, societies are bound to evolve permanently, rather than reach a steady state configuration rapidly. Second, from a normative perspective, a planner should take into account practical time limitations in order to implement a stable social order.In order to obtain our results, we use the notion of NP-completeness, a well-established model of time complexity in Computer Science. In particular, we concentrate on group stability and individual stability in hedonic games. Hedonic games are a simple class of cooperative games in which each individual's utility is entirely determined by her group. Our complexity results, phrased in terms of NP-completeness, cover a wide spectrum of preference domains, including strict preferences, indifference in preferences or undemanding preferences over sizes of groups. They also hold if we restrict the maximum size of groups to be very small (two or three players).The last two chapters deal with the interaction of agents in the social setting. It focuses on games played by agents who interact among them. The actions of each player generate consequences that spread to all other players throughout a complex pattern of bilateral influences. In "Who is Who in Networks. Wanted: The Key Player" (joint with Antoni Calvó-Armengol and Yves Zenou), we analyze a model peer effects where agents interact in a game of bilateral influences. Finite population non-cooperative games with linear-quadratic utilities, where each player decides how much action she exerts, can be interpreted as a network game with local payoff complementarities, together with a globally uniform payoff substitutability component and an own-concavity effect.For these games, the Nash equilibrium action of each player is proportional to her Bonacich centrality in the network of local complementarities, thus establishing a bridge with the sociology literature on social networks. This Bonacich-Nash linkage implies that aggregate equilibrium increases with network size and density. We then analyze a policy that consists in targeting the key player, that is, the player who, once removed, leads to the optimal change in aggregate activity. We provide a geometric characterization of the key player identified with an inter-centrality measure, which takes into account both a player's centrality and her contribution to the centrality of the others.Finally, in the last chapter, "Optimal Targets in Peer Networks" (joint with Antoni Calvó-Armengol and Yves Zenou), we analyze the previous model in depth and study the properties and the applicability of network design policies.In particular, the key group is the optimal choice for a planner who wishes to maximally reduce aggregate activity. We show that this problem is computationally hard and that a simple greedy algorithm used for maximizing submodular set functions can be used to find an approximation. We also endogeneize the participation in the game and describe some of the properties of the key group. The use of greedy heuristics can be extended to other related problems, like the removal or addition of new links in the network.

Title: An overview of selected social procedures Author: Eva Schlosáriková Department: Department of Political Science Supervisor: RNDr. Ondrej Majer, CSc. This thesis first defines social procedures. These are studied and analyzed by social soft- ware, an emerging interdisciplinary field. This thesis will focus on a prominent social procedure, the coalition bargaining and coalition formation. Basic definition and overview of the coalition theory are introduced. Last chapter will concentrate on Bram's model of the coalition formation and his definition of the stable coalition. Other models of the coalition bargaining are briefly introduced and compared to the Bram's model. Keywords: coalition bargaining, coalition formation, stability of coalition 1