# accountable_approval_sorting__9393311d.pdf

Accountable Approval Sorting

Khaled Belahcene1, Yann Chevaleyre2, Christophe Labreuche3, Nicolas Maudet4, Vincent Mousseau1, Wassila Ouerdane1

1 Laboratoire Genie Industriel, Centrale Sup elec, Universit e Paris-Saclay, Gif-sur-Yvette, France 2 Universit e Paris-Dauphine, PSL Research University, CNRS, UMR [7243], LAMSADE, France 3 Thales Research and Technology, Palaiseau, France 4 Sorbonne Universit e, CNRS, Laboratoire d Informatique de Paris 6, LIP6, France {khaled.belahcene, vincent.mousseau, wassila.ouerdane}@centralesupelec.fr, yann.chevaleyre@dauphine.fr, christophe.labreuche@thalesgroup.com, nicolas.maudet@lip6.fr

We consider decision situations in which a set of points of view (voters, criteria) are to sort a set of candidates to ordered classes (GOOD / BAD). Candidates are judged GOOD when approved by a sufﬁcient set of points of view; this corresponds to noncompensatory sorting. To be accountable, such approval sorting should provide guarantees about the decision process and decisions concerning speciﬁc candidates. We formalize accountability using a feasibility problem expressed as a boolean satisﬁability formulation. We illustrate different forms of accountability when a committee decides with approval sorting and study the information that should be disclosed by the committee.

1 Introduction A committee meets to decide upon the sorting of a number of candidates into two categories (e.g. candidates to accept or not, projects to fund or not). The committee applies a decision process which is public, the outcomes are public as well, however the details of the votes are sensitive and should not be made available. Recently, the issue of the accountability of algorithmic decisions has become a primary concern of our society [Doshi-Velez et al., 2017; Wachter et al., 2017]. To what extent can we make the committee accountable of its decisions? In particular, in our setting, a distinctive feature is that the decision may concern several individuals: being accountable for the classiﬁcation of an individual may not be the same as being accountable for all the classiﬁcations. To make things more precise, it is thus useful to distinguish the following situations: S1: an independent audit agency is commissioned to check that the decisions of the committee indeed comply with the publicly announced decision rule. S2: a candidate, (supposedly) unsatisﬁed with the outcome of the process regarding his own classiﬁcation, challenges the committee and asks for a justiﬁcation.

Situation S1 is sometimes called procedural regularity, see for instance [Kroll et al., 2017], which calls for systems able to prove to oversight authorities that decisions are made under an announced set of rules consistently applied in each case . A typical way to address situation S1 is to require transparency and let the audit agency access all the available information. This suffers from two drawbacks: (i) there are often exceptions making full disclosure of the decision procedure impossible, (ii) the burden of proof lies on the shoulders of the audit agency, which (depending on the model) may be too demanding. Alternatively, we can leave the burden of proof on the committee s side and ask for evidence that the set of classiﬁcations is compliant with the decision process. This may be done by exhibiting only part of the information, illustrating that the obtained classiﬁcation is a possible outcome of the sorting process. Since, typically, many other outcomes would also be possible, this could preserve to some extent the privacy of the committee s votes. On the other hand, failing this test would be evidence that the process was biased. Regarding situation S2, the objective is to justify the classiﬁcation of the complaining individual, again with minimal disclosure of the committee s votes. In this case, the committee will aim for evidence that the classiﬁcation of the candidate cannot be otherwise, as long as a number of other classiﬁcation outcomes are accepted. We can think of such decisions as reference cases. Technically, this requires to show the impossibility to rank the candidate in a different category, i.e. the decision is necessary with respect to the jurisprudence. More precisely, we shall primarily be concerned with a general sorting model where voters express binary judgments [Laslier and Sanver, 2010], and candidates are sorted as either good or bad depending on the fact that the coalition of voters supporting this classiﬁcation is winning or not. An important hypothesis is that the set of winning coalitions has to remain constant for the set of classiﬁcations under scrutiny. This can be seen as a requirement for the process to be unbiased. In this setting, the details of the votes cover two aspects: (i) the approval of voters at the individual level, (ii) the winning coalitions at the committee level. In this paper we address the following research question:

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

Can we make the decisions of a committee using approval sorting accountable while preserving as much as possible the details of the votes?

The details of the sorting model are given in Section 2. At the core of our proposal lies a characterization result of the sorting model which avoids explicit reference to winning coalitions, and leads to a SAT encoding (Section 3). In Section 4, we consider the different scenarios discussed in the introduction and show how this formal machinery allows us to provide argument schemes which answer, at least partially, the accountability requirements. Section 5 discusses related work and concludes.

2 Noncompensatory Sorting

We are interested in situations where there is a need to aggregate diverse, potentially conﬂicting, points of view forming a set N each i N can be seen as an agent, a voter, or a criterion into a single sorting of some alternatives taken in a set X between two categories, GOOD and BAD, expressed by an assignment α : X {GOOD, BAD}. Each point of view i N has an opinion on the entire set of alternatives in the form of a complete preorder i (i.e. i is a complete, reﬂexive and transitive binary relation on X) . This preference may stem from numeric or symbolic performance, as it is often the case in multi-criteria decision aiding, or be intrinsically ordinal, as it is often assumed in social choice contexts. Nevertheless, the aggregation procedure requires that each point of view i N expresses only a binary judgment on each alternative x X which is either approved or not according to i. We shall also consider a subset X X of alternatives with a reference status, with their assignment α : X {GOOD, BAD} serving as a basis for elaborating justiﬁcations. This abstract description covers several well-documented decision processes, e.g. :

a multiple criteria sorting problem [Bouyssou et al., 2006] with ordinal preferences (each point of view i N is a criterion);

a committee decision context (each point of view i N is a voter and the GOOD category is the set of winners). Example 1. We consider a situation with six alternatives X := {a, b, c, d, e, f}, assessed from ﬁve points of view N := {1, 2, 3, 4, 5} in the following manner:

a 1 b 1 f 1 e 1 c 1 d e 2 b 2 c 2 d 2 a 2 f f 3 a 3 b 3 d 3 e 3 c d 4 a 4 c 4 e 4 f 4 b c 5 e 5 b 5 f 5 d 5 a

We recall the deﬁnitions of an upset and the upper closure of a subset w.r.t. a binary relation:

Deﬁnition 1 (Upset and upper closure). Let A be a set and R a binary relation on A. An upset of (A, R) is a subset B A such that a A, b B, a Rb a B. The upper closure of a subset of (A, R) is the smallest upset of (A, R) containing it: B A, cl R A (B) := {a A : b B a Rb}.

We postulate that the process is bounded by two assumptions of rationality, individual and collective.

At the individual level, for all points of view i N, the approved subset of alternatives Ai X should be an upset for the preference relation i. Hence, there is no pair of alternatives x, x X where x is preferred to x w.r.t. i, x is approved by i but not x.

At the collective level, an alternative x X is collectively approved and sorted into the upper category if, and only if, it is approved by a sufﬁcient coalition of points of view. We assume the set of sufﬁcient coalitions S P(N) is ﬁxed, and is an upset for inclusion. Hence, if a coalition is sufﬁcient, any superset of this coalition is also sufﬁcient (and if a coalition is insufﬁcient, any subset of it is also insufﬁcient). We do not assume the set of sufﬁcient coalitions has an additive structure, as opposed to weighted voting games or approval balloting [Laslier and Sanver, 2010].

These two stages form the noncompensatory sorting model:

Deﬁnition 2 (NCS - noncompensatory sorting model, [Bouyssou and Marchant, 2007]). Given a set of alternatives X, a set of points of view N, and a tuple of complete preorders i, i N, if S is an upset of (P(N), ) and a tuple Ai of upsets of (P(X), i) , 1 the noncompensatory sorting model with parameters (S, Ai ) is the function NCSS, Ai mapping alternatives from X to categories in {GOOD, BAD} such that the alternative x is assigned to the upper category GOOD if, and only if, the set of points of view according to which x is approved is sufﬁcient, i.e.

NCSS, Ai (x) = GOOD, if {i N : x Ai} S BAD, else

S is the set of sufﬁcient coalitions of the model, and each Ai is the approved set according to the point of view i N.

Example 2. (ex. 1 continued) Suppose the approved sets are as follows: A1 := {a, b, f}, A2 := {e, b, c}, A3 := {f, a, b}, A4 := {d, a, c}, A5 := {c, e, b}, corresponding to the three best alternatives according to the respective points of view (3-approval). Suppose also the points of view are aggregated according to the simple majority rule, i.e. B S |B| 3. Then, the corresponding noncompensatory model assigns a, b, c to the GOOD category, and d, e, f to the BAD one. Hence, α := {(a, GOOD), (b, GOOD), (c, GOOD), (d, BAD), (e, BAD), (f, BAD)}. We note the same assignment α can be obtained with different sorting parameters, e.g. approved sets A 1 := {a, b, f}, A 2 := {e, b, c, d, a}, A 3 := {}, A 4 := {d, a, c}, A 5 := {c} and sufﬁcient coalitions S containing the coalitions {1, 2}, {5} and their supersets.

This model may appear particularly unwieldy to use explicitly, as it requires to handle a set of sufﬁcient coalitions that lies in the power set of the points of view.

1Meaning Ai i N is a tuple of subsets of X such that, for all i N, Ai is an upset of (X, i). Also, throughout the paper, when the indexing is left unspeciﬁed, the tuples are indexed by points of view i N.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

We propose an indirect approach w.r.t. the parameters of the noncompensatory sorting model implicitly describing the decision process: we suppose the inputs (ordinal preferences over the alternatives according to each point of view) and outputs (an assignment of each alternative to a category, either GOOD or BAD) of the aggregation model are given, and we query the parameters (sufﬁcient coalitions of points of view and accepted sets according to each point of view) of the model. Unlike the usual learning approach, based on the inverse problem of ﬁnding the value of a suitable tuple of parameters permitting to restore the output given the input, we instead focus on versions of this problem where the issue is merely the existence of such a tuple of parameters, and, in the case of a positive answer, to ﬁnd suitable values for the accepted sets (but not for the set of sufﬁcient coalitions).

Deﬁnition 3 (Inverse noncompensatory sorting problem: Inv-NCS). Given an assignment α : X {GOOD, BAD} of alternatives to categories, we say that α can be represented in the noncompensatory sorting model if, and only if, there is a pair of parameters (S, Ai ) where S is an upset of (P(N), ) and Ai i N is a tuple of subsets of X such that, for all i N, Ai is an upset of (X, i), so that α NCSS, Ai .

We say that α is a possible assignment if it is a YES instance of Inv-NCS, i.e. α can be represented in the noncompensatory sorting model. When there is some jurisprudence α , the assignment of a new candidate x can be necessary, in the sense that no other assignment is possible.

Deﬁnition 4 (Necessary assignment w.r.t. reference cases). Given a YES instance α of Inv-NCS, an alternative x X is necessarily assigned to a category C {GOOD, BAD} w.r.t. assignment α if α {(x, C)} is a NO instance of Inv-NCS, where C denotes the category opposite to C.

3 Feasibility of the Inverse NCS Problem

In this section, we propose a characterization of the possibility, given ordinal preferences over the alternatives according to each point of view and an assignment of each alternative to a category, either GOOD or BAD, of representing this assignment in the non-compensatory sorting model. This formulation circumvents any reference to the power set of points of view, so we derive a compact SAT formulation for the inverse problem, which is shown to be NP-hard.

3.1 Inv-NCS with Fixed Approved Sets

When the approved sets are given, solving the inverse NCS problem i.e. learning a set of sufﬁcient coalitions permitting to represent the assignment in the noncompensatory sorting model is similar to learning a disjunctive normal form from training examples. From this observation, we derive a tractable (computable in polynomial time) algorithm yielding the version space [Mitchell, 1982] of the noncompensatory sorting model with ﬁxed approved sets:

Deﬁnition 5 (Observed sufﬁcient and insufﬁcient coalitions given approved sets). Given α : X {GOOD, BAD} and a

tuple Ai of upsets of (P(X), i) , we note:

T Ai (α) := cl P(N ) S g α 1(GOOD){i N : g Ai} ,

F Ai (α) := cl P(N ) S b α 1(BAD){i N : b Ai}

Proposition 1 (Lower and upper bounds for the sufﬁcient coalitions given the approved sets). Given an assignment α, a tuple Ai of upsets of (P(X), i) and an upset S of (P(N), ), α is represented by the noncompensatory sorting model NCSS, Ai if, and only if:

T Ai (α) S P(N) \ F Ai (α)

Proof. α is represented by NCSS, Ai iff i) for all alternatives g α 1(GOOD), NCSS, Ai (g) = GOOD; and ii) for all alternatives b α 1(BAD), NCSS, Ai (b) = BAD i) holds iff S contains S g α 1(GOOD){i N : g Ai} and, as a consequence of being an upset for inclusion, S contains T Ai (α). ii) holds iff S does not contain any coalition pertaining neither to S b α 1(BAD){i N : b Ai} nor to F Ai (α).

Corollary 1 (complexity of Inv-NCS with ﬁxed approved sets). Given an assignment α of alternatives to categories and a tuple Ai of upsets of (P(X), i) , the problem of deciding whether α can be represented in the noncompensatory sorting model with approved sets Ai is tractable (computable in polynomial time).

Indeed, it boils down to checking whether T Ai (α) F Ai (α) is empty or not, which is O(|X|2 |N|).

3.2 A Pairwise Formulation for Inv-NCS The following Theorem is very important as it says that, in order to check that an assignment α is compatible with NCS, it is equivalent to ﬁnd approval subsets over each point of view such that one can discriminate each pair of GOOD and BAD alternatives on at least one point of view (i.e. the GOOD alternative is approved on this point of view, and not the BAD one). Interestingly, the concept of sufﬁcient coalitions disappears in the characterization.

Theorem 1 (Pairwise formulation of the noncompensatory sorting model). An assignment α of alternatives to categories can be represented in the noncompensatory sorting model if, and only if, there is a tuple Ai P(X)N such that:

1. for each point of view i N, Ai is an upset of (X, i)

2. for each pair of alternatives (g, b) α 1(GOOD) α 1(BAD), there is at least one point of view i N such that g Ai and b / Ai.

Proof. [ (1+2) NCS] If there are two alternatives g α 1(GOOD) and b α 1(BAD) that falsify Condition 2, then, for any potential parameters S, Ai of a noncompensatory sorting model, the nesting {i N : g Ai} {i N : b Ai} results in a sorting NCSS, Ai at least as favorable to b as to g, whereas α(b) = BAD is strictly worse than α(g) = GOOD.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

[(1+2) NCS] Given a tuple Ai P(X)N satisfying conditions 1 and 2, we consider the sets of coalitions T Ai (α) and F Ai (α). According to Proposition 1, α can be represented in the noncompensatory model iff T Ai (α) F Ai (α) = . Suppose this intersection is nonempty, and let B T Ai (α) F Ai (α). By deﬁnition of T Ai (α), there is an alternative g α 1(GOOD) such that B {i N : g Ai}: for all points of view i / B, g / Ai. By deﬁnition of F Ai (α), there is an alternative b α 1(BAD) such that B {i N : b Ai}: for all points of view i B, b Ai. Consequently, there is no point of view according to which g is accepted but not b, contradicting condition 2. Hence, T Ai (α) F Ai (α) = .

3.3 Complexity of Inv-NCS We show that the inverse NCS problem is intractable.

Proposition 2 (NP-hardness of Inv-NCS). Given an assignment α of alternatives to categories, the problem of deciding whether α can be represented in the noncompensatory sorting model is NP-hard.

Proof. By reduction from SAT: consider a SAT instance in conjunctive normal form, with n variables y1, . . . , yn and m clauses c1 cm. We build a gadget assignment with m + n points of view and 2m alternatives: g1, . . . , gm are assigned to GOOD whereas b1, . . . , bm are assigned to BAD. First, let us focus on the ﬁrst m points of view: for each k 1 . . . m, let gk k bk k g1 k k gk 1 k gk+1 k k gm k b1 k k bk 1 k bk+1 k k bm. The preference k has two equivalence classes, the upper one containing {gk, bk} and the lower one containing S k =k{gk , bk }. The n last points of view of the gadget are built considering the SAT formula. From the j-th clause, written in disjunctive form cj := W k Pj yk W k Nj yk, where Pj and Nj are disjoint subsets of 1 . . . n indexing the positive (resp. negative) atoms of cj, we build the preference relation j+m. It has at most 3 equivalence classes: the uppermost containing the alternatives S k Pj{gk}, the one in the middle containing S k Pj{bk} S k Nj{gk}, and the lowest containing S k Nj{bk} S k/ Pj Nj{gk, bk}. We note trivial accepted sets i.e. points of view i N such that Ai = or Ai = X do not contribute to the feasibility of the inverse NCS problem. For the m ﬁrst points of view, there is only one nontrivial accepted set: it accepts the upper class and rejects the lower one. For the n last points of view of the gadget, the nontrivial accepted sets accept the uppermost equivalence class, reject the lowest class, and either accept or reject the class in the middle. We deﬁne a one-to-one mapping between the nontrivial accepted sets of the gadget and the assignment of the n variables of the SAT problem: yj is False S k Pj{bk} S k Nj{gk} Am+j. Each non trivial assignment discriminates all pairs (gk, bk ) with k = k w.r.t. the point of view k. The pairs (gk, bk) is discriminated iff the clause ck is satisﬁed. Thus, a solution of the SAT problem is mapped to a tuple of accepted sets that discriminates all pairs with opposite assignments and reciprocally.

3.4 A Compact SAT Formulation for Inv-NCS We leverage Theorem 1 by formulating a boolean satisﬁability problem that answers the decision problem: can the assignment α be represented in the non-compensatory model? If the instance is a YES, any solution of the satisﬁability problem translates into suitable, yet arbitrary, explicit values for the approved sets. Upper and lower bounds for the set of sufﬁcient coalitions can be obtained thanks to Proposition 1. Corollary 2 (CNF Pairwise SAT formulation for NCS). Let α : X {GOOD, BAD} an assignment. We deﬁne the boolean function φpairwise α with variables: λi,x indexed by a point of view i N, and a value x X, µi,g,b indexed by a point of view i N, a good alternative g α 1(GOOD) and a bad alternative b α 1(BAD), as the conjunction of clauses: φpairwise α := φ1 α φ2 α φ3 α φ4 α

φ1 α := V i N V x ix (λi,x λi,x)

φ2 α := V i N , g α 1(GOOD), b α 1(BAD) ( µi,g,b λi,b)

φ3 α := V i N , g α 1(GOOD), b α 1(BAD) ( µi,g,b λi,g)

φ4 α := V g α 1(GOOD), b α 1(BAD) (W i N µi,g,b)

α can be represented in the noncompensatory sorting model if, and only if, φpairwise α is satisﬁable. Moreover, if λi,x , µi,g,b is an antecedent of 1 by φpairwise α , then the noncompensatory sorting model NCSS, Ai with accepted sets deﬁned by Ai := {x X : λi,x = 1} and any upset S of (P(N), ) of sufﬁcient coalitions containing the upset T Ai (α) and disjoint from the lower set F Ai (α) satisﬁes α NCSS, Ai . Variables λi,x are assigned to 1 when the alternative x is accepted from the point of view i, and variables µi,g,b are assigned to 1 when the point of view i accepts g but not b. The clauses φ1 α ensure the sets of accepted values of each point of view meet the ﬁrst condition of Theorem 1, i.e. Ai is an upset. The clauses φ2 α (resp. φ3 α) ensure each variable µi,g,b cannot take a value of one unless g is accepted (resp. unless b is not accepted). The clauses φ4 α ensure the second condition of Theorem 1 is met. The formulation is compact: O(|N| |X|2) variables, O(|N| |X|2) binary clauses and O(|X|2) |N|-ary clauses.

4 Accountable Decisions with Inv-NCS In this section we describe how the theoretical and algorithmic tools described in Section 3 in order to assess the feasibility of the inverse NCS problem (see Def. 3) can be used to support a decision process. More precisely, we address the situation described in Section 1 where a committee has to assign alternatives either to the GOOD or the BAD category, and to account for this assignment. Section 4.1 addresses the ﬁrst situation S1, where an audit is commissioned to check the compliance of the committee to its terms of reference, by referring to the notion of possible assignment. Section 4.2 addresses the second situation S2, where the committee is challenged by a stakeholder to defend a speciﬁc decision, by referring to the notion of necessary assignment.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

4.1 Auditing Conformity We consider the situation S1 depicted in Section 1, where an independent audit agency has to check that the decision α of the committee on candidates X is compatible with NCS. We assume X = : all the assignments should be justiﬁed together, and none should be taken for granted. Should the burden of proof be left to the auditor, the audit procedure could require either i) full disclosure of the preference proﬁle (X, i) i N , and the auditor solving the NPhard Inv-NCS problem, e.g. using a SAT solver and Corollary 2; or ii) full disclosure of the approved sets Ai i N , and the auditor solving the tractable Inv-NCS with ﬁxed accepted sets problem as described by Proposition 1. If we consider putting the burden of proof on the committee, Theorem 1 can be leveraged to compute and provide a certiﬁcate of feasibility for Inv-NCS(α) that involves the disclosure of less information, as illustrated below:

Example 3. (ex. 2 cont.) If the approved sets of the committee are A1, . . . , A5, then it needs to disclose information concerning three points of view in order to prove the assignment α is consistent with an approval procedure, e.g. :

according to the ﬁrst point of view, b is approved (and so is a which is better than b) whereas e is not (and neither is d which is worse than e), hence the procedure is able to discriminate a, b from d, e;

according to the second point of view, c is approved (and so is b which is better than c) whereas d is not (and neither is f which is worse than d), hence the procedure is able to discriminate b, c from d, f;

according to the fourth point of view, c is approved (and so is a which is better than c) whereas e is not (and neither is f which is worse than e), hence the procedure is able to discriminate a, c from e, f.

The following table summarizes the points of view permitting to discriminate each pair: BAD d e f a 1 1 4 GOOD b 1 1 2 c 2 4 2

This manner of arguing that a given assignment is indeed a possible outcome of an approval sorting procedure can be formalized into an argument scheme, an operator tying a tuple of premises pieces of information satisfying some conditions to a conclusion [Walton, 1996].

Deﬁnition 6 (Argument Scheme (AS1)). We say a tuple (i1, g1, G1, b1, B1), . . . , (in, gn, Gn, bn, Bn) instantiates the argument scheme AS1 supporting the assignment α if: i) for all k {1 . . . n}, ik N, gk Gk, α(Gk) = {GOOD}, g Gk, g ik gk, bk Bk, α(Bk) = {BAD}, b Bk, bk ik b and gk ik bk; and ii) S k {1...n} Gk Bk = α 1(GOOD) α 1(BAD)

Hence, according to the point of view ik, gk is the least preferred alternative in the subset of GOOD alternatives Gk and it is preferred to bk, the most preferred alternative in the subset of BAD alternatives Bk. This scheme is somewhat frugal

in the number of pairs of the proﬁle (X, i) i N revealed to the auditor, as the comparisons inside Gk Gk or Bk Bk are not disclosed. Theorem 1 can be reworded as follows: Corollary 3. An assignment α is a YES instance of Inv-NCS if, and only if, there is an instance of AS1 supporting it. Example 4. (Example 3 cont.) The explanations given in Example 3 instantiate AS1 as follows: (1, b, {a, b}, e, {d, e}), (2, c, {b, c}, d, {d, f}), (4, c, {a, c}, e, {e, f}) The length n of an explanation instantiating the argument scheme AS1 offers an indication regarding its cognitive complexity as well as the amount of information disclosed to the auditor. Therefore, we would rather provide the shortest possible explanations, and strive to mention as few points of view as possible. Obviously, an explanation needs to reference a speciﬁc point of view at most once, so n |N|. Unfortunately, the following result shows that one might require all points of view in a complete explanation, even in situations with relatively few alternatives. Proposition 3. For every set of points of view N, there exists a set of |N| + 1 alternatives X and an assignment α : X {GOOD, BAD} for which any tuple instantiating the argument scheme AS1 and supporting α has length |N|. Sketch of the Proof. The result is shown by induction on |N|. For |N| = {1}, we consider α1 := {(g, GOOD), (b, BAD)} with g 1 b. Consider by induction an assignment αp on p candidates Xp assessed on points of view N = {1 . . . p}. We introduce a new alternative z, judged as GOOD, and a new point of view p + 1, such that the candidates in Xp are indifferent on the new point of view, and z can be discriminated from b only on the new point of view.

4.2 Justifying Individual Decisions We now wish to justify the decision of the committee on a candidate x X (Situation S2). As we have seen in the previous section, a complete explanation of the assignment of x necessarily implies the disclosure of many information related to the other candidates, which might not be acceptable. A possible solution is for committee to base their decision on reference cases, an assignment α : X {GOOD, BAD}, e.g. compiling past decisions that are representative of its functioning mode. In order to get rid of the inﬂuence of the other candidates, we are looking for necessary assignments given these reference cases. Example 5. (ex. 2 cont.) We consider the alternatives a, b, c, d, e, f and their assignment α have a reference status, and we are interested in deciding on the assignment of two candidates, x, y such that:

a 1 f 1 b 1 e 1 c 1 y 1 d 1 x e 2 b 2 y 2 c 2 d 2 a 2 f 2 x f 3 a 3 d 3 b 3 y 3 x 3 e 3 c d 4 a 4 c 4 e 4 x 4 y 4 f 4 b c 5 y 5 e 5 b 5 f 5 x 5 d 5 a

It is not possible to represent the assignment (x, GOOD) together with the reference assignment α. Thus, x is necessarily assigned to BAD . On the contrary, both assignments (y, GOOD) and (y, BAD) can be represented together with α.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

Necessary Decisions Entailed by the Jurisprudence An explanation of the necessity of an assignment is intrinsically more complex than that for its possibility: one needs to prove that it is not possible to separate all pairs of GOOD and BAD candidates on at least one point of view. The proof relies on some deadlock that needs to be shown. Formally, this situation manifests itself in the form of an unsatisﬁable boolean formula, e.g. given by Corollary 2. The unsatisﬁability of the entire formula can be reduced to a -minimal unsatisﬁable subset of clauses (MUS), which are commonly used as certiﬁcates of infeasibility, and can also be leveraged to produce explanations [Junker, 2004; Besnard et al., 2010; Geist and Peters, 2017]. In the case of the necessary decisions by approval sorting with a reference assignment, any MUS pinpoints a set of pairs of alternatives in (α 1(GOOD) {x}) α 1(BAD) that cannot be discriminated simultaneously according to the points of view.

Example 6. (ex. 5 cont.) Consider the subset of alternatives c, d, e, f, x, and assume x to be assigned to GOOD. Each pair in GB := {(c, e), (x, d), (x, f)} needs to be discriminated from at least one point of view in N, but this is not possible simultaneously: i) none of the pairs in GB can be discriminated neither from the ﬁrst, the second nor the third point of view, as the overall GOOD alternative is deemed worse than the BAD one. ii) no more than one pair in GB can be discriminated according to each point of view among {4, 5}, and there are more pairs to discriminate than points of view.

The pattern of deadlock illustrated by Example 6 can be generalized and formalized into an argument scheme, with premises: i) a k-tuple of pairs (g1, b1), . . . , (gk, bk) of alternatives with opposite assignment, ii) a subset of points of view B N with cardinality k 1, such that, according to all points of view i / B, bj i gj for all j, and, according to all points of view i B the intervals ]b1, g1]i, . . . , ]bk, gk]i are pairwise disjoint. Clearly, the existence of an argument instantiating the premises of this scheme is a sufﬁcient condition for the infeasibility of representing the given assignment in the noncompensatory model, which in turn yields the conclusion that the candidate x is necessarily assigned to the other category. If we assume that the cognitive burden demanded by an explanation along the lines of this argument scheme increases with the number of its premises, we derive an implicit hierarchy among the necessary decisions supported by the scheme, with a nesting E1 E2 E|N|+1, where Ek denotes the set of decisions supported by a scheme with premises referencing at most k pairs of alternatives with opposite assignment. E1 is exactly the set of decisions stemming from Pareto dominance, where a candidate is either at least as good as a reference alternative in the GOOD category, or at most as good as a reference alternative in the BAD category. The question of deciding if this scheme captures a necessary condition, i.e. if any decision entailed by the jurisprudence can be supported by such an explanation, is left open.

Ambivalent Situations It may happen that, for a given candidate, both assignments to GOOD and to BAD are possible. This situation is obviously

all the more frequent as the reference set is small, or the number of points of view is high. In such a case, a design option would consist in constraining the decision of the committee, either favorably (e.g. following an innocent unless proven guilty principle) or unfavorably (e.g. following a precautionary principle). Another, more common, venue would give the freedom of choice to the committee. In this case, as opposed to the situation where the decision is entailed by the jurisprudence, and where the committee just needs to make obvious the link between the current case and the reference cases, the committee needs to disclose some information concerning its inner functioning. In some cases, though, Proposition 1 offers a solution that avoids a complete disclosure: suppose that, given the approved sets Ai , the candidate is approved from a coalition of points of view that is known to be insufﬁcient (resp. sufﬁcient), because a reference alternative is assigned to the BAD (resp. GOOD) category in a similar, or even better (resp. worse) situation than the candidate. This fortunate situation circumvents the need of discussing the particulars of the set of sufﬁcient coalitions by referring to its upper bound P(N) \ F Ai (α) (resp. lower bound T Ai (α)).

Example 7. (ex. 6 cont.) According to the ﬁrst point of view, y is disapproved, as it is worse than c / A1. According to the third point of view, y is disapproved, as it is worse than b / A3. According to the ﬁfth point of view, y is disapproved, as it is worse than f / A5. Furthermore, being approved according to both the second and fourth points of view is not enough to warrant access to the GOOD category, as illustrated by e. Hence, y is assigned to the BAD category.

5 Related Work and Conclusion

In this paper we are interested in the problem of accountability of decisions issued from a noncompensatory sorting model (NCS) [Bouyssou and Marchant, 2007]. Two situations have been mainly studied. In the ﬁrst one, the committee needs to justify that its decision is a possible NCS assignment. A characterization result helps to turn the existence of such assignment to ﬁnding separations of the pairs of GOOD and BAD candidates over at least one point of view, which can be formulated as a SAT problem. This allows us to generate a single argument scheme that can explain all possible NCS assignments. The second situation arises when the assignment of a new candidate is necessarily derived from jurisprudence. Thanks to the characterization result, one can also construct an argument scheme representing deadlock situations. The use of argument schemes as formal tools to convey explanation in the context of multi-criteria aiding has also been advocated in [Labreuche, 2011; Nunes et al., 2014; Belahcene et al., 2017]. Our solutions stem from an original take of the dual notions of possibility and necessity, often used in so-called robust optimization, decision making [Greco et al., 2010] or voting contexts [Boutilier and Rosenschein, 2016] to account for incomplete information, conveying epistemic stances of skepticism or credulousness. Instead we use them to describe the leeway left to the committee in setting its expectations: the decisions taken are bound from above by possibility, described as the feasibility of the Inv-NCS problem related to

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

their decision, and from below by necessity, described as the infeasibility of the Inv-NCS problem simultaneously related to the reference cases and impossible assignments. Barrot et al. (2013) study the problem of identifying the possible winners of an approval election, when votes are given but approval thresholds are unspeciﬁed. They show that determining whether a set of candidates are co-winners is NPcomplete when voters have ﬁxed (even equal) importance. Approval voting has been studied in the context of multiwinner elections [Aziz et al., 2015], which may seem close to our setting: indeed, we could see the candidates ranked in GOOD as the winners. However, in our context, each candidate is ranked without consideration to the other candidates, and voters are not assumed to have equal importance. Finally, several algorithms have been proposed to learn the parameters of a noncompensatory sorting model from observation: [Leroy et al., 2011] relies on a MIP formulation, [Sobrie et al., 2015] relies on a metaheuristic.

Acknowledgments

This work is partially supported by the ANR project 14CE24-0007-01 - Co Co RICo-Co Dec.

[Aziz et al., 2015] Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. Computational aspects of multi-winner approval voting. In Proceedings of AAMAS, pages 107 115, 2015. [Barrot et al., 2013] Nathana el Barrot, Laurent Gourv es, J erˆome Lang, J erˆome Monnot, and Bernard Ries. Possible winners in approval voting. In Proceedings of the third International conference on Algorithmic Decision Theory, pages 57 70, 2013. [Belahcene et al., 2017] Khaled Belahcene, Christophe Labreuche, Nicolas Maudet, Vincent Mousseau, and Wassila Ouerdane. A model for accountable ordinal sorting. In Proceedings of the 26 International Joint Conference on Artiﬁcial Intelligence, pages 814 820, 2017. [Besnard et al., 2010] Philippe Besnard, Eric Gr egoire, C edric Piette, and Badran Raddaoui. MUS-based generation of arguments and counter-arguments. In Proceedings of the IEEE International Conference on Information Reuse and Integration, pages 239 244, 2010. [Boutilier and Rosenschein, 2016] Craig Boutilier and Jeffrey S. Rosenschein. Incomplete Information and Communication in Voting, page 223 258. Cambridge University Press, 2016. [Bouyssou and Marchant, 2007] Denis Bouyssou and Thierry Marchant. An axiomatic approach to noncompensatory sorting methods in MCDM, i: The case of two categories. EJOR, 178(1):217 245, 2007. [Bouyssou et al., 2006] Denis Bouyssou, Thierry Marchant, Marc Pirlot, Alexis Tsouki as, and Philippe Vincke. Evaluation and decision models with multiple criteria: Stepping

stones for the analyst. International Series in Operations Research and Management Science. Springer, 2006. [Doshi-Velez et al., 2017] Finale Doshi-Velez, Mason Kortz, Ryan Budish, Chris Bavitz, Sam Gershman, David O Brien, Stuart Schieber, James Waldo, David Weinberger, and Alexandra Wood. Accountability of AI under the law: The role of explanation. Co RR, abs/1711.01134, 2017. [Geist and Peters, 2017] Christian Geist and Dominik Peters. Computer-aided methods for social choice theory. In Ulle Endriss, editor, Trends in Computational Social Choice, chapter 13, pages 249 267. AI Access, 2017. [Greco et al., 2010] Salvatore Greco, Vincent Mousseau, and Roman Słowi nski. Multiple criteria sorting with a set of additive value functions. European Journal of Operational Research, 207(3):1455 1470, 2010. [Junker, 2004] Ulrich Junker. Quickxplain: Preferred explanations and relaxations for over-constrained problems. In Proceedings of the 19th National Conference on Artiﬁcal Intelligence, pages 167 172, 2004. [Kroll et al., 2017] Joshua A. Kroll, Joanna Huey, Solon Barocas, Edward W. Felten, Joel R. Reidenberg, David G. Robinson, and Harlan Yu. Accountable algorithms. University of Pennsylvania Law Review, 165, 2017. [Labreuche, 2011] Christophe Labreuche. A general framework for explaining the results of a multi-attribute preference model. Artiﬁcial Intelligence Journal, 175:1410 1448, 2011. [Laslier and Sanver, 2010] Jean-Franc ois Laslier and M. Remzi Sanver. Handbook on Approval Voting. Studies in Choice and Welfare. Springer, Boston, 2010. [Leroy et al., 2011] Agnes Leroy, Vincent Mousseau, and Marc Pirlot. Learning the parameters of a multiple criteria sorting method. In Proceedings of the second International conference on Algorithmic Decision Theory, pages 219 233, 2011. [Mitchell, 1982] Tom M. Mitchell. Generalization as search. Artiﬁcial Intelligence, 18(2):203 226, 1982. [Nunes et al., 2014] Ingrid Nunes, Simon Miles, Michael Luck, Simone Diniz Junqueira Barbosa, and Carlos Jos e Pereira de Lucena. Pattern-based explanation for automated decisions. In Proceedings of 21st ECAI, pages 669 674, 2014. [Sobrie et al., 2015] Olivier Sobrie, Vincent Mousseau, and Marc Pirlot. Learning the parameters of a non compensatory sorting model. In Proceedings of the fourth International Conference on Algorithmic Decision Theory, volume 9346, pages 153 170, 2015. [Wachter et al., 2017] Sandra Wachter, Brent Mittelstadt, and Luciano Floridi. Why a Right to Explanation of Automated Decision-Making Does Not Exist in the General Data Protection Regulation. International Data Privacy Law, 7(2):76 99, May 2017. [Walton, 1996] Douglas Walton. Argumentation schemes for Presumptive Reasoning. Mahwah, N. J.,Erlbaum, 1996.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)