In the context of value-based argumentation frameworks, and collective decisions, we are interested in the behavior of agents who are willing to misrepresent their sincere beliefs about the ranking of values in order to ensure that their desired decision is agreed upon. We study the application of preference aggregation mechanisms towards reaching a compromise ranking of values for a group of agents. Further, we study under which conditions agents can manipulate the outcome of the discussion. We investigate the computational complexity of this problem.
Argumentation is an inherently multi-agent phenomenon. It often occurs when agents exchange information, aiming at reaching a collective view with respect to some issue. However, it is not clear how to conceptualize the multi-agent character of argumentation. One of the approaches towards solving this problem relies on the applications of aggregation methods, associated with social choice theory. In such approaches, a compromise structure of argumentation is provided for a number of agents, representing distinctive views on it. Further, when mechanisms merging agents’ views about the aspects of argumentation are considered, agents might be willing to provide information conflicting with their beliefs, to obtain a better outcome for themselves.
Intuitively, the goal of collectively solving argumentation problems is to select the
best arguments taking into account all relevant information that agents have at their
disposal and to fairly combine views on the structure of argumentation. Agents can have
preferences over accepted arguments, for instance if acceptance of some distinguished
arguments is determining the choice of some decision. Then, they might decide not to
submit arguments that they know about, as considered by
Several approaches towards capturing the differences in the strength of arguments have been introduced. One of them, value-based argumentation, was provided by Bench
Lisowski et al. / Preventing Manipulation in Aggregating Audiences in Value-Based Arg. Frameworks 49
Capon (2003). In this framework it is assumed that arguments appeal to specific values,
which are of a distinctive importance to a particular agent. Then, an attack can be blocked
from her perspective if she ranks the value of the attacked argument higher than the value
of its attacker. This approach is suited to the problem of argumentation-based
decisionmaking, in which factors other than credibility of information are important while
assessing the acceptability of an argument. Also, it provides a clear justification for the
determined strength of arguments. This is important when an argumentation serves as a
support for decision-making; justification of strength of arguments contributes to the
justification of a decision. It is worth noting that this constitutes a strong advantage of this
approach over assigning preferences over arguments directly, as in the preference-based
argumentation
Recently, value-based argumentation has been studied in the multi-agent argumentation setting. Airiau, Bonzon, Endriss, Maudet, and Rossit (2016) investigated the problem of rationalization of disagreements between agents with respect to the structure of attacks between arguments. They propose to use value-based argumentation for this purpose. In the current paper, we are considering a related problem of finding an argumentation framework constituting a compromise between agents disagreeing about the structure of the attack relation because of their disagreement with respect to the importance of values. Following Pu, Luo, Zhang, and Luo (2013) we consider aggregation of agents’ views on the importance of values with preference aggregation mechanisms. Then, we study the possibility of manipulation in aggregating agents’ views on the strength of arguments, determined by the importance of values they appeal to. We will consider argumentation which results in a decision to either accept a certain action, or to reject it.
In Section 2 we present the basic framework in which the results are situated. We introduce value-based argumentation, acceptability semantics, and we present the way to employ it for group decision-making. Later, in Section 3, we study the ways of manipulating aggregation in the context of value-based argumentation frameworks. For the sake of simplicity our investigations are restricted to the grounded semantics. We finish with conclusions and suggestions for future work.
An argumentation framework is then a directed graph, which nodes are the arguments, and edges represent the attacks between arguments.
A set of arguments S is said to defend an argument a if for any attacker of a there is some member of S which attacks it.
Definition 2.2 Given an argumentation framework AF = ⟨A; →⟩, a set of arguments S ⊆ A and some argument a ∈ A, S defends a iff for any b ∈ A such that b → a there is an a′ ∈ S such that a′ → b. We say that S defends a set of arguments S′ ⊆ A iff S defends all a ∈ S′.
The notion of defense is used to determine when a set of arguments can be rationally selected as an outcome of a discussion. In addition to this notion, the following criteria for selecting sets of arguments have been considered: Definition 2.3 Let AF = ⟨A; →⟩ be an argumentation framework, and S ⊆ A. S is: • Conflict-free: iff there are no a; b ∈ S such that a → b. We refer to the set of all conflict-free sets of AF as CFRAF . • Admissible: iff S is conflict-free and self-defended. We refer to the set of all admissible sets of AF as ADMAF .
Based on these criteria, acceptability semantics define which sets of arguments
(extensions) can be collectively accepted
Definition 2.4 Let AF = ⟨A; →⟩ be an argumentation framework, and S ⊆ A. S is: • Complete: iff S is admissible and F(S) = S. We refer to the set of all complete extensions of AF as CMPAF . • Grounded: iff S is the minimal complete extension of AF w.r.t. set inclusion. We refer to the grounded extension of AF as GRNDAF .
It can be noticed that the grounded extension is always unique. For simplicity, it is this uniqueness that made us restrict the results of this paper to the grounded semantics. An extension of the work to other, potentially multiple extension semantics, is left for future work.
In order to capture the specificity of argumentation about decisions, it is needed to take
into account the values to which arguments appeal
Value-based argumentation assumes that an audience of a discussion can establish the relative strength of arguments on the basis of importance of values to which arguments appeal. Consequently, an attack on an argument appealing to a higher value than its attacker, can be disregarded by a relevant audience. As a result, some particular decisionmakers can be persuaded by a given argumentation to a different extent than others.
Value-based argumentation frameworks are an extension of the abstract argumentation frameworks. In addition to the set of arguments and a binary attack relation, a set of values and a function mapping them to arguments are taken into account.
Definition 2.5 A value-based argumentation framework (VAF) is a tuple VAF = ⟨A; → ;V; val⟩ where A is a set of arguments, →⊆ A2 is an attack relation, V is a set of values and val ∶ A → V is a function assigning values to arguments.
The assignment of values to arguments provides a way of determining the strength of arguments from the perspective of a particular audience. This is done by the specification of an agent’s preferences over values.
Definition 2.6 Let VAF = ⟨A; →;V; val⟩. An audience P is a linear ordering over V . We denote that a value v1 is strictly more preferable than a value v2 for P as v1 ≻P v2.
Lisowski et al. / Preventing Manipulation in Aggregating Audiences in Value-Based Arg. Frameworks 51 Then, we say that an argument defeats another, if it attacks it and the value it is assigned is stronger or equal to the value of the attacked argument.
Definition 2.7 Let VAF = ⟨A; →;V; val⟩ be a VAF and P be an audience. Then, we say that an argument a defeats an argument b for P (we denote it as a →P b) iff a → b and it is not the case that val(b) ≻P val(a).
Given this relation, we can consider a defeat graph, which is an argumentation framework consisting of the set of arguments and of the defeat relation for some ordering P. Definition 2.8 Let VAF = ⟨A; →;V; val⟩ and P be an audience. The defeat graph of VAF P . based on P is an argumentation framework VAFP = ⟨A; → ⟩
Let us illustrate the presented formalism on an example of a specific debate regarding making a practical decision.
Example 2.1
ular, arguments A; G appeal to environmental responsibility (ER), B;C to social fairness (SF), F to economic viability (EV) and D; E - to infrastructure efficiency (IE).
on Figure 1. For each argument, the first element of its description is its name, and the second one is the name of the value it appeals to 1 . 1Notice that the name of the values arguments appeal to is left in the nodes of the defeat graph, for clarity of the representation, but that they are not part of the formal structure of the framework.
efficiency lower, but higher than social fairness. Environmental responsibility is the least important for her. Then, from her point of view attacks in which the attacker appeals to a less important value than the attacked argument are disregarded. Taking her preferences into account, the structure presented in Figure 2 (a) is obtained, after the elimination of disregarded attacks. The grounded extension of this defeat graph is {F; B; D}.
C, SF
B, SF
is the most important value. Expert 2 ranks environmental responsibility second, and social fairness third. Finally, she considers infrastructure efficiency as the least important.
in Figure 2 (b). The grounded extension of this defeat graph is {F; B; D; A}.
When aiming at reaching a decision, like in Example 2.1, an argument can be decisive, in the sense that if it states that a decision should be taken, and if it is an acceptable argument, then the decision should be taken.
This intuition can be captured by mapping information about a decisive support for a decision to a considered argument.
Definition 2.9 Let AF = ⟨A; →⟩ be an argumentation framework. We call DP = ⟨AF; D⟩ a decision problem w.r.t. an AF, where D ∈ A is the decisive argument. Also, let VAF = ⟨A; → ;V; val⟩ be a value-based argumentation framework. We call DP = ⟨VAF; D⟩ a decision problem w.r.t. a VAF, where D ∈ A is the decisive argument.
on whether the argument stating that the ban should be introduced, that is, on argument
The notion of collective defeat graph will be defined in the next section.
Lisowski et al. / Preventing Manipulation in Aggregating Audiences in Value-Based Arg. Frameworks 53 3. Aggregation of Audiences in Value-Based Argumentation Frameworks One of the intuitions behind the claim that the structure of argumentation can be viewed in distinctive ways is that agents might not agree on whether particular arguments are indeed in conflict with each other. Possible explanations for such a situation involve a scenario in which particular agents disagree on the relative strength of arguments. As it was argued earlier, it is plausible to assume that if an agent believes that some strong argument is attacked by a weak one, she might decide to disregard this attack. However, decisions about which arguments are stronger than another are at the discretion of individual assessors. Therefore, structures of successful attacks between arguments might vary among the group of agents.
One of the methods of aggregating views on the relative strength of arguments is to
reach a collective view about the ordering over values that they appeal to. This approach
makes use of preference aggregation functions, pioneered by
In order to provide the described procedure formally, preference aggregation functions will be used. This mechanism, widely studied in social choice theory, considers a profile of orderings over a set of items. Further, it provides a single, collective ordering. Definition 3.1 (Preference Aggregation Function) Let V = {v1; : : : ; vn} be a set of options, N = {1; : : : ; m} be a set of agents, and P be the set of all linear orderings over V .
function is a function F ∶ Pm → P. We denote the set of agents supporting vi ≻ v j in a profile of orderings P as Nvi≻v j .
P
Then, given a VAF = ⟨A; →;V; val⟩ and a profile P of linear orderings over V , the defeat graph AF = ⟨A; →Borda(P)⟩ can be considered as the collective defeat graph. Definition 3.2 Take a VAF = ⟨A; →;V; val⟩, a profile P of preference orderings over V and a preference aggregation function F. Then, a collective defeat graph for P under F is the argumentation framework AF = ⟨A; →F(P)⟩.
An example of such a preference aggregation function is the Borda rule. This rule is simple and easy to present which is why we use it for the illustration of the discussed mechanisms. Naturally, a variety of different rules can be used. To describe the Borda rule, let us also introduce a handy notation.
Notation 1 Let P be a linear order over some set V . We denote by top(P) the option v ∈ V such that for any v′ ≠ v, v ≻P v′. Further, we denote as rankP(v) the position of the option v in the ordering P. Formally, rankP(v) = S{v′ ∈ V Sv′ ≻P v}S + 1.
To compute the result of the Borda rule, for any element Pi of a profile of linear preference orderings P of length m over a set of options V , we assign to each option a number of points. A score of an option v j given by an agent i, called BordaScorei(v j) amounts to SV S − rankPi (v j). Then, an overall score of v j, namely BordaScore(v j) = Sin 1BordaScorei(v j). Finally Borda(P) is a preference ordering in which the rank of = each option is determined by the number of gained points. To obtain a linear ordering as the output of this function additional tie-breaking rules are needed.
pert 3. Let us present her audience, and let us recall the audiences of the other two experts. These three experts form a panel P.
• Expert 1: EV ≻ IE ≻ SF ≻ ER • Expert 2: EV ≻ ER ≻ SF ≻ IE • Expert 3: SF ≻ ER ≻ EV ≻ IE
C, SF
B, SF C, SF
B, SF G, ER
F, EV A, ER
G, ER
F, EV A, ER E, IE
D, IE E, IE
D, IE (a) Sincere audience SF ≻ ER ≻ EV ≻ IE (b) Insincere audience ER ≻ SF ≻ EV ≻ IE
7, IE: 2, SF: 5. So, Borda(P)= EV ≻ SF ≻ ER ≻ IE. The defeat graph for this ordering is presented in Figure 4 (a); this is the collective defeat graph for the panel.
C, SF
B, SF
C, SF
B, SF G, ER
F, EV
A, ER
G, ER
F, EV
A, ER E, IE
D, IE
E, IE
D, IE (a) Before any manipulation
(b) After manipulation by Expert 3
In the current work we are interested in the behavior of agents who are willing to misrepresent their sincere beliefs about the ranking of values in order to ensure that their desired decision is agreed upon. Such a behavior is called manipulation. An important assumption made for the sake of simplicity in the current work is that agents are aware
Lisowski et al. / Preventing Manipulation in Aggregating Audiences in Value-Based Arg. Frameworks 55 of orderings over values in which other agents believe. Relaxing this assumption would be an interesting direction for further research.
To formalize this notion, let us define what agents’ preferences over outcomes of aggregation are. In our setting agents are interested in ensuring that the collective preference ordering induces a defeat graph in which the decisive argument that supports their desired decision is accepted if and only if it is accepted in the defeat graph induced by agents’ own ordering.
Following this intuition we say that given a decision problem and agents’ ordering over values, an agent prefers some ordering to another if it treats the decisive argument consistently with the agent’s intentions, while the other does not. Notice that these preferences are dichotomous. Given a decision problem DP = ⟨VAF; D⟩ and a preference ordering Pi corresponding to some agent i, we say that i is in favor of D if it is in the grounded extension of the defeat graph induced by Pi. If it is not, we say that i is against D.
Definition 3.3 Let DP = ⟨VAF = ⟨A; →;V; val⟩; D⟩ be a decision problem and i be an agent with a preference ordering Pi. If i is in favor of D, for any pair of preference orderings P1; P2, P1 >i P2 iff D ∈ GwRhiNleDD⟨A∈;→GP1RNwDh⟨iAle;→DP2∉ .GRND⟨A;→P2 ⟩. Also, if i is against D, P1 >i P2 ⟩ iff D ∉ GRND⟨A;→P1 ⟩ ⟩
Let us depict the problem of manipulation on an example.
gument A is not in the grounded extension of the defeat graph based on her audience.
audience (see Figure 3 (a)) has {G;C; E; A} as grounded extension: Expert 3 also is in favor of the decision.
The decisive argument A is not in {F; B; D}, the grounded extension of the collective defeat graph of Figure 4 (a).
ordering: ER ≻ SF ≻ EV ≻ IE. Now, the Borda scores would amount to: ER: 5, EV: 7, IE: 2, SF: 4. The modified result of the Borda rule is: EV ≻ ER ≻ SF ≻ IE. The corresponding defeat graph is depicted on Figure 4 (b). The grounded extension of the defeat graph based on this ordering is {F; B; D; A}; the decisive argument belongs to this extension.
A preference aggregation rule is said to be strategy-proof, when it is never possible for a single agent to manipulate.
Definition 3.4 (Strategy-proofness with respect to argumentation) A preference aggregation rule F is strategy-proof with respect to argumentation iff for any profile of preference orderings P any agent i and any preference ordering Pi∗, it is not the case that F(Pi∗; P−Pi ) >i F(P), where (Pi∗; P−Pi ) is the profile of orderings identical to P except of the replacement of Pi with Pi∗.
Let us also phrase manipulation as a computational problem.
VAF-MANIPULATION(F) Instance: DP = ⟨VAF; D⟩, a profile of preference orderings P, agent i.
Question: Is there a preference ordering Pi∗ such that F(Pi∗; P−Pi ) >i F(P)?
The results concerning manipulation in the argumentation setting will be based on the facts about manipulation in voting mechanisms. They will be introduced in the subsequent section.
Aggregating preference orderings is strictly connected with engineering voting rules. There, a group of voters elects an option out of a set of candidates. Mechanisms of this kind aim at ensuring that the winner of the elections represents agents’ preferences accurately. Technically, a voting rule is a function F ∶ Pm → O, where P is the set of all preference orderings over the set of options O and m is the number of voters. Notice that we have imposed that a rule always selects a single option. This property is known as the resoluteness condition.
Voting rules can be envisaged as preference aggregation rules. Then, the winner of elections is the top option of the collective preference ordering.
If this is the case, preferences of particular voters can be clearly defined. Each of them wants to make sure that the winner of the election is as good as possible from the perspective of their ranking.
Definition 3.5 (Strategic Voting Preferences) Let an agent i submit some ordering Pi over some set of options V . Then, for any pair of preference orderings P1; P2 over V ,
Then, we can ask if an agent can make herself better off with respect to strategic voting preferences by submitting an insincere preference ordering. If for some function F it is never the case, we say that F is strategy-proof with respect to voting preferences. Definition 3.6 (Strategy-proofness in voting) A preference aggregation rule F is strategyproof in voting iff for any profile of preference orderings P, any agent i and any preference ordering Pi∗, it is not the case that F(Pi∗; P−Pi ) >Vi F(P).
The Gibbard-Satterthwaite theorem
voting rule for three or more alternatives must be a dictatorship.
For instance, Borda rule cannot be strategy-proof as it is not a dictatorship.
We will show that if it is possible for an agent to manipulate a preference aggregation rule with respect to voting, she might also manipulate with respect to argumentation.
voting preferences is also manipulable with respect to argumentation.
Lisowski et al. / Preventing Manipulation in Aggregating Audiences in Value-Based Arg. Frameworks 57
spect to strategic voting. This means that there is a set of voters N = {1; : : : ; n}, a set of options V = {v1; : : : ; vm} and a profile of preference orderings submitted by voters P = ⟨P1; : : : ; Pn⟩ such that for some voter i, there is some preference ordering Pi∗ over V such that ranki(to p(F (P))) < ranki(to p(F (P∗))), where P∗ is P with Pi replaced by Pi∗. Take such a profile. We will construct a decision problem DP = ⟨VAF; C⟩ which is manipulable by the successful manipulator with respect to strategic voter.
Let us take a set of values V and the set of arguments A = {a1; : : : ; am} (one per element of V ). Further, take the valuation map val such that for any ai ∈ A, val(i) = vi. For simplicity let us say that Pi = v1 ≻i v2 ≻i ⋅ ⋅ ⋅ ≻i vm. Now, let a1 be the decisive argument. Then, let v j correspond to top(F(P)). Construct the attack relation so that a j → a1. Also, for any vb such that ranki(vb) > ranki( j), let ab → a j. No other attacks are considered.
Then firstly notice that for the agent i the argument a1 should be accepted, as it is in the grounded extension of the defeat graph based on i’s preference ordering. However, it is not included in the grounded extension of the defeat graph based on F (P), as all attacks on a j are eliminated because v j is the top value. However, we know that i can submit an ordering P∗ such that some vb ≻i v j becomes the top option. Then, clearly one of the attackers of v j, which is the only attacker of the decisive argument is the top option, so the attack is preserved. Therefore, vi is accepted in the new defeat graph. So i manipulated successfully. ∎
This result is followed by an unfortunate conclusion. Namely, it turns out that for any preference aggregation rule F based on strict preferences, if F is not dictatorial with respect to strategic voting, it is manipulable in the current setting.
To justify this claim it is sufficient to take any preference aggregation rule F based on strict preferences and suppose that it is not dictatorial with respect to strategic voting. Then, by the Gibbard-Satterthwaite theorem we know that it is manipulable with respect to strategic voting. But then it follows that it is also manipulable in the argumentation setting.
This means that aggregating VAFs by preference aggregation is at least as vulnerable to strategic behavior as voting mechanisms. In fact, we can find cases in which rules strategy-proof with respect to strategic voting are manipulable within the argumentation setting.
with respect to argumentation.
preference orderings P distinguish a dictator d. Then, to p(F (P)) = to p(Pd ). To determine the rest of the collective preference ordering, eliminate the value to p(Pd ) from the profile of orderings. Apply the Borda rule to the remainder of the profile. This rule is strategy-proof with respect to strategic voting, as the top option is known from the start.
Now consider the following decision problem DP, where argument 3 is the decisive argument:
d ∶ v2 ≻ v1 ≻ v4 ≻ v3, m ∶ v3 ≻ v4 ≻ v1 ≻ v2, o ∶ v4 ≻ v3 ≻ v2 ≻ v1
score of v2 does not matter as it is dictator’s top option. So, we get F(P) = v2 ≻ v4 ≻ v3 ≻ v1. It is easy to see that under this ordering argument 3 is not in the grounded extension, as the attack 4 → 3 is preserved, while 3 → 4 is not. This leaves agent m dissatisfied, as in the defeat graph based on her preferences argument 3 is clearly accepted.
d ∶ v2 ≻ v1 ≻ v4 ≻ v3, m∗ ∶ v3 ≻ v2 ≻ v1 ≻ v4, o ∶ v4 ≻ v3 ≻ v2 ≻ v1
the collective preference ordering is v2 ≻ v4 ≻ v3 ≻ v1. Under this ordering 3 is accepted in the collective structure. So, m manipulated successfully.
This means that the current setting is strictly less immune to strategic behavior than strategic voting. However, we can show that for a large class of rules, the manipulation problem is difficult to compute. Thanks to this observation we can claim that the proposed mechanism can eliminate manipulation in practical applications. As we will show, if a rule is NP-hard with respect to the problem of strategic voting, it is also NP-hard with respect to our setting.
lem is NP-hard, so is the VAF-manipulation problem with respect to F. PROOF. Take any preference aggregation rule F for which the strategic voting problem is NP-hard. Let us show the way to reduce this problem to manipulation in the current setting. Take a profile of preference orderings P and an agent i with a preference ordering Pi. Let us construct a decision problem in which i can manipulate if and only if she can manipulate with respect to strategic voting. Take a VAF in which we have an argument corresponding to any ranked option. Also, map each of the options as values of corresponding arguments. Further, let i’s favourite option correspond to the decisive argument - ai. Now, let the argument a j, corresponding to top(F(P)) attack ai iff ai ≠ a j. Also, let any argument ab such that val(ab) ≻Pi val(ai) attack a j. Clearly, i is in favor of ai. We need to show that i can manipulate with respect to argumentation setting iff she can manipulate with respect to strategic voting. If i can manipulate with respect to argumentation setting, then there is a preference ordering Pi∗ such that ranki(top(F(Pi∗; P−Pi ))) > ranki(top(F(P))). Otherwise, ai would not be in the grounded extension of the defeat graph induced by F(Pi∗; P−Pi ). But then, i can manipulate with respect to strategic voting. But also, if there is a preference ordering Pi∗ such that ranki(top(F(Pi∗; P−Pi ))) > ranki(top(FP)), then D becomes in the grounded extension of the defeat graph induced by F(Pi∗; P−Pi ). So, i can manipulate with respect to
∎
In this work we studied applications of social choice mechanisms to aggregating views
on preferences over values. Following
We have shown that strictly more rules are manipulable with respect to the studied decision-making setting than with respect to strategic voting. This means, that any rule strategy-proof with respect to aggregating audiences in VAFs is dictatorial with respect to strategic voting. It is worth noting that this is not necessarily a very problematic result. A strategy-proof preference aggregation function which is only dictatorial with respect to one value can still be fair with respect to a large part of the preference ordering.
Our study leaves room for further work. It would be interesting to study the complexity of manipulating preference aggregation by submitting a preference ordering which is minimally different from the agents’ sincere hierarchy of values. Also, it would be beneficial to investigate the complexity of manipulation for semantics other than grounded. Another interesting avenue of research would be to investigate structural properties of VAFs eliminating the possibility of strategic behavior.