New Zealand


This paper presents a path-following combinatorial framework based on systems of polynomial equations to compute mixed Nash equilibria in $N$-person games.
We provide the first detailed implementable description of Wilson&#39;s path-following method, which extends Lemke-Howson&#39;s algorithm to N-persons games and handles degenerate games as well.
Our approach resembles, in some respects, support enumeration methods.
We thus compare both approaches, theoretically and experimentally.
Then, we show that the path-following approach allows to deal with a large family of succinctly expressed games: hypergraphical games, graphical games and polymatrix games.
The described algorithms have been implemented in Python, making use of Sagemath libraries to solve systems of polynomial equations, allowing an experimental comparison of the different combinatorial approaches on a large variety of games.

AAMAS 2022

A path-following polynomial equations systems approach for computing Nash equilibria

path following algorithm

nash equilibrium

game theory

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


This paper presents a path-following combinatorial framework based on systems of polynomial equations to compute mixed Nash equilibria in $N$-person games.
We provide the first detailed implementable description of Wilson's path-following method, which extends Lemke-Howson's algorithm to N-persons games and handles degenerate games as well.
Our approach resembles, in some respects, support enumeration methods.
We thus compare both approaches, theoretically and experimentally.
Then, we show that the path-following approach allows to deal with a large family of succinctly expressed games: hypergraphical games, graphical games and polymatrix games.
The described algorithms have been implemented in Python, making use of Sagemath libraries to solve systems of polynomial equations, allowing an experimental comparison of the different combinatorial approaches on a large variety of games.

technical paper


Nash equilibrium is a central concept in game theory. Several Nash solvers exist, yet none scale to normal-form games with many actions and many players, especially those with payoff tensors too big to be stored in memory. In this work, we propose an approach that iteratively improves an approximation to a Nash equilibrium through joint play. It accomplishes this by tracing a previously established homotopy that defines a continuum of equilibria for the game regularized with decaying levels of entropy. This continuum asymptotically approaches the \emph{limiting logit equilibrium}, proven by McKelvey and Palfrey (1995) to be unique in \emph{almost} all games, thereby partially circumventing the well-known equilibrium selection problem of many-player games. To encourage iterates to remain near this path, we efficiently minimize \emph{average deviation incentive} via stochastic gradient descent, intelligently sampling entries in the payoff tensor as needed. Monte Carlo estimates of the stochastic gradient from joint play are biased due to the appearance of a nonlinear max operator in the objective, so we introduce additional innovations to the algorithm to alleviate gradient bias. The descent process can also be viewed as repeatedly constructing and reacting to a polymatrix approximation to the game. In these ways, our proposed approach, \emph{average deviation incentive descent with adaptive sampling} (ADIDAS), is most similar to three classical approaches, namely homotopy-type, Lyapunov, and iterative polymatrix solvers. The lack of local convergence guarantees for biased gradient descent prevents guaranteed convergence to Nash, however, we demonstrate through extensive experiments the ability of this approach to approximate a unique Nash equilibrium in normal-form games with as many as seven players and twenty one actions (several billion outcomes) that are orders of magnitude larger than those possible with prior algorithms.

Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent


The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme for a one-sided matching market -- called ADHZ in this paper -- has natural applications but has instances which do not admit equilibria. By introducing approximation, we define the \epsilon-approximate ADHZ model, and we give the following results.

1. Existence of equilibrium under linear utility functions. We prove that the equilibrium satisfies Pareto optimality, approximate envy-freeness, and approximate weak core stability.

2. A combinatorial polynomial-time algorithm for an \epsilon-approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities.

3. An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium.

4. A rational convex program for HZ under dichotomous utilities; a combinatorial polynomial-time algorithm for this case was given in \cite{VY20}.

The \epsilon-approximate ADHZ model fills a void in the space of general mechanisms for one-sided matching markets; see details in the paper.

One-Sided Matching Markets with Endowments: Equilibria and Algorithms


