Anonymity (ANON): can swap players \(i\) and \(j\) and the
ranking swaps accordingly
Homogeneity (HOM): \(\phi(kA) = \phi(A)\) for all \(k > 0\);
that is, scaling the scores by a factor of \(k\) does not affect the
rankings
Symmetry (SYM): if \(A\) is symmetric (i.e. draws in all cases)
then \(\phi(A)\) is flat
Flatness preservation (FP): if \(\phi(A)\) and \(\phi(A')\) are
flat, then so is \(\phi(A + A')\). That is, combining two tournaments
(consider two rounds of a larger tournament) for which all players are
tied results in another tied tournament
Order preservation (OP): if \(i\) ranks strictly above \(j\) in
both \(A\) and \(A'\), and if \(m_i / m_j = m'_i / m'_j\), then
\(i\) ranks strictly above \(j\) in \(A + A'\) also.
The match quotient condition aims to ‘impose some balance between the
number of matches played in \(A\) and \(A'\)’
Inversion (INV): if \(i\) is ranked (weakly) above \(j\) in
\(A\), then \(j\) is ranked (weakly) above \(i\) in
\(A^\top\).
This is a kind of symmetry between victories and losses. Richard
independently suggested this axiom in our chain graph context
Negative response to losses (NRL): Let \(\Lambda =
\text{diag}(\lambda_1,\ldots,\lambda_n)\), \(\lambda_i > 0\). Then if
\(\phi(A)\) is flat, \(i\) is ranked above \(j\) in
\(\phi(A\Lambda)\) if and only if \(\lambda_i < \lambda_j\).
Note here that \(A\Lambda\) is simply \(A\) but with the
\(i\)-th column scaled by \(\lambda_i\). That is, we scale
\(i\)’s losses by some factor \(\lambda_i\). The axiom makes
sense now: if we scale \(i\)’s losses to a lesser extent than
\(j\)’s, \(i\) should rank higher.
Score consistency (SCC): \(\phi(A)\) ranks players according to
their average score (i.e. \(s_i = \sum_{j}{A_{ij}/m_i}\)) whenever
\(A\) is round-robin.
That is, average scores are all that matter when everyone plays everyone
else the same number of times
Homogeneous treatment of victories (HTV): a stronger property: if
\(M_{ik} = M_{jk}\) for all \(k \in N \setminus \{i,j\}\) (that is,
\(i\) and \(j\) play against other players the same number of
times), then \(\phi(A)\) ranks \(i\) and \(j\) according to
their average scores
Independence of irrelevant matches (IIM): if \(A\) and \(A'\)
are identical except for possibly the \((k,l)\) and \((l,k)\)
entries, then the ranking of \(i\) and \(j\) is the same in
\(\phi(A)\) as in \(\phi(A')\), for all \(i, j \in N \setminus
\{k,l\}\)
Positive responsiveness to the beating relation (PRB): Suppose
\(i\) ranks above \(j\) in \(\phi(A)\), and that \(A'\) is
identical to \(A\) except that, for some \(k \in N \setminus
\{i\}\), \(M'_{ik}=M_{ik}\) and \(A'_{ik} > A_{ik}\). Then \(i\)
ranks strictly above \(j\) in \(\phi(A')\).
In other words, if we change \(A\) so that \(i\) beats \(k\) to
a higher extent than it did before (without changing the total number of
matches), then \(i\) should get a positive boost
Bridge player independence (BPI): The authors assume throughout that
all tournament matrices are reducible. They define the notion of a
bridge player \(b\): roughly speaking, this means that the removal of
\(b\) from \(A\) would violate irreducibility, and we would be left
with two disjoint ranking problems \((N_1,A_1)\) and \((N_2,A_2)\).
The axiom roughly says that for \(i, j \in N_1\), \(i\) ranks above
\(j\) in \(\phi(A_1)\) if and only if \(i\) ranks above
\(j\) in \(\phi(A)\).
This is a somewhat weaker form of independence of irrelevant matches, I
think
Nonnegative responsiveness to the beating relation (NNRB): same as PRB
but a weak inequality in the consequent
Self-consistent monotonicity (SCM): complicated axiom which tries to
specify a situation where it is clear that \(i\) has performed better
than \(j\) on the basis of the rankings (in \(\phi(A)\)) of the
other players. The axiom then dictates that \(i\) ranks strictly better
than \(j\).
It reminds me of our coherence axioms, since it enforces the ranking of two
objects based on the rankings of other objects with which they have
interacted. The key point is that we are talking about only one ranking
Social Choice¶
Aggregating Binary Judgments Ranked By Accuracy (2020)
Approximating optimal social choice under metric preferences (2018)
Information Aggregation, Rationality, and the Condorcet Jury Theorem (1996)
When Do Noisy Votes Reveal the Truth? (2016)
Social Ranking Manipulability for the CP-Majority, Banzhaf and Lexicographic Excellence Solutions (2020)
Automated Justification of Collective Decisions via Constraint Solving (2020)
Voting rules as error-correcting codes (2016)
Ranking participants in generalized tournaments (2005)
Paired comparisons analysis: an axiomatic approach to ranking methods (2014)
A consistent extension of Condorcet’s election principle (1978)
Collective Information (2020)
Democratic Answers to Complex Questions – An Epistemic Perspective (2006)
Judgment aggregation and the problem of tracking the truth (2012)
Automated search for impossibility theorems in social choice theory: Ranking sets of objects (2011)
Belief merging, judgment aggregation and some links with social choice theory (2005)
Aggregating Binary Judgments Ranked By Accuracy (2020)¶
(Halpern, Daniel and Kehne, Gregory and Peters, Dominik and Procaccia, Ariel D and Shah, Nisarg and Skowron, Piotr)
Summary:
Consider aggregating the binary judgements of multiple agents on a single proposition
Agents are presumed to have different reliability levels and come to their judgements independently
Focus of this paper: if we don’t know the exact reliability levels but do know the ranking of them, how should the judgements be aggregated?
Authors consider three objective functions in pursuit of the above question, and develop algorithms to maximise (or minimise, as appropriate) these objectives
Model:
\(G \in \{0,1\}\) is the unknown ground truth
\(N = \{1,\ldots,n\}\) is a set of experts
\(p_i \ge \frac{1}{2}\) is the accuracy of expert \(i\)
\(X_i\) is the judgement of \(i\): it equals \(G\) with probability \(p_i\). \(\bm{X} = (X_1,\ldots,X_n)\) is the profile of judgements
Assume a ranking of experts by accuracy is known; wlog this ranking is \(1 \succ \cdots \succ n\)
\(\mathcal{P} = \{\bm{p} \in [0, 1]^n \mid p_1 \ge \cdots \ge p_n\}\) is the set of accuracy profiles consistent with the ranking
An aggregation function is \(f: \{0,1\}^n \to \{0, 1, \perp\}\), where \(\perp\) denotes a tie
\(\mathcal{L}[\bm{X}; G = y, \bm{p}]\) denote the likelihood of observing \(\bm{X}\) when the ground truth is \(y\) and accuracy profile is \(\bm{p}\) (defined in the usual way…)
Objective functions:
Distortion: For \(y \in \{0,1\}\) and \(\bm{X} \in \{0,1\}^n\):
The intuition is (I believe) similar to other notions of distortion in the COMSOC literature. It measures the worst case ratio between an outcome that could have been chosen and the output that was chosen. It should be minimised
(A technicality: can get into some trouble if all \(p_i = 1\). Authors define \(\mathcal{P}^\epsilon\) to be those accuracy profiles with \(p_i \le 1 - \epsilon\); they then look at distortion with the supremum taken over \(\mathcal{P}^\epsilon\) and take \(\epsilon \to 0\))
Authors find \(f\) which minimises distortion using a notion of the “strength” of \(y \in \{0,1\}\) for a profile \(\bm{X}\). It is relavively straightforward to understand and can be computed in linear time
Optimistic likelihood:
Optimal algorithm is somewhat complicated: authors introduce a recursive (polynomial time) scheme to calculate the optimistic likelihood for each \(y\). The optimal aggregation function just does this for \(y=0\) and \(y=1\) and outputs the \(y\) maximising the optimistic likelihood
Pressimistic likelihood: replace the supremum above with infimum.
Interestingly, optimal rule is majority judgement, or the negation of the least accuracte judgement in the case of a tie
Scoring rules:
Given a vector of weights \(\bm{w} \ge 0\), the scoring rule \(f_{\bm{w}}\) outputs the \(y \in \{0, 1}\) maximising \(\sum_{i}{w_i \cdot \bm{1}[X_i=y]}\)
Authors look to find weights that do best w.r.t worst-case values of objective functions above
Experimental analysis: fairly elaborate setup which I have only skim read for now…
Appendices:
Axiomatic approach. Three main axioms:
Resoluteness (\(f\) should never output \(\perp\))
Foundation (\(f(y) = y\) and \(f(y, 1-y) \in \{y, \perp\}\). That is, \(f\) should agree with a single expert, and in the case of two disagreeing experts, should either output a tie or agree with the more accurate expert)
Interleaving consistency (if \(f(\bm{X}_1) = f(\bm{X}_2) = y\) then, for any \(\bm{X}\) obtained by interleaving \(\bm{X}_1\) and \(\bm{X}_2\) (taking care to preserve the ordering within each \(\bm{X}_k\)) we have \(f(\bm{X}) = y\))
These imply neutrality, and characterise a set of three rules: i) the rule \(f\) which always outputs the judgement of the first expert, ii) majority with ties broken by the first expert, iii) majority with ties broken by the negation of the last expert
Bayesian approach. Authors show how to calculate expected likelihood when the accuracy levels \(p_i\) are drawn from a (discrete) distribution with known probabilities.
Randomised rules. Such rules return output a probability distribution over \(\{0,1\}\). Authors look at finding the value \(\theta = Pr[f(\bm{X}) = 1]\) which minimises a (suitably modified) notion of distortion.
Something about scoring rules…
Approximating optimal social choice under metric preferences (2018)¶
(Elliot Anshelevich and Onkar Bhardwaj and Edith Elkind and John Postl and Piotr Skowron)
Summary:
Voters and alternatives are associated with points in a metric space
Ordinal preferences are given, which must be consistent with the metric. That is, \(X \succ_i Y\) whenever \(d(i, X) < d(i, Y)\)
A quantity called distortion measures the worst-case ratio between the output of a multi-winner voting rule (which only has access to ordinal preferences, not the metric space) and the optimal alternative
Authors look at well-known voting rules and obtain upper and lower bounds on their distortion
Distortion:
Let \(d\) be a pseudo-metric on \(\mathcal{N} \cup \mathcal{A}\), where \(\mathcal{N}\) is the set of voters and \(\mathcal{A}\) the alternatives.
The utilitarian social cost of an alternative \(X\) is \(SC_\Sigma(X, d) = \sum_{i \in \mathcal{N}}{d(i, X)}\)
For a profile of ordinal votes \(\sigma\), let \(p^{-1}(\sigma)\) be the set of pseudo-metric compatible with \(\sigma\) for each agent. The distortion of a voting rule \(f\) on profile \(\sigma\) is
The numerator represents the cost of the worst winner that was chosen by \(f\). The denominator represents the best possible alternative that could be have been chosen. The distortion is the maximum (i.e. worst-case) ratio across all metrics that could be the ‘true’ metric underlying the ordinal preferences \(\sigma\).
Some care needs to be taken in case the denominator is 0. If this is the case an all alternatives have social cost 0, the authors define the ratio to be 1; otherwise it is \(+\infty\)
Results:
Plenty of results for various well-known voting rules (see Table 1 in the paper)
In brief, positional scoring rules do poorly. Approval and veto can have distortion \(+\infty\) (i.e. they can choose an alternative with positive cost when there is some other alternative with zero cost)
Copeland rule (and some other tournament-solutions) does well; the distortion is always at most 5.
Authors also consider different social cost functions beyond the sum; namely median and percentile-based cost functions
Information Aggregation, Rationality, and the Condorcet Jury Theorem (1996)¶
(Austen-Smith, David and Banks, Jeffrey S.)
Summary:
Classical statements of Condorcet’s Jury Theorem implicitly assume voters act sincerely, i.e. vote for what they believe in
This paper shows, from a game-theoretic perspective, that insincere voting can sometimes be a better strategy for the group
The model has each voter receiving a private signal about the state of the world (hereafter \(A\) or \(B\)). Voters then make their public decision based on this signal.
This first step models information accumulation. It is after this step that voters may choose to act sincerely or otherwise.
The model:
Two alternatives \(A\) and \(B\)
Set of individuals \(N = \{1,\ldots,n\}\)
\(u_i(x, y)\) describes the utility of individual \(i\) when alternative \(x\) is selected when the correct alternative is \(y\). It is given simply by
for all \(i\)
\(\pi\) is the shared prior probability that \(A\) is the correct alternative
Each voter receives a (probabilistic) private signal \(s_i \in \{0,1\}\) (with the idea that 0 indicates the correct state is \(A\)). The (conditional) distribution of the \(s_i\) is
A voting strategy is a map \(\{0,1\} \to \{A, B\}\); a strategy tells us how an indivudal votes based on their private signal
A voting strategy \(v_i\) is sincere if \(v_i(s_i) = A\) whenever \(E[u_i(A, y) \mid s_i] > E[u_i(B, y) \mid s_i]\) (where \(y\) is a random variable representing the true state) and \(v_i(s_i) = B\) otherwise. That is, when \(v_i\) simply selects the alternative with the highest expected individual utility given the private signal.
The expected utilities can be easily calculated in terms of \(q_a, q_b\) and \(\pi\)
A voting strategy \(v_i\) is informative if it simply reveals the private signal: \(v_i(0) = A\) and \(v_i(1) = B\).
An aggregation rule is a map \(f: \{A,B\}^n \to \{A, B\}\). We consider only anonymous and montonic rules; any such rule is defined by a threshold \(k_f\) s.t. \(f\) outputs \(B\) iff the number of \(B\) votes exceeds \(k_f\).
Didn’t finish the rest: although interesting it doesn’t seem relevant enough to spend the time to go through the details at the moment.
When Do Noisy Votes Reveal the Truth? (2016)¶
(Caragiannis, Ioannis and Procaccia, Ariel D. and Shah, Nisarg)
Summary:
In the context of voting where a ‘true’ ranking exists
Question: how many voters are required to recover true rankings with high probability, for different voting rules and noise models?
Second question: which voting rules are guaranteed to return true rankings with ‘infinitely many’ voters? (i.e. find the truth in the limit)
For the first question, authors look mainly at Mallows’s noise model
For the second, noise models are parametrised by distance metrics on the set of rankings. Authors characterise the metrics for which two classes of voting rules find the truth in the limit
Preliminaries:
\(A\) is a set of \(m\) alternatives
A vote is a bijection \(\sigma: A \to \{1,\ldots,m\}\); \(\mathcal{L}(A)\) denotes the set of all possible votes
A deterministic voting rule is a mapping \(r: \bigcup_{n \ge 1}{\mathcal{L}(A)^n} \to \mathcal{L}(A)\)
A randomised voting rule instead returns a probability distribution \(r(\pi)\) over \(\mathcal{L}(A)\) for any profile \(\pi\). Write \(\Pr[r(\pi) = \sigma]\) for the probability of \(\sigma\) in \(r(\pi)\)
True ranking is denoted \(\sigma^*\)
A noise model gives a probability distribution \(Pr[\sigma \mid \sigma^*]\) over \(\sigma \in \mathcal{L}(A)\)
Number of voters required in Mallows’s model:
\(\text{Acc}^r(k, \sigma)\) denotes the accuracy of a randomised rule \(r\) on profiles of \(k\) voters when the true ranking is \(\sigma\):
That is, the probability that \(r\) will return the true ranking on any profile of length \(k\) (where profiles \(\pi\) are drawn from Mallows’s model)
\(\text{Acc}^r(k)\) denotes the minimum accuracy across all \(\sigma\)
The sample complexity of a rule \(r\) is \(N^r(\epsilon) = \min\{k \ge 1 \mid \text{Acc}^r(k) \ge 1 - \epsilon\}\), i.e. the minimum number of voters required to guarantee accuracy of at least \(1 - \epsilon\)
Result: for Mallows’s model, Kemeny’s rule with uniform tie-breaking has minimum sample complexity amongst all other rules.
Whislt this is perhaps unspurising since Kemeny’s rule is an MLE for Mallows’s model, the result does not follow from this fact alone
The PM graph of a profile \(\pi\) is the directed graph whose vertices are alternatives, with \(a \to b\) iff a strict majority of voters prefer \(a\) to \(b\)
A voting rule is PM-consistent (PM-c) if, whenever the edge relation of the PM graph is a total order \(\sigma\), we have \(Pr[r(\pi) = \sigma] = 1\). This is a generalisation of Condorcet consistency, which only requries that the top ranking alternative matches the maximum in the PM graph
Result: Any PM-c rule determines the true ranking with probability at least \(1 - \epsilon\) on profiles of size \(O(\log(m / \epsilon))\) drawn from Mallows’s model
Result: Any PM-c rule requires profiles of size at least \(\Omega(\log(m / \epsilon))\) in order to find the true ranking with probability at least \(1 - \epsilon\), for \(0 < \epsilon \le 1/2\), with respect to Mallows’s model
That is, \(\log(m / \epsilon)\) is an upper and lower bound for the number of voters required in Mallows’s model for PM-c rules
Result: The plurality rule (with randomised tie-breaking) requires a number of voters exponential in \(m\) (the number of alternatives) to find the true ranking with probability at least \(1 - \epsilon\) (technical details omitted)
Result: Any positional scoring rule with strictly decreasing weights requires a number of voters polynomial in a quantity \(\beta^*\) derived from the weights (see paper), polynomial in \(m\) and logarithmic in \(m / \epsilon\) to find the true ranking with probability at least \(1 - \epsilon\) (in Mallows’s model)
More general noise models:
A rule \(r\) is accurate in the limit if \(\lim_{n \to \infty}{\text{Acc}^r(n)} = 1\)
A wide class of rules (called PD-consistent, which include all positional scoring rules but which is disjoint from the set of PM-c rules) are accurate in the limit for Mallows’s model, so this is not so hard to achieve…
A noise model is monotonic wrt a metric \(d\) on rankings if \(d(\sigma, \sigma^*) < d(\sigma', \sigma^*)\) implies \(Pr[\sigma \mid \sigma^*] > Pr[\sigma' \mid \sigma^*]\) (and equal distance implies equal probability)
A rule \(r\) is monotone-robust wrt \(d\) if it is accurate in the limit for all \(d\)-monotonic noise models
Result: Characterisation of the distances \(d\) for which all PM-c rules are monotone-robust, and an analogous result for PD-c rules
Social Ranking Manipulability for the CP-Majority, Banzhaf and Lexicographic Excellence Solutions (2020)¶
(Allouche, Tahar and Escoffier, Bruno and Moretti, Stefano and Öztürk, Meltem)
Summary:
Authors study manipulability of methods for the social ranking from coalitions problem
Look at four existing methods
Prove manipulability for three, prove non-manipulability for the other
Prove that the problem of determining whether a situation is manipulable is NP-hard, for each method
Numerical simulations on proportion of manipulable cases for small problem size
Problem formulation:
Motivation: we have a ranking on sets of individuals (e.g. performance of teams of workers). The goal is to come up with a ranking of the individuals themselves. Formally:
\(N\) is a set of individuals
\(\mathcal{P} \subseteq 2^N\) is a collection of colatitions of individuals
A social ranking solution maps any total preorder \(\succeq\) on \(\mathcal{P}\) to a total preorder \(R^{\succeq}\) on \(N\)
Manipulability:
Idea: an individual \(i\) might try to improve their ranking by degrading the performance of coalitions to which it belongs (e.g. mess up a group project to make the other member look bad…)
The formal definition gets complicated, but I think the idea is as follows:
A manipulation of \(\succeq\) by an individual \(i\) via a collection of sets \(\mathcal{C} \subseteq \mathcal{P}\) (with \(i \in S\) for each \(S \in \mathcal{C}\)) is a new tpo \({\succeq^\mathcal{C}} \ne {\succeq}\) such that:
The relative position of coalitions not in \(\mathcal{C}\) remains the same
Each \(S \in \mathcal{C}\) now ranks strictly worse than any \(T\) it was previously weakly worse than
A ranking solution is manipulable if there exists a manipulation such that \(i\) strictly improves their position
Methods:
The Ceteris Paribus relation (Latin for “other things equal”):
For individuals \(i\) and \(j\), \(d_{ij}\) is the number of coalitions \(S \subseteq 2^{N \setminus \{i,j\}}\) such that \(S \cup \{i\} \succeq S \cup \{j\}\), i.e. the number of coalitions where, all else being equal, \(i\) is better than \(j\)
\(i\) beats \(j\) in the CP relation if \(d_{ij} \ge d_{ji}\)
Problem: CP relation is not necessarily transitive, so does not give a tpo on individuals
Copeland-like method: apply something very close to Copeland’s rule from social choice to the CP relation
Kramer-Simpson-like method: apply KS (also known as minimax) using the \(d_{ij}\)
Ordinal Banzhaf: score for \(i\) is the number of \(S\) with \(S \cup \{i\} \succeq S\), minus the number of \(S'\) with \(S' \succ S' \cup \{i\}\). It aims to look at the marginal contribution of \(i\) to coalitions to which it belongs.
Lexicographic excellence: Look at the equivalence classes of the symmetric part of \(\succeq\); construct a vector for each \(i\) where the \(k\)-th entry is the number of coalitions in the \(k\)-th from top equivalence class which contain \(i\). Then rank individuals lexicographically by these vectors.
Basically says that it’s best to be part of as many high-ranking coalitions as possible. E.g. being in one of the best but many of the worst is still better than being in lots of the second-best coalitions! This is the only non-manipulable method
Hardness of manipulability: authors present the proof for Banzhaf. I cannot really follow it, but I think the reduction is from the independent set problem.
Automated Justification of Collective Decisions via Constraint Solving (2020)¶
(Boixel, Arthur and Endriss, Ulle)
Summary:
Given a profile of preferences and a potential alternative, can the selection of this alternative be justified?
The authors’ view: justification = axioms + explanation
Idea is to justify an outcome by showing, step-by-step, how a collection of given axioms (which everyone hopefully accepts) force a particular outcome
Use constraint programming to develop an algorithm to automatically search for justifications
A key idea: rather than using axioms to justify a single voting rule to use in all situations, use instances of axioms to justify a particular outcome in a particular scenario. Very interesting idea
ILLC have made a video about the paper, available on YouTube
Basic model:
\(X\) is a set of \(m\) alternatives
\(\mathcal{L}(X)\) is the set of strict linear orders on \(X\)
\(N^*\) is the universe of \(n\) agents
A profile is a function \(N \to \mathcal{L}(X)\), for an electorate \(N \subseteq N^*\), denoted by \(\succ_N\)
\(\mathcal{L}(X)^+\) denotes the set of all profiles (over all electorates)
A voting rule is a function \(F: \mathcal{L}(X)^+ \to 2^X \setminus \{\emptyset\}\) (note: multiple winners)
Axioms under consideration:
Anonymity
Neutrality
Pareto principle: if \(x \succ_i y\) for all \(i \in N\) then \(y \not\in F(\succ_N)\)
Condorcet principle: if a majority ranks \(x^*\) above \(y\) for all \(y \ne x^*\), then \(F(\succ_N) = \{x^*\}\)
Reinforcement: If \(N \cap N' = \emptyset\) and \(F(\succ_N) \cap F(\succ_{N'}) \ne \emptyset\), then \(F(\succ_{N \cup N'}) = F(\succ_N) \cap F(\succ_{N'})\)
Cancellation: if \(\#\{i \mid x \succ_i y\} = \#\{i \mid y \succ_i x\}\) for all \(x, y\), then \(F(\succ_N) = X\)
Faithfulness: if \(\#N = 1\) then \(F(\succ_N)\) consists of the sole agent’s top-ranked alternative
\(I(A)\) denotes the set of voting rules satisfying axiom \(A\). For a set of axioms \(\mathcal{A}\), \(I(\mathcal{A})\) denotes \(\bigcap_{A \in \mathcal{A}}{I(A)}\)
Justifications:
Example 4 in the paper is a small example:
Here the Pareto principle excludes \(c\), and anonymity + neutrality enforce that \(\{a,b\}\) is selected
This ‘justification’ did not use the full power of the Pareto principle for all profiles; it is just one instance for specific alternatives and a specific profile. This can be viewed as a separate axiom \(A'\)
Write \(A' \vartriangleleft A\) when \(A'\) is an instance of A`
Definition (Justification): Take a corpus of axioms \(\mathbb{A}\). A justification for profile \(\succ_{N^*}\) and outcome \(X^*\) is a pair \((\mathcal{A}^N, \mathcal{A}^E)\) of sets of axioms (the explanatory and normative components) such that
For every \(F \in I(\mathcal{A}^E)\) we have \(F(\succ_{N^*}) = X^*\), but this does not hold for any proper subset \(\mathcal{A} \subset \mathcal{A}^E\).
That is, the axioms in \(\mathcal{A}^E\) force the result \(X^*\), and every axiom is required for this
Every axiom in \(\mathcal{A}^E\) is an instance of some \(A \in \mathcal{A}^N\)
\(\mathcal{A}^N \subseteq \mathbb{A}\)
At least one voting rule satisfies the normative axioms (\(I(\mathcal{A}^N) \ne \emptyset\))
Theorem: For a given \(\succ_{N^*}\), there are no two distinct justification with the same \(\mathcal{A}^N\) that justify different winning sets \(X^*\) and \(Y^*\)
Constraint networks:
A constraint network is a triple \(\mathcal{N} = (\mathcal{V}, \mathcal{D}, \mathcal{C})\), where
\(\mathcal{V} = (V_1,\ldots,V_\ell)\) is a sequence of variables
\(\mathcal{D} = D_1 \times \ldots \times D_\ell\) is the associated domain: variable \(V_i\) takes values in \(D_i\)
\(\mathcal{C}\) is a finite set of constraints (formulated in some suitable formal language, referring to variables in \(\mathcal{V}\) and the domain values they may take)
\(I(C) \subseteq \mathcal{D}\) is the subset of the (combined) domain satisfying constraint \(C\)
Encoding of the justification problem:
Suppose we have a profile \(\succ_{N^*}\), corpus of axioms \(\mathbb{A}\), and a set of alternative \(X^*\). We form a constraint networks where
The variables \(\mathcal{V}\) are all possible profiles (including those with agent set \(N \subset N^*\))
The domain of each variable is \(2^X \setminus \{\emptyset\}\)
For each \(A \in \mathbb{A}\) we have the constraints corresponding to all instances of \(A\), together with the special constraint \(C_\text{goal}\) which says \(V_i \ne X^*\) for all variables \(V_i\)
Second main result of the paper links justifications with minimial unsatisfiable sets of constraints in the constraint network. Essentially, find the sets of constraints (including \(C_\text{goal}\)) which are subset-minimal, and form the normative and explanatory axiom sets according to the these constraints (except \(C_\text{goal}\)). If the network with normative axiom constraints without \(C_\text{goal}\) is satisfiable, then we have found a justification
(see paper for the full statement)
Authors have a proof-of-concept implementation for 3 agents and 3 alternatives, which finds justifications for a given outcome and profile (if such justification exists)
Explanatory power of axioms:
Again looking at 3-agent and 3-alternative scenarios, the authors look at which outcomes can be justified using the 7 axioms outlined earlier
They comment on possible justifications for unique- and multiple-winner outcomes. Due to the specific 3x3 situation, each profile is either an instance of the classic Condorcet paradox, or admits a Condorcet winner. For the latter class, no multiple-winner outcome can be justified.
Voting rules as error-correcting codes (2016)¶
(Ariel D. Procaccia and Nisarg Shah and Yair Zick)
Great paper
Summary:
Considers the ‘epistemic voting’ situation, where a ground truth ranking of alternatives exists, and each agent provides a noisy version of the ground truth
Traditionally people look at noise models: assume voter errors follow some distribution and find the MLE estimate under this model
Problem: in practise a unifying noise model may not exist or may not be accurate in all cases
This paper: assume that we do not know about individual noise levels, but we have an upper bound \(t\) for the average noise across all \(n\) voters. How close can we be guaranteed to get to the true ranking (in the worse case), as a function of \(n\) and \(t\)?
Connection with coding theory: ground truth is a message we want to send. Noise voter rankings represents the message with transmission errors (potentially adversarial errors, since we look at the worst case scenario). We should find an aggregation function which tries to correct these errors. The paper looks at how well this can be done when the adversarial error is bounded.
Preliminaries:
\(A\) is a set of \(m\) alternatives
\(\mathcal{L}(A)\) is the set of total orders over \(A\)
A voting rule for \(n\) agents is a function \(f: \mathcal{L}(A)^n \to \mathcal{L}(A)\)
\(\sigma^*\) denotes the (unknown) ground truth ranking
\(d\) is a distance metric on \(\mathcal{L}(A)\)
For a profile \(\pi = \langle \sigma_1,\ldots,\sigma_n \rangle\), write \(d(\pi, \sigma^*) = \frac{1}{n}\sum_{i}{d(\sigma_i,\sigma^*)}\) for the average distance from \(\pi\) to the ground truth
Worst-case optimal rule:
If \(\sigma^*\) is known to lie in \(S \subseteq \mathcal{L}(A)\), then the optimal worse-case ranking minimises the maximum distance to rankings in \(S\):
We know \(d(\pi, \sigma^*) \le t\), i.e. \(\sigma^*\) lies in the ball of radius \(t\) around \(\pi\):
Therefore the optimal-worse case voting rule is \(f^{opt}_t(\pi) = \text{minimax}(B_t(\pi))\)
Write \(k(t, \pi)\) for \(\max_{\sigma' \in B_t(\pi)}{d(f^{opt}_t(\pi), \sigma')}\) for this minimum worse-case distance, and write \(k(t) = \max_{\pi \in \mathcal{L}(A)^n}{k(t, \pi)}\). The authors are interested in upper and lower bounds on \(k(t)\)
Results:
\(k(t) \le 2t\), i.e. whenever average distance to the ground truth is less than \(t\), it is possible to find a ranking no more than \(2t\) away from the truth. Note that this ranking might not be in \(\pi\)
There is \(\sigma \in \pi\) with \(d(\sigma, \sigma^*) \le 3t\)
Roughly speaking (see paper §3.2 onwards for details), \(k(t) \ge t / 2\). I.e. we cannot guarantee to do better than around \(t/2\) in all cases
Assuming a neutrality property on the distance metric \(d\), the lower bound improves to (roughly) \(t\)
Even better: assuming one of four commonly uses distance metrics for rankings, the lower bound improves to about \(2t\)
Remainder of the paper:
Some comments on what happens if the \(t\) we are given is actually an underestimate, and some bounds in this case.
Experimental results comparing worse-case optimal rule against commonly used rules. Authors used crowdsourcing data for which the ground truth is known, and measured rule output against ground truth wrt different metrics
Ranking participants in generalized tournaments (2005)¶
(Slutzki, Giora and Volij, Oscar)
Summary:
Axioms for ranking of participants in tournaments (c.f. González-Díaz)
Axiomatic characterisation of Fair Bets method
Preliminaries:
Setting is similar to González-Díaz, with some differences…
Matrix entries are integers
They do not assume reducibility
Ranking methods produce partial preorders orders
Axioms and results:
First few axioms concern how to rank reducible tournaments. Roughly, players are partitioned into leagues, where \(i\) and \(j\) are in the same league iff \(i\) and \(j\) both indirectly beat each other (potentially via other players). The leagues themselves can then be ranked by a strict partial order according to situations where a player in one league beats a player in another, but not vice versa.
I question the appropriateness of the term ‘league’, since players can play against others outside their ‘league’…
Axioms say that
Players in higher leagues rank above those in lower leagues
Players are incomparable iff neither player (directly or indirectly) beats the other
Rankings within a league are the same as if the ranking problem consisted solely of that league (similar to per-component independence)
These allow a ranking method defined only for irreducible tournaments to be uniquely extended to one for all tournaments. Reminds me of the kind of thing where a continuous linear operator can be uniquely extended to the whole space when defined on a dense subspace…
More axioms (already seen in González-Díaz) go on to characterise Fair Bets
Authors show that the axioms are independent, in the sense that for each axiom \(A\), one can find a ranking method which fails \(A\) only
The authors mention the duality principle that Richard and I discussed for the bipartite tournaments; namely that one can form the dual ranking method of \(\succeq\) for a matrix \(A\) by reversing the ranking yielded by \(\succeq\) in \(A^\top\)
Paired comparisons analysis: an axiomatic approach to ranking methods (2014)¶
(González-Díaz, Julio and Hendrickx, Ruud and Lohmann, Edwin)
Summary:
Axiomatic analysis of rankings methods for tournaments
Motivation: want to rank objects when we have some pairwise comparisons between them
Comparisons need not be binary (i.e. win/lose), and we need not have comparison between all pairs
Want to rank objects according to how well they perform in these comparison. The opponents matter; see the following quote.
However, in general tournaments it does not suffice to know how well an alternative has scored. We need to take into account the quality of the “opponents”.
Very nicely written paper!
Preliminaries:
A ranking problem is a pair \((N, A)\) where \(N=\{1,\ldots,n\}\) is the set of players and \(A \in \R_{\ge 0}^{n \times n}\) is the results matrix: \(A_{ij}\) is the amount player \(i\) has scored over player \(j\). We assume \(A\) is 0 on the leading diagonal.
The matches matrix is \(M = A + A^\top\). \(M_{ij}\) is the number of matches played between \(i\) and \(j\). Here we mean ‘match’ in an abstract sense; \(M_{ij}\) does not have to be an integer. Rather, \(M_{ij}\) is the total number of points scores in all comparisons between \(i\) and \(j\)
\(m = Me = M[1,\ldots,1]^\top \in \R^n\) gives the number of matches played by each player
\(A\) is called round-robin if \(M_{ij} = 1\) for all \(i \ne j\)
A ranking method \(\phi\) maps each \((N, A)\) to a total preorder on \(N\), denoted \(\phi(A)\). A preorder is often defined as the ranking induced by a rating vector \(r \in \R^n\).
\(\phi(A)\) is called flat if all players rank equally
Goes over some example ranking methods…
Axioms:
Anonymity (ANON): can swap players \(i\) and \(j\) and the ranking swaps accordingly
Homogeneity (HOM): \(\phi(kA) = \phi(A)\) for all \(k > 0\); that is, scaling the scores by a factor of \(k\) does not affect the rankings
Symmetry (SYM): if \(A\) is symmetric (i.e. draws in all cases) then \(\phi(A)\) is flat
Flatness preservation (FP): if \(\phi(A)\) and \(\phi(A')\) are flat, then so is \(\phi(A + A')\). That is, combining two tournaments (consider two rounds of a larger tournament) for which all players are tied results in another tied tournament
Order preservation (OP): if \(i\) ranks strictly above \(j\) in both \(A\) and \(A'\), and if \(m_i / m_j = m'_i / m'_j\), then \(i\) ranks strictly above \(j\) in \(A + A'\) also.
The match quotient condition aims to ‘impose some balance between the number of matches played in \(A\) and \(A'\)’
Inversion (INV): if \(i\) is ranked (weakly) above \(j\) in \(A\), then \(j\) is ranked (weakly) above \(i\) in \(A^\top\).
This is a kind of symmetry between victories and losses. Richard independently suggested this axiom in our chain graph context
Negative response to losses (NRL): Let \(\Lambda = \text{diag}(\lambda_1,\ldots,\lambda_n)\), \(\lambda_i > 0\). Then if \(\phi(A)\) is flat, \(i\) is ranked above \(j\) in \(\phi(A\Lambda)\) if and only if \(\lambda_i < \lambda_j\).
Note here that \(A\Lambda\) is simply \(A\) but with the \(i\)-th column scaled by \(\lambda_i\). That is, we scale \(i\)’s losses by some factor \(\lambda_i\). The axiom makes sense now: if we scale \(i\)’s losses to a lesser extent than \(j\)’s, \(i\) should rank higher.
Score consistency (SCC): \(\phi(A)\) ranks players according to their average score (i.e. \(s_i = \sum_{j}{A_{ij}/m_i}\)) whenever \(A\) is round-robin.
That is, average scores are all that matter when everyone plays everyone else the same number of times
Homogeneous treatment of victories (HTV): a stronger property: if \(M_{ik} = M_{jk}\) for all \(k \in N \setminus \{i,j\}\) (that is, \(i\) and \(j\) play against other players the same number of times), then \(\phi(A)\) ranks \(i\) and \(j\) according to their average scores
Independence of irrelevant matches (IIM): if \(A\) and \(A'\) are identical except for possibly the \((k,l)\) and \((l,k)\) entries, then the ranking of \(i\) and \(j\) is the same in \(\phi(A)\) as in \(\phi(A')\), for all \(i, j \in N \setminus \{k,l\}\)
Positive responsiveness to the beating relation (PRB): Suppose \(i\) ranks above \(j\) in \(\phi(A)\), and that \(A'\) is identical to \(A\) except that, for some \(k \in N \setminus \{i\}\), \(M'_{ik}=M_{ik}\) and \(A'_{ik} > A_{ik}\). Then \(i\) ranks strictly above \(j\) in \(\phi(A')\).
In other words, if we change \(A\) so that \(i\) beats \(k\) to a higher extent than it did before (without changing the total number of matches), then \(i\) should get a positive boost
Bridge player independence (BPI): The authors assume throughout that all tournament matrices are reducible. They define the notion of a bridge player \(b\): roughly speaking, this means that the removal of \(b\) from \(A\) would violate irreducibility, and we would be left with two disjoint ranking problems \((N_1,A_1)\) and \((N_2,A_2)\).
The axiom roughly says that for \(i, j \in N_1\), \(i\) ranks above \(j\) in \(\phi(A_1)\) if and only if \(i\) ranks above \(j\) in \(\phi(A)\).
This is a somewhat weaker form of independence of irrelevant matches, I think
Nonnegative responsiveness to the beating relation (NNRB): same as PRB but a weak inequality in the consequent
Self-consistent monotonicity (SCM): complicated axiom which tries to specify a situation where it is clear that \(i\) has performed better than \(j\) on the basis of the rankings (in \(\phi(A)\)) of the other players. The axiom then dictates that \(i\) ranks strictly better than \(j\).
It reminds me of our coherence axioms, since it enforces the ranking of two objects based on the rankings of other objects with which they have interacted. The key point is that we are talking about only one ranking
Results:
Table of results on axiom satisfaction for their example ranking systems. Also a characterisation of one particular ranking system
Given SYM, PRB and BPI are incompatible
Some quite interesting examples
A consistent extension of Condorcet’s election principle (1978)¶
(Young, H Peyton and Levenglick, Arthur)
Summary:
Two classical French methods for aggregating preference orders to select a winning alternative:
Borda rule: for each voter, assign a score of 1 to the least ranked alternative, 2 to the second least and so on. The winning alternative is the one with the largest total score summed over all voters
Condorcet: if there exists an alternative which beats every other in a pairwise majority, then that alternative is selected as the winner
Problem: there may not be any Condorcet winner. If there is, it is not guaranteed to coincide with the Borda winner
This papers: looks at ‘certain basic properties suggested by the Borda and Condorcet approaches’, which turn out to uniquely characterise Kemeny’s rule
Preliminaries:
\(A = \{a_1,\ldots,a_m\}\) is the set of alternatives
\(L(A)\) is the set of total orders on \(A\)
An finite electorate \(M \subseteq \{0,1,2,\ldots\}\) is the set of voters
A profile is a function \(\phi: M \to L(A)\). Write \(\Phi\) for the set of profiles
For \(\phi \in \Phi\) and \(\sigma \in L(A)\), \(n_\sigma(\phi) = |\{i \in M : \phi(i) = \sigma\}|\) (i.e. the number of voters having preferences \(\sigma\))
A preference function \(f\) maps each profile \(\phi\) to a non-empty set \(f(\phi) \subseteq L(A)\).
A choice function \(g\) maps each profile \(\phi\) to a non-empty set of alternatives \(g(\phi) \subseteq A\) (the winning alternatives)
Collective Information (2020)¶
(Endriss, Ulle)
Summary:
Non-technical ‘position paper’
Makes a case for a program of study looking at collective information: aggregate many pieces of information into a single representative piece
Research into common methodology for the problem in general could benefit many domains at the same time
Key aspect is to identify which parts of aggregation are domain-independent and domain-specific
Are there universal principles aggregation methods should adhere to?
How should the specific problem affect the method chosen?
Quote: “Is it possible to formulate general principles that are parametric in the type of information at hand?”
What?
A formal language \(\mathcal{L}\) is the domain of information in question
E.g. \(\mathcal{L}\) could be a logical language (c.f. JA), rankings of objects (c.f. voting), the set of possible crowdsourcing annotations, etc
An aggregation rule is a mapping \(F: \mathcal{L}^n \to \mathcal{L}\)
Can refine this by enforcing input and output constraints if necessary (e.g. in annotation, the output must label every item)
Why?
Democracy: voting, community-drive policy design, collective argumentation
Recommendation: TripAdvisor (aggregates reviews), reputation systems, PageRank
Science: crowdsourced annotations (training data for ML), ontology merging
How?
Axiomatic social choice
Game theory: particularly relevant for strategyproofness etc
Probability and statistics: agents’ input can be seen as noisy samples of the ‘ground truth’. Specifying some probabilistic model, techniques like MLE can recover the truth
Logic and automated reasoning: JA formulated in logic, use of SAT solvers in comsoc etc
Algorithms and complexity theory: aggregation methods are algorithms; can look at complexity etc
Whither? 1
Challenge is to “understand how the specific features of the type of information at play in a given application scenario do and should influence the design of good aggregation mechanisms”
Understanding of such would allow insights and solutions to be transferred between aggregation domains
Democratic Answers to Complex Questions – An Epistemic Perspective (2006)¶
(Bovens, Luc)
Introduces and compares premise- and conclusion-based voting procedures (for discursive dilemma-type situations)
Argues that premise-based voting is better from a democratic point of view
The paper looks to compare them from an epistemic point of view
Introduces Condorcet’s Jury Theorem
Explains how some of the assumptions of the theorem can be relaxed
e.g. the reliability of agents does not have to be constant: the result holds if the mean reliability is greater that 0.5
Seems to focus just on the discursive dilemma case: two atomic propositions and one ‘decision’ proposition which is the conjunction of the other two
Introduces a probabilistic model for voting and truth of the propositions
Analyses the probability the premise- and conclusion-based operators find the truth for whatever reasons, and find the truth for the right reasons
Summary of the rest (skimmed):
Premise-based is best for finding the truth for the right reasons
Conclusion-based can be better for finding the truth for the wrong reasons in certain situations
Needs the probability \(q\) that each atomic proposition is true to be small, and the benefit of conclusion-based diminishes as the number of voters increases.
Premise-based is basically the best over all…
The paper is more philosophical than mathematical, but it has some interesting ideas.
Judgment aggregation and the problem of tracking the truth (2012)¶
(Hartmann, Stephan and Sprenger, Jan)
Summary:
Looks at premise and conclusion based JA: agents assign truth values to logically independent propositions (the premises) and a constraint rule determines the truth value of the conclusion
Two epistemic goals: make the right decision (i.e. find the correct conclusion), and do so for the right reasons (i.e. find the correct values of the premises too).
The latter goal is truth-tracking. Authors set up a probabilistic model for JA to study this.
Preliminaries:
An agenda is of the form \(\mathcal{A} = \{A_1,\ldots,A_n,D\}\). The \(A_i\) are called the premises, and \(D\) is the conclusion.
A constraint rule \(L\) is a sentence of propositional logic which expresses that \(D\) is equivalent to some combination of the \(A_i\) (plus “preserves the logical independence of the \(A_i\)”, but I am not sure what this means precisely).
e.g. for the discursive dilemma, the premises are \(A_1, A_2\), and the constraint is \(L = D \leftrightarrow A_1 \wedge A_2\).
An admissible judgement set is an assignment of truth values to the propositions in \(\mathcal{A}\) for which \(L\) holds. The set of admissible judgement sets is denoted \(\mathcal{J}_{\bullet}^L\)
Fix \(N \in \mathbb{N}\). An aggregation procedure is a mapping \(f: (\mathcal{J}_\bullet^L)^N \to \mathcal{J}_\bullet^L\)
Truth-tracking:
TT postulate is very broad: if \(s \in \mathcal{J}_\bullet^L\) is the true situation, then \(f\) chooses \(s\).
Relative measure of TT in a probabilistic model: \(f\) tracks the truth better than \(f'\) if for all profiles \(x\) and all \(s \in \mathcal{J}_\bullet^L\) we have \(P(f(x) = s | s \text{ is true}) \ge P(f'(x) = s | s \text{ is true})\) with inequality for at least one \(s\).
Authors note that TT is not important in all situations; sometimes only the outcome matters (maybe this applies to TD in the crowdsourcing case). At other times TT is important since decisions need to be justified, and correct decisions can be overturned if made for the wrong reasons (e.g. a correct judgment made by accident in a lawsuit can be overturned if based on faulty evidence)
Probabilistic model and results:
Each agent has a competence level \(p \in (0, 1)\).
Consider a fixed profile \(x\). Let \(q(s)\) be the probability that \(s\) is the true world. The mean reliability of an aggregation procedure \(f\) is \(R_q(f) = \sum_{s \in \mathcal{J}_\bullet^L}{q(s) \cdot P(f(x) = s \mid s \text{ is true})}\).
Authors define an unbiased aggregation procedure (essentially, one can choose a subset of propositions and negate them in each agent’s judgment set before applying \(f\); then the outcome is the same as negating the propositions after applying \(f\))
Theorem: the mean reliability and truth-tracking abilities of an unbiased aggregator are independent of the probability distribution \(q\).
Theorem: if each agent has \(p > 0.5\) then the premised-based aggregation procedure (see paper) is better at tracking the truth than any other unbiased procedure for any \(N, q\).
Note: a formal proof is not given. I am not even clear what the hypotheses are: does the agents’ competence need to be the same?
Automated search for impossibility theorems in social choice theory: Ranking sets of objects (2011)¶
(Christian Geist, Ulle Endriss)
Summary:
Ranking sets of objects: social choice problem to extend a preference relation on a set \(X\) to a preference relation on \(2^X\setminus\{\emptyset\}\).
Constructs first-order language in which axioms for RSOO can be expressed
Impossibility theorems can be discovered automatically with a SAT solver (!). This is what puts the computation into computational social choice
Ranking sets of objects background:
Assumes the complete uncertainty interpretation of sets: objects in \(X\) are mutually exclusive outcomes, and a subset of objects represents a set of possible outcomes from which the final outcome is selected at a later stage. The agent does not control the selection of the final outcome from the set.
Formalism: set of objects \(X\), and a total order \(\ge\). Write \(\mathcal{X}=2^X \setminus \{\emptyset\}\); we also have a total preorder \(\succeq\) on \(\mathcal{X}\).
Seminal result in the area: Kannai-Peleg Theorem:
Impossibility result involving two axioms (when \(|X| \ge 6\))
Dominance (AKA Gärdenfors principle): if \(x > a\) for all \(a \in A\), then \(A \cup \{x\} \succ A\) (and similar for \(x < a\))
Independence: if \(x \in X \setminus (A \cup B)\) and \(A \succ B\), then \(A \cup \{x\} \succeq B \cup \{x\}\)
Big result in this paper:to prove general impossibility result it is enough to show it for \(|X| = n\) for some small \(n\). Axioms need to be expressed in a logical language and have a certain syntactical form
Many-sorted logic
Domain of discourse is partitioned into sorts (e.g. dogs, cats. Sorts are like types, not to do with sorting in the sense of ordering)
We have quantifiers for each sort, e.g. \(\forall_{\text{dog}}x\phi(x)\) means that \(\phi\) holds for each dog
In this case the sorts are \(\epsilon\) (elements of \(X\)) and \(\sigma\) (sets of elements)
MSLSP: many-sorted logic for set preferences
Defines a class of sentences (ESG) in the MSLSP logic which restricts use of existential quantifier for elements and disallows it for sets
Preservation theorem: any ESG sentence satisfied in some structure is also satisfied in any substructure
Corollary: result mentioned above re small \(n\)
TODO: finish reading
Belief merging, judgment aggregation and some links with social choice theory (2005)¶
(Eckert, Daniel and Pigozzi, Gabriella)
Summary:
Surveys the literature on judgment aggregation
Applies belief merging operator to JA
Looks at links to social choice theory
Gives overview of JA
Discursive dilemma
Condorcet’s paradox in preference aggregation can be simulated by JA (propositions are \(p_{xy}\) which represent \((x > y)\)
Failure of transitivity of aggregated preference relation is due to the discursive dilemma
Gives overview of belief merging
Propositional language \(\mathcal{L}\) with propositions \(\mathcal{P}\). Possible worlds are \(\mathcal{W} = \{0,1\}^\mathcal{P}\)
\(\mathcal{K}\) denotes the set of all belief bases, i.e. finite consistent subsets of \(\mathcal{L}\)
An integrity constraint \(IC \in \mathcal{K}\) must be believed after merging
Model-based merging: a function \(m_{IC} : \mathcal{K}^n \to [IC]\) selects a model of \(IC\) when given an input of \(n\) belief bases from agents.
The corresponding merging operator is defined by \(\Delta_{IC}(\bar{K}) = \text{form}(m_{IC}(\bar{K}))\), where \(\text{form} : \mathcal{W} \to \mathcal{L}\) maps each possible world to a formula (i.e. \([\text{form}(w)] = w\))
Distance-based merging:
A distance function \(d : \mathcal{w}^2 \to \R_{\ge 0}\) gives distance between two worlds. For a belief base \(K\) and world \(w\), one can define \(d(w, K) = \min_{w' \in [K]}{d(w, w')}\)
Consider \(\bar{K} = (K_1,\ldots,K_n)\). We can aggregate the distances \(d(w, K_i)\) with an aggregation function \(D: \R_{\ge 0}^n \to \R_{\ge 0}\). Then \(D(d(w, K_1),\ldots,d(w, K_n))\) represents the distance between \(w\) and the profile \(\bar{K}\)
For a belief profile \(\bar{K}\) we then have a total preorder on \(\mathcal{W}\): \(w \le_{\bar{K}} w'\) iff \(D(d(w,K_1),\ldots,d(w,K_n)) \le D(d(w',K_1),\ldots,d(w',K_n))\)
This induces a model-based operator: \(m_{IC}(\bar{K}) = \min([IC], \le_{\bar{K}})\) (but there might not be a unique minimum…)
Widely-used example is \(\Delta^{d,\Sigma}\): \(d\) is Hamming distance (i.e. \(d(w, w')\) is the number of propositional variables on which \(w\) and \(w'\) differ) and \(D\) is summation
Applying \(\Delta^{d,\Sigma}\) to the discursive dilemma yields a tie instead of any contradiction: the output is \(p \vee q \vee r\)
Gives link with social choice:
Here ‘social choice’ seems to mean preference aggregation
It can be shown that \(\Delta^{d,\Sigma}\) is equivalent to Kemeny’s rule for preference aggregation
Let \(X\) be a set and \(L(X)\) denote (strict) total orders on \(X\). For \(L, L' \in L(X)\), the Kemeny distance \(d_K(L, L')\) is given by \(|L \setminus L' \cup L' \setminus L|\), i.e. the number of pairs in \(X^2\) on which the two orders disagree.
For a profile of preferences \(\bar{L} = (L_1,\ldots,L_n) \in L(X)^n\), the Kemeny distance induces a total preorder \(\le_{\bar{L}}^K\) on \(L(X)\) by \(L \le_{\bar{L}}^K L'\) iff \(\sum_{i=1}^{n}{d_K(L,L_i)} \le \sum_{i=1}^{n}{d_K(L',L_i)}\)
A preference order can be translated into a belief base according to the method described above for embedding Condorcet’s paradox in JA: there is a mapping \(c : L(X) \to \mathcal{K}\). It can then be shown that, for a given profile \(\bar{L}\) and with \(\bar{K}=c(\bar{L})\), \(c\) is an order-preserving mapping from \((L(X), \le_{\bar{L}}^K)\) to \((\mathcal{K}, \le_{\bar{K}})\) (here each belief base has a unique model, so we can identify \(\mathcal{K}\) with \(\mathcal{W}\)).
Talks about the benefits of distance-based operators in different contexts
e.g. there are results showing that majority is the only sensible operator, yet it can give inconsistent outcomes.
A solution is to restrict the domain, e.g. in JA, restrict the kind of agendas that are permitted. Formally, construct an aggregation rule \(f : Z^* \to Z\) for some subset \(Z^* \subseteq Z^n\). This can be extended to all of \(Z^n\) with the use of a distance function \(d: Z^n \times Z^n \to \R_{\ge 0}\): we set \(F(\bar{Z}) = f(\text{argmin}_{\bar{Z'} \in Z^*}{d(\bar{Z}, \bar{Z'})})\).
Whither means “to what place or state”