New Zealand


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.

AAMAS 2022

Equilibrium Computation For Knockout Tournaments Played By Groups

coalitional strategies

single-elimination tournaments

equilibria

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


Social decision schemes (SDSs) map the preferences of a group of voters over some set of m alternatives to a probability distribution over the alternatives. A seminal characterization of strategyproof SDSs by Gibbard (1977) implies that there are no strategyproof Condorcet extensions and that only random dictatorships satisfy ex post efficiency and strategyproofness. The latter is known as the random dictatorship theorem. We relax Condorcet-consistency and ex post efficiency by introducing a lower bound on the probability of Condorcet winners and an upper bound on the probability of Pareto-dominated alternatives, respectively. We then show that the SDS that assigns probabilities proportional to Copeland scores is the only anonymous, neutral, and strategyproof SDS that can guarantee the Condorcet winner a probability of at least 2/m. Moreover, no strategyproof SDS can exceed this bound, even when dropping anonymity and neutrality. Secondly, we prove a continuous strengthening of Gibbard's random dictatorship theorem: the less probability we put on Pareto-dominated alternatives, the closer to random dictatorship is the resulting SDS. Finally, we show that the only anonymous, neutral, and strategyproof SDSs that maximize the probability of Condorcet winners while minimizing the probability of Pareto-dominated alternatives are mixtures of the uniform random dictatorship and the randomized Copeland rule.

Relaxed Notions of Condorcet-Consistency and Efficiency for Strategyproof Social Decision Schemes


We study political parties that strategically place their candidates in districts so to maximise the number of their nominees that get elected.In each district, voters rank the nominated candidates and elect the plurality winners. After studying equilibrium existence in restricted instances, we show that deciding the existence of pure Nash equilibria for these games is Σ2P-complete, for the hardness part of which we reduce from ∃∃!-3SAT.

Computing Nash Equilibria for District-based Nominations


Bribery in an election is one of the well-studied control problems in computational social choice. In this paper, we propose and study the safe bribery problem. Here the goal of the briber is to ask the bribed voters to vote in such a way that the briber never prefers the original winner (of the unbribed election) more than the new winner, even if the bribed voters do not fully follow the briber's advice. Indeed, in many applications of bribery, campaigning for example, the briber often have limited control on whether the bribed voters eventually follow the recommendation of the briber and thus it is conceivable that the bribed voters can either partially or fully ignore the briber's recommendation. We provide a comprehensive complexity theoretic landscape of the safe bribery problem for many common voting rules in this paper.

How Hard is Safe Bribery?


In many applications, the desire is to change the behavior of users over a period of repeated episodes of similar decision making. For example, in a nutritionist scenario, one may try to encourage the user to adopt better food consumption habits. In this paper, we propose to model this recommendation scenario with a long-term goal, that we call coaching, as an iterative two-player game. At each decision time, the user makes a proposal (e.g., a meal) based on her/his preferences, the coach can then suggest a change in this proposal that the user may or may not accept. After each episode, the user updates her/his preferences and the coach adapts its model of the user.

We propose a formalization of the coaching problem and discuss several possible criteria to measure the performance of a coach. 
Different coaching strategies are described in the paper. They are then tested and compared using a real-world dataset in the field of nutrition, where a user is simulated using a simple, but general, model of decision making and adaptation. Results show that it pays to adapt to user characteristics and use non-myopic strategies, which aim for long-term gains, when the number of interactions becomes large. 

Although illustrated on choice sequences for food consumption, the scope of the proposed method goes far beyond this use case, as in sports, health, entertainment or tourist activity choices, etc.

Coaching agent: making recommendations for behavior change. A case study on improving eating habits


Cooperation is an overarching aspiration of artificial intelligence (AI) research. Recent studies demonstrate that AI agents trained with deep reinforcement learning are capable of interacting and collaborating with humans. These studies have primarily evaluated human compatibility and intelligence through "objective" metrics like task performance, obscuring potential variation in the levels of trust and subjective preference that different agents generate. To better understand the factors shaping subjective preferences in human-agent cooperation, we train deep reinforcement learning agents in Coins, a two-player social dilemma. We recruit participants for a human-agent cooperation study, and measure their social perception of the agents they encounter. Participants' perceptions of warmth and competence predict their preferences for different agents, above and beyond objective performance metrics. Drawing inspiration from social science and biology research, we subsequently implement a new "partner choice" framework to elicit revealed preferences: after playing an episode with an agent, participants are asked whether they would like to play the next round with the same agent or to play alone. As with stated preferences, social perception better predicts participants' revealed preferences than does objective performance. Given these findings, we recommend human-agent interaction researchers routinely incorporate the measurement of social perception and subjective preferences into their studies.


Warmth and Competence in Human-Agent Cooperation


In sequential decision making -- whether it's realized with or without the benefit of a model -- objectives are often underspecified or incomplete. This gives discretion to the acting agent to realize the stated objective in ways that may result in undesirable outcomes, including inadvertently creating an unsafe environment or indirectly impacting the agency of humans or other agents that typically operate in the environment. In this paper, we explore how to build a reinforcement learning (RL) agent that contemplates the impact of its actions on the wellbeing and agency of others in the environment, most notably humans. We endow RL agents with the ability to contemplate such impact by augmenting their reward based on expectation of future return by others in the environment, providing different criteria for characterizing impact. We further endow these agents with the ability to differentially factor this impact into their decision making, manifesting behaviour that ranges from self-centred to self-less, as demonstrated by experiments in gridworld environments.

Be Considerate: Avoiding Negative Side Effects in Reinforcement Learning


Confronted with patients suffering from Alzheimer's disease, professional caregivers must be aware of their own non-verbal communication as well as the patient's non-verbal communication in order to respond to the behavioural disorders which are frequent in this disease (e.g. apathy, aggression, anxiety, etc...). Virtual patients, which are interactive animated characters that simulate the behaviors of a patient, are increasingly used to train caregivers to interact with patients. The virtual patient needs to dynamically generate multimodal expressions of pathological behaviors consistent with the pedagogical goals. In this article, we introduce COPALZ (COmputational model of Pathological appraisal biases for a virtual ALZheimer's patient), a new model that supports the generation of pathological behaviors identified as pedagogically relevant for caregivers interacting with Alzheimer's patients. This model is based on the theory of appraisal biases and on interaction data that we collected using a partially simulated version of our virtual patient with 31 caregivers. We describe initial evaluations and explain how we intend to evaluate the fully automatic virtual patient during training sessions.

COPALZ: A Computational Model of Pathological Appraisal Biases for an Interactive Virtual Alzheimer Patient


Training a multi-agent reinforcement learning (MARL) model with a sparse reward is generally difficult because numerous combinations of interactions among agents induce a certain outcome (i.e., success or failure). Earlier studies have tried to resolve this issue by employing an intrinsic reward to induce interactions that are helpful for learning an effective policy. However, this approach requires extensive prior knowledge for designing an intrinsic reward. To train the MARL model effectively without designing the intrinsic reward, we propose a learning-based exploration strategy to generate the initial states of a game. The proposed method adopts a variational graph autoencoder to represent a game state such that (1) the state can be compactly encoded to a latent representation by considering relationships among agents, and (2) the latent representation can be used as an effective input for a coupled surrogate model to predict an exploration score. The proposed method then finds new latent representations that maximize the exploration scores and decodes these representations to generate initial states from which the MARL model starts training in the game and thus experiences novel and rewardable states. We demonstrate that our method improves the training and performance of the MARL model more than the existing exploration methods.

REMAX: Relational Representation for Multi-Agent Exploration


Critical sectors of human society are progressing toward the adoption of powerful artificial intelligence (AI) agents, which are trained individually on behalf of self-interested principals but deployed in a shared environment. Short of direct centralized regulation of AI, which is as difficult an issue as regulation of human actions, one must design institutional mechanisms that indirectly guide agents' behaviors to safeguard and improve social welfare in the shared environment. Our paper focuses on one important class of such mechanisms: the problem of adaptive incentive design, whereby a central planner intervenes on the payoffs of an agent population via incentives in order to optimize a system objective. To tackle this problem in high-dimensional environments whose dynamics may be unknown or too complex to model, we propose a model-free meta-gradient method to learn an adaptive incentive function in the context of multi-agent reinforcement learning. Via the principle of online cross-validation, the incentive designer explicitly accounts for its impact on agents' learning and, through them, the impact on future social welfare. Experiments on didactic benchmark problems show that the proposed method can induce selfish agents to learn near-optimal cooperative behavior and significantly outperform learning-oblivious baselines. When applied to a complex simulated economy, the proposed method finds tax policies that achieve better trade-off between economic productivity and equality than baselines, a result that we interpret via a detailed behavioral analysis.

Adaptive Incentive Design with Multi-Agent Meta-Gradient Reinforcement Learning


Machine learning of Theory of Mind (ToM) is essential to build social agents that co-live with humans and other agents. This capacity, once acquired, will help machine infer the mental states of others from observed contextual action trajectories, enabling future prediction of goals, intention, actions and successor representations. The underlying mechanism for such a prediction remains unclear, however. Inspired by the observation that humans often infer the character traits of others, then use it to explain behaviour, we propose a new neural ToM architecture that learns to generate a latent trait vector of an actor from the past trajectories. This trait vector then multiplicatively modulates the prediction mechanism via the so-called ‘fast weights’ scheme in the prediction neural network, which reads the current context and predicts the future. We empirically show that the fast weights provide a good inductive bias to model the character traits of agents and hence improves mind reading ability. On the indirect assessment of false-belief understanding, the new ToM model enables more efficient helping behaviours.

Downloads

Next from AAMAS 2022

Relaxed Notions of Condorcet-Consistency and Efficiency for Strategyproof Social Decision Schemes

Similar lecture

On the Average-Case Complexity of Predicting Round-Robin Tournaments

.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

Relaxed Notions of Condorcet-Consistency and Efficiency for Strategyproof Social Decision Schemes

Similar lecture

On the Average-Case Complexity of Predicting Round-Robin Tournaments

Downloads