\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{Committee Selection with a Weight Constraint Based on Lexicographic Rankings of Individuals}
\titlerunning{Committee Selection with a Weight Constraint}
% \author{Christian Klamler  {\footnotemark[1]} \and
% Ulrich Pferschy {\footnotemark[7]} \and
% Stefan Ruzika {\footnotemark[3]} }
%
% \date{}
%
% \maketitle
%
% \renewcommand{\thefootnote}{\fnsymbol{footnote}}
% \footnotetext[1]{University of Graz, Institute of Public Economics, Universitaetsstr.~15,
% 8010 Graz, Austria, \texttt{christian.klamler@uni-graz.at}}
% \footnotetext[7]{University of Graz, Department of Statistics and Operations Research,
% Universitaetsstr.~15, 8010 Graz, Austria,
% \texttt{pferschy@uni-graz.at}}
% \footnotetext[3]{University of Kaiserslautern, Department of Mathematics, P.O.Box 3049, 67653 Kaiserslautern, Germany,
% \texttt{ruzika@mathematik.uni-kl.de}}
% \renewcommand{\thefootnote}{\arabic{footnote}}

\author{Christian Klamler\inst{1} \and
Ulrich Pferschy\inst{2} \and
Stefan Ruzika\inst{3}}

\institute{University of Graz, Institute of Public Economics, Universitaetsstr.~15, 8010 Graz, Austria,
\email{christian.klamler@uni-graz.at}
\and
University of Graz, Department of Statistics and Operations Research Universitaetsstr.~15, 8010 Graz, Austria,
\email{pferschy@uni-graz.at}
\and
University of Kaiserslautern, Department of Mathematics, P.O.Box 3049, 67653 Kaiserslautern, Germany,
\email{ruzika@mathematik.uni-kl.de}
\footnote{
Stefan Ruzika was partially supported by Deutsche Forschungsgemeinschaft (DFG) grant 1737/7 "Algorithmik gro\ss er und komplexer Netze" and by the Rheinland-Pfalz cluster of excellence "Dependable adaptive systems and mathematical modeling".}}
\maketitle
 % typeset the title of the contribution

\begin{abstract}
\noindent
We investigate the problem of selecting a committee consisting of $k$ members from a list of $m$ candidates.
The selection of each candidate consumes a certain weight (or cost).
Hence, the choice of the $k$-committee has to satisfy a weight (or budget) constraint:
The sum of the weights of all selected committee members must not exceed a given value $W$.
While the former part of the problem is a typical question in Social Choice Theory, the latter stems from Discrete Optimization.
The purpose of our contribution is to link these two research fields:
We first define reasonable ways of ranking sets of objects, i.e.\ candidates, and then develop efficient algorithms for the actual computation of optimal committees.
We focus in particular on the running time complexity of the developed algorithms.

\vspace*{1ex}
\noindent
\textbf{Keywords:} knapsack constraint, committee selection.
\end{abstract}


\section{Introduction}


Social Choice Theory deals with the aggregation of individual preferences on sets of objects (candidates, alternatives, etc.) into a group outcome, which could either be a ranking or a set of chosen objects. Usual results focus on situations in which no other than logical restrictions are put on the possible group outcomes, an exception being Barbera et al.~\cite{BaMaNe2005}. Such restrictions could be of various forms, obvious examples being weight, cost or size constraints on the set of chosen alternatives.

A possible example for such a situation could be a sports club and a team of managers that have to decide on who to recruit for the next season. The managers' preferences might differ based on their different foci such as technical qualities or advertising value. Moreover, the club might have a restricted budget to buy new players who all have their market values and the club probably needs exactly a certain number of players, i.e.\ the set of possible new players is restricted to certain subsets.

In this article we want to select a committee of a predefined size from a set of candidates given certain restrictions.
The selection will depend on a social preference over the set of candidates
derived from one of the voting rules provided in the social choice literature
(see Brams and Fishburn~\cite{BrFi2002}).
%provides a huge amount of voting rules, such as simple majority rule, the Borda rule or
%approval voting
%(see e.g.\ Brams and Fishburn~\cite{BrFi2002}, Nurmi~\cite{Nu1987, Nu1999}, Saari~\cite{Sa1995}).
%The determination of a social preference is not discussed in the present article
%and assumed to be given.
Based on such a preference relation we consider the ranking of subsets of candidates.
Some of those rankings of subsets, e.g.\ based on best and/or worst candidates in the corresponding ranking of candidates, have been thoroughly analysed in Barbera et al.~\cite{BaBoPa}.
%However, based on concepts such as risk aversion and risk loving
We will add two new ranking options recently characterized by Klamler et al.~\cite{klpfru09}.
%- to the best of our knowledge - have not yet been considered in the literature.
%(with the notable exception of a working paper by Tang and Xu \cite{TaXu2007}).
%Characterizations of such rankings can be found in

In this contribution we want to check whether there exist applicable algorithms that compute such optimal committees with respect to the underlying ranking criterion. Given a social preference on the set of candidates and the desired conditions for ranking sets of candidates we will provide the correct algorithm to compute the committee.

This article tries to solve questions raised in Social Choice Theory by solution methods discussed in 
Operations Research and thus provides an interesting interdisciplinary link between these areas.
Efforts along these lines were also made in
Klamler and Pferschy~\cite{klpf05}, Darmann et al.~\cite{dkp08} and Perny and Spanjaard \cite{PeSp2005}
who introduce preference relations on different graph structures.

In Section~\ref{sec:frame} we will introduce the formal framework.
Sections~\ref{sec:GenericAlgorithms} and~\ref{sec:Improvements} present and discuss algorithms used to determine the optimal committees. Section \ref{sec:Conclusion} concludes the paper.
%Finally, Section~\ref concludes the paper.


\section{Formal Framework}
\label{sec:frame}

Let $X$ be a finite set of $m$ alternatives (or candidates). We define a preference on $X$ by a reflexive, complete and transitive binary relation $R\subseteq X\times X$, where $(x,y)\in R$ means that $x$ is at least as good as $y$, also written as $xRy$.\footnote{A binary relation $R$ is reflexive if and only if for all $x\in X$, $xRx$, it is complete if and only if for all $x,y\in X$, $xRy$ or $yRx$, and it is transitive if and only if for all $x,y,z\in X$, $xRy$ and $yRz$ imply $xRz$.} The asymmetric and symmetric parts of $R$ are written as $P$ and $I$ respectively. The set of all reflexive, complete and transitive binary relations is written as $\mathcal{R}$.

Let $\mathcal{X}$ denote the set of all subsets of $X$. A preference on $\mathcal{X}$ is a relation $\succsim\,\subseteq \mathcal{X}\times\mathcal{X}$. The strict preference relation and the indifference relation are denoted by $\succ$ and $\sim$ respectively.
%In case two sets $A,B\in\mathcal{X}$ are not comparable we write $A\bowtie B$.

For any $A\in\mathcal{X}$ we say that the set of best elements in $A$ according to $R$ is $max(A,R)=\{x\in A: \forall y\in A, xRy\}$.
Conversely, the set of %R-worst
worst elements in $A$ is $min(A,R)=\{x\in A: \forall y\in A, yRx\}$.\footnote{Whenever clear from the context, $max(A,R)$ ($min(A,R)$) will be written as $max(A)$ ($min(A)$).}
Whenever not mentioned otherwise we will also assume that the alternatives in $A=\{a_1,a_2,...,a_k\}$
are ordered, i.e., it is the case that $a_iRa_j$ for $i<j$.

In our model every alternative $j\in X$ is assigned a weight (or cost) $w_j \in \real_+$, where $w=(w_1,w_2,...,w_m)$.
The total weight bound is $W>0$.
For convenience, in the remainder of the paper we will denote $w(S)= \sum_{i\in S}w_i$ for any subset $S$ of alternatives.
In addition, throughout this article we will exclusively focus on situations where we select and compare sets of a particular cardinality. Hence, let $\mathcal{X}_k$ be the set of subsets containing exactly $k\leq m$ alternatives and $\mathcal{X}_k^W$ the set of subsets $S$ containing exactly $k\leq m$ alternatives such that $\sum_{i\in S}w_i\leq W$.

This inequality is known in the Operations Research literature as knapsack constraint
and was widely studied as an optimization problem in its own right (see Kellerer et al.~\cite{kpp04})
and as a side constraint for other problems.
In particular, knapsack problems with a cardinality constraint were considered by Caprara et al.~\cite{ckpp00}.
% NEU
However, in the latter each candidate is assigned a certain profit value and the quality of a committee is given
by the sum of profits over all candidates.
This generalization of the standard knapsack problem is \np-hard,
while the preference based valuations of committees in this paper permit polynomial time algorithms.
Moreover, the algorithms from~\cite{ckpp00} do not apply to our problems.


A \emph{k-committee selection function with constraint} is a function $C:\mathcal{R}\times \real_+^m \rightarrow \mathcal{X}_k^W$ that assigns to every preference $R \in \mathcal{R}$ and weight profile $w \in \real_+^m$ the $k$-committee $C(R,w)\in \mathcal{X}_k^W$.

Throughout this article the quality of a committee is based on the quality (i.e.\ ranking position) of its candidates with respect to the social preference on the set of candidates. Hence, let $k'\leq k$ denote the $k'$-best position of a candidate in a committee with respect to the social preference on $X$. One possibility of ranking sets $A,B\in\mathcal{X}$ is to compare the quality of the candidates in the $k'_1$-position in $A$ and $B$, respectively. Some of those rules are also lexicographic by nature, i.e., in case society is indifferent between the candidates in $k'_1$-position, the sets are compared according to some other $k'_2$-position. Further extensions up to the usual lexicographic rule, by starting with the best candidates and going down to the worst, are feasible.


Although there exist various ways of ranking sets in $\mathcal{X}$ that fall in particular into the class of $(k'_1,k'_2)$-rules which compare the candidate in $k'_1$-position first and - in case of indifference - move on to comparing candidates in $k'_2$-position, certain simple $k'$-rules have not been extensively studied yet. The special - and most intuitive - cases here are the $k'=1$ case which compares sets according to their best alternatives and which will be called \emph{Maximize Max Ordering}. Analogously we could have $k'=k$, i.e.\ sets are ranked according to their worst candidates contained. This will be called \emph{Maximize Min Ordering}.
%A characterization of these orderings follows in Section~\ref{sec:characterization}.
%All other set orderings used in this paper have been extensively discussed in the literature %already and we refer the reader to the survey by Barbera et al.~\cite{BaBoPa}.

