New Zealand

In adversarial patrolling games, a mobile Defender strives to discover intrusions at vulnerable targets initiated by an Attacker.
The Attacker&#39;s utility is traditionally defined as the probability of completing an attack, possibly weighted by target costs.
However, in many real-world scenarios, the actual damage caused by the Attacker depends on the time elapsed since the attack&#39;s initiation to its detection.
We introduce a formal model for such scenarios, and we show that the Defender always has an optimal strategy achieving maximal protection.
We also prove that finite-memory Defender&#39;s strategies are sufficient for achieving protection arbitrarily close to the optimum.
Then, we design an efficient strategy synthesis algorithm based on differentiable programming and gradient descent.
We evaluate the efficiency of our method experimentally.

AAMAS 2022

Minimizing Expected Intrusion Detection Time in Adversarial Patrolling

strategy synthesis

adversarial patrolling

security games

The Conference on Uncertainty in Artificial Intelligence (UAI) is one of the premier international conferences on research related to knowledge representation, learning, and reasoning in the presence of uncertainty. It is supported by the [Association for Uncertainty in Artificial Intelligence (AUAI).](https://www.auai.org/)

The 37th Conference on Uncertainty in Artificial Intelligence (UAI 2021) is held fully online. We have an exciting program consisting of keynote talks by [Susan Murphy](https://www.auai.org/uai2021/program?block=A), [Eric Horvitz](https://www.auai.org/uai2021/program?block=B), [Lenka Zdeborová](https://www.auai.org/uai2021/program?block=C), [Judea Pearl](https://www.auai.org/uai2021/program?block=D) and [Ankur Moitra](https://www.auai.org/uai2021/program?block=E), a town hall meeting, peer-reviewed papers, and three workshops. The main conference is single-track and each paper is show-cased with a live component (either a live discussion and Q&A, or a live lightning talk). All papers are also featured in video presentations and in poster sessions in gather.town. The three parallel workshops on Friday allow for smaller meetings on current topics.

The walkthrough video below shows how you can navigate this site and use the different possibilities for interaction: UAIsland2021 on gather.town for posters and social interactions, the mementor platform for virtual mentoring sessions, and the chat and Q&A systems for discussions about talks and posters.

Have a great UAI 2021! 
<br>
<br>Cassio de Campos and Marloes Maathuis
<br>UAI 2021 Program Chairs
<br>uai2021programchairs@gmail.com

<figure class="video_container">
  <iframe src="https://screencast-o-matic.com/watch/cri0lsViAGK?v=6&ff=1&title=0&controls=1" width=526  height=226  frameborder="0" allowfullscreen="true"> </iframe>
</figure>


A ticket is required to access this conference. Please use the provided link to register for the event.

https://auai.org/uai2021/registration

UAI 2021

The Conference on Uncertainty in Artificial Intelligence (UAI) is one of the premier international conferences on research related to knowledge representation, learning, and reasoning in the presence of uncertainty. It is supported by the [Association for Uncertainty in Artificial Intelligence (AUAI).](https://www.auai.org/)

In adversarial patrolling games, a mobile Defender strives to discover intrusions at vulnerable targets initiated by an Attacker.
The Attacker's utility is traditionally defined as the probability of completing an attack, possibly weighted by target costs.
However, in many real-world scenarios, the actual damage caused by the Attacker depends on the time elapsed since the attack's initiation to its detection.
We introduce a formal model for such scenarios, and we show that the Defender always has an optimal strategy achieving maximal protection.
We also prove that finite-memory Defender's strategies are sufficient for achieving protection arbitrarily close to the optimum.
Then, we design an efficient strategy synthesis algorithm based on differentiable programming and gradient descent.
We evaluate the efficiency of our method experimentally.

poster

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

The AAMAS conference series was initiated in 2002 in Bologna, Italy as a joint event comprising the 6th International Conference on Autonomous Agents (AA), the 5th International Conference on Multiagent Systems (ICMAS), and the 9th International Workshop on Agent Theories, Architectures, and Languages (ATAL).

Subsequent AAMAS conferences have been held in Melbourne, Australia (July 2003), New York City, NY, USA (July 2004), Utrecht, The Netherlands (July 2005), Hakodate, Japan (May 2006), Honolulu, Hawaii, USA (May 2007), Estoril, Portugal (May 2008), Budapest, Hungary (May 2009), Toronto, Canada (May 2010), Taipei, Taiwan (May 2011), Valencia, Spain (June 2012), Minnesota, USA (May 2013), Paris, France (May 2014), Istanbul, Turkey (May 2015), Singapore (May 2016), São Paulo (2017) and Stockholm, Sweden (2018), Montreal (May 2019), Auckland (May 2020, Virtual), London (May 2021, Virtual).
<br>
<br>



A ticket is required to attend this event, please register using the link below:

https://aamas2022-conference.auckland.ac.nz/attending/registration/

Registration Is Required

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

We consider the computational problem of partitioning items into bundles among alternatives to maximize social welfare. Unfortunately, many important classes of this problem are computationally hard, including well-known instances in the multi-agent systems literature. We analyze novel concise representations and restrictions that admit polynomial-time algorithms for many such combinatorial assignment problems, and prove several complexity results for them. We provide efficient approximation algorithms and non-trivial exponential-time algorithms for the hard cases.

Concise Representations and Complexity of Combinatorial Assignment Problems

We consider the popular Partially Observable Monte-Carlo Planning (POMCP) algorithm and propose a methodology, called Active XPOMCP, for generating compact logical rules that represent properties of the control policy.
These rules are then used as shields to prevent POMCP from selecting unexpected actions, with useful implications on the security and trustworthiness of the algorithm.
Contrary to state-of-the-art methods, Active XPOMCP does not require a previously generated set of belief-action pairs to generate the logical rule, but it actively generates this data in an information-efficient way by querying the algorithm.
Active XPOMCP reduces the number of beliefs needed to generate accurate rules with respect to state-of-the-art methods, and it allows to produce more accurate shields when few belief-action samples are available.

Active Generation of Logical Rules for POMCP Shielding


We study the problem of fair allocation of a set of indivisible items among agents with additive valuations, under cardinality constraints. In this setting, the items are partitioned into categories, each with its own limit on the number of items it may contribute to any bundle. We consider the fairness measure known as the maximin share (MMS) guarantee and propose a novel polynomial-time algorithm for finding 1/2-approximate MMS allocations–an improvement from the previously best available guarantee of 11/30.

Guaranteeing Half-Maximin Shares Under Cardinality Constraints


Multi-agent task allocation methods seek to distribute a set of tasks fairly amongst a set of agents. In real-world settings, such as fruit farms, human labourers undertake harvesting tasks, organised each day by farm manager(s) who assign workers to the fields that are ready to be harvested. The work presented here considers three challenges identified in the adaptation of a multi-agent task allocation methodology applied to the problem of distributing workers to fields. First, the methodology must be fast to compute so that it can be applied on a daily basis. Second, the incremental acquisition of harvesting data used to make decisions about worker-task assignments means that a data-backed approach must be derived from incomplete information as the growing season unfolds. Third, the allocation must take “fairness” into account and consider worker motivation. Solutions to these challenges are demonstrated, showing statistically significant results based on the operations at a soft fruit farm during their 2020 and 2021 harvesting seasons.

Multi-agent Task Allocation for Fruit Picker Team Formation


Training reinforcement learning agents in real-world environments is costly, particularly for safety-critical applications. Human input can enable an agent to learn a good policy while avoiding unsafe actions, but at the cost of bothering the human with repeated queries. We present a model for safe learning in safety-critical environments from human input that minimises bother cost. Our model, JPAL-HA, proposes an efficient mechanism to harness human preferences and justifications to significantly improve safety during the learning process without increasing the number of interactions with a user. We show this with both simulation and human experiments.

How to train your agent: Active Learning from Human Preferences and Justifications in Safety-critical Environments


Affective reaction is a mechanism that is triggered by a perceived emotion and results in the observer's emotion, subsequently steering the behavior of the observer. It is crucial to understand this mechanism as it constitutes a mediator between the emotional expressions of one agent and the (behavioral) responses of another thus facilitating social interaction among agents. This paper reports on a formal specification of affective reaction based on its psychological analysis using values and value systems as agents' appraisal standards.

Modeling Affective Reaction in Multi-agent Systems


Formal verification of strategic abilities is a hard problem. We propose to use the methodology of assume-guarantee reasoning in order to facilitate model checking of alternating-time temporal logic with imperfect information and imperfect recall.

Towards Assume-Guarantee Verification of Strategic Ability


It is an established fact in behavioral economics that in lab experi-
ments of auctions, human subjects do not adhere to the risk-neutral
Bayesian Nash equilibria of such games. Several attempts at explain-
ing this Overbidding Puzzle focus on the bidders’ psychology and
suggest they may have parametrized utility functions that differ
from the risk-neutral payoff. However, analytical equilibria of the
resulting modified games are generally not available. Consequently,
it has been difficult to identify the specific parameters and assess
the merits of these proposed modifications in explaining empirical
observations.
With recent advances in equilibrium learning, it has become
tractable to compute approximations of Bayesian Nash equilibria.
Building on these advances and Bayesian optimization, we propose
a novel regression framework to infer unobserved parameters of
Bayesian games from behavioral data. We apply our method to two
data sets of human bidding behavior in all-pay auctions. For the first
time, this makes it possible to directly compare the goodness-of-fit
of several proposed qualitative explanations of overbidding.

Approaching the Overbidding Puzzle in All-Pay Auctions: Explaining Human Behavior through Bayesian Optimization and Equilibrium Learning


We study the NP-hard Fair Connected Districting problem: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios, such as district-based elections, where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. We conduct a fine-grained analysis of the (parameterized) computational complexity of Fair Connected Districting: We study its parameterized complexity with respect to various graph parameters, including treewidth, and problem-specific parameters, including the numbers of colors and districts, and its complexity on graphs from different classes (such as paths, stars, and trees).

A Refined Complexity Analysis of Fair Districting over Graphs


We present a Nash equilibrium analysis for single-buyer singleseller multi-unit k-double auctions for scaling-based bidding strategies. We then design a Deep Deterministic Policy Gradient (DDPG) based learning strategy, DDPGBBS, for a participating agent to suggest bids that approximately achieve the above Nash equilibrium. We expand DDPGBBS to be helpful in more complex settings with multiple buyers/sellers trading multiple units in a Periodic Double Auction (PDA), such as the wholesale market in smart-grids. We demonstrate the efficacy of DDPGBBS with Power Trading Agent Competition’s (PowerTAC) wholesale market PDA as a testbed.

Downloads

Next from AAMAS 2022

Concise Representations and Complexity of Combinatorial Assignment Problems

Similar lecture

Efficient Strategy Synthesis for Adversarial Patrolling 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 2022

Concise Representations and Complexity of Combinatorial Assignment Problems

Similar lecture

Efficient Strategy Synthesis for Adversarial Patrolling Games

Stay up to date with the latest Underline news!

PRODUCT

COMPANY

RESOURCES

Downloads