United Kingdom

We present a scalable tree search planning algorithm for large multi-agent sequential decision problems that require dynamic collaboration. Teams of agents need to coordinate decisions in many domains, but naive approaches fail due to the exponential growth of the joint action space with the number of agents. We circumvent this complexity through an anytime approach that allows us to trade computation for approximation quality and also dynamically coordinate actions. Our algorithm comprises three elements: online planning with Monte Carlo Tree Search (MCTS), factored representations of local agent interactions with coordination graphs, and the iterative Max-Plus method for joint action selection. We evaluate our approach on the benchmark SysAdmin domain with static coordination graphs and achieve comparable performance with much lower computation cost than our MCTS baselines. We also introduce a multi-drone delivery domain with dynamic, i.e., state-dependent coordination graphs, and demonstrate how our approach scales to large problems on this domain that are intractable for other MCTS methods. We provide an open-source implementation of our algorithm at https://github.com/JuliaPOMDP/FactoredValueMCTS.jl.

AAMAS 2021

Scalable Anytime Planning for Multi-Agent MDPs

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 

technical paper

We advocate the development of a discipline of interacting with and extracting information from models, both mathematical (e.g. game-theoretic ones) and computational (e.g. agent-based models). We outline some directions for the development of a such a discipline: - the development of logical frameworks for the systematic formal specification of stylized facts and social mechanisms in (mathematical and computational) social science. Such frameworks would bring to attention new issues, such as <i>phase transitions</i>, i.e. dramatical changes in the validity of the stylized facts beyond some critical values in parameter space. We argue that such statements are useful for those logical frameworks describing properties of ABM. - the adaptation of tools from the theory of reactive systems (such as bisimulation) to obtain practically relevant notions of two systems "having the same behavior". - the systematic development of an adversarial theory of model perturbations, that investigates the robustness of conclusions derived from models of social behavior to variations in several features of the social dynamics. These may include: activation order, the underlying social network, individual agent behavior.

Models We Can Trust: Toward a Systematic Discipline of (Agent-Based) Model Interpretation and Validation (Blue Sky Ideas Track)

In recent work, Gourvès, Lesca, and Wilczynski propose a variant of the classic housing markets model where the matching between agents and objects evolves through Pareto-improving swaps between pairs of adjacent agents in a social network. To explore the swap dynamics of their model, they pose several basic questions concerning the set of reachable matchings. In their work and other follow-up works, these questions have been studied for various classes of graphs: stars, paths, generalized stars (i.e., trees where at most one vertex has degree greater than two), trees, and cliques. For generalized stars and trees, it remains open whether a Pareto-efficient reachable matching can be found in polynomial time.

Object Allocation Over a Network of Objects: Mobile Agents with Strict Preferences

We analyze portfolio compression, the netting of cycles in a financial network, as a strategic decision made by firms within a debt network. We define a network game in which firms have only local information and ask what criteria the firms should consider in their decision to compress. We propose a variety of heuristic strategies and evaluate them using agent-based simulation and empirical game-theoretic analysis. Our results show that some simple strategies based on local information perform better than the unconditional strategies of always agreeing or disagreeing to a compression and that when the decision is made strategically, the price of anarchy is always high.

A Strategic Analysis of Portfolio Compression

Social choice functions (SCFs) map the preferences of a group of agents over some set of alternatives to a non-empty subset of alternatives. The Gibbard-Satterthwaite theorem has shown that only extremely unattractive single-valued SCFs are strategyproof when there are more than two alternatives. For set-valued SCFs, or so-called social choice correspondences, the situation is less clear. There are miscellaneous--mostly negative--results using a variety of strategyproofness notions and additional requirements. The simple and intuitive notion of Kelly-strategyproofness has turned out to be particularly compelling because it is weak enough to still allow for positive results. For example, the Pareto rule is strategyproof even when preferences are weak, and a number of attractive SCFs (such as the top cycle, the uncovered set, and the essential set) are strategyproof for strict preferences. In this paper, we show that, for weak preferences, only indecisive SCFs can satisfy strategyproofness. In particular, (i) every strategyproof rank-based SCF violates Pareto-optimality, (ii) every strategyproof support-based SCF (which generalize Fishburn's C2 SCFs) that satisfies Pareto-optimality returns at least one most preferred alternative of every voter, and (iii) every strategyproof non-imposing SCF returns a Condorcet loser in at least one profile.

On the Indecisiveness of Kelly-Strategyproof Social Choice Functions

We present a model for the strategic selection of party nominees, where competing groups choose their representatives based on the expected electoral returns. Technically, we look at a generalisation of the Hotelling-Downs model, where each nominee has a predefined position on the political spectrum and attracts the closest voters compared to all other representatives. Within this framework we explore the algorithmic properties of Nash equilibria, which are not guaranteed to exist even in two party competitions. We show that finding a Nash equilibrium is NP-complete for the general case. However, if there are only two competing parties, this can be achieved in linear time. The results readily extend to games with restricted positioning options for the players involved, such as facility location and Voronoi games.

A Hotelling-Downs Framework for Party Nominees

Various voting rules are based on ranking the candidates by scores induced by aggregating voter preferences. A winner (respectively, unique winner) is a candidate who receives a score not smaller than (respectively, strictly greater than) the remaining candidates. Examples of such rules include the positional scoring rules and the Bucklin, Copeland, and Maximin rules. When voter preferences are known in an incomplete manner as partial orders, a candidate can be a possible/necessary winner based on the possibilities of completing the partial votes. Past research has studied in depth the computational problems of determining the possible and necessary winners and unique winners. These problems are all special cases of reasoning about the range of possible positions of a candidate under different tiebreakers. We investigate the complexity of determining this range, and particularly the extremal positions. Among our results, we establish that finding each of the minimal and maximal positions is NP-hard for each of the above rules, including all positional scoring rules, pure or not. Hence, none of the tractable variants of necessary/possible winner determination remain tractable for extremal position determination. Tractability can be retained when reasoning about the top- k  positions for a fixed  k . Yet, exceptional is Maximin where it is tractable to decide whether the maximal rank is  k  for $k=1$ (necessary winning) but it becomes intractable for all $k>1$.

Computing the Extremal Possible Ranks with Incomplete Preferences

This paper addresses modeling and simulating pedestrian trajectories when interacting with an autonomous vehicle in a shared space. Pedestrian motion models integrating pedestrians interactions with an autonomous vehicle already exist. However, they fail to accurately predict the individual trajectory of each pedestrian, and they do not deal with the diversity of possible pedestrian interactions with the vehicle in a shared space (front, back or lateral). Moreover, previous works do not sufficiently provide a quantitative evaluation of the model's predictions. In this paper, we propose an hybrid pedestrian model that combines the social force model and a new decision model for conflicting pedestrian-vehicle interactions. The proposed model integrates different observed pedestrians behaviors, as well as the behaviors of the social groups of pedestrians. We validate the model and evaluate its predictive potential through qualitative and quantitative comparisons with ground truth trajectories. The proposed model reproduces observed behaviors that have not been replicated by the social force model and outperforms the social force model at predicting pedestrians trajectories on the used dataset. This model will be used by an autonomous vehicle in a shared space to predict the trajectories of surrounding pedestrians.

An Agent-Based Model to Predict Pedestrians Trajectories with an Autonomous Vehicle in Shared Spaces

The real world is awash with multi-agent problems that require collective action by self-interested agents, from the routing of packets across a computer network to the management of irrigation systems. Such systems have local incentives for individuals, whose behavior has an impact on the global outcome for the group. Given appropriate mechanisms describing agent interaction, groups may achieve socially beneficial outcomes, even in the face of short-term selfish incentives. In many cases, collective action problems possess an underlying graph structure, whose topology crucially determines the relationship between local decisions and emergent global effects. Such scenarios have received great attention through the lens of network games. However, this abstraction typically collapses important dimensions, such as geometry and time, relevant to the design of mechanisms promoting cooperation. In parallel work, multi-agent deep reinforcement learning has shown great promise in modelling the emergence of self-organized cooperation in complex gridworld domains. Here we apply this paradigm in graph-structured collective action problems.

Modelling Cooperation in Network Games with Spatio-Temporal Complexity

Pay-per-last-$N$-shares'' (PPLNS) is one of the most common payout strategies used by mining pools in Proof-of-Work (PoW) cryptocurrencies such as Bitcoin.As with any payment scheme, it is imperative to study issues of incentive compatibility of miners within the pool. For PPLNS this question has only been partially answered; we know that reasonably-sized miners within a PPLNS pool prefer following the pool protocol over employing {\em specific} deviations. In this paper, we present a novel modification to PPLNS where we randomise the protocol in a natural way. We call our protocol ''Randomised pay-per-last-$N$-shares'' (RPPLNS), and note that the randomised structure of the protocol greatly simplifies the study of its incentive compatibility. We show that RPPLNS maintains the strengths of PPLNS (i.e., fairness, variance reduction, and resistance to pool hopping), while also being robust against a richer class of strategic mining than what has been shown for PPLNS.

RPPLNS: Pay-per-last-N-shares with a Randomised Twist

Most frameworks for computing solution concepts in hedonic games are theoretical in nature, and require complete knowledge of all agent preferences, an impractical assumption in real-world settings. This paper presents the first application of strategic hedonic game models on real-world data. We show that PAC stable solutions can reflect Members of Knesset' political positions and reveal politicians who are known to deviate from party lines. Moreover, these models compare favorably to machine learning models.

Scalable Anytime Planning for Multi-Agent MDPs

Downloads

Next from AAMAS 2021

Models We Can Trust: Toward a Systematic Discipline of (Agent-Based) Model Interpretation and Validation (Blue Sky Ideas Track)

Similar lecture

Temporal Watermarks for Deep Reinforcement Learning Models

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Scalable Anytime Planning for Multi-Agent MDPs

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

Models We Can Trust: Toward a Systematic Discipline of (Agent-Based) Model Interpretation and Validation (Blue Sky Ideas Track)

Similar lecture

Temporal Watermarks for Deep Reinforcement Learning Models

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads