Search

Recent years have seen the application of deep reinforcement learning techniques to cooperative multi-agent systems, with great empirical success. However, given the lack of theoretical insight, it remains unclear what the employed neural networks are learning, or how we should enhance their learning power to address the problems on which they fail. In this work, we empirically investigate the learning power of various network architectures on a series of one-shot games. Despite their simplicity, these games capture many of the crucial problems that arise in the multi-agent setting, such as an exponential number of joint actions or the lack of an explicit coordination mechanism. Our results extend those in Castellini et al. (Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS’19.International Foundation for Autonomous Agents and Multiagent Systems, pp 1862–1864, 2019) and quantify how well various approaches can represent the requisite value functions, and help us identify the reasons that can impede good performance, like sparsity of the values or too tight coordination requirements. [ABSTRACT FROM AUTHOR]

While outdoor advertisements are common features within towns and cities, they may reinforce social inequalities in health. Vulnerable populations in deprived areas may have greater exposure to fast food, gambling and alcohol advertisements, which may encourage their consumption. Understanding who is exposed and evaluating potential policy restrictions requires a substantial manual data collection effort. To address this problem we develop a deep learning workflow to automatically extract and classify unhealthy advertisements from street-level images. We introduce the Liverpool 360 ∘ Street View (LIV360SV) dataset for evaluating our workflow. The dataset contains 25,349, 360 degree, street-level images collected via cycling with a GoPro Fusion camera, recorded Jan 14th–18th 2020. 10,106 advertisements were identified and classified as food (1335), alcohol (217), gambling (149) and other (8405). We find evidence of social inequalities with a larger proportion of food advertisements located within deprived areas and those frequented by students. Our project presents a novel implementation for the incidental classification of street view images for identifying unhealthy advertisements, providing a means through which to identify areas that can benefit from tougher advertisement restriction policies for tackling social inequalities. [ABSTRACT FROM AUTHOR]

We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same time (for example, by solving a single LP that combines the two players' payoffs), our algorithm first solves two independent LPs, each of which is derived from one of the two payoff matrices, and then computes an approximate Nash equilibrium using only limited communication between the players. Our method gives improved bounds on the complexity of computing approximate Nash equilibria in a number of different settings. Firstly, it gives a polynomial-time algorithm for computing approximate well supported Nash equilibria (WSNE) that always finds a 0.6528-WSNE, beating the previous best guarantee of 0.6608. Secondly, since our algorithm solves the two LPs separately, it can be applied to give an improved bound in the limited communication setting, giving a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and finds a 0.6528-WSNE, which beats the previous best known guarantee of 0.732. It can also be applied to the case of approximate Nash equilibria, where we obtain a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and always finds a 0.382-approximate Nash equilibrium, which improves the previous best guarantee of 0.438. Finally, the method can also be applied in the query complexity setting to give an algorithm that makes O(nlogn) payoff queries and always finds a 0.6528-WSNE, which improves the previous best known guarantee of 2/3. [ABSTRACT FROM AUTHOR]

In an $$\epsilon $$ -Nash equilibrium, a player can gain at most $$\epsilon $$ by unilaterally changing his behavior. For two-player (bimatrix) games with payoffs in [0, 1], the best-known $$\epsilon $$ achievable in polynomial time is 0.3393 (Tsaknakis and Spirakis in Internet Math 5(4):365-382, 2008). In general, for n-player games an $$\epsilon $$ -Nash equilibrium can be computed in polynomial time for an $$\epsilon $$ that is an increasing function of n but does not depend on the number of strategies of the players. For three-player and four-player games the corresponding values of $$\epsilon $$ are 0.6022 and 0.7153, respectively. Polymatrix games are a restriction of general n-player games where a player's payoff is the sum of payoffs from a number of bimatrix games. There exists a very small but constant $$\epsilon $$ such that computing an $$\epsilon $$ -Nash equilibrium of a polymatrix game is $$\mathtt {PPAD}$$ -hard. Our main result is that a $$(0.5+\delta )$$ -Nash equilibrium of an n-player polymatrix game can be computed in time polynomial in the input size and $$\frac{1}{\delta }$$ . Inspired by the algorithm of Tsaknakis and Spirakis [28], our algorithm uses gradient descent style approach on the maximum regret of the players. We also show that this algorithm can be applied to efficiently find a $$(0.5+\delta )$$ -Nash equilibrium in a two-player Bayesian game. [ABSTRACT FROM AUTHOR]

In an $$\epsilon $$ -Nash equilibrium, a player can gain at most $$\epsilon $$ by changing his behaviour. Recent work has addressed the question of how best to compute $$\epsilon $$ -Nash equilibria, and for what values of $$\epsilon $$ a polynomial-time algorithm exists. An $$\epsilon $$ - well-supported Nash equilibrium ( $$\epsilon $$ -WSNE) has the additional requirement that any strategy that is used with non-zero probability by a player must have payoff at most $$\epsilon $$ less than a best response. A recent algorithm of Kontogiannis and Spirakis shows how to compute a 2/3-WSNE in polynomial time, for bimatrix games. Here we introduce a new technique that leads to an improvement to the worst-case approximation guarantee. [ABSTRACT FROM AUTHOR]

This paper presents the 'Game Theory Explorer' software tool to create and analyze games as models of strategic interaction. A game in extensive or strategic form is created and nicely displayed with a graphical user interface in a web browser. State-of-the-art algorithms then compute all Nash equilibria of the game after a mouseclick. In tutorial fashion, we present how the program is used, and the ideas behind its main algorithms. We report on experiences with the architecture of the software and its development as an open-source project. [ABSTRACT FROM AUTHOR]

We study the performance of Fictitious Play (FP), when used as a heuristic for finding an approximate Nash equilibrium of a two-player game. We exhibit a class of two-player games having payoffs in the range $$[0,1]$$ that show that FP fails to find a solution having an additive approximation guarantee significantly better than $$1/2$$. Our construction shows that for $$n\times n$$ games, in the worst case both players may perpetually have mixed strategies whose payoffs fall short of the best response by an additive quantity $$1/2 - O(1/n^{1-\delta })$$ for arbitrarily small $$\delta $$. We also show an essentially matching upper bound of $$1/2 - O(1/n)$$. [ABSTRACT FROM AUTHOR]

This paper describes algorithms for finding all Nash equilibria of a two-player game in strategic form. We present two algorithms that extend earlier work. Our presentation is self-contained, and explains the two methods in a unified framework using faces of best-response polyhedra. The first method lrsnash is based on the known vertex enumeration program lrs, for “lexicographic reverse search”. It enumerates the vertices of only one best-response polytope, and the vertices of the complementary faces that correspond to these vertices (if they are not empty) in the other polytope. The second method is a modification of the known EEE algorithm, for “enumeration of extreme equilibria”. We also describe a second, as yet not implemented, variant that is space efficient. We discuss details of implementations of lrsnash and EEE, and report on computational experiments that compare the two algorithms, which show that both have their strengths and weaknesses. [ABSTRACT FROM AUTHOR]

We investigate the computational complexity of several decision problems in a simple strategic game of network formation. We find that deciding if a player has a strategy that guarantees him a certain payoff against a given strategy profile of the other players is an NP-complete problem. Deciding if there exists a strategy profile that guarantees a certain aggregate payoff is also NP-complete. Deciding if there is a Nash equilibrium in pure strategies which guarantees a certain payoff to each player is NP-hard. The problem of deciding if a given strategy profile is a Nash equilibrium is investigated as well. [ABSTRACT FROM AUTHOR]

We investigate the restriction of animal movements as a method to control the spread of bluetongue, an infectious disease of livestock that is becoming increasingly prevalent due to the onset of climate change. We derive control policies for the UK that minimise the number of infected farms during an outbreak using Bayesian optimisation and a simulation-based model of BT. Two cases are presented: first, where the region of introduction is randomly selected from England and Wales to find a generalised strategy. This "national" model is shown to be just as effective at subduing the spread of bluetongue as the current strategy of the UK government. Our proposed controls are simpler to implement, affect fewer farms in the process and, in so doing, minimise the potential economic implications. Second, we consider policies that are tailored to the specific region in which the first infection was detected. Seven different regions in the UK were explored and improvements in efficiency from the use of specialised policies presented. As a consequence of the increasing temperatures associated with climate change, efficient control measures for vector-borne diseases such as this are expected to become increasingly important. Our work demonstrates the potential value of using Bayesian optimisation in developing cost-effective disease management strategies. [ABSTRACT FROM AUTHOR]

Policy gradient methods have become one of the most popular classes of algorithms for multi-agent reinforcement learning. A key challenge, however, that is not addressed by many of these methods is multi-agent credit assignment: assessing an agent’s contribution to the overall performance, which is crucial for learning good policies. We propose a novel algorithm called Dr.Reinforce that explicitly tackles this by combining difference rewards with policy gradients to allow for learning decentralized policies when the reward function is known. By differencing the reward function directly, Dr.Reinforce avoids difficulties associated with learning the Q-function as done by counterfactual multi-agent policy gradients (COMA), a state-of-the-art difference rewards method. For applications where the reward function is unknown, we show the effectiveness of a version of Dr.Reinforce that learns an additional reward network that is used to estimate the difference rewards. [ABSTRACT FROM AUTHOR]