Accountable Approval Sorting

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 classification of an individual may not be the same as being accountable for all the classifications. 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) unsatisfied with the outcome of the process regarding his own classification, challenges the committee and asks for a justification.

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 classifications is compliant with the decision process. This may be done by exhibiting only part of the information, illustrating that the obtained classification 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 classification of the complaining individual, again with minimal disclosure of the committee's votes. In this case, the committee will aim for evidence that the classification of the candidate cannot be otherwise, as long as a number of other classification 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 classification is winning or not. An important hypothesis is that the set of winning coalitions has to remain constant for the set of classifications 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:

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 conflicting, 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, reflexive 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 justifications.

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 five points of view N := {1, 2, 3, 4, 5} in the following manner:

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

Definition 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, aRb ⇒ a ∈ B. The upper closure of a subset of (A,R) is the smallest upset of (A,R) containing it: ∀B ⊆ A, clR A (B) := {a ∈ A : ∃b ∈ B aRb}.

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 sufficient coalition of points of view. We assume the set of sufficient coalitions S ⊆ P(N) is fixed, and is an upset for inclusion. Hence, if a coalition is sufficient, any superset of this coalition is also sufficient (and if a coalition is insufficient, any subset of it is also insufficient). We do not assume the set of sufficient 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:

Definition 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 sufficient, i.e.

S is the set of sufficient 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 sufficient 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 sufficient coalitions that lies in the power set of the points of view.

1 Meaning 〈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 unspecified, the tuples are indexed by points of view i ∈ N .

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 (sufficient 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 finding 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 find suitable values for the accepted sets (but not for the set of sufficient coalitions).

Definition 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.

Definition 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 sufficient 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 fixed approved sets:

Definition 5 (Observed sufficient and insufficient coalitions given approved sets). Given α : X → {GOOD, BAD} and a tuple 〈Ai〉 of upsets of 〈(P(X), ≿i)〉, we note:

Proposition 1 (Lower and upper bounds for the sufficient 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:

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 ⋃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 ⋃b∈α-1 (BAD) {i ∈ N : b ∈ Ai} nor to F〈Ai〉(α).

Corollary 1 (complexity of Inv-NCS with fixed 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 find 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 sufficient 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.

[(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 definition 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 definition 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 first 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 ⋃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 := ∨k∈Pj yk ∨ ∨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 ⋃k∈Pj {gk}, the one in the middle containing ⋃k∈Pj {bk}∪⋃k∈Nj {gk}, and the lowest containing ⋃k∈Nj {bk} ∪ ⋃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 first 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 define 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 ⇐⇒ ⋃k∈Pj {bk} ∪ ⋃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 satisfied. 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 ACompact SAT Formulation for Inv-NCS

We leverage Theorem 1 by formulating a boolean satisfiability 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 satisfiability problem translates into suitable, yet arbitrary, explicit values for the approved sets. Upper and lower bounds for the set of sufficient coalitions can be obtained thanks to Proposition 1.

Corollary 2 (CNF Pairwise SAT formulation for NCS). Let α : X → {GOOD, BAD} an assignment. We define 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α

α can be represented in the noncompensatory sorting model if, and only if, φpairwise α is satisfiable.

Moreover, if 〈λi,x〉, 〈µi,g,b〉 is an antecedent of 1 by φpairwise α , then the noncompensatory sorting model NCSS,〈Ai〉 with accepted sets defined by Ai := {x ∈ X : λi,x = 1} and any upset S of (P(N),⊆) of sufficient coalitions containing the upset T〈Ai〉(α) and disjoint from the lower set F〈Ai〉(α) satisfies α ≡ 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 first 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 first 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 specific decision, by referring to the notion of necessary assignment.

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 justified 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 profile 〈(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 fixed 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 certificate 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 first 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:

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].

Definition 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) ⋃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 profile 〈(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 specific 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 influence 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:

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 α.

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 unsatisfiable boolean formula, e.g. given by Corollary 2. The unsatisfiability of the entire formula can be reduced to a ⊆-minimal unsatisfiable subset of clauses (MUS), which are commonly used as certificates 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 first, 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 sufficient 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 insufficient (resp. sufficient), 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 sufficient coalitions by referring to its upper bound P(N) \ F〈Ai〉(α) (resp. lower bound T〈Ai〉(α)).

Example 7. (ex. 6 cont.) According to the first 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 fifth 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 RelatedWork 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 first 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 finding 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 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 unspecified. They show that determining whether a set of candidates are co-winners is NPcomplete when voters have fixed (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 - CoCoRICo-CoDec.