New Zealand


In the Binary Networked Public Goods game, every player needs to decide if she participates in a public project whose utility is shared equally by the community. We study the problem of deciding if there exists a pure strategy Nash equilibrium (PSNE) in such games. The problem is already known to be NP-complete. We provide fine-grained analysis of this problem under the lens of parameterized complexity theory. We consider various natural graph parameters and show either W[1]-hardness or exhibit an FPT algorithm. Hence, our work allows us to understand the situations better where PSNE serves as a reliable solution concept versus where it is not.

AAMAS 2022

On Parameterized Complexity of Binary Networked Public Goods Game

fully homogeneous

pure strategy nash equilibrium

public goods game

binary networked

w-hierarchy

fixed-parameter tractability

heterogeneous

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


Bayesian persuasion studies how an informed sender should partially disclose information so as to influence the behavior of self-interested receivers. In the last years, a growing attention has been devoted to relaxing the assumption that the sender perfectly knows receiver's payoffs. The first crucial step towards such an achievement is to study the case in which a receiver's payoffs depend on their unknown type, which is randomly determined by a known finite-supported probability distribution. This begets considerable computational challenges, as computing a sender-optimal signaling scheme is inapproximable up to within any constant factor, even in basic settings with a single receiver. In this work, we circumvent this issue by leveraging ideas from mechanism design. In particular, we introduce a type reporting step in which the receiver is asked to report their type to the sender, after the latter has committed to a menu defining a signaling scheme for each possible receiver's type. Surprisingly, we prove that, with a single receiver, the addition of this type reporting stage makes the sender's computational problem tractable. Then, we extend our Bayesian persuasion framework with type reporting to settings with multiple receivers, focusing on the widely-studied case of no inter-agent externalities and binary actions. In such setting, we show that it is possible find a sender-optimal solution in polynomial-time by means of the ellipsoid method, given access to a suitable polynomial-time separation oracle. This can be implemented for supermodular and anonymous sender's utility functions. As for the case of submodular sender's utility functions, we first approximately cast the sender's problem into a linearly-constrained mathematical program whose objective function is the multi-linear extension of the sender's utility. Then, we show how to find in polynomial-time an approximate solution to the program by means of a continuous greedy algorithm. This provides a (1 -1/e)-approximation to the problem, which is tight.

Bayesian Persuasion Meets Mechanism Design: Going Beyond Intractability with Type Reporting


We study the effects of spoofing attacks on frequent call markets (FCMs). Spoofing---a strategic manipulation to mislead market participants by creating spurious limit orders---could harm the market efficiency and has been declared illegal in many countries. However, this practice is still very common, which inspired extensive research on measuring, detecting and curbing such manipulation in the popular market model of continuous double auctions (CDAs). In this paper, we extend this research to frequent call markets and use agent-based modelling to simulate spoofing in this context. Specifically, we apply empirical game-theoretic analysis (EGTA) to compute equilibria of agent-based markets, and demonstrate that while spoofing may be profitable in both market models, it has less impact on FCMs compared to CDAs. Finally, we explore several FCM mechanism designs to help to curb this type of market manipulation even further.

The spoofing resistance of frequent call markets


The last-mile delivery market is highly competitive and is saturated with numerous small operators. In this context, the fierce competition between operators, joint with the rapid increase in the demand for home-delivery, results in a significant increase in urban freight traffic further worsening congestion and pollution. To resolve these issues, previous research has studied the implementation of collaborative last-mile operations, with organisations sharing resources in the form of inventory space or transportation capacity. However, a common limitation of the proposed models is ignoring the effects of externalities such as network congestion due to the increased number of vehicles from selfish routing, and time windows. 

This study proposes a framework to quantify the worst efficiency loss in the urban last-mile delivery system by formulating the fully-decentralised and fully-centralised last-mile delivery problem. In doing so, we develop a Multi-depot Vehicle Routing Problem with Time Windows and Congestible Network that is solved using a bespoke Parallel Hybrid Genetic Algorithm that overcomes the non-linearities from modelling endogenous network congestion. 

The model is evaluated using a case study based on central London to assess the efficiency gaps of a realistic last-mile delivery operation. Our results show that the relative efficiency loss tends to fluctuate the most with a small number of customers until it stabilises to less than 15% for instances with over 100 customers without considering time windows. However, time windows could significantly exacerbate the degradation of efficiency and this degradation is 25% on average.

The Competition and Inefficiency in Urban Road Last-Mile Delivery


The multi-agent pickup and delivery (MAPD) problem, in which multiple agents iteratively carry materials without collisions, has received attention, but the conventional MAPD algorithms usually assume grid-like environments that are specifically designed such as automated warehouses. In these environments, many pickup/delivery locations are deployed where agents can stay for a long time, and the detours to avoid collision are plentiful because of freedom of movement. In contrast, a maze-like environment such as a rescue or a construction site generally has fewer pickup/delivery locations and the numbers may be unbalanced, resulting in many agents concentrating on these locations and inefficient operations. Moreover, the agents easily get stuck to avoid other agents and are deadlocked. Therefore, we propose a deadlock avoidance method, standby-based deadlock avoidance (SBDA), to improve transportation efficiency even in a maze-like environment. The SBDA is an algorithm using standby nodes, which is determined in real-time using the articulation-point-finding algorithm, and in which the agent is guaranteed to wait for any finite time. We demonstrated that our proposed method outperforms the conventional methods in maze-like restricted environments. Then, we analyze how the parameter for selecting standby nodes affects the performance.

Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks


Object pose estimation methods allow finding locations of objects in unstructured environments. This is a highly desired skill for autonomous robot manipulation as robots need to estimate the precise poses of the objects in order to manipulate them. In this paper, we investigate the problems of tactile pose estimation and manipulation for category-level objects. Our proposed method uses a Bayes filter with a learned tactile observation model and a deterministic motion model. Later, we train policies using deep reinforcement learning where the agents use the belief estimation from the Bayes filter. Our models are trained in simulation and transferred to the real world. We analyze the reliability and the performance of our framework through a series of simulated and real-world experiments and compare our method to the baseline work. Our results show that the learned tactile observation model can localize the pose of novel objects at 2-mm and 1-degree resolution for position and orientation, respectively. Furthermore, we experiment on a bottle opening task where the gripper needs to reach the desired grasp state to open the bottle cap.

Tactile Pose Estimation and Policy Learning for Unknown Object Manipulation


Autonomous robots need to be able to efficiently compute long-horizon motion plans for achieving user desired tasks. Hierarchical planning approaches address this problem but require input state and action abstractions to decompose the overall problem and guide motion planners. This paper presents a new approach for bootstrapping the entire abstraction process by learning to predict the critical regions of a configuration space, using them to construct high-level actions as transitions between critical regions, and finally, by using the discovered actions to efficiently compute long-horizon motion plans. We also propose methods for auto-generating robot- and environment-specific deep neural network architectures for predicting high-dimensional critical regions in the configuration space. The overall algorithm is probabilistically complete and guaranteed to return sound abstractions of configuration spaces for holonomic robots. We evaluated our hierarchical approach based on learned abstractions against state-of-the-art sampling-based motion planners on a range of environments. The results show that our approach reduces the time required to compute motion plans by the magnitude of 10 compared to other motion planners.

Using Deep Learning to Bootstrap Abstractions for Hierarchical Robot Planning


Many multi-robot planning problems are burdened by the curse of dimensionality, which compounds the difficulty of applying solutions to large-scale problem instances. The use of learning-based methods in multi-robot planning holds great promise as it enables us to offload the online computational burden of expensive centralized, yet optimal solvers, to an offline learning procedure. The hope is that by training a policy to copy an optimal pattern generated by a small-scale (centralized) system, we can transfer that policy to much larger, decentralized systems while maintaining near-optimal performance. Yet, a number of issues impede us from leveraging this idea to its full potential. This blue-sky paper elaborates some of the key challenges that remain.

The Holy Grail of Multi-Robot Planning: Learning to Generate Online-Scalable Solutions from Offline-Optimal Experts


Multi-agent reinforcement learning (MARL) requires coordination by some means of interaction between agents to efficiently solve tasks. Interaction graphs allow reasoning about joint actions based on the local structure of interactions, but they disregard the potential impact of an agent’s action on its neighbors’ behaviors, which could rapidly alter in dynamic settings. In this paper, we thus present a novel perspective on opponent modeling in domains with only local interactions using (level-1) Graph Probabilistic Recursive Reasoning (GrPR2). Unlike previous work on recursive reasoning, each agent iteratively best-responds to other agents’ policies over all possible local interactions. Agents’ policies are approximated via a variational Bayes scheme for capturing their uncertainties, and we prove that an induced variant of Q-learning converges under self-play when there exists only one Nash equilibrium. In cooperative settings, we further devise a variational lower bound on the likelihood of each agent's optimality. Opposed to other models, optimizing the resulting objective prevents each agent from attaining an unrealistic modelling of others, and yields an exact tabular Q-iteration method that holds convergence guarantees. Then, we deepen the recursion to level-k via Cognitive Hierarchy GrPR2 (GrPR2-CH), which lets each level-k player best-respond to a mixture of strictly lower levels in the hierarchy. We prove that: (1) level-3 reasoning is the optimal hierarchical level, maximizing each agent's expected return; and (2) the weak spot of the classical CH models is that 0-level is uniformly distributed, as it may introduce policy bias. Finally, we propose a practical actor-critic scheme, and illustrate that GrPR2-CH outperforms strong MARL baselines in the particle environment.

Optimizing Multi-Agent Coordination via Hierarchical Graph Probabilistic Recursive Reasoning


Centaurs are half-human, half-AI decision-makers where the AI's goal is to complement the human. To do so, the AI must be able to recognize the goals and constraints of the human and have the means to help them. We present a novel formulation of the interaction between the human and the AI as a sequential game where the agents are modelled using Bayesian best-response models. We show that in this case the AI's problem of helping bounded-rational humans make better decisions reduces to a Bayes-adaptive POMDP. In our simulated experiments, we consider an instantiation of our framework for humans who are subjectively optimistic about the AI's future behaviour. Our results show that when equipped with a model of the human, the AI can infer the human's bounds and nudge them towards better decisions. We discuss ways in which the machine can learn to improve upon its own limitations as well with the help of the human. We identify a novel trade-off for centaurs in partially observable tasks: for the AI's actions to be acceptable to the human, the machine must make sure their beliefs are sufficiently aligned, but aligning beliefs might be costly. We present a preliminary theoretical analysis of this trade-off and its dependence on task structure.

Best-Response Bayesian Reinforcement Learning with BA-POMDPs for Centaurs


Despite recent breakthroughs for learning a rich set of behaviors in simulated tasks, reinforcement learning agents are not yet in widespread use in the real world where rewards are naturally sparse. In fact, efficient exploration remains a key challenge in sparse-reward tasks as it requires quickly finding informative and task-relevant experiences. While cloning behaviors provided by an expert is a promising approach to the exploration problem, learning from a fixed set of demonstrations may be impracticable due to lack of state coverage or distribution mismatch - when the learner’s goal deviates from the demonstrated behaviors. Moreover, we aim to obtain a policy that can accomplish a variety of goals guided by the same set of demonstrations (i.e. without additional human effort). We present a goal-conditioned method that leverages very small sets of goal-driven demonstrations to significantly accelerate learning. Crucially, we present the concept of active goal-driven demonstrations to query the demonstrator only in hard-to-learn and uncertain regions of the state space. We evaluate our framework on a set of robot control tasks. The present work outperforms prior imitation learning approaches in most of the tasks in terms of data efficiency and average scores while reducing the amount of human effort.

On Parameterized Complexity of Binary Networked Public Goods Game

Downloads

Next from AAMAS 2022

Bayesian Persuasion Meets Mechanism Design: Going Beyond Intractability with Type Reporting

Similar lecture

Parameterized Algorithms for Kidney Exchange

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

On Parameterized Complexity of Binary Networked Public Goods Game

.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

Bayesian Persuasion Meets Mechanism Design: Going Beyond Intractability with Type Reporting

Similar lecture

Parameterized Algorithms for Kidney Exchange

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads