United Kingdom

Search has played a fundamental role in computer game research since the very beginning.   And while online search has been commonly used in perfect information games such as Chess and Go, online search methods for imperfect information games have only been introduced relatively recently. This paper addresses the question of what is a sound online algorithm in an imperfect information setting of two-player zero-sum games? We argue that the fixed-strategy definitions of exploitability and epsilon-Nash equilibria are ill suited to measure the worst-case performance of an online algorithm. We thus formalize epsilon-soundness, a concept that connects the worst-case performance of an online algorithm to the performance of an epsilon-Nash equilibrium. Our definition of soundness and the consistency hierarchy finally provide appropriate tools to analyze online algorithms in repeated imperfect information games.  We thus inspect some of the previous online algorithms in a new light, bringing new insights into their worst case performance guarantees.

AAMAS 2021

Sound Algorithms in Imperfect Information Games

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 2022

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

poster

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://assets.underline.io/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

Institutions and investors face the constant challenge of making accurate decisions and predictions regarding how best they should distribute their endowments. The problem of achieving an optimal outcome at minimal cost has been extensively studied and resolved using several heuristics. However, these works fail to address how an external decision maker can target different types of fair behaviour and how limited information can shape this complex interplay. Here, we consider the well-known Ultimatum game in a spatial setting and propose a hierarchy of interference mechanisms based on the amount of information available to the external decision maker and desired standards of fairness. Our key findings show that asymmetric interactions have drastically different dynamics when compared to symmetric games, such as the Prisoner's Dilemma, and discuss why gathering information about the agents' behaviour allows for the most efficient investment strategies.

Promoting Fair Proposers, Fair Responders or Both? Cost-Efficient Interference in the Spatial Ultimatum Game

We tackle the problem of allocating teams to tasks. For that, we propose a novel allocation problem that matches teams with tasks based on the similarity between the competencies required by the tasks and the competencies offered by teams. We formally cast our problem as an optimisation problem, characterise the size of its search space and outline a heuristic approach to solve it.

Towards a Competence-Based Approach to Allocate Teams to Tasks

Liquid Democracy (LD) uses transitive delegations in voting. In its simplest form, it is used for binary decisions, however its promise holds also for more advanced voting settings. Here we consider LD in the context of Participatory Budgeting (PB), which is a direct democracy approach to budgeting, most usually done in municipal budgeting processes. In particular, we study Knapsack Voting, in which PB voters approve projects, such that the sum of costs of projects each voter approves must respect the budget limit. We observe possible inconsistencies, as the cost of voter-approved projects may go over the budget limit after resolving delegations. We offer ways to overcome them by studying the computational complexity of updating as few delegations as possible to arrive  after following all project delegations  to a consistent profile.

Preserving Consistency for Liquid Knapsack Voting

A finite-time consensus protocol is developed for a connected network of agents, where communication between agents occurs locally, some of the agents are malicious, and the non-malicious or cooperative agents do not know the identities of the malicious ones. The agents are modeled with first-order dynamics, and the inputs to each agent that enable consensus are designed using the principles of sliding mode control (SMC). The use of the SMC algorithm guarantees finite-time consensus and ensures that in the transient stage, the agents' states are contained within the convex hull formed by their initial conditions (ICs). With this feature and by modeling the network as a connected graph, the protocol guarantees consensus amongst the cooperative agents when the malicious agents transmit values of their states lying outside the convex hull of ICs, and the graph formed by the cooperative agents with the removal of the malicious agents is strongly connected. The protocol does not require a cooperative agent to know the number of malicious or other cooperative agents in the network, and is based only on local communication.

Finite-time Consensus in the Presence of Malicious Agents

Crowdfunding has become an effective way of raising capital for
developing and producing new products. In a typical crowdfunding campaign, a fundraiser (a seller) sets a product pre-buy price
and a campaign success threshold. Consumers can indicate their
willingness to pay the pre-buy price now, in exchange of a product
in the future. Only when the number of consumers who commit to
pre-buy exceeds the threshold, the crowdfunding is successful and
the seller gets the corresponding pre-buy payments.
A series of works has modeled crowdfunding as imperfect information games, where each player (potential contributor) has a
private valuation for the product, and has characterized the equilibrium behavior for some specific settings [1–4]. Other works focus
on the effectiveness or the moral hazard of the crowdfunding campaigns by regarding it as an option to raise money for either private
[5, 9, 10] or public projects [6–8].
However, the strategic aspect of crowdfunding from the seller’s
perspective hasn’t attracted its deserved attention. In this paper,
we take a mechanism design perspective and explore how a seller
can design crowdfunding campaigns to maximize his profit. In
addition to choosing the pre-buy price and the campaign success
threshold for a crowdfunding campaign, the seller in our paper can
consider two richer design variants: (1) choose two price-threshold
pairs where a pre-buy price discount is given when the number
of committed buyers exceeds the larger threshold, and (2) offer
two differentiating products (simplified vs. standard) and set two
success thresholds such that the advanced product will be delivered
if the larger threshold is reached. We examine the optimal profit
achieved in each scheme. Somewhat surprisingly, the richer design
variants may not improve the seller’s profit.

Optimal Crowdfunding Design

Conditional preference statements have been used to compactly represent preferences over combinatorial domains. They are at the core of CP-nets and their generalizations, and lexicographic preference trees. Several works have addressed the complexity of some queries (optimization, dominance in particular). We extend in this paper some of these results, and study other queries which have not been addressed so far, like equivalence, thereby contributing to a knowledge compilation map for languages bas­ed on conditional preference statements. We also introduce a new parameterised family of languages, which enables to balance expressiveness against the complexity of some queries.

A Knowledge Compilation Map for Conditional Preference Statements-based Languages

Multi-agent influence diagrams (MAIDs) are a popular form of graphical model that, for certain classes of games, have been shown to offer key complexity and explainability advantages over traditional extensive form game (EFG) representations. In this paper, we extend previous work on MAIDs by introducing the concept of a MAID subgame, as well as subgame perfect and trembling hand perfect equilibrium refinements. We then prove several equivalence results between MAIDs and EFGs. Finally, we describe an open source implementation for reasoning about MAIDs and computing their equilibria.

Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice

This paper presents new algorithms and theoretical results for solutions to Multi-action Multi-armed Restless Bandits, an important but insufficiently studied generalization of traditional Multi-armed Restless Bandits (MARBs). Though MARBs are popular for modeling many problems, they are restricted to binary actions, i.e., "to act or not to act". This renders them unable to capture critical complexities faced by planners in real domains, such as a system manager balancing maintenance, repair, and job scheduling, or a health worker deciding among treatments for a given patient. Limited previous work on Multi-action MARBs has only been specialized to sub-problems. Here we derive multiple algorithms for use on general Multi-action MARBs using Lagrangian relaxation techniques, leading to the following contributions: (i) We develop BLam, a bound optimization algorithm which leverages problem convexity to quickly and provably converge to the well-performing Lagrange policy; (ii) We develop SampleLam, a fast sampling technique for estimating the Lagrange policy, and derive a concentration bound to investigate its convergence properties; (iii) We derive best and worst case computational complexities for our algorithms as well as our main competitor; (iv) We provide experimental results comparing our algorithms to baselines on simulated distributions, including one motivated by a real-world community health intervention task. Our approach achieves significant, up to ten-fold speedups over more general methods without sacrificing performance and is widely applicable across general Multi-action MARBs. Code is available at https://github.com/killian-34/MAMARB-Lagrange-Policies.

Beyond "To Act or Not to Act": Fast Lagrangian Approaches to General Multi-Action Restless Bandits

Partially Observable Monte-Carlo Planning (POMCP) is a powerful online algorithm able to generate approximate policies for large Partially Observable Markov Decision Processes. The online nature of this method supports scalability by avoiding complete policy representation. The lack of an explicit representation however hinders interpretability. In this work, we propose a methodology based on Satisfiability Modulo Theory (SMT) for analyzing POMCP policies by inspecting their traces, namely sequences of belief-action-observation triplets generated by the algorithm. The proposed method explores local properties of policy behavior to identify unexpected decisions. We propose an iterative process of trace analysis consisting of three main steps, i) the definition of a 
 by means of a parametric logical formula describing (probabilistic) relationships between beliefs and actions, ii) the generation of an 
 by computing the parameters of the logical formula that maximize the number of satisfied clauses (solving a MAX-SMT problem), iii) the analysis of the generated logical formula and the related decision boundaries for identifying unexpected decisions made by POMCP with respect to the original question. We evaluate our approach on Tiger, a standard benchmark for POMDPs, and a real-world problem related to mobile robot navigation. Results show that the approach can exploit human knowledge on the domain, outperforming state-of-the-art anomaly detection methods in identifying unexpected decisions. An improvement of the Area Under Curve up to 47% has been achieved in our tests.

Identification of Unexpected Decisions in Partially Observable Monte-Carlo Planning: A Rule-Based Approach

A key issue in artificial intelligence methods for interactive preference elicitation is choosing at each stage an appropriate query to the user, in order to find a near-optimal solution as quickly as possible. A theoretically attractive method is to choose a query that minimises max setwise regret (which corresponds to the worst case loss response in terms of value of information). We focus here on the situation in which the choices are represented explicitly in a database, and with a model of user utility as a weighted sum of the criteria; in this case when the user makes a choice, an agent learns a linear constraint on the unknown vector of weights. We develop an algorithmic method for computing minimax setwise regret for this form of preference model, by making use of a SAT solver with cardinality constraints to prune the search space, and computing max setwise regret using an extreme points method. Our experimental results demonstrate the feasibility of the approach and the very substantial speed up over the state of the art.

Sound Algorithms in Imperfect Information Games

Next from AAMAS 2021

Promoting Fair Proposers, Fair Responders or Both? Cost-Efficient Interference in the Spatial Ultimatum Game

Similar lecture

Lyapunov Exponents for Diversity in Differentiable Games

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES