New Zealand


A classical problem in the fair allocation literature is finding an envy-free assignment of indivisible resources to agents with additive utility-based preferences over resources. Motivated by the possible non-existence but evident need of envy-free allocations in some applications, we study the following problem modeling one possible way out: Given an allocation of indivisible resources to agents, is it possible to socially donate some of the resources (which means removing these resources from the allocation instance) such that the resulting modified allocation is envy-free (up to one good). We require that the number of deleted resources and/or the caused utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity of this problem considering various natural and problem-specific parameters (e.g., the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent in the initial allocation) and different preference models, including unary and 0/1-valuations. In our studies, we obtain a rich set of (parameterized) tractability and intractability results and discover several surprising contrasts, for instance, between the two closely related fairness concepts envy-freeness and envy-freeness up to one good and between the influence of the parameters maximum number and welfare of the deleted resources.

AAMAS 2022

Multivariate Algorithmics for Eliminating Envy by Donating Goods

donating goods

indivisible resources

fair allocation

parameterized algorithmics

envy-freeness

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

technical paper


The notion of envy-freeness is a natural and intuitive fairness requirement in resource allocation. With indivisible goods, such fair allocations are unfortunately not guaranteed to exist. Classical works have avoided this issue by introducing an additional divisible resource, i.e., money, to subsidize envious agents. In this paper, we aim to design a truthful allocation mechanism of indivisible goods to achieve both fairness and efficiency criteria with a limited amount of subsidy. Following the work of Halpern and Shah, our central question is as follows: to what extent do we need to rely on the power of money to accomplish these objectives? We show that, when agents have matroidal valuations, there is a truthful allocation mechanism that achieves envy-freeness and utilitarian optimality by subsidizing each agent with at most 1, the maximum marginal contribution of each item for each agent. The design of the mechanism rests crucially on the underlying matroidal M-convexity of the Lorenz dominating allocations. For superadditive valuations, we show that there is a truthful mechanism that achieves envy-freeness and utilitarian optimality, with each agent receiving a subsidy of at most m; furthermore, we show that the amount m is necessary even when agents have additive valuations.

Fair and Truthful Mechanism with Limited Subsidy


We study the problem of fairly allocating a set of $m$ indivisible chores (i.e. items with non-positive value) to $n$ agents. We consider the desirable fairness notion of $1$-out-of-$d$ maximin share (MMS)---the minimum value that an agent can guarantee by partitioning items into $d$ bundles and selecting the least valued bundle---and focus on ordinal approximation of MMS that aims at finding the largest $d$ for which $1$-out-of-$d$ MMS exists. Our main theoretical contribution is showing the existence of $1$-out-of-$\lfloor\frac{3n}{4}\rfloor$ MMS allocations and proving that $1$-out-of-$\lfloor\frac{2n}{3}\rfloor$ MMS allocations of chores can be computed in polynomial time. Furthermore, we show that practical polynomial-time algorithms exist for approximating $1$-out-of-$\lfloor\frac{3n}{4}\rfloor$ MMS bound for chores. This is in contrast to computing allocations that guarantee a fraction of MMS to each agent, where only a polynomial-time approximation scheme (PTAS) with run-time exponential in the approximation accuracy $1/\epsilon$ is known.

Ordinal Maximin Share Approximation for Chores


The problem of fair division known as ``cake cutting'' has been the focus of multiple papers spanning several decades. The most prominent problem in this line of work has been to bound the query complexity of computing an envy-free outcome in the Robertson-Webb query model. However, the root of this problem's complexity is somewhat artificial: the agents' values are assumed to be additive across different pieces of the ``cake'' but infinitely complicated within each piece. This is unrealistic in most of the motivating examples, where the cake represents a finite collection of homogeneous goods. 

We address this issue by introducing a fair division model that more accurately captures these applications: the value that an agent gains from a given good depends only on the amount of the good they receive, yet it can be an arbitrary function of this amount, allowing the agents to express preferences that go beyond standard cake cutting. In this model, we study the query complexity of computing allocations that are not just envy-free, but also approximately Pareto optimal among all envy-free allocations. Using a novel flow-based approach, we show that we can encode the ex-post feasibility of randomized allocations via a polynomial number of constraints, which reduces our problem to solving a linear program.

Beyond Cake Cutting: Allocating Homogeneous Divisible Goods


Autonomous shepherding is a bio-inspired swarm guidance approach, whereby an artificial sheepdog guides a swarm of artificial or biological agents, such as sheep, towards a goal. While the success in this guidance depends on the set of behaviours exhibited by the sheepdog, the main source of complexity for learning effective behaviours lies within the highly non-linear dynamics featured among the swarm members as well as between the swarm and the sheepdog. 
Attempts to apply reinforcement learning (RL) to shepherding have so far relied greatly on rule-based algorithms for calculating waypoints to guide the RL algorithm. In this paper, we propose a curriculum-based approach for RL that does not rely on any external algorithm to pre-determine waypoints for the sheepdog. Instead, the approach uses task decomposition by formulating shepherding in terms of two sub-tasks: (1) pushing an agent from a start to a target location and (2) selecting between collecting scattered agents or driving the biggest cluster of agents to the goal. Simple-to-complex curriculum learning is used to accelerate the learning of each sub-task. For the first sub-task, the complexity is gradually increased over training time, whereas for the second sub-task a simplified environment is designed for initial learning before proceeding with the main environment. 
The proposed approach results in high-performance shepherding with a success rate of about 96\%. While curriculum learning was found to expedite the learning of the first sub-task, it was not as efficient for the second sub-task. Our analyses highlight the need for the careful design of the curriculum to ensure that skills acquired in intermediate tasks are useful for the main tasks.

Autonomous Swarm Shepherding Using Curriculum-Based Reinforcement Learning


This paper presents a hybrid online Partially Observable Markov Decision Process (POMDP) planning system that addresses the problem of autonomous navigation in the presence of complex, multi-modal uncertainties introduced by other agents in the environment. As a particular example, we consider the problem of autonomous navigation in dense crowds of pedestrians and among obstacles. A popular previous approach first generates a path using ad-hoc assumptions about uncertainty and then uses an online tree-based POMDP planning algorithm that reasons about uncertainty to control a very limited aspect of the problem (i.e. speed along the path). We advocate a more general alternative approach in which the tree-based POMDP planner has control over all degrees of freedom (i.e. speed and heading for this autonomous navigation problem). Since this modification greatly extends the region of the state space that the POMDP planner reasons over, an important challenge is finding effective roll-out policies within the limited computational budget. Our key insight is to use multi-query motion planning techniques (e.g., Probabilistic Roadmaps or Fast Marching Method) that generate efficient roll-out policies for every state that the POMDP planning tree might reach during its limited horizon search. Our proposed approach generates trajectories that are safe and significantly more efficient than the previous approach, even in densely crowded dynamic environments with long planning horizons.

Intention-Aware Navigation in Crowds with Extended-Space POMDP Planning


Robots learning from observations in the real world using inverse reinforcement learning (IRL) may encounter objects or agents in the environment, other than the expert, that cause nuisance observations during the demonstration. These confounding elements are typically removed in fully-controlled environments such as virtual simulations or lab settings. When complete removal is impossible the nuisance observations must be filtered out. However, identifying the source of observations when large amounts of observations are made is difficult. To address this, we present a hierarchical Bayesian process that models both the expert's and the confounding elements' observations thereby explicitly modeling the diverse observations a robot may receive. We extend an existing IRL algorithm originally designed to work under partial occlusion of the expert to consider the diverse and noisy observations. In a simulated robotic sorting domain containing both occlusion and confounding elements, we demonstrate the model's effectiveness. In particular, our technique outperforms several other comparative methods, second only to having perfect knowledge of the subject's trajectory.

A Hierarchical Bayesian Process for Inverse RL in Partially-Controlled Environments


Sampling-based motion planners such as RRT* and BIT*, when applied to kinodynamic motion planning, rely on steering functions to generate time-optimal solutions connecting sampled states. Implementing exact steering functions requires either analytical solutions to the time-optimal control problem, or nonlinear programming (NLP) solvers to solve the boundary value problem given the system's kinodynamic equations. Unfortunately, analytical solutions are unavailable for many real-world domains, and NLP solvers are prohibitively computationally expensive, hence fast and optimal kinodynamic motion planning remains an open problem. We provide a solution to this problem by introducing State Supervised Steering Function (S3F), a novel approach to learn time-optimal steering functions. S3F is able to produce near-optimal solutions to the steering function orders of magnitude faster than its NLP counterpart. Experiments conducted on three challenging robot domains show that RRT* using S3F significantly outperforms state-of-the-art planning approaches on both solution cost and runtime. We further provide a proof of probabilistic completeness of RRT* modified to use S3F.

State Supervised Steering Function for Sampling-based Kinodynamic Planning


Wireless Rechargeable Sensor Networks (WRSNs) are especially promising in large-area monitoring tasks that are previously impossible to complete by traditional Wireless Sensor Networks (WSNs). Mobile Chargers (MCs) in WRSNs are to cooperatively charge battery drained sensor nodes high efficiently and with a guarantee of sensors survival. Considering the unpredictability and high dynamics of WRSNs during the charging process, Multi-Agent Reinforcement Learning (MARL) is an attractive alternative to schedule the cooperation among MCs. However, most existing MARL methods based on Dec-POMDP only work for scenarios that agents make decisions at the same time step. Nevertheless, MCs in WRSNs perform charging asynchronously since the charging time of each sensor node varies. To address this problem, we first formulate an Asynchronous Dec-POMDP (AD-POMDP) for asynchronous decision-making. We propose an algorithm called Asynchronous and Scalable Multi-Agent PPO (ASM-PPO) which is a multi-agent PPO variant that allows asynchronous decision-making in AD-POMDP. Furthermore, ASM-PPO takes advantage of the translation invariance in WRSNs to avoid the huge input space dimensions caused by centralized training. The evaluation results not only indicate that our method achieves much charging efficiency and the longer lifetime of sensor nodes, but also demonstrate that ASM-PPO has advantages in terms of stability and scalability over existing methods.

ASM-PPO: Asynchronous and Scalable Multi-Agent PPO for Cooperative Charging


Agile software development is a popular and widely adopted practice due to its flexible and iterative nature that facilitates rapid prototyping. Recent work presented an agile approach to capturing requirements in agent systems via user and system stories. User and system stories present the requirements from the user and system perspective, respectively. Each story contains a set of acceptance criteria , which are a set of statements that identify the conditions under which the system behaviour can be accepted by the users or stakeholders. In this paper, we present a novel approach to testing the requirements that are specified via User and System stories in an agent system. We do this by developing a systematic approach to validating the execution traces output by the system against the specified acceptance criteria for each story. The approach identifies acceptance criterion that are met successfully in execution and those that fail. We present a fault model that categorises the failures providing insight to the developers to address the failed cases. We classify three kinds of faults for a given acceptance criteria: (a) the trigger condition is never met; (b) when the trigger occurs the preconditions are not met; or (iii) the trigger and preconditions are met but the resulting actions are not as expected. The motivating application of our work, which is also the test-bed for evaluation, is an agent-based simulation application for modelling the behaviours of civilians in a bushfire emergency scenario that is used in practice. We show our approach is able to successfully test and uncover requirements that were not met in this application.

Testing requirements via User and System Stories in Agent Systems


Decentralized cooperation in partially-observable multi-agent systems requires effective communications among agents. To support this effort, this work focuses on the class of problems where global communications are available but may be unreliable, thus precluding differentiable communication learning methods. We introduce FCMNet, a reinforcement learning based approach that allows agents to simultaneously learn a) an effective multi-hop communications protocol and b) a common, decentralized policy that enables team-level decision-making. Specifically, our proposed method utilizes the hidden states of multiple directional recurrent neural networks as communication messages among agents. Using a simple multi-hop topology, we endow each agent with the ability to receive information sequentially encoded by every other agent at each time step, leading to improved global cooperation. We demonstrate FCMNet on a challenging set of StarCraft II micromanagement tasks with shared rewards, as well as a collaborative multi-agent pathfinding task with individual rewards. There, our comparison results show that FCMNet outperforms state-of-the-art communication-based reinforcement learning methods in all StarCraft II micromanagement tasks, and value decomposition methods in certain tasks. We further investigate the robustness of FCMNet under realistic communication disturbances, such as random message loss or binarized messages (i.e., non-differentiable communication channels), to showcase FMCNet’s potential applicability to robotic tasks under a variety of real-world conditions.

Multivariate Algorithmics for Eliminating Envy by Donating Goods

Downloads

Next from AAMAS 2022

Fair and Truthful Mechanism with Limited Subsidy

Similar lecture

A Refined Complexity Analysis of Fair Districting over Graphs

Multivariate Algorithmics for Eliminating Envy by Donating Goods

.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

Fair and Truthful Mechanism with Limited Subsidy

Similar lecture

A Refined Complexity Analysis of Fair Districting over Graphs

Downloads