Multi-Agent Algorithms for Solving Graphical Games

AAAI Conferences

Consider the problem of a group of agents trying to find a stable strategy profile for a joint interaction. A standard approach is to describe the situation as a single multi-player game and find an equilibrium strategy profile of that game. However, most algorithms for finding equilibria are computationally expensive; they are also centralized, requiring that all relevant payoff information be available to a single agent (or computer) who must determine the entire equilibrium profile. In this paper, we exploit two ideas to address these problems. We consider structured game representations, where the interaction between the agents is sparse, an assumption that holds in many real-world situations.


AAAI Conferences

Department of Economics University of Bristol 8 Woodland Road Bristol BS8 1TNFEngland Abstract This paper analyzes automated distributive negotiation where agents have firm deadlines that are private information. The agents are allowed to make and accept offers in any order in continuous time. We show that the only sequential equilibrium outcome is one where the agents walt until the first deadline, at which point that agent concedes everything to the other. This holds for pure and mixed strategies. So, interestingly, rational agents can never agree to a nontrivial split because offers signal enough weakness of bargaining power (early deadline) so that the recipient should never accept. Similarly, the offerer knows that it offered too much if the offer gets accepted: the offerer could have done better by out-waiting the opponent. In most cases, the deadline effect completely overrides time discounting and risk aversion: an agent's payoff does not change with its discount factor or risk attitude. Several implications for the design of negotiating agents are discussed. We also present an effective protocol that implements the equilibrium outcome in dominant strategies. 1 Introduction Multiagent systems for automated negotiation between self-interested agents are becoming increasingly important due to both technology push and application pull. The competitive pressure on the side with many agents often reduces undesirable strategic effects. On the other handFmarket mechanisms often have difficulty in "scaling down" to small numbers of agents (Osborne & Rubinstein 1990). In the limit of one-to-one negotiationFstrategic considerations become prevalent.

Optimal Efficient Learning Equilibrium: Imperfect Monitoring in Symmetric Games

AAAI Conferences

Efficient Learning Equilibrium (ELE) is a natural solution concept for multi-agent encounters with incomplete information. It requires the learning algorithms themselves to be in equilibrium for any game selected from a set of (initially unknown) games. In an optimal ELE, the learning algorithms would efficiently obtain the surplus the agents would obtain in an optimal Nash equilibrium of the initially unknown game which is played. The crucial part is that in an ELE deviations from the learning algorithms would become non-beneficial after polynomial time, although the game played is initially unknown. While appealing conceptually, the main challenge for establishing learning algorithms based on this concept is to isolate general classes of games where an ELE exists. Unfortunately, it has been shown that while an ELE exists for the setting in which each agent can observe all other agents' actions and payoffs, an ELE does not exist in general when the other agents' payoffs cannot be observed. In this paper we provide the first positive results on this problem, constructively proving the existence of an optimal ELE for the class of symmetric games where an agent can not observe other agents' payoffs.

Verifiable Equilibria in Boolean Games

AAAI Conferences

This work is motivated by the following concern. Suppose we have a game exhibiting multiple Nash equilibria, with little to distinguish them except that one of them can be verified while the others cannot. That is, one of these equilibria carries sufficient information that, if this is the outcome, then the players can tell that an equilibrium has been played. This provides an argument for this equilibrium being played, instead of the alternatives. Verifiability can thus serve to make an equilibrium a focal point in the game. We formalise and investigate this concept using a model of Boolean games with incomplete information. We define and investigate three increasingly strong types of verifiable equilibria, characterise the complexity of checking these, and show how checking their existence can be captured in a variant of modal epistemic logic.

Successful Nash Equilibrium Agent for a 3-Player Imperfect-Information Game Artificial Intelligence

Creating strong agents for games with more than two players is a major open problem in AI. Common approaches are based on approximating game-theoretic solution concepts such as Nash equilibrium, which have strong theoretical guarantees in two-player zero-sum games, but no guarantees in non-zero-sum games or in games with more than two players. We describe an agent that is able to defeat a variety of realistic opponents using an exact Nash equilibrium strategy in a 3-player imperfect-information game. This shows that, despite a lack of theoretical guarantees, agents based on Nash equilibrium strategies can be successful in multiplayer games after all.