United Kingdom

Tournaments are commonly used to identify winners, for example in sports. We study the computational complexity of problems related to scheduling the matches in a tournament and predicting the outcome with a special focus on round-robin tournaments, which is the most prominent tournament type used in sports. Besides the general financial and intrinsically motivated interest of various agents in tournament prediction, the recently very relevant winner determination for suddenly discontinued tournaments is a strong motivation. We show the immense theoretical complexity of predicting the winners in round-robin tournaments even under the assumption that only three matchdays remain to be played. On the other hand, we present an FPT algorithm and analyze its practical complexity using experiments on real-world and generated data, showing the applicability of the algorithm in praxis. To the best of our knowledge, this is the first exact and not purely brute-force oriented approach for predicting round-robin tournaments.

AAMAS 2021

Complexity of Scheduling and Predicting Round-Robin Tournaments

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 present an extension of the organizational model and infrastructure adopted in JaCaMo, that explicitly encompasses the notion of exception. We propose an exception handling mechanism for organization management in multi-agent systems. This mechanism relies on abstractions that are seamlessly integrated with organizational concepts, such as responsibilities, goals and norms.

Distributing Responsibilities for Exception Handling in JaCaMo

We present Strategy RV, a tool that allows to approximate the verification of Alternating-time Temporal Logic under imperfect information and perfect recall, which is known to be undecidable, by using Runtime Verification. The tool uses an interface to enter the game model and the specifications and to provide results. We test Strategy RV in a variant of the Curiosity rover scenario and provide some experimental results.

Strategy RV: A Tool to Approximate ATL Model Checking under Imperfect Information and Perfect Recall

Value alignment is a crucial aspect of ethical multiagent systems. An important step toward value alignment is identifying values specific to an application context. However, identifying context-specific values is complex and cognitively demanding. To support this process, we develop a methodology and a collaborative web platform that employs AI techniques. We describe this platform, highlighting its intuitive design and implementation.

A Collaborative Platform for Identifying Context-Specific Values

Agents operating in the open world often produce negative side effects (NSE), which are difficult to identify at design time. We examine how a human can assist an agent, beyond providing feedback, and exploit their broader scope of knowledge to mitigate the impacts of NSE. We formulate this problem as a human-agent team with decoupled objectives. The agent optimizes its assigned task, during which its actions may produce NSE. The human shapes the environment through minor reconfiguration actions so as to mitigate the impacts of agent's side effects, without significantly degrading agent performance. We present an algorithm to solve this problem. Empirical evaluation shows that the proposed framework can successfully mitigate NSE, without affecting the agent's ability to complete its assigned task.

Mitigating Negative Side Effects via Environment Shaping

Multi-agent crowd simulation is generally used to construct an environment suitable for reality by parameter estimation. This estimation is to modify a model defined by human movements and behaviors to fit real-world data by means of statistics or optimization [2, 11]. In the field of traffic engineering, for example, parameter estimation is used to modify speed models and collision models of pedestrians and vehicles [10, 13]. For different simulation settings, it is not easy to obtain original data of each real-world environment. Few existing estimation methods have been fairly evaluated. Therefore, there is a need for a benchmark to discuss the applicability of certain estimation methods to other use cases.

MAS-Bench: Parameter Optimization Benchmark for Multi-agent Crowd Simulation

This is a short version of ''Logic-based specification and verification of homogeneous dynamic multi-agent systems'' in Autonomous Agents and Multi-Agent Systems 34, 2 (2020), where we developed a logic-based framework for formal specification and algorithmic verification of homogeneous and dynamic concurrent multi-agent transition systems (HDMAS). Homogeneity means that all agents have the same available actions at any given state and the actions have the same effects regardless of which agents perform them. Dynamicity means that the numbers of controllable and uncontrollable agents may vary throughout the system evolution, possibly at every transition. As a specification language, we extended Alternating-time Temporal Logic to express properties such as: "a coalition of (at least) n controllable agents can ensure against (at most) m uncontrollable agents that any possible evolution of the system satisfies a given objective &#947;", where &#947; is specified again as a formula of that language and each of n and m is either a fixed number or a variable that can be quantified over. Finally, we show the algorithm and worst-case complexity for the model checking problem.

Logic-based Specification and Verification of Homogeneous Dynamic Multi-agent Systems (JAAMAS Track)

Public announcement logic (PAL) extends multi-agent epistemic logic with dynamic operators modelling the effects of public communication. Allowing quantification over public announcements lets us reason about the existence of an announcement to reach a certain epistemic goal. Two notable examples of logics of quantified announcements are arbitrary public announcement logic (APAL) and group announcement logic (GAL). The notion of common knowledge plays an important role in PAL, and in particular in characterisations of epistemic states that an agent or a group of agents might make come about by performing public announcements. In this paper, we study extensions of APAL and GAL with common knowledge, which has not been done before. We consider both conservative extensions where the semantics of the quantifiers is not changed, as well as extensions where the scope of quantification also includes common knowledge formulas. We compare the expressivity of these extensions relative to each other and other connected logics, and provide sound and complete axiomatisations.

Quantified Announcements and Common Knowledge

We present a logic of evaluation which clarifies the relationship between knowledge, values and preferences of multiple agents in an interactive setting. Evaluation is a fundamental concept for understanding how an ethical agent's decision is affected by her values. We provide a complete axiomatics for the logic and present a dynamic extension by the concept of value expansion. We show that value expansion indirectly affects the agents' preferences by inducing a preference upgrade operation.

A Logic of Evaluation

We investigate whether Jacobi preconditioning, accounting for the bootstrap term in temporal difference (TD) learning, can help boost performance of adaptive optimizers. Our method, TDprop, computes a per-parameter learning rate based on the diagonal preconditioning of the TD update rule. We show how this can be used in both n-step returns and TD(?). Our theoretical findings demonstrate that including this additional preconditioning information is comparable to normal semi-gradient TD if the optimal learning rate is found for both via a hyperparameter search. This matches our experimental results. In Deep RL experiments using Expected SARSA, TDprop meets or exceeds the performance of Adam in all tested games under near-optimal learning rates, but a well-tuned SGD can yield similar performance in most settings. Our findings suggest that Jacobi preconditioning may improve upon Adam in Deep RL, but despite incorporating additional information from the TD bootstrap term, may not always be better than SGD. Moreover, they suggest that more theoretical investigations are needed to understand adaptive optimizers under optimal hyperparameter regimes in TD learning: simpler methods may, surprisingly, be theoretically comparable after a hyperparameter search.

TDprop: Does Adaptive Optimization With Jacobi Preconditioning Help Temporal Difference Learning?

Multi-player mean-payoff games are a natural formalism to model concurrent and multi-agent systems with self-interested players. Players in such a game traverse a graph, while trying to maximise a mean-payoff function that depends on the plays so generated. As with all games, the equilibria that could arise may have undesirable properties. However, as system designers, we typically wish to ensure that equilibria in such systems correspond to desirable system behaviours, for example, satisfying certain safety or liveness properties. One natural way to do this would be to specify such desirable properties using temporal logic. Unfortunately, the use of temporal logic specifications causes game theoretic verification problems to have very high computational complexity. To this end, we consider ømega-regular specifications, which offer a concise and intuitive way of specifying desirable behaviours of a system. The main results of this work are characterisation and complexity bounds for the problem of determining if there are equilibria that satisfy a given ømega-regular specification in a multi-player mean-payoff game in a number of computationally relevant game-theoretic settings.

Complexity of Scheduling and Predicting Round-Robin Tournaments

Downloads

Next from AAMAS 2021

Distributing Responsibilities for Exception Handling in JaCaMo

Similar lecture

Temporal Watermarks for Deep Reinforcement Learning Models

Complexity of Scheduling and 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 2021

Distributing Responsibilities for Exception Handling in JaCaMo

Similar lecture

Temporal Watermarks for Deep Reinforcement Learning Models

Downloads