New Zealand

Alireza Chakeri, Nasser Sadati and Guy A. Dumont (March 27th 2013). Nash Equilibrium Strategies in Fuzzy Games, Game Theory Relaunched, Hardy Hanappi, IntechOpen, DOI: 10.5772/54677.

 Kyriakos G. Vamvoudakis and Frank L. Lewis (January 14th 2011). Online Gaming: Real Time Solution of Nonlinear Two-Player Zero-Sum Games Using Synchronous Policy Iteration, Advances in Reinforcement Learning, Abdelhamid Mellouk, IntechOpen, DOI: 10.5772/13209. 

A two-player finite game is represented by two payoff matrices $(A,B)$, one for each player. Imitation games are a subclass of two-player games in which $B$ is the identity matrix, implying that the second player gets a positive payoff only if she ``imitates&quot;&quot; the first. Given that the problem of computing a Nash equilibrium (NE) is known to be provably hard, even to approximate, we ask if it is any easier for imitation games.

We show that much like the general case, for any $c&gt;0$, computing a $\frac{1}{n^c}$-approximate NE of imitation games remains PPAD-hard, where $n$ is the number of moves available to the players. On the other hand, we design a polynomial-time algorithm to find $\epsilon$-approximate NE for any given constant $\epsilon&gt;0$ (PTAS). The former result also rules out the smooth complexity being in $\Ptime$, unless $\PPAD \subset \RP$. 


AAMAS 2020

Approximate Nash Equilibria of Imitation Games: Algorithms and Complexity

ppad-hardness

ptas

imitation games

two-player games

nash equilibrium

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

AAAI 2021

A two-player finite game is represented by two payoff matrices $(A,B)$, one for each player. Imitation games are a subclass of two-player games in which $B$ is the identity matrix, implying that the second player gets a positive payoff only if she ``imitates"" the first. Given that the problem of computing a Nash equilibrium (NE) is known to be provably hard, even to approximate, we ask if it is any easier for imitation games.

We show that much like the general case, for any $c>0$, computing a $\frac{1}{n^c}$-approximate NE of imitation games remains PPAD-hard, where $n$ is the number of moves available to the players. On the other hand, we design a polynomial-time algorithm to find $\epsilon$-approximate NE for any given constant $\epsilon>0$ (PTAS). The former result also rules out the smooth complexity being in $\Ptime$, unless $\PPAD \subset \RP$. 


technical paper

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). The aim of the joint conference is to provide a single, high-profile, internationally-respected archival forum for scientific research in the theory and practice of autonomous agents and multi-agent systems.

Browse keynotes, discussions, panels and over 300 presentations.


AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). 

In games with Imperfect information players have partial knowledge about their position in the game, which makes it difficult to compute optimal strategies. Here we present several results on computational complexity of games with imperfect information. We also present a generalized model for Bridge Bidding phase to motivate further theoretical study of this phase of Bridge. 


A Bridge between Polynomial Optimization and Games with Imperfect Recall

Cryptocurrenties

Deregulated power systems with high renewable penetration often involve complex decision-making by self-interested private investors. In this work, we study the setting of privately developed and shared network capacity, where the power grid infrastructure, renewable generation and storage units are built by profit-driven investors. Specifically, we consider a case where demand and generation sites are not co-located, and a private investor installs generation capacity and a power line between the two locations providing also access to rival competitors (local generators and storage investors) against a fee. We show such a setting leads to a bilevel Stackelberg-Cournot game between the line investor (leader) and local investors (followers) and develop a data-driven solution to derive the profit-maximising capacities installed by players at equilibrium, based on analysis of a large-scale empirical dataset from a grid upgrade project in the UK. Our method provides a realistic tool to analyse decision-making of private investors in such games and subsequently encourage further adoption of renewable generation.

Strategic Decision-Making for Power Network Investments With Distributed Renewable Generation

Social interactions are key in multi-agent systems. Social dilemmas have been widely studied to model specific problems in social interactions. However, state-of-the-art social dilemmas have disregarded specific ethical aspects affecting interactions.

Here we propose a novel model for social dilemmas, the so-called Sequential Moral Dilemmas, that do capture the notion of moral value. First, we provide a formal definition of sequential moral dilemmas as Markov Games. Thereafter, we formally characterise theoretically the conditions for agents to learn to behave ethically, so that they are aligned with the moral value. Moreover, we exploit our characterisation to provide a structural solution to a sequential moral dilemma, namely how to configure the Markov game to solve the dilemma. 

Finally, we illustrate our proposal through the so-called public civility game, an example of a sequential moral dilemma considering the civility value. We show the social benefits obtained when the agents learn to adhere to the moral value.

A Structural Solution to Sequential Moral Dilemmas

BDI logics, i.e., logics with belief, desire and intention attitudes, are one of the most widely studied formal languages for modelling rational agents. 
In this paper, we consider the logic CTL∗_BDI that augments the branching-time logic CTL∗ with the BDI modalities and adopt the possible-world semantics by Rao and Georgeff. We recall that in this semantics bdi relations vary over time according to a branching-time structure. We study the related model-checking question for finite-state structures, and in particular, we focus on models that are described as tuples of Kripke structures (one for
each world) and where the BDI relations are captured by finite-state relations. Note that for formulas that do not contain BDI modalities this corresponds to standard CTL∗ model-checking that is known to be PSPACE-complete. We show that by adding the BDI modalities
the computational complexity of model-checking remains PSPACE-complete. 
The problem is still PSPACE-hard even if we disallow the nesting of temporal operators in the path formulas, i.e., we restrict to the temporal modalities of CTL. 
Finally, we give a fixed-point formulation of our algorithm for Ctlbdi that implements it on the top of existing symbolic fixed-point solvers.

On the Model-Checking of Branching-time Temporal Logic with BDI Modalities

Bidding and acceptance strategies have a substantial impact on the outcome of negotiations in scenarios with linear additive and nonlinear utility functions. Over the years, it has become clear that there is no single best strategy for all negotiation settings, yet many fixed strategies are still being developed. We envision a shift in the strategy design question from: What is a good strategy?, towards: What could be a good strategy? For this purpose, we developed a method leveraging automated algorithm configuration to find the best strategies for a specific set of negotiation settings. By empowering automated negotiating agents using automated algorithm configuration, we obtain a flexible negotiation agent that can be configured automatically for a rich space of opponents and negotiation scenarios.
To critically assess our approach, the agent was tested in an ANAC-like bilateral automated negotiation tournament setting against past competitors. We show that our automatically configured agent outperforms all other agents, with a 5.1% increase in negotiation payoff compared to the next-best agent. We note that without our agent in the tournament, the top-ranked agent wins by a margin of only 0.01%.

Automated Configuration of Negotiation Strategies

While reinforcement learning (RL) has helped artificial agents solve challenging tasks, high sample complexity is still a major concern. Inter-agent teaching -- endowing agents with the ability to respond to instructions from others -- has been responsible for many developments towards scaling up RL. RL agents that can leverage instructions can learn tasks significantly faster than agents that cannot take advantage of such instruction. That said, the inter-agent teaching paradigm presents many new challenges due to, among other factors, differences between the agents involved in the teaching interaction. This paper is a summary of our JAAMAS article, where we propose two frameworks that provide a comprehensive view of the challenges associated with inter-agent teaching. We highlight state-of-the-art solutions, open problems, prospective applications, and argue that new research in this area should be developed in the context of the proposed frameworks.


Agents Teaching Agents: A Survey on Inter-agent Transfer Learning

Opportunism is a behavior that takes advantage of knowledge asymmetry and results in promoting agents' own value and demoting others' value. It is important to eliminate such selfish behavior in multi-agent systems, as it has undesirable results for the participating agents. In order for monitoring and eliminating mechanisms to be put in the right place, it is needed to know in which context agents are likely to perform opportunistic behavior. In this paper, we develop a formal framework to reason about agents' opportunistic propensity. Opportunistic propensity refers to the potential for an agent to perform opportunistic behavior. In particular, agents in the system are assumed to have their own value systems and knowledge. With value systems, we define agents' state preferences. Based on their value systems and incomplete knowledge about the state, they choose one of their rational alternatives to perform, which might be opportunistic behavior. We then characterize the situation where agents are likely to perform opportunistic behavior and the contexts where opportunism is impossible to occur, and prove the computational complexity of predicting opportunism.


A Formal Framework for Reasoning about Opportunistic Propensity in Multi-agent Systems

We study a sequential preference aggregation procedure based on voting rules for settings where several agents express their preferences over a common set of variable assignments via soft constraints. We evaluate this approach by providing both theoretical and experimental results. 


Sequential Voting in Multi-agent Soft Constraint Aggregation

Many real-world decision problems are inherently multi-objective in nature and concern multiple actors, making multi-objective multi-agent systems a key domain to study. We argue that trade-offs between conflicting objective functions should be analysed on the basis of the utility that these trade-offs have for the users of a system. We develop a new taxonomy which classifies multi-objective multi-agent decision making settings, on the basis of the reward structures and utility functions. We analyse which solution concepts apply to the different settings in our taxonomy, which allows us to offer a structured view of the field and identify promising directions for future research.


Downloads

Next from AAMAS 2020

A Bridge between Polynomial Optimization and Games with Imperfect Recall

Similar lecture

On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-Player Games

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAMAS 2020

A Bridge between Polynomial Optimization and Games with Imperfect Recall

Similar lecture

On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-Player Games

Downloads