Naturally, choosing committees according to set orderings
raises questions about the computational complexity.
The computation of a committee based on the \emph{Maximize Max Ordering} can be done in linear time. This is an improvement to the general case of \textsc{$k'$-Max} and, surprisingly, this improvement does not carry over to the \emph{Maximize Min Ordering}.\footnote{Beware that $k'$-Max for $k'>1$ also contains the interesting "Median" ordering based on the median element(s) of the ranking of candidates.}


As previously mentioned, we will also discuss usual lexicographic rules.\footnote{Characterizations of lexicographic rules can be found in Pattanaik and Peleg \cite{PaPe1984}.} Let $A,B\in\mathcal{X}_k$. The {\em leximin ordering} $\succsim_{min}^L$ is defined by letting for all $A,B\in\mathcal{X}_k$
\[A\succsim_{min}^L B \Leftrightarrow a_i I b_i\ \forall\, i\ \mbox{or}\ \exists j\in \{1,...k\}\
\mbox{such that}\ a_iI b_i\ \forall\, i>j\ \mbox{and}\ a_jP b_j . \]

\noindent
Analogously, we can define the {\em leximax ordering} $\succsim_{max}^L$ by letting for all $A,B\in\mathcal{X}_k$ %s.t.
\[A\succsim_{max}^L B \Leftrightarrow a_i I b_i\ \forall\, i\ \mbox{or}\ \exists\, j\in \{1,...k\}\
\mbox{such that}\ a_iI b_i\ \forall\, i<j\ \mbox{and}\ a_jP b_j .\]
To give an overview, the computational complexities of the algorithms discussed in this paper
are given in Table~\ref{tab:complex}.
\begin{table}[h]
\begin{center}
\begin{tabular}{l@{\quad}l}
Algorithm / Ordering & Computational Complexity\\
\hline \hline
\textsc{$k'$-Max} & $\OO(m \log k)$ \\
\textsc{MaximizeMax} & $\OO(m)$ \\
\hline
\textsc{$(k'_1,k'_2)$-Max} & $\OO(m \log k)$ \\
\hline
\textsc{$(k'_1, \dots k'_k)$-Max} & $\OO(km \log k)$ \\
\textsc{LexiMin} & $\OO(m \cdot \min \{ k ,  \log m \} )$ \\
\textsc{LexiMax} & $\OO(m + k \log k)$\\
\hline
\end{tabular}
\end{center}
\caption{Overview of complexity results\label{tab:complex}}
\end{table}


%\vspace*{-10mm}

\section{Generic Algorithms}
\label{sec:GenericAlgorithms}
%Having proposed different preference relations for ranking sets of objects
%subject to a knapsack side constraint, the question of how to compute efficiently
%a most preferred committee suggests itself.
In this section we address the generic preference relations \textsc{$k'$-Max}, \textsc{$(k'_1,k'_2)$-Max} and \textsc{$(k'_1, \dots ,k'_k)$-Max} and consider general algorithms for committee selection based on these relations.
Efficient algorithms (in terms of asymptotic complexity) can be formulated when using adequate data structures.% for handling the set of alternatives.


Priority queues %are abstract data structures
allow to assign a key value to its elements. This key defines a sorting on the elements of the queue. In our case, this key can either be the weight value of an element or a number being consistent with the preference relation of the elements in $X$.
Using either of these values, the priority queue can be minimum or maximum ordered.
In a minimum ordered priority queue the top-most element has a minimal key among all elements left in the priority queue.
We use Fibonacci heaps (see \cite[Sec.~20]{clr01}) for implementing priority queues.
Table~\ref{tab:fibo} surveys the most relevant priority queue operations together with their amortized complexities.
\begin{table}[htp]
\begin{center}
\begin{tabular}{lll}
\hline
\textsc{Make}() & creates empty priority queue $Q$ & $\OO (1)$\\
\textsc{Insert}($Q,x$) & allows insertion of element $x$ in $Q$ & $\OO (1)$\\
\textsc{Top}($Q$) & accesses the top-most element of $Q$ & $\OO (1)$\\
\textsc{Extract-Top}($Q$) & deletes the top-most element of $Q$ & $\OO (\log n )$\\
\hline
\end{tabular}
\end{center}
\caption{Priority queue operations - brief description and amortized complexities.\label{tab:fibo}}
\end{table}

%\vspace*{-5mm}
%In this section we show how to apply
These four operations will be applied to select committees efficiently for the general cases of the three orderings \textsc{$k'$-Max}, \textsc{$(k'_1,k'_2)$-Max} and
\textsc{$(k'_1, \dots , k'_k)$-Max}.
Priority queues will represent different orderings
%to be minimum \emph{or} maximum ordered with respect to the weight value
%\emph{or} the preference ranking -
depending on what suits our needs best.

Consider the \textsc{$k'$-Max} ordering for $k' \leq k$. Let $Q_A, Q_B$ be \emph{maximum weight ordered} priority queues.
Thus, the top-most element has largest weight among all elements in the queue, i.e., $\textsc{Top}(Q)$ accesses the \emph{heaviest} element in the queue. We introduce two auxiliary arrays $A[j]$ and $B[j]$ of length $m$ with the following definition:
% NEU
$A[j]$ and $B[j]$ contain the total weight of the subset consisting of the $k'-1$ and $k-k'$ items of smallest weight among all items ranked higher and lower than~$j$, respectively, as illustrated in the following example.

\medskip
\noindent
{\bf Example:}

\smallskip
\setlength{\tabcolsep}{1ex}
\begin{tabular}{l|llll|l|llll|}
element & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\hline
weight & 8 & 6 & 9 & 3 & 6 & 2 & 5 & 7 & 1
\end{tabular}

\medskip
The elements are numbered in decreasing order of their ranking.
Let $k=6$, $k'=4$ and $j=5$.
Then we have $A[5]=8+6+3=17$ and $B[5]=2+1=3$.

\medskip
Algorithm \ref{alg:generic} first computes the entries of these arrays by keeping the current subset of these items in a priority queue.
Then, the best ranked $k'$th largest item in a feasible $k$-committee can be determined in a single run over these two arrays $A$ and $B$
by looking for the best ranked item such that an appropriate number of smallest weight elements ranked higher and lower fulfill the weight constraint.

We assume that a feasible solution exists (otherwise the while-loop would not terminate).
To reconstruct the subset yielding the optimal solution (i.e.\ the feasible committee) we repeat the two for-loops but stop as soon as the index reaches the $k'$th element found before.


\begin{algorithm}
\textsc{Max$(L,W,k,k')$}\vspace{0.1cm} \\
\textbf{Input:} A list $L := \{ e_1 , \dots , e_m \}$ representing the ranking of $m$ elements;\\
a weight bound $W \in \mathbb{R}$, $k \in \mathbb{N}$ and $k' \in \mathbb{N}$, $k' \leq k$.\\
\textbf{Output:} The maximal $k'$-element for which a feasible $k$-committee exists.

\begin{algorithmic}[1]
\FORALL{$i \leftarrow 1 , \dots , k'-1$}\label{alg:for1}
\STATE \textsc{Insert}($Q_A, e_i$)
%\STATE $w(Q_A) \leftarrow w(Q_A) + w(e_i)$
\ENDFOR\label{alg:for2}
\STATE $A[k'] \leftarrow w(Q_A)$\label{alg:for3}
\FORALL{$ j \leftarrow k', \ldots, m-(k-k'+1)$}
\IF{$w(e_j) < w(\textsc{Top}(Q_A))$}\label{alg:if1}
        \STATE \textsc{Extract-Top}($Q_A$)
%       \STATE $w(Q_A) \leftarrow w(Q_A) - w$(\textsc{TOP($Q_A$)})
        \STATE \textsc{Insert}($Q_A, e_j)$)
%        \STATE $w(Q_A) \leftarrow w(Q_A) + w(e_j)$
\ENDIF\label{alg:if2}
\STATE $A[j+1] \leftarrow w(Q_A)$\label{alg:if3}
\ENDFOR
\FORALL{$i \leftarrow m-(k-k') + 1 , \dots , m$}
\STATE \textsc{Insert}($Q_B, e_i$)
%\STATE $w(Q_B) \leftarrow w(Q_B) + w(e_i)$
\ENDFOR

\STATE $B[m-k+k'] \leftarrow w(Q_B)$
\FORALL{$ j \leftarrow m-(k-k'), \dots , k'+1$}
\IF{$w_j < w(\textsc{Top}(Q_B))$}
        \STATE \textsc{Extract-Top}($Q_B$)
%        \STATE $w(Q_B) \leftarrow w(Q_B) - w$(\textsc{TOP($Q_B$)})
        \STATE \textsc{Insert}($Q_B, e_j)$)
%        \STATE $w(Q_B) \leftarrow w(Q_B) + w(e_j)$
\ENDIF
\STATE $B[j-1] \leftarrow w(Q_B)$
\ENDFOR
\STATE $j \leftarrow k'$\label{alg:feas1}
\WHILE{$A[j]+w_j+B[j] > W$}
\STATE $j \leftarrow j+1$
\ENDWHILE\label{alg:feas2}
\STATE \textbf{return} $e_j$
\end{algorithmic}
\caption{A new algorithm solving the $k'$-Max problem.\label{alg:generic}}
\end{algorithm}


\begin{proposition}
\textsc{Max$(L,W,k,k')$} is correct.
\end{proposition}


\begin{proof}
The correctness of this algorithm relies on two facts:
\begin{description}
        \item [(i)] The entry $A[j]$ of array $A$ contains the total weight of the $k'-1$ lowest weight items which are ranked better then $j$.
        \item [(ii)] The entry $B[j]$ contains the total weight of the $k-k'$ lowest weight items which are ranked worse than $j$.
\end{description}
Once we have established this observation, we simply test for the best ranked element which can be completed to a feasible committee (lines~\ref{alg:feas1} - \ref{alg:feas2}).
Let us focus on $A[j]$ now.
The for-loop in lines~\ref{alg:for1} to~\ref{alg:for2} determines the weights of the $k'-1$ top-ranked elements which are also the lowest-weight elements being ranked better than $k'$.
Thus, with line~\ref{alg:for3}, statement (i) holds for $j=k'$.
Note that the entries $A[1], \dots , A[k'-1]$ are meaningless.
In lines~\ref{alg:if1} - \ref{alg:if2} it is tested if a subsequent element should replace the heaviest among the $k'-1$ lowest-weight items.
In line~\ref{alg:if3} the loop invariant follows for $A[j], j = k'+1 , \dots , m - (k-k' + 1)$.
All other entries are not important. Thus, statement $(i)$ is shown.
Analogously, it can be verified that $(ii)$ holds.
\qed\end{proof}


\begin{proposition}
\label{prop:generic}
\textsc{Max$(L,W,k,k')$} can be performed in $\mathcal O(m \log k)$ time.
\end{proposition}


\begin{proof}
Note that the sizes of the priority queues $Q_A$ and $Q_B$ are bounded by $k$.
The dominating operation is \textsc{Extract-Top} which is in $\mathcal O(\log k)$.
The number of \textsc{Extract-Top}-operations is in $\mathcal O(m)$. Thus, we get an overall asymptotic complexity of $\OO(m \log k)$ time.
\qed\end{proof}

\medskip
Let us now consider the ordering $(k'_1,k'_2)$-\textsc{Max} as an extension of the $k'$-\textsc{Max} ordering.
In this case, we first fix the $k'_1$-best ranked element using the previous algorithm. Then, we use the same algorithm for finding the $k'_2$-best ranked element. This leads to a $\OO(m \log k)$ algorithm the pseudocode of which is given in Algorithm \ref{alg:k1k2max}.


\begin{algorithm}[h]
\caption{An algorithm for $(k'_1,k'_2)$-\textsc{Max} Ordering} \label{alg:k1k2max}
\vspace{0.2cm}
\textsc{$(k'_1,k'_2)$-Max}\\
\textbf{Input:} A list $L := \{ e_1 , \dots , e_m \}$ representing the ranking of $m$ elements; a weight bound $W \in \mathbb{R}$, $k \in \mathbb{N}$, $k_1' \in \mathbb{N}$, $k_2' \in \mathbb{N}$,
$k_1' \leq k_2' \leq k$.\\
\textbf{Output:} The best possible pair $(k_1', k_2')$ for which a feasible $k$-committee exists.

\begin{algorithmic}[1]
\STATE Find the best possible $k_1'$ element by algorithm \textsc{Max$(L,W,k,k'_1)$}
\STATE Delete the first $k'_1$ elements from $L$
\STATE $W \leftarrow  W - \sum_{i=1}^{k'_1} w(e_i)$
\STATE Find the best possible $k'_2$ element by calling algorithm \textsc{Max$(L,W,k-k'_1,k'_2)$}
\STATE \textbf{return} $(k'_1,k'_2)$
\end{algorithmic}
\end{algorithm}


This idea can now be iteratively extended to as many as $k$ alternatives. The corresponding algorithm is then a $\OO(k m \log k)$ algorithm.

In the following section, we improve the running times originating from this generic approach for the
special cases of $k'=1$, i.e., the \textsc{Maximize-Max} problem and for
the leximax and leximin orders, respectively, which can be written as
$(1,2,\ldots, k)$-\textsc{Max} and $(k,k-1,\ldots, 1)$-\textsc{Min}, respectively.



\section{Improvements}
\label{sec:Improvements}


\subsection{\textsc{Maximize-Max} or $k'=1$-Max Order}


An optimal $k$-committee with respect to the maximize-max order can be  computed in linear time
thus improving upon the $\OO( m \log k)$ bound given in Proposition~\ref{prop:generic}.
% NEU
The main idea is quite simple:
Starting from a solution $S$ containing the $k$ lightest elements we look for the highest
ranked element $e_j$ which can be added to $S$ and preserves feasibility.
To maintain feasibility, the best choice of removing an element from $S$
is given by the heaviest element $e^h$.

\begin{algorithm}
\textsc{MaximizeMax$(L,W,k)$}\vspace{0.1cm} \\
\textbf{Input:} A list $L := \{ e_1 , \dots , e_m \}$ representing the ranking of $m$ elements; a weight bound $W \in \mathbb{R}$, $k \in \mathbb{N}$.\\
\textbf{Output:} A feasible set $S$ containing $k$ elements of $L$.

\begin{algorithmic}[1]
%  \STATE $S \leftarrow \emptyset$, $w(S) \leftarrow 0$
  \STATE Find the $k$th lightest element of $L$ \label{FindingK-Lightest}
  %\FORALL{$ j = 1, \dots , m$}
  %\IF{$w(e_j) < w(e)$}
  %\STATE $S \leftarrow S \cup \{ e_j \}$
  %\STATE $w(S) \leftarrow w(S) \cup \{ w(e_j) \}$
  %\ENDIF
  %\ENDFOR
  \STATE Denote $S$ the set containing the $k$~lightest elements
  \STATE Denote $e^{br}$ the best ranked element in $S$
  \STATE Denote $e^h$ the heaviest element in $S$
  \STATE $\text{stop} \leftarrow \mathtt{false}$, $j \leftarrow 1$.
  \WHILE{$\text{stop} = \mathtt{false}$ \textbf{and} $e_j \not = e^{br}$}
  \IF{$w(S) - w(e^h) + w(e_j) \leq W$}
        \STATE $S \leftarrow S \setminus \{ e^h \} \cup \{ e_j \}$
        \STATE $\text{stop} \leftarrow \mathtt{true}$
  \ENDIF
   \STATE $j \leftarrow j+1$
  \ENDWHILE
  \STATE \textbf{return} $S$
\end{algorithmic}
\caption{An algorithm for finding an optimal solution to the maximize max order.}\label{alg:maximizemax}
\end{algorithm}


\begin{proposition}\label{prop:maximizemax}
Algorithm \ref{alg:maximizemax} computes an optimal $k$-committee with respect to the maximize-max order in $\OO(m)$.
\end{proposition}


\begin{proof}
Observe that $S$ always includes the $k-1$ lightest elements. At termination of the algorithm, let $S := \{ e_{i_1} , \dots , e_{i_k} \}$. Without loss of generality, we may assume that $e_{i_l} R e_{i_{l+1}}$ for all $ l = 1, \dots , k-1$. Let $\bar S := \{ e_{j_1} , \dots , e_{j_k} \}$ be an optimal solution for the maximize-max order with $e_{j_l} R e_{j_{l+1}}$ for all $ l = 1, \dots , k-1$, $e_{j_1} R e_{i_1}$ and $\sum_{l = 1}^k w(e_{j_l}) \leq W$.
\begin{description}
        \item[Case 1:] $e_{j_1}$ is among the $k-1$ lightest elements. Then $e_{j_1} \in S$. Thus, $e_{i_1} R e_{j_1}$ and therefore $e_{i_1} I e_{j_1}$.
        \item[Case 2:] $e_{j_1}$ is not among the $k-1$ lightest elements.
Then, consider $\hat S$ consisting of $e_{j_1}$ together with the $k-1$ lightest elements.
$\hat S$ is weight feasible since $w(\hat S) \leq w(\bar S)$.
Without loss of generality, we may assume that $e_{j_1}$ is the best ranked element in $\hat S$. Due to the while-loop of the algorithm,
$e_{i_1}$ is the overall best ranked element which --- together with the $k-1$ lightest elements --- forms a feasible committee. Thus, $e_{i_1} R e_{j_1}$ and therefore $e_{i_1} I e_{j_1}$.
\end{description}

\noindent
The straightforward details of the running time are omitted.
%For the running time, observe that line~\ref{FindingK-Lightest} can be accomplished
%in $\OO(m)$ time (see \cite[p.~183]{clr01}).
%The $k$~lightest elements can then be found by a single pass through all elements
%and comparing their weight with the weight of the $k$th lightest one.
%The rest is obvious.
\qed\end{proof}


\subsection{Leximax-Order}

Obviously, an optimal $k$-committee with respect to the leximax order can be computed by executing $k$ iterations
of the generic Algorithm~\ref{alg:generic} in $\OO(k m \log k)$ time.
However, we can do much better.

In principle, the underlying idea of algorithm \textsc{MaximizeMax} can be extended to solve also the leximax ordering
by continuing the exchange operation as long as possible.
However, the details of the resulting algorithm require considerable attention.
%Hence, we state \textsc{LexiMax} explicitly.
Throughout the algorithm we will keep a priority queue $Q$
containing a set of the lightest elements sorted in decreasing order of weights.
The solution set $S$ is constructed iteratively by trying to insert an item ranked better than the
currently best item in $Q$ denoted by $e^{br}$.
If no such item is found then $e^{br}$ is inserted in $S$ and the procedure is continued.
Since we cannot explicitly delete an arbitrary element from $Q$,
we postpone the removal of $e^{br}$ from $Q$ to the point when it is accessed as the heaviest element of $Q$.
The necessary update of $e^{br}$ can be done easily by linking the elements of $Q$ when they are first generated
and keeping labels to check whether an element was inserted into $S$.

\begin{algorithm}
\textsc{LexiMax$(L,W,k)$}\vspace{0.1cm} \\
\textbf{Input:} A list $L := \{ e_1 , \dots , e_m \}$ representing the ranking of $m$ elements;
a weight bound $W \in \mathbb{R}$, $k \in \mathbb{N}$.\\
\textbf{Output:} A feasible set $S$ containing $k$ elements of $L$.

\begin{algorithmic}[1]
  \STATE $S \leftarrow \emptyset$%, $w(S) \leftarrow 0$
  \STATE Find the $k$th lightest element of $L$
  \STATE Insert the $k$~lightest elements of $L$ into $Q$ \label{u:FindingK-Lightest}
  \STATE Denote $e^{br}$ the best ranked element in $Q\setminus S$
  \STATE $j \leftarrow 1$

  \REPEAT\label{u:repeat}
	\IF{$e_j=e^{br}$}
		\STATE $S \leftarrow S \cup \{ e_j \}$\label{u:ins1}
		\IF{$e^{br}=\textsc{Top}(Q)$}  \label{u:notins1}
		\STATE  \textsc{Extract-Top}($Q$)\label{u:extract}
		\ENDIF
		\STATE Update $e^{br}$
	\ELSIF{$w(S) + w(Q) - w(\textsc{Top}(Q)) + w(e_j) \leq W$} \label{u:ifweight}
		\STATE $S \leftarrow S \cup \{ e_j \}$\label{u:ins2}
		\STATE  \textsc{Extract-Top}($Q$)
		\WHILE{\textsc{Top}(Q) $\in S$} \label{u:notins2}
			\STATE  \textsc{Extract-Top}($Q$)	\label{u:extr}
		\ENDWHILE
		\STATE Update $e^{br}$
	\ENDIF
	\STATE $j \leftarrow j+1$
  \UNTIL{$Q =\emptyset$}\label{u:until}
  \STATE \textbf{return} $S$
\end{algorithmic}
\caption{An algorithm for finding an optimal solution to the leximax order.}\label{alg:leximax}
\end{algorithm}




\begin{proposition}
\textsc{LexiMax$(L,W,k)$} is correct.
\end{proposition}

\begin{proof}
omitted.
\qed\end{proof}

\begin{proposition}
\textsc{LexiMax$(L,W,k)$} runs in $\OO(m + k\log k)$.
\end{proposition}

\begin{proof}
As pointed out in the proof of Proposition~\ref{prop:maximizemax}
the items in $Q$ can be found in $\OO(m)$ time and inserted into a priority queue in $\OO(k)$ time.
The loop in lines~\ref{u:repeat}-\ref{u:until} is performed at most $\OO(m)$ times,
while the  \textsc{Extract-Top}($Q$) command requiring $\OO(\log k)$ time can be executed
at most $k$ many times before $Q=\emptyset$.
Note that we never insert elements into $Q$.

Updating $e^{br}$ can be done in constant time if the items in $Q$ are linked in decreasing order of
rank when they are identified in line~\ref{u:FindingK-Lightest}.
Whenever an element is deleted from $Q$ this linked structure can be easily updated in constant time
(e.g.\ by using a double-linked list).
This proves the statement.
\qed\end{proof}


\subsection{Leximin-Order}

An optimal $k$-committee with respect to the maximize-min order can be
computed in a straightforward way by
performing \textsc{Max$(L,W,k,k)$} in $\OO(m \log k)$ time.
% \textsc{MaximizeMin$(L,W)$}
For the  leximin-order it remains to adjust the remaining $k-1$~elements.
A trivial approach would apply \textsc{Max$(L',W',j,j)$} iteratively for $j=k-1, k-2, \ldots, 1$
with adapted sets of elements $L'$ and weight bounds $W'$.
Along these lines an $\OO(k\,m \log k)$ algorithm for the leximin-order is derived.

%At first, we slightly modify the previous algorithm. Those elements of~$L$ which have been visited but
%\begin{description}
% \item[a)] which never have entered $Q$ or (Diesen Fall brauchen wir vermutlich nicht??? Er macht aber auch nichts kaputt.)
% \item[b)] which have been extracted from $Q$
%\end{description}
%are inserted in a Fibonacci heap $Q_2$ which is minimum-ordered with respect to weight.
%This increases the running time of the previous algorithm to $\OO(m \log m)$.
%Using the $k$~elements of $Q$, we build another heap~$Q_3$
%which is maximum-ordered with respect to the ranking, i.e., the top-most element is the worst-ranked one.
%This can be done in %$\OO(k)$. We extract the top-most element (since it is already correctly fixed)
%and update the weight bound by subtracting the weight of this extracted element.
%The idea of the following algorithm
%is to try to improve the $i$th~worst-ranked element (for $i = 1, \dots , k-1$)
%by looking at the elements collected in $Q_2$.

\begin{algorithm}
\textsc{LexiMin$(L,W,k)$}\vspace{0.1cm} \\
\textbf{Input:} A list $L := \{ e_1 , \dots , e_m \}$ representing the ranking of $m$ elements;
%Priority queues $Q_2$ and $Q_3$;
a weight bound $W \in \mathbb{R}$, $k \in \mathbb N$.\\
\textbf{Output:} A feasible set $S$ containing $k$ elements.

\begin{algorithmic}[1]
\STATE Run \textsc{Max$(L,W,k,k)$} to compute a committee with a worst ranked element $e_{\ell}$
\STATE $S \leftarrow \{e_{\ell}\}$ %; $W \leftarrow W - w_{e_{\ell}}$
\STATE Insert the $k-1$ lightest elements from $\{e_1, \ldots, e_{\ell-1}\}$ into $Q_S$\label{alg:start1}
%\STATE insert $L_M \setminus \{e_{\ell}\}$ into $Q_S$
\STATE Insert the remaining elements $\{e_1,\ldots, e_{\ell -1}\} \setminus Q_S$ into $Q_R$
\label{alg:start2}
\WHILE{$Q_S \not = \emptyset \textbf{ and }  Q_R \not = \emptyset$}\label{alg:mainwhile}
        \WHILE{$\text{rank}(\textsc{Top}(Q_R)) \text{ worse than } \text{rank}(\textsc{Top}(Q_S))$} \label{whileworse}
        \STATE \textsc{Extract-Top}($Q_R$)  \label{extrr} %\COMMENT{Die werden ja nicht mehr gebraucht.}
  \ENDWHILE
  \IF{$w(S)+ w(Q_S) -  w(\textsc{Top}(Q_S)) + w(\textsc{Top}(Q_R)) \leq W$} \label{ifweight}
%        \STATE $w(Q_S) \leftarrow w(Q_S) -  w(\textsc{Top}(Q_S)) + w(\textsc{Top}(Q_R))$
        \STATE \textsc{Extract-Top}($Q_S$) \label{exchb}
        \STATE \textsc{Insert}($Q_S, \textsc{Top}(Q_R)$) \label{alg:addqs}
        \STATE \textsc{Extract-Top}($Q_R$) \label{exche}
  \ELSE
%        \STATE $W \leftarrow W - w(\textsc{Top}(Q_S))$
        \STATE $S \leftarrow S \cup \textsc{Top}(Q_S)$ \label{adds}
        \STATE \textsc{Extract-Top}($Q_S$) \label{extrs}
  \ENDIF
\ENDWHILE
\STATE \textbf{return} $S$
\end{algorithmic}
\caption{An algorithm for finding an optimal solution to the leximin order.}
\end{algorithm}


The remaining $k-1$~elements can be computed more efficiently. Algorithm \textsc{Lexi\-Min}$(L,W,k)$ starts with a feasible solution consisting of $S=\{e_{\ell}\}$ determined by \textsc{Max}$(L,W,k,k)$ and the $k-1$ elements of smallest weight
ranked better than $e_{\ell}$ which are stored in $Q_S$.
Throughout the algorithm, elements of the optimal solution are computed iteratively and added to $S$ while $Q_S$ keeps items complementing $S$ to a feasible solution.
All items ranked better than the best element currently in $S$ but not contained in $Q_S$
are candidates for an improvement of the current feasible solution and stored in $Q_R$.

Both, $Q_S$ and $Q_R$, are organized as Fibonacci heaps.
$Q_S$ is maximum-ordered with respect to the ranking, i.e., the top element is the worst-ranked one, since this is the first element which we try to replace in the current feasible solution.
The second heap $Q_R$ is minimum-ordered with respect to weight, since the lightest element
is most likely to fit into a new feasible solution.

After initializing this structure in lines ~\ref{alg:start1}-\ref{alg:start2}
we enter the main loop of the algorithm.
There, we first remove all items in $Q_R$ which are ranked worse than the worst element in $Q_S$
(line~\ref{whileworse}).
Then we try to improve the current feasible solution (line~\ref{ifweight}) by removing its worst element (among those which are still not fixed).
The best chance to construct a new feasible solution is given by the element with smallest weight
(among those with better ranking), i.e.\ $\textsc{Top}(Q_R)$.
If the improvement step was successful we update $Q_S$ and $Q_R$ (lines~\ref{exchb}-\ref{exche}), otherwise we have to include the lowest ranked element of $Q_S$ permanently in the solution
and thus move it into $S$ (lines~\ref{adds}-\ref{extrs}).


\begin{proposition} \label{prop:leximincorr}
\textsc{LexiMin$(L,W,k)$} is correct.
\end{proposition}

\begin{proof}
omitted.
\qed\end{proof}


\begin{proposition}
\textsc{LexiMin$(L,W,k)$} runs in $\OO(m \log m)$.
\end{proposition}

\begin{proof}
Running  \textsc{Max$(L,W,k,k)$} takes $\OO(m \log k)$ time (see Proposition~\ref{prop:generic}) while the generation of the two heaps requires $\OO(m)$ time.
In every execution of the main while-loop the number of operations is dominated by the number of  \textsc{Extract-Top} operations.
$Q_R$ contains at most $m-k$ elements at the beginning and no elements are ever added to $Q_R$.
$Q_S$ starts with $k-1$ items and may receive at most $|Q_R|$ additional elements from $Q_R$
during the execution of the algorithm.
Therefore, the total number of  \textsc{Extract-Top} operations is bounded by $m-k+(k-1+m-k)<2m$
which proves the statement.
\qed\end{proof}

For small values of $k$ we can formulate a more efficient algorithm
which is however not discussed here for lack of space.

\begin{proposition}\label{prop:leximinsmall}
An optimal $k$-committee for the leximin order can be computed in $\OO(m k)$ time.
\end{proposition}

\begin{proof}
See our technical report \cite{klpfru09}.
\qed\end{proof}

\smallskip
Comparing \textsc{LexiMin$(L,W,k)$} and Proposition~\ref{prop:leximinsmall}
it turns out that
for $k > \log m$ \textsc{LexiMin$(L,W,k)$} dominates its competitor.
On the other hand, for $k \leq \log m$ the algorithm quoted in
Proposition~\ref{prop:leximinsmall} is superior.
Hence, a combination of the two algorithms yields a $\OO( m \cdot \min\{k, \log m\})$
running time bound.

\section{Conclusion}
\label{sec:Conclusion}
In this paper we try to link social choice theory with methods from discrete optimization.
Based on a social ordering of the candidates and a weight or budget constraint on that set,
we derive and analyze efficient algorithms for the computation of socially optimal committees.
Particular attention is devoted to the running time complexities of the algorithms.

Further work on this subject might include analyzing different set orderings, additional constraints or the relationship to conceptual approaches that might provide certain insight, such as ''prudent orders'' in group decision problems.

%\subsubsection*{Acknowledgement}
%Stefan Ruzika was partially supported by Deutsche Forschungsgemeinschaft (DFG) grant 1737/7 %"Algorithmik gro\ss er und komplexer Netze" and by the Rheinland-Pfalz cluster of excellence %"Dependable adaptive systems and mathematical modeling".

%\setlength{\bibsep}{1.3mm}
%\setlength{\bibsep}{0.3mm}
\begin{thebibliography}{99}
\bibitem{BaBoPa}
Barbera, S., W. Bossert and P.K. Pattanaik,
''Ranking Sets of Objects'', in: Barbera, S., Hammond, P.J. and C. Seidl (eds.), {\it Handbook of Utility Theory. Volume 2}, Boston, Kluwer Academic Publishers, 2004.

\bibitem{BaMaNe2005}
Barbera, S., J. Masso  and A. Neme,
''Voting by committees under constraints'', {\em Journal of Economic Theory}, {\bf 122}, 185--205, 2005.

%\bibitem{BoPaXu2000}
%Bossert, W., Pattanaik, P.K. and Y. Xu,
%''Choice under complete uncertainty: axiomatic characterizations of some decision rules'',
%{\em Economic Theory} {\bf 16}, 295--312, (2000).

\bibitem{BrFi2002}
Brams, S.J. and P.C. Fishburn,
''Voting Procedures'', in: Arrow, K.J., Sen A.K. and K. Suzumura (eds.), {\it Handbook of Social Choice and Welfare. Volume 1}, Amsterdam, Elsevier, 173--236, 2002.

%\bibitem{brfi83}
%Brams, S.J. and P.C. Fishburn, {\it Approval Voting}, Boston, Birkhauser, 1983.

\bibitem{ckpp00}
Caprara, A., H. Kellerer, U. Pferschy and D. Pisinger,
``Approximation algorithms for knapsack problems with cardinality constraints'',
{\em European Journal of Operational Research} {\bf 123}, 333--345, 2000.

\bibitem{clr01}
Cormen, T.H., C.E. Leiserson, R.L. Rivest and C. Stein,
{\it Introduction to Algorithms},
2nd ed., MIT Press, 2001.

\bibitem{dkp08}
Darmann, A., C. Klamler and U. Pferschy,
``Finding socially best spanning trees'',
Social Science Research Network, {\tt http://ssrn.com/abstract=1328916}, 2008.
%submitted.
% submitted to {\sl Theory and Decision}


\bibitem{kpp04}
Kellerer, H., U. Pferschy and D. Pisinger,
{\it Knapsack Problems}, Springer, 2004.

\bibitem{klpf05}
Klamler, C. and U. Pferschy,
``The traveling group problem'',
{\em Social Choice and Welfare} {\bf 29}, 429--452, 2007.

\bibitem{klpfru09}
Klamler, C., U. Pferschy and S. Ruzika,
``Committee selection under weight constraints'',
Technical Report, available in: Social Science Research Network, {\tt http://ssrn.com/abstract=1361770}, 2009.

%\bibitem{Nu1987}
%Nurmi, H., {\it Comparing Voting Systems}, Dordrecht, D. Reidel, 1987.
%\bibitem{Nu1999}
%Nurmi, H., {\it Voting Paradoxes and How to Deal with Them}, Springer, 1999.

\bibitem{PaPe1984}
Pattanaik, P.K. and B. Peleg, ''An axiomatic characterization of the lexicographic maximin extension of an ordering over a set to the power set'', {\em Social Choice and Welfare} {\bf 1}, 113--122, 1984.

\bibitem{PeSp2005}
Perny, P. and O. Spanjaard, ''A preference-based approach to spanning trees and shortest paths problems'', {\em European Journal of Operational Research}, {\bf 162}, 584--601, 2005.
%\bibitem{Sa1995}
%Saari, D.G., {\it A Basic Geometry of Voting}, Springer, 1995.


\end{thebibliography}


\end{document} 