New Zealand


Given a set of agents with approval preferences over each other, we study the task of finding k matchings fairly representing everyone&#39;s preferences. We model the problem as an approval-based multiwinner election where the set of candidates consists of matchings of the agents, and agents&#39; preferences over each other are lifted to preferences over matchings. Due to the exponential number of candidates in such elections, standard algorithms for classical sequential voting rules (such as those proposed by Thiele and Phragmén) are rendered inefficient. We show that the computational tractability of these rules can be regained by exploiting the structure of the approval preferences. Moreover, we establish algorithmic results and axiomatic guarantees that go beyond those obtainable in the general multiwinner setting: Assuming that approvals are symmetric, we show that Proportional Approval Voting (PAV), a well-established but computationally intractable voting rule, becomes polynomial-time computable, and that its sequential variant, which does not provide any proportionality guarantees in general, fulfills a rather strong guarantee known as extended justified representation. Some of our algorithmic results extend to other types of compactly representable elections with an exponential candidate space.

AAMAS 2022

Proportional Representation in Matching Markets: Selecting Multiple Matchings under Dichotomous Preferences

matching markets

multiwinner elections

proportional representation

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


Given a set of agents with approval preferences over each other, we study the task of finding k matchings fairly representing everyone's preferences. We model the problem as an approval-based multiwinner election where the set of candidates consists of matchings of the agents, and agents' preferences over each other are lifted to preferences over matchings. Due to the exponential number of candidates in such elections, standard algorithms for classical sequential voting rules (such as those proposed by Thiele and Phragmén) are rendered inefficient. We show that the computational tractability of these rules can be regained by exploiting the structure of the approval preferences. Moreover, we establish algorithmic results and axiomatic guarantees that go beyond those obtainable in the general multiwinner setting: Assuming that approvals are symmetric, we show that Proportional Approval Voting (PAV), a well-established but computationally intractable voting rule, becomes polynomial-time computable, and that its sequential variant, which does not provide any proportionality guarantees in general, fulfills a rather strong guarantee known as extended justified representation. Some of our algorithmic results extend to other types of compactly representable elections with an exponential candidate space.

technical paper


Many models have been proposed for computing a one-to-one matching between two equal-sized sets/sides of agents, each assigned with one preference list of the agents in the opposite side. The most prominent one might be the Stable Matching model. Recently, the Stable Matching model has been extended to the multi-modal setting \cite{UncertainLinearPfAziz2020,ChenEC2018Multi,Miyazaki19Jointly}, where each agent has more than one preference lists, each represents a criteria based on which the agents of the opposite side are evaluated. We use a layer to denote the set of preference lists of agents, which are based on the same criteria. Thus, the single modal matching problem has only one layer. This setting finds applications in many real-world scenarios. However, it turns out that computing a stable matching with multi-modal preferences is NP-hard and W-hard with respect to several natural parameters. Here, we introduce three position-based matching models, which minimize the ``dissatisfaction score''. We define four dissatisfaction scores, namely, the one of a single agent (the position of an agent's matching partner in his/her preference), the one of a matching pair (the sum of the dissatisfaction scores of two agents forming a matching pair), the dissatisfaction score of one side (the sum of the dissatisfaction scores of all agents in one side), and the total dissatisfaction score (the sum of all dissatisfaction scores of all agents). The first model minimizes the total respective dissatisfaction score over all layers, while the second minimizes the maximum of the respective score over all layers. The third model seeks for a matching $M$ which is \PO, meaning that there does not exist a matching $M^\prime$, which is at least as good as $M$ with respect to the respective dissatisfaction score in all layers, but is strictly better in at least one layer.
We present diverse complexity results for these three models, among others, polynomial-time solvability for the first model. We also investigate the generalization which given an upper bound on the dissatisfaction score, computes a matching involving subsets of agents and a subset of layers. Hereby, we mainly focus on the parameterized complexity with respect to parameters such as the size of agent subsets, or the size of the layer subset and achieve fixed-parameter tractability as well as intractability results.

Position-based Matching with Multi-Modal Preferences


In the simplest game-theoretic formulation of Schelling's model of segregation on graphs, agents of two different types each select their own vertex in a given graph so as to maximize the fraction of agents of their type in their occupied neighborhood. Two ways of modeling agent movement here are either to allow two agents to swap their vertices or to allow an agent to jump to a free vertex.
The contributions of this paper are twofold. First, we prove that deciding the existence of a swap-equilibrium and a jump-equilibrium in this simplest model of Schelling games is NP-hard, thereby answering questions left open by Agarwal et al. [AAAI '20] and Elkind et al. [IJCAI '19]. Second, we introduce two measures for the robustness of equilibria in Schelling games in terms of the minimum number of edges or the minimum number of vertices that need to be deleted to make an equilibrium unstable. We prove tight lower and upper bounds on the edge- and vertex-robustness of swap-equilibria in Schelling games on different graph classes.

Equilibria in Schelling Games: Computational Hardness and Robustness


A social ranking solution, or, briefly, a social ranking, over a set N is defined as a map assigning to each coalitional relation (i.e. a ranking over subsets of N) another ranking over the single elements in N. Differently, coalition formation situations, and, in particular, hedonic games, mainly focus on partitions of the set N into disjoint coalitions, which are in general referred to as coalition structures. A coalition structure may be stable according to various notions of stability and the objective is to understand under which conditions a coalition structure is stable. 
In this paper we merge the framework of coalition formation with the one of social rankings to keep into account the effect of hierarchies within coalitions on the stability of coalition structures. We consider alternative classes of coalition formation games where the preferences of the agents over coalitions are induced by a social ranking. More precisely, agents compare coalition structures keeping into account both the relative ranking of coalitions to which they belong (according to a coalitional relation) and their position in the social ranking within each coalition. Constructive characterizations of the set of core-stable coalition structures are provided for alternative classes of hedonic games, together with an impossibility theorem on the existence of core-stable coalitions structures for (nonhedonic) coalition formation situations.

Coalition Formation Games and Social Ranking Solutions


A crucial challenge for robotic systems is to figure out the behavior of another agent. We cast this challenge as a problem of causal inference. The presentation introduces the complications of inferring causal relationships from human behavior under two conditions that question the approach's feasibility. Subsequently, the presentation describes how we instantiated the approach and its feasibility despite the challenging conditions enforced.

Empirical Estimates on Hand Manipulation are Recoverable: A Step Towards Individualized and Explainable Robotic Support in Everyday Activities


As more and more hard and complex procedures are being automated with the aid of artificial intelligence, the need for humans to understand the rationale behind AI decisions becomes imperative. Adequate explanations for decisions made by an intelligent system do not just help describing how the system works, they also earn users' trust. In this work we focus on a general methodology for justifying why certain teams are formed and others are not by a team formation algorithm (TFA). Specifically, we introduce an algorithm that wraps up any existing TFA and builds justifications regarding the teams formed by such TFA. This is done without modifying the TFA in any way. Our algorithm offers a user a collection of commonly-asked questions within a team formation scenario and builds justifications as contrastive explanations. Finally, we conduct an empirical evaluation to measure the quality of the justifications of our algorithm.

Building contrastive explanations for multi-agent team formation


Multi-Agent Path Finding (MAPF) and Multi-Robot Motion Planning (MRMP) are complex problems to solve, analyze and build algorithms for. Automatically-generated explanations of algorithm output, by improving human understanding of the underlying problems and algorithms, could potentially alleviate this issue. Explanations are contextual, however, and thus developers need a good understanding of the questions that can be made about algorithm output, the kinds of explanations that exist, and the potential users and uses of explanations in MAPF/MRMP applications. In this paper we provide a first step towards establishing a taxonomy of explanations, and a list of requirements for the development of explainable MAPF/MRMP planners. We use interviews and a questionnaire with expert developers and industry practitioners to identify the kinds of questions, explanations, users, uses, and requirements of explanations that should be considered in the design of such explainable planners. Our insights cover a diverse set of applications of MAPF/MRMP: warehouse automation, computer games, mining, and manufacturing.

Explainability in Multi-Agent Path/Motion Planning: User-study-driven taxonomy and requirements


Trust is a fundamental aspect of teamwork in Human-Agent Teams(HATs). Trust violations are an inevitable aspect of the cycle of trust,so effective trust repair strategies are needed to ensure durable andsuccessful team performance. This study explores the effectivenessof four trust repair strategies. In a first-person shooter resemblingHAT task, a trust violation was provoked when the robotic agentfailed to detect an approaching enemy. After this, the agent offeredan apology composed of an explanation and/or an expression ofregret (either one alone, both or neither). Our results indicated thatexpressing regret was crucial for effective trust repair, and thattrust repair was most effective when the apology contained bothcomponents.

Trust repair in human-agent teams: the effectiveness ofexplanations and expressing regret


We investigate the use of multi-agent allocation techniques on problems related to Earth observation scenarios with multiple users and satellites. We focus on the problem of coordinating users having reserved exclusive orbit portions and one central planner having several requests that may use some intervals of these exclusives. We define this problem as Earth Observation Satellite Constellation Scheduling Problem (EOSCSP) and map it to a Mixed Integer Linear Program. As to solve EOSCSP, we propose market-based techniques and a distributed problem solving technique based on Distributed Constraint Optimization (DCOP), where agents cooperate to allocate requests without sharing their own schedules. These contributions are experimentally evaluated on randomly generated EOSCSP instances based on real large-scale or highly conflicting observation order books.

Auction-based and Distributed Optimization Approaches for Scheduling Observations in Satellite Constellations with Exclusive Orbit Portions


Wind farms suffer from the so-called wake effects: when some of the turbines are located in the wakes of other turbines, their power output is substantially reduced. These losses can be partially mitigated via actively changing the yaw from the individually optimal direction. Many of the existing wake control techniques have two major limitations: they use simplified wake models to optimize the control strategy, and they assume that the atmospheric conditions remain stable. In this paper, we address these limitations by applying reinforcement learning (RL) to the active wake control problem. RL forgoes the wake model entirely and learns the optimal control strategy based on the observed atmospheric conditions and the reward signal, in this case the power output of the farm. It also accounts for random transitions in the observations, such as turbulent fluctuations in the wind. To evaluate the benefits of RL for active wake control, we implement a simulator based on the state-of-the-art FLORIS model in the OpenAI gym format, making it readily available to the RL community. Next, we propose three different state-action representations of the active wake control problem and investigate their effect on the performance of RL-based wake control. Finally, we compare RL to a state-of-the-art wake control strategy based on FLORIS and show that RL is less sensitive to changes in unobservable data.

Deep Reinforcement Learning for Active Wake Control


In agent programming and engineering, learning has been explored so far mainly as an effective AI technique to tackle specific problems, improving agents' (and MAS as well) adaptability and autonomy at runtime. 

In this paper we consider a broader role of learning, impacting on the full spectrum of agent programming and engineering - from design to runtime. In particular, we introduce a perspective in which agent development is conceived as a kind developmental learning process of the agent itself. In that view, a software agent "is born" with some core domain-independent learning capabilities at the architectural level and is grown up in a proper learning environment to acquire the proper skills to be able then to achieve its designed objectives once it will be deployed, analogously to children in the human case.

The idea relies on - on the one hand - existing literature about how learning has been injected in cognitive architectures as developed in cognitive science (e.g. SOAR, LIDA), as well as in agent architecture such as BDI. On the other hand, the idea drawn inspiration from human science, in particular the literature investigating the role of learning in human development, children in particular, and the impact of capabilities on human autonomy and practical reasoning.

From a software engineering point of view, this idea is meant to be a conceptual baseline to explore general-purpose architectures and methodologies - eventually extending existing ones, such as the BDI - to seamlessly and systematically integrate both parts engineered by developers (e.g. plans) and parts learnt by the agent, eventually adopting different learning strategies.

Main challenges of this view include devising the model and features for the primitive domain-independent learning system to be injected in agent core architecture and reasoning cycle, to support both developmental/continual learning, and how to structure the learning process occurring in the learning environment during the design/development stage. In the paper, causal reasoning and learning are identified and discussed as a main reference to this purpose, to be integrated with practical reasoning as implemented by modern agent architectures and technologies.

Proportional Representation in Matching Markets: Selecting Multiple Matchings under Dichotomous Preferences

Downloads

Next from AAMAS 2022

Position-based Matching with Multi-Modal Preferences

Similar lecture

Simulating Multiwinner Voting Rules in Judgment Aggregation

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Proportional Representation in Matching Markets: Selecting Multiple Matchings under Dichotomous 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

Position-based Matching with Multi-Modal Preferences

Similar lecture

Simulating Multiwinner Voting Rules in Judgment Aggregation

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads