A Characterisation of Strategy-Proofness for Grounded Argumentation Semantics

1 Introduction

Argumentation has recently become one of the key approaches to automated reasoning and rational interaction in Artificial Intelligence [Bench-Capon and Dunne, 2007]. A key milestone has been Dung's landmark framework [Dung, 1995]. Arguments are viewed as abstract entities, with a binary defeat relation among them (resulting in a so-called argument graph). This view of argumentation enables highlevel analysis while abstracting away from the internal structure of individual arguments. Much research has been done on defining criteria (so-called semantics) for evaluating complex argument structures [Baroni and Giacomin, 2007].

However, most research that employs Dung's approach discounts the fact that argumentation is often a multi-agent, adversarial process. Thus, the outcome of argumentation is determined not only by the rules by which arguments are evaluated, but also by the strategies employed by the agents who present these arguments. As these agents may be selfinterested, they may have conflicting preferences over which arguments end up being accepted. As such, the design of the argument evaluation rule should take the mechanism design perspective [Mas-Colell et al., 1995, Ch 23]: what game rules guarantee a desirable social outcome when each selfinterested agent selects the best strategy for itself?

Recently, we introduced Argumentation Mechanism Design (ArgMD) as a framework for analysing the strategic incentives in argumentation and applied it to the well-known grounded semantics [Rahwan and Larson, 2008]. However, this preliminary analysis focused on a rather peculiar form of agent preferences: each agent wishes to get as many of its arguments accepted as possible. Moreover, they assumed agents can only hide, but not lie about, arguments.

In this paper, we apply the ArgMD framework to a more natural form of agent preferences, namely situations in which each agent has a single focal argument it wishes to have accepted. We provide a full characterisation of the strategyproofness (i.e. truth-telling being a dominant strategy equilibrium) under grounded semantics when agents both hide and/or lie about arguments. We also provide intuitive, sufficient graph-theoretic conditions for strategy-proofness.

The paper advances the state-of-the-art in the computational modelling of argumentation in two major ways. Firstly, it provides the first comprehensive analysis of strategic incentives under grounded semantics when agents have focal arguments. This is a much more realistic (and common) form of agent preferences than the only other analysis undertaken to-date for grounded semantics (by [Rahwan and Larson, 2008]). Secondly, the paper provides the first analysis of incentives when agents can lie in argumentation. This is important since it shows that the ArgMD approach can be extended to such more realistic cases.

2 Background

We now briefly outline some of key elements of abstract argumentation frameworks. We begin with Dung's abstract characterisation of an argumentation system [Dung, 1995].

Definition 1 (Argumentation framework). An argumentation framework is a pair AF = 〈A,⇀〉 where A is a set of arguments and ⇀⊆ A×A is a defeat relation. We say that an argument α defeats an argument β if (α, β) ∈⇀ (sometimes written α ⇀ β). 1

An argumentation framework can be represented as a directed graph in which vertices are arguments and directed arcs characterise defeat among arguments.

Definition 2 (Conflict-free, Defence). Let 〈A,⇀〉 be an argumentation framework and let S ⊆ A and let α ∈ A.

1 We restrict ourselves to finite sets of arguments.

• S is conflict-free if S ∩ S+ = ∅.
• S defends argument α if α- ⊆ S+. We also say that argument α is acceptable with respect to S.

Intuitively, a set of arguments is conflict free if no argument in that set defeats another. A set of arguments defends a given argument if it defeats all its defeaters. We now look at the collective acceptability of a set of arguments.

Definition 3 (Characteristic function). Let AF = 〈A,⇀〉 be an argumentation framework. The characteristic function of AF is FAF : 2A → 2A such that, given S ⊆ A, we have FAF (S) = {α ∈ A | S defends α}.

When there is no ambiguity about the argumentation framework in question, we will use F instead of FAF .

Definition 4 (Acceptability semantics). Let S be a conflictfree set of arguments in framework 〈A,⇀〉.

• S is admissible if it is conflict-free and defends every element in S (i.e. if S ⊆ F(S)).
• S is a complete extension if S = F(S).
• S is a grounded extension if it is the minimal (w.r.t. setinclusion) complete extension.

Intuitively, a set of arguments is admissible if it is a conflict-free set that defends itself against any defeater - in other words, if it is a conflict free set in which each argument is acceptable with respect to the set itself.

An admissible set S is a complete extension if and only if all arguments defended by S are also in S (that is, if S is a fixed point of the operator F). There may be more than one complete extension, each corresponding to a particular consistent and self-defending viewpoint.

A grounded extension contains all the arguments which are not defeated, as well as the arguments which are defended directly or indirectly by non-defeated arguments. This can be seen as a non-committal view (hence the least fixed point of F). There always exists a unique grounded extension.

Definition 5 (Indirect defeat and defence [Dung, 1995]). Let α, β ∈ A. We say that α indirectly defeats β, written α ↪→ β, if and only if there is an odd-length path from α to β in the argument graph. We say that α indirectly defends β, written α ↬ β, if and only if there is an even-length path (with non-zero length) from α to β in the argument graph.

Finally, the set of initial arguments, denoted IN(AF), contains all arguments that have no defeaters.

3 ArgumentationMechanismDesign

In this section we briefly define the mechanism design problem for abstract argumentation, as introduced by [Rahwan and Larson, 2008]. In particular, we specify the agents' type spaces and utility functions, what sort of strategic behaviour agents might indulge in, as well as the kinds of social choice functions we are interested in implementing.

We define a mechanism with respect to an argumentation framework 〈A,⇀〉 with semantics S, and we assume that there is a set of I self-interested agents. We define an agent's type to be its set of arguments.

Definition 6 (Agent Type). Given an argumentation framework 〈A,⇀〉, the type of agent i, Ai ⊆ A, is the set of arguments that the agent is capable of putting forward.

An agent's type can be seen as a reflection of its expertise or domain knowledge. For example, medical experts may only be able to comment on certain aspects of forensics in a legal case, while a defendant's family and friends may be able to comment on his/her character. Also, such expertise may overlap, so agent types are not necessarily disjoint.

A social choice function f maps a type profile (agent type vector) into a subset of arguments. It specifies the arguments the judge would wish to accept if he knew all actual arguments.

We will be particularly interested in argument acceptability social choice functions.

Definition 7 (Argument Acceptability Social Choice Functions). Given an argumentation framework 〈A,⇀〉 with semantics S, and given a type profile (A1, . . . ,AI), the argument acceptability social choice function f is defined as the set of acceptable arguments given the semantics S. That is,

As is standard in the mechanism design literature, we assume that agents have preferences over the outcomes o ∈ 2A, represented in utility functions: ui(o,Ai) denotes agent i's utility for outcome o when its type is argument set Ai.

Agents may not have incentive to reveal their true types because they may be able to influence the status of arguments and thus obtain higher utility. On one hand, an agent might hide some of its arguments, e.g. to break defeat chains in the argument framework, thus changing the final set of acceptable arguments. Alternatively, an agent might lie by makingup new arguments that it does not have in its argument set. ArgMD aims to obtain the desired outcome (as per the social choice function) despite the potential for such manipulations.

A strategy of an agent specifies a complete plan that describes what action the agent takes for every decision that a player might be called upon to take, for every piece of information that the player might have at each time that it is called upon to act. In our model, the actions available to an agent involve announcing arguments according to some protocol. Thus a strategy, si ∈ Σi for agent i (where Σi is i's strategy space) would specify for each possible subset of arguments that could define its type, what set of arguments to reveal. An agent's strategy space specifies all its possible strategies.

Definition 8 (Argumentation Mechanism). Given an argumentation framework AF = 〈A,⇀〉 and semantics S, an argumentation mechanism is defined as

Note that in the above definition, the notion of dialogue strategy is broadly construed and would depend on the argumentation protocol. In a direct mechanism, however, the strategy spaces of the agents are restricted so that they can only reveal a subset of arguments indicating its (alleged) type

-that is, Σi = 2A. We focus here on direct mechanisms since, according to the revelation principle [Mas-Colell et al., 1995, Ch 23], any equilibrium of an indirect mechanism has an equivalent truthful direct mechanism. This approach is common in the mechanism design literature, since it greatly simplifies analysis without losing generality.

In Table 1, we summarise the mapping of multi-agent abstract argumentation as an a mechanism design problem.

We now present a direct mechanism for argumentation based on grounded semantics. The mechanism calculates the grounded extension given the arguments revealed by agents. We will refer to a specific action (i.e. set of declared arguments) as A◦i ∈ Σi.

Definition 9 (Grounded Direct Argumentation Mechanism). A grounded direct argumentation mechanism for argumentation framework 〈A,⇀〉 is Mgrnd AF = (Σ1, . . . , ΣI , g(.)) where:

• Σi ∈ 2A is the set of strategies available to each agent;
• g : Σ1 × · · · × ΣI → 2A is an outcome rule defined as: g(A◦1 , . . . ,A◦I ) = Acc(〈A◦1 ∪ · · · ∪ A◦I , ⇀〉, S grnd ) where S grnd denotes sceptical grounded acceptability semantics.

4 Agents with Focal Arguments

Earlier [Rahwan and Larson, 2008], we analysed the grounded argumentation mechanism under a highly restrictive form of agent preferences, called acceptability maximising preference: each agent wishes to get as many of its arguments accepted as possible. This is rarely seen in practice.

In many realistic dialogues, each agent i is interested in the acceptance of a particular argument ˆαi ∈ Ai, which we call the focal argument of agent i. Here, other arguments in Ai\{ˆαi } can merely be instrumental towards the acceptance of the focal argument. We are interested in characterising conditions under which Mgrnd AF is strategy-proof for scenarios in which each agent has a focal argument (Other preference criteria are also reasonable, such as wanting to win any argument from a set that support the same conclusion).

Definition 10 (Focal Argument for an Agent). An agent i has a focal argument ˆαi ∈ Ai if and only if ∀o1, o2 ∈ O such that ˆαi ∈ o1 and ˆαi /∈ o2, we have ui(o1, Ai) > ui(o2, Ai), otherwise ui(o1, Ai) = ui(o2, Ai).

Let o ∈ O be an arbitrary outcome. If ˆαi ∈ o, we say that agent i wins in outcome o. Otherwise, i loses in outcome o.

5 When Agents can Hide Arguments

In this section, following our earlier work [Rahwan and Larson, 2008], we assume that there is an external verifier that is capable of checking whether it is possible for a particular agent to actually make a particular argument. Informally, this means that presented arguments, while still possibly defeasible, must at least be based on some sort of demonstrable 'plausible evidence.' If an agent is caught making up arguments then it will be removed from the mechanism. For example, in a court of law, any act of perjury by a witness is punished, at the very least, by completely discrediting all evidence produced by the witness. Moreover, in a court of law, arguments presented without any plausible evidence are normally discarded (e.g. "I did not kill him, since I was abducted by aliens at the time of the crime!"). For all intents and purposes this assumption removes the incentive for an agent to make things up.

To investigate whether mechanism Mgrnd AF is strategyproof for any argumentation framework for agents with focal arguments, consider the following example.

Example 1. Consider a grounded direct argumentation mechanism with agents x, y and z with types Ax = {α1, α4}, Ay = {α2} and Az = {α3} respectively, and with focal arguments defined as follows: ˆαx = α4; ˆαy = α2; ˆαz = α3. Let the defeat relation be defined as follows: ⇀= {(α1, α2), (α2, α3), (α3, α4)}. If agents reveal all their arguments, we have the graph shown in Figure 1(a), with the accepted arguments marked by boxes. Here, agent z is the only winner.

It turns out that the mechanism is susceptible to strategic manipulation, even if we suppose that agents do not lie by making up arguments (i.e., they may only withhold some arguments). In this case, for both agents y and z, revealing their true types weakly dominates revealing nothing at all (since hiding their single focal arguments can only guarantee their respective loss). However, it turns out that agent x is better off only revealing {α4}. By withholding α1, the resulting argument network becomes as depicted in Figure 1(b). Under this outcome, x wins, which is better for x than truth-revealation.

Remark 1. Given an arbitrary argumentation framework AF and agents with focal arguments, mechanismMgrnd AF is not strategy-proof.

Having established this property, the natural question to ask is whether mechanism Mgrnd AF is strategy-proof under some conditions. The following theorem provides a full characterisation of strategy-proof mechanisms for sceptical argumentation frameworks, for agents with focal arguments, when hiding arguments is possible. Note that A-i denotes arguments of all agents other than agent i.

Theorem 1. Let AF be an arbitrary argumentation framework, and let GE(AF) denote its grounded extension. Mechanism Mgrnd AF is strategy-proof for agents with focal arguments if and only if AF satisfies the following condition: ∀i ∈ I, ∀S ⊆ Ai and ∀A-i, we have ˆαi /∈ GE (〈Ai∪A-i, ⇀ 〉) implies ˆαi /∈ GE (〈(Ai\S) ∪ A-i, ⇀〉).

Proof. ⇒) Let i ∈ I be an arbitrary agent with type Ai and focal argument ˆαi ∈ Ai. Suppose Mgrnd AF is strategy-proof. This implies that ∀S ⊆ Ai and ∀A-i:

Therefore, by definition of the focal argument: if ˆαi ∈ GE(〈S ∪A-i,⇀〉) then ˆαi ∈ GE(〈Ai ∪A-i,⇀〉). Then, by contraposition we have that:

ˆαi /∈ GE (〈Ai ∪A-i,⇀〉) implies ˆαi /∈ GE (〈S∪A-i, ⇀〉). ⇐) Suppose that given any A-i, we have that ∀i ∈ I, ∀S ⊆ Ai, ˆαi /∈ GE(〈Ai ∪ A-i,⇀〉) implies ˆαi /∈ GE(〈S ∪ A-i, ⇀〉).

We want to prove that:

But this means that ˆαi ∈ GE(〈S′ ∪ A-i,⇀〉) while ˆαi /∈ GE (〈Ai ∪ A-i,⇀〉). Contradiction. Therefore, i has no incentive to declare any arguments other than those of her type, and thus the mechanism is strategy-proof.

This result is consistent with the literature on mechanism design. While general strategy-proof results obtain only at the cost of dropping other desirable properties (like nondictatorship, as per the Gibbard-Satterthwaite theorem [MasColell et al., 1995, Ch 23]), positive results obtain by restricting the domain of types on which the mechanism is applied (e.g. restriction to quasi-linear preferences [Mas-Colell et al., 1995, Ch 21]).

Although the above theorem gives us a full characterisation, it is difficult to apply in practice. In particular, the theorem does not give us an indication of how agents (or the mechanism designer) can identify whether the mechanism is strategy-proof for a class of argumentation frameworks by appealing to explicit graph-theoretic properties. Below, we provide such analysis. But before we can do this, we present the following lemma. This lemma explores what happens when we add a new argument (and its associated defeats) to a given argumentation framework, thus resulting in a new argumentation framework. In particular, we are interested in conditions under which arguments acceptable in the first framework are also accepted in the second. We show that this is true under the condition that the new argument does not indirectly defeat arguments acceptable in the first framework.

Lemma 1 ([Rahwan and Larson, 2008]). Let AF1 = 〈A,⇀1〉 and AF2 = 〈A ∪ {α′ },⇀2〉 such that ⇀1⊆⇀2 and (⇀2 \ ⇀1) ⊆ ({α′ } ×A) ∪ (A× {α′ }). If α is in the grounded extension of AF1 and α′ does not indirectly defeat α, then α is also in the grounded extension of AF2.

With the above lemma in place, we now provide an intuitive, graph-theoretic condition that is sufficient to ensure that Mgrnd AF is strategy-proof when agents have focal arguments.

Theorem 2. Suppose every agent i ∈ I has a focal argument ˆαi ∈ Ai. If each agent's type contains no (in)direct defeat against ˆαi (formally ∀i ∈ I, ∄α ∈ Ai such that α ↪→ ˆαi ), then Mgrnd AF is strategy-proof.

Proof. Let A′-i = (A′1 , . . . ,A′i-1 ,A′i+1 , . . . ,A′I ) be arbitrary revelations from all agents not including i. We will show that agent i is always best off revealing Ai. That is, no matter what sets of arguments the other agents reveal, agent i is best off revealing its full set of arguments. Formally, we will show that ∀i ∈ I ui(Acc(〈A′1 ∪ · · · ∪ Ai ∪ · · · ∪ A′I , ⇀ 〉, S grnd ),Ai) ≥ ui(Acc(〈A′1 ∪ · · · ∪ A◦i ∪ · · · ∪ A′I , ⇀ 〉, S grnd ), Ai) for any A◦i ⊂ Ai .

We use induction over the sets of arguments agent i may reveal, starting from the focal argument ˆαi ( note that any strategy that does not reveal ˆαi can be safely ignored). We show that, considering any strategy A′′ i ⊆ Ai, revealing one more argument can only increase i's chance of getting ˆαi accepted, i.e. it (weakly) improves i's utility.

Base Step: If Ai = {ˆαi }, then trivially, revealing Ai weakly dominates revealing ∅.

Induction Step: Suppose that revealing argument set A′′ i ⊆ Ai weakly dominates revealing any subset of A′′ i . We need to prove that revealing any additional argument can increase, but never decrease the agent's utility. In other words, we need to prove that revealing any set A′i , where A′′ i ⊂ A′i ⊆ Ai and |A′i | = |A′′ i | + 1, weakly dominates revealing A′′ i .

Let α′ where {α′ } = A′i - A′′ i be the new argument.

Suppose the focal argument ˆαi is in the grounded extension when revealing A′′ i (formally ˆαi ∈ Acc(〈A′1 ∪ · · · ∪ A′′ i ∪ · · · ∪A′I , ⇀〉, S grnd )). We need to show that after adding α′ , argument ˆαi remains in the grounded extension. Formally, we need to show that ˆαi ∈ A′i ∩Acc(〈A′1 ∪· · ·∪A′i ∪· · ·∪A′I , ⇀ 〉, S grnd ). This is true from Lemma 1, and from the fact that Ai does not include indirect defeats against ˆαi .

Thus, by induction, revealing the full set Ai weakly dominates revealing any sub-set thereof.

Note that in the theorem, ↪→is over all arguments inA. Intuitively, to guarantee the strategy-proof property for agents with focal arguments, it suffices that no (in)direct defeats exist from an agent's own arguments to its focal argument. Said differently, each agent i's arguments must not undermine its own focal argument, neither explicitly and implicitly. By 'explicitly,' we mean that none of i's own arguments can defeat its focal argument. By 'implicitly,' we mean that other agents cannot possibly present a sequence of arguments that reveal an indirect defeat between i's own arguments and its focal argument. More concretely, in Example 1 and Figure 1(a), while agent x's argument set Ax = {α1, α4} is conflict-free, when agents y and z presented their own arguments α2 and α3, they revealed an implicit conflict between x's arguments and x's focal argument. In other words, they showed that x contradicts himself (i.e. committed a fallacy of some kind).

An important observation is that under the condition in Theorem 2, we need not assume that the actual set of possible presentable arguments is common knowledge. To ensure the strategy-proof property, each agent only needs to know that indirect defeat chains cannot arise from any of its arguments to its focal argument.

One may reasonably ask if the sufficient condition in Theorem 2 is also necessary for agents to reveal all their arguments truthfully. As Example 2 shows, this is not the case. In particular, for certain argumentation frameworks, an agent may have truthtelling as a dominant strategy despite the presence of indirect defeats among its own arguments.

Example 2. Consider the variant of Example 1 with the additional argument α5 and defeat (α5, α3). Let the agent types be Ax = {α1, α4, α5}, Ay = {α2} and Az = {α3} respectively. The full argument graph is depicted in Figure 2. With full revelation, the mechanism outcome rule produces the outcome o = {α1, α4, α5}.

Note that in Example 2, truth revelation is now a dominant strategy for x despite the fact that α1 ↪→ α4 (note that here, x gains nothing by hiding α1). This hinges on the presence of an argument (namely α5) that cancels out the negative effect of the (in)direct self-defeat among x's own arguments.

6 When Agents can Hide or Lie

In the previous section, we restricted agent strategies to showing or hiding arguments in their own type. We did not allow agents to reveal arguments that are outside of their types. That is, agents were not allowed to lie by stating something they did not know, but only by hiding something they do know. This is the approach taken originally by us [Rahwan and Larson, 2008].

In this section, we investigate (for the first time) strategyproofness of grounded mechanisms without this assumption. We first show that the characterization of strategy-proofness is identical to that when agents could only hide arguments (the only difference is that S ranges over A instead of Ai).

Theorem 3. Let AF be an arbitrary argumentation framework, and let GE(AF) denote its grounded extension. Mechanism Mgrnd AF is strategy-proof for agents with focal arguments if and only if AF satisfies the following condition: ∀i ∈ I, ∀S ⊆ A and ∀A-i, we have ˆαi /∈ GE (〈Ai ∪A-i, ⇀ 〉) implies ˆαi /∈ GE (〈S ∪ A-i, ⇀〉).

Proof. The proof is essentially the same as the proof of Theorem 1, such that S ranges over A instead of Ai.

As we did in the case of hiding, this result can be weakened to yield a more intuitive sufficient condition for strategyproofness.

Theorem 4. Suppose every agent i ∈ I has a focal argument ˆαi ∈ Ai. If the following conditions hold:

• (A) no agent type contains (in)direct defeat against its focal argument (formally ∀i ∈ I, ∄β ∈ Ai such that β ↪→ ˆαi );
• (B) no argument outside any agent's type (in)directly defends its focal argument (formally ∀i ∈ I, ∄β ∈ A\Ai such that β ↬ ˆαi );

Proof. What we want to prove is that ∀i, ∀A-i and ∀S ̸= Ai, if (A) and (B) hold, then

Following the definition of focal arguments, our goal above can be rephrased as proving, for any arbitrary S ̸= Ai, that:

Suppose ˆαi /∈ GE(〈Ai ∪ A-i,⇀〉), and let us show that ˆαi /∈ GE (〈S ∪ A-i, ⇀〉).

We do this by showing, recursively, that for a given ˆαi ,

there must exist a β ⇀ α such that for all z ⇀ β: z /∈ GE(〈Ai ∪A-i,⇀〉) then z /∈ GE(〈S ∪A-i,⇀〉) implies α /∈ GE(〈Ai ∪A-i,⇀〉) then α /∈ GE(〈S∪A-i,⇀ 〉).

Base Step: From ˆαi /∈ GE(〈Ai ∪A-i,⇀〉), it follows that ∃β ∈ Ai ∪A-i, β ⇀ ˆαi for which ∄z ∈ GE(〈Ai ∪A-i, ⇀〉) such that z ⇀ β. Let β1 = β be such a defeater.

By assumption (A), β1 /∈ Ai (since otherwise, we would have β1 ⇀ ˆαi and therefore β1 ↪→ ˆαi for some β1 ∈ Ai). But since β1 ∈ Ai∪A-i, we conclude that β1 ∈ A-i. This in turn implies that β1 ∈ S ∪A-i. In other words, the defeaters of ˆαi given action profile Ai ∪ A-i are preserved when the agent changes the action profile to S ∪ A-i.

We will now show that ∄z ∈ GE(〈S ∪A-i, ⇀〉) such that z ⇀ β1 .

Let z1 ∈ S ∪ A-i, such that z1 ⇀ β1 , be an arbitrary defeater of β1 when agent i lies. By assumption (B), we conclude that z1 /∈ A\Ai (since otherwise, we would have z1 ⇀ β1 ⇀ ˆαi and therefore z ↬ ˆαi for some z ∈ A\Ai). This in turn implies that z1 ∈ Ai. In other words, no new defenders of ˆαi can be introduced when the agent moves from action profile Ai ∪A-i to action profile S ∪A-i. Therefore, since we already know that z1 /∈ GE(〈Ai ∪ A-i,⇀〉), z1 cannot be in GE(〈S ∪A-i,⇀〉). Then:

Suppose now that ˆαi ∈ GE(〈S∪A-i, ⇀〉). This would mean that for every β ∈ Ai ∪A-i, β ⇀ ˆαi , ∃z ∈ GE(〈S∪A-i,⇀ 〉) such that z ⇀ β, but then, for β1 there should exist a z1 satisfying this condition. But by (∗), no z1 ∈ GE(〈S ∪ A-i,⇀〉). Therefore, we have from (∗) that:

ˆαi /∈ GE (〈Ai ∪A-i,⇀〉) implies ˆαi /∈ GE (〈S∪A-i, ⇀〉). Recursive Step: Let zk ∈ Ai ∪A-i be an arbitrary argument such that zk ⇀ βk for some βk with βk ↪→ ˆαi . Assume that zk /∈ GE(〈Ai ∪ A-i,⇀〉). We will show that zk /∈ GE (〈S ∪ A-i, ⇀〉).

From zk /∈ GE (〈Ai ∪A-i,⇀〉), it follows that ∃β ∈ Ai ∪ A-i such that β ⇀ zk while ∄zk+1 ∈ GE(〈Ai ∪ A-i, ⇀〉). Let βk+1 = β be such a defeater.

By assumption (A), βk+1 /∈ Ai (since otherwise, we would have βk+1 ↪→ ˆαi for some βk+1 ∈ Ai). But since βk+1 ∈ Ai ∪A-i, we conclude that βk+1 ∈ A-i. This in turn implies that βk+1 ∈ S ∪A-i. In other words, the defeaters of zk+1 given action profile Ai ∪ A-i are preserved when the agent changes the action profile to S ∪ A-i.

We will now show that ∄z ∈ GE(〈S ∪A-i, ⇀〉) such that z ⇀ βk+1 .

Let zk+1 ∈ S ∪ A-i such that zk+1 ⇀ βk+1 be an arbitrary defeater of βk+1 when agent i lies. By assumption (B), we conclude that zk+1 /∈ A\Ai (since otherwise, we would have zk+1 ⇀ βk+1 ↪→ ˆαi and therefore z ↬ ˆαi for some z ∈ A\Ai). This in turn implies that zk+1 ∈ Ai. In other words, no new defenders of ˆαi can be introduced when the agent moves from action profile Ai ∪ A-i to action profile S ∪ A-i. Therefore, since we already know that zk+1 /∈ GE(〈Ai ∪ A-i,⇀〉), zk+1 cannot be either in GE(〈S ∪A-i,⇀〉). Then:

Suppose now that zk ∈ GE(〈S ∪ A-i,⇀〉). This would mean that for every β ∈ Ai ∪A-i, β ⇀ ˆαi , ∃z ∈ GE(〈S ∪ A-i,⇀〉) such that z ⇀ β, but then, for βk there should exist a zk satisfying this condition. But by (∗∗), no zk+1 ∈ GE(〈S ∪ A-i,⇀〉). Therefore, we have that from (∗∗) it follows that:

zk /∈ GE (〈Ai ∪A-i,⇀〉) implies zk /∈ GE (〈S∪A-i, ⇀〉). Recursion Termination: The recursion must eventually reach some βK ∈ IN(〈Ai ∪ A-i,⇀〉) with βK ↪→ ˆαi . Let zK ∈ S ∪ A-i such that zK ⇀ βK be an arbitrary defeater of βK when agent i lies. By assumption (B), we conclude that zK /∈ A\Ai (since otherwise, we would have zK ⇀ βK ↪→ ˆαi and therefore z ↬ ˆαi for some z ∈ A\Ai). But this in turn implies that zK ∈ Ai. But this contradicts with the fact that βK ∈ IN(〈Ai ∪ A-i,⇀〉). Hence, no such zK exists and therefore zK /∈ GE(〈Ai ∪ A-i, ⇀〉). Furthermore, we conclude that βK /∈ IN(〈S ∪ A-i,⇀〉) and thus βK /∈ GE(〈S ∪ A-i,⇀〉). Therefore, zK /∈ GE (〈Ai ∪A-i,⇀〉) such that zK ⇀ βK . In summary:

zK /∈ GE(〈Ai∪A-i,⇀〉) implies zK /∈ GE (〈S∪A-i, ⇀〉). By the above recursion, we conclude that, since ˆαi /∈ GE (〈Ai ∪A-i,⇀〉) it follows that ˆαi /∈ GE (〈S ∪A-i, ⇀〉). Therefore, Mgrnd AF is strategy-proof.

Let us interpret the above theorem intuitively. The theorem rests on two key conditions: (a) that an agent cannot benefit from hiding any of its own arguments, because its arguments cannot "harm" its focal argument; and (b) that an agent cannot benefit from revealing any argument it does not have, because these arguments cannot "benefit" its focal argument. For the theorem to hold, these conditions must be satisfied for every agent, no matter what the other agents reveal. While this may appear obvious in hindsight, the precise proof is rather involved, and requires careful attention to the intricate aspects of the grounded semantics when applied to different related argument graphs - namely graphs corresponding to different strategy profiles that agents may choose to play. This level of attention to detail is essential for any thorough analysis of strategic argumentation.

7 Conclusion

ArgMD is a new paradigm for studying argumentation among self-interested agents using game-theoretic techniques. It provides a fresh perspective on the study of semantics for conflicting knowledge bases, especially when those are distributed among different entities (e.g. knowledge-based agents on the Semantic Web). While game-theoretic approaches have been applied extensively to resource allocation among agents (e.g. through auctions), no similar development has yet taken place for strategic aspects of interaction among knowledge-based agents.

The only other paper that uses ArgMD to-date [Rahwan and Larson, 2008] dealt with a highly restricted form of agent preferences, and assumed agents can only hide, but not lie about, arguments. In this paper, we showed how ArgMD can be applied to more realistic preferences and action spaces.

Future work includes analysing incentives under other varieties of agent preferences and other argumentation semantics.

Acknowledgments

We are grateful to the anonymous reviewers for the valuable advice, which helped us improve the paper.