New Zealand

The past few years have seen a surge of work on fairness in allocation problems where items must be fairly divided among agents having individual preferences. In comparison, fairness in matching settings with preferences on both sides, that is, where agents have to be matched to other agents, has received much less attention. Moreover, the two-sided matching literature has largely focused on ordinal preferences. We study leximin optimality over stable many-to-one matchings under cardinal preferences. We first investigate matching problems with ranked valuations for which we give efficient algorithms to find the leximin optimal matching over the space of stable matchings. We complement these results by showing that relaxing the ranked valuations condition in any way, makes finding the leximin optimal stable matching intractable.

AAMAS 2022

On Achieving Leximin Fairness and Stability in Many-to-One Matchings

leximin optimality

many-to-one matchings

stability

fairness

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

poster


Advances in Reinforcement Learning (RL) have demonstrated data efficiency and optimal control over large state spaces at the cost of scalable performance. Genetic methods, on the other hand, provide scalability but depict hyperparameter sensitivity towards evolutionary operations. A combination of the two methods has recently demonstrated success in scaling RL agents to high-dimensional action spaces. Parallel to recent developments, we present the Evolution-based Soft Actor-Critic (ESAC), a scalable RL algorithm. We abstract exploration from exploitation by combining Evolution Strategies (ES) with Soft Actor-Critic (SAC). Through this lens, we enable dominant skill transfer between offsprings by making use of soft winner selections and genetic crossovers in hindsight. Simultaneously we improve hyperparameter sensitivity in evolutions using the novel Automatic Mutation Tuning (AMT). AMT gradually replaces the entropy framework of SAC allowing the population to succeed at the task while acting as randomly as possible, without making use of backpropagation updates. In a study of challenging locomotion tasks consisting of high-dimensional action spaces and sparse rewards, ESAC demonstrates improved performance and sample efficiency in comparison to the Maximum Entropy framework. Additionally, ESAC presents efficacious use of hardware resources and algorithm overhead.

Off-Policy Evolutionary Reinforcement Learning with Maximum Mutations


This paper considers multi-agent reinforcement learning (MARL) tasks where agents receive a shared global reward at the end of an episode. The delayed nature of this reward affects the ability of the agents to assess the quality of their actions at intermediate time-steps. This paper focuses on developing methods to learn a temporal redistribution of the episodic reward to obtain a dense reward signal. Solving such MARL problems requires addressing two challenges: identifying (1) relative importance of states along the length of an episode (along time), and (2) relative importance of individual agents’ states at any single time-step (among agents). In this paper, we introduce Agent-Temporal Attention for Reward Redistribution in Episodic Multi-Agent Reinforcement Learning (AREL) to address these two challenges. AREL uses attention mechanisms to characterize the influence of actions on state transitions along trajectories (temporal attention), and how each agent is affected by other agents at each time-step (agent attention). The redistributed rewards predicted by AREL are dense, and can be integrated with any given MARL algorithm. We evaluate AREL on challenging tasks from the Particle World environment and the StarCraft Multi-Agent Challenge. AREL results in higher rewards in Particle World, and improved win rates in StarCraft compared to three state-of-the-art reward redistribution methods.

Agent-Temporal Attention for Reward Redistribution in Episodic Multi-Agent Reinforcement Learning


We investigate the discounting mismatch in actor-critic algorithm implementations from a representation learning perspective. 
Theoretically, actor-critic algorithms have discounting for both the actor and critic,
i.e., there is a $\gamma^t$ term in the actor update for the transition observed at time $t$ in a trajectory and the critic is a discounted value function.
Practitioners, however, usually ignore the discounting ($\gamma^t$) for the actor while still using a discounted critic.
We investigate this mismatch in two scenarios.
In the first one, 
we consider optimizing an undiscounted objective $(\gamma = 1)$ where $\gamma^t$ disappears naturally $(1^t = 1)$. 
We then propose to interpret the discounting in the critic in terms of a bias-variance-representation trade-off and provide supporting empirical results.
In the second scenario,
we consider optimizing a discounted objective ($\gamma < 1$) and propose to interpret the omission of the discounting in the actor update
from an auxiliary task perspective and provide supporting empirical results.

A Deeper Look at Discounting Mismatch in Actor-Critic Algorithms


Despite recent advances in RL, many problems, especially real-world tasks, remain prohibitively expensive to learn. To address this issue, several lines of research have explored how tasks, or data samples themselves, can be sequenced into a curriculum to learn a problem that may otherwise be too difficult to learn from scratch. However, generating and optimizing a curriculum in a realistic scenario still requires extensive interactions with the environment. To address this challenge, we formulate the curriculum transfer problem, in which the schema of a curriculum optimized in a simpler, easy-to-solve environment (e.g., a grid world) is transferred to a complex, realistic scenario (e.g., a physics-based robotics simulation or the real world). We present "ACuTE" (Automatic Curriculum Transfer from Simple to Complex Environments), a novel framework to solve this problem, and evaluate our proposed method by comparing it to other baseline approaches (e.g., domain adaptation) designed to speed up learning. We observe that our approach produces improved jumpstart and time-to-threshold performance when adding task elements that further increase the difficulty of the realistic scenario. Finally, we demonstrate our approach is independent of the learning algorithm used for curriculum generation, and is Sim2Real transferrable to a real world scenario using a physical robot.

ACuTE: Automatic Curriculum Transfer from Simple to Complex Environments


Recent studies show that Deep Reinforcement Learning (DRL) models are vulnerable to
adversarial attacks. Most of these adversarial attacks have been conducted against DRL
by adding small perturbations to the observations. However, some attacks hold 
strong assumptions on the availability of the victim model, and some other attacks require a huge
amount of computation, which makes them less feasible for real world applications. In this work,
we expand on the existing literature by studying other aspects of performing such
attacks and provide a further exploration for vulnerabilities of DRL with realistic and efficient attacks. First, for the
plausible scenario where the attacker does not have access to the model parameters, we 
adapt and propose efficient black-box attack techniques to DRL settings. Second, to 
address the high computational demands of existing attacks, we introduce an efficient online 
sequential attacks that exploits temporal consistency across consecutive steps. Third, 
we explore the possibility of an attacker perturbing other quantities in the DRL 
setting, such as the environment dynamics. Finally, to account for imperfections in 
how an attacker would inject a perturbation in the physical world, we devise a method
for generating a robust physical perturbation to be printed, placed under various physical 
conditions, and observed by a real-world agent from different viewpoints. We conduct
extensive experiments both in simulation such as Atari games, robotics and
autonomous driving, and on real-world robotics, to compare the effectiveness of
the proposed attacks with several baseline approaches. To the best of our knowledge, we are the first to apply adversarial attacks on DRL systems to physical robots.

Characterizing Attacks on Deep Reinforcement Learning


Ridge Rider (RR) is an algorithm for finding diverse solutions to optimization problems by following eigenvectors of the Hessian (“ridges”). RR is designed for conservative gradient systems (i.e., settings involving a single loss function), where it branches at saddles — easy-to-find bifurcation points. We generalize this idea to non-conservative, multi-agent gradient systems by proposing a method – denoted Generalized Ridge Rider (GRR) – for finding arbitrary bifurcation points. We give theoretical motivation for our method by leveraging machinery from the field of dynamical systems. We construct novel toy problems where we can visualize new phenomena while giving insight into high-dimensional problems of interest. Finally, we empirically evaluate our method by finding diverse solutions in the iterated prisoners’ dilemma and relevant machine learning problems including generative adversarial networks.

Lyapunov Exponents for Diversity in Differentiable Games


The cost-sharing connection game is a variant of routing games on a network. In this model, given a directed graph with edge costs and capacities, each agent wants to construct a path from a source to a sink with low cost. The cost of each edge is shared by the users based on a cost-sharing function. One of simple cost-sharing functions is defined as the cost divided by the number of users. It models an ideal setting, where no overhead arises when people share things, though it might be quite rare in real life. In this paper, we model more realistic scenarios of cost-sharing connection games by generalizing the cost-sharing function. The arguments do not depend on specific cost-sharing functions and are applicable for a class of all natural cost-sharing scenarios, which include equal divisions with any natural functional overheads. We show that many bounds of the Price of Anarchy and the Price of Stability under sum-cost and max-cost criteria inherit the no-overhead case.

