Changelog:
21st April
Brief word on peer ranking
Section on possible generalisations of the model
Question Answering¶
Note:
This supersedes the previous version of the axiomatic question answering work.
Problem Formulation¶
Consider finite sets of sources \(\S\) and questions \(\Q\). Each source answers all questions and gets a subset of questions correct. This is represented by a correctness relation on \(\S \times \Q\).
Definition (Correctness Relation)
A correctness relation is a subset \(K \subseteq \S \times \Q\), where \(sKq\) means that \(s\) answers question \(q\) correctly.
We write \(K(s) = \{q \in \Q : sKq\}\) for the neighbourhood of a source \(s\), i.e. the set of questions that \(s\) answers correctly. Similarly, write \(K^{-1}(q) = \{s \in \S : sKq\}\).
\(K\) induces a (partial) preorder \(\nle_K\) on \(\S\) defined by \(s \nle_K t\) iff \(K(s) \subseteq K(t)\).
Note that the complement \(\comp{K} = (\S \times \Q) \setminus K\) is the ‘incorrectness’ relation: \(s\comp{K}q\) iff \(s\) answers \(q\) incorrectly.
Given a correctness relation, our aim is to rank the sources in terms of their performance on the questions. We define a ranking operator.
Notation. Let \(\orderings{X}\) denote the set of total preorders on a set \(X\) (i.e. the set of relations which are transitive and total).
Definition (Operator)
An operator is a mapping \(\phi: 2^{\S \times \Q} \to \orderings{\S}\). We write \({\le_K^\phi}\) for \(\phi(K)\).
Generalisations¶
Add some structure to the questions. E.g. questions could have an associated topic, questions could be logical formulas (i.e. sources are asked whether a formula holds)
Add some structure in the answers. Rather than a binary correct/incorrect evaluation, allow some variability in the answers. E.g. weighted edges to indicate how close a source was to the correct answer, or an actual value provided for each question and its distance to the true answer measured.
Allow abstensions. Not every student answers every question.
Unknown true answers. If the motivation is crowdsourced questions, it is possible that low-quality sources provide invalid questions, or provide incorrect answers to the questions they provide. This situation seems to bring us quite close to truth discovery…
Set-valued outputs. Maybe it’s unreasonable to require resoluteness in the ranking that an operator gives?
Partial orders as outputs. In an exam on a single topic, it might be reasonable to require a total order on sources as outputs. In general though we may just have a collection of questions, not necessarily related to each other (see idea above about topics for questions). In this case a partial order might be more appropriate as the output of operators. Alternatively we could go somewhere in the middle and require an interval order, which allows us to represent uncertainty in the ranking by assigning each source a ‘competency interval’ (or something like that…)
Variable set of sources and questions.
The last point warrants some further discussion. In the present formulation we have a fixed set of sources and questions. This simplifies things conceptually but might not match an intuitive picture of a ranking system for exam grades. For example, it seems likely that most ranking systems in practical use will work for an arbitrary number of sources (and probably for an arbitrary number of questions).
An alternative formulation is as follows. Let \(U\) be a set of labels for sources and questions. A domain is a pair \(D=\tuple{S,Q}\) of subsets of \(U\) such that \(S \cap Q = \emptyset\). Write \(S_D\) for S and \(Q_D\) for \(Q\). A scenario in \(D\) is a set \(K \subseteq S_D \times Q_D\). An operator is a function \(\phi\) such that for each domain \(D\) and each scenario \(K\) in \(D\), \(\phi_D(K)\) is a total preorder on \(S_D\).
A nice benefit of this alternative formulation is that we can switch sources and questions around to get a ranking of questions. Let \(\comp{D} = \tuple{Q_D, S_D}\) and define the ‘dual’ of \(\phi\) as \(\psi\), where \(q \le_{D,K}^\psi q'\) iff \(q \le_{\comp{D}, \comp{K}}^\phi q'\). This might make it possible to state axioms only for the question-ranking side of things: e.g. \(\phi\) has independence on the source side if and only if its dual has independence on the question side. This is getting complicated though…
Notation for Examples¶
For the purposes of writing down examples in this document, take \(\S \subseteq \{s,t,u,\ldots\}\) and \(\Q \subseteq \{q_1,q_2,q_3,\ldots\}\). Any relation \(K\) can then be represented more compactly as a tuple \(\hat{K}\) which lists the neighbourhoods of each source in turn, denoting a set of questions by the concatenation of their indices.
For example, if
then \(\hat{K} = \tuple{12,3,13}\). Conversely, any vector \(\hat{K}\) of this form uniquely identifies a correctness relation \(K \subseteq \S \times \Q\).
Basic Axioms and Operators¶
Notation. For \(K \subseteq \S \times \Q\) and \(S \subseteq \S\), \(Q \subseteq \Q\), write \(K \rs S, Q = K \cap (S \times Q)\). We omit components that are unconstrained (e.g. \(K \rs S = K \rs S, \Q\)) and omit brackets for single elements (e.g. \(K \rs s = K \rs \{s\}, \Q\)).
For a bijection \(\pi: \S \to \S\) and \(K \subseteq \S \times \Q\), define \(K_\pi = \{\tuple{\pi(s), q} : \tuple{s,q} \in K\}\). For a bijection \(\sigma: \Q \to \Q\), define \(K_\sigma = \{\tuple{s, \sigma(q)} : \tuple{s,q} \in K\}\).
Some of the standard axioms studied in social choice theory can be introduced here. In the statement of each axiom we omit universal quantification over \(K \subseteq \S \times \Q\) and \(s,s' \in \S\).
IIA: \(s \le_K^\phi s'\) iff \(s \le_{K \rs \{s,s'\}}^\phi s'\)
s-sym: for all bijections \(\pi: \S \to \S\), \(s \le_K^\phi s'\) iff \(\pi(s) \le_{K_\pi}^\phi \pi(s')\)
q-sym: for all bijections \(\sigma: \Q \to \Q\), \(s \le_K^\phi s'\) iff \(s \le_{K_\sigma}^\phi s'\)
pos-resp: if \(s \le_K^\phi s'\) and \(q \not\in K(s')\), then \(s <_{K \cup \{\tuple{s',q}\}}^\phi s'\)
IIA is an analogue to Arrow’s Independence of Irrelevant Alternatives: it says that the ranking of \(s\) and \(s'\) does not depend on the answering pattern of any other source \(t\). The source and question symmetry axioms say that \(\phi\) is not sensitive to the ‘names’ chosen for the sources and questions. The final axiom is a positive responsiveness property, which says that a source answering an additional correctly should not worsen its ranking (and should break ties in its favour).
Let \(\Phi_\text{IIA}, \Phi_\text{s-sym}, \Phi_\text{q-sym}\) and \(\Phi_\text{pos-resp}\) denote the set of operators satisfying IIA, s-sym, q-sym, and pos-resp respectively.
IIA and the two symmetries in combination characterise the following class of operators.
Definition (Cardinality-based operators)
\(\phi\) is a cardinality-based operator if there is a function \(f: \{0,\ldots,|\Q|\} \to \R\) such that for all \(K \subseteq \S \times \Q\) and \(s, s' \in \S\):
That is, the ranking of \(s\) and \(s'\) depends only on the number of questions answered correctly by \(s\) and \(s'\) respectively.
Let \(\Phi_\text{card}\) denote the set of cardinality-based operators.
We need some preliminary results before providing the axiomatic characterisation of \(\Phi_\text{card}\).
Lemma
\(\phi \in \Phi_\text{IIA} \cap \Phi_\text{s-sym}\) if and only if there exists a total preorder \(\preceq\) on \(2^\Q\) such that \(s \le_K^\phi s'\) iff \(K(s) \preceq K(s')\).
Let \(\phi \in \Phi_\text{IIA} \cap \Phi_\text{s-sym}\) and \(\preceq\) be as above. Then \(\phi \in \Phi_\text{q-sym}\) if and only if \(|Q|=|Q'\mid\) implies \(Q \preceq Q'\) and \(Q' \preceq Q\).
Proof.
The ‘if’ statement is pretty straightforward to prove. IIA follows upon noting that \(K(t) = (K \rs \{s,s'\})(t)\) for \(t \in \{s,s'\}\). Source-symmetry follows from the fact that \(K(s)=K_\pi(\pi(s))\) for any permutation \(\pi\) and source \(s\).
For the ‘only if’ direction, suppose \(\phi\) has IIA and source-symmetry. For distinct \(s, s' \in \S\) and \(Q, Q' \subseteq \Q\), write
\[\mathcal{K}_{s,s'}(Q, Q') = \{ K \subseteq \S \times \Q : K(s) = Q, K(s') = Q' \} \ne \emptyset\]so that \(\mathcal{K}_{s,s'}(Q, Q')\) is the set of \(K\) where \(s\) answers exactly the set of questions \(Q\) correctly, and \(s'\) answers exactly \(Q'\) correctly.
First note that, due to IIA, the ranking of \(s\) and \(s'\) is constant across \(\mathcal{K}_{s,s'}(Q, Q')\). Indeed, if \(K \in \mathcal{K}_{s,s'}(Q, Q')\) then \(K \rs \{s,s'\} = (\{s\} \times Q) \cup (\{s'\} \times Q')\). In particular, if \(K_1,K_2 \in \mathcal{K}_{s,s'}(Q, Q')\) then \(K_1 \rs \{s,s'\} = K_2 \rs \{s, s'\}\) and so IIA gives \(s \le_{K_1}^\phi s'\) iff \(s \le_{K_2}^\phi s'\).
For each pair \(s,s'\) we can therefore define a relation \(\preceq_{s,s'}\) on \(2^\Q\) by
\[Q \preceq_{s,s'} Q' \iff s \le_K^\phi s'\]for arbitrary \(K \in \mathcal{K}_{s,s'}(Q, Q')\).
Next we apply source-symmetry to show that, in fact, \(\preceq_{s,s'}\) does not depend on \(s\) and \(s'\). Let \(t, t' \in \S\) with \(\tuple{s,s'} \ne \tuple{t,t'}\). We will show that \(Q \preceq_{s,s'} Q'\) iff \(Q \preceq_{t,t'} Q'\).
Let \(\pi\) be a permutation of \(\S\) such that \(\pi(s) = t\) and \(\pi(s') = t'\). 1 Take \(K \in \mathcal{K}_{s,s'}(Q, Q')\). Then \(Q = K(s) = K_\pi(\pi(s)) = K_\pi(t)\). Similarly, \(Q' = K_\pi(t')\). Hence \(K_\pi \in \mathcal{K}_{t,t'}(Q, Q')\). From the definition of \(\preceq_{s,s'}\) and \(\preceq_{t,t'}\) respectively, we have
\[Q \preceq_{s,s'} Q' \iff s \le_K^\phi s' \\ Q \preceq_{t,t'} Q' \iff t \le_{K_\pi}^\phi t'\]But by source-symmetry, \(s \le_K^\phi s'\) iff \(t \le_{K_\pi}^\phi t'\). We see that \(Q \preceq_{s,s'} Q'\) iff \(Q \preceq_{t,t'} Q'\) as required. That is, \(\preceq_{s,s'}\) and \(\preceq_{t,t'}\) are the same relation, which we now denote simply by \(\preceq\).
Despite the suggestive notation, we are yet to show that \(\preceq\) is a total preorder.
Transitivity. Suppose \(Q_1 \preceq Q_2\) and \(Q_2 \preceq Q_3\). Take arbitrary distinct \(s, s', t \in \S\). 2 Construct \(K\) such that \(K(s) = Q_1, K(t) = Q_2\) and \(K(s') = Q_3\). We have
\[K \in \mathcal{K}_{s,t}(Q_1, Q_2) \tag{1}\]\[K \in \mathcal{K}_{t,s'}(Q_2, Q_3) \tag{2}\]\[K \in \mathcal{K}_{s,s'}(Q_1, Q_3) \tag{3}\]Since \(Q_1 \preceq Q_2\), we have \(Q_1 \preceq_{s,t} Q_2\) and thus (1) gives \(s \le_K^\phi t\). On the other hand \(Q_2 \preceq Q_3\), so \(Q_2 \preceq_{t,s'} Q_3\) and so (2) gives \(t \le_K^\phi s'\). Transitivity of \(\le_K^\phi\) therefore gives \(s \le_K^\phi s'\). In light of (3) this means \(Q_1 \preceq_{s,s'} Q_3\) and thus \(Q_1 \preceq Q_3\), as required for transitivity.
Totality. Let \(Q, Q' \subseteq \Q\). Take artbitrary distinct \(s, s' \in \S\) and let \(K \in \mathcal{K}_{s,s'}(Q, Q')\). By totality of \(\le_K^\phi\), either \(s \le_K^\phi s'\) or \(s' \le_K^\phi s\). In the first case, \(Q \preceq_{s,s'} Q'\) and thus \(Q \preceq Q'\). In the latter case, since \(K \in \mathcal{K}_{s',s}(Q', Q)\) we have \(Q' \preceq_{s',s} Q\) and thus \(Q' \preceq Q\).
To complete the proof we show that \(s \le_K^\phi s'\) iff \(K(s) \preceq K(s')\) for all \(K, s, s'\). Indeed, for any \(K\) we clearly have \(K \in \mathcal{K}_{s,s'}(K(s), K(s'))\), so
\[s \le_K^\phi s' \iff K(s) \preceq_{s,s'} K(s') \iff K(s) \preceq K(s')\]as required.
Let \(\phi \in \Phi_\text{IIA} \cap \Phi_\text{s-sym}\). Let \(\preceq\) be as in part (1).
For the ‘if’ statement, suppose \(|Q|=|Q'|\) implies both \(Q \preceq Q'\) and \(Q' \preceq Q\). Let \(\sigma\) be a permutation of questions, \(K \subseteq \S \times \Q\) and \(s, s' \in \S\).
Note that \(q \in K(s)\) iff \(\sigma(q) \in K_\sigma(s)\). This means \(\sigma\) restricted to \(K(s)\) is a bijection into \(K_\sigma(s)\). In particular, \(|K(s)| = |K_\sigma(s)|\). Similarly, \(|K(s')| = |K_\sigma(s')|\). By our hyopthesis, \(K(s) \simeq K_\sigma(s)\) and \(K(s') \simeq K_\sigma(s')\). 3 Supposing that \(K(s) \preceq K(s')\), we have
\[K_\sigma(s) \preceq K(s) \preceq K(s') \preceq K_\sigma(s')\]Similarly one can show that \(K_\sigma(s) \preceq K_\sigma(s')\) implies \(K(s) \preceq K(s')\). Hence
\[s \le_K^\phi s' \iff K(s) \preceq K(s') \iff K_\sigma(s) \preceq K_\sigma(s') \iff s \le_{K_\sigma}^\phi s'\]so \(\phi\) satisfies question-symmetry.
Now the ‘only if’ statement. Suppose \(\phi\) also satisfies question-symmetry, and suppose \(|Q| = |Q'|\) for some \(Q,Q' \subseteq \Q\). Since \(\preceq\) is total, assume without loss of generality that \(Q \preceq Q'\). We must show \(Q' \preceq Q\).
Note that \(|Q \setminus Q'| = |Q' \setminus Q|\), so there is a bijection \(\tau: Q \setminus Q' \to Q' \setminus Q\). Define \(\sigma: \Q \to \Q\) by
\[\sigma(q) = \begin{cases} \tau(q), & q \in Q \setminus Q' \\ \tau^{-1}(q), & q \in Q' \setminus Q \\ q, & \text{ otherwise} \end{cases}\]Then \(\sigma\) is bijective. Now take \(K \in \mathcal{K}_{s,s'}(Q, Q')\); since \(Q \preceq Q'\) we have \(s \le_K^\phi s'\). Applying question-symmetry, we get \(s \le_{K_\sigma}^\phi s'\) also. It is not too difficult to see that \(K_\sigma(t) = \sigma(K(t))\) for all sources \(t\). Hence \(K_\sigma(s) = \sigma(K(s)) = \sigma(Q) = Q'\). Similarly, \(K_\sigma(s') = \sigma(Q') = Q\). Thus \(K_\sigma \in \mathcal{K}_{s,s'}(Q', Q)\). Since \(s \le_{K_\sigma}^\phi s'\), this gives \(Q' \preceq_{s,s'} Q\) and \(Q' \preceq Q\) as required.
Lemma
Let \(\preceq\) be a total preorder on a finite set \(X\). Then there is a function \(g: X \to \R\) such that \(x \preceq y\) iff \(g(x) \le g(y)\).
Proof.
Write \(L(x) = \{z \in X : z \preceq x\}\) and set \(g(x) = |L(x)|\). First suppose \(x \preceq y\). Then by transitivity of \(\preceq\) we have \(L(x) \subseteq L(y)\), and so \(|L(x)| \le |L(y)|\), i.e. \(g(x) \le g(y)\).
Now suppose \(g(x) \le g(y)\). For contradiction suppose \(x \not\preceq y\). Then by totality, \(y \preceq x\). As above, this means \(L(y) \subseteq L(x)\). Note that by reflexivity of \(\preceq\) we have \(x \in L(x)\), and by assumption \(x \not\in L(y)\). This means that in fact \(L(y)\) is a strict subset of \(L(x)\). In turn this means \(g(y) = |L(y)| < |L(x)| = g(x)\) – a contradiction! Hence \(x \preceq y\) as required.
We are ready to prove the main result.
Theorem
\(\Phi_\text{card} = \Phi_\text{IIA} \cap \Phi_\text{s-sym} \cap \Phi_\text{q-sym}\).
Proof.
The inclusion \(\Phi_\text{card} \subseteq \Phi_\text{IIA} \cap \Phi_\text{s-sym} \cap \Phi_\text{q-sym}\) is pretty easy to show (but tedious to write out!). We show the other inclusion.
Suppose \(\phi\) has IIA, source-symmetry and question-symmetry. By our previous lemma, there is a total preorder \(\preceq\) on \(2^\Q\) such that \(s \le_K^\phi s'\) iff \(K(s) \preceq K(s')\), and moreover \(Q \simeq Q'\) whenever \(|Q| = |Q'|\), for \(Q, Q' \subseteq \Q\).
By the other lemma, there is a function \(g: 2^\Q \to \R\) such that \(Q \preceq Q'\) iff \(g(Q) \le g(Q')\). Note that \(g(Q)=g(Q')\) if \(|Q|=|Q'|\). We can therefore define \(f: \{0,\ldots,|\Q|\} \to \R\) by \(f(n) = g(Q_n)\), where \(Q_n \subseteq \Q\) is an arbitrary set of \(n\) questions. Note that, in particular, \(g(Q) = f(|Q|)\).
Finally, we have
and so \(\phi \in \Phi_\text{card}\).
Perhaps the simplest cardinality-based operator is the one corresponding to \(f(n) = n\). Let us call this the counting operator, denoted by \(\phi_\text{count}\). That is, \(s \le_K^{\phi_\text{count}} s'\) iff \(|K(s)| \le |K(s')|\). 4 Amongst the cardinality-based operators, \(\phi_\text{count}\) is characterised by positive responsiveness. I think this result is similar to May’s theorem. (Edit 4th June: I now see that this theorem is essentially the main result of [Rub80]. The idea of cardinality-based operators – and their axiomatic characterisation – is not considered there, though).
Theorem
\(\phi\) satisfies IIA, s-sym, q-sym and pos-resp if and only if \(\phi = \phi_\text{count}\).
Proof.
First the ‘if’ statement. Clearly \(\phi_\text{count} \in \Phi_\text{card}\), so by the above theorem \(\phi_\text{count}\) has IIA, s-sym and q-sym. For pos-resp, suppose \(s \le_K^{\phi_\text{count}} s'\) and \(q \not\in K(s')\). Write \(\hat{K} = K \cup \{\tuple{s', q}\}\). Then
so \(s \le_{\hat{K}}^{\phi_\text{count}} s'\).
For the ‘only’ if statement, suppose \(\phi\) satisfies the stated axioms. By the previous theorem, there is some \(f\) such that \(s \le_K^\phi s'\) iff \(f(|K(s)|) \le f(|K(s')|)\).
First we show that \(f(n) < f(n+1)\), for all \(0 \le n < |\Q|\). Indeed, take two distinct sources \(s,s' \in \S\) and some set \(Q_n \subseteq \Q\) of \(n\) questions. Construct \(K\) such that \(K(s) = K(s') = Q_n\). Then clearly \(s\) and \(s'\) rank equally, and in particular \(s \le_K^\phi s'\). Since \(|Q_n| = n < |\Q|\), there is some \(q \in \Q \setminus Q_n\). Write \(\hat{K} = K \cup \{\tuple{s', q}\}\). Then pos-resp implies \(s <_{\hat{K}}^\phi s'\), i.e. \(f(|\hat{K}(s)|) < f(|\hat{K}(s')|)\). Since \(|\hat{K}(s)| = |K(s)| = n\) and \(|\hat{K}(s')| = |K(s')| + 1 = n + 1\), this shows \(f(n) < f(n+1)\).
Now we show \(n \le m\) iff \(f(n) \le f(m)\). Indeed, if \(n=m\) then clearly \(f(n) \le f(m)\). If \(n < m\) then \(f(n) < f(n+1) < \ldots < f(m)\). For the converse, if \(f(n) \le f(m)\) then we cannot have \(m < n\) (as just shown, this would imply \(f(m) < f(n)\)), so it must be the case that \(n \le m\).
In other words, for any \(K, s, s'\):
so \({\le_K^\phi} = {\le_K^{\phi_\text{count}}}\) for all \(K\), i.e. \(\phi = \phi_\text{count}\).
Note. I think a simpler and more direct proof of the above is possible, which does not require the preceding lemmas and theorem (it’s essentially the same as our result for Voting in TD, and that proof was more straightforward than this one). However, I think the characterisation of \(\Phi_\text{IAA} \cap \Phi_\text{s-sym}\) in terms of the \(\preceq\) ordering, and the characterisation of \(\Phi_\text{card}\), are of interest in their own right.
Accounting for Question Difficulty¶
The cardinality-based operators discussed above are somewhat naive in that they assume all questions are equally difficult. Intuitively, correctly answering difficult questions should carry more weight than easy questions when comparing sources. Moreover, the difficulty of questions may not be fixed, but determined by the relation \(K\) itself. The following class of difficulty-aware operators generalises cardinality-based operators to account for these factors.
Definition (Difficulty-aware operator)
A difficulty function is a mapping \(d: 2^{\S \times \Q} \to (\Q \to \R)\). We write \(d_K\) for \(d(K)\), so that \(d_K\) is a mapping \(\Q \to \R\).
An aggregation function is a mapping \(F: \bigcup_{n=0}^{|\Q|}{\R^n} \to \R\) such that \(F(x_1,\ldots,x_n) = F(x_{\pi(1)},\ldots,x_{\pi(n)})\) for any permutation \(\pi\) on \(\{1,\ldots,n\}\). 5 6
For \(K \subseteq \S \times \Q\) and \(s \in \S\), enumerate \(K(s) = \{q_1,\ldots,q_n\}\) and write \(F_K(s) = F(d_K(q_1),\ldots,d_K(q_n))\). 7
Then the difficulty-aware operator associated with \(d\) and \(F\) is \(\phi_{d,F}\) defined by
Let \(\Phi_\text{diff}\) denote the set of difficulty-aware operators.
Remarks.
Any associative and commutative binary operation \(\oplus\) on \(\R\) gives rise to an aggregation function by setting \(F(x_1,\ldots,x_n) = x_1 \oplus \cdots \oplus x_n\).
\(\Phi_\text{card} \subseteq \Phi_\text{diff}\): take \(d_K(q) = 1\) for all \(K\) and \(q\) and \(F(x_1,\ldots,x_n)=f(\sum_{i=1}^{n}{x_i})\).
An interesting subset of \(\Phi_\text{diff}\) consists of the ‘constant difficulty’ operators: those \(\phi_{d,F}\) such that \(d_K = d_{K'}\) for all \(K, K'\). That is, there is some fixed mapping \(d_*: \Q \to \R\) such that \(d_K(q) = d_*(q)\) for all \(K\) and \(q\).
Such operators can be seen as weighted versions of cardinality-based ones, and could model situations such as examinations where the question-setter assigns a fixed number of marks (in some sense representing difficulty) to each question ahead of time. The following result shows that any operator with IIA, source-symmetry and an additional ‘fairness’ property is of this form.
Caution
The following proof is complicated. It needs to be thoroughly checked through after some time away from it.
Theorem
Consider the following property
fairness: if \(s \simeq_K^\phi s'\) and \(q \not\in K(s) \cup K(s')\), then \(s \simeq_{K \cup \{\tuple{s,q}, \tuple{s',q}\}}^\phi s'\)
That is, \(\phi\) satisfies fairness if \(s\) and \(s'\) answering an additional question correctly affects both sources equally whenever \(s\) and \(s'\) were equally ranked to begin with.
Then if \(\phi\) satisfies IIA, source-symmetry and fairness, \(\phi = \phi_{d,F}\) for some aggregation function \(F\) and constant difficulty function \(d\).
Proof.
Suppose \(\phi\) satisfies IIA, source-symmetry and fairness.
By an earlier lemma, IIA and source-symmetry together imply that there is a total preorder \(\preceq\) on \(2^\Q\) such that \(s \le_K^\phi s'\) iff \(K(s) \preceq K(s')\). Moreover there is a function \(g: 2^\Q \to \R\) such that \(Q \preceq Q'\) if and only if \(g(Q) \le g(Q')\). Set \(d_*(q) = g(\{q\})\) (and \(d_K \equiv d_*\) for all \(K\)).
Now, for \(x_1,\ldots,x_n \in \R\), write
Write \(\X = \{\vec{x} : T(\vec{x}) \ne \emptyset\}\). Thus, \(\X\) is the set of vectors which might arise as the input to \(F\) in the definition of \(F_K(s)\). As a special case note that \(T(\tuple{}) = \{\emptyset\}\).
Our next aim is to show that all elements of \(T(\vec{x})\) are equivalent with respect to \(\preceq\). The following claims are required.
If \(Q \simeq Q'\) and \(Q \cap R = Q' \cap R = \emptyset\), then \(Q \cup R \simeq Q' \cup R\).
If \(Q = \{q_1,\ldots,q_n\}\) and \(Q' = \{q'_1,\ldots,q'_n\}\) are sets of distinct questions with \(\{q_i\} \simeq \{q'_i\}\) for each \(1 \le i \le n\), then \(Q \simeq Q'\).
For (1), we proceed by induction on \(n=|R|\). If \(n=0\) then \(R = \emptyset\), and the claim is obvious. Suppose the result holds for \(n\), and \(|R| = n + 1\). Write \(R = \{r_1,\ldots,r_{n+1}\}\). Let \(s, s'\) be arbitrary distinct sources, and construct \(K\) such that
Then \(K(s) \simeq K(s')\) by the inductive hypothesis, so \(s \simeq_K^\phi s'\). Note that \(r_{n+1} \not\in K(s)\) and \(r_{n+1} \not\in K(s')\). Write \(\hat{K} = K \cup \{\tuple{s,r_{n+1}}, \tuple{s',r_{n+1}}\}\). Then fairness gives \(s \simeq_{\hat{K}}^\phi s'\), i.e. \(\hat{K}(s) \simeq \hat{K}(s')\). But \(\hat{K}(s) = K(s) \cup \{r_{n+1}\} = Q \cup R\), and similarly \(\hat{K}(s') = Q' \cup R\). Hence \(Q \cup R \simeq Q' \cup R\) as required.
For (2), we proceed by induction on \(n\) directly. Here we take \(n=1\) as the base case; the claim is obvious in this case. Now suppose the claim holds for \(n\), and let \(Q = \{q_1,\ldots,q_{n+1}\}\), \(Q' = \{q'_1,\ldots,q'_{n+1}\}\) where \(\{q_i\} \simeq \{q'_i\}\) for each \(1 \le i \le n + 1\).
Without loss of generality, \(q_{n+1} \not\in \{q'_1,\ldots,q'_n\}\). 8 Using the inductive hypothesis and (1) twice we have
as required.
We can now show that \(Q, Q' \in T(\vec{x})\) implies \(Q \simeq Q'\). Indeed, write \(\vec{x} = \tuple{x_1,\ldots,x_n}\). By definition of \(T(\vec{x})\), \(Q\) and \(Q'\) can be enumerated as \(\{q_1,\ldots,q_n\}\) and \(\{q'_1, \ldots, q'_n\}\) respectively such that \(d_*(q_i)=x_i=d_*(q'_i)\) for each \(1 \le i \le n\). By definition of \(d_*\) and \(g\) it can be seen that \(\{q_i\} \simeq \{q'_i\}\). Property (2) above therefore gives \(Q \simeq Q'\).
Now, this means that if \(Q,Q' \in T(\vec{x})\) and \(R,R' \in T(\vec{y})\), we have \(Q \preceq R\) if and only if \(Q' \preceq R'\). We can therefore define a relation \(\sqsubseteq\) on \(\X\) by \(\vec{x} \sqsubseteq \vec{y}\) iff \(Q \preceq R\). Transitivity and totality of \(\preceq\) imply the respective properties for \(\sqsubseteq\), so this is in fact a total preorder on \(\X\).
We are now ready to define the aggregation function \(F\):
Note that \(F(\vec{x}) \le F(\vec{y})\) if and only if \(\vec{x} \sqsubseteq \vec{y}\), for \(\vec{x}, \vec{y} \in \X\).
To show that \(F\) has the symmetry required property, let \(\vec{x} = \tuple{x_1,\ldots,x_n} \in \R^n\) and \(\pi\) be a permutation of \(\{1,\ldots,n\}\). Write \(\vec{x}_\pi = \tuple{x_{\pi(1)},\ldots,x_{\pi(n)}}\). It is easy to see that \(T(\vec{x}) = T(\vec{x}_\pi)\), and thus \(\vec{x} \in \X\) iff \(\vec{x}_\pi \in \X\). If \(\vec{x},\vec{x}_\pi \not\in \X\), then \(F(\vec{x}) = 0 = F(\vec{x}_\pi)\). If \(\vec{x},\vec{x}_\pi \in \X\), then both \(\vec{x} \sqsubseteq \vec{x}_\pi\) and \(\vec{x}_\pi \sqsubseteq \vec{x}\), which means \(F(\vec{x}) = F(\vec{x}_\pi)\).
It only remains to show that \(\phi = \phi_{d,F}\). Let \(K \subseteq \S \times \Q\) and \(s, s' \in \S\). Enumerate \(K(s) = \{q_1,\ldots,q_n\}\), \(K(s') = \{r_1,\ldots,r_m\}\). Write \(\vec{x} = \tuple{d_K(q_1),\ldots,d_K(q_n)} \in \X\) and \(\vec{y}=\tuple{d_K(r_1),\ldots,d_K(r_m)} \in \X\) so that \(K(s) \in T(\vec{x})\) and \(K(s') \in T(\vec{y})\). Recall that, by definition, \(s \le_K^{\phi_{d,F}} s'\) iff \(F(\vec{x}) \le F(\vec{y})\). Hence we have
which completes the proof.
Remark. I think the converse is true if we tighten the definition of an aggregation function to require the following (quite reasonable) condition:
If \(F(x_1,\ldots,x_n) = F(y_1,\ldots,y_m)\) and \(u \in \R\), then \(F(x_1,\ldots,x_n,u) = F(y_1,\ldots,y_m,u)\).
Need to check this properly, though.
TODO:
Comment on axiom satisfaction for \(\phi_{d,F}\). It seem that most of them will depend on \(d\).
It might be worthwhile to look more closely a few specific difficulty- and aggregation-functions. Particularly intuitive ones are \(d_K(q) = -|K^{-1}(q)|\) (a question is difficult if it is not answered correctly by many sources) and \(F = \sum\) or \(F=\max\).
If instead of an ordinal operator we had a numeric version \(\phi: 2^{\S \times \Q} \to (\S \to \R)\), there is a natural symmetry between \(\phi\) and the difficulty function \(d\). This then becomes pretty similar to our TD setting, and we can look at iterative operators and coherence, etc.
Comment on the fact that this could be generalised further to penalise sources for their incorrect answers. E.g. two aggregation functions \(F_\text{correct}\), \(F_\text{incorrect}\), and then another aggregation function to aggregate the resulting scores. This might be getting a bit too complicated though.
See if chain operators (see below) fall into this class. I suspect not, because \(\phi_{d,F}\) only looks at the questions \(s\) got correct in \(K\). Going to the nearest chain graph involves adding or removing questions which means \(\phi_{d,F}\) is probably aggregating over the wrong set.
Chain Relations¶
We will say that \(K\) has the chain property if \((\S \cup \Q, K)\) is a bipartite chain graph (see also [DDLS15]).
Definition (Chain Propery)
\(K\) has the chain property if there is a total preorder \(\preceq\) on \(\S\) such that \(s \preceq t\) implies \(K(s) \subseteq K(t)\).
Write \(\ch\) for the set of all relations with the chain property.
For an arbitrary \(K\), we are interested in closest relations \(K'\) with the chain property (c.f. chain editing [DDLS15]). We also consider the closest \(K'\) obtained only by enlarging or reducing \(K\) (chain addition and deletion, respectively).
Definition
For \(K \subseteq \S \times \Q\), write
where \(X \symdiff Y = (X \setminus Y) \cup (Y \setminus X)\) is the symmetric difference of sets \(X\) and \(Y\).
Equivalently, \(m(K) = \min\{|F|: F \subseteq \S \times \Q, K \symdiff F \in \ch\}\). 9 Write \(\ch(K) = \{K' \in \ch : |K \symdiff K'| = m(K)\}\) for the set of chain relations closest to \(K\).
For the addition and deletion variants, define
and define \(\ch_\text{add}(K), \ch_\text{del}(K)\) similarly.
The chain property can be expressed more simply in terms of the neighbourhood set-inclusion relation \(\nle_K\). Note that this result is implicit in the proof of Proposition 1.4 in [JRG17].
Proposition
\(K\) has the chain property if and only if \(\nle_K\) is total.
Proof.
For the ‘if’ statement, suppose \(\nle_K\) is total. Then it is a total preorder (since \(\subseteq\) is transitive). By definition we have \(s \nle_K t\) implies \(K(s) \subseteq K(t)\), so we may take \({\preceq} = {\nle_K}\) in the definition of the chain property.
For the ‘only if’ statement, suppose \(K\) has the chain property. Let \(s, t \in \S\) and suppose \(s \not\nle_K t\). We must show \(t \nle_K s\).
Let \({\preceq}\) be as in the definition of the chain property. Since \(K(s) \not\subseteq K(t)\) we must have \(s \not\preceq t\). By totality of \({\preceq}\) we have \(t \preceq s\), i.e. \(K(t) \subseteq K(s)\) and \(t \nle_K s\) as required.
Determining \(m(K)\) may be tricky, but there is a simple lower bound available. Some basic properties regarding set differences are required first.
Lemma
\(X \setminus (X \setminus Y) = X \cap Y\)
Write \(F_+ = Y \setminus X\) and \(F_- = X \setminus Y\). Then \(Y = F_+ \cup (X \setminus F_-)\)
Let \(K, K' \subseteq \S \times \Q\) and write \(F_+ = K' \setminus K\), \(F_- = K \setminus K'\). Then if \(s, t \in \S\) satisfy \(K'(s) \subseteq K'(t)\),
\[K(s) \setminus K(t) \subseteq F_-(s) \cup F_+(t)\]
Proof.
Let \(X\) and \(Y\) be sets. For any element \(z\):
\[\begin{aligned} z \in X \setminus (X \setminus Y) & \iff (z \in X) \wedge (z \not\in X \setminus Y) \\ & \iff (z \in X) \wedge \neg(z \in X \wedge z \not\in Y) \\ & \iff (z \in X) \wedge (z \not\in X \vee z \in Y) \\ & \iff \perp \vee (z \in X \wedge z \in Y) \\ & \iff z \in X \wedge z \in Y \\ & \iff z \in X \cap Y \end{aligned}\]Using property (1) we have
\[\begin{aligned} Y &= (Y \setminus X) \cup (X \cap Y) \\ &= F_+ \cup (X \setminus (X \setminus Y)) \\ &= F_+ \cup (X \setminus F_-) \end{aligned}\]Let \(q \in K(s) \setminus K(t)\).
First suppose \(q \in K'(s)\). Since \(K'(s) \subseteq K'(t)\) we have \(q \in K'(t)\). In particular, \(q \in K'(t) \setminus K(t)\). That is, \((t, q) \in K' \setminus K = F_+\), i.e. \(q \in F_+(t)\).
Now suppose \(q \not\in K'(s)\). Then \(q \in K(s) \setminus K'(s)\), i.e. \(\tuple{s, q} \in K \setminus K' = F_-\). In particular, \(q \in F_-(s)\).
Proposition
Proof.
We will show that for any \(K' \in \ch\) and \(s, t \in \S\) it holds that \(|K \symdiff K'| \ge \min\{|K(s) \setminus K(t)|, |K(t) \setminus K(s)|\}\); from this the result follows.
Let \(K' \in \ch\) and write \(F_- = K \setminus K'\), \(F_+ = K' \setminus K\) and \(F = F_- \cup F_+\). Also write \(z = \min\{|K(s) \setminus K(t)|, |K(t) \setminus K(s)|\}\). Since \(K'\) has the chain property, either \(K'(s) \subseteq K'(t)\) or \(K'(t) \subseteq K'(s)\).
If \(K'(s) \subseteq K'(t)\), property (3) of the above lemma gives \(K(s) \setminus K(t) \subseteq F_-(s) \cup F_+(t)\). It is easy to see that \(|F_-(s) \cup F_+(t)| \le |F_- \cup F_+| = |F| = |K \symdiff K'|\). Thus
The other case is alsmost identical: if \(K'(t) \subseteq K'(s)\) then the lemma gives \(|K(t) \setminus K(s)| \le |K \symdiff K'|\).
In either case, \(z \le |K \symdiff K'|\) as required.
Note that there are some \(K\) for which this inequality is exact (e.g. \(\hat{K}=\tuple{1,2}\)), and others for which the inequality is strict (e.g. \(\hat{K}=\tuple{12,23,13}\)).
A Maximum Likelihood Interpretation¶
Consider an operator \(\phi\) which, for each input \(K\), chooses some closest chain relation \(K' \in \ch(K)\) and ranks sources according to \(\nle_{K'}\).
Definition (Chain Operator)
\(\phi\) is a chain operator if for each \(K \subseteq \S \times \Q\) there is \(K' \in \ch(K)\) such that \({\le_K^\phi} = {\nle_{K'}}\).
If instead \(K' \in \ch_\text{add}(K)\) then \(\phi\) is a chain addition operator, and if \(K' \in \ch_\text{del}(K)\) then \(\phi\) is a chain deletion operator.
Write \(\Phi_\text{chain}, \Phi_\text{chain}^\text{add}\) and \(\Phi_\text{chain}^\text{del}\) for the set of chain, chain addition and chain deletion operators respectively.
It can be seen that these operators arise from maximum likelihood considerations in a specific probabilistic model, outlined below.
The model¶
Suppose each question \(q\) has a true difficulty level \(d(q) \in \N\). Also suppose each source \(s\) has an expertise level \(e(s) \in \N\) describing the maximum difficulty level at which \(s\) is capable of giving a correct answer. That is, \(s\) is capable of answering \(q\) correctly iff \(e(s) \ge d(q)\).
We assume here that a source’s expertise is interpreted with respect to the questions being asked; they are not general expertise levels. With this in mind, the following condition is intuitive (and necessary for technical reasons later):
This just says that if \(s'\) has strictly more expertise then there should be good reason for it, i.e. there is at least one question which \(s'\) is capable of answering but \(s\) is not.
Now, the capabilities of a source in principle may not align with what is observed in reality: a source may mistakenly get an easy question wrong (a false negative) or get a difficult question right by coincidence (a false positive). Let us assume such false negatives occur with probability \(\alpha\), and false positives occur with probability \(\beta\). 10
The ingredients are now in place to define the probabilistic model. Write \(\Theta\) for the parameter space, i.e.
For each \(\tuple{s, q} \in \S \times \Q\) we have a binary random variable \(z_{s,q}\) where
Here \(z_{s,q} = 1\) represents \(s\) answering \(q\) correctly. A random variable \(K\) in \(\S \times \Q\) can now be built by sampling each \(z_{s,q}\) independently (conditioned on \(\theta\)):
where \(\comp{K}\) denotes the complement of \(K\) in \(\S \times \Q\).
Maximum likelihood estimation finds \(\theta\) which maximises \(P(K \mid \theta)\), for a fixed \(K\). This allows us to define the class of MLE operators.
Definition (MLE operator)
\(\phi\) is an MLE operator if for all \(K \subseteq \S \times \Q\) there is \(\tuple{e_K,d_K} \in \argmax_{\theta \in \Theta}{P(K \mid \theta)}\) such that for all \(s, s' \in \S\) we have \(s \le_K^\phi s'\) iff \(e_K(s) \le e_K(s')\).
Write \(\Phi_\text{MLE}(\alpha, \beta)\) for the set of MLE operators when the false negative and false positive probabilites are \(\alpha\) and \(\beta\) respectively.
The relation to the chain property¶
The parameter space \(\Theta\) is closely linked to the set of chain relations \(\ch\). Indeed, for \(\theta \in \Theta\) write
so that \(\tuple{s,q} \in K_\theta\) if and only if \(s\) is capable of answering \(q\) correctly (when the true parameters are \(\theta\)). Then \(K_\theta \in \ch\), and moreover every \(K \in \ch\) is of this form. Additionally, \({\nle_{K_\theta}}\) simply ranks sources according to \(e\).
Lemma
\(K \in \ch\) iff \(K = K_\theta\) for some \(\theta \in \Theta\).
For all \(\theta = \tuple{e,d} \in \Theta\), \(s \nle_{K_\theta} s'\) iff \(e(s) \le e(s')\).
Proof.
First we show the ‘if’ statement. Let \(\theta \in \Theta\). By an earlier proposition, to show \(K_\theta \in \ch\) it is sufficient to show that \({\nle_{K_\theta}}\) is total. Let \(s, s' \in \S\). We will show that \(e(s) \le e(s')\) implies \(s \nle_{K_\theta} s'\).
Indeed, suppose \(e(s) \le e(s')\) and let \(q \in K_\theta(s)\). Then \(d(q) \le e(s)\) by definition of \(K_\theta\), so \(d(q) \le e(s) \le e(s')\). This means \(q \in K_\theta(s')\) also. That is, \(K_\theta(s) \subseteq K_\theta(s')\) and \(s \nle_{K_\theta} s'\) as required.
For the ‘only if’ statement, suppose \(K \in \ch\). Set \(\theta = \tuple{e, d}\) where
\[\begin{aligned} e(s) &= |\{s' \in \S : K(s') \subseteq K(s)\}| \\ d(q) &= \begin{cases} \min\{e(s) : s \in K^{-1}(q)\}, & K^{-1}(q) \ne \emptyset \\ 1 + |\S|, & K^{-1}(q) = \emptyset \end{cases} \end{aligned}\]We need to show that (*) holds for this choice of \(\theta\). For this, suppose \(e(s) < e(s')\). Then transitivity of \({\subseteq}\) and totality of \({\nle_{K_\theta}}\) gives \(K(s) \subset K(s')\). This means there is \(q \in K(s') \setminus K(s)\). Let \(s''\) be the point at which the minimum is achieved in the definition of \(d(q)\), i.e. \(s \in K^{-1}(q)\) and \(d(q) = e(s'')\). Then \(q \in K(s'')\), so \(K(s'') \not\subseteq K(s)\) and therefore \(K(s) \subset K(s'')\). This means \(e(s) < e(s'')\), and so \(e(s) < e(s'') = d(q) \le e(s')\) as required. Hence \(\theta \in \Theta\).
To conclude we must show that \(K = K_\theta\), i.e. \(\tuple{s,q} \in K\) iff \(e(s) \ge d(q)\).
Suppose \(\tuple{s,q} \in K\). Then \(s \in K^{-1}(q)\). Since \(d(q)\) is the minimum of \(e(s')\) for \(s' \in K^{-1}(q)\), we clearly have \(e(s) \ge d(q)\).
Now suppose \(e(s) \ge d(q)\). Since \(e(s) \le |\S|\), we must have \(K^{-1}(q) \ne \emptyset\). Thus \(d(q) = e(s')\) for some \(s' \in K^{-1}(q)\) (i.e. \(s'\) is the source at which the minimum is achieved). Since \(K\) has the chain property, either \(K(s) \subset K(s')\) or \(K(s') \subseteq K(s)\). If the first case held, then transitivity and reflexivity of \({\subseteq}\) imply that \(e(s) < e(s')\). But then we get \(d(q) \le e(s) < e(s') = d(q)\) which is clearly a contradiction. Therefore we must be in the second case, and so \(q \in K(s') \subseteq K(s)\) implies \(q \in K(s)\) and \(\tuple{s,q} \in K\) as desried.
We have already shown in part (1) that \(e(s) \le e(s')\) implies \(s \nle_{K_\theta} s'\). For the other direction we prove the contrapositive. Suppose \(e(s) > e(s')\). Then \(K_\theta(s) \supseteq K_\theta(s')\), and by (*) there is some \(q \in \Q\) with \(e(s) \ge d(q) > e(s')\). Clearly \(q \in K_\theta(s) \setminus K_\theta(s')\), so we have \(K_\theta(s) \supset K_\theta(s')\), i.e. \(s' \nlt_{K_\theta} s\) as required.
Deriving the maximum likelihood estimate¶
Given a fixed \(K\), we need to find \(\theta\) which maximises \(P(K \mid \theta)\). First we simplify the products in \(P(K \mid \theta)\) by noting that the two cases in the definition of \(P(z_{s,q} \mid \theta)\) correspond to \(\tuple{s,q} \in K_\theta\) and \(\tuple{s,q} \in \comp{K_\theta}\) respectively. Therefore we can split each factor in \(P(K \mid \theta)\) according to whether \(\tuple{s,q} \in K_\theta\) or \(\tuple{s,q} \in \comp{K_\theta}\). We have
and similarly
Hence
Note that \(P(K \mid \theta)\) is maximised when \(\log{P(K \mid \theta)}\) is. Noting also that \(|\comp{K} \cap \comp{K_\theta}| = |\S|\cdot|\Q| - |K \cap K_\theta| - |K \cap \comp{K_\theta}| - |\comp{K} \cap K_\theta|\), we have
Note that the first term does not depend on \(\theta\), and we can write \(K \cap \comp{K_\theta}\) as \(K \setminus K_\theta\) etc. So finding an MLE estimate boils down to maximising
In general this will depend on the specific values of \(\alpha\) and \(\beta\). Simple solutions are available in special cases.
First suppose \(\alpha = \beta\); that is, false positives and false negatives occur at the same rate. Moreover suppose \(\alpha < 0.5\). Then the first term in \(L_K(\theta)\) vanishes, and writing \(\gamma = \log(\beta/(1-\beta)) = \log(\alpha(1-\beta)) < 0\) we have
Since \(\gamma < 0\), this is maximised exactly when \(|K \symdiff K_\theta|\) is minimised. An earlier lemma showed that \(K_\theta\) is always a chain graph, and that all chain graphs correspond to some \(K_\theta\). This means that \(P(K \mid \theta)\) is maximised exactly when \(K_\theta \in \ch(K)\), i.e. \(K_\theta\) is one of the closest chain graphs to \(K\).
Now consider the case where \(\beta = 0\), i.e. false positives do not occur. In other words, no sources get a question right by coincidence. It is easy to see from (**) that \(P(K \mid \theta)\) is only non-zero when \(K \cap \comp{K_\theta} = \emptyset\), i.e. \(K \subseteq K_\theta\). Amongst such \(K_\theta\), \(L_K(\theta)\) is well-defined and applying similar steps to the above we find
This is maximised when \(|K_\theta \setminus K|\) is minimised. But if \(K \subseteq K_\theta\) then \(K_\theta \setminus K = K \symdiff K_\theta\). All in all we see that \(P(K \mid \theta)\) is maximised exactly when \(K_\theta \in \ch_\text{add}(K)\).
The situation for \(\alpha = 0\) is almost identical: \(P(K \mid \theta)\) is maximal when \(K_\theta \in \ch_\text{del}(K)\). This discussion is summarised as follows.
Lemma
Take \(K \subseteq \S \times \Q\). Write \(\hat{\Theta}(\alpha, \beta) = \argmax_{\theta \in \Theta}{P(K \mid \theta)} \subseteq \Theta\) for the set of maximum likelihood estimates when the false negative and false positive rates are \(\alpha\) and \(\beta\) respectively. Then
For all \(\alpha \in (0, 0.5)\), \(\theta \in \hat{\Theta}(\alpha, \alpha)\) iff \(K_\theta \in \ch(K)\).
For all \(\beta \in (0, 1)\), \(\theta \in \hat{\Theta}(0, \beta)\) iff \(K_\theta \in \ch_\text{del}(K)\).
For all \(\alpha \in (0, 1)\), \(\theta \in \hat{\Theta}(\alpha, 0)\) iff \(K_\theta \in \ch_\text{add}(K)\).
In terms of MLE and chain operators, the above lemma tells us that the MLE operators for the special cases of \(\alpha,\beta\) coincide exactly with the chain operators. The result is as follows.
Theorem
\(\Phi_{\text{MLE}}(\alpha, \alpha) = \Phi_{\text{chain}}\) for all \(\alpha \in (0, 0.5)\).
\(\Phi_{\text{MLE}}(0, \beta) = \Phi_{\text{chain}}^\text{del}\) for all \(\beta \in (0, 1)\).
\(\Phi_{\text{MLE}}(\alpha, 0) = \Phi_{\text{chain}}^\text{add}\) for all \(\alpha \in (0, 1)\).
Proof.
We will prove the first statement only (the others are similar). Suppose \(\phi \in \Phi_{\text{MLE}}(\alpha, \alpha)\). Let \(K \subseteq \S \times \Q\). Then there is \(\theta = \tuple{e,d} \in \hat{\Theta}(\alpha, \alpha)\) such that \(s \le_K^\phi s'\) iff \(e(s) \le e(s')\). But from an earlier lemma, \(e(s) \le e(s')\) iff \(s \nle_{K_\theta} s'\). Therefore \({\le_K^\phi} = {\nle_{K_{\theta}}}\). Now note that the directly preceding lemma gives \(K_\theta \in \ch(K)\). Taking \(K' = K_\theta\) in the definition of a chain operator, we see that \(\phi \in \Phi_\text{chain}\).
Now suppose \(\phi \in \Phi_\text{chain}\). Let \(K \subseteq \S \times \Q\). Then there is \(K' \in \ch(K)\) such that \({\le_K^\phi} = {\nle_{K'}}\). The ealier lemma gives that \(K' = K_\theta\) for some \(\theta = \tuple{e,d} \in \Theta\), and that \(s \nle_{K'} s'\) iff \(e(s) \le e(s')\). That is, \(s \le_K^\phi s'\) iff \(e(s) \le e(s')\). But again, the directly preceding lemma tells us that in fact \(\theta \in \hat{\Theta}(\alpha, \alpha)\). It follows that \(\phi \in \Phi_\text{MLE}(\alpha, \alpha)\).
Misc bits¶
Things that at one stage I thought might be useful, but now appear not to be.
Lemma
Let \(K \in \ch\) and \(s, s' \in \S\). Then \(K(s) \subseteq K(s')\) if and only if for all \(q \in K(s)\) there is \(q' \in K(s')\) such that \(K^{-1}(q') \subseteq K^{-1}(q)\).
Proof.
For the ‘if’ statement, let \(q \in K(s)\) and take \(q' \in K(s')\) such that \(K^{-1}(q') \subseteq K^{-1}(q)\). Then \(s' \in K^{-1}(q') \subseteq K^{-1}(q)\), so \(q \in K(s')\). That is, \(K(s) \subseteq K(s')\).
For the ‘only if’ statement, suppose \(K(s) \subseteq K(s')\) and let \(q \in K(s)\). If \(K(s) = K(s')\), then we can just take \(q' = q\). Otherwise, \(K(s) \subset K(s')\). Take \(q' \in K(s') \setminus K(s)\).
Suppose for contradiction that \(K^{-1}(q) \subset K^{-1}(q')\). Then there is some \(t \in K^{-1}(q')\) with \(t \not\in K^{-1}(q)\), i.e. \(q' \in K(t)\) and \(q \not\in K(t)\). But this means
i.e. neither \(K(s) \subseteq K(t)\) not \(K(t) \subseteq K(s)\). This contradicts the chain property, and we are done.
- 1
E.g. \(\pi = (s, t)(s', t')\) if \(s \ne t'\) and \(s' \ne t\). In other cases the particular permuation may be different, but is guaranteed to exist.
- 2
Here \(Q \simeq Q'\) means \(Q \preceq Q'\) and \(Q' \preceq Q'\).
- 3
The proof assumes \(|\S| \ge 3\). I have not checked if the result holds for only two sources…
- 4
\(\phi_\text{count}\) is also the operator which arises if we view the questions as agents who provide an approval voting ballot, with \(q\) approving \(s\) iff \(s\) answers \(q\) correctly.
- 5
Here \(\R^0\) denotes the set containing only the empty sequence \(\tuple{}\).
- 6
Note that aggregation functions such as these are used in in belief merging (where we aggregate distances between a world and (the models of) each agent’s knowledge base) and for gradual argumentation semantics (where we aggregate the acceptability scores of attacking/supporting arguments).
- 7
The symmetry property of \(F\) ensures that \(F_K(s)\) does not depend on the enumeration chosen.
- 8
Indeed, if this assumption fails then \(q_{n+1} = q'_j\) for exactly one \(j \in \{1,\ldots,n\}\). We can relabel \(Q'\) as \(\{q''_1,\ldots,q''_{n+1}\}\) by swapping \(q'_j\) with \(q'_{n+1}\) (that is, \(q''_j = q'_{n+1}\), \(q''_{n+1} = q'_j\) and \(q''_i = q'_i\) for all \(i \not\in \{j,n+1\}\)). Then
\[\{q_{n+1}\} = \{q'_j\} = \{q''_{n+1}\} \\\]\[\{q_j\} \simeq \{q'_j\} = \{q_{n+1}\} \simeq \{q'_{n+1}\} = \{q''_j\}\]Thus our assumptions still hold, and \(q_{n+1} \not\in \{q''_1,\ldots,q''_n\}\).
- 9
The equivalence follows upon noting that \(X \symdiff (X \symdiff Y) = Y\).
- 10
Note that this assumes the false positive/negative rate is the same for all sources. This is quite a strong assumption which might not hold in practise.