The behavior of no-regret learning algorithms is well understood in two-player min-max (i.e, zero-sum) games. In this paper, we investigate the behavior of no-regret learning in min-max games with dependent strategy sets, where the strategy of the first player constrains the behavior of the second. Such games are best understood as sequential, i.e., min-max Stackelberg, games. We consider two settings, one in which only the first player chooses their actions using a no-regret algorithm while the second player best responds, and one in which both players use no-regret algorithms. For the former case, we show that no-regret dynamics converge to a Stackelberg equilibrium. For the latter case, we introduce a new type of regret, which we call Lagrangian regret, and show that if both players minimize their Lagrangian regret, then play converges to a Stackelberg equilibrium. We then observe that online mirror descent (OMD) dynamics in these two settings correspond respectively to a known nested (i.e., sequential) gradient descent-ascent (GDA) algorithm and a new simultaneous GDA-like algorithm, thereby establishing convergence of these algorithms to Stackelberg equilibrium. Finally, we analyze the robustness of OMD dynamics to perturbations by investigating dynamic min-max Stackelberg games. We prove that OMD dynamics are robust for a large class of dynamic min-max games (with independent strategy sets). In the dependent case, we demonstrate the robustness of OMD dynamics experimentally by simulating them in dynamic Fisher markets, a canonical example of a min-max Stackelberg game (with dependent strategy sets).

Robust No-Regret Learning in Min-Max Stackelberg Games


This paper presents an extension to the Jason BDI language to allow qualitative reasoning under uncertainty. We demonstrate the need for such an extension using a challenge from the 2019 Multi-Agent Programming Contest (MAPC), namely localization for navigation. Given the ability to qualitatively reason about what the agent knows and what it considers possible (or impossible), these challenges become easier to express, reason about, and act upon in a Jason program.

Through the use of epistemic logic and the epistemic reasoner in Hintikka's World, our extension allows agents to express epistemic queries; specifically, utilizing the class of single-agent S5 epistemic models to model-check queries about the agent's uncertainty. This paper also provides an evaluation of the overall performance and scalability of the extension's implementation to show how it impacts the agent's reasoning time; from the evaluation results, we use the official 2019 MAPC time constraints to examine the performance tradeoffs of using the presented extension to model and reason about uncertainty.

Epistemic Reasoning in Jason


We present two logics of collective belief with a semantics exploiting the notion of belief base. The semantics distinguishes explicit from implicit belief: an agent's belief of explicit type is a piece of information contained in the agent's belief base, while a belief of implicit type corresponds to a piece of information that is derivable from the agent's belief base. The first part of the paper is devoted to the logic of implicit common belief, while the second presents the logic of explicit common belief. Implicit common belief is defined as a mutual belief of any order. This leads to the usual fixpoint construction of common belief. Explicit common belief is the collective counterpart of explicit individual belief and has a public nature. It moreover implies implicit common belief. We study axiomatic aspects of our logics as well as complexity of satisfiability checking. We show that, while the satisfiability checking problem is EXPTIME-hard for the logic of implicit common belief, it is in PSPACE for the logic of explicit common belief. This makes the latter logic a natural candidate for reasoning about collective attitudes of agents in multi-agent scenarios and applications. We also study a dynamic extension of the logic of explicit common belief in which private and public forms of information dynamics can be modeled.

Logical Theories of Collective Attitudes and the Belief Base Perspective


Computational agents based on the BDI framework typically rely on abstract plans and plan refinement to reach a degree of autonomy in dynamic environments: agents are provided with the ability to select how-to achieve their goals by choosing from a set of options. In this work we focus on a related, yet under-studied feature: abstract goals. These constructs refer to the ability of agents to adopt goals that are not fully grounded at the moment of invocation, refining them only when and where needed: the ability to select what-to (concretely) achieve at run-time. We present a reference-based approach to goal refinement, defining preferences based on extended Ceteris Paribus Networks (CP-Nets) for an AgentSpeak(L)-like agent programming language, and utilizing the established CP-Nets logic and algorithms to guide the goal refinement step. As a technical contribution, we present an implementation of this method that solely uses a Prolog-like inference engine of the agent's belief-base to reason about preferences, thus minimally affecting the decision-making mechanisms hard-coded in the agent framework.

Preference-Based Goal Refinement in BDI Agents


The original BOID is a cognitive architecture that unifies Belief, Obligation, Intention and Desire rules to calculate which actions should an agent undertake next. In the current paper, we adapt the original BOID with an aim to model autonomous agency. The new BOID* architecture is able to capture anticipation that we believe to be one of the hallmarks of autonomous agency. We focus on developing algorithms for anticipatory reasoning through a new BOID* goal deliberation component. The key method that BOID* introduces is abductive reasoning as a way to represent motivational attitudes, such as desires and obligations. As a result of deliberation via abduction, BOID* specifies intention revision procedures that connect motivational and informational attitudes. The BOID* is a part of the project to build autonomous AI models that make explicit the reasoning behind adopting future goals, prioritizing selected goals and forming intentions.

BOID*: Autonomous goal deliberation through abduction


This paper presents a new multi-agent model for simulating malware
propagation in device-to-device (D2D) 5G networks. This model
allows to understand and analyze mobile malware spreading dynamics in such highly dynamical networks. Additionally, we present a
theoretical study to validate and benchmark our proposed approach
for some basic scenarios that are less complicated to model mathematically and also to highlight the key parameters of the model. Our
simulations identifying critical thresholds for "no propagation" and
for "maximum malware propagation" and make predictions on the
malware spread velocity as well as device infection rates. To the best
of our knowledge, this paper is the first study applying agent-based
simulations for malware propagation in D2D.

Agent-based modeling and simulation for malware spreading in D2D networks


Agents have been used for simulating cultural evolution and cultural evolution can be used as a model for artificial agents. Previous results have shown that horizontal, or intra-generation, knowledge transmission allows agents to improve the quality of their knowledge to a certain level. Moreover, variation generated through vertical, or inter-generation, transmission allows agents to exceed that level. Such results have been obtained under specific conditions such as the drastic selection of agents allowed to transmit their knowledge, seeding the process with correct knowledge or introducing artificial noise during transmission. Here, we question the necessity of such measures and study their impact on the quality of transmitted knowledge. For that purpose, we combine the settings of two previous experiments and we relax these assumptions (no strong selection of teachers, no fully correct seed, no introduction of artificial noise). The rationale is that if interactions lead agents to improve their overall knowledge quality, this should be sufficient to ensure correct knowledge transmission, and that transmission mechanisms are sufficiently imperfect to produce variation. In this setting, we confirm that vertical transmission improves on horizontal transmission even without drastic selection and oriented learning. We also show that horizontal transmission is able to compensate for the lack of parent selection if it is maintained for long enough. This shows that it is not necessary to take the most successful agents as teachers, neither in vertical nor horizontal transmission, to cumulatively improve knowledge.

Knowledge Transmission and Improvement Across Generations do not Need Strong Selection


Ants have evolved to seek and retrieve food by leaving trails of pheromones. This mechanism has inspired several approaches to decentralized multi-robot coordination. However, in this paper, we show that pheromone trails are a fragile mechanism for coordination, and can be sabotaged to starve the colony. We introduce detractors: malicious agents that leave a misleading, but indistinguishable, trail of food pheromone to distract and trap cooperator ants in the nest. We analyze the effectiveness of detractors with respect to parameters such as evaporation rate of misleading pheromone and fraction of detractors in the colony. In addition, we propose a countermeasure to this attack by introducing a new type of pheromone: the cautionary pheromone. Cooperator ants secrete this type of pheromone atop existing food trails as a warning. When the cautionary pheromone intensity exceeds the food pheromone intensity, cooperator ants ignore overlapping food pheromone. We show that, despite its simplicity, this defense mechanism can limit, but not nullify, the effect of detractors. Ultimately, our work shows that pheromone-based coordination, while effective, is also fragile.

A path-following polynomial equations systems approach for computing Nash equilibria

Downloads

Next from AAMAS 2022

Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent

Similar lecture

Learning Equilibria in Mean-Field Games: Introducing Mean-Field PSRO

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

A path-following polynomial equations systems approach for computing Nash equilibria

.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

Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent

Similar lecture

Learning Equilibria in Mean-Field Games: Introducing Mean-Field PSRO

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads