Search

A mesura que augmenten les capacitats dels sistemes robòtics, també ho fa el seu potencial per ser desplegats en entorns dinàmics i altament interactius. Aquest informe es centra en el repte de raonar sobre la coordinació i la seguretat en escenaris on els agents robòtics han de planificar tenint en compte el comportament d'altres actors en l'entorn. L'escrit presenta dos projectes en els quals he treballat durant la meva investigació com a part de the Safe Robotics Lab de Princeton University que utilitzen la teoria de jocs dinàmics per abordar el problema de la interacció entre múltiples agents., A medida que aumentan las capacidades de los sistemas robóticos, también lo hace su potencial para ser desplegados en entornos dinámicos y altamente interactivos. Este informe se centra en el desafío de razonar sobre la coordinación y la seguridad en escenarios donde los agentes robóticos tienen que planificar teniendo en cuenta el comportamiento de otros actores en el entorno. El cuerpo principal del trabajo presenta dos proyectos en los que he trabajado durante mi investigación como parte de the Safe Robotics Lab de Princeton University que emplean la teoría de juegos dinámicos para abordar el problema de la interacción entre múltiples agentes., As robotic systems capabilities increase so does their potential for being deployed in dynamic and highly interactive environments. This report focuses on the challenge of reasoning about coordination and safety in scenarios where robotic agents have to plan while taking into account the behavior of other actors in the environment. The main body of the work presents two projects I've worked on during my research at Princeton University's Safe Robotics Lab which leverage dynamic game theory to approach the problem of multi-agent interaction., Outgoing

The addition of fibres to concrete is an effective solution for enhancing its post-cracking tensile strength (fctR). Currently, this property is characterized through high-cost and time-consuming experimental tests since no reliable analytical methods exist to predict this mechanical property. This study provides two neural networks for predicting the fctR obtained from flexural beam tests for crack mouth opening displacements of 0.50 mm (fR1) and 2.50 mm (fR3). Network architectures are obtained with an optimization process that involved training 1568 Multi-Layer Perceptron configurations under Monte Carlo cross-validation over 50 iterations, with a total of 78,400 trainings for each fR,i. The resulting models were evaluated using performance metrics including Coefficient of Determination (R2), Correlation Coefficient (CC), Mean Absolute Error (MAE), Root Mean Square Error (RMSE) and Scatter index (SI). High predictive accuracies were achieved for both fR1 (R2 = 0.87, CC = 0.93, MAE = 0.64 MPa, RMSE = 0.90 MPa, SI = 19.2%) and fR3 (R2 = 0.85, CC = 0.92, MAE = 0.73 MPa, RMSE = 0.95 MPa, SI = 19.8%). Furthermore, the analysis of their global and local interpretability through the game-theory-based SHAP explanation method confirms their consistency with established understandings of fibre-reinforced concrete (FRC) behaviour. Moreover, numerical expressions are proposed as an alternative to traditional testing methods, offering a tool to predict the flexural post-cracking tensile strength for pre-design and quality control purposes of FRC structures. These approaches are deemed essential for advancing FRC technology marking a significant advancement in addressing the design limitations and widespread application challenges associated with the material., This work was supported by the Catalan agency AGAUR through its research group support program (2021 SGR 00341) and by the Spanish Ministry of Science and Innovation under the scope of project CREEF (PID2019-108978RB-C32/AEI/10.13039/ 501100011033)., Peer Reviewed, Postprint (author's final draft)

© 2023 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., We consider a large population of decision makers that choose their evolutionary strategies based on simple pairwise imitation rules. We describe such a dynamic process by the replicator dynamics. Differently from the available literature, where the payoffs signals are assumed to be updated continuously, we consider a more realistic scenario where they are updated occasionally. Our main technical contribution is to devise two event-triggered communication schemes with asymptotic convergence guarantees to a Nash equilibrium. Finally, we show how our proposed approach is applicable as an efficient distributed demand response mechanism., This research was supported by the project PID2020-115905RB-C21 (L-BEST) funded by MCIN/ AEI /10.13039/501100011033, the ERC under research project COSMOS (802348), and the project BPIN 2021000100499 funded by CTeI - SGR and MinCiencias, Colombia., Peer Reviewed, Postprint (author's final draft)

The paper that introduces the Felsenthal index is titled: ‘A well-behaved index of a priori P-Power for simple n-person games.’ In 2016, Felsenthal introduced his index for simple games. His definition does not base on the axiomatic approach. Then, Felsenthal regarded some properties and proved that his index satisfies a list of six reasonable and compelling postulates. Three of the properties that he regarded refer to the weighted games, but this fact does not reduce the definition of his index to weighted games. He proves that none of seven well-known efficient power indices proposed to date satisfies the list of postulates, indicating for each of them which of the six postulates violate. In this paper we extend some of his postulates, originally defined for weighted games, to simple games. The main objective of the article is to answer three open questions motivated in his article. In particular, we prove that his index may not be the unique one fulfilling the six proposed postulates, provide an axiomatic characterization for his index and, propose an impossibility result, which is obtained by adding a new postulate to a sublist of the postulates he considered. We also remark the existence of some alternative compelling postulates which are not satisfied for the index., This research is part of the I+D+i project PID2019-104987GB-I00 supported by MCIN/AEI/10.13039/501100011033/. We thank José María Alonso-Meijide for his comments and suggestions, which helped us to improve the manuscript. We greatly appreciate the comments of two referees that have contributed to improve this work., Peer Reviewed, Postprint (published version)

En Teoria de Jocs, un Joc de Creació de Xarxes modela la creació d'una xarxa descentralitzada, com per exemple Internet, deixant que diferents agents construeixin la xarxa segons diversos criteris. Aquest projecte estudia un nou model basat en fluxos sobre xarxes que representa l'alta demanda en amplada de banda que tenen els serveis de reproducció en línia moderns. L'article original defineix el model i inclou demostracions sobre propietats de Teoria de Jocs. Entre els seus resultats hi trobem la demostració de l'existència d'Equilibris de Nash Purs, una manera de construir xarxes òptimes, un valor exacte pel Preu de l'Estabilitat i una cota quasi exacta en el Preu de l'Anarquia. A més a més, també demostren que la Dinàmica del Joc pot entrar en un bucle quan els agents juguen una millor resposta. El nostre objectiu principal és fer una recerca empírica i teòrica de les propietats topològiques dels Equilibris de Nash i de les xarxes Socialment Òptimes en aquest model de Creació de Xarxes basat en Fluxos. En concret, volem estudiar el temps necessari perquè la Dinàmica de Jocs convergeixi i estudiar la connectivitat i la topologia de les xarxes obtingudes en la Dinàmica i comparar-les en contra dels dos models presentats en l'article. Per fer això, durem a terme diversos experiments en una simulació de la Dinàmica de Jocs quan els agents juguen la seva Millor Resposta., In Game Theory, a Network Creation Game models the creation of decentralized networks such as the Internet, by letting different agents build the network based on different criteria. This project studies a new model based on flow on networks that aims to represent the high-demand bandwidth of modern streaming services. The original article defines the model and includes demonstrations on properties of Game Theory. Their main results are the proof of existence of pure Nash equilibrium networks, a way of building optimal networks, an exact value for the Price of Stability and an almost tight bound for the Price of Anarchy. Furthermore, it is shown that the Game Dynamics can cycle when agents play a better response. Our main goal of this work is to make a theoretical and empirical research of topological properties of Nash Equilibrium and Social Optimum networks in this Flow-Based Network Creation Games. Especially, we want to study the time needed for convergence in the Best Response Game Dynamics and the connectivity and topology of the achieved networks in the Dynamics and compare them against the two models presented in the article. For this we will make a simulation of a Best Response Game Dynamics of this model and conduct various experiments with it.

En este artículo, consideramos el marco de dinámicas evolutivas y juegos poblacionales. Para una clase de dinámicas evolutivas y una familia de juegos poblacionales contractivos, desarrollamos un método novedoso para la búsqueda distribuida de equilibrios de Nash bajo información parcial respecto a las decisiones de los demás agentes. La principal contribución es que establecemos condiciones suficientes para garantizar la estabilidad asintótica del conjunto de equilibrios de Nash del juego poblacional subyacente. Además, ilustramos nuestros resultados teóricos en una aplicación numérica de un juego de congestión de gran escala., Juan Martinez-Piazuelo agradece a la Universitat Politécnica de Catalunya y al Banco Santander, España, por la financiación de su beca FPI-UPC. Adicionalmente, los autores agradecen a los proyectos PID2020-115905RB-C21 (L-BEST) y TED2021-129927B-I00 (MASHED), financiados por MCIN/ AEI/10.13039/501100011033 y por la European Union Next GenerationEU/PRTR, por financiar esta investigación. Finalmente, Nicanor Quijano agradece el proyecto BPIN2021000100499, de la asignación para CTeI-SGR y Minciencias., Peer Reviewed, Postprint (published version)

This paper addresses the problem of distributed Nash equilibrium (NE) seeking in strongly contractive aggregative multi-population games subject to partialdecision information. In particular, we consider the scenario where the so-called payoff providers of the multiple populations communicate through a possibly noncomplete network, and we formulate some consensus-like dynamics for the payoff providers to distributedly compute their payoff signals using local information only. Moreover, by exploiting the notions of d-passivity and d-antipassivity, we provide a unified analysis for several classes of evolutionary game dynamics. As the main contributions, we provide sufficient conditions to guarantee the d-antipassivity of a class of continuous-time dynamical systems, and we exploit such results to design distributed NE seeking dynamics for strongly contractive aggregative population games, as well as for a class of merely contractive aggregative population games. To the best of our knowledge, this is the first paper to consider the problem of distributed NE seeking for such classes of population games and from a unifying passivity-based perspective., This research has been supported by the projects PID2020-115905RB-C21 (LBEST) and TED2021-129927B-I00 (MASHED) funded by MCIN/AEI /10.13039/501100011033, and by the project BPIN2021000100499 funded by CTeI-SGR and MinCiencias,Colombia., Peer Reviewed, Postprint (published version)

We developed a mixed-strategy gaming approach for distributed and real-time optical subscarrier management in point-to-multipoint networks, achieving traffic loss rates close to those by ILP-based centralized optimization., This work was supported in part by NSFC under Project 62201627, by the European Commission though the HORIZON SEASON (G.A. 101096120) projects, by the MICINN IBON (PID2020-114135RB-I00) project and from the ICREA institution., Peer Reviewed, Postprint (author's final draft)

In voting theory and social choice theory, decision systems can be represented as simple games, i.e., cooperative games defined through their players or voters and their set of winning coalitions. The weighted voting games form a well-known strict subclass of simple games, where each player has a voting weight so that a coalition wins if the sum of weights of their members exceeds a given quota. Since the number of winning coalitions can be exponential in the number of players, simple games can be represented much more compactly as intersections or unions of weighted voting games. A simple game’s dimension (codimension) is the minimum number of weighted voting games such that their intersection (union) is the given game. It is known there are voting systems with a high (co)dimension. This work introduces the multidimension as the minimum size of an expression with intersections and unions on weighted voting games necessary to obtain the considered simple game. We generalize this notion to subclasses of weighted voting games and analyze the generative properties of these subclasses. We also characterize the simple games with finite generalized multidimension over the set of weighted voting games without dummy players. We provide a comprehensive classification for simple games up to a certain number of players. These results complement similar classification results for generalized (co)dimensions. Our results show how generalized multidimension allows representing more simple games and more compactly, even for a small number of players and for subclasses., "Xavier Molinero was partially supported by the Spanish Ministry of Economy and Competitiveness (MINECO) and the European Union (FEDER funds) [PID2019-104987GB-I00, JUVOCO]. Fabián Riquelme was supported by the Fondecyt de Iniciación 11200113 from ANID, Chile. Maria Serna was partially supported by the Spanish Agencia Estatal de Investigación [PID-2020-112581GB-C21, MOTION]. Xavier Molinero, Salvador Roura, and Maria Serna were also partially supported by the Catalan government [2021 SGR 01419 ALBCOM]", Peer Reviewed, Postprint (published version)

© 2023. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0, Many real-world voting systems consist of voters that occur in just two different types. Indeed, each voting system with a “House” and a “Senate” is of that type. Here we present structural characterizations and an explicit enumeration formula for these so-called bipartite simple games. This formula extends some partial enumerations of simple games related to completeness or the number of minimal winning coalitions., This paper is part of the project PID2019-104987GB-I00 financed by MCIN/AEI/10.13039/ 501100011033., Postprint (author's final draft)

We study the complexity of computing the Banzhaf index in incompatibility games. We show: 1) weak #P-completeness for computing the index when the incompatibility graph has very few maximal independent sets, 2) strong #P-completeness if the incompatibility graph is co-planar and perfect, 3) weak NP-completeness for deciding whether the index is non-zero when the incompatibility graph has few maximal independent sets. Finally, we discuss the possible existence of pseudopolynomial time algorithms to compute the index for some classes of incompatibility graphs.

Weighted voting games are simple games that can be represented by a collection of integer weights for each player so that a coalition wins if the sum of the player weights matches or exceeds a given quota. It is known that a simple game can be expressed as the intersection or the union of weighted voting games. The dimension (codimension) of a simple game is the minimum number of weighted voting games such that their intersection (union) is the given game. In this work, we analyze some subclasses of weighted voting games and their closure under intersection or union. We introduce generalized notions of dimension and codimension regarding some subclasses of weighted voting games. In particular, we show that not all simple games can be expressed as intersection (union) of pure weighted voting games (those in which dummy players are not allowed) and we provide a characterization of such simple games. Finally, we experimentally study the generalized dimension (codimension) for some subclasses defined by establishing restrictions on the representations of weighted voting games, Peer Reviewed, Postprint (author's final draft)

© 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting /republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works, This paper investigates the problem of generalized Nash equilibrium (GNE) seeking in population games under the Brown-von Neumann-Nash dynamics and subject to general affine equality constraints. In particular, we consider that the payoffs perceived by the decision-making agents are provided by a so-called payoff dynamics model (PDM), and we show that an appropriate PDM effectively steers the agents to a GNE. More formally, using Lyapunov stability theory, we provide sufficient conditions to guarantee the asymptotic stability of the set of generalized Nash equilibria of the game, for the case when the game is a so-called stable game (also known as contractive game). Furthermore, we illustrate the application of the considered framework to an energy market game considering coupled equality constraints over the players decisions., Peer Reviewed, Postprint (author's final draft)

This is an Accepted Manuscript of an article published by Taylor & Francis in Optimization on 13 Dec 2022, available at: http://www.tandfonline.com/10.1080/02331934.2022.2154126., This paper considers inequivalent monotone Boolean functions of an arbitrary number of variables, two monotone Boolean functions are equivalent if one can be obtained from the other by permuting the variables. It focuses on some inequivalent monotone Boolean functions with three and four types of equivalent variables, where the variables are either dominant or dominated. The paper provides closed formulas for their enumeration as a function of the number of variables. The problem we deal with is very versatile since inequivalent monotone Boolean functions are monotonic simple games, structures that are used in many fields such as game theory, neural networks, artificial intelligence, reliability or multiple-criteria decision-making., This publication is part of the I+D+i project/PID2019-104987GB-I00, financed by MCIN/AEI/10.13039/501100011033/; Spanish Ministry of Science and Innovation., Peer Reviewed, Postprint (author's final draft)

Many decision-making situations require the evaluation of several voters or agents. In a situation where voters evaluate candidates, the question arises of how best to aggregate evaluations so as to compare the candidates. The aim of this work is to propose a method of aggregating the evaluations of the voters, which has outstanding properties and serve as a potential evaluative tool in many contexts. Ordered weighted averages is a family of rules appropriate for studying this problem. In this paper, I propose as a solution an ordered weighted average that satisfies compelling properties and whose weights are derived from the binomial distribution., This research is part of the I+D+i project PID2019-104987GB-I00 supported by MCIN/AEI/10.13039/501100011033/., Peer Reviewed, Postprint (published version)

This thesis focuses on positional games. Positional games is a branch of mathematics that studies two- player games of perfect information. Maker-Breaker positional games will be of special interest, and more precisely, biased Maker-Breaker games, introduced by Chvatal and Erdös, will be widely studied. The main interest in the study of biased Maker-Breaker games is to determine the so-called threshold bias. In this thesis, a study of Maker-Breaker games in general is done, and finally some specific games are analysed. In the last chapter, the new result of the thesis is presented, giving a strategy for the Schur s game, that improves the existing bound for the critical bias of this game.

© 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., In the present, there are different indices that measure the difficulty level of reading a text, i.e. the readability of a text. Different studies have been made on the frequency of occurrence of letters in several languages, but as we know there are not thorough studies on the occurrence of letters according to the readability of a text. The main objective of the present work is to study the frequency of occurrence of letters in a text according to its legibility. This occurrence will be approached from two points of view. First, through the so-called power indices of game theory. To the best of our knowledge, it is the first time that a game is associated with a text and the influence or power of each letter will be analysed by means of the so-called power indices of the game theory. Thus, we present a new application of game theory. Second, by means of basic statistics to study relative frequency of letters in a text., Peer Reviewed, Postprint (author's final draft)

This brief proposes a novel decision-making model for generalized Nash equilibrium seeking in the context of full-potential population games under capacity and migration constraints. The capacity constraints restrict the mass of players that are allowed to simultaneously play each strategy of the game, while the migration constraints introduce a networked interaction structure among the players and rule the strategic switches that players can make. In this brief, we consider both decoupled capacity constraints regarding individual strategies, as well as coupled capacity constraints regarding disjoint groups of strategies. As main technical contributions, we prove that the proposed decision-making protocol guarantees the forward time invariance of the feasible set, and we provide sufficient conditions on the connectivity level of the migration graph to guarantee the asymptotic stability of the set of generalized Nash equilibria of the underlying game when the game is a full-potential population game with concave potential function. Furthermore, we also provide an alternative discrete-time analysis of the proposed evolutionary game dynamics, which allows us to formulate a population-game-inspired distributed optimization algorithm that guarantees the hard satisfaction of the constraints over all iterations. Finally, the theoretical results are validated numerically on a constrained networked congestion game., Juan Martinez-Piazuelo gratefully acknowledges the Universitat Politècnica de Catalunya and Banco Santander for the financial support of his predoctoral grant FPI-UPC. In addition, the authors would like to thank the project PID2020-115905RB-C21 (L-BEST) funded by MCIN/ AEI /10.13039/501100011033 for supporting this research., Peer Reviewed, Preprint

The game theory started as a mathematical exploration of human behaviours. The term has expanded to cover this mathematical exploration of the decision-making not only of humans but also of animals and computers. Through this project, we will be able to study how can we integrate the mathematical aspect of a specific topic from game theory into a development of a game. Furthermore, what advantages or inconveniences can we find on our way to integrating this field into game development? First, we must focus on learning key concepts about game theory topics, specifically Game Trees and subgame perfect equilibrium. These concepts will help us create a game tree and calculate the decision-making values, so later, it becomes easier to mix with other concepts once we accomplish the research. When we look at a game tree, we can easily relate some similarities with another well-known video game system. These systems are narrative trees or decision trees. So the main focus of this project is to create a game prototype where a player has to make decisions like in a narrative game. However, instead of a standard decision tree, we will investigate making this tree with the concepts learned through game theory. The key to success will be learning how to create a game tree and combining this with some psychology so players can feel that their decisions have some value, as we would see in a game tree. All these challenges will illustrate through the development part of the project.

Este artículo se centra en resaltar la basta utilidad de la teoría de juegos, en particular aquella basada en la vertiente dinámica evolutiva, dentro del modelado y control de sistemas dinámicos complejos y de gran escala. Concretamente, y a través de ejemplos claros y de aplicación real, se motiva el uso de las dinámicas poblacionales para el modelado de sistemas ciberfísicos, así como los modelos dinámicos de pago para complementar un sistema de control en lazo cerrado con restricciones (físicas y operacionales), cuyos objetivos se alinean con la distribución dinámica de recursos y el alcance de equilibrios generalizados de Nash., This paper focuses on highlighting the vast usefulness of game theory, particularly that based on the evolutionary dynamic branch, within the modeling and control of complex and large-scale dynamic systems. Specifically, and through clear examples of real application, the use of population dynamics for modeling cyber-physical systems is motivated, as well as dynamic payment models to complement a closed-loop control system with restrictions (physical and operational), whose objectives are aligned with the dynamic resource allocation and the reachment of generalized Nash equilibria., Los autores agradecen al proyecto PID2020115905RB-C21 (L-BEST) financiado por MCIN/ AEI /10.13039/501100011033., Peer Reviewed, Postprint (author's final draft)

En aquesta tesi, posem a prova en el laboratori un model sobre comptabilitat electoral i corrupció en carreres polítiques. Partint del model de teoria de jocs de Martinelli (2022), l'estudiem utilitzant les teories d'equilibri bayesià i d'equilibri quantal d'agents per predir les accions tant dels polítics com els votants. Trobem que el remordiment per agafar un suborn explica el comportament dels polítics i que els jugadors no sempre estan atents al joc., En esta tesis, ponemos a prueba en el laboratorio un modelo sobre contabilidad electoral y corrupción en carreras políticas. Partiendo del modelo de teoría de juegos de Martinelli (2022), lo estudiamos utilizando las teorías de equilibrio bayesiano y de equilibrio quantal de agentes para predecir las acciones tanto de los políticos como de los votantes. Encontramos que el remordimiento por la toma de sobornos explica el comportamiento de los políticos y que los jugadores no siempre están atentos al juego., In this thesis, we test in the lab a model about electoral accountability and corruption in political careers. Starting from a game-theory model by Martinelli (2022), we study it using the Bayesian equilibrium and Agent Quantal Response equilibrium theories to make predictions about the actions of both politicians and voters. We find that the regret for taking bribes explains the behavior of politicians and that players do not always pay attention to the game., Outgoing

© 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., In this paper, we consider the framework of population games and evolutionary dynamics. Based on such a framework, we formulate a novel approach for distributed Nash equilibrium seeking under partial-decision information for a class of evolutionary dynamics and a family of contractive population games. As the main contribution, we provide sufficient conditions to guarantee the asymptotic stability of the set of Nash equilibria of the underlying game. To the best of our knowledge, this is the first paper to address the problem of distributed Nash equilibrium seeking under partial-decision information in the aforementioned context of population games and evolutionary dynamics., The authors would like to thank the project PID2020-115905RB-C21 (L-BEST) funded by MCIN/AEI /10.13039/501100011033 for supporting this research., Peer Reviewed, Postprint (author's final draft)

An influence game is a simple game represented over an influence graph (i.e., a labeled, weighted graph) on which the influence spread phenomenon is exerted. Influence games allow applying different properties and parameters coming from cooperative game theory to the contexts of social network analysis, decision-systems, voting systems, and collective behavior. The exact calculation of several of these properties and parameters is computationally hard, even for a small number of players. Two examples of these parameters are the length and the width of a game. The length of a game is the size of its smaller winning coalition, while the width of a game is the size of its larger losing coalition. Both parameters are relevant to know the levels of difficulty in reaching agreements in collective decision-making systems. Despite the above, new bio-inspired metaheuristic algorithms have recently been developed to solve the NP-hard influence maximization problem in an efficient and approximate way, being able to find small winning coalitions that maximize the influence spread within an influence graph. In this article, we apply some variations of this solution to find extreme winning and losing coalitions, and thus efficient approximate solutions for the length and the width of influence games. As a case study, we consider two real social networks, one formed by the 58 members of the European Union Council under nice voting rules, and the other formed by the 705 members of the European Parliament, connected by political affinity. Results are promising and show that it is feasible to generate approximate solutions for the length and width parameters of influence games, in reduced solving time, "Funding Statement: F. Riquelme has been partially supported by Fondecyt de Iniciación 11200113, Chile, and by the SEGIB scholarship of Fundación Carolina, Spain; X. Molinero under grants PID2019-104987GB-I00 (JUVOCO); M. Serna under grants PID2020-112581GB-C21 (MOTION) and 2017-SGR-786 (ALBCOM)", Peer Reviewed, Postprint (published version)

This letter proposes a novel form of continuous-time evolutionary game dynamics for generalized Nash equilibrium seeking in equality-constrained population games. Using Lyapunov stability theory and duality theory, we provide sufficient conditions to guarantee the asymptotic stability, non-emptiness, compactness, and optimality of the equilibria set of the proposed dynamics for certain population games. Moreover, we illustrate our theoretical developments through a numerical simulation of an equality-constrained congestion game., Peer Reviewed, Postprint (author's final draft)

This paper studies the problem of generalized Nash equilibrium seeking in population games under general affine equality and convex inequality constraints. In particular, we design a novel payoff dynamics model to steer the decision-making agents to a generalized Nash equilibrium of the underlying game, i.e., to a self-enforceable state where the constraints are satisfied and no agent has incentives to unilaterally deviate from her selected strategy. Moreover, using Lyapunov stability theory, we provide sufficient conditions to guarantee the asymptotic stability of the corresponding equilibria set in stable population games. Auxiliary results characterizing the properties of the equilibria set are also provided for general continuous population games. Furthermore, our theoretical developments are numerically validated on a Cournot game considering various market-related and production-related constraints., Juan Martinez-Piazuelo gratefully acknowledges the Universitat Politècnica de Catalunya, Spain and Banco Santander, Spain for the financial support of his predoctoral grant FPI-UPC, Spain . In addition, the authors would like to thank the project PID2020-115905RB-C21 (L-BEST) funded by MCIN/ AEI /10.13039/501100011033 for supporting this research. Finally, Nicanor Quijano would like to thank the UK-PACT Project (2019-2021), Systemic perspectives on low-carbon cities in Colombia – An integrated urban modelling approach for policy and regulatory analysis., Peer Reviewed, Postprint (published version)

En aquesta tesi de grau estudiem el model de Jocs de Formació de Xarxa amb atac i immunització introduït per Goyal et al. El model consta d'agents que volen maximitzar el benefici per connectar-se amb altres agents, fet que implica el cost de crear connexions. A més, un adversari atacarà la xarxa generada pels agents i els agents poden decidir immunitzar-se contra l'atac pagant un cost addicional. Goyal et al. van proposar diferents tipus d'adversaris. L'objectiu és comprendre el model enfocant-se a l'adversari d'atac aleatori i obtenir resultats de connectivitat, benestar social, diversitat de xarxes d'equilibri i dinàmiques de millor resposta basats en treballs previs. Pel que fa a l'adversari d'atac aleatori, demostrem que quan el cost de crear una aresta CE > 1 la xarxa d'equilibri no trivial (amb almenys una aresta i almenys un vèrtex immunitzat) resultant G és un graf connex, i quan CE i el cost de la immunització CI són constants i CE > 1, llavors el benestar de G és n^2-O(n^(5/3)). També estudiem la diversitat de xarxes d'equilibri i demostrem que entre els tipus de xarxes d'equilibri per l'adversari de màxima matança presentat per Goyal et al., graf nul, arbres, cicles, flors i graf bipartit complet també són equilibris per l'adversari d'atac aleatori amb lleugera diferència als paràmetres, les xarxes bosc tenen un cas particular d'equilibri per l'adversari d'atac aleatori però en general són només equilibri respecte a l'adversari de màxima matança. Finalment, estudiem la convergència de la dinàmica de millor resposta pel que fa a l'adversari d'atac aleatori i demostrem que pot ciclar. Concloem la nostra recerca amb una simulació de la dinàmica de millor resposta, observem que convergeix ràpidament a un equilibri eficient per l'adversari d'atac aleatori., In this bachelor thesis we study the Network Formation Games model with attack and immunization introduced by Goyal et al. The model consists of agents who want to maximize their benefit by connecting with other agents, which involves the cost of creating connections. Furthermore, an adversary will attack the network generated by agents and the agents can decide to immunize against the attack paying an additional cost. Different types of adversaries were proposed by Goyal et al. The objective is to gain an understanding of the model focusing on the random attack adversary and obtain results of connectivity, social welfare, diversity of equilibrium networks and best response dynamics based on previous works. With respect to the random attack adversary we prove that when cost of creating an edge CE > 1 the resulting non-trivial equilibrium network (with at least one edge and at least one immunized vertex) G is a connected graph, and when CE and cost of immunization CI are constants and CE > 1 then the welfare of G is n^2-O(n^(5/3)). We also study the diversity of equilibrium networks and we show that among the types of equilibrium networks for the maximum carnage adversary presented by Goyal et al., empty graph, trees, cycles, flowers and complete bipartite graph are also equilibria for the random attack adversary with slight difference in parameters, the forest networks have a particular case of equilibrium for the random attack adversary but in general they are only equilibrium with respect to the maximum carnage adversary. Finally, we study the convergence of the best response dynamics with respect to the random attack adversary and we prove that it can cycle. We conclude our research with a simulation of the best response dynamics, we observe that it converges rapidly to an efficient equilibrium for the random attack adversary.

Este proyecto ha tenido como objetivo principal la construcción de un robot capaz de jugar autónomamente al conocido juego 2048. Se puede desglosar el trabajo en dos grandes partes: una de software y una de hardware. En lo que respecta a la primera, se ha realizado un análisis inicial de diversos aspectos del juego y se ha comparado distintos métodos de resolución, principalmente minimax, expectimax y redes neuronales. De todos estos métodos se han propuesto multitud de variantes en las que se han añadido diversas características como, por ejemplo, las distintas heurísticas para evaluar los nodos del árbol de búsqueda en los métodos minimax y expectimax o distintas arquitecturas en el caso de las redes neuronales. En cuanto al hardware, se ha construido un robot ideado para ser posicionado delante de la pantalla de un ordenador con el juego abierto e interaccionar con el ordenador, dando las órdenes de movimiento a través del puerto USB. El robot incorpora una placa Raspberry Pi 4, una placa Pro Micro ATmega32u4, una cámara y componentes de soporte, todo ello, dentro de una carcasa hecha a partir de modelado e impresión 3D., The main objective of this project was the construction of a robot capable of autonomously playing the well-known game 2048. The work has two main parts: software and hardware. Regarding the first, an initial analysis of various aspects of the game has been carried out and different resolution methods have been compared, mainly minimax, expectimax and neural networks. Many variants of all these methods have been proposed in which various features have been added, such as, for example, the different heuristics to evaluate the nodes of the search tree in the minimax and expectimax methods or different architectures in the case of neural networks. For the hardware, a robot has been built and designed to be positioned in front of a computer screen with the game open and interact with the computer, giving movement orders through the USB port. The robot incorporates a Raspberry Pi 4 board, a Pro Micro ATmega32u4 board, a camera and supporting components, all inside a 3D modelled and printed case.

In this project we study the dynamic behaviour of Strategic Network Formation Games with attacks and immunization introduced by Goyal et al., 2016. This model takes Reachability Network Formation Games introduced by Bala et al., 2000, and introduces an adversarial attack, as well as immunization against the attack. The benefit of each agent is the expected size of her connected component post-attack (as in the Reachability Network Formation Games, forming links has a cost), and agents may choose to immunize at some additional cost. In this project we expand the experimental study conducted by Goyal et al. We do a systematical study of the topology of the swapstable equilibria found with different initial configurations. We then extend the model to a new one in which we give more power to the adversary, and we do an experimental research on the swapstable equilibria found. We again focus on the topologies found with different initial configurations. Finally, we compare the results obtained with both models., En aquest projecte estudiem el comportament dinàmic dels Strategic Network Formation Games with attacks and immunization introduïts per Goyal et al., 2016. Aquest model agafa els Reachability Network Formation Games introduïts per Bala et al., 2000, i introdueix l'atac d'un adversari, així com immunització contra l'atac. El benefici de cada agent és el tamany esperat del seu component connex després de l'atac (com en els Reachability Network Formation Games, formar enllaços té un cost), i els agents poden escollir immunitzar-se amb un cost addicional. En aquest projecte ampliem l'estudi experimental dut a terme per Goyal et al. Fem un estudi sistemàtic de la topologia dels swapstable equilibria trobats amb diferents configuracions inicials. Després estenem el model a un de nou en què donem més poder a l'adversari, i fem una recerca experimental sobre els swapstable equilibria trobats. Ens tornem a centrar en les topologies trobades amb diferents configuracions inicials. Finalment, comparem els resultats obtinguts amb els dos models.

A connected and undirected graph G of size n≥1 is said to be a sum basic equilibrium iff for every edge uv from G and any node v′ from G, when performing the swap of the edge uv for the edge uv′ the sum of the distances from u to all the other nodes is not strictly reduced. This concept comes from the so called Network Creation Games, a wide subject inside Algorithmic Game Theory that tries to better understand how Internet-like networks behave. It has been shown that the diameter of sum basic equilibria is 2O(logn√) in general and at most 2 for trees. In this paper we see that the upper bound of 2 not only holds for trees but for bipartite graphs, too. Specifically, we show that the only bipartite sum basic equilibrium networks are the complete bipartite graphs Kr,s with r,s≥1 ., This work has been partially supported by funds from the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R) and from the Catalan Agency for Management of University and Research Grants (AGAUR, Generalitat de Catalunya) under project ALBCOM 2017-SGR-786., Peer Reviewed, Postprint (author's final draft)

In this paper, we analyze the frequency distributions of weights and quotas in weighted majority voting games (WMVG) up to eight players. We also show different procedures that allow us to obtain some minimum or minimum sum representations of WMVG, for any desired number of players, starting from a minimum or minimum sum representation. We also provide closed formulas for the number of WMVG with n players having a minimum representation with quota up to three, and some subclasses of this family of games. Finally, we complement these results with some upper bounds related to weights and quotas., Peer Reviewed, Postprint (published version)

In this paper we discuss on several ways to extend power indices defined on simple games to the context of (j, 2)-games, i.e., games with 2 possible outputs and j possible input levels. The purpose of this paper is more conceptual than technical, and shows that different power indices can be obtained in (j, 2)-games depending on how the criticality of a player is measured. Some power indices for simple games, regarded as measures of power as payment, can be obtained from the selection of two items: (1) a probabilistic model, and (2) a collection of winning coalitions. The combination of two particular probabilistic models and three collections of winning coalitions lead to six well-known power indices for simple games. The Banzhaf and the Johnston power indices are among them. The main goal of the paper is to discuss the generalizations of these six power indices from (2, 2)-games to (j, 2)-games for j=3. The probabilistic model and the collection of winning coalitions are trivially extendable to (j, 2)-games. However, at least four possible ways of measuring the criticality of a player can be considered in this new context, and lead to different possible extensions of the six power indices to (j, 2)-games. We highlight two of them as being the most interesting under our point of view. The first one would be suitable for assessing sensitivity, because it measures the player’s ability to modify the output by a small change in his input level. The second one would be adequate to evaluate strength, because it measures the voter’s ability to modify the output by any change in his voting. The main conclusion is that different extensions of the considered power indices, as the Banzhaf and the Jonnston indices, are possible for j=3 and that they should be taken into account when working in a multiple input context., This research was partially supported by funds from the Spanish Ministry of Economy and Competitiveness (MINECO) and from the European Union (FEDER funds) under grant MTM2015-66818-P(MINECO/FEDER)., Peer Reviewed, Postprint (author's final draft)

This work proposes a novel data-driven distributed formation-control approach based on multi-population evolutionary games, which is structured in a leader-follower scheme. The methodology considers a time-varying communication graph that describes how the multiple agents share information to each other. We present stability guarantees for configurations given by time-varying interaction networks, making the proposed method suitable for real-world problems where communication constraints change along the time. Additionally, the proposed formation controller allows for an agent to leave or enter the group without the need to modify the behaviors of other agents in the group. This game-theoretical approach is evaluated through numerical simulations and real outdoors experimental results using a fleet of aerial autonomous vehicles, showing the control performance., Peer Reviewed, Postprint (author's final draft)