New Zealand


Formal verification of strategic abilities is a hard problem. We propose to use the methodology of assume-guarantee reasoning in order to facilitate model checking of alternating-time temporal logic with imperfect information and imperfect recall.

AAMAS 2022

Towards Assume-Guarantee Verification of Strategic Ability

strategic ability

assume-guarantee reasoning

model checking

ECAI2020 featured a full programme of technical papers, as well as many AI-related events of interest for researchers, students and all attendants who are interested on contemporary AI, including:




**An extensive programme of workshops, tutorials, and invited speakers**

**The Prestigious Applications of Intelligent Systems conference (PAIS)**

**The Frontiers in AI track sessions**

**The Lab To Market event**

**The Women in AI time**

**The EU Challenges forum**

… and many more!

ECAI 2020

ECAI 2020 featured a full programme of technical papers, as well as many AI-related events of interest for researchers, students and all attendants who are interested on contemporary AI.

poster

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


Two actively researched problem settings in matchings under preferences are popular matchings and the three-dimensional stable matching problem with cyclic preferences. In this paper, we apply the optimality notion of the first topic to the input characteristics of the second one. We investigate the connection between stability, popularity, and their strict variants, strong stability and strong popularity in three-dimensional instances with cyclic preferences. Furthermore, we also derive results on the complexity of these problems when the preferences are derived from master lists.

Three-Dimensional Popular Matching with Cyclic Preferences

We consider the well-studied many-to-one bipartite matching problem of assigning applicants $\A$ to posts $\B$ where applicants rank posts in the order of preference. This setting models many important real-world allocation problems like assigning students to courses, applicants to jobs, amongst many others. In such scenarios, it is natural to ask for an allocation that satisfies guarantees of the form ``match at least 80\% of applicants to one of their top three choices'' or ``it is unacceptable to leave more than 10\% of applicants unassigned''. The well-studied notions of rank-maximality and fairness fail to capture such requirements due to their property of optimizing extreme ends of the {\em signature} of a matching. We, therefore, propose a novel optimality criteria, which we call as the ``cumulative better signature''.

We investigate the computational complexity of the new notion of optimality in the setting where posts have associated {\em fixed} quotas. We prove that under the fixed quota setting, the problem turns out to be NP-hard under severe restrictions. We provide randomized algorithms in the fixed quota setting when the number of ranks is constant. We also study the problem under a {\em cost-based quota} setting and show that min-cost cumulative better matching can be computed efficiently. Apart from circumventing the hardness, the cost-based quota setting is motivated by real-world applications like course allocation, school choice where the capacities or quotas need not be rigid.

Optimal Matchings with One-Sided Preferences: Fixed and Cost-Based Quotas

The stable matching problem sets the economic foundation of several practical applications ranging from school choice and medical residency to ridesharing and refugee placement. It is concerned with finding a matching between two disjoint sets of agents wherein no pair of agents prefer each other to their matched partners. The Deferred Acceptance (DA) algorithm is an elegant procedure that guarantees a stable matching for any input; however, its outcome may be unfair as it always favors one side by returning a matching that is optimal for one side (say men) and pessimal for the other side (say women). A desirable fairness notion is minimizing the sex-equality cost, i.e. the difference between the total rankings of both sides. Computing such stable matchings is a strongly NP-hard problem, which raises the question of what tractable algorithms to adopt in practice. We conduct a series of empirical evaluations on the properties of sex-equal stable matchings when preferences of agents on both sides are correlated. Our empirical results suggest that under correlated preferences, the DA algorithm returns stable matchings with low sex-equality cost, which further confirms its broad use in many practical applications.

Fair Stable Matching Meets Correlated Preferences


It is an established fact in behavioral economics that in lab experi-
ments of auctions, human subjects do not adhere to the risk-neutral
Bayesian Nash equilibria of such games. Several attempts at explain-
ing this Overbidding Puzzle focus on the bidders’ psychology and
suggest they may have parametrized utility functions that differ
from the risk-neutral payoff. However, analytical equilibria of the
resulting modified games are generally not available. Consequently,
it has been difficult to identify the specific parameters and assess
the merits of these proposed modifications in explaining empirical
observations.
With recent advances in equilibrium learning, it has become
tractable to compute approximations of Bayesian Nash equilibria.
Building on these advances and Bayesian optimization, we propose
a novel regression framework to infer unobserved parameters of
Bayesian games from behavioral data. We apply our method to two
data sets of human bidding behavior in all-pay auctions. For the first
time, this makes it possible to directly compare the goodness-of-fit
of several proposed qualitative explanations of overbidding.

Approaching the Overbidding Puzzle in All-Pay Auctions: Explaining Human Behavior through Bayesian Optimization and Equilibrium Learning


We study the NP-hard Fair Connected Districting problem: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios, such as district-based elections, where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. We conduct a fine-grained analysis of the (parameterized) computational complexity of Fair Connected Districting: We study its parameterized complexity with respect to various graph parameters, including treewidth, and problem-specific parameters, including the numbers of colors and districts, and its complexity on graphs from different classes (such as paths, stars, and trees).

A Refined Complexity Analysis of Fair Districting over Graphs


We present a Nash equilibrium analysis for single-buyer singleseller multi-unit k-double auctions for scaling-based bidding strategies. We then design a Deep Deterministic Policy Gradient (DDPG) based learning strategy, DDPGBBS, for a participating agent to suggest bids that approximately achieve the above Nash equilibrium. We expand DDPGBBS to be helpful in more complex settings with multiple buyers/sellers trading multiple units in a Periodic Double Auction (PDA), such as the wholesale market in smart-grids. We demonstrate the efficacy of DDPGBBS with Power Trading Agent Competition’s (PowerTAC) wholesale market PDA as a testbed.

Multi-unit Double Auctions: Equilibrium Analysis and Bidding Strategy using DDPG in Smart-grids


The recent emergence of navigational tools has changed traffic patterns and has now enabled new types of congestion-aware routing control like dynamic road pricing. Using the fundamental diagram of traffic flows - applied in macroscopic and mesoscopic traffic modeling - the article introduces a new N-player dynamic routing game with explicit congestion dynamics. The model is well-posed and can reproduce heterogeneous departure times and congestion spill back phenomena. However, as Nash equilibrium computations are PPAD-complete, solving the game becomes intractable for large but realistic numbers of vehicles N. Therefore, the corresponding mean field game is also introduced. Experiments were performed on several classical benchmark networks of the traffic community: the Pigou, Braess, and Sioux Falls networks with heterogeneous origin, destination and departure time tuples. The Pigou and the Braess examples reveal that the mean field approximation is generally very accurate and computationally efficient as soon as the number of vehicles exceeds a few dozen. On the Sioux Falls network (76 links, 100 time steps), this approach enables learning traffic dynamics with more than 14,000 vehicles.

Solving N player dynamic routing games with congestion: a mean field approach


Reconfigurable multi-agent systems consist of a set of autonomous agents, with integrated interaction capabilities that feature oppor tunistic interaction. Agents seemingly reconfigure their interactions interfaces by forming collectives, and interact based on mutual interests. Finding ways to design and analyse the behaviour of these systems is a vigorously pursued research goal. We propose a model checker, named R-CHECK, to allow reasoning about these systems both from an individual- and a system- level. R-CHECK also permits reasoning about interaction protocols and joint missions. R-CHECK supports a high-level input language with symbolic semantics, and provides a modelling convenience for interaction features such as reconfiguration, coalition formation, self-organisation, etc.

R-CHECK: A Model Checker for Verifying Reconfigurable MAS

**Read paper on the following link:**

https://ifaamas.org/Proceedings/aamas2022/pdfs/p1768.pdf

**Abstract:**



On the Complexity of Controlling Amendment and Successive Winners

**Read paper on the following link:**

https://ifaamas.org/Proceedings/aamas2022/pdfs/p1780.pdf

**Abstract:**



Towards Assume-Guarantee Verification of Strategic Ability

Downloads

Next from AAMAS 2022

Three-Dimensional Popular Matching with Cyclic Preferences

Similar lecture

A Logic of Explicit and Implicit Distributed Belief

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Towards Assume-Guarantee Verification of Strategic Ability

.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

Three-Dimensional Popular Matching with Cyclic Preferences

Similar lecture

A Logic of Explicit and Implicit Distributed Belief

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads