New Zealand


In multiagent systems, the complex interaction of fixed incentives can lead agents to outcomes that are poor (\emph{inefficient}) not only for the group, but also for each individual. Price of anarchy is a technical, game-theoretic definition that quantifies the inefficiency arising in these scenarios\textemdash it compares the welfare that can be achieved through perfect coordination against that achieved by self-interested agents at a Nash equilibrium. We derive a differentiable, upper bound on a price of anarchy that agents can cheaply estimate during learning. Equipped with this estimator, agents can adjust their incentives in a way that improves the efficiency incurred at a Nash equilibrium. Agents do so by learning to mix their reward (equiv. negative loss) with that of other agents by following the gradient of our derived upper bound. We refer to this approach as D3C. In the case where agent incentives are differentiable, D3C resembles the celebrated Win-Stay, Lose-Shift strategy from behavioral game theory, thereby establishing a connection between the global goal of maximum welfare and an established agent-centric learning rule. In the non-differentiable setting, as is common in multiagent reinforcement learning, we show the upper bound can be reduced via evolutionary strategies, until a compromise is reached in a distributed fashion. We demonstrate that D3C improves outcomes for each agent and the group as a whole on several social dilemmas including a traffic network exhibiting Braess’s paradox, a prisoner’s dilemma, and several multiagent domains.

AAMAS 2022

Reducing the Price of Anarchy in Multi-Agent Learning

win-stay lose-shift

reward sharing

collective intelligence

multiagent reinforcement learning

price of anarchy

nash

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


Participatory budgeting (PB) is a democratic process for allocating funds to projects based on the votes of members of the community. 
Different rules have been used to aggregate participants' votes. Past research has studied the trade-off between notions of social welfare and fairness in the multi-winner setting (a special case of participatory budgeting with identical project costs) by Lackner and Skowron (2020). 
But there is little understanding of this trade-off in the more general PB setting. 
This paper provides a theoretical and empirical study of the worst-case guarantees of several common rules to better understand the trade-off between social welfare, representation. 
We show that many of the guarantees from the multi-winner setting do not generalize to the PB setting, and that the introduction of costs leads to substantially worse guarantees, thereby exacerbating the welfare-representation trade-off. 
We extend our theoretical analysis to studying how the requirement of proportionality over voting rules affects this trade-off. 
We further study how the requirement of proportionality over voting rules effects the guarantees on social welfare and representation. We study the latter point also empirically, both on real and synthetic datasets. 
We show that variants of the recently suggested voting rule Rule-X (which satisfies proportionality) do very well in practice both with respect to social welfare and representation.

Welfare vs. Representation in Participatory Budgeting


We simulate voting rules for multiwinner elections in a model of judgment aggregation that distinguishes between rationality and feasibility constraints. These constraints restrict the structure of the individual judgments and of the collective outcome computed by the rule, respectively. We extend known results regarding the simulation of single-winner voting rules to the multiwinner setting, both for elections with ordinal preferences and for elections with approval-based preferences. This not only provides us with a new tool to analyse multiwinner elections, but it also suggests the definition of new judgment aggregation rules, by generalising some of the principles at the core of well-known multiwinner voting rules to this richer setting. We explore this opportunity with regards to the principle of proportionality. Finally, in view of the computational difficulty associated with many judgment aggregation rules, we investigate the computational complexity of our embeddings and of the new judgment aggregation rules we put forward.

Simulating Multiwinner Voting Rules in Judgment Aggregation


In some universities, there is a fixed number of PhD grants, but a larger number of eligible projects and students, each student being allowed to apply on several projects, and a committee builds up a ranking (masterlist) over student-project pairs. The paper analyses three mechanisms to choose the pairs to be funded. The first one, used in some universities, is a greedy mechanism that gives a huge priority to the masterlist and very little to student's preferences. At the other extremity of the spectrum, we have a priority-list variant of student-oriented Gale-Shapley. It is strategyproof and optimal for students, but has one drawback: it pays too little attention to the masterlist, and thus to the committee. Inbetween, we have an intermediate mechanism which can be seen as a good trade-off. Among the properties we study, one is specific to our setting: dynamic monotonicity, which deals with cases when a student suddenly leaves the system in the middle of the process.

Selecting PhD Students and Projects with Limited Funding


While our physical lives are mostly in democracies (one person, one vote — e.g., the EU and the US), our digital lives are mostly in autocracies (one person, all votes — e.g., Facebook). Cryptocurrencies promise liberation but stop short at plutocracy (one coin, one vote). What would it take for us to live in a digital democracy? This paper aims to offer a vision and a concrete roadmap towards answering this question, and charts the unexplored theoretical grounds it presents for the MAS community.

Foundations for the Grassroots Formation of a Democratic Metaverse


In many social-choice mechanisms the resulting choice is not the most preferred one for some of the participants, thus the need for methods to justify the choice made in a way that improves the acceptance and satisfaction of said participants. We propose the use of automatically generated explanations based on desirable mechanism features found in theoretical mechanism design literature. Also, another natural method for providing such explanations is to ask people to provide them, e.g., through crowdsourcing, and choosing the most convincing arguments among those received. We test the effectiveness of both of the methods through a series of experiments conducted with over 600 participants in ranked voting, a classic social choice mechanism. The analysis of the results reveals that explanations indeed affect both aggregated satisfaction and acceptance of the outcome in preference ballots. In particular, explanations are shown to have a positive effect on acceptance when the outcome (the winning candidate in our case) is the most undesirable choice for the participant. A further analysis of the automatically generated explanations reveals that similar levels of satisfaction and acceptance of an outcome can be achieved as with the more costly alternative of crowdsourced explanations, hence eliminating the need to keep humans in the loop.

Justifying Social-Choice Mechanism Outcome for Improving Participant Satisfaction


Cooperative artificial intelligence with human or superhuman proficiency in collaborative tasks stands at the frontier of machine learning research. Prior work has tended to evaluate cooperative AI performance under the restrictive paradigms of self-play (teams composed of agents trained together) and cross-play (teams of agents trained independently but using the same algorithm). Recent work has indicated that AI optimized for these narrow settings may make for undesirable collaborators in the real-world. We propose an alternative criteria for evaluating cooperative AI, referred to as inter-algorithm cross-play, where agents are evaluated on teaming performance with all other agents within an experiment pool with no assumption of algorithmic similarities between agents. We show that existing state-of-the-art cooperative AI algorithms, such as Other-Play and Off-Belief Learning, under-perform in this paradigm. We propose the Any-Play learning augmentation—a multi-agent extension of diversity-based intrinsic rewards for zero-shot coordination (ZSC)—for generalizing self-play-based algorithms to the inter-algorithm cross-play setting. We apply the Any-Play learning augmentation to the Simplified Action Decoder (SAD) and demonstrate state-of-the-art performance in the collaborative card game Hanabi.

Any-Play: an Intrinsic Augmentation for Zero-Shot Coordination

As autonomous systems are deployed at a large scale in both public and private spaces, robots owned and operated by competing organisations will be required to interact. Interactions in such settings will be inherently non-cooperative. We therefore address the problem of non-cooperative multi-agent path finding. We design an auction mechanism that allows a group of agents to reach their goals whilst minimising the total cost of the system, in such a way that rational agents are incentivised to participate. Our Privileged Knowledge Auction (PKA) consists of a modified combinatorial Vickrey-Clarke-Groves (VCG) auction. Our approach restricts the initial number of bids in the VCG auction, then uses the privileged knowledge of the auctioneer to identify and solve path conflicts, whilst maintaining the autonomy of individual agents. The mechanism provides a heuristic method to maximise social welfare whilst remaining computationally efficient. We also propose an algorithm which allows individual agents to generate unique and diverse bids, which increases the success likelihood of both the restricted bid VCG auction and our novel approach on synthetic data. Our results on synthetic data outperform existing work on this problem.

Negotiated Path Planning for Non-Cooperative Multi-Robot Systems


Probabilistic Dynamic Epistemic Logic (PDEL) is a formalism for reasoning about the higher-order probabilistic knowledge of agents, and about how this knowledge changes when events occur. While PDEL has been studied for its theoretical appeal, it was only ever applied to toy examples: the combinatorial explosion of probabilistic Kripke structures makes the PDEL framework impractical for realistic applications, such as card games.

This paper is a first step towards the use of PDEL in more practical settings: in line with recent work applying ideas from symbolic model checking to (non-probabilistic) DEL, we propose a ``symbolic'' representation of probabilistic Kripke structures as pseudo-Boolean functions, which can be represented with several data structures of the decision diagram family, in particular Algebraic Decision Diagrams (ADDs). We show that ADDs scale much better than explicit Kripke structures, and that they allow for efficient symbolic model checking, even on the realistic example of the Hanabi card game, thus paving the way towards the practical application of epistemic planning techniques.

A Symbolic Representation for Probabilistic Dynamic Epistemic Logic


It is widely accepted that an ideal community in networks is the onewhose structure is closest to a (maximal) clique. However, in most real-word graphs the clique model is too restrictive, as it requires complete pairwise interactions. More realistic and relaxed forms of cohesive subgraph models were then studied. A k-plex is one of the arguably most studied pseudo-clique model. A k-plex of size n is a subgraph where any vertex is adjacent to at least (n-k) vertices. Unfortunately, some maximal k-plexes are far from representing meaningful communities in complex networks. In this paper, we first introduce a novel variant of k-plex model, called cohesive k-plex, which is more appropriate for modeling real communities. Then, we reduce the problem of enumerating maximal cohesive k-plexes in a graph to those of enumerating the models of a formula in propositional logic. Afterwards, to make our approach more efficient, we provide a graph decomposition technique that is particularly suitable for deriving smaller and independent sub-problems easy to resolve. Finally, extensive experiments on real-world graphs confirm the efficiency and scalability of our proposed approach.

A Declarative Framework for Maximal k-plex Enumeration Problems


Hand-crafting accurate heuristics for optimization problems is often costly due to requiring expert knowledge and time-consuming parameter tuning. Automating this procedure using machine learning has in recent years shown great promise. However, a large number of important problem classes remain unexplored. This paper investigates one such instance by exploring learning-based methods for generating heuristics to perform value-maximizing combinatorial assignment (the partitioning of elements among alternatives). In more detail, we use machine learning together with generating and optimally solving subproblems to produce heuristics that can, for example, be used with search algorithms to find feasible solutions of higher quality more quickly. Our results show that our learned heuristics outperform the state of the art in several benchmarks.

Reducing the Price of Anarchy in Multi-Agent Learning

Downloads

Next from AAMAS 2022

Welfare vs. Representation in Participatory Budgeting

Similar lecture

Learning to Advise and Learning from Advice in Cooperative Multiagent Reinforcement Learning

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES