Hi.
I found that some query contains unnecessary information
sample query
https://arxiv.org/pdf/1605.00495v1.pdf
results
{
"title": "Coalition Formability Semantics with Conflict-Eliminable Sets of Arguments",
"authors": [
"Ryuta Arisaka",
"Ken Satoh"
],
"abstruct": " We consider abstract-argumentation-theoretic coalition formability in this\nwork. Taking a model from political alliance among political parties, we will\ncontemplate profitability, and then formability, of a coalition. As is commonly\nunderstood, a group forms a coalition with another group for a greater good,\nthe goodness measured against some criteria. As is also commonly understood,\nhowever, a coalition may deliver benefits to a group X at the sacrifice of\nsomething that X was able to do before coalition formation, which X may be no\nlonger able to do under the coalition. Use of the typical conflict-free sets of\narguments is not very fitting for accommodating this aspect of coalition, which\nprompts us to turn to a weaker notion, conflict-eliminability, as a property\nthat a set of arguments should primarily satisfy. We require numerical\nquantification of attack strengths as well as of argument strengths for its\ncharacterisation. We will first analyse semantics of profitability of a given\nconflict-eliminable set forming a coalition with another conflict-eliminable\nset, and will then provide four coalition formability semantics, each of which\nformalises certain utility postulate(s) taking the coalition profitability into\naccount.\n",
"pdfurl": "https://arxiv.org/pdf/1605.00495v1",
"references": [
"] I taking the coalition prof itability into account. A . 1 Introduction s c Coalition formation among agents is an important topic in many ",
"[ domains including economics, political science, and computer sci- 1 ence. Two groups of agents, by teaming up together, could achieve v a task which they cannot on their own. Exploring abstract argumen- 5 tation theory for finding an apt characterisation of coalition forma- 9 bility looks specially rewarding, and there are already a few papers 4 in the literature looking at this subject matter: with preference-based 0 argumentation frameworks and task allocations [1]; with a coopera- 0 tive goal generation and fulf illing ",
"[7] respecting the property of reci- . 5 procity, i.e.agents give to the coalition they are in and benef it from 0 it; and with dialogue games and pay-offs ",
"[21]. Shared by them is the 6 theme of identifying a group of individual agents who optimise ben- 1 efits/social welfare to themselves by being in the group. The optimal : v group thus formed is free of internal conflicts, and the participating i agents do not have to give up anything by being a part. We consider X these types of coalitions supportive. r The sort of coalition formationwehaveinmind,ontheotherhand, a is one that may be found in political alliance among political parties. Such alliance is motivated if, for example, political parties want to reach the voting threshold of passing certain bills. A politicalalliance-like coalition exhibits the following unique characteristics: More organisational than individual It is not possible to freely move agents across multiple political parties such as to connect 1 National Institute of Informatics, Japan, email: ryutaarisaka@gmail.com 2 National Institute of Informatics, Japan, email: ksatoh@nii.ac.jp those having close interests together for formation of optimal political parties. A participant to a political party is often expected to stay in the party during the parliament term. The assumption of self-interested agents as studied in ",
"[21] does not fit very well here. There are repercussions to prof itability of a coalition, too, in that it is primarily for a party’s, or parties’, benef its than the participants’ benef its that a political alliance is formed. Partial internal conflicts Agents in a political party should support the party’s agendas and policies. Hence they do not defeat each other about them, broadly spoken. It is common, however, that there are smaller factions within a political party arguing against one another over details. This often entails that some participating agents cannot proclaim their opinions on certain policies as the party’s opinions. Put another way, some individual opinions may be toned down for the party. Asymmetry in attacks to and from a coalition For a political alliance to retain any credibility for the arguments it expresses, it must argue only by the conflict-free, i.e. self-contradiction-free, portion of the arguments of the party’s participants. But the other political parties not in the alliance are unhindered by the personal circumstance of the alliance. If a political party A is in alliance with another political party B, then an external party C can argue against any argument of the individual participants in A or in B as an argument against the coalition. Better larger than smaller In ",
"[1], the rate of defections is associated to the number of agents in a coalition, thus a smaller set preferred. That does not carry over here: if one single political party or one single political alliance dominates the parliament, it has total freedom in policy making, which is clearly desirable. While not primarily on abstract argumentation, there is a work ",
"[8] on alternating-temporal logic incorporating the framework of ",
"[1]. In the logic, a larger set is better. In this work, we contemplate abstract-argumentation-theoretic char- acterisations of prof itability, and then formability, of a coalition of this kind. More specif ically we consider the following questions: (1) supposea set of arguments that may contain partial internal conflicts (as an abstract representation of a political party) and suppose also rational criteria of prof itability, with which other (disjoint) sets of ar- guments that may also contain partial internal conflicts (i.e. represen- tations of other political parties) can it prof itby forming a coalition?; and (2) suppose the prof itability relation, supposesome rational prin- ciples to judge the goodness of a coalition, and suppose such a set of arguments, which other (disjoint) such sets of arguments can it actu- ally form a coalition? The following are particularly interesting technicalities in the derivation of these semantics. First and foremost, the above- described coalition formability is not simply about whether the re- sulting coalition is acceptable, which could be handled by adapting the standard acceptability semantics in abstract argumentation the- ory, but about whether a set of arguments potentially with partial internal conflicts forms a coalition with another similar set. The for- mer concerns the state of the resulting set, while the latter must be parametrised by coalition prof itabilities of both sets. Secondly, be- cause of the presence of partial internal conflicts and of the asymme- try in attacks to and from a coalition, we have to: (1) obviously need a weaker notion than conflict-freeness asa property that a set of ar- guments should primarily satisfy - conflict-eliminability as we term it, which permits members of a set to attack other members of the same set so long as none of them is completely defeated; (2) obtain intrinsic arguments of a conflict-eliminable set, which are the argu- ments that would remain if any partial internal conflicts within the 3 set were resolved away ; and (3) use the intrinsic arguments to de- termine which external arguments are being attacked by the conflict- eliminable set, while still keeping the original arguments of the set in order to determine if it is being attacked by external arguments (see Asymmetry in attacks to and from a coalition above). Here again, our task is not just whether some set of arguments satisf ies conflict- eliminability, and we must consider if any attacks are strong enough to defeat an argument, and, in case an argument is attacked but not defeated, how much it would be weakened/compromised by the at- tacks. To cope with these, we attach argument capacity, a numerical value, to each argument, and an attack strength, again a numerical value, to each attack. The idea is: a set of arguments is conflict- eliminable just when none of the members of the set attack an ar- gument of the same set with a greater numerical value than the argu- ment’s capacity. As the argument capacities and attack strengths are both numerical, it iseasy to derive its intrinsic arguments and their attacks on external arguments. 1.1 Related work We are not aware of other works in the literature of abstract ar- gumentation theory dealing with this kind of political-alliance-like coalition formation. Also, to the best of our knowledge, the previous approaches proposed in the abstract argumentation literature are not self-suff icient for dealing with the two above-mentioned technicali- ties. We have already mentioned the key works on coalition forma- tion ",
"[1, 7, 21]. They apply Dung’s acceptability semantics ",
"[13] for characterising acceptability of a coalition that is individual-benef it- oriented, that is conflict-free, and that generally prefers a smaller set. In Section 4 of ",
"[7], a coalition is associated to a set of tasks/goals, and conflicts between coalitions are measured such as by competition which occurs when two coalitions share the same tasks/goals. We, however, focus on political-alliance-like coali- tion prof itability/formability semantics with conflict-eliminable sets of arguments. We do not consider the meta-knowledge of tasks or goals. Instead, we measure prof itability of a coalition for a conflict- eliminable set of arguments by: (1) the size of the coalition; (2) whether the number of attackers to the conflict-eliminable set of arguments increases or decreases in the coalition; and (3) how de- fended the coalition is from external arguments. Coalition forma- bility is relativised to prof itabilities of two conflict-eliminable sets. A rather different perspective of coalition formation: calculation of 3 This should not be confused. We are not meaning that some arguments would disappear as the result. The internal conflicts are assumed nondefeating. We rather mean that some arguments may be weakened of their potency. See Partial internal conflicts. What would remain are then those arguments unaffected by the partial internal conflicts and those weakened arguments. probabilistic likelihood of a coalition formation capable of achieving sometask,givenpriorprobabilityofagents’joininginacoalitionand of preventing other members from joining in the coalition, was high- lighted in probabilistic argumentation frameworks ",
"[19]. Such quan- titative judgement is out of the scope of this work. We mention other works relevant to ours. Attack-tolerant abstract argumentation Characterisation of acceptability semantics for a non-conflict-free set of arguments is gaining attention. Conflict-tolerant semantics ",
"[3] relaxes conflictfreeness by using four values (accept, reject, no opinion, and mixed feeling) for labelling arguments for para-consistent abstract argumentation. However, this approach does not incorporate numerical values, which makes it diff icult to reason about the strength of attacks. Weighted argument systems ",
"[15] attach numerical values to attack relations. There is also a system-wide numerical value called the inconsistency budget. In their systems, conflicts in a set of arguments are quantif ied as the sum of numerical values given to the attack relations appearing in the set. If the sum does not exceed the given inconsistency budget, then the set is considered para-conflict-free. Their acceptability semantics is relative to the global inconsistency budget. In our setting, having numerical attack strengths alone is not suff icient, aswe must know intrinsic arguments of a conflict-eliminable set, which relies both on attack strengths and on argument strengths. We do not use any global and uniform budget. Further, substantively we do not tolerate any inconsistency: intrinsic arguments must be conflictfree. Social abstract argumentation frameworks ",
"[18], to which an equational approach by Gabbay and Rodrigues ",
"[16] also relates, attach numerical values to arguments in the form of for votes and against votes. They allow for fine-grained para-consistency. We could potentially adapt their approach for characterisation of our conflict-eliminability. However, their numerical attack characterisations by votes are quite specif ic. We choose more abstract, axiomatic characterisations. In the literature, axiomatic approaches have been considered to for instance ensure logical consistency of an argumentation framework ",
"[2,9]. Classif ications of attack relations by axioms they satisfy have been also done ",
"[17]. The axiomatic approaches help regulate an abstract argumentation system from a general standpoint. Dynamic abstract argumentation From one perspective, our framework possessesa certain kind of dynamic nature. So far dynamic changes have been considered within the literature of abstract argumentation to: assume structural argumentation (e.g. Assumption-based argumentation ",
"[14]) and modify nonfalsif iable facts ",
"[22]; add a new argument ",
"[10]; revise attack relations ",
"[12]; revise an argumentation framework by encoding it into propositional logic ",
"[11]; and revise an argumentation framework with an argumentation framework ",
"[4].4 Given an argumentation framework, these works calculate a revised argumentation framework. That is, they derive a post-state from a pre-state given some input. In our setting, however, we require interactions between the initial set of arguments (the pre-state) and intrinsic arguments of a conflict-eliminable set (post-states) due to the asymmetry in attacks to and from a coalition. The pre-state/post-state coordinations are, as far as we are able to fathom, not dealt with in the above-mentioned studies. Meanwhile, one of the works on coalition formation mentioned earlier, namely ",
"[7], allows for coalitional and non-coalitional 4 There are also analysis on mutability of acceptable arguments by adding or removing an argument and/or an attack ",
"[5,6]. views ofagentsFrom anon-coalitionview ofagents,anumber of coalitionviews may bederived.Stilwhat theyconsiderare conflictamong coalitionviews (fogoal fulf illmewhich is a problempossessingadifferennature. 1.2 The remaining sections In therestwe willrecallNielsen-Parsonsargumentationframe- works ",
"[20]thatgeneralisDung’s oneswithgroup attack(Section 2);introduceourargumentationframeworksfor conflict-eliminable setsofarguments(Sectio3);and developsemanticforprof itability, and thenformabilityofcoalitioformation,atthe same timepre- sentingtheoreticresults(Sectio4),beforedrawing conclusions. We omit triviproofs. 2 Preliminaries WhileDung’sargumentationframeworks",
"[13]arethemostimportant in thabstracargumentationliteratuNielsen-Parsonsgeneralised versionwith groupattackareprobablyclosertoour own.Letus re- callthekeydefinitionoftheiframeworks. An argument isanabstracentityandtheclassofallargumentsis A..AnnaarmeennttaatffmwoorrkkiiattuupA,G)e whheeAre⊆⊆ffAA A\\∅) in and G :(2 × A. A set A1 ⊆ A is saito attacan argu- mentta ∈ A iiaannoonnliiorrsmpplliiffA(A,a) ∈ G ffosomee 0 0,a) 00 0, A 00,a) .We saythat (A ∈ G is minimalifforeveryA ⊂ A (A 6∈ G. A set A1 ⊆ A isconflict-friffthereexistno a ∈ A1 such thatA1 attacksa.A set A1 ⊆ A defendsa ∈ A iffif (A,a) ∈ G forAx ⊆ A is minimalthenA1 attacksome ax ∈ Ax. A setA1 ⊆ A accepta ∈ A iffA1 defends a.A set A1 ⊆ A is admissibiffA1 acceptsalitsmembers.A setA1 ⊆ A is apreferredset (extensioniffA1 is admissibleand thereexistno A1 ⊂ A2 ⊆ A such thatA2 is admissibleThere are othernotions such as complete sets(extensions)stable sets(extensions)and the grounded set(extension)An interestereader willfindmore infor- mation in ",
"[13,20]. 3 Argumentation Frameworks for Conflict-Eliminable Sets of Arguments Let N be the clasofnaturalnumbers including0, and leS be A×N. We refer toany element of S by swith or withouta subscriptEach of them representsan argument. Not justany setof arguments will we be interestein, however. Definition 1 (Coherent sets of arguments) Let S1 be a subset of S. We say thatS1 is coherent ifS1 satisf ithefollowing condi- tions. 1. S1 isafinitesubsetof S. 2. For any (a,n) ∈ S1,it holdsthatn > 0. 3. For any (a,n) ∈ S1, thereisno m 6= n such that(a,m) ∈ S1 . An argumentation framework usuallysatisf ithefirstconditionTo explain the second condition,we mention thateach argument has argument capacity.For(a,n) ∈ S, a is its identifand,n is itca- pacity.An argument having argument capacityof0 basicallymeans thatthe argument has no utilitThe thirdpropertyisto ensurethat each argument identityisused at mostby one argument in achosen subset of S.From hereon, by S with orwithout a subscriptwe de- note acoherent setof arguments. S Also let R beapartialfunction2 × S * N such thatit satisf ies the following conditions (or axioms). Informally R(S,s) represents the attack strength of S’s attack on s. In the below, ‘R is defined for (S,s)’ is synonymous to ‘R(S,s) is defined’. 1. R is undef ined for (∅,s) for any s ∈ S ",
"[Coherence]. 2. For any S1 ⊆ S ⊆f in S and for any s ∈ S, if R is defined for (S1 ,s), then R is defined for any (S2 ,s) for ∅ ⊂ S2 ⊆ S1 . ",
"[Quasi-closure by subset relation]. 3. For any S1 ,S2 ⊆ S ⊆f S and for any s ∈ S, if R is defined both in for (S1 ,s) and for (S2 ,s), then R is defined also for (S1 ∪S2 ,s) ",
"[Closure by set union] 4. For any S1 ⊆ S ⊆f in S and for any s ∈ S such that R is defined for (S1 ,s), it holds that R(S1 ,s) > 0 ",
"[Attack with a positive strength]. 5. For any (a,n),(a,m) ∈ S such that n ≤ m, the following holds true: if R(S1 ,s) for some s ∈ S and for some S1 ⊆f in S such that (a,n) ∈ S1 is defined, then R(S2 ,s) for S2 = (S1 \\(a,n)) ∪ (a,m) is defined and is such that R(S1 ,s) ≤ R(S2 ,s) ",
"[Attack relation monotonicity (source)]. 6. For any S1 ,S2 ⊆ S ⊆f S and for any s ∈ S, if R is defined for in (S1 ,s), (S2 ,s) and (S1 ∩ S2 ,s), then R(S1 ∩ S2 ,s) ≤ R(Si ,s) for both i = 1 and i = 2 ",
"[Attack strength monotonicity (source)]. 7. For any (a,n),(a,m) ∈ S such that n ≤ m, it holds that if R is defined for (S1 ,(a,n)) for some S1 ⊆fin S such that SSNl∈∈N S1 ∩ {(a,l)} = ∅, then it is defined for (S1 ,(a,m)), and, moreover, R(S1 ,(a,n)) ≤ R(S1 ,(a,m)) ",
"[Attack relation and strength monotonicity (target)] 8. For any S1 ⊆fin S aand for any s ∈ SS, R is undef ined for (S1 ,s) if s ∈ S1 .",
"[No self attacks]. ",
"[Coherence] ensures that an attack must come from some argu- ment(s). ",
"[Quasi-closure by subset relation] ensures that there is a group attack from a set of arguments on an argument just because each member of the set is attacking the argument. This can be con- trasted with the group attacks in Nielsen-Parsons’ argumentation frameworks. But it must be noted, as we are to mention shortly, that that there is an attack of an argument (a1 ,n1 ) on another argument (a2 ,n2 ) does not mean that (a1 ,n1 ) defeats (a2 ,n2 ) in our frame- work. ",
"[Closure by set union] is the reverse of ",
"[Quasi-closure by sub- set relation]. The purpose of ",
"[Attack with a positive strength] is as follows: we mentioned earlier that R(S1 ,s) is the strength of attack by S1 on s, measured in N. The value being positive means that S1 is indeed attacking s. The value being 0 would mean that S1 is not at- tacking s. The purpose of an attack relation in abstract argumentation frameworks is to know which arguments attack which arguments. Consequently, we only consider positive values for R. ",
"[Attack rela- tion monotonicity] expresses the following reasonable property: an attack may be occurring from some S1 ⊆ S ⊆fin S on some s ∈ S; now,increase theattackcapacityof justoneargument s1 ∈ S1 ,keep- ing all else equal; then the attack which occurred before the capacity increase should still occur. ",
"[Attack strength monotonicity] expresses the property that ifan attack occurs from a set of arguments on an ar- gument with some strength, then any superset does not decrease the attack strength. To explain ",
"[Attack relation and strength monotonic- ity], let us say that a set of arguments is attacking an argument with certain argument capacity. That intuitively means that the set intends to tone down the argument. Now, if the argument capacity of the argument increases, the set still intends to tone down the argument just as strongly or even more strongly, but not less strongly, for there are more materials in the argument that the set could attack. This is the direct reading of the condition. In the technical development to follow, the converse reading will be more useful: ifthe argument ca- pacity of the argument on the other hand decreases, the set may no longer intend to tone it down further. Finally, ",
"[No self attacks] pre- vents self-contradictory arguments from being present. Additivity of attack strengths is not postulated for R: if an ar- gument s1 is attacked by s2 and s3 such that R({s2 },s1 ) = n1 and such that R({s3 },s1 ) = n2 , it is not necessary that R({s2 ,s3 },s1 ) = n1 + n2 . The additivity holds good when each attack can be assumed independent, but may not in other cases. A generalisedversionof",
"[Attackrelationmonotonicity]holdsgood.Let π be a projection function that takes a natural number and an ordered set List and that outputs a set member, such that π(n,List) = {the nn--ttmeembbeerr ooff LLiissIItt iiss uunnddeeffiifnniisgrreeaattetthhaantthhee ssiooffe the ordered set. Proposition 1 (Generalised attack relation monotonicity) Let S1 ⊆fin S and s ∈ S be such that R(S1 ,s) is defined. Then if SSssxx SSssxx S2 ⊆fin S is such that: (1) ∈S1 π(1,sx ) = ∈S2 π(1,sx ); and that (2) (a,n) ∈ S1 materially implies (a,m) ∈ S2 for n ≤ m, then R(S2 ,s) is defined. Proof. By induction on the number of arguments s1 ∈ S1 and s2 ∈ S2 for which π(1,s1 ) = π(2,s2 ) and π(2,s1 ) < π(2,s2 ). Here and everywhere, we may make use of and (having the semantics of classical logic conjunction), distinguishing ‘and’ in formal contexts from ‘and’ in natural contexts for greater clarity. The base case is vacuous. Use ",
"[Attack relation monotonicity] for inductive cases. 2 Our argumentation framework is (S,R) for some coherent set of ar- guments S and for some R. 3.1 Attacks We distinguish complete attacks (defeats) from partial attacks (attacks). Definition 2 (Attacks and defeats) WesaythatS1 ⊆ S attackss ∈ S iff there exists S2 ⊆⊆ SS11such that R is defined for (S2 ,s). We say 5 that S1 ⊆ S defeats s ∈ S iff S1 attacks s and R(S1 ,s) ≥ π(2,s). Informally, an attack defeats its target when the attack strength surpasses the target’s argument capacity. Definition 3 (Maximum attack strengths) We define V max (S1 ,s) to be: 0 if S1 does not attack s; otherwise, R(S2 ,s) for some S2 ⊆ S1 such that: (1) R is defined for (S2 ,s); and such that (2) if R is defined for (Sx ,s) for Sx ⊆ S1 ,then R(Sx ,s) ≤ R(S2 ,s). 3.2 Conflict-eliminable sets Definition 4 (Conflict-eliminable sets of arguments) We say that S1 ⊆⊆ S iiss ccoonnffmiinnaabblleeliimiifftthheerreexxiissnoo ss ∈∈ S11 such that S1 defeats s. Conflict-eliminability is a weaker notion of the usual conflictfreeness, i.e. the property that there exists no s ∈ S1 such that S1 attacks s. For the rationale behind obtaining this definition and using it as a primitive entity in our argumentation framework, let us consider one mock example of a peer review which, just as political alliance we saw does, exhibits partial internal conflicts: 1. (Authors) We have addressed a gap in the literature about LMN in this paper. Our approach is entirely new. 5 See in the proof of Proposition 1 for what and is. 2. (A reviewer) My overall impression is that the paper contains suf- ficiently new and interesting materials to be warranted acceptance. Nonetheless, their claim that the approach considered in the paper is entirely new is misleading. There are for instance papers by XYZ et al that use a similar method to solve problems ABC. I suggest that they include the references. 3. (The handling editor) I accept the paper on the condition that the authors modify the part mentioned by the reviewer. Now, if not wholly, the reviewer is stillattacking the authors. Despite that, the decisions by the reviewer as well as by the handling editor are overall favourable ones to them. They could take the expert opinion of the reviewer into account, weaken their claim; and then their paper will be accepted. In this example, (1) that the authors have addressed some problem about LMN, (2) that a similar method was used by XYZ et al. to solve problems ABC, and (3) that the paper is accepted, are basically intrinsic arguments of the three arguments given. The authors’ contribution is not completely defeated by the reviewer, and the modif ication is a necessary compromise for the acceptance of their argument (that is, their paper). Intrinsic arguments are the arguments that result from resolving, in a conflict-eliminable set, internal non-defeating attacks. S S Definition 5 (Intrinsic arguments) Let α : 2 * 2 be such that it is defined for S1 ⊆ S iff S1 is conflict-eliminable. If α is de- fined for S1 ⊆ S, then we define that α(S1 ) = {(π(1,s),n) | s ∈ max S1 and n = π(2,s)−V (S1 ,s)}. We say that α(S1 ) are intrinsic arguments of S1 . Proposition 2 (Well-definedness) For any S1 ⊆ S, if α is defined for S1 ,then every member of α(S1 ) is a member of S: in particular, there exists no a ∈ A and no n ∈ N such that (a,−n) ∈ α(S1 ). Intrinsic arguments of a conflict-eliminable set must be substantively conflict-free. Definition 6 (The view of intrinsic arguments) Let DelR (S,Sx ) bbee{SyyS ,,ss)||ss ∈∈ SSxx and Sy ⊆⊆ SSxx and R(Sy ,,ss)iiss ddeeffiinneedd..}},, which is the set of attack relations within Sx . Now, let S1 be a subset of S. If α is defined for S1 , then we say that ((S\\S1 ) ∪ α(S1 ),R\\Del(S,S1 )) is the view that S1 has about S, or simply S1 ’s view of S. We denote S1 ’s view of S by ViewR (S,S1 ). Proposition 3 Let S1 be a subset of S. If α(S1 ) is defined, then α(S1 ) is conflict-free in ViewR (S,S1 ). 3.3 Coalition attacks, c-admissible sets and c-preferred sets A coalition may attack external arguments only by its intrinsic arguments. Definition 7 (C-attacks and c-defeats) We say that S1 ⊆⊆ S c-attacks s ∈ S iff α is defined for S1 and there exists some S2 ⊆ α(S1 ) such that π(2,ViewR (S,S1 )) is defined for (S2 ,s). We say that S1 c-defeats s ∈ S iff S1 c-attacks s and π(2,ViewR (S,S1 )))(α(S1 ),s) ≥ π(2,s). There are no self c-attacks; Cf. Proposition 3. Proposition 4 The following are equivalent. 1. S1 ⊆ S c-attacks s ∈ S. 2. S1 ⊆ S c-attacks s ∈ π(1,ViewR (S,S1 )). Also, the following are equivalent. 1. S1 ⊆ S c-defeats s ∈ S. 2. S1 ⊆ S c-defeats s ∈ π(1,ViewR (S,S1 )). Proof. By definition, π(2,ViewR (S,S1 ))(Sx ,s) is undef ined for any Sx ⊆ S1 ∪ α(S1 ) and for any s ∈ S1 ∪ α(S1 ). Hence if S1 ⊆ S c-attacks s ∈ S, then s 6∈ S1 and s 6∈ α(S1 ). Meanwhile, (S\\S1 ) = (π(1,ViewR (S,S1 ))\\α(S1 )). 2 We now def ine the notions of c-admissible and c-preferred sets, which are analogous to admissible and preferred sets we touched upon in Section 2, but which are for conflict-eliminable sets. One part in the def inition could appear diff icult at first. We italicise the part, and elaborate it later. Definition 8 (C-admissible/c-preferred sets) We say that S1 ⊆⊆ S is c-admissible iff α is defined for S1 and if S2 ⊆ π(1,ViewR (S,S1 )) attacks s ∈ S1 and if Sx ⊆ S2 is such that R(Sx ,s) is defined, then there exists some S3 ⊆ α(S1 ) such that S3 c-defeat some sx ∈ Sx . We say that S1 ⊆ S is c-preferred iff S1 is c-admissible and there exists no S1 ⊂⊂ SSyy ⊆⊆ S such haat Syy is c-admissible. We explain why in the italicised part in the above definition it is S2 ⊆ π(1,ViewR (S,S1 )) and not S2 ⊆ S; and why it is s ∈ S1 and not s ∈ α(S1 ). The notion of c-admissibility is intuitively the sameas that of admissibility in Section 2: subsets of S2 are attacking a conflict-eliminable set S1 ; and so S1 is not admissible unless some member of S1 defeat all the attacking subsets of S2 . Now, because we are presuming that S1 is conflict-eliminable and not necessarily conflict-free, S2 ⊆ S would include any partial conflict in S1 as an attack. However, c-admissibility, which is the admissibility of a conflict-eliminable set in the view of the set, should not be defined to defeat it. This explains why S2 ⊆ π(1,ViewR (S,S1 )) which compiles away all those purely internal partial conflicts. On the other hand, the reason that it should be s ∈ S1 and not s ∈ α(S1 ) is because of the asymmetry in attacks to and from a conflict-eliminable set. Recall Asymmetry in attacks to and from a coalition in Section 1. 3.4 Reduction to Nielsen-Parsons’ argumentation frameworks ↓ Theorem 1 (Restricted (S,R) as Nielsen-Parsons’) Let R be such that it satisfies all but ",
"[Quasi-closure by subset relation]. Let S be such that for any S1 ⊆⊆ S aannddffooranyy s ∈ SS, iiRf R is defined for (S1 ,s), then S1 defeats s. Then (S,R ↓) is Nielsen-Parsons’ argumentation framework, and the following all hold good. 1. Any conflict-eliminable set in S is a conflict-free set. 2. If α is defined for S1 ⊆ S, then α(S1 ) = S1 and π(1,ViewR (S,S1 )) = S. 3. A c-attack by S1 ⊆ S on s ∈ S is an attack by S1 on s. 4. A c-attack is a c-defeat. 5. A c-admissible set is an admissible set, and a c-preferred set is a preferred set. Proof. ↓ 1. Bydef inition,ifR isdefinedfor(S1 ,s),thenS1 defeatss.Hence it isnecessary that a conflict-eliminable set be a conflict-free set. 2. By 1., it is vacuous that α(S1 ) = S1 . Further, Del(S,S1 ) = ∅, and so π(1,ViewR (S,S1 )) = S. 3. By 2., both are trivial. 4. By definitionof (S,R ↓). 5. By 2.,both are trivial. With these, itis straightforward to see that (S,R ↓) is NielsenParsons’ argumentation framework. 2 4 Semantics for coalition profitability and formability Itisof interestto learnmeaningful conflict-eliminablesets ofarguments.Inthissectionweshowsemanticcharacterisationsofcoalition formabilityout of conflict-eliminablesets.Since coalition formation presupposes at leasttwo groups of arguments, what we are characterisingisnot whether a set ofarguments is admissible and how good anadmissible setover otheradmissible sets is, but whetheraconflicteliminable setcan form a coalitionwith another conflict-eliminable set,and how good a coalitionover othercoalitions is.We presume some conflict-eliminable set at fronand will talkof coalitionformabilitysemantics relativeto the conflict-eliminable set.We will first discussprof itabilitrelationof a coalition,will show itstheoretical properties,and willthen present four coalitionformability semanticseach of which formalises certain utilitypostulate(s)taking the prof itabiliintoaccount. We assume the following notations. Definition 9 (One-directional attacks) Let S1 ⊆ S be such that α(S1 ) is defined.We say that S1 is one-directionally attacked iff thereexistsSx ⊆ π(1,ViewR (S,S1 ))such thatSx attackss ∈ S1 and S1 does not c-attackany sx ∈ Sx . Definition 10 (States ofa conflict-eliminable set) Let ?: 2 S × 2S be a binary relationsuch that (S1 ,S2 ) ∈?, written also S1 ? S2 , iffα is defined both for S1 and S2 and any of the three conditions below is satisf ied: 1. S2 is c-admissible. 2. S1 is one-directionally attacked. 3. neither S1 nor S2 is c-admissible or one-directionally attacked. Informally if Sx ⊆ S is c-admissible, then it is fully defended from external attacks and is good. If Sx is one-directionally attacked, then that means that Sx does not have any answer to external attacks, which is bad. Any conflict-eliminable set that does not belong to either of them is better than being one-directionally attacked but is worse than being c-admissible. Consequently, if S1 ? S2 , then S2 is in a better state or in at least as good a state as S1 . Definition 11 (Coalition permission) We say that coalition is permitted between S1 ⊆ S and S2 ⊆ S iiff S1 ∩ S2 = ∅ and α is defined for S1 ∪ S2 . The following results tell that this definition of coalition permission isnot underspecif ied. Lemma 1 (Defeats are unresolvable) Let S1 and s be such that S1 ⊆ S and s ∈ S1 . If S1 defeats s, then for all S2 such that S1 ⊆ S2 ⊆ S it holds that S2 defeats s. Proof. By ",
"[Attack strength monotonicity] of R. 2 Proposition 5 (Coalition and conflict-eliminability) If coalition is permitted between S1 and S2 , then α is necessarily defined for S1 and S2 . Proof. Suppose otherwise, then by conflict-eliminability of a set, there must be an argument in Si ,i ∈ {1,2}, such that Si defeats s ∈ Si .The required result obtains via Lemma 1. 2 We make one notion formally explicit for convenience, and then de- fine coalition prof itability. S S Definition 12 (Attackers) Let Attacker : 2 → 2 be such that Attacker(S1 ) = {s ∈ S | there exists some s1 ∈ S1 such that s attacks s1 .}. We say that Attacker(S1 ) is the set of attackers to S1 . S S Definition 13 (Coalition profitability) Let ? : 2 ×2 be such that S1 ? S2 (or (S1 ,S2 ) ∈ ?) satisf iesthree axioms below. 1. S1 ⊆ S2 (larger set). 2. S1 ? S2 (better state). 3. |{s ∈ Attacker(S1 ) | S1 does not c-defeat s and s 6∈ S1 }| ≥ |{s ∈ Attacker(S1 ) | S2 does not c-defeat s and s 6∈ S2 }| (fewer attackers). Due to (better state), S1 ?S2 implies that α is definedboth for S1 and S2 .By (larger set), a set that contains more arguments is a better set. By (better state), a set that is in a better state is a better set. Finally, by (fewer attackers), a set that is attacked by a smaller number of arguments is a better set. The S1 in Attacker(S1 ) on the second line is not a typo: this criterion is for measuring the prof its of coalition formation for S1 . Proposition 6 A (S,R) can be chosen in such a way that a pair of S1 ⊆ S and S2 ⊆ S do not satisfy more than one axioms. Proof. (larger set) s3 s3 (a1,2) (a2,2) (a1,1) (a2,1) Let S be {(a1 ,2),(a2 ,2),s3 }, and let R be such that it is defined only for any combination that matches the attack arrows in the two drawings above. Def ine that R({(a1 ,2)},(a2 ,2)) = R({(a2 ,2)},(a1 ,2)) = R({s3 },(a1 ,2)) = R({s3 },(a1 ,1)) = R({(a2 ,2),s3 },(a1 ,2)) = 1, and that R({(a1 ,2)},s3 ) ≥ π(2,s3 ) (, among others implicit by the conditions of R). Then the left and the right drawings represent (S,R) and respectively ViewR (S,{(a1 ,2),(a2 ,2)}). Now, let S1 be {(a1 ,2)} and let S2 be {(a1 ,2),(a2 ,2)}. Then clearly S1 ⊆ S2 . However, it does not satisfy (better state): S1 is neither c-admissible nor onedirectionally attacked but S2 is one-directionally attacked. It does not satisfy (fewer attackers), either: Attacker(S1 )) = {{ss3}},S11 cdefeats s3 ,and S2 c-defeats none. (better state) s1 s2 s3 Let S be {s1 ,s2 ,s3 }, and let R be such that it is defined only mutually for s1 and s2 as shown above, and such that R({s1 },s2 ) ≥ π(2,s2 ) and R({s2 },s1 ) ≥ π(2,s1 ). Now, let S1 be {s1 } and let S2 be {s3 }. Then S1 ? S2 because S2 is c-admissible. However, clearly it is not the case that S1 ⊆ S2 .Also, Attacker(S1 ) = {s2 }, S1 c-defeats s2 , but S2 does not c-defeat it. (fewer attackers) Let S be {s1 ,s2 ,s3 }, and let R be such that it is defined as is previously, and such that R({s1 },s2 ) < π(2,s2 ) aanndR(({{ss2}},,s)11< π(2,s1 ). Now, let S1 bbee {{ss3aanndlleeS2 be {s2 }.ThenAttacker(S1 ) = ∅,andso(fewerattackers)issatisf ied trivially.However, clearly it is not the case that S1 ⊆ S2 . And it is not the case that S1 ? S2 ,because S1 is c-admissible, while S2 is neither c-admissible nor one-directionally attacked. 2 4.1 Theoretical results around profitability It is triviato show that there exists some (S,R) and some S1 ,S2 ⊆ S such that S1 ? S1 ∪ S2 .We show other results. Theorem 2 (Profitable coalition for subsets of a c-admissible set) Let S1 ⊆ S be such that α(S1 ) is defined, and let Sx ⊆ S be a c-admissible set.If S1 ⊂ Sx , then the following all hold good. 1. α is defined for S2 = Sx \\S1 . 2. Coalition is permitted between S1 and S2 . 3. S1 ? Sx . Proof. 1. Suppose otherwise, then S2 would defeat at least one s ∈ S2 suchthat S2 woulddefeat s.Bylemma 1, Sx wouldthendefeat s, for S2 ⊆ Sx . But Sx ,being c-admissible, does not defeat s. 2. α is defined for Sx by definition; and S1 ∩∩ SS22= ∅∅,aso by def-nition. 3. S1 ⊆ Sx ; Sx is a c-admissible set; and |{s ∈ AAttacker(S1 ) | Sx does not c-defeat s and s 6∈ Sx }| = 0. 2 Theorem 3 (Existence theorem) If,for any S1 ⊆ S, there exists some S2 ⊆⊆ S su hh that coalion is perm ted between S11 and S2 and S1 ? S1 ∪ S2 and S1 ∪ S2 is c-admissible, then there exists some S3 ⊆ S such that coalition is permitted between S1 and S3 and S1 ? S1 ∪ S3 and S1 ∪ S3 is c-preferred and S2 ⊆ S3 . Proof. As S is of a finite size, it is straightforward to see that if S1 ∪ S2 is c-admissible, then there must exist some Sx such that it is c-preferred and that S1 ∪ S2 ⊆ Sx . We show that the choice of Sx \\S1 for S3 ensures the requirement to be satisf ied. By Theorem 2 coalition is permitted between S1 and S3 and S1 ? S1 ∪ S3 . By assumption, S1 ∪ S3 = Sx is c-preferred and S2 ⊆ S3 . 2 Theorem 4 (A c-preferred set as a mutually maximal coalition) Let S1 ⊆ S be such that α(S1 ) is defined, and let Pref(S1 ) be the set of all c-preferred sets that contain S1 as their sub- set. If Pref(S1 ) 6= ∅, then the following holds good: for any Sx ∈ Pref(S1 ), S1 ? Sx and (Sx \\S1 ) ? Sx and there exists no Sx ⊂ Sy ⊆ S such that S1 ? Sy or such that (Sx \\S1 ) ? Sy . Proof. By Theorem 2 and by definition of a set being c-preferrable. 2In general, though, mutual prof itability is not guaranteed. Theorem 5 (Asymmetry of profitabilities) There exists an argu- mentation framework (S,R) such that there are disjoint subsets: S1 and S2 ,of S such that S1 ? S1 ∪ S2 , but such that it is not the case that S2 ? S1 ∪ S2 . Proof. s3 s1 s3 s1 (a2,2) s4 (a2,1) s4 s5 s5 Let S be {s1 ,(a2 ,2),s3 ,s4 ,s5 }, and let R be such that it is defined only for any combination that matches the attack arrows in the drawings above, and such that: R({s1 },(a2 ,2)) = 1; R({s1 ,(a2 ,1)},s3 ) ≥ π(2,s3 ); R({s1 },s3 ) < π(2,s3 ); R({(a2 ,2)},s3 ) < π(2,s3 ); R({(a2 ,1)},s4 ) < π(2,s4 ); R({(a2 ,1)},s5 ) < π(2,s5 ); R({(a2 ,2)},s4 ) ≥ π(2,s4 ); R({(a2 ,2)},s5 ) ≥ π(2,s5 ); R({s3 },s1 ) ≥ 2; R({s4 },(a2 ,1)) ≥ 2; and R({s5 },(a2 ,1)) ≥ 2, among others. Now, let S1 be {s1 }, and let S2 be {(a2 ,2)}. Then S1 ? S1 ∪ S2 , for S1 and S1 ∪ S2 are both neither c-admissible nor one-directionally attacked. The axiom (fewer attackers) is also satisf ied. However, it is not the case that S2 ? S1 ∪ S2 , for it does not satisfy (fewer attackers). 2 Moreover, ? does not satisfy what we may at first expect hold good. Definition 14 (Continuation property of ?) Let S1 ⊆ S be such that α(S1 ) is defined, and let Max(S1 ) be the set of all Sx ⊆ S such that S1 ? Sx and such that if Sx ⊂ Sy ⊆ S, then it is not the case that S1 ? Sy . Then we say that ? is weakly continuous for S1 iff there exists some Sz ∈ Max(S1 ) such that, for any Sw ⊆ Sz , if coalition is permitted between S1 and Sw \\S1 , then S1 ?Sw .We say that ? is continuous for S1 iff it is weakly continuous for S1 for any Sz ∈ Max(S1 ). Theorem 6 (Coalition profitability discontinuation theorem) There exist S1 ,S2 ,Sx ⊆ S such that: (1) α is defined for S1 ,S2 and Sx ; (2) Sx ∈ Max(S1 ); and (3) S2 ⊆ Sx ,but such that S1 ? S2 does not hold good. Moreover, Max(S1 ) = Pref(S1 ) would not change this result. Proof. It suffices to consider the case where Max(S1 ) = Pref(S1 ). s3 s3 s5 s5 s4 s4 (a1, 2) (a2,2) (a1,1) (a2,1) Let S be {(a1 ,2),(a2 ,2),s3 ,s4 ,s5 }, and let R be such that it is defined only for any combination that matches the attack arrows in the drawings above, and such that: R({(a1 ,2)},s4 ) ≥ π(2,s4 ); R({(a2 ,2)},s5 ) ≥ π(2,s5 ); R({(a1 ,2)},(a2 ,2)) = 1; R({(a2 ,2)},(a1 ,2)) = 1; R({s3 },s4 ) ≥ π(2,s4 ); R({(a2 ,1),s3 },s5 ) ≥ π(2,s5 ); R({s4 },(a1 ,1)) ≥ 2; and R({s5 },(a2 ,1)) ≥ 2, among oth- ers. Clearly α is defined for S1 = {(a1 ,2)}, Sa = {(a2 ,2)} S2 = S1 ∪ Sa , and Sx = {(a1 ,2),(a2 ,2),s3 }, among others. Further, Sx is c-preferrable. However, it is not the case that S1 ? S2 . In fact, it is also not the case that Sa ? S2 , since S2 is one-directionally attacked (see the right drawing for the attacks in ViewR (S,{(a1 ,2),(a2 ,2)})), whereas S1 and Sa are neither c-admissible nor one-directionally attacked (see the left drawing). 2 Coalition prof itability continuation property satisf ies in certain special cases, however. Theorem 7 (Coalition profitability continuation theorem) Let Sx ⊆ S be a c-preferred set. Then ? is weakly continuous for any S1 ⊂ Sx iff any disjoint pair Sy ,Sz of subsets of Sx satisfy Sy ? Sy ∪ Sz . Proof. If: Suppose, by way of showing contradiction, there are three disjoint subsets of Sx : Sa ,Sb and Sc , such that Sa ? Sa ∪ Sb 6?(Sa ∪ Sb ) ∪ Sc .By assumption we have (Sa ∪ Sb ) ? (Sa ∪ Sb ) ∪ Sc ,contradiction. Only if: By definition of weak continuation property of ?. 2 4.2 Coalition formability semantics We use the prof itability relation to express our coalition formability semantics. We set forth three rational utility postulates: I Coalition is good when it is prof itable at least to one party. II Coalition is good when it is prof itable to both parties. III Coalition is good when maximal potential future prof its are expected from it. Of these, the first two can be understood immediately with the prof itability relation. Our interpretation for the last postulate is as follows. Suppose a party, some conflict-eliminable set S1 ⊆⊆ SS in our context, considers coalitionformation with another conflict- eliminable setS2 .We know thatS2 issome subset of S1 ⊆ S\\S1 . Before S1 forms a coalition with S2 , we have Max(S1 ) as the set of maximal coalitionspossible for S1. Once the coalition is formed, we have Max(S1 ∪ S2 )as theset ofmaximal coalitionspossible for the coalition. Here clearly Max(S1 ∪ S2 ) ⊆ Max(S1 ). What this means is thata particular choice of S2 blocks any possibilitiesin Max(S1 )MaxSS1 ∪∪ SS22 they become unrealisable from S1 ∪∪ SS.2 Hence S1 has an incentive not to form a coalition with such a S2 if all the members of Max(S1 ∪S2 ) are strictland comparatively less prof itablethan some member of Max(S1 ). We reflectthisintuition. Definition 15 (Maximal profitabilityrelation) Let ≤ll≤bb ≤ff : 2 S × 2 S be such thatthey satisfyall thefollowing: 1. S1 ≤l S2 iff|S1 | ≤|S2 |. 2. S1 ≤b S2 iffS2 is at leasas good by (better state)asS1 . 3. S1 ≤f S2 iffS2 is atleastas good by (fewer attackers)as S1 . We writeS1 <β S2 for each β ∈ {l,b,f} justwhen it is thecase that S1 ≤ββ S2 and it is not thcase that S2 ≤ββ S1 .Then we deine ?m :2S ×2 S to be such thatifS1 ?m S2 ,then both of thefollowing conditions satisfy: 1. S1 ? S2 . 2. Some Sx ∈ Max(S2 ) is such that, for all Sy ∈ Max(S1 ), if Sx <β Sy for some β ∈ {l,b,f}, then there exists γ ∈ ({l,b,f}\\β) such that Sy <γ Sx . Intuitively,ifS1 ?m S2 ,then at leasone set iMax(S1 ) maximal in the three criteriathe setsize,the statequality and the number of ex- ternal attackers,is reachablefrom S2.The maximality here is judged by the principle that if S2 ,S3 ∈ Max(S1 ) are equal by two criteria, then S3 is better ifit is better than S2 by the remaining criterion. We define four formability semantics: W which respects I, M which respects II (and implicitly also I), WS which respects I and III, and S which respects II and III. Definition 16 (Coalition formability semantics) W(S1 ) = {S2 ⊆ S | S1 ? S1 ∪ S2 or S2 ? S1 ∪ S2 }. M(S1 ) = {S2 ⊆ S | S1 ? S1 ∪ S2 and S2 ? S1 ∪ S2 }. WS(S1 ) = {S2 ⊆ S | S1 ?m S1 ∪ S2 or S2 ?m S1 ∪ S2 }. S(S1 ) = {S2 ⊆ S | S1 ?m S1 ∪ S2 and S2 ?m S1 ∪ S2 }. Here, or has the semantics of classical logic disjunction. Intuitively, ρ(S1 ) for ρ ∈ {W,M,WS,S} means that S1 is comfortable with forming a coalition with S2 ∈ ρ(S1 ) under the given criteria. Theorem 8 (The relation among coalition formability semantics) Let S1 ⊆ S be such that α(S1 ) is defined. The following all hold good. (1) M(S1 ) ⊆ W(S1 ). (2) WS(S1 ) ⊆ W(S1 ). (3) S(S1 ) ⊆ M(S1 ). (4) S(S1 ) ⊆ WS(S1 ). Meanwhile, neither WS(S1 ) ⊆ M(S1 ) nor M(S1 ) ⊆ WS(S1 ) is necessary. We provide one example to illustrate the semantic differences. (a3, 2) s1 (a3, 2) s1 (a3, 1) s1 s4 s4 s4 (a2, 2) (a2, 1) (a2, 2) s5 s5 s5 s6 s6 s6 s7 s7 s7 Let S = {{ss11,(a2 ,2),(a3 ,2),s4 ,s5 ,s6 }},, aanndd lleett R bbee ssuucchh that it is defined only for any combination that matches the attack arrows in the above drawings, and such that: RR(({{((aa22 ,,22))}},,((aa33,2)) = 1; RR(({{((aa22 ,,22))}},,ss44 )) ≥≥ ππ((22,,ss44 ); RR(({{((aa22 ,,22))}},,ss55)) ≥≥ ππ((22,,ss55 ); RR(({{((aa22 ,1),s1 }},,((aa33,,22)))) ≥≥ 22;; RR(({{((aa22 ,,11))}},,ss44) < π(2,s4 ); RR(({{((aa22 ,,11))}},,ss55 ) < π(2,s5 ); RR(({{ss11 }},,((aa33,2)) = 1; RR(({{((aa33 ,,11))}},,ss11 )) ≥≥ ππ((22,,ss11 ); RR(({{((aa33 ,,11))}},,ss66)) ≥≥ ππ((22,,ss66 ); RR(({{ss66 }},,((aa33,1)) = 2; R({s6 },s7 ) ≥ π(2,s7 ); R({s7 },s6 ) ≥ π(2,s6 ); RR(({{ss77 }},,ss55)) ≥≥ ππ((22,,ss55 ); RR(({{ss77 }},,ss44 )) ≥≥ ππ((22,,ss44 ); RR(({{ss44 }},,ss77) < π(2,s7 ); RR(({{ss44 }},,((aa22,1)) = 2; RR(({{ss55 }},,((aa22,1)) = 2; RR(({{ss55 }},,ss77 ) < π(2,s7 ); RR(({{ss44 ,s5 }},,ss77)) ≥≥ ππ((22,,ss77 ), among others that are implicit by the conditions of R. The left drawing, the middle drawing, and the right drawing represent (S,R), ViewR ((SS,,{{ss11 ,(a2 ,,22))}})),, and respectively ViewR (S,{(a2 ,2),(a3 ,2)}). We have: W({(a2 ,2)}) = {{(a3 ,2)},{s1 },{s6 },{s7 },{s1 ,s6 },{s1 ,s7 }, {(a3 ,2),s7 }}. M({(a2 ,2)}) = {{(a3 ,2)},{s7 },{s1 ,s6 },{s1 ,s7 },{(a3 ,2),s7 }}. WS({(a2 ,2)}) = {{(a3 ,2)},{s1 },{s7 },{s1 ,s7 },{(a3 ,2),s7 }}. S({(a2 ,2)}) = WS({(a2 ,2)}). The first two equalities can be checked one by one. For WS({(a2 ,2)}), we note that {s1 ,s6 } is excluded because: (1) for {(a2 ,2)}, {(a2 ,2),(a3 ,2),s7 } and {s1 ,(a2 ,2),s7 } are both strictly better in ?m than {s1 ,(a2 ,2),s6 }; and (2) for {s1 ,s6 }, {s1 ,s6 ,s4 ,s5 } is strictly better in ?m than {s1 ,(a2 ,2),s6 }. Similarlyl {s6 } is excluded. Finally, in this particular example, both {s1 ,(a2 ,2),s7 } and {(a2 ,2),(a3 ,2),s7 } are c-preferred, and, moreover, we have: {(a3 ,2)} ?m {(a2 ,2),(a3 ,2),s7 }; {s1 } ?m {s1 ,(a2 ,2),s7 }; {s7 } ?m {s1 ,(a2 ,2)s7 }; and {s7 } ?m {(a2 ,2),(a3 ,2),s7 }. By these, together with the subsumption of S({(a2 ,2)}) in WS({(a2 ,2)}) (Theorem 8), the last equality for S({(a2 ,2)}) follows. 5 Conclusion We proposed abstract-argumentation-theoretic coalition prof itability and formability semantics for conflict-eliminable sets. Further, we showed theoretical results around the semantics. We also showed how our framework can be reduced to Nielsen-Parsons’ argumen- tation framework. Our work has a connection to several important subf ields of abstract argumentation theory such as postulate-based abstract argumentation, attack-tolerant abstract argumentation and dynamic abstract argumentation. It is our hope that this study will further aid in linking the rich knowledge that is being accumulated in the literature. REFERENCES ",
"[1] Leila Amgoud, ‘An argumentation-based model for reasoning about coalition structures’, in Argumentation in Multi-Agent Systems, pp. 217–228, (2005). ",
"[2] Leila Amgoud and Philippe Besnard, ‘Bridging the Gap between Abstract Argumentation Systems and Logic’, in SUM, pp. 12–27, (2009). ",
"[3] Ofer Arieli, ‘Conflict-Tolerant Semantics for Argumentation Frameworks’, in JELIA, pp. 28–40, (2012). ",
"[4] Ringo Baumann and Gerhard Brewka, ‘AGM Meets Abstract Argumentation: Expansion and Revision for Dung Frameworks’, in IJCAI, pp. 2734–2740, (2015). ",
"[5] Guido Boella, Souhila Kaci, and Leendert van der Torre, ‘Dynamics in Argumentation with Single Extensions: Abstraction Principles and the Grounded Extension’, in ECSQARU, pp. 107–118, (2009). ",
"[6] Guido Boella, Souhila Kaci, and Leendert van der Torre, ‘Dynamics in Argumentation with Single Extensions: Attack Refinement and the Grounded Extension’, in AAMAS, pp. 1213–1214. :, (2009). ",
"[7] Guido Boella, Leendert van der Torre, and Serena Villata, ‘Social Viewpoints for Arguing about Coalitions’, in PRIMA, pp. 66–77, (2008). ",
"[8] Nils Bulling, Jurgen Dix, and Carlos I. Ches ˜evar, ‘Modelling Coalitions: ATL + Argumentation’, in AAMAS, pp. 681–688, (2008). ",
"[9] Martin Caminada and Leila Amgoud, ‘An Axiomatic Account of Formal Argumentation’, in AAAI, pp. 608–613, (2005). ",
"[10] Claudette Cayrol, Florence Dupin de Saint-Cyr, and Marie-Christine Lagasquie-Schiex, ‘Change in Abstract Argumentation Frameworks: Adding an Argument’, Journal of Artificial Intelligence Research, 38, 49–84, (2010). ",
"[11] Sylvie Coste-Marquis and S ebastien Konieczny, ‘A Translation-Based Approach for Revision of Argumentation Frameworks’, in JELIA, pp. 397–411, (2014). ",
"[12] Sylvie Coste-Marquis, S´ebastien Konieczny, Jean-Guy Mailly, and Pierre Marquis, ‘On the Revision of Argumentation Systems: Minimal Change of arguments Statuses’, in KR, (2014). ",
"[13] Phan M. Dung, ‘On the Acceptability of Arguments and Its Fundamental Role in Nonmonotonic Reasoning, Logic Programming, and nPerson Games’, Artificial Intelligence, 77(2), 321–357, (1995). ",
"[14] Phan M. Dung, ‘Assumption-based argumentation’, in Argumentation in AI, pp. 25–44. Springer, (2009). ",
"[15] Paul E. Dunne, Anthony Hunter, Peter McBurney, Simon Parsons, and Michael Wooldridge, ‘Weighted argument systems: Basic definitions, algorithms, and complexity results’, Artificial Intelligence, 175(2), 457–486, (2011). ",
"[16] Dov M. Gabbay and Odinaldo Rodrigues, ‘An equational approach to the merging of argumentation networks’, Journal of Logic and Computation, 24(6), 1253–1277, (2014). ",
"[17] Nikos Gorogiannis and Anthony Hunter, ‘Instantiating abstract argumentation with classical logic arguments: Postulates and properties’, Artificial Intelligence, 175(9-10), 1479–1497, (2011). ",
"[18] Jo ao Leite and Jo ao Martins, ‘Social Abstract Argumentation’, in IJCAI, pp. 2287–2292, (2011). ",
"[19] Hengfei Li, Nir Oren, and Timothy J. Norman, ‘Probabilistic Argumentation Frameworks’, in TAFA, pp. 1–16, (2012). ",
"[20] Søren Holbech Nielsen and Simon Parsons, ‘A generalization ofDung’s Abstract Framework for Argumentation’ , in Argumentation in MultiAgent Systems, pp. 54–73, (2006). ",
"[21] Luke Riley, Katie Atkinson, and Terry Payne, ‘A Dialogue Game for Coalition Structure Generation with Self-Interested Agents’, in COMMA, pp. 229–236, (2012). ",
"[22] Nicol as Rotstein, Mart ın O. Moguillansky, Alejandro J. Garc ´ıa, and Guillermo R. Simari, ‘An abstract Argumentation Framework for Han- dling Dynamics’, in Proceedings of the Argument, Dialogue and Decision Workshop in NMR 2008, pp. 131–139, (2008)."
]
}
following lines are unnecessary:
"references": [
"] I taking the coalition prof itability into account. A . 1 Introduction s c Coalition formation among agents is an important topic in many ",
"[ domains including economics, political science, and computer sci- 1 ence. Two groups of agents, by teaming up together, could achieve v a task which they cannot on their own. Exploring abstract argumen- 5 tation theory for finding an apt characterisation of coalition forma- 9 bility looks specially rewarding, and there are already a few papers 4 in the literature looking at this subject matter: with preference-based 0 argumentation frameworks and task allocations [1]; with a coopera- 0 tive goal generation and fulf illing ",
...
"[Coherence]. 2. For any S1 ⊆ S ⊆f in S and for any s ∈ S, if R is defined for (S1 ,s), then R is defined for any (S2 ,s) for ∅ ⊂ S2 ⊆ S1 . ",
"[Quasi-closure by subset relation]. 3. For any S1 ,S2 ⊆ S ⊆f S and for any s ∈ S, if R is defined both in for (S1 ,s) and for (S2 ,s), then R is defined also for (S1 ∪S2 ,s) ",
"[Closure by set union] 4. For any S1 ⊆ S ⊆f in S and for any s ∈ S such that R is defined for (S1 ,s), it holds that R(S1 ,s) > 0 ",
"[Attack with a positive strength]. 5. For any (a,n),(a,m) ∈ S such that n ≤ m, the following holds true: if R(S1 ,s) for some s ∈ S and for some S1 ⊆f in S such that (a,n) ∈ S1 is defined, then R(S2 ,s) for S2 = (S1 \\(a,n)) ∪ (a,m) is defined and is such that R(S1 ,s) ≤ R(S2 ,s) ",
"[Attack relation monotonicity (source)]. 6. For any S1 ,S2 ⊆ S ⊆f S and for any s ∈ S, if R is defined for in (S1 ,s), (S2 ,s) and (S1 ∩ S2 ,s), then R(S1 ∩ S2 ,s) ≤ R(Si ,s) for both i = 1 and i = 2 ",
"[Attack strength monotonicity (source)]. 7. For any (a,n),(a,m) ∈ S such that n ≤ m, it holds that if R is defined for (S1 ,(a,n)) for some S1 ⊆fin S such that SSNl∈∈N S1 ∩ {(a,l)} = ∅, then it is defined for (S1 ,(a,m)), and, moreover, R(S1 ,(a,n)) ≤ R(S1 ,(a,m)) ",
"[Attack relation and strength monotonicity (target)] 8. For any S1 ⊆fin S aand for any s ∈ SS, R is undef ined for (S1 ,s) if s ∈ S1 .",
"[No self attacks]. ",
"[Coherence] ensures that an attack must come from some argu- ment(s). ",
"[Quasi-closure by subset relation] ensures that there is a group attack from a set of arguments on an argument just because each member of the set is attacking the argument. This can be con- trasted with the group attacks in Nielsen-Parsons’ argumentation frameworks. But it must be noted, as we are to mention shortly, that that there is an attack of an argument (a1 ,n1 ) on another argument (a2 ,n2 ) does not mean that (a1 ,n1 ) defeats (a2 ,n2 ) in our frame- work. ",
"[Closure by set union] is the reverse of ",
"[Quasi-closure by sub- set relation]. The purpose of ",
"[Attack with a positive strength] is as follows: we mentioned earlier that R(S1 ,s) is the strength of attack by S1 on s, measured in N. The value being positive means that S1 is indeed attacking s. The value being 0 would mean that S1 is not at- tacking s. The purpose of an attack relation in abstract argumentation frameworks is to know which arguments attack which arguments. Consequently, we only consider positive values for R. ",
"[Attack rela- tion monotonicity] expresses the following reasonable property: an attack may be occurring from some S1 ⊆ S ⊆fin S on some s ∈ S; now,increase theattackcapacityof justoneargument s1 ∈ S1 ,keep- ing all else equal; then the attack which occurred before the capacity increase should still occur. ",
"[Attack strength monotonicity] expresses the property that ifan attack occurs from a set of arguments on an ar- gument with some strength, then any superset does not decrease the attack strength. To explain ",
"[Attack relation and strength monotonic- ity], let us say that a set of arguments is attacking an argument with certain argument capacity. That intuitively means that the set intends to tone down the argument. Now, if the argument capacity of the argument increases, the set still intends to tone down the argument just as strongly or even more strongly, but not less strongly, for there are more materials in the argument that the set could attack. This is the direct reading of the condition. In the technical development to follow, the converse reading will be more useful: ifthe argument ca- pacity of the argument on the other hand decreases, the set may no longer intend to tone it down further. Finally, ",
"[No self attacks] pre- vents self-contradictory arguments from being present. Additivity of attack strengths is not postulated for R: if an ar- gument s1 is attacked by s2 and s3 such that R({s2 },s1 ) = n1 and such that R({s3 },s1 ) = n2 , it is not necessary that R({s2 ,s3 },s1 ) = n1 + n2 . The additivity holds good when each attack can be assumed independent, but may not in other cases. A generalisedversionof",
"[Attackrelationmonotonicity]holdsgood.Let π be a projection function that takes a natural number and an ordered set List and that outputs a set member, such that π(n,List) = {the nn--ttmeembbeerr ooff LLiissIItt iiss uunnddeeffiifnniisgrreeaattetthhaantthhee ssiooffe the ordered set. Proposition 1 (Generalised attack relation monotonicity) Let S1 ⊆fin S and s ∈ S be such that R(S1 ,s) is defined. Then if SSssxx SSssxx S2 ⊆fin S is such that: (1) ∈S1 π(1,sx ) = ∈S2 π(1,sx ); and that (2) (a,n) ∈ S1 materially implies (a,m) ∈ S2 for n ≤ m, then R(S2 ,s) is defined. Proof. By induction on the number of arguments s1 ∈ S1 and s2 ∈ S2 for which π(1,s1 ) = π(2,s2 ) and π(2,s1 ) < π(2,s2 ). Here and everywhere, we may make use of and (having the semantics of classical logic conjunction), distinguishing ‘and’ in formal contexts from ‘and’ in natural contexts for greater clarity. The base case is vacuous. Use ",
"[Attack relation monotonicity] for inductive cases. 2 Our argumentation framework is (S,R) for some coherent set of ar- guments S and for some R. 3.1 Attacks We distinguish complete attacks (defeats) from partial attacks (attacks). Definition 2 (Attacks and defeats) WesaythatS1 ⊆ S attackss ∈ S iff there exists S2 ⊆⊆ SS11such that R is defined for (S2 ,s). We say 5 that S1 ⊆ S defeats s ∈ S iff S1 attacks s and R(S1 ,s) ≥ π(2,s). Informally, an attack defeats its target when the attack strength surpasses the target’s argument capacity. Definition 3 (Maximum attack strengths) We define V max (S1 ,s) to be: 0 if S1 does not attack s; otherwise, R(S2 ,s) for some S2 ⊆ S1 such that: (1) R is defined for (S2 ,s); and such that (2) if R is defined for (Sx ,s) for Sx ⊆ S1 ,then R(Sx ,s) ≤ R(S2 ,s). 3.2 Conflict-eliminable sets Definition 4 (Conflict-eliminable sets of arguments) We say that S1 ⊆⊆ S iiss ccoonnffmiinnaabblleeliimiifftthheerreexxiissnoo ss ∈∈ S11 such that S1 defeats s. Conflict-eliminability is a weaker notion of the usual conflictfreeness, i.e. the property that there exists no s ∈ S1 such that S1 attacks s. For the rationale behind obtaining this definition and using it as a primitive entity in our argumentation framework, let us consider one mock example of a peer review which, just as political alliance we saw does, exhibits partial internal conflicts: 1. (Authors) We have addressed a gap in the literature about LMN in this paper. Our approach is entirely new. 5 See in the proof of Proposition 1 for what and is. 2. (A reviewer) My overall impression is that the paper contains suf- ficiently new and interesting materials to be warranted acceptance. Nonetheless, their claim that the approach considered in the paper is entirely new is misleading. There are for instance papers by XYZ et al that use a similar method to solve problems ABC. I suggest that they include the references. 3. (The handling editor) I accept the paper on the condition that the authors modify the part mentioned by the reviewer. Now, if not wholly, the reviewer is stillattacking the authors. Despite that, the decisions by the reviewer as well as by the handling editor are overall favourable ones to them. They could take the expert opinion of the reviewer into account, weaken their claim; and then their paper will be accepted. In this example, (1) that the authors have addressed some problem about LMN, (2) that a similar method was used by XYZ et al. to solve problems ABC, and (3) that the paper is accepted, are basically intrinsic arguments of the three arguments given. The authors’ contribution is not completely defeated by the reviewer, and the modif ication is a necessary compromise for the acceptance of their argument (that is, their paper). Intrinsic arguments are the arguments that result from resolving, in a conflict-eliminable set, internal non-defeating attacks. S S Definition 5 (Intrinsic arguments) Let α : 2 * 2 be such that it is defined for S1 ⊆ S iff S1 is conflict-eliminable. If α is de- fined for S1 ⊆ S, then we define that α(S1 ) = {(π(1,s),n) | s ∈ max S1 and n = π(2,s)−V (S1 ,s)}. We say that α(S1 ) are intrinsic arguments of S1 . Proposition 2 (Well-definedness) For any S1 ⊆ S, if α is defined for S1 ,then every member of α(S1 ) is a member of S: in particular, there exists no a ∈ A and no n ∈ N such that (a,−n) ∈ α(S1 ). Intrinsic arguments of a conflict-eliminable set must be substantively conflict-free. Definition 6 (The view of intrinsic arguments) Let DelR (S,Sx ) bbee{SyyS ,,ss)||ss ∈∈ SSxx and Sy ⊆⊆ SSxx and R(Sy ,,ss)iiss ddeeffiinneedd..}},, which is the set of attack relations within Sx . Now, let S1 be a subset of S. If α is defined for S1 , then we say that ((S\\S1 ) ∪ α(S1 ),R\\Del(S,S1 )) is the view that S1 has about S, or simply S1 ’s view of S. We denote S1 ’s view of S by ViewR (S,S1 ). Proposition 3 Let S1 be a subset of S. If α(S1 ) is defined, then α(S1 ) is conflict-free in ViewR (S,S1 ). 3.3 Coalition attacks, c-admissible sets and c-preferred sets A coalition may attack external arguments only by its intrinsic arguments. Definition 7 (C-attacks and c-defeats) We say that S1 ⊆⊆ S c-attacks s ∈ S iff α is defined for S1 and there exists some S2 ⊆ α(S1 ) such that π(2,ViewR (S,S1 )) is defined for (S2 ,s). We say that S1 c-defeats s ∈ S iff S1 c-attacks s and π(2,ViewR (S,S1 )))(α(S1 ),s) ≥ π(2,s). There are no self c-attacks; Cf. Proposition 3. Proposition 4 The following are equivalent. 1. S1 ⊆ S c-attacks s ∈ S. 2. S1 ⊆ S c-attacks s ∈ π(1,ViewR (S,S1 )). Also, the following are equivalent. 1. S1 ⊆ S c-defeats s ∈ S. 2. S1 ⊆ S c-defeats s ∈ π(1,ViewR (S,S1 )). Proof. By definition, π(2,ViewR (S,S1 ))(Sx ,s) is undef ined for any Sx ⊆ S1 ∪ α(S1 ) and for any s ∈ S1 ∪ α(S1 ). Hence if S1 ⊆ S c-attacks s ∈ S, then s 6∈ S1 and s 6∈ α(S1 ). Meanwhile, (S\\S1 ) = (π(1,ViewR (S,S1 ))\\α(S1 )). 2 We now def ine the notions of c-admissible and c-preferred sets, which are analogous to admissible and preferred sets we touched upon in Section 2, but which are for conflict-eliminable sets. One part in the def inition could appear diff icult at first. We italicise the part, and elaborate it later. Definition 8 (C-admissible/c-preferred sets) We say that S1 ⊆⊆ S is c-admissible iff α is defined for S1 and if S2 ⊆ π(1,ViewR (S,S1 )) attacks s ∈ S1 and if Sx ⊆ S2 is such that R(Sx ,s) is defined, then there exists some S3 ⊆ α(S1 ) such that S3 c-defeat some sx ∈ Sx . We say that S1 ⊆ S is c-preferred iff S1 is c-admissible and there exists no S1 ⊂⊂ SSyy ⊆⊆ S such haat Syy is c-admissible. We explain why in the italicised part in the above definition it is S2 ⊆ π(1,ViewR (S,S1 )) and not S2 ⊆ S; and why it is s ∈ S1 and not s ∈ α(S1 ). The notion of c-admissibility is intuitively the sameas that of admissibility in Section 2: subsets of S2 are attacking a conflict-eliminable set S1 ; and so S1 is not admissible unless some member of S1 defeat all the attacking subsets of S2 . Now, because we are presuming that S1 is conflict-eliminable and not necessarily conflict-free, S2 ⊆ S would include any partial conflict in S1 as an attack. However, c-admissibility, which is the admissibility of a conflict-eliminable set in the view of the set, should not be defined to defeat it. This explains why S2 ⊆ π(1,ViewR (S,S1 )) which compiles away all those purely internal partial conflicts. On the other hand, the reason that it should be s ∈ S1 and not s ∈ α(S1 ) is because of the asymmetry in attacks to and from a conflict-eliminable set. Recall Asymmetry in attacks to and from a coalition in Section 1. 3.4 Reduction to Nielsen-Parsons’ argumentation frameworks ↓ Theorem 1 (Restricted (S,R) as Nielsen-Parsons’) Let R be such that it satisfies all but ",
"[Quasi-closure by subset relation]. Let S be such that for any S1 ⊆⊆ S aannddffooranyy s ∈ SS, iiRf R is defined for (S1 ,s), then S1 defeats s. Then (S,R ↓) is Nielsen-Parsons’ argumentation framework, and the following all hold good. 1. Any conflict-eliminable set in S is a conflict-free set. 2. If α is defined for S1 ⊆ S, then α(S1 ) = S1 and π(1,ViewR (S,S1 )) = S. 3. A c-attack by S1 ⊆ S on s ∈ S is an attack by S1 on s. 4. A c-attack is a c-defeat. 5. A c-admissible set is an admissible set, and a c-preferred set is a preferred set. Proof. ↓ 1. Bydef inition,ifR isdefinedfor(S1 ,s),thenS1 defeatss.Hence it isnecessary that a conflict-eliminable set be a conflict-free set. 2. By 1., it is vacuous that α(S1 ) = S1 . Further, Del(S,S1 ) = ∅, and so π(1,ViewR (S,S1 )) = S. 3. By 2., both are trivial. 4. By definitionof (S,R ↓). 5. By 2.,both are trivial. With these, itis straightforward to see that (S,R ↓) is NielsenParsons’ argumentation framework. 2 4 Semantics for coalition profitability and formability Itisof interestto learnmeaningful conflict-eliminablesets ofarguments.Inthissectionweshowsemanticcharacterisationsofcoalition formabilityout of conflict-eliminablesets.Since coalition formation presupposes at leasttwo groups of arguments, what we are characterisingisnot whether a set ofarguments is admissible and how good anadmissible setover otheradmissible sets is, but whetheraconflicteliminable setcan form a coalitionwith another conflict-eliminable set,and how good a coalitionover othercoalitions is.We presume some conflict-eliminable set at fronand will talkof coalitionformabilitysemantics relativeto the conflict-eliminable set.We will first discussprof itabilitrelationof a coalition,will show itstheoretical properties,and willthen present four coalitionformability semanticseach of which formalises certain utilitypostulate(s)taking the prof itabiliintoaccount. We assume the following notations. Definition 9 (One-directional attacks) Let S1 ⊆ S be such that α(S1 ) is defined.We say that S1 is one-directionally attacked iff thereexistsSx ⊆ π(1,ViewR (S,S1 ))such thatSx attackss ∈ S1 and S1 does not c-attackany sx ∈ Sx . Definition 10 (States ofa conflict-eliminable set) Let ?: 2 S × 2S be a binary relationsuch that (S1 ,S2 ) ∈?, written also S1 ? S2 , iffα is defined both for S1 and S2 and any of the three conditions below is satisf ied: 1. S2 is c-admissible. 2. S1 is one-directionally attacked. 3. neither S1 nor S2 is c-admissible or one-directionally attacked. Informally if Sx ⊆ S is c-admissible, then it is fully defended from external attacks and is good. If Sx is one-directionally attacked, then that means that Sx does not have any answer to external attacks, which is bad. Any conflict-eliminable set that does not belong to either of them is better than being one-directionally attacked but is worse than being c-admissible. Consequently, if S1 ? S2 , then S2 is in a better state or in at least as good a state as S1 . Definition 11 (Coalition permission) We say that coalition is permitted between S1 ⊆ S and S2 ⊆ S iiff S1 ∩ S2 = ∅ and α is defined for S1 ∪ S2 . The following results tell that this definition of coalition permission isnot underspecif ied. Lemma 1 (Defeats are unresolvable) Let S1 and s be such that S1 ⊆ S and s ∈ S1 . If S1 defeats s, then for all S2 such that S1 ⊆ S2 ⊆ S it holds that S2 defeats s. Proof. By ",
"[Attack strength monotonicity] of R. 2 Proposition 5 (Coalition and conflict-eliminability) If coalition is permitted between S1 and S2 , then α is necessarily defined for S1 and S2 . Proof. Suppose otherwise, then by conflict-eliminability of a set, there must be an argument in Si ,i ∈ {1,2}, such that Si defeats s ∈ Si .The required result obtains via Lemma 1. 2 We make one notion formally explicit for convenience, and then de- fine coalition prof itability. S S Definition 12 (Attackers) Let Attacker : 2 → 2 be such that Attacker(S1 ) = {s ∈ S | there exists some s1 ∈ S1 such that s attacks s1 .}. We say that Attacker(S1 ) is the set of attackers to S1 . S S Definition 13 (Coalition profitability) Let ? : 2 ×2 be such that S1 ? S2 (or (S1 ,S2 ) ∈ ?) satisf iesthree axioms below. 1. S1 ⊆ S2 (larger set). 2. S1 ? S2 (better state). 3. |{s ∈ Attacker(S1 ) | S1 does not c-defeat s and s 6∈ S1 }| ≥ |{s ∈ Attacker(S1 ) | S2 does not c-defeat s and s 6∈ S2 }| (fewer attackers). Due to (better state), S1 ?S2 implies that α is definedboth for S1 and S2 .By (larger set), a set that contains more arguments is a better set. By (better state), a set that is in a better state is a better set. Finally, by (fewer attackers), a set that is attacked by a smaller number of arguments is a better set. The S1 in Attacker(S1 ) on the second line is not a typo: this criterion is for measuring the prof its of coalition formation for S1 . Proposition 6 A (S,R) can be chosen in such a way that a pair of S1 ⊆ S and S2 ⊆ S do not satisfy more than one axioms. Proof. (larger set) s3 s3 (a1,2) (a2,2) (a1,1) (a2,1) Let S be {(a1 ,2),(a2 ,2),s3 }, and let R be such that it is defined only for any combination that matches the attack arrows in the two drawings above. Def ine that R({(a1 ,2)},(a2 ,2)) = R({(a2 ,2)},(a1 ,2)) = R({s3 },(a1 ,2)) = R({s3 },(a1 ,1)) = R({(a2 ,2),s3 },(a1 ,2)) = 1, and that R({(a1 ,2)},s3 ) ≥ π(2,s3 ) (, among others implicit by the conditions of R). Then the left and the right drawings represent (S,R) and respectively ViewR (S,{(a1 ,2),(a2 ,2)}). Now, let S1 be {(a1 ,2)} and let S2 be {(a1 ,2),(a2 ,2)}. Then clearly S1 ⊆ S2 . However, it does not satisfy (better state): S1 is neither c-admissible nor onedirectionally attacked but S2 is one-directionally attacked. It does not satisfy (fewer attackers), either: Attacker(S1 )) = {{ss3}},S11 cdefeats s3 ,and S2 c-defeats none. (better state) s1 s2 s3 Let S be {s1 ,s2 ,s3 }, and let R be such that it is defined only mutually for s1 and s2 as shown above, and such that R({s1 },s2 ) ≥ π(2,s2 ) and R({s2 },s1 ) ≥ π(2,s1 ). Now, let S1 be {s1 } and let S2 be {s3 }. Then S1 ? S2 because S2 is c-admissible. However, clearly it is not the case that S1 ⊆ S2 .Also, Attacker(S1 ) = {s2 }, S1 c-defeats s2 , but S2 does not c-defeat it. (fewer attackers) Let S be {s1 ,s2 ,s3 }, and let R be such that it is defined as is previously, and such that R({s1 },s2 ) < π(2,s2 ) aanndR(({{ss2}},,s)11< π(2,s1 ). Now, let S1 bbee {{ss3aanndlleeS2 be {s2 }.ThenAttacker(S1 ) = ∅,andso(fewerattackers)issatisf ied trivially.However, clearly it is not the case that S1 ⊆ S2 . And it is not the case that S1 ? S2 ,because S1 is c-admissible, while S2 is neither c-admissible nor one-directionally attacked. 2 4.1 Theoretical results around profitability It is triviato show that there exists some (S,R) and some S1 ,S2 ⊆ S such that S1 ? S1 ∪ S2 .We show other results. Theorem 2 (Profitable coalition for subsets of a c-admissible set) Let S1 ⊆ S be such that α(S1 ) is defined, and let Sx ⊆ S be a c-admissible set.If S1 ⊂ Sx , then the following all hold good. 1. α is defined for S2 = Sx \\S1 . 2. Coalition is permitted between S1 and S2 . 3. S1 ? Sx . Proof. 1. Suppose otherwise, then S2 would defeat at least one s ∈ S2 suchthat S2 woulddefeat s.Bylemma 1, Sx wouldthendefeat s, for S2 ⊆ Sx . But Sx ,being c-admissible, does not defeat s. 2. α is defined for Sx by definition; and S1 ∩∩ SS22= ∅∅,aso by def-nition. 3. S1 ⊆ Sx ; Sx is a c-admissible set; and |{s ∈ AAttacker(S1 ) | Sx does not c-defeat s and s 6∈ Sx }| = 0. 2 Theorem 3 (Existence theorem) If,for any S1 ⊆ S, there exists some S2 ⊆⊆ S su hh that coalion is perm ted between S11 and S2 and S1 ? S1 ∪ S2 and S1 ∪ S2 is c-admissible, then there exists some S3 ⊆ S such that coalition is permitted between S1 and S3 and S1 ? S1 ∪ S3 and S1 ∪ S3 is c-preferred and S2 ⊆ S3 . Proof. As S is of a finite size, it is straightforward to see that if S1 ∪ S2 is c-admissible, then there must exist some Sx such that it is c-preferred and that S1 ∪ S2 ⊆ Sx . We show that the choice of Sx \\S1 for S3 ensures the requirement to be satisf ied. By Theorem 2 coalition is permitted between S1 and S3 and S1 ? S1 ∪ S3 . By assumption, S1 ∪ S3 = Sx is c-preferred and S2 ⊆ S3 . 2 Theorem 4 (A c-preferred set as a mutually maximal coalition) Let S1 ⊆ S be such that α(S1 ) is defined, and let Pref(S1 ) be the set of all c-preferred sets that contain S1 as their sub- set. If Pref(S1 ) 6= ∅, then the following holds good: for any Sx ∈ Pref(S1 ), S1 ? Sx and (Sx \\S1 ) ? Sx and there exists no Sx ⊂ Sy ⊆ S such that S1 ? Sy or such that (Sx \\S1 ) ? Sy . Proof. By Theorem 2 and by definition of a set being c-preferrable. 2In general, though, mutual prof itability is not guaranteed. Theorem 5 (Asymmetry of profitabilities) There exists an argu- mentation framework (S,R) such that there are disjoint subsets: S1 and S2 ,of S such that S1 ? S1 ∪ S2 , but such that it is not the case that S2 ? S1 ∪ S2 . Proof. s3 s1 s3 s1 (a2,2) s4 (a2,1) s4 s5 s5 Let S be {s1 ,(a2 ,2),s3 ,s4 ,s5 }, and let R be such that it is defined only for any combination that matches the attack arrows in the drawings above, and such that: R({s1 },(a2 ,2)) = 1; R({s1 ,(a2 ,1)},s3 ) ≥ π(2,s3 ); R({s1 },s3 ) < π(2,s3 ); R({(a2 ,2)},s3 ) < π(2,s3 ); R({(a2 ,1)},s4 ) < π(2,s4 ); R({(a2 ,1)},s5 ) < π(2,s5 ); R({(a2 ,2)},s4 ) ≥ π(2,s4 ); R({(a2 ,2)},s5 ) ≥ π(2,s5 ); R({s3 },s1 ) ≥ 2; R({s4 },(a2 ,1)) ≥ 2; and R({s5 },(a2 ,1)) ≥ 2, among others. Now, let S1 be {s1 }, and let S2 be {(a2 ,2)}. Then S1 ? S1 ∪ S2 , for S1 and S1 ∪ S2 are both neither c-admissible nor one-directionally attacked. The axiom (fewer attackers) is also satisf ied. However, it is not the case that S2 ? S1 ∪ S2 , for it does not satisfy (fewer attackers). 2 Moreover, ? does not satisfy what we may at first expect hold good. Definition 14 (Continuation property of ?) Let S1 ⊆ S be such that α(S1 ) is defined, and let Max(S1 ) be the set of all Sx ⊆ S such that S1 ? Sx and such that if Sx ⊂ Sy ⊆ S, then it is not the case that S1 ? Sy . Then we say that ? is weakly continuous for S1 iff there exists some Sz ∈ Max(S1 ) such that, for any Sw ⊆ Sz , if coalition is permitted between S1 and Sw \\S1 , then S1 ?Sw .We say that ? is continuous for S1 iff it is weakly continuous for S1 for any Sz ∈ Max(S1 ). Theorem 6 (Coalition profitability discontinuation theorem) There exist S1 ,S2 ,Sx ⊆ S such that: (1) α is defined for S1 ,S2 and Sx ; (2) Sx ∈ Max(S1 ); and (3) S2 ⊆ Sx ,but such that S1 ? S2 does not hold good. Moreover, Max(S1 ) = Pref(S1 ) would not change this result. Proof. It suffices to consider the case where Max(S1 ) = Pref(S1 ). s3 s3 s5 s5 s4 s4 (a1, 2) (a2,2) (a1,1) (a2,1) Let S be {(a1 ,2),(a2 ,2),s3 ,s4 ,s5 }, and let R be such that it is defined only for any combination that matches the attack arrows in the drawings above, and such that: R({(a1 ,2)},s4 ) ≥ π(2,s4 ); R({(a2 ,2)},s5 ) ≥ π(2,s5 ); R({(a1 ,2)},(a2 ,2)) = 1; R({(a2 ,2)},(a1 ,2)) = 1; R({s3 },s4 ) ≥ π(2,s4 ); R({(a2 ,1),s3 },s5 ) ≥ π(2,s5 ); R({s4 },(a1 ,1)) ≥ 2; and R({s5 },(a2 ,1)) ≥ 2, among oth- ers. Clearly α is defined for S1 = {(a1 ,2)}, Sa = {(a2 ,2)} S2 = S1 ∪ Sa , and Sx = {(a1 ,2),(a2 ,2),s3 }, among others. Further, Sx is c-preferrable. However, it is not the case that S1 ? S2 . In fact, it is also not the case that Sa ? S2 , since S2 is one-directionally attacked (see the right drawing for the attacks in ViewR (S,{(a1 ,2),(a2 ,2)})), whereas S1 and Sa are neither c-admissible nor one-directionally attacked (see the left drawing). 2 Coalition prof itability continuation property satisf ies in certain special cases, however. Theorem 7 (Coalition profitability continuation theorem) Let Sx ⊆ S be a c-preferred set. Then ? is weakly continuous for any S1 ⊂ Sx iff any disjoint pair Sy ,Sz of subsets of Sx satisfy Sy ? Sy ∪ Sz . Proof. If: Suppose, by way of showing contradiction, there are three disjoint subsets of Sx : Sa ,Sb and Sc , such that Sa ? Sa ∪ Sb 6?(Sa ∪ Sb ) ∪ Sc .By assumption we have (Sa ∪ Sb ) ? (Sa ∪ Sb ) ∪ Sc ,contradiction. Only if: By definition of weak continuation property of ?. 2 4.2 Coalition formability semantics We use the prof itability relation to express our coalition formability semantics. We set forth three rational utility postulates: I Coalition is good when it is prof itable at least to one party. II Coalition is good when it is prof itable to both parties. III Coalition is good when maximal potential future prof its are expected from it. Of these, the first two can be understood immediately with the prof itability relation. Our interpretation for the last postulate is as follows. Suppose a party, some conflict-eliminable set S1 ⊆⊆ SS in our context, considers coalitionformation with another conflict- eliminable setS2 .We know thatS2 issome subset of S1 ⊆ S\\S1 . Before S1 forms a coalition with S2 , we have Max(S1 ) as the set of maximal coalitionspossible for S1. Once the coalition is formed, we have Max(S1 ∪ S2 )as theset ofmaximal coalitionspossible for the coalition. Here clearly Max(S1 ∪ S2 ) ⊆ Max(S1 ). What this means is thata particular choice of S2 blocks any possibilitiesin Max(S1 )MaxSS1 ∪∪ SS22 they become unrealisable from S1 ∪∪ SS.2 Hence S1 has an incentive not to form a coalition with such a S2 if all the members of Max(S1 ∪S2 ) are strictland comparatively less prof itablethan some member of Max(S1 ). We reflectthisintuition. Definition 15 (Maximal profitabilityrelation) Let ≤ll≤bb ≤ff : 2 S × 2 S be such thatthey satisfyall thefollowing: 1. S1 ≤l S2 iff|S1 | ≤|S2 |. 2. S1 ≤b S2 iffS2 is at leasas good by (better state)asS1 . 3. S1 ≤f S2 iffS2 is atleastas good by (fewer attackers)as S1 . We writeS1 <β S2 for each β ∈ {l,b,f} justwhen it is thecase that S1 ≤ββ S2 and it is not thcase that S2 ≤ββ S1 .Then we deine ?m :2S ×2 S to be such thatifS1 ?m S2 ,then both of thefollowing conditions satisfy: 1. S1 ? S2 . 2. Some Sx ∈ Max(S2 ) is such that, for all Sy ∈ Max(S1 ), if Sx <β Sy for some β ∈ {l,b,f}, then there exists γ ∈ ({l,b,f}\\β) such that Sy <γ Sx . Intuitively,ifS1 ?m S2 ,then at leasone set iMax(S1 ) maximal in the three criteriathe setsize,the statequality and the number of ex- ternal attackers,is reachablefrom S2.The maximality here is judged by the principle that if S2 ,S3 ∈ Max(S1 ) are equal by two criteria, then S3 is better ifit is better than S2 by the remaining criterion. We define four formability semantics: W which respects I, M which respects II (and implicitly also I), WS which respects I and III, and S which respects II and III. Definition 16 (Coalition formability semantics) W(S1 ) = {S2 ⊆ S | S1 ? S1 ∪ S2 or S2 ? S1 ∪ S2 }. M(S1 ) = {S2 ⊆ S | S1 ? S1 ∪ S2 and S2 ? S1 ∪ S2 }. WS(S1 ) = {S2 ⊆ S | S1 ?m S1 ∪ S2 or S2 ?m S1 ∪ S2 }. S(S1 ) = {S2 ⊆ S | S1 ?m S1 ∪ S2 and S2 ?m S1 ∪ S2 }. Here, or has the semantics of classical logic disjunction. Intuitively, ρ(S1 ) for ρ ∈ {W,M,WS,S} means that S1 is comfortable with forming a coalition with S2 ∈ ρ(S1 ) under the given criteria. Theorem 8 (The relation among coalition formability semantics) Let S1 ⊆ S be such that α(S1 ) is defined. The following all hold good. (1) M(S1 ) ⊆ W(S1 ). (2) WS(S1 ) ⊆ W(S1 ). (3) S(S1 ) ⊆ M(S1 ). (4) S(S1 ) ⊆ WS(S1 ). Meanwhile, neither WS(S1 ) ⊆ M(S1 ) nor M(S1 ) ⊆ WS(S1 ) is necessary. We provide one example to illustrate the semantic differences. (a3, 2) s1 (a3, 2) s1 (a3, 1) s1 s4 s4 s4 (a2, 2) (a2, 1) (a2, 2) s5 s5 s5 s6 s6 s6 s7 s7 s7 Let S = {{ss11,(a2 ,2),(a3 ,2),s4 ,s5 ,s6 }},, aanndd lleett R bbee ssuucchh that it is defined only for any combination that matches the attack arrows in the above drawings, and such that: RR(({{((aa22 ,,22))}},,((aa33,2)) = 1; RR(({{((aa22 ,,22))}},,ss44 )) ≥≥ ππ((22,,ss44 ); RR(({{((aa22 ,,22))}},,ss55)) ≥≥ ππ((22,,ss55 ); RR(({{((aa22 ,1),s1 }},,((aa33,,22)))) ≥≥ 22;; RR(({{((aa22 ,,11))}},,ss44) < π(2,s4 ); RR(({{((aa22 ,,11))}},,ss55 ) < π(2,s5 ); RR(({{ss11 }},,((aa33,2)) = 1; RR(({{((aa33 ,,11))}},,ss11 )) ≥≥ ππ((22,,ss11 ); RR(({{((aa33 ,,11))}},,ss66)) ≥≥ ππ((22,,ss66 ); RR(({{ss66 }},,((aa33,1)) = 2; R({s6 },s7 ) ≥ π(2,s7 ); R({s7 },s6 ) ≥ π(2,s6 ); RR(({{ss77 }},,ss55)) ≥≥ ππ((22,,ss55 ); RR(({{ss77 }},,ss44 )) ≥≥ ππ((22,,ss44 ); RR(({{ss44 }},,ss77) < π(2,s7 ); RR(({{ss44 }},,((aa22,1)) = 2; RR(({{ss55 }},,((aa22,1)) = 2; RR(({{ss55 }},,ss77 ) < π(2,s7 ); RR(({{ss44 ,s5 }},,ss77)) ≥≥ ππ((22,,ss77 ), among others that are implicit by the conditions of R. The left drawing, the middle drawing, and the right drawing represent (S,R), ViewR ((SS,,{{ss11 ,(a2 ,,22))}})),, and respectively ViewR (S,{(a2 ,2),(a3 ,2)}). We have: W({(a2 ,2)}) = {{(a3 ,2)},{s1 },{s6 },{s7 },{s1 ,s6 },{s1 ,s7 }, {(a3 ,2),s7 }}. M({(a2 ,2)}) = {{(a3 ,2)},{s7 },{s1 ,s6 },{s1 ,s7 },{(a3 ,2),s7 }}. WS({(a2 ,2)}) = {{(a3 ,2)},{s1 },{s7 },{s1 ,s7 },{(a3 ,2),s7 }}. S({(a2 ,2)}) = WS({(a2 ,2)}). The first two equalities can be checked one by one. For WS({(a2 ,2)}), we note that {s1 ,s6 } is excluded because: (1) for {(a2 ,2)}, {(a2 ,2),(a3 ,2),s7 } and {s1 ,(a2 ,2),s7 } are both strictly better in ?m than {s1 ,(a2 ,2),s6 }; and (2) for {s1 ,s6 }, {s1 ,s6 ,s4 ,s5 } is strictly better in ?m than {s1 ,(a2 ,2),s6 }. Similarlyl {s6 } is excluded. Finally, in this particular example, both {s1 ,(a2 ,2),s7 } and {(a2 ,2),(a3 ,2),s7 } are c-preferred, and, moreover, we have: {(a3 ,2)} ?m {(a2 ,2),(a3 ,2),s7 }; {s1 } ?m {s1 ,(a2 ,2),s7 }; {s7 } ?m {s1 ,(a2 ,2)s7 }; and {s7 } ?m {(a2 ,2),(a3 ,2),s7 }. By these, together with the subsumption of S({(a2 ,2)}) in WS({(a2 ,2)}) (Theorem 8), the last equality for S({(a2 ,2)}) follows. 5 Conclusion We proposed abstract-argumentation-theoretic coalition prof itability and formability semantics for conflict-eliminable sets. Further, we showed theoretical results around the semantics. We also showed how our framework can be reduced to Nielsen-Parsons’ argumen- tation framework. Our work has a connection to several important subf ields of abstract argumentation theory such as postulate-based abstract argumentation, attack-tolerant abstract argumentation and dynamic abstract argumentation. It is our hope that this study will further aid in linking the rich knowledge that is being accumulated in the literature. REFERENCES ",
]
Hi. I found that some query contains unnecessary information
sample query
results
following lines are unnecessary: