Representing pure Nash equilibria in argumentation

1.Introduction

Game theory studies how multiple rational decision-makers should act given interactions between their strategies, and preferences over the resultant outcomes. Game theory has been applied to myriad fields [9]. Within game theory, decision-makers (referred to as players), their strategies, preferences and outcomes are represented within a game, and the solutions to a game identify some form of rational outcome. One such solution concept is that of a dominant strategy, where a player has a strategy or a set of strategies that will always result in the best outcome for them, regardless of what other players do. However, such dominant strategies often do not exist. In this work, we consider instead the notion of a Nash equilibrium, which identifies optimal strategies given that other players also pursue their own optimal strategies. Such Nash equilibria therefore represent a form of best response, and provide a well understood solution concept in game theory. However, finding Nash equilibria is computationally difficult, and it is sometimes difficult for a non-expert to understand why a given strategy is (or is not) a Nash equilibrium. We believe that by providing an argumentation-based representation of games, dialogues can be used to explain a Nash equilibrium to such non-experts. While work such as [7] has considered game theory in the context of ABA, to our knowledge, this work is the first to link abstract argumentation and Nash equilibria. We consider only so-called pure strategies for normal form games and intend to relax this restriction in future work.

The remainder of the paper is structured as follows. In Section 2, we provide a brief overview of argumentation and game-theory concepts necessary to understand our article. In Section 3, we describe how a normal form game can be encoded using argumentation. Section 4 examines some formal properties of our approach. Section 5 shows how we can build upon the proposed framework to provide explanations to a user about whether a strategy profile is a Nash equilibrium or not. Lastly, we discuss related and future work in Section 6 before concluding.

2.Background

We begin by providing the necessary background in game theory and argumentation required for the rest of the paper.

2.1.Game theory

In this paper, we use the usual normal form for games [16].

Definition 1

Definition 1(Normal game).

A (normal) game is G=(Ag,Ac,Av,Ou,Ef,⩽) where Ag={0,1,…,n} is a finite set of players; Ac is a finite set of strategies; Av=[Ac0,…,Acn] with Aci⊆Ac denoting the strategies available to i; Ou={o0,…,om} is a set of possible outcomes; Ef:Acn→Oun captures the consequences of the joint strategies for each player; and ⩽=[⩽0,…,⩽n] with ⩽i⊆Ou×Ou denoting the preference relation for player i.

The notation ok⩽iol means that player i prefers outcome ol to ok. As commonly done, we write oi<ioj iff oi⩽ioj and oj≰ioi.11 Likewise, we will use the notation oi⩾ioj iff oi≮ioj and oi>ioj iff oi≰ioj. A pure strategy profile S is a tuple containing one strategy from each player in the game. The set of all such pure strategy profiles is SG=∏i∈AgAci, and represents one joint strategy of all players. A partial strategy profile is a tuple containing a single strategy for a subset of the players. Given any pure strategy profile S=[s0,…,sn], we write S−i to denote the partial strategy profile [s0,…,si−1,∅,si+1,…,sn], where the strategy for player i is not specified. We then write S−i⊕si to denote strategy profile S. With a slight abuse of notation, for any S,S′∈SG we write that S⩽iS′ iff Ef(S)i⩽iEf(S′)i.22

Table 1

Two games in normal form

Example 1.

Let us consider the stag hunt game G=({0,1},Ac,Av,Ou,Ef,⩽), where Ac={stag,hare}, Av=[Ac,Ac], Ou={4,3,2,1}, ⩽ is the standard less than relation over numbers. Table 1a graphically illustrates this game in normal form, and specifies Ef. For example, the tuple (1,3) in the column “hare” and row “stag” means that Ef([stag,hare])=(1,3). Given the pure strategy profile S=[stag,hare], S−0=[∅,hare] and S−0⊕hare=[hare,hare]. Here [stag,hare]⩽0[hare,hare] because (1,3)0⩽0(2,2)0 but [hare,hare]⩽1[stag,hare].

In asking why a player should pursue some strategy, we must take into account the strategies of others.

If each player has chosen a strategy, and no player can increase their own outcome by changing their strategy while the other players keep theirs unchanged, then the current pure strategy profile constitutes a Nash equilibrium.

Definition 2.

Let G=(Ag,Ac,Av,Ou,Ef,⩽), we say that S∈SG is a Nash equilibrium if for every i∈Ag and for any strategy s∈Aci, it holds that S−i⊕s⩽iS.

A simple algorithm to identify all Nash equilibrium in the presence of pure strategies involves iterating through every player and identifying the best strategy profile (in terms of Ef for that player) given all other players’ possible joint strategies. Any strategy profile which all players consider best is then a Nash equilibrium.

Given a game in normal form, the above algorithm involves – for a two player game – scanning down each column and marking the best strategy for the row player, and then doing the same for each row marking the best strategy for the column player. Each cell marked for both players is a Nash equilibrium. In the remainder of this paper, we show an argumentation-based alternative.

Example 2

Example 2(Cont’d).

There are two Nash equilibria in the stag hunt game: [stag,stag] and [hare,hare]. The strategy profile [stag,stag] is a Nash equilibrium because [hare,stag]⩽0[stag,stag] and [stag,hare]⩽1[stag,stag]. Similarly, [hare,hare] is also a Nash equilibrium as [stag,hare]⩽0[hare,hare] and [hare,stag]⩽1[hare,hare].

3.Argumentation-based approach for games

We consider an argumentation framework with multi-level arguments. At the base level, we consider all possible strategy profiles as arguments. Since only a single strategy profile can ever occur (as players execute one set of strategies in the interaction), every argument at this level must attack every other argument. We refer to such arguments as game-based arguments, and note that they are equivalent to pure strategy profiles.

The set of all game-based arguments for a game G is denoted by Ag(G).

Next, we introduce preference arguments. Intuitively, these can be interpreted as statements of the form: “Given that the other players are performing a given set of strategies, the remaining player’s preferred strategy should be playing x”.

The set of preference arguments for a game G is denoted by Ap(G). A cluster of preference arguments is a maximal set of preference arguments sharing the same partial strategy profile.

Finally, we introduce valuation arguments, which can be interpreted as statements of the form: “Given that the other players are performing a given set of strategies, it is the case that the outcome of strategy s is better than the outcome of strategy s′ for the remaining player”.

The set of valuation arguments for a game G is denoted by Av(G).

We now turn our attention to attacks. We note that preference and valuation arguments provide reasons why one argument should not attack another, and therefore introduce not only attacks between arguments, but also attacks on attacks.

The first attack captured within Definition 9 is between every two distinct game-based arguments. As each player has to choose exactly one strategy, different strategy profiles are clearly incompatible. The second bullet point represents attacks between preference arguments. In the stag hunt example for instance, a5 attacks a6 (and vice-versa) because in the event of player 0 hunting a stag, player 1 can either hunt a stag or a hare. The third type of attack captures attacks from preference arguments to attacks between game-based arguments. Within the stag hunt, a5 attacks (a1,a2) because a5 states that it is preferable for player 1 to hunt a stag when player 0 is also hunting a stag. Note that in general, the preference argument (S1,s2) attacks all attacks against the game-based argument S1⊕s2 coming from any other game-based arguments of the form S1⊕s′, for any s′∈Ac such that s′≠s2. The last type of attack captures attacks from valuation arguments to attacks between preference arguments. Returning to the stag hunt, a13 attacks (a6,a5) as a13 states that the strategy “hunt a stag” is better than the strategy “hunt a hare” for player 1 when player 0 is hunting a stag.

The arguments and attacks induce a very specific type of extended argumentation framework, where object-level (game-based) arguments have their attacks attacked by meta-arguments (preference arguments) at level one, and where attacks between these meta-arguments are attacked by meta-arguments at level two (valuation arguments).

The first layer is needed to encode every possible outcomes, the second layer is useful for specifying outcomes that are comparable whereas the third layer returns an agent’s preference between two outcomes.

Example 4

Example 4(Example 3 Contd).

Fig. 1 represents the game-based, preference and valuation arguments of G using blue (a1, a2, a3 and a4), yellow (a5 to a12) and green nodes respectively (a13 to a16). The attacks between arguments (C) and on attacks (D) are represented using solid black arrows and dashed red arrows respectively.

Fig. 1.

Argumentation graph corresponding to stag hunt game.

For our framework to be an EAF, it must satisfy some constraints, as described in [12], and we can easily show that this is the case.

Since – given Proposition 1 – our argumentation system is an EAF, we can use EAF semantics to evaluate it.

4.System properties

Having described our system, we now consider its properties. The most important result we seek to show is the correspondence between argumentation semantics and Nash equilibria, and we begin by laying the groundwork for this. We then consider how many arguments will be generated for an arbitrary normal form game.

We begin by considering which preference arguments will appear in a preferred extension. This result is used in later proofs.

Next, we show that if there is a preferred extension with game-based arguments, then each such extension has exactly one game-based argument.

We now show that a game-based argument which is not a Nash equilibrium will not appear in any preferred extension of the associated argumentation system.

In the next proposition, we show that if a preferred extension contains a game-based argument, then it is a stable extension.

It may seem intuitive that the preferred and stable extension should coincide. However, this is not the case, as demonstrated by the following counter-example.

Furthermore, even when multiple preferred extensions exist, these may not coincide with the stable extensions.

Table 4

Three strategy variant of the matching pennies game

We now turn to our main result, namely the equivalence of the Nash equilibrium with the game-based arguments found in the preferred extensions.

Returning to the stable extensions, the following result shows that there is a one-to-one correspondence between the sets of Nash equilibria and the set of classes of stable extensions,33 where each Nash equilibrium S corresponds to the class of stable extensions containing argument S.

Finally, we consider how many arguments an argumentation system representing a normal form game will contain.

We note that computing Nash equilibria is known to be computationally difficult, and the result regarding the number of arguments is therefore unsurprising.

5.Dialogue-based explanations

In this section, we show how our framework can be used for determining whether a pure strategy profile is a Nash equilibrium or not. Let G=(Ag,Ac,Av,Ou,Ef,⩽) be a game, and ASG=(A,C,D) the corresponding AS. We consider a dialogue between two agents (the proponent P and the opponent O). The proponent’s goal is to show that an argument A is a Nash Equilibrium and the opponent seeks to demonstrate that the proponent’s game argument (A) is not a Nash equilibrium by proposing an alternative game-based argument (B) such that there is a player i∈Ag for which A−i=B−i and A≠B and for whom B yields a better outcome than A.

We now demonstrate the sequence of utterances dialogue participants should use to ensure that the proponent will win the dialogue if and only if A is a Nash equilibrium. However, argument B advanced by the opponent may not be a Nash Equilibrium. Therefore, multiple rounds of the dialogue may be required to identify such equilibria.

The dialogue consists of agents advancing locutions which refer to arguments, valuations and players. While a dialogue without locutions can be defined, we believe that such locutions aid the explanatory process without introducing additional complexity, and that the locutions’ intuitive meaning is clear. We therefore do not provide a formal account of these locutions. There can be three possible scenarios for the dialogue:

If the resultant dialogue evolves as per Scenario 1, then the proponent’s game argument is not a Nash Equilibrium.

6.Discussion, related and future work

In this paper, we described how normal form games can be given an argumentation-based interpretation so as to allow – via argumentation semantics – for pure Nash equilibria to be computed. Intuitively, a Nash equilibrium identifies the best strategy a player can pursue given others’ strategies. However, explaining – to a non-expert – why some set of strategies forms a Nash equilibrium is often difficult, and our argument-based interpretation is the first step towards an explanatory dialogue for such explanation. Other work has shown the utility of providing such dialogue-based explanations [5,8,15].

Our approach is based on extended argumentation frameworks, and Modgil [12] has proposed a proof dialogue for such frameworks. The dialogue presented in Section 5 is tailored for our framework and more specialised than Modgil’s proof dialogue, but (we believe) provides a better explanation. In addition, while Modgil’s dialogue specifies legal moves, it does not identify what arguments should be advanced by a dialogue participant, noting only that there exists a winning strategy to demonstrate that an argument is in the credulous preferred semantics. In contrast, our (simple) dialogue amalgamates both the legal moves that a player can make and the strategy that they must follow. This is best illustrated in Table 8, which shows two possible dialogues of the stag hunt game (shown in Table 1 and Fig. 1) from Modgil’s system. The left hand dialogue is analogous to Scenario 2 of our approach (cf. Section 5), but contains only the arguments themselves without explaining why they exist or attack other arguments (unlike our approach). The dialogue on the right demonstrates a non-winning but legal strategy in Modgil’s system, which has no explanatory power.

Examining Tables 5–7, we note that the losing player will make a last concede move in all cases. This is similar to [11]’s proof dialogue where the winning player makes the last move. Furthermore, Tables 5–7 capture all possible evolutions of our explanatory dialogue.

If A is a Nash Equilibrium, then there is no dialogue whose first move by P is claim(A) and finishes with P conceding. Thus, P will win the dialogue and show that A is a Nash Equilibrium. Similarly, if A is not a Nash Equilibrium, then there is a dialogue whose first move by P is claim(A) and finishes by P conceding. Thus, P will lose the dialogue under perfect play. Therefore, our dialogue will identify whether a game argument is, or is not a NE. By running the dialogue over every game argument A, we are able to determine whether it is a NE. In other words, our dialogue is sound and complete. We note that the dialogue game of [11] is also sound and complete, making them – in some sense – equivalent in this context.

In the short term, we intend to empirically evaluate the explanatory capability of our dialogue with human subjects. Other extensions which we intend to investigate include providing an argumentation semantics for mixed Nash equilibria (perhaps through the use of some form of ranking semantics [1,4,10]), and investigating other solution concepts (e.g., Pareto optimality) for more complex types of games. Finally, there are clear links between game theory and group-based practical reasoning. Building on work such as [2,19], we intend to investigate how an argument-based formulation to practical reasoning underpinned by game theory can be created.

In this work, we introduced three levels of argument to compute the Nash equilibria. An obvious alternative formulation would use a single level, where joint strategy profiles are arguments (equivalent to game-based arguments), and attacks are constructed based on the algorithm for computing equilibria. While this approach would yield similar results, it provides no explanation as to why the attacks appear (and therefore why something is a Nash equilibrium).In our formulation, we have arguments about the object level (i.e., game arguments), as well as arguments about preferences over these objects, which are themselves reasoned about. Modgil [11] demonstrates that the standard way of reasoning about such structures is through the use of meta-level argumentation, instantiated as an extended argumentation framework. By making use of this multi-level approach, we have shown how our dialogues can exploit this structure to provide explanation.

Several other authors have investigated some links between game theory and argumentation. For example, in his seminal paper, Dung [6] noted that the stable extension corresponds to the stable solution of an cooperative n-person game, but did not seem to deal with non-cooperative games as we do here. Game theory was also used to describe argument strength by Matt and Toni [10], and Rahwan and Larson [17] investigated the links between argumentation and game theory from a mechanism design point of view. Perhaps most closely related to the current work is Fan and Toni’s work [7] exploring the links between dialogue and assumption-based argumentation (ABA). Here, the authors showed how admissible sets of arguments obtained from their ABA constructs are equivalent to Nash equilibria. In contrast to the current work, they only considered two player games and utilised structured argumentation, allowing them to describe a proof dialogue with associated strategies.

7.Conclusions

In this paper, we provided an argumentation-based interpretation of pure strategies in normal form games, demonstrating how argumentation semantics can be aligned with the Nash equilibrium as a solution concept, and examining some of the argumentation system’s properties. We also formalised dialogues for our framework, highlighting how it can be used for real-word explanations of Nash Equilibria to non-experts.

We believe that this work has significant application potential in the context of argument-based explanation. At the same time, we recognise that there are significant open avenues for research in this area, but believe that the current work is an important step in investigating the linkages between the two domains.