New Zealand


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.

AAMAS 2022

Learning Heuristics for Combinatorial Assignment by Optimally Solving Subproblems

inapproximability

coalition formation

operations research

combinatorial auctions

heuristic search

combinatorial optimization

machine learning

neural networks

deep learning

We are pleased to announce the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25), which will be held in Philadelphia, Pennsylvania at the Pennsylvania Convention Center from February 25 to March 4, 2025.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

### [Invited Speakers](https://aaai.org/conference/aaai/aaai-25/aaai-25-invited-speakers/)

Register [here](https://aaai.org/conference/aaai/aaai-25/registration/)

AAAI 2025

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.



technical paper

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

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


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 single-elimination knockout tournaments, participants face each other based on a starting seeding and progress to the next rounds by beating their direct opponents.
In this paper we initiate the study of coalitional knockout tournaments, which generalise single-elimination knockout tournaments by allowing groups of players, or coalitions, to strategically select one of their members to take part in the tournament, following the starting seeding. We investigate the algorithmic properties of pure strategies Nash equilibria in these games under various setups, i.e., whether or not choices can be made at each round and whether or not tournament progression is important to the group. Despite the more complex tournament structure when compared to single-elimination, we provide tractable algorithms for all cases. Our results can be applied to those tournaments where pre-play selection plays an important role, such as sport events or elections with run-off.

Equilibrium Computation For Knockout Tournaments Played By Groups


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


In collaborative tasks involving human and robotic teammates, live communication between agents has potential to substantially improve task efficiency and fluency. Effective communication provides essential situational awareness to adapt successfully during uncertain situations and encourage informed decision-making. In contrast, poor communication can lead to incongruous mental models resulting in mistrust and failures. In this work, we first introduce characterizations of and generative algorithms for two complementary modalities of visual guidance: prescriptive guidance (visualizing recommended actions), and descriptive guidance (visualizing state space information to aid in decision-making). Robots can communicate this guidance to human teammates via augmented reality (AR) interfaces, facilitating synchronization of notions of environmental uncertainty and offering more collaborative and interpretable recommendations. We also introduce a decentralized min-entropy multi-agent collaborative planning algorithm for uncertain environments, informing the generation of these proactive visual recommendations for more informed human decision-making. We illustrate the effectiveness of our algorithm and compare these different modalities of AR-based guidance in a human subjects study involving a collaborative, partially observable search task. Finally, we synthesize our findings into actionable insights informing the use of prescriptive and descriptive visual guidance.

Descriptive and Prescriptive Visual Guidance to Improve Shared Situational Awareness in Human-Robot Teaming


Fairness has emerged as an important concern in automated decision-making in recent years, especially when these decisions affect human welfare. In this work, we study fairness in temporally extended decision-making settings, specifically those formulated as Markov Decision Processes (MDPs). Our proposed notion of fairness ensures that each state-action pairs' long-term visitation frequency is more than a specified fraction. This quota based notion of fairness is natural in most resource-allocation settings where the dynamics of a single resource being allocated is governed by an MDP and the distribution of the shared resource is captured by its state-action visitation frequency. In an average-reward MDP (AMDP) setting, we formulate the problem as a bilinear saddle point program and, for a generative model, solve it using a Stochastic Mirror Descent (SMD) based algorithm. The proposed solution guarantees a simultaneous approximation on the expected average-reward and fairness requirement. We give sample complexity bounds for the proposed algorithm and validate our theoretical results with experiments on a simulated data.

Long-Term Resource Allocation Fairness in Average Markov Decision Process (AMDP) Environment


Simulators offer a scalable platform to train robots, offering a path to creative and innovative solutions that are difficult for humans to envision a priori. We introduce a way to leverage this property, along with a new paradigm where robots discover creative solutions in simulation, then teach humans or other agents to physically execute the learned solutions via reverse teleoperation. We provide various examples ranging from learning new skills, to rehabilitation, to everyday activities, where such a system would be valuable.

Robots Teaching Humans: A New Communication Paradigm via Reverse Teleoperation


Ensemble methods are built by training many different models and aggregating their outputs to output the prediction of the whole system. In this work, we study the behavior of an ensemble method where voting rules are used to aggregate the output of a set of randomly-generated classifiers. We provide both a theoretical and an empirical analysis of this method, showing that it performs comparably with other state-of-the-art ensemble methods, while not requiring any domain expertise to fine-tune the individual classifiers.

Downloads

Next from AAMAS 2022

Welfare vs. Representation in Participatory Budgeting

Similar lecture

Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation

.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

Welfare vs. Representation in Participatory Budgeting

Similar lecture

Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation

Downloads