New Zealand

Jingtao Shi (September 26th 2018). Stochastic Leader-Follower Differential Game with Asymmetric Information, Game Theory - Applications in Logistics and Economy, Danijela Tuljak-Suban, IntechOpen, DOI: 10.5772/intechopen.75413.

Stefan Rass, Peter Schartner and Raphael Wigoutschnigg (January 1st 2010). Security as a Game – Decisions from Incomplete Models, Decision Support Systems, Chiang S. Jao, IntechOpen, DOI: 10.5772/39453. 

Artem Katasonov and Vagan Terziyan (January 1st 2010). Using Semantic Technology to Enable Behavioural Coordination of Heterogeneous Systems, Semantic Web, Gang Wu, IntechOpen, DOI: 10.5772/7304. 

Recent work studied Stackelberg security games with multiple defenders, in which heterogeneous defenders allocate security resources to protect a set of targets against a strategic attacker. Equilibrium analysis was conducted to characterize outcomes of these games when defenders act independently. Our starting point is the observation that the use of resources in equilibria may be inefficient due to lack of coordination. We explore the possibility of reducing this inefficiency by coordinating the defenders---specifically, by pooling the defenders&#39; resources and allocating them jointly. The defenders&#39; heterogeneous preferences then give rise to a collective decision-making problem, which calls for a mechanism to generate joint allocation strategies. We seek a mechanism that encourages coordination, produces efficiency gains, and incentivizes the defenders to report their true preferences and to execute the recommended strategies. Our results show that, unfortunately, even these basic properties clash with each other and no mechanism can achieve them simultaneously, which reveals the intrinsic difficulty of achieving meaningful defense coordination in security games. On the positive side, we put forward mechanisms that fulfill some of these properties and we identify special cases of our setting where more of these properties are compatible.


AAMAS 2020

Mechanism Design for Defense Coordination in Security Games

security game

mechanism design

stackelberg game

coordination

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

Recent work studied Stackelberg security games with multiple defenders, in which heterogeneous defenders allocate security resources to protect a set of targets against a strategic attacker. Equilibrium analysis was conducted to characterize outcomes of these games when defenders act independently. Our starting point is the observation that the use of resources in equilibria may be inefficient due to lack of coordination. We explore the possibility of reducing this inefficiency by coordinating the defenders---specifically, by pooling the defenders' resources and allocating them jointly. The defenders' heterogeneous preferences then give rise to a collective decision-making problem, which calls for a mechanism to generate joint allocation strategies. We seek a mechanism that encourages coordination, produces efficiency gains, and incentivizes the defenders to report their true preferences and to execute the recommended strategies. Our results show that, unfortunately, even these basic properties clash with each other and no mechanism can achieve them simultaneously, which reveals the intrinsic difficulty of achieving meaningful defense coordination in security games. On the positive side, we put forward mechanisms that fulfill some of these properties and we identify special cases of our setting where more of these properties are compatible.


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). 

The problem of probabilistic goal recognition consists of automatically inferring a probability distribution over a range of possible goals of an autonomous agent based on the observations of its behavior. The state-of-the-art approaches for probabilistic goal recognition assume the full knowledge about the world the agent operates in and possible agent’s operations in this world. In this paper, we propose a framework for solving the probabilistic goal recognition problem using process mining techniques for discovering models that describe the observed behavior and diagnosing deviations between the discovered models and observations. The framework imitates the principles of observational learning, one of the core mechanisms of social learning exhibited by humans, and relaxes the above assumptions. The reported experimental results confirm the effectiveness and efficiency of the approach, both for rational and irrational agents’ behaviors.


Goal Recognition Using Off-The-Shelf Process Mining Techniques

Trajectory-User Linking (TUL), which links trajectories to users, is a recently introduced trajectory mining task with a wide spectrum of applications, ranging from personalized recommendation systems and location-based social networks to potential criminals identification. Previous approaches on solving the TUL task generally rely on classic models or Recurrent Neural Network (RNN) models. However, their prediction accuracy is always not satisfactory due to the following reasons: 1) trajectory data is low-sampling and sparse; 2) user mobility patterns are high-order and multi-periodic; and 3) previous approaches fail to utilize existing abundant features. In this paper, we propose DeepTUL, which is composed of a feature representation layer and a recurrent network with attention mechanism, to solve TUL task. DeepTUL not only combines multiple features that govern user mobility to model high-order and complex mobility patterns, but also learns from labeled historical trajectory to capture multi-periodic nature of user mobility and alleviate the data sparsity problem. Extensive experiments show that DeepTUL yields significant improvements over the existing methods on two types of real-life mobility datasets (i.e., check-in dataset and WLAN dataset). Moreover, DeepTUL provides intuitive interpretation into the trajectory-user linking.


Trajectory-User Linking with Attentive Recurrent Network

We propose a deep reinforcement learning algorithm for semi-cooperative multi-agent tasks, where agents are equipped with their separate reward functions, yet with some willingness to cooperate. It is intuitive that defining and directly maximizing a global reward function leads to cooperation because there is no concept of selfishness among agents. However, it may not be the best way of inducing such cooperation due to problems that arise from training multiple agents with a single reward (e.g., credit assignment). In addition, agents may intentionally be given separate reward functions to induce task prioritization whereas a global reward function may be difficult to define without diluting the effect of different tasks and causing their reward factors to be disregarded. Our algorithm, called Peer Evaluation-based Dual DQN (PED-DQN), proposes to give peer evaluation signals to observed agents, which quantify how they strategically value a certain transition. This exchange of peer evaluation among agents over time turns out to render agents to gradually reshape their reward functions so that their action choices from the myopic best response tend to result in a more cooperative joint action.

Inducing Cooperation through Reward Reshaping based on Peer Evaluations in Deep Multi-Agent Reinforcement Learning

Given the preferences of several agents over a set of alternatives, there may be competing views on which of the alternative would be “best” to choose. We propose a formal model, grounded in social choice theory, for providing a justification for a given choice in the context of a given corpus of basic normative principles (so-called axioms) on which to base any possible step-by-step explanation for why a given target alternative should be elected in a given situation. Thus, our notion of justification has both an explanatory and a normative component. We also develop an algorithm for computing such justifications that exploits the analogy between
the notion of explanation and the concept of minimal unsatisfiable subset used in constraint programming. Finally, we report on an application of a proof-of-concept implementation of our approach for an experimental study of the explanatory power of several axioms proposed in the social choice literature.


Automated Justification of Collective Decisions via Constraint Solving

In this work, we study the fair resource sharing problem, where a set of resources needs to be shared by a set of agents. Each agent is unit-demand and each resource can serve a limited number of agents. The agents have (heterogeneous) preferences for the resources, and preferences for other agents with whom they share the resources. Our definition of fairness is mainly captured by envy-freeness. Due to the fact that an envy-free assignment may not exist even in simple settings, we propose a way to relax the definition: Pareto envy-freeness, where an assignment is Pareto envy-free if for any two agents i and j, agent i does not envy agent j for her received resource or the set of agents she shares the resource with. We study
to what extent Pareto envy-free assignments exist. Particularly, we are interested in a typical model, dorm assignment problem, where a number of students need to be accommodated to the dorms with the same capacity and the students’ preferences for dorm-mates are binary. We show that when the capacities of the dorms are 2, a Pareto envy-free assignment always exists and can be found in polynomial time; however, if the capacities increase to 3, Pareto envy-freeness cannot be guaranteed any more.


Fair Resource Sharing and Dorm Assignment

Counterfactual Regret Minimization (CFR) has found success in settings like poker which have both terminal states and perfect recall. We seek to understand how to relax these requirements. As a first step, we introduce a simple algorithm, local no-regret learning (LONR), which uses a Q-learning-like update rule to allow learning without terminal states or perfect recall. We discuss its provable convergence for the basic case of MDPs and present empirical results showing that it achieves last iterate convergence in NoSDE games, a class of general sum Markov games specifically designed to be challenging to learn where no prior algorithm is known to achieve convergence to a stationary equilibrium even on average. 


Combining No-Regret and Q-Learning

This presentation is about our AAMAS 2020 paper ""Plannable Approximations to MDP Homomorphisms: Equivariance under Actions"". This work exploits action equivariance for representation learning in reinforcement learning. Equivariance under actions states that
transitions in the input space are mirrored by equivalent transitions in latent space, while the map and transition functions should also commute. We introduce a contrastive loss function that enforces action equivariance on the learned representations. We prove that when our loss is zero, we have a homomorphism of a deterministic Markov Decision Process (MDP). Learning equivariant maps leads to structured latent spaces, allowing us to build a model on which we plan through value iteration. We show experimentally that for deterministic MDPs, the optimal policy in the abstract MDP can be successfully lifted to the original MDP. Moreover, the approach easily adapts to changes in the goal states. Empirically, we show that in such MDPs, we obtain better representations in fewer epochs compared to representation learning approaches using reconstructions, while generalizing better to new goals than model-free approaches.


Plannable Approximations to MDP Homomorphisms: Equivariance under Actions

Consider a closed environment with static obstacles and mobile agents moving around. There are hider agents that hide from the seeker agents. The seeker has a limited visibility range, and if a hider comes into the visibility region of a seeker, it is considered caught. The practical applications range from gaming to security. In this work, we focus on deterministic capture of hiders, even if they are guided by an Oracle which knows the future positions of seekers. We develop strategies for seekers, having limited visibility ranges, to catch all hiders and establish minimum bounds on the number of seekers required to catch the hiders, on a per strategy basis. We use spatio-temporal graph models and reasoning to formulate and address the problem.


Capturing Oracle Guided Hiders

Effective coordination is a critical requirement for human teaming, and is increasingly needed in teams of humans and robots. Building on decades of work in the behavioral literature, we have implemented a computational framework for coordination based on Shared Mental Models (SMMs) in which robots use a distributed knowledge base to coordinate activity. We also built a novel system connecting the robotic architecture, DIARC, to the 3D simulation environment, Unity, to serve as an evaluation platform for the framework implementation, and also for more general explorations of teaming with autonomous robots. Using this platform, we ran a user study to evaluate the framework by comparing performance of teams in which the robots used SMMs with those that did not. We found that teams in which the robots used SMMs significantly outperformed those without SMMs. This represents the first empirical demonstration that SMMs can be successfully used by fully autonomous robots interacting in natural language to improve team performance, bringing robots a step closer to genuine teammate


Toward Genuine Robot Teammates: Improving Human-Robot Team Performance Using Robot Shared Mental Models

An important aspect of multi-agent systems concerns the formation of coalitions that are stable or optimal in some well-defined way. The notion of popularity has recently received a lot of attention in this context. A partition is popular if there is no other partition in which more agents are better off than worse off. 
In 2019, a long-standing open problem concerning popularity was solved by proving that computing popular partitions in roommate games is NP-hard, even when preferences are strict. We show that this result breaks down when allowing for randomization: mixed popular partitions can be found efficiently via linear programming and a separation oracle. Mixed popular partitions are particularly attractive because they are guaranteed to exist in any coalition formation game.
Our result implies that one can efficiently verify whether a given partition in a roommate game is popular and that strongly popular partitions can be found in polynomial time (resolving an open problem). By contrast, we prove that both problems become computationally intractable when moving from coalitions of size 2 to coalitions of size 3, even when preferences are strict and globally ranked.


Downloads

Next from AAMAS 2020

Goal Recognition Using Off-The-Shelf Process Mining Techniques

Similar lecture

Coalition Formation in Multi-Defender Security Games

Stay up to date with the latest Underline news!

PRODUCT

COMPANY

RESOURCES

.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

Goal Recognition Using Off-The-Shelf Process Mining Techniques

Similar lecture

Coalition Formation in Multi-Defender Security Games

Stay up to date with the latest Underline news!

PRODUCT

COMPANY

RESOURCES

Downloads