On Middle Grounds for Preference Statements

1 Introduction

High stake decisions or moral dilemmas, such as medical triage or the trolley problem, may prompt stakeholders to have strong opinions with little flexibility. The need to solve such decisions in real life requires the deliberation and consolidation of such possibly conflicting opinions. In this paper, we aim to break down stakeholder statements (e.g. statements about their moral preferences) into an agreeable set of statements - a middle ground. Efforts in defining such a notion of a middle ground have recently been made by Ozaki et al. (2024). However, their notion is designed for Horn logic. We propose a notion of middle ground for a generic logic formalized as a satisfaction system [Aiguier et al., 2018] and provide a case study for a logic that expresses preferences.

Finding a middle ground between stakeholders can be an important first step to understanding and creating solutions for conflicting opinions. Applications of our work are thus manifold. Freedman et al. (2020), e.g., investigate human values in kidney exchanges, where patients are described by features of age, health, and drinking behaviour. Unsurprisingly, the 289 participants of their survey did not agree on the prioritisation of patients. Many other real-life scenarios may provoke conflicting opinions or values: end-of-life medical decisions, decisions prompting trade-offs between economic advantages and preservation of nature, or hiring where the roles in a hiring committee warrant emphasis of different applicant features.

The application scenarios above often include stakeholders who express preferences over alternatives. We concentrate our case study on satisfaction systems similar to those described by Wilson et al. (2015), with a language of comparative statements of the form "I prefer a to b.", where alternatives a and b are vectors of values from given variable domains. Models are then lexicographic or hierarchical orders, i.e., total pre-orders on the set of alternatives. That is, we assume stakeholders have (unknown) orders of importance for the features, by which they compare alternatives. These satisfaction systems transfer well to the Moral Machine Experiment [Awad et al., 2018].

Example 1. In the Moral Machine Experiment, participants (stakeholders) are asked to choose one out of two groups of individuals (alternatives) to save from a car accident. The participant's choices can be interpreted as comparative preference statements like "I prefer saving 1 adult, 4 children, and 0 dogs, to saving 2 adults, 3 children, and 3 dogs.", in symbols, (1, 4, 0) > (2, 3, 3). This could, e.g., be modelled by the lexicographic model (child, adult, dog), which prioritizes children, over adults, and adults over dogs, or by the hierarchical model ({adult, child}, child) where alternatives are first compared on the number of humans, and only if they are equal (there are 5 humans in both groups), is the number of children considered (4 in the first group, 3 in the second). The number of dogs is disregarded in the second model.

Inspired by these scenarios, this paper contributes with the following theoretical results.

General Notion of Middle Ground (MG): We provide a general definition of middle ground for satisfaction systems (Section 3.1), show conditions for existence of a MG (Section 3.2) and an algorithm for construction (Section 3.3).

Case Study for Preference Statements: We describe a satisfaction system similar to that of Wilson et al.(2015) for modelling preferences (Section 4.1), prove that existence and uniqueness of a MG is not guaranteed under this system (Section 4.2), and complexity results of deciding the consistency of preferences and existence of a MG (Section 4.3) for hierarchical models and the special case of lexicographic models.

Section 5 concludes. More proof details and discussions can be found in a longer version on Arxiv under the same title.

2 RelatedWork

There has been several logic-based approaches exploring the task of aggregating information and resolving conflicts in different fields such as non-monotonic reasoning [Horty, 1994; Delgrande and Schaub, 1997], belief merging [G¨ardenfors, 1986], argumentation [Liao et al., 2023], ontology repair [Moodley et al., 2011], and normative reasoning in ethical and legal contexts [Ju et al., 2020; Kollingbaum et al., 2008].

Our work is most similar to that by Ozaki et al. (2024) which defines a middle ground notion for Horn logic and considers the Moral Machine Experiment [Awad et al., 2018]. However, while the postulates (P'1-P'6) in their definition explicitly use structural aspects of Horn expressions like the antecedent and consequent, we facilitate a more general definition with postulates (P1-5) for satisfaction systems. When interpreting their notion of coherence as the counterpart of consistency, then the two liken each other in spirit. The middle ground is a set of statement that is in it self coherent / consistent (P'1 / P1), if possible equivalent to the union of all stakeholders' statements (P'2 / P2) and otherwise at least not in direct opposition to a stakeholders statement (P'3 / P3). Further, all statements in the middle ground should be motivated by stakeholder statements and retain their statements as close as possible (P'4-6 / P4-5). The work by Konieczny and P´erez (2011) in belief merging contains some postulates that resemble the notion of a middle ground. There, an operator takes possibly conflicting beliefs frommultiple sources as input and returns the belief base that is closest to the input and some integrity constraints. This differs from middle ground in that they require more properties to hold. In particular, integrity constraints expressed in propositional logic need to be satisfied and the operator needs to compute the closest belief base (which may not exist or be unique for middle ground). Within social choice theory, Botan et al. (2023) investigate egalitarianism in judgement aggregation using propositional logic. Adler (2016) considers preference aggregation, arguing that preferences are more suitable than judgment for moral aggregation. As a fundamental difference, a middle ground might be insufficient on its own for subsequent decision making but maintains some agreement of all stakeholders that a compromise or aggregation found by means of social choice methods cannot facilitate.

Previous attempts to model preferences include weighted sums over features (which are restrictive w.r.t. to the nature of such features)[Wilson and Montazery, 2016], Pareto models which lead to only partial orders [George and Wilson, 2016], and perhaps most convincingly but also less tractable Conditional Preference Networks [Boutilier et al., 2004] and the expressive prototypical preference logic [Bienvenu et al., 2010]. Here, we lean our case study of preference statements onto the satisfaction systems described in [Wilson et al., 2015]. Preferences are modelled by some kind of hierarchical models which are represented by importance orders on variables/ features of alternatives. One drawback of these models is that they require variables to be non-repeating in the importance order. Instead, we consider models that are non-empty and allow for repeating variables at several importance levels.

3 Middle Grounds for Sets of Statements

In this section we consider a general notion of middle ground for sets of statements and establish sufficient conditions for its existence. To make the presentation as general as possible, we first recall the notion of a satisfaction system [Aiguier et al., 2018; Delgrande et al., 2018; Guimar˜aes et al., 2023].

Definition 1 (Satisfaction System). A satisfaction system is a triple (L, |=,M), where L is a language, M a set of models, and |= a satisfaction relation on M× L. The relation |= contains pairs of the form (π, ϕ) with model π satisfying ϕ.

Given Φ ⊆ L, π |= Φ iff π |= ϕ for all ϕ ∈ Φ. Given Φ, Φ′ ⊆ L, we say that Φ entails Φ′ , written Φ |= Φ′ if, for all π ∈ M, π |= Φ implies π |= Φ′ . Let mod(Φ) denote the set of models that satisfy Φ ⊆ L.

Satisfaction systems have the following properties [Aiguier et al., 2018]: if Φ ⊆ Φ′ then (1) mod(Φ′ ) ⊆ mod(Φ); and (2) Φ′ |= Φ (monotonicity). In this work, we consider satisfaction systems with finite L. We may treat ϕ in L and singleton set {ϕ} interchangeably. Elements of L are called statements. A set of statements Φ ⊆ L is consistent if mod(Φ) ̸= ∅ and falsifiable if mod(Φ) ̸= M. Also, Φ is non-trivial if it is consistent and falsifiable.

Throughout this section, we consider an arbitrary satisfaction system (L, |=,M) and omit explicit references to it.

3.1 Notion of Middle Ground

Before we provide a formal definition of middle ground, we motivate it by considering a scenario where stakeholders have conflicting statements. Recall Example 1, suppose another participant prefers the second alternative, that is, to save 2 adults, 3 children, and 3 dogs, in symbols, (1, 4, 0) < (2, 3, 3). Is there a middle ground for these two participants? The union of their preferences is clearly inconsistent but perhaps by "weakening" the second alternative, e.g., to (2, 3, 0) and also making the preference of the first participant non-strict, we can find an agreeable statement. That is, intuitively, (1, 4, 0) ≥ (2, 3, 0) is "between" the preferences of both participants. This intuition is what we aim at capturing with middle grounds.

Definition 2 (Middle Ground). Let Φ1, . . . ,Φn be non-trivial sets of statements, each associated with a stakeholder i ∈ {1, . . . , n}. A set of statements Φ is a middle ground for Φ1, . . . ,Φn if it satisfies each of the following postulates:

• (P1) Φ is non-trivial;
• (P2) if ⋃ni=1 Φi is consistent, then Φ ≡ ⋃ni=1 Φi;
• (P3) for each ϕ ∈ Φ and for all i ∈ {1, . . . , n} and all ϕi ∈ Φi, there is π ∈ M such that π |= ϕ and π |= ϕi;
• (P4) for each ϕ ∈ Φ, there is i ∈ {1, . . . , n} with Φi |= ϕ;
• (P5) there is no Φ′ such that Φ′ |= Φ and Φ ̸|= Φ′ and Φ′ satisfies (P1)-(P4).

Considering the postulates in turn, we give an intuition behind the formalisation. The first postulate, P1, merely expresses that the statements in the middle ground should in itself make sense and be non-trivial. The second postulate, P2, expresses that whenever the stakeholders statements are not contradictory, the middle ground should simply consist of a union of their statements or a logical equivalent (≡). P3 expresses that any statement in the middle ground should be consistent with any individual statement of any of the stakeholders. Though, the middle ground might still oppose a collection of stakeholder preferences. P4 demands that any statement in the middle ground is justified by a stakeholder who's statements demand it. This is to prevent adding unnecessary statements to the middle ground. Finally, P5 ensures that among the sets of statements that satisfy P1-P4, the middle ground is maximal in the sense that it cannot be implied by another (non-equivalent) set.

To check that a middle ground is well defined, we need to consider the case of consistent stakeholders. It is easy to see that their joint statements satisfy the middle ground postulates.

Proposition 1. If ⋃ni=1 Φi is consistent, then ⋃ni=1 Φi is a middle ground (Definition 2), that is, it satisfies P1-P5.

3.2 Existence of Middle Ground

The satisfaction of P1-P4 is sufficient for the existence. For this, we note that the |=-relation is transitive, i.e., for Φ |= Φ′ and Φ′ |= Φ′′ we have Φ |= Φ′′ . Thus, |= is acyclic for non-equivalent statements, i.e., there exists no chain of nonequivalent sets of statements Φ1 , . . . , Φk such that Φi |= Φi+1 for i = 1, . . . , k - 1 and Φk |= Φ1 . In consequence, since we assume L is finite, there exists a dominating set Φ such that there exists no other non-equivalent set Φ′ |= Φ. Restricting |= to sets of statements that satisfy P1-P4 preserves this. Using this observation and Proposition 1 the following holds.

Proposition 2. Let Φ1, . . . ,Φn be non-trivial sets of statements. If there exists a set of statements Φ that satisfies P1, P3, and P4 then a middle ground exists for Φ1, . . . , Φn.

Further, by using that π |= Φ implies π |= ϕ for ϕ ∈ Φ and transitivity of |=, we can show that to check existence of a middle ground it is sufficient to consider single statements rather than sets of statements.

Proposition 3. Let Φ1, . . . ,Φn be non-trivial sets of statements. If there exists a set of statements Φ that satisfies P3 and P4 for Φ1, . . . , Φn then any statement φ such that ϕ |= φ for some ϕ ∈ Φ satisfies P3 and P4.

Similarly, one can also show that any φ with Φ |= φ satisfies P3 if Φ satisfies P3. The same is not true for P4.

However, if their union is consistent then we can show that it satisfies P1-P4 and thus, since they individually satisfy P5, they must be logically equivalent. Thus, middle grounds are either equivalent or inconsistent together.

Proposition 4. Let Φ and Φ′ be two sets of statements that are middle grounds for stakeholder statements Φ1, . . . , Φn. Then either Φ ≡ Φ′ or Φ∪Φ′ is inconsistent.

3.3 Construction of Middle Grounds

We can show that we can construct a middle ground with the help of the following algorithm, if there exists one. While not computationally efficient in general, this algorithm exploits the result of Proposition 3 by only considering satisfaction of P1, P3 and P4 for single statements rather than sets. This makes Algorithm 1 tractable for cases in which consistency and deduction problems are efficient.

Algorithm 1: Middle Ground for Statements

Input :Non-trivial statement sets Φ1, . . . ,Φn ⊆ L Output :Set of all middle grounds (up to equivalence). 1 if ⋃ni=1 Φi is consistent then return {⋃ni=1 Φi} ; 2 Ψ1 := {φ ∈ L | φ non-trivial} ; 3 Ψ3 := {φ ∈ L | ∀φ′ ∈ ⋃ni=1 Φi : {φ, φ′ } consistent} ; 4 Ψ4 := {φ ∈ L | ∃i ∈ {1, . . . , n}: Φi |= φ} ; 5 return the set of all cardinality-maximal consistent subsets of Ψ1 ∩Ψ3 ∩Ψ4 (possibly empty) ;

Proof Sketch. If ⋃ni=1 Φi is consistent, then by Line 1 the algorithm returns ⋃ni=1 Φi which, by P2 is the only middle ground (up to logical equivalence). Then, assume ⋃ni=1 Φi is inconsistent. In Lines 2-4, Algorithm 1 constructs the sets Ψi of ϕ ∈ L that, individually, satisfies Pi, with i ∈ {1, 3, 4}. We show that Φ is a middle ground iff Φ is equivalent to a cardinality-maximal consistent subset of Ψ := Ψ1 ∩Ψ3 ∩Ψ4, returned by Algorithm 1 (Line 5) (note that Ψ can be empty).

One can argue with the help of the postulates P1-4 and Proposition 3, that if Φ is a middle ground then Φ is equivalent to a consistent subset of Ψ. Next, one can show that any consistent subset Φ of Ψ satisfies P1-P4. Note that elements of a set of statements satisfy P3 and P4 individually, then the set also satisfies P3 and P4. We can now show that any cardinalitymaximal subset Φ of Ψ that is consistent satisfies P5. Assume for contradiction that another set of statements Φ′ satisfys P1-P4 and Φ′ |= Φ and Φ ̸|= Φ′ . One can now showΦ∪Φ′ is inconsistent which implies Φ ̸|= Φ′ - a contradiction.

We have shown that any middle ground is equivalent to a consistent subset of Ψ, and any cardinality-maximal consistent subset of Ψ is a middle ground. By Proposition 4, any two middle grounds are either equivalent or their union is inconsistent. Now, any non-cardinality-maximal consistent subset Φ of Ψ is consistent with one that is cardinality-maximal and thus is a middle ground. Hence, any middle ground is equivalent to a cardinality-maximal consistent subset of Ψ.

4 Middle Grounds for Preferences

Here, we instantiate the general framework of Section 3 for the satisfaction system Λ with the language of preferences (Definition 6) and hierarchical models (Definition 3). We also consider the special case of Λ where we consider the class of lexicographic models (Definition 4). We start by formally defining all necessary notions and then analyse the complexity of deciding the existence of a middle ground.

4.1 Hierarchical Preferences

Variables and Alternatives: Let V be a set of m variables (or features) which describe alternatives. For each variable v ∈ V , let v denote its domain, i.e., the set of possible values of v. Assume that v is finite and contains more than one element. An alternative is an element of V = ∏v∈V v i.e., an assignment to all the variables. For alternative α ∈ V and variable v ∈ V , let α(v) ∈ v be the value α assigns to v.

Example 2 (cont.). As before, we consider a setting similar to that in the Moral Machine Experiment [Awad et al., 2018]. More concretely, let the alternatives be described by three variables with values between 0 and 5 as domains, such that V = adult × child × dog. Consider the alternatives:

Then, α describes a set of 1 adult, 4 children, and 0 dogs. Similarly, β and γ specify sets of adults, children, and dogs.

A hierarchical model consists of a hierarchy over variables. At each level of the hierarchy, we combine the variable assignments by a commutative and associative operator ⊕. Here, we assume that value domains of variables are compatible, i.e., there exists an operator ⊕ that can combine any subset of variables in a meaningful way, and there exists a natural order relation over the value domains as well as over values of combinations of variables. We can then compare alternatives by a lexicographic order. That is, we compare alternatives first based on the value combinations of the first-level variables; only if these are equal is the combination of the next most important variables considered, and so on.

Definition 3 (Hierarchical Model). A hierarchical model, or simply model, π over variables V , is defined to be a non-empty sequence of the form (Y1, . . . , Yk). Here Y1, . . . , Yk ⊆ V are k non-empty sets of variables in V .

Definition 4 (Lexicographic Model). A lexicographic model is a hierarchical model with singleton variable sets. With an abuse of notation, we write such sequences as (v1, . . . , vk), where v1, . . . , vk ∈ V .

Our definitions are very similar to the models defined by Wilson et al. (2015), but differ in two points. First, we assume that neither hierarchical nor lexicographic models can be empty sequences. The corner case of empty models is a technical detail but, as becomes clearer in the following, does not contribute meaningful inference of preference statements. A more important difference is that, by our definition, hierarchical models may have non-disjoint sets of variables. That is, it would be possible to express that the number of humans is most important and the number of children is second most important, since children would appear in two levels of the importance order. Our definition is, in this latter point, a generalisation of the models defined in [Wilson et al., 2015].

For any hierarchical models together with a commutative and associative operator ⊕ we define an order relation ⪰π over alternatives (omitting ⊕ for readability).

Definition 5 (Order Relation ⪰π). Let V be variables and ⊕ a commutative and associative operator on the variable domains. Assume that there exists a total order relation ≥ on the variable domains and on ⊕-combinations of variable values. For a model π = (Y1, . . . , Yk) over variables V the binary relation ⪰π on V is defined as follows.

For alternatives α, β ∈ V , we have α ⪰π β if and only if

• (ii) there exists i ∈ {1, . . . , k} s.t.
• ⊕y∈Yi α(y) > ⊕y∈Yi β(y) and
• ⊕y∈Yj α(y) = ⊕y∈Yj β(y) for all j < i.

The order relation ⪰π is a total pre-order on V , i.e., reflexive, transitive and total. The order relation is not necessarily complete as it, e.g., does not necessarily include all variables. Thus, two alternatives might appear to be equivalent under ⪰π whereas they are different elements in V .

The corresponding strict relation ≻π is given by α ≻π β if and only if (ii) is satisfied, i.e., there exists i ∈ {1, . . . , k} such that ⊕y∈Yi α(y) > ⊕y∈Yi β(y) and for all j < i, ⊕y∈Yj α(y) = ⊕y∈Yj β(y). The corresponding equivalence relation ≡π is given by α ≡π β if and only if (i) is satisfied, i.e., for all i = 1, . . . , k, α(Yi) = β(Yi).

Example 3 (cont.). Consider the alternatives in Example 2. If, it is desirable to save as many living beings as possible, then the natural order is "the more the better". As the domains are compatible (they are all the same) we could for example take the usual addition as the operator ⊕. Consider π = ({adult, child}, {child}). This hierarchical model expresses that the number of humans to be saved from a car crash is the most important. Only if they are equal do we consider the number of children. Dogs are irrelevant in the comparison. Under the order relation induced by π, we have that α is strictly preferred to γ (and β), α ≻π γ and thus α ̸⪯π γ.

Definition 6 (Preference Language L, [Wilson et al., 2015]). We define the language of non-strict and strict preference statements that are simple comparisons of alternatives V as:

We add parenthesis around preference statements when they appear in sequence, e.g. (α ≥ β), (γ < δ), for visualization. As Wilson et al. (2015), we define the meaning of these statements, and a satisfaction relation |= between hierarchical models π and statements, in correspondence to ⪰π.

Definition 7 (SatisfactionRelation |=). Let π be a hierarchical model, and α, β ∈ V alternatives.

• We say that π satisfies the non-strict statement α ≥ β, denoted by π |= α ≥ β, if and only if α ⪰π β. That is, under π, α is at least as preferred as β.
• We say that π satisfies the strict statement α > β, denoted by π |= α > β, if and only if α ≻π β. That is, under π, α is strictly preferred to β.

Through L, a stakeholder can express indifference between α and β via the statements α ≥ β and β ≥ α together. Further, as Wilson et al. (2015) already state, because ⪰π is a total pre-order over the alternatives, π ̸|= α ≥ β is equivalent to π |= β > α. For this reason, we omit the definition of negated statements in L. The notion of entailment is as in Definition 1.

Example 4 (cont.). The statement β > α, i.e., β is strictly preferred to α, intuitively implies that any model π of the statement contains at least one set of individuals (that are important to the stakeholder) from which there are strictly more beings saved in β than in α, e.g., ({adult, child}, {dog}) |= β > α. While ({adult, child}, {dog}) |= α > γ, we cannot deduce α > γ from β > α ({β > α} ̸|= γ > α) because also ({dog}) |= β > α and ({dog}) ̸|= α > γ.

4.2 Non-Uniqueness and Non-Existence

As a first result, we note that there may be more than one middle ground for preference statements in L.

Theorem 6. There exist sets of stakeholder statements in L that admit multiple non-equivalent middle grounds.

Proof Sketch. Consider the following alternatives defined over four binary variables V = {x, y, z,w}:

Consider two stakeholders expressing non-trivial statements:

The stakeholder's statements are consistent individually, but inconsistent together. Thus, the union of Φ1 and Φ2 cannot be a middle ground. One can show that there are at least two non-equivalent middle grounds for Φ1 and Φ2 with help of the two statements ψ1 = γ > δ and ψ2 = δ > γ. In particular:

1. ψ1 and ψ2 are individually non-trivial;
2. ψ1 and ψ2 are inconsistent together;
3. for all i, j ∈ {1, 2} and all ϕi ∈ Φi, there is π such that π |= ψj and π |= ϕi;
4. for i ∈ {1, 2}, Φi |= ψi.

To conclude, we claim that there are at least two nonequivalent middle grounds: one that contains ψ1 and another one that contains ψ2. Indeed, Points (1), (3), (4) and Theorem 5 imply that that there is a middle ground for Φ1 and Φ2 that contains ψ1 (plus possibly other statements, so as to satisfy P5) and a middle ground for Φ1 and Φ2 that contains ψ2. Point (2) implies that there is no middle ground that contains both ψ1 and ψ2 (otherwise P1 would be violated). So there are two non-equivalent middle grounds for Φ1 and Φ2.

Further, we show that a middle ground may not exist.

Theorem 7. There exist sets of stakeholder statements in L that admit no middle ground.

The set of non-trivial statements in this case is given by N = {(γ > α), (γ ≤ α), (γ > β), (γ ≤ β), (α > β), (α ≥ β), (α < β), (α ≤ β), (α > δ), (α ≤ δ), (β > δ), (β ≤ δ)}.

Consider two stakeholders with preference statements:

These statements are consistent individually, but inconsistent together. In particular, the only hierarchical model that satisfies Φ1 is ({x}). Thus Φ1 entails non-trivial statements {(γ > β), (α ≥ γ), (α > β), (α ≥ β), (α > δ), (δ ≥ β)} ⊆ N. None of these statements is consistent with Φ2. By symmetry, the only hierarchical model satisfying Φ2 is ({y}) and none of the entailed statements from Φ2 are consistent with Φ1.

By P4 any statement in the middle ground is entailed by some stakeholders statements. However, by P3 and because the stakeholders have only one statement each, the middle ground needs to be consistent with the stakeholders statements. As argued above, there is no such middle ground.

4.3 Deciding Existence of aMiddle Ground

Through Proposition 2 we have established that for the existence of a middle ground it is sufficient to check whether there exists a set of statements that satisfies P1, P3, and P4. Further, we found that, by Proposition 3, it is sufficient to only check for the existence of single (non-trivial) statements that satisfy P3 and P4. For preference statements of language L we can further narrow down which statements shall be investigated to determine existence of a middle ground.

As a consequence of Proposition 3, and because (α > β) |= (α ≥ β), we have the following relation between strict and non-strict statements satisfying P3 and P4.

Corollary 8. Let Φ1, . . . , Φn ⊆ L be non-trivial sets of statements. If the strict statement α > β satisfies P3 and P4 then its non-strict version α ≥ β satisfies P3 and P4.

Here the non-strict version, while satisfying P3 and P4, might be trivial (i.e., violating P1) even if the strict statement is non-trivial. However, we can observe that this can only happen in a specific case.

Lemma 9. If α > β is non-trivial then either α ≥ β is non-trivial or

• ⊕y∈Y α(y) ≥ ⊕y∈Y β(y) for all Y ⊆ V , and
• there exists Y ⊆ V with ⊕y∈Y α(y) = ⊕y∈Y β(y).

Thus, if a strict statement is non-trivial, its "non-strict version" cannot be a contradiction. Further, it can only be a tautology, if there is a variable set that is indifferent.

The discussion above together with Propositions 2 and 3 allows us now to specify sets of non-trivial strict and non-strict statements that are sufficient to check w.r.t. P3 and P4 to guarantee the existence of a middle ground.

Corollary 10. Let Φ1, . . . ,Φn be non-trivial sets of statements. There exists a middle ground that includes a strict or a non-strict statement if and only if one of the following statements satisfies P3 and P4:

While we can exactly determine the sets of statements in Corollary 10 and they are finite, they are exponentially large on the number of variables. As we see next, checking the postulates of the definition of a middle ground is not in P for hierarchical models, unless P=NP and P=coNP. Thus, we consider lexicographic models, which are a special case of hierarchical models. For these we can narrow down the set of preference statements that need to be checked for satisfying P3 and P4 to only 2 · |V | statements. Since checking the satisfaction of P3 and P4 is polynomial for lexicographic models [Wilson et al., 2015], the existence of a middle ground is decidable in polynomial time.

Hierarchical Models

To analyse the complexity of deciding the existence of a middle ground for hierarchical models, we first show that it is NP-complete to decide consistency for hierarchical models.

Wilson et al. (2015) show that deciding Γ |= α ≥ β is coNP-complete for their definition of hierarchical models which they call HCLP models, even if Γ is a set of non-strict statements [Wilson et al., 2015]. Consequentially, deciding consistency of a set of statements Γ is NP-complete under HCLP models. However, as outlined before, HCLP models are slightly differently defined than hierarchical models and the construction of the reduction from 3SAT to prove their central result is not transferable to hierarchical models. In particular their Lemma 2 does not hold if variable sets in models are allowed to be non-disjoint.

To show NP-completeness of deciding consistency of a set of statements w.r.t. our definition of hierarchical models, we instead use a reduction from the Subset Sum Problem. 1 An instance of Subset Sum consists of a multi-set of integers S and a target integer T. The task is to decide whether there exists a multi-set A ⊆ S such that the sum of its element is T , i.e., ∑a∈A a = T . This problem is NP-complete even if all integers in S are positive [Kleinberg and Tardos, 2006].

Theorem 11. Deciding consistency of a set of preference statements is NP-complete w.r.t. hierarchical models with operators ⊕ that can be computed in time polynomial in the number of variables.

Proof. To see that the consistency problem is in NP, we show that one can check in time polynomial in the number of variables and statements, whether a given hierarchical model π = (Y1, . . . , Yk) satisfies a set of given preference statements Γ ⊆ L. That is, for every non-strict statement (α ⪰ β) ∈ Γ we need to check whether ⊕y∈Yi α(y) ≥ ⊕y∈Yi β(y) for all i = 1, . . . , k, and, for every strict statement (α ≻ β) ∈ Γ, we need to additionally check whether there exists i ∈ {1, . . . , k} with ⊕y∈Yi α(y) ≥ ⊕y∈Yi β(y). By our assumption on ⊕ this can be computed in polynomial time.

We show the completeness of the problem by a reduction from Subset Sum with positive integers. For this, let S be a multiset of positive integers and T ∈ N a target. We construct three preference statements that, when satisfied together, force a hierarchical model to contain a variable set that corresponds to a solution of Subset Sum for S and T .

1 The same proof can also be used to show NP-completeness for HCLP models with an addition for the (trivial) case of the empty HCLP model. It thus offers a more concise alternative to the proof of Wilson et al. (2017). More generally, it shows that deciding consistency is NP-complete even for models containing only one set of variables, and only three preference statements.

Variables: We construct a variable va for each a ∈ S and one variable vT . Denote the set of variables by V . Then |V | = |S| + 1. Let the domain of each variable be N.

Operator: The operator ⊕ is the normal addition. Preference Statements: Consider preference statements

for alternatives αT , βT , αΣ, βΣ that are defined as follows:

Satisfaction: We first show that if there exists a hierarchical model satisfying Φ then there exists a Subset Sum solution. Then we show the reverse.

Assume that there is a hierarchical model π with π |= Φ. Because αT > βT is a strict statement, but all variables are indifferent under αT and βT except vT , π must contain vT in some variable set. Let C be the first such variable set in π with vT ∈ C. Then by π |= (αΣ ≥ βΣ), either (1) C is preceded by another variable set C ′ in π, or (2) C contains other variables and ∑vc∈C αΣ(vc) ≥ ∑vc∈C βΣ(vc) = T . By π |= (βΣ ≥ αΣ) and because integers in S are positive, case (1) is not possible. Thus assume that case (2) holds and let A = {a ∈ S | va ∈ C \ {vT}}. Then ∑a∈A a = ∑vc∈C\{vT } αΣ(vc) ≥ T . Further, by π |= (βΣ ≥ αΣ) and because there is no other variable set preceding C in π, we have T = ∑vc∈C βΣ(vc) ≥ ∑vc∈C αΣ(vc) = ∑a∈A a. So, if π |= Φ then π contains a set of variables C corresponding to T and integers A ⊆ S such that T = ∑a∈A a.

For the reverse, assume there exists a multiset A that is a subset of integers S with T = ∑a∈A a. Then, as shown before, the hierarchical model π = ({va | a ∈ A} ∪ {vT}) satisfies Φ. Thus there exists a hierarchical model satisfying Φ iff there exists a subset of S that sums to T . Because construction of Φ is polynomial in the size of the Subset Sum instance, and Subset Sum is NP-complete, so is deciding consistency for hierarchical models and preference statements.

Recall that for preference statements Γ, α > β, we have Γ |= (α > β) if and only if Γ ∪ {α ≤ β} is inconsistent [Wilson et al., 2017]. Similarly, Γ |= (α ≥ β) if and only if Γ ∪ (α < β) is inconsistent. Then Theorem 11 has the following consequences for the complexity of deduction and testing middle ground.

Corollary 12. Deciding Γ |= φ for preference statements Γ and φ w.r.t. hierarchical models is coNP-complete.

Corollary 13. Let Φ1, . . . ,Φn be non-trivial sets of statements. Let Φ be a given set of statements and consider the satisfaction relation w.r.t. hierarchical models. Then, deciding whether Φ satisfies (P1) is NP-complete and deciding whether Φ satisfies (P4) for Φ1, . . . , Φn is coNP-complete.

Lexicographic Models

For lexicographic models, we are able to decrease the set of statements in Corollary 10 that need to be considered to determine existence of a middle ground to a polynomial size. We first show that it is sufficient to consider binary variables. Informally, this follows from the fact that lexicographic models only consider ordinal relations between the variable assignments and not their actual values.

Proposition 14. Given statement ϕ = (α ≥ β), let ϕb = (αb ≥ βb ) be the result of replacing α(v) and β(v) in ϕ by

• 1 and 0, respectively, if α(v) > β(v);
• 0 and 1, respectively, if α(v) < β(v); and
• 0 and 0, respectively, if α(v) = β(v), for all v ∈ V .

Under the assumption that 1 > 0, we have for all lexicographic models π, that π |= ϕ iff π |= ϕb .

We can further decrease the set of statements to consider for testing existence of a middle ground as follows.

Theorem 15. Consider inference based on lexicographic models on variables V . Let ⃗0 denote the vector of |V | zeros and let ⃗0v be the same as ⃗0 but with 1 at the position corresponding to a variable v ∈ V . Similarly, let ⃗1 denote the vector of |V | ones and let ⃗1v = ⃗1 -⃗0v. There exists a middle ground for non-trivial sets of statements Φ1, . . . , Φn if and only if one of the following statements satisfy P3 and P4:

Proof. Suppose there exists a middle ground for Φ1, . . . , Φn that includes a non-trivial statement ϕ. By Proposition 14, and under the assumption that 1 > 0 we have for all lexicographic models π, that π |= ϕ iff π |= ϕb . Here ϕb is the statement over binary variables as defined in Proposition 14. We can thus focus our following argumentation on ϕb instead of ϕ.

Assume that ϕb is a non-strict statement α ≥ β. Then because it is non-trivial, and in particular not a tautology, there exists variable v such that α(v) < β(v). Any lexicographic model that satisfies α ≥ β must include another variable v′ preceding v or not include v at all. Thus, any such model also satisfies ⃗1v ≥⃗0v, i.e., (α ≥ β) |= (⃗1v ≥⃗0v).

Now assume that ϕb is a strict statement α > β. Then because it is non-trivial, by Lemma 9, it entails either (1) a non-trivial non-strict statement or (2) there exists a variable v such that α(v) = β(v)(= 0) and α(v′ ) ≥ β(v′ ) for all variables v′ ∈ V \ {v}. In case (1), by our arguments above, α > β also entails a non-trivial non-strict statement ⃗1v ≥ ⃗0v for some v ∈ V . For case (2), we show that α > β entails the statement ⃗1v > ⃗0. Because α > β is a strict statement and because α(v) = β(v) the lexicographic model that only includes v does not satisfy α > β. Thus, any lexicographic model satisfying α > β must also include some other variable v′ . Any such model then also satisfies ⃗1v > ⃗0.

As shown above, any middle ground of statements entails a statement in {⃗1v ≥ ⃗0v | v ∈ V } ∪ {⃗1v > ⃗0 | v ∈ V }. By Proposition 3, this statement satisfies P3 and P4.

For the converse direction, assume there exists a statement in {⃗1v ≥ ⃗0v | v ∈ V } ∪ {⃗1v > ⃗0 | v ∈ V } that satisfies P3 and P4. Because all such statements are by construction non-trivial, they also satisfy P1. Then by Proposition 2 there exists a middle ground.

Algorithm 2: Existence of Middle Ground

Input :Sets of non-trivial preferences Φ1, . . . ,Φn. Output :'yes' if it exists, 'no' otherwise. 1 if ⋃ni=1 Φi is consistent then return ⋃ni=1 Φi ; 2 Lb := {(⃗1v ≥⃗0v), (⃗1v >⃗0) | v ∈ V }; 3 Ψ3 := {φ ∈ Lb | ∀ψ ∈ ⋃ni=1 Φi : {φ, ψ} consistent}; 4 Ψ4 := {φ ∈ Lb | ∃i ∈ {1, . . . , n}: Φi |= φ}; 5 if Ψ3 ∩Ψ4 = ∅ then return 'no'; 6 else return 'yes';

Wilson et al. (2015) establish that checking consistency or inference is polynomial-time solvable for lexicographic models and strict and non-strict preference statements. In consequence, we can check in polynomial-time whether a statement satisfies P3 or P4. By Theorem 15, we only need to do this for 2 · |V | many statements for lexicographic models.

Corollary 16. Let Φ1, . . . ,Φn be non-trivial sets of statements. Checking whether there exists a middle ground w.r.t. lexicographic models that includes a (non-trivial) strict or non-strict statement is polynomial-time solvable.

We summarise the algorithm to decide existence of a middle ground in Algorithm 2. Here, the set of statements Lb has cardinality 2 · |V |. To construct Ψ3 we need to perform 2 · |V | · | ⋃ni=1 Φi| consistency checks between two statements. To construct Ψ4 we need to perform 2 · |V | · n checks to see if a statement can be deduced from a stakeholder's statements.

One can also employ Algorithm 1 to construct a middle ground for lexicographic models. In case the stakeholders statements are inconsistent (which can be checked in polynomial time), by Proposition 14, one can then focus on binary statements instead of the complete language L. The number of strict and non-strict statements over |V | variables with binary domains is O(22|V |-1 ). We then need to check every one of the O(22|V |-1 ) statements on whether they satisfy P1, P3 and P4. Thus, while each of these tests individually can be done in polynomial time, Algorithm 1 remains exponential even for lexicographic models. It remains an open question whether there exist tractable algorithms to solve this problem.

5 Conclusion

We investigate the notion of middle ground, exploring its properties, including the fact that it may not exist or be unique. We establish necessary conditions for its existence and describe an algorithmic procedure for both existence checking and construction. Our case study focuses on preference statements, with a notable application in moral preferences and hiring: while the general problem is coNP-complete, we show that deciding existence is tractable for lexicographic models.

Our postulate P3 concerns statements in the middle ground individually and not the whole set. It remains open whether a stronger version of this or other postulates lead to more tractable algorithms or a unique middle ground. Other future work may analyse the tractability of constructing middle grounds for lexicographic models and explore the concept for non-preference-based languages, such as propositional logic.

Acknowledgments

This work was supported by the Research Council of Norway through its Centre of Excellence: Integreat - The Norwegian Centre for knowledge-driven machine learning, project number 332645.