\documentclass[runningheads,a4paper]{llncs}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{algorithm, algorithmic}
%\usepackage{natbib}

%\hoffset=-1.2truecm
%\topmargin=-0.3in\relax%
%\textheight=23.5truecm\relax%
%\textwidth=15.5truecm\relax%

%\newtheorem{theorem}{Theorem}
%\newtheorem{acknowledgement}[theorem]{Acknowledgement}
%\newtheorem{algorithm}[theorem]{Algorithm}
%\newtheorem{axiom}[theorem]{Axiom}
%\newtheorem{case}[theorem]{Case}
%\newtheorem{claim}[theorem]{Claim}
%\newtheorem{conclusion}[theorem]{Conclusion}
%\newtheorem{condition}[theorem]{Condition}
%\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{corollary}{Corollary}
%\newtheorem{criterion}[theorem]{Criterion}
%\newtheorem{definition}{Definition}
%\newtheorem{example}{Example}
%\newtheorem{exercise}[theorem]{Exercise}
%\newtheorem{lemma}{Lemma}
%\newtheorem{notation}[theorem]{Notation}
%\newtheorem{problem}[theorem]{Problem}
%\newtheorem{proposition}{Proposition}
%\newtheorem{remark}[theorem]{Remark}
%\newtheorem{solution}[theorem]{Solution}
%\newtheorem{summary}[theorem]{Summary}
%\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}

\newcommand{\OO}{\mathcal{O}}

\def\np{${\cal NP}$}
\def\real{\hbox{\rm\vrule\kern-1pt R}}
\def\nat{\hbox{\rm\vrule\kern-1pt N}}
\def\l{\ell}
\def\eps{\varepsilon}

\newcommand{\non}{\nonumber}
\newlength{\algowidth}
\setlength{\algowidth}{\textwidth}
\addtolength{\algowidth}{-2cm}
\newlength{\algowidthplus}
\setlength{\algowidthplus}{\textwidth}
\addtolength{\algowidthplus}{-15mm}

\def\ein{\mbox{}\qquad}
\def\einn{\mbox{}\qquad\qquad}
\def\einnn{\mbox{}\qquad\qquad\qquad}
\def\einnnn{\mbox{}\qquad\qquad\qquad\qquad}
\def\einnnnn{\mbox{}\qquad\qquad\qquad\qquad\qquad}
\def\einnnnnn{\mbox{}\qquad\qquad\qquad\qquad\qquad\qquad}

\def\ow{\mbox{$\overline{w}$}}
\newlength{\figwidth}
\setlength{\figwidth}{0.25\textwidth}
%\addtolength{\figwidth}{-1cm}
\begin{document}

\title{A geometric approach to paradoxes of majority voting in abstract aggregation theory}
\titlerunning{A geometric approach to paradoxes of majority voting}
\author{Daniel Eckert and Christian Klamler}

\institute{University of Graz, Institute of Public Economics, Universitaetsstr.~15, 8010 Graz, Austria,
\email{\{daniel.eckert,christian.klamler\}@uni-graz.at}}
\maketitle

\begin{abstract}
In this paper we extend Saari's geometric approach to paradoxes of preference
aggregation to the analysis of paradoxes of majority voting in a more general
setting like Anscombe's paradox and paradoxes of judgment aggregation. In
particular we use Saari's representation cubes to provide a geometric
representation of profiles and majority outcomes. Within this geometric
framework, we show how profile decompositions can be used to derive
restrictions on profiles that avoid the paradoxes of majority voting.

\end{abstract}

\institute{Institute of Public Economics\\University of Graz\\
\email{{daniel.eckert,christian.klamler}@uni-graz.at}}

\section{Introduction\label{intro}}

In the last thirty years, there have been several attempts to generalize the
Arrovian framework of preference aggregation (e.g.\ Rubinstein and Fishburn
\cite{RuFi1986} or Wilson \cite{Wi1975}). This literature on abstract
aggregation has been considerably stimulated by the growing interest in
problems of judgment aggregation. The problem of judgment aggregation consists
in aggregating individual judgments on an agenda of logically interconnected
propositions into a collective set of judgments on these propositions (see
List and Puppe \cite{LiPu2009} for a survey).

As an example of a paradox in judgment aggregation, consider a variant of the
so-called discursive dilemma, in which a committee of three recruitment
officers in a firm has to decide whether a job applicant should be hired or
not. There is a written test and an oral interview and each of them is advised
to recommend hiring the applicant if and only if the applicant passes the
written test and gives a satisfiable interview. Table \ref{job} shows the
judgments of the officers and their majority decisions.

\begin{table}[h]%
\[%
\begin{array}
[b]{c|c|c||c}%
\mbox{Officer} & \mbox{written test} & \mbox{oral interview} &
\mbox{decision}\\\hline
\mbox{Officer 1} & 1 & 1 & 1\\
\mbox{Officer 2} & 1 & 0 & 0\\
\mbox{Officer 3} & 0 & 1 & 0\\\hline
\mbox{Majority Outcome} & 1 & 1 & 0
\end{array}
\]
\caption{Discursive Dilemma}%
\label{job}%
\end{table}

Based on the majority of the individual decisions, the job applicant will not
be hired as a majority does not find her acceptable. However, a majority finds
the written test as well as the interview acceptable.

Problems of judgment aggregation are structurally similar to paradoxes and
problems in social choice theory like the Condorcet paradox and Arrow's
general possibility theorem, but also related to paradoxes of compound
majorities like the Anscombe or Ostrogorski paradoxes, both nicely analysed by
Nurmi \cite{Nu1999} (see also Nurmi \cite{Nu1987}). Contemporarily, Saari
\cite{Sa1995} has developed and popularized a geometric approach to Arrovian
social choice theory. His approach has helped to understand what drives many
of the impossibility results and paradoxes in social choice theory.

In this paper we develop - in Saari's style - a geometric approach to abstract
aggregation theory starting from the Anscombe paradox and extending this
framework to typical paradoxes in judgment aggregation.

Our approach focuses on and will be exhaustive for aggregation problems that
can be represented in the three-dimensional hypercube. While this is the
smallest dimension in which interesting aggregation problems can be formulated
and particularly illuminating for problems that naturally fall into this
framework, we have to give a warning that most of our results are not easily
extendable to more than three dimensions.

A major difference of judgment aggregation to social choice theory lies in the
representation of the information involved. While binary relations over a set
of alternatives are a canonical representation of preferences, a natural
representation of judgments are binary valuations over a set of propositions,
where the logical interconnections between these propositions determine the
set of admissible (i.e. logically consistent) valuations. E.g.\ the agenda of
the famous discursive dilemma $\{p,q,p\wedge q\}$ is associated the set of
admissible valuations $\{(0,0,0),(1,0,0),(0,1,0),(1,1,1)\}$.

The paper is structured as follows: In section 2 we introduce the formal
framework with the main definitions and properties. Section 3 discusses
paradoxes of majority voting. We will use Saari's representation cubes to
provide a unified geometric representation of profiles and majority rule
outcomes and introduce Saari's idea of a profile decomposition. In this
framework we will provide a characterization of profiles leading to the
Anscombe paradox. Section 4 applies the same tools to judgment aggregation. In
particular we show what drives the logical inconsistency of majority outcomes
and how this can be avoided with the help of restrictions on the distribution
of individual valuations, i.e.\ give a kind of generalized domain restriction.

\section{Abstract aggregation theory and majority voting: Formal framework and
central properties}

In the binary framework of abstract aggregation theory individual vectors of
binary valuations $v=(v^{1},v^{2},...,v^{|J|})$ from a set $X\subseteq
\{0,1\}^{|J|}$ of admissible valuations over the set $J$ of issues (the
agenda) are aggregated into a collective valuation. (In a slight abuse of
notation we will use the term valuation both for a the binary valuation of a
single issue as for vectors of binary valuations.)

Such an issue $j\in J$ might be the pairwise comparison between two
alternatives in preference aggregation or a proposition on which a judgment
needs to be made. Typically, the interconnections between the issues constrain
the set of admissible valuations. In judgment aggregation a valuation
$v=(v^{1},v^{2},...,v^{|J|})\in X\subseteq\{0,1\}^{|J|}$, represents an
individuals' beliefs, where $v_{{}}^{j}=1$ means that proposition $j$ is
believed and $X$ denotes the set of all admissible (logically consistent)
valuations (see Dokow and Holzman \cite{DoHo2008}).

Given a set $N$ of individuals, a profile of individual valuations is then a
mapping $\pi:N\rightarrow\{0,1\}^{|J|}$ which assigns to each individual a
vector of binary valuations. A desirable property of an aggregation rule,
stronger than non-dictatorship, is of course anonymity, which requires that
the same collective valuation be assigned to any permutation of the set of individuals.

If anonymity is assumed, a profile of individual valuations can be represented
by a vector $\mathbf{p}=(p_{1},..,p_{|X|})\in\lbrack0,1]^{|X|}$ with
$\underset{k}{\sum}p_{k}=1$, which associates with every admissible valuation
$v_{k}\in X$ the share $p_{k}$ of individuals with this valuation. Such an
anonymous representation of profiles is particularly appropriate for the
analysis of majority voting, where anonymity is typically assumed. While such
an anonymous representation is unique only up to a permutation of the original
profile, we however use the term profile for it in the following.

Geometrically any binary valuation is a vertex of the $|J|$-dimensional
hypercube and, more interestingly, any profile $\mathbf{p}\in\lbrack
0,1]^{|X|}$ can be given a lower-dimensional representation by a point
$x(\mathbf{p)}\in\lbrack0,1]^{|J|}$ in the $|J|$-dimensional $0/1$-polytope,
i.e. the convex hull of the hypercube $\{0,1\}^{|J|}$, where for each
component $j\in J$, $x^{j}(\mathbf{p)=}\underset{k\in\{1,...,|X|\}}{\sum}%
p_{k}v_{k}^{j}$ denotes the average support for issue $j$. Thus the
$|J|$-dimensional $0/1$-polytope will be referred to as the representation
polytope of the profiles.

An anonymous aggregation rule is a mapping $f$ that associates with every
profile $\mathbf{p}=(p_{1},p_{2},...,p_{|X|})\in\lbrack0,1]^{|X|}$ a valuation
$v=f(x(\mathbf{p}))\in\{0,1\}^{|J|}$.

We will write $v(\mathbf{p)}$ for $f(x(\mathbf{p}))$ and identify by
$v^{j}(\mathbf{p)}$ the $j$th component of $v(\mathbf{p)}$ under the given
aggregation rule.

In this framework majority voting on issues (or majority voting for short) is
defined as follows:

\begin{definition}
For any issue $j\in J$ and any profile $\mathbf{p\in}[0,1]^{|X|}$, $^{M}%
v^{j}(\mathbf{p)}\in\{0,1\}$ is the outcome of majority voting on issue $j$ if%
\[
v^{j}(\mathbf{p})=1\Leftrightarrow x^{j}(\mathbf{p)}>0.5\text{.}%
\]

\end{definition}

This representation immediately provides majority with a wellknown metric
rationalization in terms of the Hamming distance between binary vectors. (For
any two binary vectors $v,v^{\prime}\in\{0,1\}^{|J|}$, the Hamming distance
$d_{H}(v,v^{\prime})$ is the number of components in which these two vectors differ.)

\begin{proposition}
(Brams et al. \cite{BrKiSa2004}) For any profile $\mathbf{p\in}[0,1]^{|X|}$,
the valuation $^{M}v(\mathbf{p)}\in\{0,1\}^{|J|}$ is the majority outcome if
and only if it minimizes the sum of Hamming distances weighted by the
population shares, or formally,
\[
^{M}v(\mathbf{p)}=\underset{v\in\{0,1\}^{|J|}}{\arg\min}\sum_{k=1}^{|X|}%
p_{k}d_{H}(v_{k},v).
\]

\end{proposition}

Thus, whenever the sum of Hamming distances can be interpreted as an
appropriate measure of social disutility, majority voting can be justified by
its minimization.

Observe however that nothing in this characterisation prevents the majority
outcome $^{M}v(\mathbf{p)}\in\{0,1\}^{|J|}$ from being an inadmissible
valuation, i.e. that $^{M}v(\mathbf{p)\in}\{0,1\}^{|J|}\backslash X$.

In the hypercube, a more natural metric representation of majority voting can
be given in terms of the euclidean distance $d_{E}$.

\begin{proposition}
For any profile $\mathbf{p\in}[0,1]^{|X|}$, the valuation $^{M}v(\mathbf{p)}%
\in\{0,1\}^{|J|}$ is the majority outcome if and only if it minimizes the
euclidean distance between the corresponding vertex and the point
$x(\mathbf{p})$ in the representation polytope, or formally,
\[
^{M}v(\mathbf{p)}=\underset{v\in\{0,1\}^{|J|}}{\arg\min}d_{E}(x(\mathbf{p}%
),v).
\]

\end{proposition}

Conversely, the set of all profiles for a given majority outcome
$v\in\{0,1\}^{|J|}$ defines a subcube of $[0,1]^{|J|},P_{v}=[|v^{j}%
-0.5|]^{|J|}$, which is the set of all profiles for which $v$ is the majority
outcome. Such a subcube will be called the majority subcube of $v$ (or simply
$v$-subcube) and can be seen in Figure \ref{Pic2} for vertex $(1,0,1)$.

\begin{figure}[h]
\centering
\includegraphics{Fig1.eps}\caption{Majority subcube}%
\label{Pic2}%
\end{figure}

\section{The Anscombe paradox and the irrationality of a metric
rationalization}

Because majority voting on issues has a metric rationalization in terms of
distance minimization, it is quite disturbing that the majority outcome need
not be the one that minimizes the distance for the majority of individuals, as
the Anscombe paradox shows. In other words the Anscombe paradox states that a
majority of the voters can be on the loosing side on a majority of issues.
Formally, the Anscombe paradox can be defined in the following way:

\begin{definition}
A profile $\mathbf{p}=(p_{1},..,p_{|X|})\in\lbrack0,1]^{|X|}$ exhibits the
Anscombe paradox if
\[
\sum_{k\in\{1,...,|X|\}:d_{H}(v_{k},^{M}v(\mathbf{p}))>\frac{|J|}{2}}%
p_{k}>\frac{1}{2}%
\]

\end{definition}

Indeed, it is the particular distribution of individual valuations that leads
to the paradox. To analyse this and further paradoxes in later sections, we
will numerate the vertices of the three-dimensional hypercube as listed in
Table \ref{valuations}.

\begin{table}[h]%
\[%
\begin{array}
[b]{c|c||c|c}%
\mbox{valuation} &  & \mbox{valuation} & \\\hline
v_{1} & (0,0,0) & v_{5} & (1,1,0)\\
v_{2} & (1,0,0) & v_{6} & (1,0,1)\\
v_{3} & (0,1,0) & v_{7} & (0,1,1)\\
v_{4} & (0,0,1) & v_{8} & (1,1,1)
\end{array}
\]
\caption{Valuations in three-dimensional hypercube}%
\label{valuations}%
\end{table}

Now, consider the profile $\mathbf{p}=(\frac{2}{5},0,0,0,\frac{1}{5},\frac
{1}{5},\frac{1}{5},0)$, which specifies exactly an Anscombe paradox situation.
It is easily observed, that $x(\mathbf{p})=(\frac{2}{5},\frac{2}{5},\frac
{2}{5})$ and hence the majority outcome is $^{M}v(\mathbf{p})=(0,0,0)$.

Are we able to specify profiles that lead to an Anscombe type or other
paradoxical majority outcome? Saari \cite{Sa2008} identifies what he calls
\textquotedblright Condorcet portions\textquotedblright\ as the driving part
of paradoxes of preference aggregation.\footnote{A \textquotedblright
Condorcet portion\textquotedblright\ is a multiple of the set of individuals
that has the following preferences over 3 alternatives $a,b,c$: $a\succ
_{1}b\succ_{1}c$, $c\succ_{2}a\succ_{2}b$, $b\succ_{3}c\succ_{3}a$ leading to
the the majority cycle $a\succ b\succ c\succ a$.} In our three-dimensional
setting for abstract aggregation problems, we can consider such portions as
triples of valuations that have a common neighbor, i.e.\ a valuation that
differs from each of the three valuations in exactly one
issue.\footnote{Equivalently we could say that they are each of Hamming
distance 1 from their joint neighbor.} Given that, we can now easily specify
for every vertex in the hypercube its triple of neighbors. E.g.\ for $v_{5}$
the corresponding triple of neigbors is $(v_{2},v_{3},v_{8})$. Table
\ref{triples} indicates the triples for all eight vertices, the set of all
such triples will be denoted by $\mathcal{P}$.

\begin{table}[h]%
\[%
\begin{array}
[b]{c|c||c|c}%
\mbox{valuation} & \mbox{triple} & \mbox{valuation} & \mbox{triple}\\\hline
v_{1} & (v_{2},v_{3},v_{4}) & v_{5} & (v_{2},v_{3},v_{8})\\
v_{2} & (v_{1},v_{5},v_{6}) & v_{6} & (v_{2},v_{4},v_{8})\\
v_{3} & (v_{1},v_{5},v_{7}) & v_{7} & (v_{3},v_{4},v_{8})\\
v_{4} & (v_{1},v_{6},v_{7}) & v_{8} & (v_{5},v_{6},v_{7})
\end{array}
\]
\caption{Triples of neighbors}%
\label{triples}%
\end{table}

To analyse the paradoxical outcomes and suggest restrictions to overcome them,
we will use a profile decomposition technique developed by Saari
\cite{Sa1995}. From a majority point of view it is clear that two opposite
valuations about an issue cancel out, i.e.\ have no impact on the majority
outcome. This can, however, be extended to any number of valuations by
decomposing a profile into subprofiles:

\begin{definition}
For any profile $\mathbf{p}=(p_{1},..,p_{|X|})\in\lbrack0,1]^{|X|}$ with
$\underset{k}{\sum}p_{k}=1$ a subprofile is a vector $\underline{\mathbf{p}%
}=(\underline{p}_{1},..,\underline{p}_{|X|})\in\lbrack0,1]^{|X|}$ such that
$\underline{p}_{k}\leq p_{k}$ for all $k\in\{1,...,|X|\}$
\end{definition}

It is obvious that the above decomposition argument for two opposite
valuations does hold for any subprofile $\underline{\mathbf{p}}$ of
$\mathbf{p}$ for which $x(\underline{\mathbf{p}})=(\frac{1}{2},\frac{1}%
{2},\frac{1}{2})$. Such a subprofile does not influence the majority outcome
based on $\mathbf{p}$ at all.

As an example consider two individuals with the respective valuations $v_{2}$
and $v_{7}$. They are exact opposites, so from a majority point of view those
two valuations cancel out. Hence this implies that in any profile $\mathbf{p}%
$, for all opposite valuations we can cancel the share of the valuation held
by the smaller number of individuals (and correct for the other shares
accordingly) and still have the majority outcome unchanged.

\begin{lemma}
Let $\mathbf{p}$ and $\mathbf{p}^{\prime}$ be two profiles such that, for each
$i\in\{1,...,8\}$,
\[
p^{\prime}_{i}=\frac{max\{p_{i}-p_{9-i},0\}}{\sum_{k=1}^{4}|p_{k}-p_{9-k}|}.
\]
Then $x^{j}(\mathbf{p})\geq\frac{1}{2}\Leftrightarrow x^{j}(\mathbf{p}%
^{\prime})\geq\frac{1}{2}$.
\end{lemma}

\begin{proof}
The average support for each of the three issues can be stated as
follows:\newline$x^{1}(\mathbf{p})=p_{2}+p_{5}+p_{6}+p_{8}$\newline%
$x^{2}(\mathbf{p})=p_{3}+p_{5}+p_{7}+p_{8}$\newline$x^{3}(\mathbf{p}%
)=p_{4}+p_{6}+p_{7}+p_{8}$\newline Now, let $x^{j}(\mathbf{p})=a$ and for some
$i$, $|p_{i}-p_{9-i}|=t$, and assume w.l.o.g.\ that $1>a\geq\frac{1}{2}$ and
$0<t<a$. For $\frac{a}{1}\geq\frac{1}{2}$ we also get $\frac{a-t}{1-2t}%
\geq\frac{1}{2}$. To see this suppose this is not the case, i.e.\ $\frac
{a-t}{1-2t}<\frac{1}{2}$. It follows that $2a-2t<1-2t$. For $a\geq\frac{1}{2}$
this is false and therefore $\frac{a-t}{1-2t}\geq\frac{1}{2}$ is true. Repeat
this for all $i\in\{1,...,4\}$. For necessity just reverse the above arguments.
\end{proof}

The lemma shows that in a subprofile $\mathbf{p}^{\prime}$ at most 4 entries
can be positive. As already previously mentioned, we can reduce a profile by
any subprofile that does not change the majority outcome. Consider a
subprofile $\underline{\mathbf{p}}$ with positive shares only for the
valuations $(0,0,0)$, $(1,1,0)$, $(1,0,1)$ and $(0,1,1)$, namely
$\underline{\mathbf{p}}=(\frac{1}{8},0,0,0,\frac{1}{8},\frac{1}{8},\frac{1}%
{8},0)$. On each issue there is the same number of individuals in favor of it
and against it, i.e. $x(\underline{\mathbf{p}})=(\frac{1}{2},\frac{1}{2}%
,\frac{1}{2})$. Hence, the elimination of such a subprofile does not change
the majority outcome of the original profile and eventually increases the
number of zero entries in the profile. The only two sets of valuations useable
for such a reduction are $\{v_{1},v_{5},v_{6},v_{7}\}$ and $\{v_{2}%
,v_{3},v_{4},v_{8}\}$.

Both, the pairwise reduction as well as the reduction using 4 valuations, lead
to a reduced profile, the majority outcome of which is identical to the
majority outcome of the original profile.

Now we can use the above concepts for a result in a three-dimensional
framework, namely that the Anscombe paradox manifests itself in a particularly
strong form:

\begin{proposition}
For $|J|=3$ the Anscombe paradox will always show up in its \textit{strong
form}, i.e.\ a majority of the voters has a lower Hamming distance to the
valuation which is the exact opposite of the majority outcome than to the
majority outcome itself.
\end{proposition}

\begin{proof}
Assume, w.l.o.g., that we want the majority outcome to be $^{M}v(\mathbf{p}%
)=(0,0,0)$. As $|J|=3$, each voter $k$ among a majority of the voters needs to
have $d_{H}(v_{k},^{M}v(\mathbf{p}))\geq2$. Starting with $^{M}v(\mathbf{p}%
)=v_{1}$ this leads to the following conditions needed to be satisfied for the
Anscombe paradox to occur, where the first three conditions guarantee the
majority outcome to be $v_{1}$ and the fourth condition ensures that a
majority of voters is of a Hamming distance of at least 2 from the majority outcome:

\begin{enumerate}
\item $x^{1}(\mathbf{p})=p_{2}+p_{5}+p_{6}+p_{8}<\frac{1}{2}$

\item $x^{2}(\mathbf{p})=p_{3}+p_{5}+p_{7}+p_{8}<\frac{1}{2}$

\item $x^{3}(\mathbf{p})=p_{4}+p_{6}+p_{7}+p_{8}<\frac{1}{2}$

\item $p_{5}+p_{6}+p_{7}+p_{8}>\frac{1}{2}$
\end{enumerate}

Based on our previous decomposition argument (especially Lemma 1), no
identical change in $p_{8}$ and $p_{1}$ would change the truth of any of the
above inequalities. But this is also true for any other pair of opposite
valuations. Hence we can directly look at the reduced profile
$\mathbf{p^{\prime}}$ with at most 4 entries. For $^{M}v^{j}(\mathbf{p}%
^{\prime})=0$ it is not possible that more than half of the shares are located
on one plane of the cube, i.e.\ $p^{\prime}_{8}+p^{\prime}_{r}+p^{\prime}%
_{s}<\frac{1}{2}$ for all $r,s\in\{5,6,7\}$. But this implies that $p^{\prime
}_{r}>0$ for all $r\in\{5,6,7\}$ and hence $p^{\prime}_{1}>0$ (and therefore
$p^{\prime}_{8}=0$ to enable $^{M}v(\mathbf{p}^{\prime})=v_{1}$). Now for any
$k\in\{5,6,7\}$, $v_{k}$ is not closer to a majority of the voters' valuation
than to $^{M}v(\mathbf{p})$, as $p_{k}<\frac{1}{2}$, and this would be the
only voters with smaller distance. For any $k\in\{2,3,4\}$, $v_{k}$ is not
closer to a majority of the voters' valuation than to $^{M}v(\mathbf{p})$, as
$p^{\prime}_{r}+p^{\prime}_{s}<\frac{1}{2}$ for all $r,s\in\{5,6,7\}$ and only
two valuations out of $\{v_{5},v_{6},v_{7}\}$ are closer to $v_{k}$ than to
$^{M}v(\mathbf{p})$.
\end{proof}

\section{Judgment aggregation and the logical inconsistency of the majority
outcome}

In judgment aggregation, the issues in the agenda are logically interconnected
propositions and thus not all valuations are admissible, i.e. logically
consistent. Given the binary structure of the problem, we see that the tools
of the geometric approach can be used to analyse paradoxes of judgment
aggregation.\footnote{See e.g.\ Saari \cite{Sa2008} for a very brief
discussion of the link of his geometric approach to judgment aggregation.} The
discursive dilemma with the agenda $\{p,q,p\wedge q\}$ and the associated set
of admissible valuations $X=\{(0,0,0),(1,0,0),(0,1,0),(1,1,1)\}$ can again be
analysed in our three-dimensional hypercube, in which the four admissible
vertices determine the representation polytope as seen in Figure \ref{Pic3}.

\begin{figure}[h]
\centering
\includegraphics{Fig2.eps}\caption{Representation polytope}%
\label{Pic3}%
\end{figure}

Given the set of admissible valuations $X$, consider the profile
$\mathbf{p}=(0,\frac{1}{3},\frac{1}{3},0,0,0,0,\frac{1}{3})$, i.e.\ no voter
has valuation $(0,0,0)$, one third of the voters has valuation $(1,0,0)$, and
so on. As this maps into the point $x(\mathbf{p})=(\frac{2}{3},\frac{2}%
{3},\frac{1}{3})$ - a point whose closest vertex is $(1,1,0)$ - the
representation polytope obviously passes through the majority subcube of an
inadmissible valuation, i.e. the set of admissible valuations $X$ is not
closed under majority voting. In this case $X$ is called majority inconsistent.

That this type of paradox can easily occur with majority voting is seen from
the following lemma:

\begin{lemma}
Given any vertex $v\in\{0,1\}^{|J|}$, there exist 3 vertices $v_{a}%
,v_{b},v_{c}$ with respective shares $p_{a},p_{b},p_{c}$ such that for some
profile $\mathbf{p}$ with $p_{k}=0$ for all $k\notin\{a,b,c\}$, $x(\mathbf{p}%
)$ lies in the v-subcube.
\end{lemma}

For $|J|=3$, these 3 vertices necessarily need to have $v$ as their common
neighbor. Given that, we can now provide a simple result for the majority
inconsistency of a set of valuations $X$, i.e. a necessary condition for $X$
not to be closed under majority voting.

\begin{proposition}
For $|J|=3$, the set of admissible valuations $X$ is majority inconsistent
only if for some triple of vertices in the domain with a common neighbor, this
common neighbor is not contained in the domain.
\end{proposition}

In our 3-dimensional setting, we can easily specify all possible triples that
could lead to inadmissible majority outcomes. The reduced profile does have an
interesting feature in exactly those situations when inadmissible majority
outcomes could occur:

\begin{proposition}
For $|J|=3$, if for some $v_{i}\in\{0,1\}^{3}$ with $p_{i}\leq p_{9-i}$, each
valuation in the triple of neigbors has a larger share in $\mathbf{p}$ than
its opposite valuation, then the reduced profile $\bar{\mathbf{p}}$ has at
most 3 positive entries.
\end{proposition}

\begin{proof}
Let $\mathbf{p}=(p_{1},p_{2},...,p_{8})$ s.t.\ $\sum_{k}p_{k}=1$. From Lemma 1
we know that
\[
p^{\prime}_{i}=\frac{max\{p_{i}-p_{9-i},0\}}{\sum_{k=1}^{4}|p_{k}-p_{9-k}|}.
\]
Now in $\mathbf{p^{\prime}}$ there are at most 4 positive entries. Given that
it is not possible that $\left[  p^{\prime}_{i}>0 \wedge p^{\prime}%
_{9-i}>0\right]  $ for any $i=1,...,8$, and that for some $v_{k}$ each
valuation in the triple of neigbors has a larger share than its opposite
valuation, this only leaves two possibilities, namely that we have positive
shares at most either for all of $(p_{1},p_{5},p_{6},p_{7})$ or for all of
$(p_{2},p_{3},p_{4},p_{8})$. However, in both cases - as was discussed before
- further reductions are possible by looking for particular subprofiles. Let -
for the above two combinations - $\mathcal{A}=\{i:p^{\prime}_{i}>0\}$ be all
valuations for which there is a positive share. Then we can reduce the profile
further to profile $\bar{\mathbf{p}}$ such that
\[
\bar{p}_{i}=\frac{max_{j\in\mathcal{A}/\{i\}}\{p^{\prime}_{i}-p^{\prime}%
_{j},0\}}{\sum_{i\in\mathcal{A}}p^{\prime}_{i}-min_{j\in\mathcal{A}}p^{\prime
}_{j}}.
\]
Obviously $\bar{\mathbf{p}}$ has at most 3 positive entries.
\end{proof}

\begin{example}
Let us consider the following set of admissible valuations $X=\{v_{1}%
,v_{2},v_{3},v_{8}\}$, i.e.\ any profile $\mathbf{p}=(p_{1},p_{2}%
,p_{3},0,0,0,0,p_{8})$, where $p_{k}\geq0$ for all $k=1,2,3,8$ and $\sum
_{k}p_{k}=1$. As $v_{1}=(0,0,0)$ and $v_{8}=(1,1,1)$ are exact opposites, the
reduced profile will have a share of $0$ for the valuation held by the smaller
number of individuals. In the case of $p_{1}>p_{4}$ such a reduced profile
will be $\bar{\mathbf{p}}=(\frac{p_{1}-p_{4}}{p_{1}+p_{2}+p_{3}-p_{4}}%
,\frac{p_{2}}{p_{1}+p_{2}+p_{3}-p_{4}},\frac{p_{3}}{p_{1}+p_{2}+p_{3}-p_{4}%
},0,0,0,0,0)$, in the case of $p_{1}\leq p_{4}$ we can create the reduced
profile accordingly. Hence the reduced profile maps into one of the following
two planes shown in Figure \ref{Pic4}, namely either into the one determined
by the vertices $v_{1}$, $v_{2}$ and $v_{3}$ or the one determined by the
vertices $v_{2}$, $v_{3}$ and $v_{8}$.

\begin{figure}[h]
\centering
\scalebox{0.95}{\includegraphics{Fig3.eps}}\caption{Planes}%
\label{Pic4}%
\end{figure}

Problems may arise if the reduced profile has positive shares only for 3
valuations that constitute a triple in $\mathcal{P}$. For the above example
this would be the triple $(v_{2},v_{3},v_{8})$ on the right side of Figure
\ref{Pic4}. Now, in Figure \ref{Pic5} the intersection of this plane with the
$(1,1,0)$ majority subcube is indicated by the shaded triangle. Only if the
reduced profile maps into this triangle do inadmissible majority outcomes arise.

\begin{figure}[h]
\centering
\includegraphics{Fig4.eps}\caption{Plane T}%
\label{Pic5}%
\end{figure}
\end{example}

Now, for the 3-dimensional framework we can state the following result:

\begin{proposition}
A set of admissible valuations $X\subseteq\{0,1\}^{3}$ is majority
inconsistent if and only if for some reduced profile $\bar{\mathbf{p}}$ the
following conditions are met:\newline

\begin{enumerate}
\item $\bar{\mathbf{p}}$ has 3 positive entries

\item the 3 valuations with positive shares form a triple $(v_{a},v_{b}%
,v_{c})\in\mathcal{P}$ whose joint neighbor is not in $X$

\item the following condition holds for all $v_{k}\in\{v_{a},v_{b},v_{c}\}$
with corresponding shares $\bar{p_{k}}\in\{\bar{p_{a}},\bar{p_{b}},\bar{p_{c}%
}\}$:
\[
\frac{\bar{p_{k}}}{\bar{p_{a}}+\bar{p_{b}}+\bar{p_{c}}}\leq\frac{1}{2}%
\]

\end{enumerate}
\end{proposition}

\begin{proof}
The sufficiency part is obvious from Figure \ref{Pic5}. For necessity, it is
clear that with less than 3 positive entries in $\bar{\mathbf{p}}$ no
inadmissible outcome can occur. Moreover, any triple not in $\mathcal{P}$ is
closed under majority rule. In the case of 4 positive entries in
$\bar{\mathbf{p}}$ problems only arise in case a triple in $\mathcal{P}$ has a
positive share where the joint neigbor is not contained in $X$. But then the
fourth positive entry must be one such that the resulting profile can still be
further reduced and hence this contradicts the assumption that $\bar
{\mathbf{p}}$ was the reduced profile already. Now, the only further option is
a triple in $\mathcal{P}$ with a joint neigbor not in $X$. In this situation
inconsistency occurs exactly in the cut with the respective majority subcube
(see Figure \ref{Pic5}) whose points are specified by the condition above.
\end{proof}

One interesting feature of this result is that the complementary set of
profiles actually determines the domain that is closed under majority rule. As
those restrictions are based on the space of profiles, this approach is more
general than restrictions on the space of valuations which is usually used in
the classical literature on domain restrictions. E.g.\ List \cite{Li2005}
introduces the unidimensional alignment domain which has a certain resemblence
to Black's single peakedness condition in social choice theory. It requires
individuals to be ordered from left to right such that on each proposition
there occurs only one switch from believing it to not believing it (or vice
versa). For $|J|=3$ a unidimensional alignment domain would not satisfy one of
the above conditions for inadmissible majority outcomes.\footnote{For a more
elaborated discussion on majority voting on restricted domains see also
Dietrich and List \cite{DiLi2007}.}

\section{Conclusion}

In this paper we have shown how geometry can be used to analyse paradoxes
occuring under majoritarian aggregation and (impossibility) results in
judgment aggregation, such as inadmissible majority outcomes and distance
based aggregation rules. In addition we gave generalized domain conditions
characterizing these paradoxes and determined the likelihood of such
inadmissible majority outcomes.

Most of the stated results do not easily extend to more than three issues
because of problems of dimensionality. E.g.\ an agenda with three propositions
and their conjunction, like $\{p,q,r,p\wedge q\wedge r\}$, leads to eight
admissible valuations, i.e.\ eight vertices out of the 16 vertices in the
four-dimensional hypercube. The extensions of our (domain) restrictions and
calculations of the likelihood of the occurrence of paradoxes to those higher
dimensions are not obvious and need further work.

\begin{thebibliography}{99}                                                                                               %


\bibitem {BrKiSa2004}Brams, S.J., Kilgour M.D. and M.R. Sanver (2004): A
minimax procedure for negotiating multilateral treaties. In: Wiberg, M. (ed.):
\textit{Reasoned choices: Essays in Honor of Hannu Nurmi.} Turku, Finland:
Finnish Political Science Association

\bibitem {DiLi2007}Dietrich, F. and C. List (2007): Majority voting on
restricted domains. \textit{mimeo}

\bibitem {DoHo2008}Dokow, E. and Holzman, R. (2008), Aggregation of binary
evaluations, \textit{Journal of Economic Theory} doi:10.1016/j.jet.2007.10.004

\bibitem {Li2005}List, C. (2005): The probability of inconsistencies in
complex collective decisions. \textit{Social Choice and Welfare} 24, 3--32

\bibitem {LiPu2009}List, C. and C. Puppe (2009): Judgment aggregation. in:
Anand, P., P.K. Pattanaik, and C. Puppe (eds.), \textit{The Handbook of
Rational and Social Choice: An Overview of New Foundations and Applications}.
Oxford University Press

\bibitem {Nu1987}Nurmi, H. (1987): \textit{Comparing voting systems}. D.
Reidel, Dordrecht.

\bibitem {Nu1999}Nurmi, H. (1999): \textit{Voting paradoxes and how to deal
with them}. Springer, Berlin

\bibitem {RuFi1986}Rubinstein, A. and P.C. Fishburn (1986): Algebraic
aggregation theory. \textit{Journal of Economic Theory} 38, 63--77

\bibitem {Sa1995}Saari, D.G. (1995): \textit{Basic geometry of voting}.
Springer, Berlin

\bibitem {Sa2008}Saari, D.G. (2008): \textit{Disposing dictators, demystifying
voting paradoxes: Social choice analysis}. Cambridge University Press, New York

\bibitem {Wi1975}Wilson, R. (1975): On the theory of aggregation.
\textit{Journal of Economic Theory} 10, 89--99
\end{thebibliography}


\end{document}