New Zealand

We consider the well-studied many-to-one bipartite matching problem of assigning applicants $\A$ to posts $\B$ where applicants rank posts in the order of preference. This setting models many important real-world allocation problems like assigning students to courses, applicants to jobs, amongst many others. In such scenarios, it is natural to ask for an allocation that satisfies guarantees of the form ``match at least 80\% of applicants to one of their top three choices&#39;&#39; or ``it is unacceptable to leave more than 10\% of applicants unassigned&#39;&#39;. The well-studied notions of rank-maximality and fairness fail to capture such requirements due to their property of optimizing extreme ends of the {\em signature} of a matching. We, therefore, propose a novel optimality criteria, which we call as the ``cumulative better signature&#39;&#39;.

We investigate the computational complexity of the new notion of optimality in the setting where posts have associated {\em fixed} quotas. We prove that under the fixed quota setting, the problem turns out to be NP-hard under severe restrictions. We provide randomized algorithms in the fixed quota setting when the number of ranks is constant. We also study the problem under a {\em cost-based quota} setting and show that min-cost cumulative better matching can be computed efficiently. Apart from circumventing the hardness, the cost-based quota setting is motivated by real-world applications like course allocation, school choice where the capacities or quotas need not be rigid.

AAMAS 2022

Optimal Matchings with One-Sided Preferences: Fixed and Cost-Based Quotas

randomized algorithms

network flows

matchings with preferences

np-hardness

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 well-studied many-to-one bipartite matching problem of assigning applicants $\A$ to posts $\B$ where applicants rank posts in the order of preference. This setting models many important real-world allocation problems like assigning students to courses, applicants to jobs, amongst many others. In such scenarios, it is natural to ask for an allocation that satisfies guarantees of the form ``match at least 80\% of applicants to one of their top three choices'' or ``it is unacceptable to leave more than 10\% of applicants unassigned''. The well-studied notions of rank-maximality and fairness fail to capture such requirements due to their property of optimizing extreme ends of the {\em signature} of a matching. We, therefore, propose a novel optimality criteria, which we call as the ``cumulative better signature''.

We investigate the computational complexity of the new notion of optimality in the setting where posts have associated {\em fixed} quotas. We prove that under the fixed quota setting, the problem turns out to be NP-hard under severe restrictions. We provide randomized algorithms in the fixed quota setting when the number of ranks is constant. We also study the problem under a {\em cost-based quota} setting and show that min-cost cumulative better matching can be computed efficiently. Apart from circumventing the hardness, the cost-based quota setting is motivated by real-world applications like course allocation, school choice where the capacities or quotas need not be rigid.

technical paper

The stable matching problem sets the economic foundation of several practical applications ranging from school choice and medical residency to ridesharing and refugee placement. It is concerned with finding a matching between two disjoint sets of agents wherein no pair of agents prefer each other to their matched partners. The Deferred Acceptance (DA) algorithm is an elegant procedure that guarantees a stable matching for any input; however, its outcome may be unfair as it always favors one side by returning a matching that is optimal for one side (say men) and pessimal for the other side (say women). A desirable fairness notion is minimizing the sex-equality cost, i.e. the difference between the total rankings of both sides. Computing such stable matchings is a strongly NP-hard problem, which raises the question of what tractable algorithms to adopt in practice. We conduct a series of empirical evaluations on the properties of sex-equal stable matchings when preferences of agents on both sides are correlated. Our empirical results suggest that under correlated preferences, the DA algorithm returns stable matchings with low sex-equality cost, which further confirms its broad use in many practical applications.

Fair Stable Matching Meets Correlated Preferences

To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient-donor pools. We consider a recent credit system where in each round, countries are given an initial kidney transplant allocation which is adjusted by a credit function yielding a target allocation. The goal is to find a solution in the patient-donor compatibility graph that approaches the target allocation as closely as possible, to ensure long-term stability of the international pool. As solutions, we use maximum matchings that lexicographically minimize the country deviations from the target allocation. We first give a polynomial-time algorithm for computing such matchings. We then perform, for the first time, a computational study for a {\it large} number of countries. For the initial allocations we use, besides two easy-to-compute solution concepts, two classical concepts: the Shapley value and nucleolus. These are hard to compute, but by using state-of-the-art software we show that they are now within reach for IKEPs of up to fifteen countries. Our experiments show that using lexicographically minimal maximum matchings instead of ones that only minimize the largest deviation from the target allocation (as previously done) may make an IKEP up to 52\% more balanced.

Computing Balanced Solutions for Large International Kidney Exchange Schemes


In multi-objective optimization, learning all the policies that reach Pareto-efficient solutions is an expensive process. The set of optimal policies grows exponentially with the number of objectives, and recovering all solutions requires an exhaustive exploration of the entire state space. We propose Pareto Conditioned Networks (PCN), a method that uses a single neural network to encompass all non-dominated policies. PCN associates every past transition with its episode's return. It trains the network such that, when conditioned on this same return, it should reenact said transition. In doing so we transform the optimization problem into a classification problem. We recover a concrete policy by conditioning the network on the desired Pareto-efficient solution. Our method is stable as it learns in a supervised fashion, thus avoiding moving target issues. Moreover, by using a single network, PCN scales efficiently with the number of objectives. Finally, it makes minimal assumptions on the shape of the Pareto front, which makes it suitable to a wider range of problems than previous state-of-the-art multi-objective RL algorithms.

Pareto Conditioned Networks


Recent success in reinforcement learning (RL) has brought renewed attention to the design of reward functions by which agent behavior is reinforced or deterred. Manually designing reward functions is tedious and error-prone. An alternative approach is to specify a formal, unambiguous logic requirement, which is automatically translated into a reward function to be learned from. Omega-regular languages, of which Linear Temporal Logic (LTL) is a subset, are a natural choice for specifying such requirements due to their use in verification and synthesis. However, current techniques based on omega-regular languages learn in an episodic manner whereby the environment is periodically reset to an initial state during learning. In some settings, this assumption is challenging or impossible to satisfy. Instead, in the continuing setting the agent explores the environment without resets over a single lifetime. This is a more natural setting for reasoning about omega-regular specifications defined over infinite traces of agent behavior. Optimizing the average reward instead of the usual discounted reward is more natural in this case due to the infinite-horizon objective that poses challenges to the convergence of discounted RL solutions. 

We restrict our attention to the omega-regular languages which correspond to \emph{absolute liveness} specifications. These specifications cannot be invalidated by any finite prefix of agent behavior, in accordance with the spirit of a continuing problem. We propose a translation from absolute liveness omega-regular languages to an average reward objective for RL. Our reduction can be done on-the-fly, without full knowledge of the environment, thereby enabling the use of model-free RL algorithms. Additionally, we propose a reward structure that enables RL without episodic resetting in communicating MDPs, unlike previous approaches. We demonstrate empirically with various benchmarks that our proposed method of using average reward RL for continuing tasks defined by omega-regular specifications is more effective than competing approaches that leverage discounted RL.

Translating Omega-Regular Specifications to Average Objectives for Model-Free Reinforcement Learning


In partially observable reinforcement learning, offline training gives access to latent information which is not available during online training and/or execution, such as the system state. Asymmetric actor-critic methods exploit such information by training a history-based policy via a state-based critic. However, many asymmetric methods lack theoretical foundation, and are only evaluated on limited domains. We examine the theory of asymmetric actor-critic methods which use state-based critics, and expose fundamental issues which undermine the validity of a common variant, and limit its ability to address partial observability. We propose an unbiased asymmetric actor-critic variant which is able to exploit state information while remaining theoretically sound, maintaining the validity of the policy gradient theorem, and introducing no bias and relatively low variance into the training process. An empirical evaluation performed on domains which exhibit significant partial observability confirms our analysis, demonstrating that unbiased asymmetric actor-critic converges to better policies and/or faster than symmetric and biased asymmetric baselines.

Unbiased Asymmetric Reinforcement Learning under Partial Observability


Recent Multi-Agent Reinforcement Learning (MARL) literature has been largely focused on Centralized Training with Decentralized Execution (CTDE) paradigm. CTDE has been a dominant approach for both cooperative and mixed environments due to its capability to efficiently train decentralized policies. While in mixed environments full autonomy of the agents can be a desirable outcome, cooperative environments allow agents to share information to facilitate coordination. Approaches that leverage this technique are usually referred as communication methods, as full autonomy of agents is compromised for better performance. Although communication approaches have shown impressive results, they do not fully leverage this additional information during training phase. In this paper, we propose a new communication method called MAMBA which utilizes on Model-Based Reinforcement Learning (MBRL) to further leverage centralized training in multi-agent environments. We show that communication between agents can be used to sustain a world model for each agent during execution phase while imaginary rollouts can be used for training, removing the necessity to interact with the environment. These properties yield sample efficient algorithm that can scale gracefully with the number of agents. We empirically confirm that MAMBA achieves good performance while reducing the number of interactions with the environment up to the orders of magnitude compared to Model-Free state-of-the-art approaches in challenging domains of SMAC and Flatland.

Scalable Multi-Agent Model-Based Reinforcement Learning


Multi-agent pathfinding is the problem of finding collision-free paths for a set of agents. Solving this problem optimally is computationally hard, therefore many techniques based on reductions to other formalisms were developed. In comparison to search-based techniques, the reduction-based techniques fall behind on large maps even for a small number of agents. To combat this phenomenon, we propose several strategies for pruning vertices off large instances that will most likely not be used by agents. First, we introduce these strategies conceptually and prove which of them maintain completeness and optimality. Eventually, we conduct an exhaustive evaluation and show that graph pruning strategies make reduction-based solvers comparable to search-based techniques on large maps while maintaining their advantage on small dense maps.

Reduction-based Solving of Multi-agent Pathfinding on Large Maps Using Graph Pruning


Multi-Agent Path Finding (MAPF) is a well studied problem with many existing optimal algorithms capable of solving a wide variety of instances, each with its own strengths and weaknesses. 
While for some instances the fastest algorithm can be easily determined, not enough is known about their performance to predict the fastest algorithm for every MAPF instance, or what makes some instances more difficult than others. There is no clear answer for which features dominate the hardness of MAPF instances. 
In this work, we study how betweenness centrality affects the empirical difficulty of MAPF instances. To that end, we benchmark the largest and most complete optimal MAPF algorithm portfolio to date. We analyze the algorithms' performance independently and as part of the portfolio, and discuss how betweenness centrality can be used to improve estimations of algorithm performance on a given instance of MAPF.

Betweenness Centrality in Multi-Agent Path Finding


Multi-agent path planning (MAPP) in continuous spaces is a challenging problem with significant practical importance. One promising approach could first construct graphs approximating the spaces called roadmaps, then apply multi-agent pathfinding (MAPF) algorithms on those roadmaps to derive a set of conflict-free trajectories. While conventional studies have just utilized roadmap construction methods developed for single-agent planning, it remains largely unexplored what can serve as effective roadmaps for multiple agents and how we can construct them. To this end, we propose a novel concept of graph representations of the space named cooperative timed roadmaps (CTRMs). CTRMs enable each agent to focus on their important locations around potential solution paths, in a way to consider the behavior of other agents to avoid inter-agent collisions (i.e., "cooperative"), while being augmented in time direction to make it easy to derive a "timed" solution path. To construct CTRMs, we develop a machine learning approach that learns a generative model from a collection of relevant problem instances and plausible solutions and uses the learned model to sample the vertices of CTRMs for new, previously-unseen problem instances. Our empirical evaluation revealed that the use of CTRMs significantly reduced the planning effort with acceptable overheads while maintaining its success rate and solution quality comparable to conventional roadmap construction approaches.

CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces


Planning for multi-robot coordination during long-horizon missions in complex environments requires considering robot resources, temporal constraints, and probabilistic uncertainty. This could be computationally expensive and impractical for online planning and execution. We propose a decoupled framework for temporal and probabilistic planning. At the high-level, we plan for multi-robot missions that require coordination amongst robots considering temporal and numeric constraints. The temporal plan is decomposed into low-level plans for individual robots. At the low-level, we perform online learning and adaptation due to unexpected probabilistic outcomes to achieve mission goals. Our framework learns over time from goal execution failures to improve the performance by (1) updating the learned domain model to reduce model prediction errors and (2) constraining the robot's capabilities which in turn improves goal allocation. The approach provides a solution to planning problems by pondering mission execution quality over implementation time. We demonstrate our approach to experiments involving a fleet of heterogeneous robots.

Downloads

Next from AAMAS 2022

Fair Stable Matching Meets Correlated Preferences

Similar lecture

Pareto optimal and popular house allocation with lower and upper quotas

.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 Stable Matching Meets Correlated Preferences

Similar lecture

Pareto optimal and popular house allocation with lower and upper quotas

Downloads