United Kingdom

We address the problem of strategyproof (SP) facility location mechanisms on discrete trees. Our main result is a full characterization of onto and SP mechanisms. In particular, we prove that when a single agent significantly affects the outcome, the trajectory of the facility is almost contained in the trajectory of the agent, and both move in the same direction along the common edges. We show tight relations of our characterization to previous results on discrete lines and on continuous trees. We then derive further implications of the main result for infinite discrete lines.

AAMAS 2021

Strategyproof Facility Location Mechanisms on Discrete Trees

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://assets.underline.io/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

technical paper

This extended abstract summarises the contributions from the journal article Fisher et al. (Autonomous Agents and Multi Agent Systems 35, 1 (2021), 8).

Summarising a Framework for the Certification of Reliable Autonomous Systems (JAAMAS Track)

Large teams of heterogeneous agents have the potential to solve complex multi-task problems that are intractable for a single agent working independently. However, solving complex multi-task problems requires leveraging the relative strengths of the different kinds of agents in the team. We present Stochastic TRAit-based Task Assignment (STRATA), a unified framework that models large teams of heterogeneous agents and performs effective task assignments. Specifically, given information on which traits (capabilities) are required for various tasks, STRATA computes the assignments of agents to tasks such that the trait requirements are achieved. Inspired by prior work in robot swarms and biodiversity, we categorize agents into different species (groups) based on their traits. We model each trait as a continuous variable and differentiate between traits that can and cannot be aggregated from different agents. STRATA is capable of reasoning about both species-level and agent-level variability in traits. We illustrate the necessity and effectiveness of STRATA using detailed numerical simulations and in a capture-the-flag game environment.

STRATA: Unified Framework for Task Assignments in Large Teams of Heterogeneous Agents (JAAMAS Track)

Many real-world scenarios involve teams of agents that have to coordinate their actions to reach a shared goal. We focus on the setting in which a team of agents faces an opponent in a zero-sum, imperfect-information game. Team members can coordinate their strategies before the beginning of the game, but are unable to communicate during the playing phase of the game. This is the case, for example, in Bridge, collusion in poker, and collusion in bidding.

Multi-Agent Coordination in Adversarial Environments through Signal Mediated Strategies

In recent years there has been an increasing interest in ensuring that autonomous systems behave consistently with human values. A popular approach to this challenge is through the incorporation of norms that regulate behaviour in an ethical way. However, such norms must be effective at promoting the values we consider most important. In this work, we introduce a systematic methodology for the automated synthesis of parametric normative systems based on value promotion. We introduce the new concepts of 
 and 
 To quantify the effectiveness of norms at upholding the values we consider relevant, we adopt the value alignment indicator from a previously established framework. We apply our model to a toy system which we use to illustrate our approach from end to end.

Value-Guided Synthesis of Parametric Normative Systems

Online social networks fail to support users to adequately share co-owned content, which leads to privacy violations. Scholars proposed collaborative mechanisms to support users, but they did not satisfy one or more requirements needed according to empirical evidence in this domain, such as explainability, role-agnosticism, adaptability, and being utility- and value-driven. We present ELVIRA, an agent that supports multiuser privacy, whose design meets all these requirements. By considering the sharing preferences and the moral values of users, ELVIRA identifies the optimal sharing policy. Furthermore, ELVIRA justifies the optimality of the solution through explanations based on argumentation. We prove via simulations that ELVIRA provides solutions with the best trade-off between individual utility and value adherence. We also show through a user study that ELVIRA suggests solutions that are more acceptable than existing approaches and that its explanations are also more satisfactory.

ELVIRA: An Explainable Agent for Value and Utility-Driven Multiuser Privacy