Capacitated Network Design Games on a Generalized Fair Allocation Model

Story sifting (or story recognition) allows for the exploration of events, stories, and patterns that emerge from agent-based simulations. Current approaches to story sifting require users to manually write search queries in a technical language which can be burdensome to users who are unfamiliar with writing code. The goal of this work is to automate and reduce the authoring burden for writing sifting queries. In this paper, we use the event traces of agent-based simulations to create Dynamic Character Networks that track the changing relationship scores between every agent in a simulation. These networks allow for the fortunes between any two agents to be plotted against time as a story arc. By using the time-series comparison technique Dynamic Time Warping, similarity scores between story arcs from the simulation and a user’s query arc can be calculated. Events corresponding to the story arc that best matches the input arc can then be returned to the user, thus providing an intuitive means for users to sift a variety of stories without the need to author a search query. These components are implemented in our experimental prototype Arc Sift which we present in this poster. We also present the results of a user study that supports our expectation that Arc Sift is an intuitive and accurate tool that allows human users to sift stories out from a larger chronicle of events produced by an agent-based simulation.

Automated Story Sifting Using Story Arcs


We consider the allocation of limited resources to heterogeneous customers who arrive in an online fashion. We would like to allocate the resources “fairly”, so that no group of customers is marginalized in terms of their overall service rate. We study whether this is possible to do so in an online fashion, and if so, what a good online allocation policy is.
We model this problem using online bipartite matching under stationary arrivals, a fundamental model in the literature typically studied under the objective of maximizing the total number of customers served. We instead study the objective of maximizing the minimum service rate across all groups, and propose two notions of fairness: long-run and short-run.
For these fairness objectives, we analyze how competitive online algorithms can be, in comparison to offline algorithms which know the sequence of demands in advance. For long-run fairness, we propose two online heuristics (Sampling and Pooling) which establish asymptotic optimality in different regimes (no specialized supplies, no rare demand types, or imbalanced supply/demand). By contrast, outside all of these regimes, we show that the competitive ratio of online algorithms is between 0.632 and 0.732. For short-run fairness, we show for complete bipartite graphs that the competitive ratio of online algorithms is between 0.863 and 0.942; we also derive a probabilistic rejection algorithm which is asymptotically optimal in the total demand.
Depending on the overall scarcity of resources, either our Sampling or Pooling heuristics could be desirable. The most difficult situation for online allocation occurs when the total supply is just enough to serve the total demand, in which case an organization could try to make allocations offline instead. 
We simulate our algorithms on a public ride-hailing dataset, which both demonstrates the efficacy of our heuristics and validates our managerial insights.

Group-level Fairness Maximization in Online Bipartite Matching

Conventional multi-agent reinforcement learning (MARL) methods suffer from low sample efficiency and poor local optimum in complex tasks. We propose a novel framework of Learning to Advise and Learning from Advice (LALA) to enhance MARL, which consists of a centralized advisor, MARL agents and discriminators. The advisor is realized through a spatiotemporal dual graph convolutional network (DualGCN) to give advice to agents from a global perspective via fusing decision information, resolving spatial conflicts, and maintaining temporal continuity. A policy-level generative adversarial learning method is used to advise each agent to learn from advice. Each discriminator trained can distinguish between the policies of the advisor and an agent. Leveraging the discriminator’s judgment, each agent learns to match with the advised policy in addition to learning by its own exploration, which accelerates learning and enhances policy performance. Additionally, an advisor boosting method which incorporates the relevant evaluation made by the discriminators into the training of DualGCN is proposed to further help improve MARL agents. We validate our methods in cooperative navigation tasks. Experimental results demonstrate that our method outperforms baseline methods in terms of both learning efficiency and policy efficacy.


Downloads

Next from AAMAS 2022

Off-Policy Evolutionary Reinforcement Learning with Maximum Mutations

Similar lecture

Fair Stable Matching Meets Correlated Preferences

.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

Off-Policy Evolutionary Reinforcement Learning with Maximum Mutations

Similar lecture

Fair Stable Matching Meets Correlated Preferences

Downloads