New Zealand


Round-robin tournaments are, besides single-elimination tournaments, by far the most prominent and widely used tournament format in sports and other competitions. We study the average-case complexity of two problems related to the prediction of roundrobin tournaments, namely first the problem of calculating the championship probability of a team and second the well-known sports elimination problem where one has to decide whether a team still has the possibility to become champion. We show that, under certain assumptions, these problems are solvable in expected polynomial time for a distribution which, for the algorithm used, seems to dominate the distribution of real instances in terms of complexity, despite their computational worst-case hardness.

AAMAS 2022

On the Average-Case Complexity of Predicting Round-Robin Tournaments

probabilistic tournaments

predicting

round-robin tournaments

average-case complexity

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

poster


Gale and Shapley introduced a matching problem between two sets of agents where each agent on one side has an exogenous preference ordering over the agents on the other side. They defined a matching as stable if no unmatched pair can both improve their utility by forming a new pair. They proved, algorithmically, the existence of a stable matching. Shapley and Shubik, Demange and Gale, and many others extended the model by allowing monetary transfers. We offer a further extension by assuming that matched couples obtain their payoff endogenously as the outcome of a strategic game they have to play in a usual non-cooperative sense (without commitment) or in a semi-cooperative way (with commitment, as the outcome of a bilateral binding contract in which each player is responsible for his/her part of the contract). Depending on whether the players can commit or not, we define in each case a solution concept that combines Gale-Shapley pairwise stability with a (generalized) Nash equilibrium stability. In each case, we give the necessary and sufficient conditions for the set of stable allocations to be non-empty, we study its lattice structure, and provide an algorithm that converges to its maximal element. Finally, we prove that our second model -with commitment- encompasses and refines most of the literature.

Stable Matching Games


In settings without well-defined goals, methods for reward learning
allow reinforcement learning agents to infer goals from human
feedback. Existing work has discussed the problem that such agents
may manipulate humans, or the reward learning process, in order
to gain higher reward. We introduce the neglected problem that, in
multi-agent settings, agents may have incentives to manipulate one
another’s reward functions in order to change each other’s behav-
ioral policies. We focus on the setting with humans acting alongside
assistive (artificial) agents who must learn the reward function by
interacting with these humans. We propose a possible solution to
manipulation of human feedback in this setting: the Shared Value
Prior (SVP). The SVP equips agents with an assumption that the
reward functions of all humans are similar. Given this assumption,
the actions of any human provide information to an agent about
its reward, and so the agent is incentivised to observe these actions
rather than to manipulate them. We present an expository example
in which the SVP prevents manipulation.

On Agent Incentives to Manipulate Human Feedback in Multi-Agent Reward Learning Scenarios


In this work we propose a concept for the real-world implementation of traffic light (TL) optimization by reinforcement learning (RL). This is achieved by combining RL with state-of-the-art traffic theory and real-world control and perception methods.

Reinforcement Learning for Traffic Signal Control Optimization: A Concept for Real-World Implementation


We propose a new self-reconfiguration method based on organizing modules in meta-modules that form a 3D porous structure allowing modules to flow in parallel inside of it without blocking. We first propose a new meta-module model which can be used to fill in its internal volume an additional number of modules and describe the structure that can be built with our meta-modules which allow it to be compressible and expandable. We then show how to self-reconfigure the structure from an initial shape to a given goal shape.

A New Porous Structure for Modular Robots


Recently reinforcement learning (RL) has been applied as a successful strategy for the anti-adversary paradigm for providing reliable communication in wireless communication networks. However, studying the RL-based approaches from the adversary’s perspective, either for active defense or for designing defense mechanisms, has received little attention. Additionally, RL-based approaches in an anti-adversary or adversary paradigm mostly consider single-channel communication (either channel selection or single channel power control), while multi-channel communication is more common in practice. In this paper, we propose a multi-agent adversary system (MAAS) for modeling and analyzing adversaries in a wireless communication scenario by careful design of the reward function under realistic communication scenarios. In particular, by modeling the adversaries as learning agents, we show that the proposed MAAS is able to successfully choose the transmitted channel(s) together with the allocated power(s) without any prior knowledge of the sender strategy. Compared to the single-agent adversary (SAA), multi-agents in MAAS can achieve significant reduction of signal-to-noise ratio (SINR) under the same power constraints and partial observability while providing additional stability and a more efficient learning process.

Multi-Agent Adversarial Attacks for Multi-Channel Communications


We investigate the mean dynamics of the soft-max policy gradient algorithm in multi-agent normal-form games by resorting to evolutionary game theory and dynamical system tools. First, we consider the best-response problem analysis, where a single learner plays against a fixed opponent in continuous time.
For such dynamics, we provide a complete characterization of the set of bad initializations (points for which the dynamics initially move towards sub-optimal strategies). Then, we resort to models based on single- and multi-population games, showing that the dynamics preserve the volume and, in arbitrary instances, it is impossible to obtain last-iterate convergence when the equilibrium of the game is fully mixed. Furthermore, we give empirical evidence that dynamics starting from close initial points may expand over time, thus showing that the behavior of the dynamics in games with fully-mixed equilibrium is chaotic.

The Evolutionary Dynamics of Soft-Max Policy Gradient in Multi-Agent Settings


We introduce MA-Trace - a simple, scalable and effective multi-agent reinforcement learning algorithm with theoretical guarantees.

Off-Policy Correction For Multi-Agent Reinforcement Learning


Learning effective policies for real-world problems is still an open challenge for the field of reinforcement learning (RL). The main limitation being the amount of data needed and the pace at which that data can be obtained. In this paper, we study how to build lightweight simulators of complicated systems that can run sufficiently
fast for deep RL to be applicable. We focus on domains where agents interact with a reduced portion of a larger environment while still being affected by the global dynamics. Our method combines the use of local simulators with learned models that mimic the influence of the global system. The experiments reveal that incorporating this idea into the deep RL workflow can considerably accelerate the training process and presents several opportunities for the future.

Speeding up Deep Reinforcement Learning through Influence-Augmented Local Simulators

**Read paper on the following link:**

https://ifaamas.org/Proceedings/aamas2022/pdfs/p1613.pdf

**Abstract:**



Proof-of-Work as a Stigmergic Consensus Algorithm


We propose the notion of deep reinforcement learning-based strategy templates for multi-issue bilateral negotiation. Each strategy template consists of a set of interpretable parameterized tactics that are used to decide an optimal action at any time. This contrasts with existing work that only estimates the threshold utility for those tactics that require it. As a result, we build automated agents for multi-issue negotiations that can adapt to different negotiation domains without the need to be pre-programmed.

On the Average-Case Complexity of Predicting Round-Robin Tournaments

Downloads

Next from AAMAS 2022

Stable Matching Games

Similar lecture

Intelligent Communication over Realistic Wireless Networks in Multi-Agent Cooperative Games

On the Average-Case Complexity of 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 2022

Stable Matching Games

Similar lecture

Intelligent Communication over Realistic Wireless Networks in Multi-Agent Cooperative Games

Downloads