In cooperative multi-agent reinforcement learning, a collection of agents learns to interact in a shared environment to achieve a common goal. We propose the use of reward machines (RM) -- Mealy machines used as structured representations of reward functions -- to encode the team's task. The proposed novel interpretation of RMs in the multi-agent setting explicitly encodes required teammate interdependencies, allowing the team-level task to be decomposed into sub-tasks for individual agents. We define such a notion of RM decomposition and present algorithmically verifiable conditions guaranteeing that distributed completion of the sub-tasks leads to team behavior accomplishing the original task. This framework for task decomposition provides a natural approach to decentralized learning: agents may learn to accomplish their sub-tasks while observing only their local state and abstracted representations of their teammates. We accordingly propose a decentralized q-learning algorithm. Furthermore, in the case of undiscounted rewards, we use local value functions to derive lower and upper bounds for the global value function corresponding to the team task. Experimental results in three discrete settings exemplify the effectiveness of the proposed RM decomposition approach, which converges to a successful team policy an order of magnitude faster than a centralized learner and significantly outperforms hierarchical and independent q-learning approaches.

Reward Machines for Cooperative Multi-Agent Reinforcement Learning

Most studies investigating models and algorithms for distributed constraint optimization problems (DCOPs) assume messages arrive instantaneously or within a (short) bounded delay.

Latency-Aware Local Search for Distributed Constraint Optimization

The agile software development life cycle is widely used in industry today due to its highly flexible and iterative processes that facilitate rapid prototyping. There has been recent work in bringing concepts and processes from agile methodologies to agent-oriented software engineering (AOSE). We contribute to this effort by presenting in this paper a novel approach to capturing requirements of agent systems in AOSE using and extending agile concepts. In this paper, we propose to adopt and extend the well-known concept of 
 to facilitate the development of agent systems. We introduce a novel concept, 
, that defines requirements from the perspective of the system. These System Stories are refinements of User Stories and provide more intuitive mappings to agent concepts in the design and implementation. We show how our approach allows better traceability of requirements between stories and the different software development artifacts. We validate our proposal with a feature-based comparison to recent related work, and a preliminary user evaluation based on a drone simulation of a simple search and rescue case study.

User and System Stories: An Agile Approach for Managing Requirements in AOSE

Distributed Constraint Optimization Problems (DCOPs) are a suitable formulation for coordinating interactions (i.e. constraints) in cooperative multi-agent systems. The traditional DCOP model assumes that variables owned by the agents can take only discrete values and constraints' cost functions are defined for every possible value assignment of a set of variables. While this formulation is often reasonable, there are many applications where the decision variables are continuous-valued and constraints are in functional form. To overcome this limitation, Continuous DCOPs (C-DCOPs), an extension of the DCOPs model has been proposed that is able to formulate problems having continuous variables. The existing methods for solving C-DCOPs come with a huge computation and communication overhead. In this paper, we apply continuous non-linear optimization methods on Cooperative Constraint Approximation (CoCoA) algorithm, which is a non-iterative, fast incomplete local search approach for solving DCOPs. We empirically show that our algorithm is able to provide high-quality solutions at the expense of smaller communication cost and execution time compared to the state-of-the-art C-DCOP algorithms.

A Local Search Based Approach to Solve Continuous DCOPs

Gestures augment speech by performing a variety of communicative functions in humans and virtual agents, and are often related to speech by complex semantic, rhetorical, prosodic, and affective elements. In this paper we briefly present an architecture for human-like gesturing in virtual agents that is designed to realize complex speech-to-gesture mappings by exploiting existing machine-learning based parsing tools and techniques to extract these functional elements from speech. We then deeply explore the rhetorical branch of this architecture, objectively assessing specifically whether existing rhetorical parsing techniques can classify gestures into classes with distinct movement properties. To do this, we take a corpus of spontaneously generated gestures and correlate their movement to co-speech utterances. We cluster gestures based on their rhetorical properties, and then by their movement. Our objective analysis suggests that some rhetorical structures are identifiable by our movement features while others require further exploration. We explore possibilities behind these findings and propose future experiments that may further reveal nuances of the richness of the mapping between speech and motion. This work builds towards a real-time gesture generator which performs gestures that effectively convey rich communicative functions.

Strategyproof Facility Location Mechanisms on Discrete Trees

Downloads

Next from AAMAS 2021

Summarising a Framework for the Certification of Reliable Autonomous Systems (JAAMAS Track)

Similar lecture

Egalitarian and Just Digital Currency Networks

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Strategyproof Facility Location Mechanisms on Discrete Trees

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

Summarising a Framework for the Certification of Reliable Autonomous Systems (JAAMAS Track)

Similar lecture

Egalitarian and Just Digital Currency Networks

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads