\documentclass{llncs}
\usepackage{graphicx}

%
%
%
%
\usepackage{url}
\usepackage{hyperref}
\usepackage{mathptmx}
\sloppy


%
%
%
%
%

%

%
%
%
%
%
%
%
%
%
%
%
%
%


%


\pagestyle{plain}

\usepackage{pifont}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{amsfonts}
%
%
%
%
%
%
\usepackage{nicefrac}

%

%
%
%
%
%


%
\newcommand{\Omit}[1]{} %
%

%
%
\newcommand{\jfootnote}[1]{\footnote{{\bf {#1}-- JR}}}




%
%
%
%
%
%
%
%

\newcommand\qedblob{\mbox{\ding{113}}}
\def\qedsymbol{{\ \nolinebreak\hfill\mbox{\qedblob\quad}}\smallskip}
%
\def\literalqed{{\ \nolinebreak\hfill\mbox{\qedblob\quad}}}
\def\qedcareful{\literalqed}
\def\qed{\literalqed}
\newenvironment{proofs}{\noindent{\bf Proof.}\hspace*{1em}}{\literalqed\bigskip}
\newenvironment{desctight}
  {\begin{list}{}{\setlength\labelwidth{0pt}%
        \setlength{\itemsep}{0.5pt}%
        \setlength{\parsep}{0pt}%
        \setlength\itemindent{-\leftmargin}%
        \let\makelabel\descriptionlabel}}
    {\end{list}}

%
%
%
%





%
%
%
%
%
%
%
%
%
%
%
%
%


%
\hyphenation{theory theoretical area areas theorem theorems par-allel par-allelize par-allelized threshold Hemaspaan-dra}




%
%
%




%
\makeatletter
\def\@cite#1#2{[#1\if@tempswa , #2\fi]}
\makeatother

%
%
%
\makeatletter
\def\@citex[#1]#2{\if@filesw\immediate\write\@auxout{\string\citation{#2}}\fi
  \def\@citea{}\@cite{\@for\@citeb:=#2\do
    {\@citea\def\@citea{,\linebreak[0]}\@ifundefined
       {b@\@citeb}{{\bf ?}\@warning
       {Citation `\@citeb' on page \thepage \space undefined}}%
\hbox{\csname b@\@citeb\endcsname}}}{#1}}
\makeatother


%
\makeatletter
\def\ps@thesis{\def\@oddhead{\hfil\rm\thepage\hfil}\def\@oddfoot{}\def\@evenhead{\hfil\rm\thepage\hfil}\def\@evenfoot{}\def\chaptermark##1{}\def\sectionmark##1{}}
\makeatother






\newcommand{\prob}{{\rm Prob}}
\newcommand{\avgp}{\mbox{\rm AvgP}}

\newcommand{\deficit}{{\rm Deficit}}
\newcommand{\poly}{\mathit{poly}}
\newcommand{\Good}{\mathit{good}}
\newcommand{\Unknown}{\mathit{unknown}}
\newcommand{\exponential}{\mathit{exponential}}
\newcommand{\expectation}{\mbox{\sc E}}
\newcommand{\opt}{{\rm OPT}}
\newcommand{\cost}{\mathit{cost}}
\newcommand{\costeffective}{\mathit{cost-effectiveness}}
\newcommand{\price}{\mathit{price}}
\newcommand{\posset}{\mathit{Pos}}
\newcommand{\negset}{\mathit{Neg}}
\newcommand{\dscore}{{\rm DodgsonScore}}
\def\pair#1{{{(#1)}}}

\newcommand{\probbf}{\rm}
\newcommand{\problobbying}{{\textsc{Probabilistic}\hbox{ }\allowbreak\textsc{Lobbying}\hbox{ }\allowbreak\textsc{Problem}}}
%
\newcommand{\sat}{{\probbf \mbox{SAT}}}
\newcommand{\hp}{{\probbf \mbox{HP}}}
\newcommand{\threesat}{{\probbf 3\hbox{-}\allowbreak\mbox{SAT}}}
\newcommand{\optimalweightedlobbying}{{\probbf \mbox{Optimal}\hbox{-}\allowbreak\mbox{Weighted}\hbox{-}\allowbreak\mbox{Lobbying}}}
\newcommand{\optimallobbying}{{\probbf \mbox{Optimal}\hbox{-}\allowbreak\mbox{Lobbying}}}
\newcommand{\dodgsonwinner}{{\probbf \mbox{Dodgson}\hbox{-}\allowbreak\mbox{Winner}}}
\newcommand{\greedywinner}{{\probbf \mbox{Greedy}\hbox{-}\allowbreak\mbox{Winner}}}
\newcommand{\greedyscore}{{\probbf \mbox{Greedy}\hbox{-}\allowbreak\mbox{Score}}}
\newcommand{\averagewinner}{{\probbf \mbox{Average}\hbox{-}\allowbreak\mbox{Winner}}}
\newcommand{\rationals}{\ensuremath{{ \mathbb{Q} }}}
\newcommand{\rationalnumbers}{\ensuremath{{ \mathbb{Q} }}}
\newcommand{\rationalszeroone}{\ensuremath{{ \mathbb{Q}_{[0,1]} }}}
\newcommand{\matrixrationalszeroone}[2]{\ensuremath{{ \mathbb{Q}_{[0,1]}^{#1{\times }#2} }}}

\newcommand{\wtwo}{{\ensuremath{\rm{W}[2]}}}
\newcommand{\wt}[1]{{\ensuremath{\rm{W}[#1]}}}
\newcommand{\scriptnp}{\mbox{\protect\scriptsize\rm NP}}
\newcommand{\scriptpp}{\mbox{\protect\scriptsize\rm PP}}
\newcommand{\p}{\ensuremath{\rm P}}
\newcommand{\parallelnp}{\mbox{$\p_{\|}^{\scriptnp}$}}
\newcommand{\pnptt}{\ensuremath{\p^{\scriptnp}_{\mbox{\protect\scriptsize\rm{}truth-table}}}}
\newcommand{\pnplog}{\ensuremath{\p^{\scriptnp[\log ]}}}
\newcommand{\np}{{\ensuremath{\rm NP}}}

\newcommand{\dtime}{{\ensuremath{\rm DTIME}}}
\newcommand{\sigmastar}{\mbox{$\Sigma^\ast$}}
\newcommand{\naturalnumber}{\ensuremath{{  \mathbb{N} }}}
\def\nats{\naturalnumber}
\def\natsplus{\nats^+}

%
%
%


\newcommand{\naturals}{\mathbb{N}}
\newcommand{\integers}{\mathbb{Z}}

\newcommand{\condition}{\,\mid \:}
%

\newcommand{\MIN}{\textsc{MIN}}
\newcommand{\ol}{\textsc{OL}}
\newcommand{\owl}{\textsc{OWL}}
\newcommand{\plp}[2]{\textsc{B$_{#1}$-C$_{#2}$-PLP}}
\newcommand{\plpiw}[2]{\textsc{B$_{#1}$-C$_{#2}$-PLP-WIW}}
\newcommand{\fhplp}[2]{\textsc{Finite Horizon $B_{#1}$-$C_{#2}$-PLP}}
\newcommand{\fhplpsp}[2]{\textsc{Finite Horizon $B_{#1}$-$C_{#2}$-PLP with Systematic Pressure}}

%

\newcommand{\YES}{\textup{\textsf{YES}}}
\newcommand{\NO}{\textup{\textsf{NO}}}
 \newcommand{\Oh}{{\mathcal{O}}}
%

\newcommand{\nat}{{\mathbb N}}


\newcommand{\pbSNTMCname}{short nondeterministic Turing machine computation}
\newcommand{\pbSNTMC}{{\sc\pbSNTMCname}\index{\pbSNTMCname}}
\newcommand{\pbSNTMCs}{{\sc SNTMC}\index{\pbSNTMCname}}

\newcommand{\pbBNTMCname}{bounded nondeterminism Turing machine computation}
\newcommand{\pbBNTMC}{{\sc\pbBNTMCname}\index{\pbBNTMCname}}
\newcommand{\pbBNTMCs}{{\sc BNTMC}\index{\pbBNTMCname}}

\newcommand{\pbSMNTMCname}{short multi-tape nondeterministic Turing machine computation}
\newcommand{\pbSMNTMC}{{\sc\pbSMNTMCname}\index{\pbSMNTMCname}}
\newcommand{\pbSMNTMCs}{{\sc SMNTMC}\index{\pbSMNTMCname}}


\newcommand{\LC}[1]{\lowercase{#1}}

\newcommand{\paramproblem}[4]{An instance of {\sc #1}
is given by #2, and the parameter, #3. The question is: #4}

\newcommand{\Pol}{\mbox{$\mathcal{P}$}}
%
\newcommand{\FPT}{\ensuremath{\rm FPT}}
\newcommand{\NP}{\mbox{$\mathcal{NP}$}}

\newcommand{\problemsize}[1]{|#1|}

\newcommand{\defines}[1]{\index{#1|emph}\emph{#1}}



\begin{document}

\title{The Complexity of Probabilistic Lobbying
\thanks{Supported
 in part by DFG grants RO~\mbox{1202/11-1} and RO~\mbox{1202/12-1},
 the European Science Foundation's EUROCORES program LogICCC,
%
 the Alexander von Humboldt Foundation's TransCoop program, and
 NSF grant ITR-0325063.
 \Omit{Work done in part while the first author
 was visiting Universit\"at Trier and while the third author
 was visiting Heinrich-Heine-Universit\"at D\"usseldorf.}
 }}
\author{
G\'{a}bor Erd\'{e}lyi\inst1,  
%
%
Henning Fernau\inst2, 
%
%
Judy Goldsmith\inst3,\\
%
%
%
Nicholas Mattei\inst3,
%
%
Daniel Raible\inst2, and 
%
%
J\"{o}rg Rothe\inst1
%
}


\institute{%
%
Universit\"{a}t D\"{u}sseldorf,
Institut f\"{u}r Informatik, 
40225 D\"{u}sseldorf,
Germany
%
\and
Universit\"{a}t Trier, FB 4---Abteilung Informatik, %
54286 Trier,
Germany
%
%
\and
University of Kentucky,
Department of Computer Science,
Lexington, KY 40506, 
USA
%
%
%
%
%
%
}

\date{\today}

\maketitle


\begin{abstract}
We propose various models for lobbying in a probabilistic environment,
in which an actor (called ``The Lobby'') seeks to influence the
voters' preferences of voting for or against multiple issues when the
voters' preferences are represented in terms of probabilities.  In
particular, we provide two evaluation criteria and three bribery
methods to formally describe these models, and we consider the
resulting forms of lobbying with and without issue weighting.  We
provide a formal analysis for these problems of lobbying in a
stochastic environment, and determine their classical and
parameterized complexity depending on the given bribery/evaluation
criteria.  Specifically, we show that some of these problems can be
solved in polynomial time, some are $\np$-complete but fixed-parameter
tractable, and some are $\wtwo$-complete.  Finally, we provide
(in)approximability results.
\end{abstract}






\section{Introduction}

In the American political system, laws are passed by elected officials
who are supposed to represent their constituency.  
\Omit{Individual entities
such as citizens or corporations are not supposed
%
to have undue influence in the wording or passage of a law.  However,
they are allowed to make contributions to representatives, and it is
common to include an indication that the contribution carries an
%
%
expectation
%
that
the representative will vote a certain way on a particular issue.}
Many factors can affect a representative's vote on a particular issue:
%
a representative's personal beliefs about the issue, 
%
%
%
campaign contributions, communications from
constituents, communications from potential donors, and the
representative's own expectations of further contributions and
political support.

It is a complicated process to reason about.  Earlier work considered
the problem of meting out contributions to representatives in order to
pass a set of laws or influence a set of votes.  However, the earlier
computational complexity work on this problem made the assumption that
a politician who accepts a contribution will in fact---if the
contribution meets a given threshold---vote according to the wishes of
the donor.

It is said that ``An honest politician is one who stays bought,'' but
that does not take into account the ongoing pressures from personal
convictions and opposing lobbyists and donors.  We consider the
problem of influencing a set of votes under the assumption that we
can influence only the \emph{probability} that the politician votes
as we desire.  The methods for exerting influence on the voters is discussed
in the section on bribery criteria while the notion of sufficient influence for a
voter is discussed in the section on evaluation criteria.

\Omit{   The first is
the notion of sufficiency:  What does it mean to say we have donated
enough to influence the vote?  Does it mean that the probability that
a single vote will go our way is greater than some threshold?  That the
probability that all the votes go our way is greater than that
threshold?  We discuss these and other criteria in the section
on evaluation criteria.

How does one donate money to a campaign?  In the United States there
are several laws that influence how, when, and how much a particular
person or organization can donate to a particular candidate.  We
examine ways in which money can be channeled into the political
process in
Section~\ref{sec:models-for-probabilistic-lobbying}.}\Omit{\footnote{We
  stress that when we use the term ``bribery'' in this paper, it is
  meant in the sense of lobbying~\cite{chr-fel-ros-sli:j:lobbying},
  not in the sense Faliszewski et
  al.~\cite{fal-hem-hem:c:bribery} define
  bribery (see also, e.g.,
  \cite{fal-hem-hem-rot:c:llull,fal-hem-hem-rot:c:copeland-fully-resists-constructive-control,fal-hem-hem-rot:j:llull-copeland-full-techreport}).}}

%
%

Lobbying has been studied formally by economists, computer scientists,
and special interest groups since at least 1983
\cite{rei:j:formal-lobby} and as an extension to formal game theory
since 1944 \cite{neu-mor:b:games}.  Each discipline has considered
mostly disjoint aspects of the process while seeking to accomplish
distinct goals with their respective formal models.  Economists have
formalized models and studied them as ``economic games,'' as
defined by von Neumann and Morgenstern \cite{neu-mor:b:games}.  This
analysis is focused on learning how these complex systems work and
deducing optimal strategies for winning the competitions
\cite{rei:j:formal-lobby,bay-kov-dev:j:rig,bay-kov-dev:j:completeinfo}.
This work has also focused on how to ``rig'' a vote and how to optimally
dispense the funds among the various individuals
%
%
%
\cite{bay-kov-dev:j:rig}.  Economists are interested in finding
effective and efficient bribery schemes \cite{bay-kov-dev:j:rig} as
well as determining strategies for instances of two or more players
\cite{bay-kov-dev:j:rig,rei:j:formal-lobby,bay-kov-dev:j:completeinfo}.
Generally, they reduce the problem of finding an effective lobbying
strategy to one of finding a winning strategy for the specific type of
game.
%
%
%
Economists have also formalized this problem for bribery systems in
both the United States \cite{rei:j:formal-lobby} and the European
Union~\cite{cro:j:eulobby}.

%
%
%
%
In the emerging field of computational social choice, voting and
preference aggregation are studied from a computational perspective,
with a particular focus on the complexity of winner determination,
manipulation, procedural control, and bribery in elections (see, e.g.,
the survey \cite{fal-hem-hem-rot:b:richer} and
the references cited therein), and also with respect to lobbying in the
context of direct democracy where voters vote on multiple
referenda.
%
%
%
%
%
%
%
%
%
In particular, Christian et
al.~\cite{chr-fel-ros-sli:j:lobbying} show that ``Optimal
Lobbying'' ($\ol$) is complete for the (parameterized) complexity
class $\wtwo$.  The $\ol$ problem is a deterministic and nonweighted
version of the problems that we present in this paper.
Sandholm noted that the ``Optimal Weighted Lobbying'' ($\owl$) problem,
which allows different voters to have different prices, can be
expressed as and solved via the ``binary multi-unit combinatorial reverse
auction winner-determination problem''
(see~\cite{san-sur-gil-lev:c:combinatorial-auction-generalizations}).

We extend the models of lobbying, and provide algorithms and analysis
for these extended models in terms of classical and parameterized
complexity.  Our problems are still
%
related to the reverse auction winner-determination problem---in
particular, our extensions of the optimal lobbying problem allow the
seller to express desire over the objects, thus
%
crucially changing the original problem in both the economic and
complexity-theoretic senses.  This change is a result of the
probabilistic modeling of the seller's reaction to the bribery.  We
also show novel computational and algorithmic approaches to these new
problems.  In this way we add breadth and depth to not only
the models but also the understanding of lobbying behavior.

\section{Models for Probabilistic Lobbying}
\label{sec:models-for-probabilistic-lobbying}

\subsection{Initial Model}
\label{sec:initialmodel}

We begin with a simplistic version of the \textsc{Probabilistic
  Lobbying Problem} (\textsc{PLP}, for short), in which voters start
with initial probabilities of voting for an issue and are assigned
known costs for increasing their probabilities of voting according to
``The Lobby's'' agenda by each of a finite set of increments.

The question, for this class of problems, is: Given the above 
information, along with an agenda and a 
fixed budget $B$, can The Lobby target its bribes in order 
to achieve its agenda?  The complexity of 
the problem seems to hinge on the evaluation criterion for 
what it means to ``win a vote'' or 
``achieve an agenda.''  We discuss the possible 
interpretations of evaluation and bribery later
in this section.
First, however, we will formalize the problem
by defining data objects needed to represent the problem
instances.\Omit{\footnote{A similar model was first 
discussed by Reinganum \cite{rei:j:formal-lobby} in the continuous 
case and we translate it here to the discrete case.  
This will allow us to present algorithms for, and the complexity 
analysis of, the problem.}}

Let $\matrixrationalszeroone{m}{n}$ denote the set of
$m {\times} n$ matrices over $\rationals_{[0,1]}$ (the
rational numbers in the interval $[0,1]$).
We say $P \in \matrixrationalszeroone{m}{n}$ is a probability 
matrix (of size $m {\times} n$),
%
%
%
where each entry $p_{i,j}$ of $P$ gives the probability that voter
$v_{i}$ will vote ``yes'' for referendum (synonymously, for issue)
$r_{j}$.  The result of a vote can be either a ``yes'' (represented by
$1$) or a ``no'' (represented by $0$).  Thus, we can represent the
result of any vote on all issues as a $0/1$ vector $\vec{X} = (x_1,
x_2, \dots, x_n)$, which is sometimes also denoted as a string in
$\{0,1\}^n$.

We now associate with each pair $(v_i,r_j)$ of voter/issue,
a discrete price function $c_{i,j}$ for changing $v_i$'s
probability of voting ``yes'' for issue~$r_j$.
%
%
%
%
%
%
%
Intuitively, $c_{i,j}$
%
gives the cost for The Lobby of raising or
lowering (in discrete steps) the $i$th voter's probability of voting
``yes'' on the $j$th issue.  A formal description is as follows.

Given the entries $p_{i,j} = \nicefrac{a_{i,j}}{b_{i,j}}$ of a
probability matrix $P \in \matrixrationalszeroone{m}{n}$, choose some
$k \in \nats$ such that $k+1$ is a common multiple of all $b_{i,j}$,
where $1 \leq i \leq m$ and $1 \leq j \leq n$, and partition the
probability interval $[0,1]$ into $k+1$ steps of size
$\nicefrac{1}{(k+1)}$ each.\Omit{\footnote{There is some arbitrariness in
  this choice of~$k$.  One might think of more flexible ways of
  partitioning $[0,1]$.  We have chosen this way for the sake of
  simplifying the representation, but we mention that all that matters
  is that for each $i$ and~$j$,
%
  the discrete price function $c_{i,j}$
  is defined on the value $p_{i,j}$, and is set to zero for this value.}}
For each $i \in \{1, 2, \ldots , m\}$ and $j \in \{1, 2, \ldots ,
n\}$, $c_{i,j} : \{0,\nicefrac{1}{(k+1)},\nicefrac{2}{(k+1)}, \ldots
,\nicefrac{k}{(k+1)}, 1\} \rightarrow \nats$ is the
\emph{(discrete) price function for $p_{i,j}$}, i.e.,
$c_{i,j}(\nicefrac{\ell}{(k+1)})$ is the price for changing the
probability of the $i$th voter voting ``yes'' on the $j$th issue from
$p_{i,j}$ to $\nicefrac{\ell}{(k+1)}$, where $0 \leq \ell \leq k+1$.
Note that the domain of $c_{i,j}$ consists of $k+2$ elements of
$\rationalszeroone$ including~$0$, $p_{i,j}$, and~$1$.  In particular,
we require $c_{i,j}(p_{i,j})=0$, i.e., a cost of zero is associated
with leaving the initial probability of voter $v_i$ voting on issue
$r_j$ unchanged.  Note that $k=0$ means $p_{i,j} \in \{0,1\}$, i.e.,
in this case each voter either accepts or rejects each issue with
certainty and The Lobby can only flip these results.\footnote{This is
  the special case of Optimal Lobbying.}
%
The image of $c_{i,j}$ consists of $k+2$ nonnegative integers
including~$0$, and we require that,
%
%
%
for any two elements $a,b$ in the domain of $c_{i,j}$, if
$p_{i,j} \leq a \leq b$ or $p_{i,j} \geq a \geq b$, then
$c_{i,j}(a) \leq c_{i,j}(b)$.  This guarantees monotonicity on the prices.



We represent the list of
%
price functions associated with
a probability matrix $P$ as a table $C_P$ whose $m \cdot n$ rows give
the
%
price functions $c_{i,j}$ and whose $k+2$
columns give the costs $c_{i,j}(\nicefrac{\ell}{(k+1)})$, 
where $0 \leq \ell \leq k+1$.  
Note that we choose the same $k$ for each $c_{i,j}$, so we have
the same number of columns in each row of~$C_P$.
The entries of $C_P$ can be
thought of as ``price tags'' that The Lobby must 
pay in order to change the probabilities of voting.

The Lobby also has an integer-valued budget $B$ and an ``agenda,''
which we will denote as a vector $\vec{Z} \in \{0,1\}^{n}$, where $n$
is the number of issues, containing the outcomes The Lobby would like
to see on the corresponding issues.  For simplicity, we may assume
that The Lobby's agenda is all ``yes'' votes, so the target vector is
$\vec{Z} = 1^{n}$.  This assumption can be made without loss of
generality, since if there is a zero in $\vec{Z}$ at position~$j$, we
can flip this zero to one and also change the corresponding
probabilities $p_{1,j}, p_{2,j}, \dots , p_{m,j}$ in the $j$th column
of $P$ to $1-p_{1,j}, 1-p_{2,j}, \dots , 1-p_{m,j}$ (see the
evaluation criteria in Section~\ref{sec:eval} for how to determine the
result of voting on a referendum).

%
%
%
%
%
%
%
%
%

\begin{example}
We create a problem instance with $k=9$, $m=2$ (number of voters), and
$n = 3$ (number of issues).  We will use this as a running example for
the rest of this paper.  In addition to the above definitions for $k$,
$m$, and $n$, we also give the following matrix for $P$.  (Note that
this example is normalized for an agenda of $\vec{Z} = 1^3$, which is
why The Lobby has no incentive for lowering the acceptance
probabilities, so those costs are omitted below.)

Our example consists of
%
a probability matrix~$P$:
%
%
\[
\begin{array}{|c||c|c|c|}
\hline
    & r_1 & r_2 & r_3 \\ \hline\hline
v_1 & 0.8 & 0.3 & 0.5 \\ \hline
v_2 & 0.4 & 0.7 & 0.4 \\ \hline
\end{array}
\]
{\small
%
and the corresponding cost matrix~$C_P$:
\[
\begin{array}{|@{\hspace*{1mm}}l@{\hspace*{1mm}}||@{}r@{\hspace*{1mm}}|@{}r@{\hspace*{1mm}}|@{}r@{\hspace*{1mm}}|@{}r@{\hspace*{1mm}}|@{}r@{\hspace*{1mm}}|@{}r@{\hspace*{1mm}}|@{}r@{\hspace*{1mm}}|@{}r@{\hspace*{1mm}}|@{}r@{\hspace*{1mm}}|@{}r@{\hspace*{1mm}}|@{}r@{\hspace*{1mm}}|@{}}
\hline
\multicolumn{1}{@{}|@{}c@{\hspace*{1mm}}||}{c_{i,j}} &
\multicolumn{1}{c@{\hspace*{1mm}}|}{0.0} &
\multicolumn{1}{c@{\hspace*{1mm}}|}{0.1} &
\multicolumn{1}{c@{\hspace*{1mm}}|}{0.2} &
\multicolumn{1}{c@{\hspace*{1mm}}|}{0.3} &
\multicolumn{1}{c@{\hspace*{1mm}}|}{0.4} &
\multicolumn{1}{c@{\hspace*{1mm}}|}{0.5} &
\multicolumn{1}{c@{\hspace*{1mm}}|}{0.6} &
\multicolumn{1}{c@{\hspace*{1mm}}|}{0.7} &
\multicolumn{1}{c@{\hspace*{1mm}}|}{0.8} &
\multicolumn{1}{c@{\hspace*{1mm}}|}{0.9} &
\multicolumn{1}{c@{\hspace*{1mm}}|}{1.0} \\
\hline\hline
c_{1,1} & -- & -- &   -- &  -- &  -- & -- &  -- & -- & 0 & 100 & 140
 \\ \hline
c_{1,2} & -- & -- & -- & 0 & 10 & 70 &  100 &   140 &  310 &  520 & 600
 \\ \hline
c_{1,3} & -- & -- & -- &  -- &  -- &  0 &  15 &  25 &  70 &  90 & 150
 \\ \hline
c_{2,1} & -- & -- & -- &  -- &  0 & 30 &  40 &  70 &  120 & 200 & 270
 \\ \hline
c_{2,2} &  -- &  -- &  -- &  -- &  -- & -- & -- & 0 & 10 & 40 & 90
 \\ \hline
c_{2,3} & -- & -- & -- & -- &   0 & 70 &  90 & 100 & 180 & 300 & 450
 \\ \hline
\end{array}
\]
}
%
%
%
%
\label{ex:runex}
\end{example}

In Section~\ref{sec:briberymethods}, we describe three bribery
methods, i.e., three specific ways 
in which The Lobby can influence the voters.  These
will be referred to as \textsc{B}$_i$, $i \in \{1,2,3\}$.  
In addition to the three 
bribery methods described in Section~\ref{sec:briberymethods},
we also define two ways in which The Lobby can win
a set of votes.  These evaluation criteria are defined
in Section~\ref{sec:eval}
and will be referred to as \textsc{C}$_j$, $j \in \{1,2\}$.
They are important because votes counted in different ways can result
in different outcomes depending on voting and evaluation systems (cf.\
Myerson and Weber~\cite{mye-web:j:theoryofvoting}).


%
We now introduce the six basic problems that we will study.  For $i
\in \{1,2,3\}$ and $j \in \{1,2\}$, we define:


\begin{description}
\item[Name:] \textsc{B$_i$-C$_j$ Probabilistic Lobbying Problem}
($\plp{i}{j}$, for short).
\item[Given:] A probability matrix 
$P \in \matrixrationalszeroone{m}{n}$ with 
table $C_P$ of price functions,
a target vector $\vec{Z} \in \{0,1\}^{n}$, and a budget~$B$.
\item[Question:] Is there a way for The Lobby to influence $P$ (using
bribery method \textsc{B}$_i$ and evaluation criterion
\textsc{C}$_j$,
%
without exceeding budget $B$) such that the result of the votes on all
issues equals $\vec{Z}$?
\end{description}

\subsection{Bribery Methods}
\label{sec:briberymethods}
We begin by first formalizing the bribery methods by which 
The Lobby can influence votes on issues.  We will define three
methods for donating this money.

\subsubsection{Microbribery (\textsc{B}$_1$)}

The first method at the disposal of The Lobby
is what we will call \emph{microbribery}.
\Omit{\footnote{Although our
  notion was inspired by theirs, we stress that it should not be
  confused with the term ``microbribery'' used by Faliszewski et
  al.~\cite{fal-hem-hem-rot:c:llull,fal-hem-hem-rot:c:copeland-fully-resists-constructive-control,fal-hem-hem-rot:j:llull-copeland-full-techreport}
  in the different context of bribing ``irrational'' voters in
  Llull/Copeland elections via flipping single entries in their
  preference tables.}}  We define microbribery to be the editing of
individual elements of the $P$ matrix according to the costs in the
$C_P$ matrix.  Thus The Lobby picks not only which voter
to influence but also which issue to influence for that voter.  This
bribery method allows the most flexible version of bribery, and models
private donations made to candidates in support of specific issues.

\subsubsection{Issue Bribery (\textsc{B}$_2$)}

The second method at the disposal of The Lobby
is \emph{issue bribery}.  We can see from the $P$ matrix that each
column represents how the voters think about a particular issue.  In
this method of bribery, The Lobby can pick a column of the matrix and
edit it according to some budget.  The money will be equally
distributed among all the voters and the voter probabilities will move
accordingly. So, for $d$ dollars each voter
receives a fraction of $\nicefrac{d}{m}$
and their probability of voting ``yes''
changes accordingly.  This can be thought of as special-interest group
donations.  Special-interest groups such as PETA focus on issues and
dispense their funds across an issue rather than by voter.  The
bribery could be funneled through such groups.

\subsubsection{Voter Bribery (\textsc{B}$_3$)}

The third and final method at the disposal of The Lobby
is \emph{voter bribery}.  We can see from the $P$
matrix that each row represents what an individual voter thinks about
all the issues on the docket.  In this method of bribery, The Lobby
picks a voter and then pays to edit the entire row at once with the
funds being equally distributed over all the issues.  So, for
$d$ dollars a fraction of $\nicefrac{d}{n}$
is spent on each issue, which
moves accordingly.  The cost of moving the voter is generated using
the $C_P$ matrix as before.  This method of bribery is analogous to
``buying'' or pushing a single politician or voter.  The Lobby seeks
to donate so much money to an individual voter that he or she has no
choice but to move his or her votes toward The Lobby's agenda.

\subsection{Evaluation Criteria}
\label{sec:eval}
Defining criteria for how an issue is won is the next important step in 
formalizing our models.  Here we define two methods
that one could use to evaluate the eventual outcome of a vote.  
Since we are focusing on problems that are probabilistic in nature,
it is important to 
note that no evaluation criteria will guarantee a win.  
The criteria below yield different 
outcomes depending on the model and problem instance.

\subsubsection{Strict Majority (\textsc{C}$_1$)}

For each issue, a strict majority of the individual voters have
probability at least some threshold, $t$, of voting according to the
agenda.  In our running example (see Example~\ref{ex:runex}), with
$t=50\%$, the result of the votes would be $\vec{X} = (0,0,0)$,
because none of the issues has a strict majority of voters with above
$50\%$ likelihood of voting according to the agenda.

\subsubsection{Average Majority (\textsc{C}$_2$)}

For each issue, $r_{j}$, of a given probability matrix~$P$, we define:
$\overline{p_{j}} = \nicefrac{\left(\sum^{m}_{i=1} p_{i,j}\right)}{m}$.
We can now evaluate the vote to say that $r_{j}$ is 
accepted if and only if $\overline{p_{j}} > t$ where $t$ 
is some threshold.  
This would, in our running example, with $t = 50\%$, 
give us a result vector of $\vec{X} = (1,0,0)$.

\subsection{Issue Weighting}
\label{sec:issueweighting}
Our %
modification to the model will bring in the concept of issue 
weighting.  It is reasonable to surmise that certain issues will
be of more importance to The Lobby than others.  For this 
reason we will allow The Lobby to specify higher weights to the 
issues that they deem more important.  These weights 
will be defined for each issue.

We will specify these weights as a vector $\vec{W} \in \integers^{n}$
with size $n$ equal to the total number of issues in our problem
instance.  The higher the weight, the more important that particular
issue is to The Lobby.
%
%
Along with the weights for each issue we are also given an objective
value $O \in \integers^{+}$ which is the minimum weight The Lobby
wants to see passed.
%
%
%
%
Since this is a partial ordering, it is possible
for The Lobby to have an ordering such as:
$w_1 = w_2 = \cdots = w_n$.  If this is the case,
we see that we are left with an instance of $\plp{i}{j}$.

We now introduce the six probabilistic lobbying problems with issue
weighting.  For $i \in \{1,2,3\}$ and $j \in \{1,2\}$, we define: 

\begin{description}
\item[Name:] \textsc{B$_i$-C$_j$-Probabilistic Lobbying Problem with
Issue Weighting} (\plpiw{i}{j}, for short).
\item[Given:] A probability matrix $P \in
\matrixrationalszeroone{m}{n}$ with table $C_P$ of price functions and
a lobby target vector $\vec{Z} \in \{0,1\}^{n}$, a lobby weight vector
$\vec{W} \in \integers^{n}$, an objective value $O \in \integers^{+}$,
and a budget~$B$.
\item[Question:] Is there a way for The Lobby to influence $P$ (using
  bribery method \textsc{B}$_i$ and evaluation criterion
  \textsc{C}$_j$, without exceeding budget $B$) such that the total
  weight of all issues for which the result coincides with The Lobby's
  target vector $\vec{Z}$ is at least~$O$?
\end{description}

%
\section{Complexity-Theoretic Notions}
\label{sec:background-parameterized-complexity}

We assume the reader is familiar with standard notions of (classical)
complexity theory, such as $\p$, $\np$, and $\np$-completeness.  Since
we analyze the problems stated in
Section~\ref{sec:models-for-probabilistic-lobbying} not only in terms
of their classical complexity, but also with regard to their
\emph{parameterized} complexity,
%
we provide some basic notions here
%
%
(see, e.g., Downey and
Fellows~\cite{dow-fel:b:parameterized-complexity}
for more background).  As we derive our
results in a rather specific fashion, we will employ the ``Turing
way'' as proposed by
Cesati~\cite{ces:j:turing-way-parameterized-complexity}.

A \emph{parameterized problem} $\mathcal{P}$ is a subset of $\Sigma^*
{\times} \nat$, where $\Sigma$ is a fixed alphabet and $\nat$ is the
set of nonnegative integers. %
Each instance of the
parameterized problem $\mathcal{P}$ is a pair $(I, k)$, where the
second component $k$ is called the {\it parameter}. The language
$L(\mathcal{P})$ is the set of all \YES\ instances of $\mathcal{P}$. 
%
 The parameterized problem $\mathcal{P}$ is {\it
fixed-parameter tractable} if there is an algorithm (realizable by a
deterministic Turing machine) that decides whether an input $(I, k)$
is a member of $L(\mathcal{P})$ in time $f(k)|I|^c$, where $c$ is a
fixed constant and $f$ is a function whose argument $k$ is independent
of the overall input length, $|I|$. The class of all fixed-parameter
tractable problems is denoted by $\FPT$.

\Omit{
The $\Oh^*(\cdot)$ notation has by now become standard in
%
 exact
algorithms.  It neglects not only constants (as the more
familiar $\Oh(\cdot)$-notation does) but also polynomial factors in the
function estimates.  Thus, a problem is in $\FPT$ if and only if an
instance (with parameter $k$) can be solved in time $\Oh^*(f(k))$ for
some computable function~$f$.
}

There is also a theory of parameterized hardness
(see, e.g., \cite{dow-fel:b:parameterized-complexity}), most notably 
the $\wt{t}$ hierarchy,
which complements fixed-parameter tractability:
$\FPT = \wt{0} \subseteq \wt{1} \subseteq \wt{2} \subseteq \cdots$.
It is commonly believed that this hierarchy is strict.
%
Only the second level, $\wtwo$, will be of interest to us
in this paper (see, e.g., \cite{dow-fel:b:parameterized-complexity}
for the definition).
%
%
%

\Omit{
A \emph{parameterized reduction} is a function $r$ that,
for some polynomial $p$ and some function $g$, 
is computable in  time $\Oh(g(k)p(\problemsize{I}))$
 and maps an instance
$(I,k)$ of  $\mathcal{P}$ onto an instance
$r(I,k)=(I',k')$ of  $\mathcal{P}'$
such that 
%
%
$(I,k)$ is a \YES\ instance of  $\mathcal{P}$ if and only if 
$(I',k')$  is a \YES\ instance of  $\mathcal{P}'$
and 
%
$k'\leq g(k)$.
%
We then say that  $\mathcal{P}$ \defines{reduces to} $\mathcal{P}'$.


$\wtwo$ can be characterized by the following problem on Turing machines:
%
%
%
%
%
%
%
\begin{description}
\item[Name:] \textsc{Short Nondeterministic Turing Machine Computation}
(\textsc{SMNTMC}, for short).
\item[Given:] A multi-tape nondeterministic Turing machine $M$ (with
 two-way infinite tapes) and an input string $x$ (both $M$ and $x$ are
 given in some standard encoding).
\item[Parameter:] A positive integer $k$.
\item[Question:] Is there an accepting computation of $M$ on input $x$
 that reaches a final accepting state in at most $k$ steps?
\end{description}


More specifically, a parameterized problem $\mathcal{P}$ is in $\wtwo$
if and only if it can be reduced to \textsc{SMNTMC} via a
parameterized reduction, see
Cesati~\cite{ces:j:turing-way-parameterized-complexity}.  This can be
accomplished by giving an appropriate multi-tape nondeterministic
Turing machine for solving $\mathcal{P}$.  Hardness can be shown by
giving a parameterized reduction in the opposite direction, from
\textsc{SMNTMC} to~$\mathcal{P}$.
}

The complexity of a classical problem depends on the chosen
parameterization.  For problems that involve a budget $B\in\nat$ (and
hence can be viewed as minimization problems),
%
the most obvious parameterization would be the given budget bound~$B$.  In
this sense, we state parameterized results in this paper.  (For
other applications of fixed-parameter tractability and parameterized
complexity to problems from computational social choice, see,
e.g.,~\cite{lin-rot:mpg:fpt-comsoc}.)
            









%




\section{Classical Complexity Results}
\label{sec:classical-complexity}
%
%
We now provide a formal complexity analysis of the
probabilistic lobbying problems for all
combinations of evaluation criteria and bribery methods.
%
%
%
%
%
%
%
%
%


Table~\ref{tab:plp} summarizes our results for $\plp{i}{j}$, $i \in
\{1,2,3\}$ and $j \in \{1,2\}$.  Some of these results are known from
previous work by Christian et al.  \cite{chr-fel-ros-sli:j:lobbying},
as will be mentioned below.  In this sense, our results generalize the
results of~\cite{chr-fel-ros-sli:j:lobbying} by extending the model to
probabilistic settings.

\begin{table}[tb]
\caption{Complexity results for \plp{i}{j}}
\centering
\begin{tabular}{|c||c|c|}
\hline
 Bribery   &\multicolumn{2}{|c|}{Evaluation Criterion}\\ \cline{2-3}
 Criterion & \textsc{C}$_1$ & \textsc{C}$_2$          \\ \hline\hline
\textsc{B}$_1$ & $\p$              & $\p$       \\ \hline
\textsc{B}$_2$ & $\p$              & $\p$       \\ \hline
\textsc{B}$_3$ & $\wtwo$-complete  & $\wtwo$-complete \\ \hline
\end{tabular}
\label{tab:plp}
\end{table}


\subsection{Microbribery}

%
%
%
%

The following result can be easily seen.

\begin{theorem}
\label{thm:B1C1PLP}
$\plp{1}{1}$ is in~$\p$.
\end{theorem}

\Omit{
\begin{proofs}
The aim is to win all referenda.  Per referendum $r$ and voter $v$, we
can compute in polynomial time the amount $b(r,v)$ The Lobby has to
spend to turn the favor of $v$ in the direction of The Lobby (beyond
the given threshold $t$).  In particular, set $b(r,v)=0$ if voter $v$
would already vote according to the agenda of The Lobby.  For each
issue $r$, sort $\{b(r,v)\mid 1\leq v\leq m\}$ increasingly, yielding
the sequence $b_1(r)$, \dots, $b_n(r)$.  To win referendum~$r$, The
Lobby must spend at least $B(r)=\sum_{i\leq (m+1)/2}b_i(r)$ dollars.
Hence, all referenda can be won if and only if $\sum_{r=1}^nB(r)$ is
at most the given bribery budget $B$.~\end{proofs}
}

The complexity of microbribery with evaluation criterion
\textsc{C}$_2$ is somewhat harder to determine.
We use the following auxiliary
problem. %
Here, a \emph{schedule} $S$ of $q$ jobs (on a single
  machine) is a sequence $J_{i(1)}, \ldots , J_{i(q)}$ such that
  $J_{i(r)}=J_{i(s)}$ implies $r=s$.  The \emph{cost of schedule $S$}
  is $c(S)=\sum_{k=1}^q c(J_{i(k)})$.  $S$ is said to \emph{respect the
  precedence constraints} of graph $G$ if for every (path)-component
  $P_i=J_{i,1}, \ldots , J_{i,p(i)}$ and for each $k$ with $2 \le k
  \le p(i)$, we have: If $J_{i,k}$ occurs in the schedule $S$ then
  $J_{i,k-1}$ occurs in $S$ before $J_{i,k}$.
%


\begin{description}
\item[Name:] {\sc Path Schedule}
\item[Given:] A set $V=\{J_1, \ldots , J_n\}$ of jobs, a directed
  graph $G=(V,A)$ consisting of pairwise disjoint paths $P_1,\ldots,
  P_z$, two numbers $C,q \in \mathbb{N}$, and
%
%
a cost function $c:V \to \mathbb{N}$.
\item[Question:]
%
%
%
Can we find a schedule $J_{i(1)},\ldots,J_{i(q)}$ of $q$ jobs of cost
at most $C$ respecting the precedence constraints
of~$G$?
\end{description}

%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

{\sc Path Schedule} is in~$\p$ by dynamic programming. Then we show how to
reduce $\plp{1}{2}$ to {\sc Path Schedule}, which implies that
$\plp{1}{2}$ is in $\p$ as well.

\begin{lemma}
\label{lem:mps}
\textsc{Path Schedule} is in~$\p$.
\end{lemma}

\Omit{
\begin{proofs}The following dynamic programming approach finally calculates
$T[\{P_1,\ldots ,P_z\},q]$, which gives the minimum cost to solve the
problem. 
We build up a table $T[\{P_1,\ldots ,P_\ell\},j]$ storing the
minimum cost of scheduling $j$ jobs out of the jobs contained in the
paths $P_1,\ldots, P_\ell$.  %
%
%
Let 
$P_i=J_{i,1}, \ldots , J_{i,p(i)}$. 
Clearly, for $k\leq p(1)$, 
$T[\{P_1\},k]=\sum_{s=1}^kJ_{1,s}$. 
For $k>p(1)$, set $T[\{P_1\},k]=\infty$. 
If $\ell>1$, 
$T[\{P_1,\ldots,P_\ell\},j]$ equals $\min_{0 \le k \le
  \min\{j,p(\ell)\}} T[\{P_1,\ldots ,P_{\ell-1}\},j-k] + \sum_{s=1}^k
c(J_{\ell,s})$.  Consider each possible scheduling of the first
$k$ jobs of~$P_\ell$.  For the remaining $j-k$ jobs, look up a
solution in the table.  
%
%
Notice that we can re-order each schedule $S$ so that all jobs from
one path contiguously appear in $S$, without violating the precedence
constraints by this re-ordering, nor changing the cost of the schedule. 
Hence, $T[\{P_1,\ldots ,P_z\},q]$ gives the minimum schedule cost. 
%
%
%
The number of entries in the table is $z\cdot q$, and computing each entry $T[\{P_1,\dots, P_\ell\},\cdot]$ 
is linear in $p(\ell)$ (for each $1\leq \ell\leq z$), which leads to a run time of the
dynamic programming algorithm that is polynomially bounded by the input size.~\end{proofs}
}

\begin{theorem}
\label{thm:plp12-is-in-p}
$\plp{1}{2}$ is in~$\p$.
\end{theorem}

\begin{proofs}
Let $(P,C_P,\vec{Z},B)$ be a given $\plp{1}{2}$ instance, where $P \in
\matrixrationalszeroone{m}{n}$, $C_P$ is a table of price functions,
$\vec{Z} \in \{0,1\}^{n}$ is The Lobby's target vector, and $B$ is its
budget.  For $j \in \{1, 2, \ldots, n\}$, let $d_j$ be the minimum
cost for The Lobby to bring referendum $r_j$ into line with the $j$th
entry of its target vector~$\vec{Z}$. If $\sum_{j=1}^n d_j \le B$ then
The Lobby can achieve its goal that the votes on all issues equal
$\vec{Z}$.  We now focus on the first task. For every~$r_j$, create an
equivalent \textsc{Path Scheduling} instance.  First, compute for
$r_j$ the minimum number $b_j$ of bribery steps needed to achieve The
Lobby's goal on~$r_j$.  That is, choose the smallest $b_j \in
\mathbb{N}$ such that $\overline{p_j}+\nicefrac{b_j}{(k+1)m} >t$.
Now, for every voter~$v_i$, derive a path $P_i$ from the price
function $c_{i,j}$. Let $s$, $0 \le s \le k+1$, be minimum with the
property $c_{i,j}(s)\in \mathbb{N}_{>0}$. Then create a path $P_i =
p_s, \ldots , p_{k+1}$, where $p_h$ represents the $h$th entry of
$c_{i,j}$ (viewed as a vector).  Assign the cost $\hat c(p_h)=
c_{i,j}(h)-c_{i,j}(h-1)$ to $p_h$. Observe that $\hat c(p_h)$
represents the cost of raising the probability of voting ``yes'' from
$\nicefrac{(h-1)}{(k+1)}$ to $\nicefrac{h}{(k+1)}$.  In order to do
so, we must have reached
%
an acceptance probability of $\nicefrac{(h-1)}{(k+1)}$ first.  Now,
let the number of jobs to be scheduled be
%
$b_j$.  Note that one can take $b_j$ bribery steps at
the cost of $d_j$ dollars if and only if one can schedule $b_j$ jobs
with a cost of~$d_j$. Hence, we can decide whether or not
$(P,C_P,\vec{Z},B)$ is in $\plp{1}{2}$ by using 
\Omit{the dynamic program
given in the proof of }Lemma~\ref{lem:mps}.~\end{proofs}




%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

\Omit{
\begin{proofs}
%
%
 We focus on \textsc{Exact}-$\plp{1}{1}$ and note that the reduction
can be carried over straightforwardly to the case of
\textsc{Exact}-$\plp{1}{2}$.  

To see membership in $\np$, observe that an instance $I$ of \textsc{Exact}-$\plp{1}{j}$
can be transformed into another instance $I'$ of \textsc{Exact}-$\plp{1}{j}$
after guessing which issue and which voter should be bribed by an amount
of money specified by the first non-zero entry in the corresponding row of the cost matrix $C_P$ and
modifying $C_P$ accordingly. After repeated guesses, we either arrive at
an amount of left-over money that cannot be used for any bribery anymore
(since it is either too small or possibly no money can be spent at all, since
all issues and voters have been ``completely bribed''); 
in this case, the nondeterministic procedure simply stops.
Or, all money was (exactly) spent. In that case, it is 
checked if the evaluation criterion was met.
If it is met, the algorithm gives and affirmative answer;
otherwise, it rejects.
Hence, the nondeterministic procedure will either succeed in one branch,
yielding an affirmative answer, or there is no solution, and no affirmative
answer will be produced.

To show $\np$-hardness of
\textsc{Exact}-$\plp{1}{1}$, we provide a reduction from
\textsc{Subset Sum} (see, e.g., Garey and
Johnson~\cite{gar-joh:b:int}): Given $a_1,\ldots , a_n, S \in
\mathbb{N}^{+}$, does there exist a subset $I \subseteq \{1,\ldots
,n\}$ such that $\sum_{i \in I} a_i=S$?  For such a \textsc{Subset
  Sum} instance, create an \textsc{Exact}-$\plp{1}{1}$ instance with
only one referendum $r_1$ and with voters $v_1,\ldots , v_{2n}$. Let
$k=0$. Set $P_{i1}=1$ and $c_{i1}(1)=0$ for $1 \le i \le n$, and set
$P_{i1}=0$, $c_{i1}(0)=0$, $c_{i1}(1)=a_{i-n}$ for $n+1 \le i \le
2n$. Let $B=S$ and $t=0.5$. Observe that we have to influence at least
one of the voters not in accordance with~$r_1$. Thus we can turn $r_1$
to The Lobby's favor by spending exactly $B$ dollars on a set of
voters $v_{i_1},\ldots, v_{i_\ell}$ ($n+1\le i_j \le 2n$) if and only
if there is a subset $I \subseteq \{1,\ldots ,n\}$, $|I|=\ell$, such
that $\sum_{i \in I} a_i=S$.~\end{proofs}
}

\subsection{Issue Bribery}

A greedy strategy succeeds for proving:

\begin{theorem}
\label{thm:plp21}
$\plp{2}{1}$ and $\plp{2}{2}$ are in $\p$.
\end{theorem}

\Omit{
\begin{proofs}
We prove that $\plp{2}{1}$ is in $\p$; the proof for \plp{2}{2} is
analogous.  Observe that $\plp{i}{j}$ (just like the problem $\ol$
defined in Section~\ref{sec:parameterized-complexity}) contains a
vector that represents the issues that The Lobby would like to see
passed.  In Theorem~\ref{thm:plpw2} below (see
Section~\ref{sec:parameterized-complexity}), the constraint from
$\ol$, $b$, is expressed over the number of \emph{voters} that need to
be influenced.  In $\plp{2}{1}$, however, we are required to influence
a certain number of issues.  Thus, in order to determine a win we
construct a \emph{cost difference} matrix representing how much it
would cost The Lobby to win each issue (since all voters receive the
same amount of money, this can be determined in time polynomial in the
number of voters and issues).  Using this cost difference matrix, we
greedily select the cheapest issues to influence in order to achieve
The Lobby's agenda.~\end{proofs}
}

\subsection{Probabilistic Lobbying with Issue Weighting}

\begin{table}[tb]
\caption{Complexity results for $\plpiw{i}{j}$}
\centering
\begin{tabular}{|c||c|c|}
\hline
 Bribery   &\multicolumn{2}{|c|}{Evaluation Criterion}\\ \cline{2-3}
 Criterion & \textsc{C}$_1$ & \textsc{C}$_2$ \\ \hline \hline
\textsc{B}$_1$ & $\np$-compl., $\FPT$ & $\np$-compl., $\FPT$ \\ \hline
\textsc{B}$_2$ & $\np$-compl., $\FPT$ & $\np$-compl., $\FPT$ \\ \hline
\textsc{B}$_3$ & $\wtwo$-complete & $\wtwo$-complete \\ \hline
\end{tabular}
\label{tab:plpiw}
\end{table}

Table~\ref{tab:plpiw} summarizes our results for $\plpiw{i}{j}$, $i
\in \{1,2,3\}$ and $j \in \{1,2\}$.  The most interesting
%
observation
%
is that introducing issue weights raises the complexity from
%
$\p$ to $\np$-completeness for all cases of microbribery and issue
bribery by using \textsc{Knapsack} in the reduction (though it remains the same for voter bribery).  Nonetheless,
we show later as Theorem~\ref{thm-issueweighted-FPT} 
that these $\np$-complete problems are fixed-parameter tractable.
%
%

%
%
%

\begin{theorem}
\label{thm:plpiw-11-12-21-22-is-np-hard}
For $i,j \in \{1,2\}$, $\plpiw{i}{j}$ is $\np$-complete.
\end{theorem}

\Omit{
\begin{proofs}
Membership in $\np$ is easy to observe for each problem
$\plpiw{i}{j}$, where $i,j \in \{1,2\}$.

To prove that $\plpiw{1}{1}$ is $\np$-hard, we give a reduction from
\textsc{Knapsack} to $\plpiw{1}{1}$.  In \textsc{Knapsack}, we are
given a set of objects $U=\{o_1,\ldots , o_n\}$ with weights $w:U \to
\mathbb{N}$ and profits $p:U \to \mathbb{N}$, and $W,P \in
\mathbb{N}$.  The question is whether there is a subset $I \subseteq
\{1,\ldots ,n\}$ such that $\sum_{i \in I} w(o_i) \le W$ and $\sum_{i
  \in I} p(o_i) \ge P$.  Given a \textsc{Knapsack} instance
$(U,w,p,W,P)$, create a $\plpiw{1}{1}$ instance with $k=0$ and only
one voter, $v_1$,
%
%
where for each issue, $v_1$'s acceptance probability
%
is either zero or one.  For each object~$o_j \in U$, create
%
an issue $r_j$ such that the acceptance probability of $v_1$ is
zero. Let the cost of raising this probability on $r_j$ be
$c_{1,j}=w(o_j)$ and let the weight of issue $r_j$ be $w_j=p(o_j)$.  Let
The Lobby's budget be $W$ and its objective value be $O=P$.  By
construction,
%
there is a subset $I \subseteq \{1,\ldots ,n\}$ with $\sum_{i \in I}
w(o_i) \le W$ and $\sum_{i \in I} p(o_i) \ge P$ if and only if there
is a subset $I \subseteq \{1,\ldots ,n\}$ with $\sum_{i \in I} c_{1,i} \le
W$ and $\sum_{i \in I} w_i \ge O$.

%
%
%
%

As the reduction introduces only one voter, there is no difference
between the bribery methods \textsc{B}$_1$ and \textsc{B}$_2$, and no
difference either between the evaluation criteria \textsc{C}$_1$ and
\textsc{C}$_2$.  Hence, the above reduction works for all four
other problems.~\end{proofs}
}

\section{Parameterized Complexity Results}
\label{sec:parameterized-complexity}

\subsection{Voter Bribery}

Christian et al.~\cite{chr-fel-ros-sli:j:lobbying} proved that the
following problem is $\wtwo$-complete.
%
%
%
We state this problem here as is common in parameterized complexity:

\begin{description}
\item[Name:] \textsc{Optimal Lobbying} ($\ol$, for short).
\item[Given:] An $m {\times} n$ matrix~$E$ and a $0/1$ vector
$\vec{Z}$ of length $n$.  Each row of $E$ represents a voter.  Each
column represents an issue in the election.
%
%
The vector $\vec{Z}$ represents The Lobby's target outcome.
\item[Parameter:] A positive integer $k$
(representing the number of voters to be influenced).
\item[Question:] Is there a choice of $k$ rows of the matrix (i.e., of
$k$ voters) that can be changed such that in each column of the
resulting matrix (i.e., for each issue) a majority vote yields the
outcome targeted by The Lobby?
\end{description}

Christian et al.~\cite{chr-fel-ros-sli:j:lobbying} proved this problem
to be $\wtwo$-complete by a reduction from $k$-\textsc{Dominating Set}
to $\ol$ (showing the lower bound) and from $\ol$ to
\textsc{Independent}-$k$-\textsc{Dominating Set} (showing the upper
bound).
%
%
%
%
To employ the $\wtwo$-hardness result of Christian et
al.~\cite{chr-fel-ros-sli:j:lobbying}, we show that $\ol$ is a special
case of $\plp{3}{1}$ and thus (parameterized) polynomial-time reduces
to $\plp{3}{1}$.  The ``Turing'' approach suggested by 
Cesati~\cite{ces:j:turing-way-parameterized-complexity} shows membership
in $\wtwo$. 
%
Analogous arguments apply to $\plp{3}{2}$.

\Omit{
\begin{theorem}
For $j \in \{1,2\}$, $\plp{3}{j}$ (parameterized by the budget) is
$\wtwo$-hard.
\label{thm:plpw2}
\end{theorem}

\begin{proofs}
We first prove that $\plp{3}{1}$ is $\wtwo$-hard
%
%
by providing a parameterized reduction from
$\ol$ to $\plp{3}{1}$, where the parameter (number of voters to be
influenced by The Lobby) is the same in both problems.
We are given an instance $(E,\vec{Z},b)$ of $\ol$, where $E$ is a $m
{\times} n$ $0/1$ matrix, $b$ is the number of votes to be
edited, and $\vec{Z}$ is the agenda for The Lobby. We may assume
without loss of generality that $\vec{Z} = 1^{n}$.
%
%

We construct an instance of $\plp{3}{1}$ consisting of the given
matrix $P = E$ (a ``degenerated'' probability matrix with only the
probabilities $0$ and~$1$), a corresponding cost matrix~$C_P$, a
target vector $\vec{Z} = 1^{n}$, and a budget~$B$.  $C_P$ has two
columns (i.e., we have $k=0$, since the problem instance is
deterministic, see Section~\ref{sec:initialmodel}), one column for
probability $0$ and one for probability~$1$.  All entries of $C_P$ are
set to unit cost.

The cost of increasing any value in $P$ is $n$, since donations are
distributed evenly across issues for a given voter.  We want to know
whether there is a set of bribes of cost at most $b\cdot n=B$ such that
The Lobby's agenda passes.  This holds if and only if there are $b$
voters that can be bribed so that they vote uniformly according to The
Lobby's agenda and that is sufficient to pass all the issues.  Thus,
%
the given instance $(E,\vec{Z},b)$ is in $\ol$ if and only if the
constructed instance $(P, C_P, \vec{Z}, B)$ is in $\plp{3}{1}$, which
shows that $\ol$ is a polynomial-time recognizable special case of
$\plp{3}{1}$, and thus $\plp{3}{1}$ is $\wtwo$-hard.

Note that for the construction above it doesn't matter whether we use
the strict-majority criterion (\textsc{C}$_1$) or the average-majority
criterion (\textsc{C}$_2$).  Since the entries of $P$ are $0$ or~$1$,
we have $\overline{p_{j}} > 0.5$ if and only if we have a strict
majority of ones in the $j$th column.  Thus, $\plp{3}{2}$ is
$\wtwo$-hard too.
\end{proofs}
}

\begin{theorem}
For $j \in \{1,2\}$, $\plp{3}{j}$ (parameterized by the budget) is
$\wtwo$-complete.
\label{thm:plpw2-a}
\end{theorem}

\Omit{
\begin{proofs}
Again, we give only the details for the case of $\plp{3}{1}$; the
proof for $\plp{3}{2}$ is analogous.  $\wtwo$-hardness has been shown
in Theorem~\ref{thm:plpw2}.  To show membership in $\wtwo$, we reduce
$\plp{3}{1}$ to \textsc{SMNTMC}, which was defined in
Section~\ref{sec:background-parameterized-complexity}.  To this end,
it suffices to describe how a nondeterministic multi-tape Turing
machine can solve such a lobbying problem.


Consider an instance of $\plp{3}{1}$: a probability matrix $P \in
\matrixrationalszeroone{m}{n}$ with a table $C_P$ of price functions
and a budget $B$.  Again, we may assume that the target vector is
$\vec{Z} = 1^{n}$.  Moreover, we assume that the target threshold $t$
is fixed.  We can identify $t$ with a certain step level for the
%
price functions.

The reducing machine works as follows.  From $P$, $C_P$, and $t$, the
machine extracts the information $H_{i,j}(d)$, where $H_{i,j}(d)$ is
true if either $p_{i,j}\geq t$ or $c_{i,j}(t)\leq d/n$ (since
according to this scenario, the bribery money is distributed among all
issues).  Note that $H_{i,j}(d)$ captures whether paying $d$ dollars
to voter $v_i$ helps to raise the acceptance probability of $v_i$ on
referendum $r_j$ above the threshold~$t$.  Moreover, for each
referendum~$r_j$, we compute
%
the minimum number of voters that need to switch their opinion so that
majority is reached for that specific referendum; let $s(j)$ denote
this threshold for~$r_j$.  Since we assume payments in dollar units, a
referendum with $s(j)>B$ yields a \NO\ instance. We can therefore
replace any value $s(j)> B$ by the value $B+1$.

The nondeterministic multi-tape Turing machine $M$ we describe next
has, in particular, access to $H_{i,j}$ and to $s(j)$.  $M$ has $n+1$
working tapes $T_j$, $0\leq j\leq n$, all except one of which
correspond to issues~$r_j$, $1 \leq j \leq n$.  We will use the set of
voters, $V=\{v_1,\dots,v_m\}$, as alphabet.  The (formal) input tape
of $M$ is ignored.

$M$ starts by writing $s(j)$ symbols $\#$ onto tape~$j$ for each~$j$,
$1 \leq j \leq n$.  By using parallel writing steps, this needs at
most $B+1$ steps, since $s(j)\leq B+1$ as argued above.

Second, for each $i \in \{1,\dots,m\}$, $M$ writes $k_i$ symbols $v_i$
from the alphabet $V$ on the zeroth tape, $T_0$, such that
$\sum_{i=1}^{m} k_i\leq B$.  This is the nondeterministic guessing
phase where the amount of bribery money spent on each voter is
determined. Notice that no more than $B$ voters can be bribed.

In the third phase, for each voter $v_i$ that will be bribed, $M$
counts the corresponding amount $k_i$ of bribery money and determines
(by using $H_{i,j}$) if it is enough to change $v_i$'s opinion
regarding the $j$th issue.  If so, the head of $M$ on tape $j$ moves
one step to the left.  Again, all these head moves are performed in
parallel.  Hence, the string on the zeroth tape is being processed in
at most $B$ (parallel) steps.

Finally, it is checked if the left border is reached (again) for all
tapes~$T_j$, $j>0$.  This is the case if and only if the guessed
bribery was successful.~\end{proofs}
}

%
%
%
%

%
%
%
%
%
%

\subsection{Probabilistic Lobbying with Issue Weighting}
%


Recall from Theorem~\ref{thm:plpiw-11-12-21-22-is-np-hard} that
$\plpiw{i}{j}$, where $i,j \in \{1,2\}$, is $\np$-hard.
Theorem~\ref{thm-issueweighted-FPT} says
that each of these problems is fixed-parameter tractable when
parameterized by the
%
budget, using \textsc{Knapsack} again.

\begin{theorem}
\label{thm-issueweighted-FPT}
For $i,j \in \{1,2\}$, $\plpiw{i}{j}$ (parameterized by the budget) is
in $\FPT$.
\end{theorem}

\Omit{
\begin{proofs}
Since the four unweighted variants are in~$\p$, we can compute the
number
%
of dollars to be spent to win referendum $r_j$ in polynomial time in
each case.  Now re-interpret the given $\plpiw{i}{j}$ instance as a
\textsc{Knapsack} instance: Every issue $r_j$ is an object $o_j$ with
weight $d_j$ and profit $p_j$, both set to be the same as weight $w_j$
of issue~$r_j$.  Let the \textsc{Knapsack} bound be the total number
$B$ of dollars allowed to be spent.  Now use the pseudo-polynomial
algorithm to solve \textsc{Knapsack} in time $\Oh(n 2^{|B|})$, where
$|B|$ denotes the length of the encoding of~$B$.~\end{proofs}
}

%
%
%
%

%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%



%
%
%
%

%
%
%
%
%
%

%
%
%
%
%
%
%
%
%
%

Voter bribery with issue weighting remains $\wtwo$-complete for both
evaluation criteria; the membership proof is somewhat more involved than the
one in the unweighted case.

\begin{theorem}
\label{thm:plpiw31}
For $j \in \{1,2\}$, $\plpiw{3}{j}$ (parameterized by the budget) is
$\wtwo$-complete.
\end{theorem}

\Omit{
\begin{proofs}
By Theorem~\ref{thm:plpw2}, $\plp{3}{1}$ is $\wtwo$-hard.  Since
$\plp{3}{1}$ is a special case of $\plpiw{3}{1}$, where all the issues
have unit weight, $\plpiw{3}{1}$ is $\wtwo$-hard as well.  An
analogous argument shows that $\plpiw{3}{2}$ is $\wtwo$-hard, too.
%
%
%
%
%
%
%
%
%

Membership in $\wtwo$ is a bit more tricky than in the unweighted case
from Theorem~\ref{thm:plpw2-a}.  In the following, we indicate only
the necessary modifications:
\begin{itemize}
 \item The reducing machine calculates the difference $O'$ between the
target weight and the sum of the weights of the referenda that are
already won.
\item For each referendum that is not already won, the reducing
machine introduces a special letter $r_i$ to be used on the zeroth
tape.
\item The Turing machine that has been built at the very beginning
also guesses at most $B$ referenda that (additionally) should be
won. (Note that influencing any issue costs at least one dollar.)
Then, the Turing machine will spend $\Oh(f(B))$ time to calculate
if winning those guessed referenda $r_{i1},\dots,r_{ib}$, $b\leq B$,
would be sufficient to get beyond the threshold. Only if sufficiency
is guaranteed, the Turing machine continues working.
\item The Turing machine will then continue to work as described in
  the proof of Theorem~\ref{thm:plpw2-a}.
\item At the very end, the Turing machine will verify in at most $B$
  steps if all referenda guessed in the very beginning have been won.
\end{itemize}

Note that it is quite tempting to try to avoid the weight calculations
within the Turing machine, letting the reducing machine do this
job. However, this seems to necessitate coding the winning situations
in the state set of the Turing machine, leading to a possible
exponential size of this Turing machine (measured in the overall input
size of the voting scenario).


$\wtwo$-completeness of $\plpiw{3}{2}$ can be proven by an analogous
argument.~\end{proofs}
}


%
%
%
%

%
%
%
%
%
%
%
%
%
%

%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

\section{Approximability}

As seen in Tables~\ref{tab:plp} and~\ref{tab:plpiw}, many problem
variants of probabilistic lobbying are $\np$-complete.
Hence, it is interesting to
study them not only from the viewpoint of parameterized complexity,
but also from the viewpoint of approximability.

The budget constraint on the bribery problems studied so far gives
rise to natural minimization problems: Try to minimize the amount
spent on bribing.  For clarity, let us denote 
these minimization problems by prefixing the problem name with MIN,
leading to, e.g., $\MIN$-$\ol$.
%
%
%
%

%
%

The already mentioned reduction of Christian et
al.~\cite{chr-fel-ros-sli:j:lobbying} (that proved that $\ol$ is
$\wtwo$-hard) is parameter-preserving (regarding the budget). It
further has the property that a possible solution found in the $\ol$
instance can be re-interpreted as a solution to the
\textsc{Domininating Set} instance the reduction started with, and the
$\ol$ solution and the \textsc{Domininating Set} solution are of the
same size. This in particular means that inapproximability results for
\textsc{Domininating Set} transfer to inapproximability results for
$\ol$. Similar observations are true for the interrelation of
\textsc{Set Cover} and \textsc{Dominating Set}, as well as for $\ol$
and $\plpiw{3}{1}$ (or $\plpiw{3}{2}$).

The known inapproximability
results~\cite{bel-gol-lun-rus:c:efficient-pcp-approximations,raz-saf:c:subconstant-lowdegree-test-pcp} for
\textsc{Set Cover} hence give the following result (see also
Footnote~4
in~\cite{san-sur-gil-lev:c:combinatorial-auction-generalizations}).
%

%

\begin{theorem} 
%
There is a constant $c>0$ such that %
$\MIN$-$\ol$
%
is not approximable within factor
$c\cdot\log(n)$ unless $\np\subset\dtime(n^{\log\log(n)})$,
where $n$ denotes the number of issues.
\end{theorem}

Since $\ol$ can be viewed as a special case of both $\plp{3}{i}$ and
$\plpiw{3}{i}$ for $i \in \{1,2\}$, we have the following corollary.

\begin{corollary}
For $i \in \{1,2\}$, there is a constant $c_i>0$ such that 
%
%
both $\MIN$-$\plp{3}{i}$ and $\MIN$-$\plpiw{3}{i}$ are not
approximable within factor $c_i\cdot \log(n)$ unless
$\np\subset\dtime(n^{\log\log(n)})$, where $n$ denotes the number of
issues.
\end{corollary}


\Omit{
Conversely, a logarithmic-factor approximation can be given for the minimum-budget versions
of all our
problems, as we will show now. We first discuss the relation to the well-known \textsc{Set Cover} problem,
sketching a tempting reduction and discussing the pitfalls of this reduction. This motivates
that we shall later give a complete approximation algorithm for $\MIN$-$\plp{3}{2}$.
Moreover, we define the notion of cover number that allows to state 
inapproximability results for $\MIN$-$\plp{3}{2}$.
Similar results hold for  $\MIN$-$\plp{3}{1}$, the constructions
being sketched at the end of the section. 


Voter bribery problems are closely related to set cover problems, in
particular in the average-majority scenario, so that we should be able to carry over
approximability ideas from that area.  The intuitive translation of a $\MIN$-$\plp{3}{2}$ instance
into a \textsc{Set Cover} instance is as follows: The universe of the derived
\textsc{Set Cover} instance should be the set of
issues, and the sets (in the \textsc{Set Cover} instance) are formed by considering the sets of
issues that could be influenced (by changing a voter's opinion)
through bribery of a specific voter.  Namely, when we pay voter $v$ a
specific amount of money, say $d$ dollars, he will invest 
$\nicefrac{d}{n}$ dollars to each issue and possibly change $v$'s opinion
(or at least raise $v$'s acceptance probability to the ``next
level'').  The weights associated to the sets of issues correspond to
the bribery costs that are (minimally) incurred to lift the issues in
the set to some ``next level.''
There are four differences to classical set covering problems:
\begin{enumerate}
\item We cannot neglect the voter who has been bribed, so different
  voters (with different bribing costs) may
%
  be associated with the same set of issues.
\item The sets associated with one voter are not independent. For each voter,
the sets of issues that can be influenced by bribing that voter are linearly
ordered by set inclusion. Moreover, when bribing a specific voter, we have
  to first influence the ``smaller sets'' (which might be expensive)
  before possibly influencing the ``larger ones''; so, weights are
  attached to set differences, rather than to sets.
\item
}
 A \emph{cover number} $c(r_j)$ is associated with each
  issue~$r_j$, indicating by how many levels voters must raise their
  acceptance probabilities in order to arrive at average majority
  for~$r_j$.  The cover numbers can be computed beforehand
  for a given instance.  Then, we can also associate cover numbers to
  sets of issues (by summation), which finally leads to the cover
  number $N=\sum_{j=1}^n c(r_j)$ of the whole instance.
\Omit{
\item The money paid ``per issue'' might not have been sufficient for
  influencing a certain issue up to a certain level, but it is not
  ``lost''; rather, it would make the next bribery step cheaper, hence
  (again) changing weights in the
%
set cover interpretation. 
%
%
\end{enumerate}

To understand these connections better, let us have another look at
our running example (under the voter bribery with average-majority
evaluation), assuming an all-ones target vector.  If we paid 30
dollars to voter~$v_1$, he or she would invest 10 dollars to each
issue, which would raise his or her acceptance probability for the
second issue from .3 to .4; no other issue level is changed.  Hence,
this would
%
correspond to a set containing only $r_2$ with weight 30.  Note that
by this bribery, the costs for raising the acceptance probability of
voter $v_1$ to the next level would be lowered for the other two
issues. For example, spending 15 more dollars on $v_1$ would raise
$r_3$ from .5 to .6, since all in all 45 dollars have been spent on
voter $v_1$, which means 15 dollars per issue.  If the threshold is
60\% in that example, then the first issue is already accepted (as
desired by The Lobby), but the second issue has gone up from .5 to .6
on average, which means that we have to raise either the acceptance
probability of one voter by two levels (for example, by paying 210
dollars to voter~$v_1$), or we have to raise the acceptance
probability of each voter by one level (by paying 30 dollars to voter
$v_1$ and another 30 dollars to voter~$v_2$).  This can be expressed
by saying that the first issue has a cover number of zero, and the
second has a cover number of two.
}

When we interpret an $\ol$ instance as a $\plp{3}{2}$ instance, 
the cover number of that resulting instance equals the number of issues, 
assuming that the votes for all issues need amendment.
%
Thus we have the following corollary:
%

\begin{corollary}
%
There is a constant $c>0$ such that %
$\MIN$-$\plp{3}{2}$ is not approximable within factor
$c\cdot \log(N)$ unless $\np\subset\dtime(N^{\log\log(N)})$, where
$N$ is the cover number of the given instance.
A fortiori, the same statement holds for
 $\MIN$-$\plpiw{3}{2}$. 
\end{corollary}

Let $H$ denote the harmonic sum function, i.e., $H(r)=\sum_{i=1}^r
\nicefrac{1}{i}$.  It is well known that $H(r)=O(\log(r))$. More
precisely, it is known that
\[
\left\lfloor \ln r \right\rfloor \leq H(r) \leq \left\lfloor \ln
r\right\rfloor +1.
\]

We show the following theorem by providing and
analyzing a greedy approximation algorithm.

\begin{theorem}
\label{thm:plp-32-approximation}
$\MIN$-$\plp{3}{2}$
%
can be approximated within a factor of $\ln(N)+1$, where $N$ is the
cover number of the given instance.
\end{theorem}

\Omit{
\begin{proofs}
Consider the following greedy algorithm (given threshold $t$ and
assuming (w.l.o.g.) the target vector $\vec{1}$); notice that the
cover numbers (per referendum) can be computed from the cost matrix
$C_P$ and the threshold $t$ before calling the algorithm the very
first time:

\smallskip

\noindent
{\bf Greedy Voter Bribery} (GVB):\\
\underline{Input:} A probability matrix $P \in
\matrixrationalszeroone{m}{n}$ (implicitly specifying a set $V$ of $m$
voters and a set $R$ of $n$ referenda),
%
a cost matrix $C_P$, and $n$ cover numbers
%
$c(r_1), \ldots , c(r_n) \in \mathbb{N}$.
%
%
%
%
%
%
%
%
%
%
%
%
\begin{enumerate}
\item Delete referenda that are already won (indicated by $c(r_j)=0$),
  and modify $R$ and $C_P$ accordingly.
\item If $R=\emptyset$, STOP.
\item For each voter $v$, compute the cheapest amount of money, $d_v$,
  that allows to raise any level in $C_P$. Let $n_v$ be the number of
  referenda whose levels are raised when spending $d_v$ dollars on
  voter~$v$.
\item
%
 Bribe voter $v$ such that $\nicefrac{d_v}{n_v}$ is minimum.
\item Modify $C_P$ by subtracting $\nicefrac{d_v}{n}$ from each amount
  listed for voter~$v$.
\item Modify $c$ by subtracting one from $c(r)$ for those referenda $r
  \in R$ influenced by this bribery action.
\item Recurse.
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

%
%
\end{enumerate}

Observe that our greedy algorithm influences voters only via raising
their acceptance probabilities by only one level, so that the amount
$d_v$ possibly spent on voter $v$ in Step~3 of the algorithm actually
correponds to a set of referenda; we do not have to consider
multiplicities of issues (raised over several levels) here.

Let $S_1,\dots,S_\ell$ be the sequence of sets of referenda picked by
the greedy bribery algorithm, along with the sequence
$v_1,\dots,v_\ell$ of voters and the sequence $d_1,\dots, d_\ell$ of
bribery dollars spent this way.  Let
$R_1=R,\dots,R_\ell,R_{\ell+1}=\emptyset$ be the corresponding
sequence of sets of referenda, with the accordingly modified cover
numbers $c_i$.  Let $j(r,k)$ denote the index of the set in the
sequence influencing referendum $r$ the $k$th time with $k\leq c(r)$,
i.e., $r\in S_{j(r,k)}$ and $|\{i<j(r)\mid r\in S_i\}|=k-1$.  To cover
$r$ the $k$th time, we have to pay
$\chi(r,k)=\nicefrac{d_{j(r,k)}}{|S_{j(r,k)}|}$ dollars.  The greedy
algorithm will incur a cost of $\chi_{\textit{greedy}}=\sum_{r\in
  R}\sum_{k=1}^{c(r)} \chi(r,k)$ in total.

An alternative view on the greedy algorithm is from the perspective of
the referenda: By running the algorithm, we implicitly define a
sequence $r_1,\dots,r_N$ of referenda, where $N=c(R)=\sum_{r\in
R}c(r)$ is the cover number of the original instance, such that
$S_1=\{r_1,\dots,r_{|S_1|}\}$,
$S_2=\{r_{|S_1|+1},\dots,r_{|S_1|+|S_2|}\}$, etc.  Ties (how to list
elements within $S_i$) are broken arbitrarily.  This (implicitly)
defines two functions $L,R:\{1,\dots,\ell\}\to \{1,\dots,N\}$ such
that $S_i=\{r_{L(i)}\cdots r_{R(i)}\}$.  Slightly abusing notation, we
can associate a cost $\chi'(r_i)$ to each element in the sequence
(keeping in mind the multiplicities of covering implied by the
sequence), so that $\chi_{\textit{greedy}}=\sum_{i=1}^N\chi'(r_i)$.
Notice that $d_i=\sum_{L(i)\leq r\leq R(i)}\chi'(x_r)$.

%
%
%

%
Consider $r_j$ with $L(i)\leq j\leq R(i)$. The current referenda set
$R_{i}$ has cover number $N-L(i)+1$, i.e., of at least $N-j+1$.  Let
$\chi_{\textit{opt}}$ be the cost of an optimum bribery strategy
$\mathcal{C}^*$ of the original universe.  Of course, this also yields
a cover of the referenda set $R_{i}$ with cost at most
$\chi_{\textit{opt}}$. The average cost per element (taking into
account multiplicities as given by the cover numbers) is
$\nicefrac{\chi_{\textit{opt}}}{c(R_i)}$.  (So, whether or not some
new levels are obtained through bribery does not really matter here,
as long as the threshold is not
%
exceeded.)
%

%
$\mathcal{C}^*$ can be described by a sequence of sets of referenda
$C_1,\dots,C_q$ , with corresponding voters $z_1,\dots,z_q$ and
dollars $d_1^*,\dots, d_q^*$ spent.  Hence,
$\chi_{\textit{opt}}=\sum_{\kappa=1}^qd_\kappa^*$.
%
%
%
%
To each bribery step we associate the cost factor
$\nicefrac{d_\kappa^*}{|C_\kappa|}$, for each issue
%
$r$ contained in $C_\kappa$.
$\mathcal{C}^*$ could be also viewed as a bribery strategy for
%
$R_i$.  By pigeon hole, there is a referendum $r$ in $R_i$ (to be
influenced the $k$th time) with cost factor at most
$\nicefrac{d_\kappa^*}{|C_\kappa\cap R_i|}\leq
\nicefrac{\chi_{\textit{opt}}}{c(R_i)}$, where $\kappa$ is the index
such that $C_\kappa$ contains $r$ for the $k$th time in
$\mathcal{C}^*$ (usually, the cost would be smaller, since part of the
bribery has already been paid before).  Since $(S_i,v_i)$ was picked
to minimize $\nicefrac{d_i}{|S_i|}$, we find
$\nicefrac{d_i}{|S_i|}\leq \nicefrac{d_\kappa^*}{|C_\kappa\cap
R_i|}\leq \nicefrac{\chi_{\textit{opt}}}{c(R_i)}$.

We conclude that
\[
\chi'(r_j)\leq
\nicefrac{\chi_{\textit{opt}}}{c(R_i)}=
\nicefrac{\chi_{\textit{opt}}}{N-L(i)+1}\leq
\nicefrac{\chi_{\textit{opt}}}{N-j+1}.
\]

Hence,
$\chi_{\textit{greedy}}
  =  \sum_{j=1}^N\chi'(r_j)
 \leq \sum_{j=1}^N\nicefrac{\chi_{\textit{opt}}}{N-j+1}
  =  H(N) \chi_{\textit{opt}}
 \leq (\ln(N)+1)\chi_{\textit{opt}}$.
\end{proofs}
}

In the strict-majority scenario, cover numbers would have a different
meaning---we thus call them \emph{strict cover numbers}: For each
referendum, the corresponding strict cover number tells in advance how
many voters
%
have to change their opinions (bringing them individually over the
given threshold~$t$) to accept this referendum.  The strict
cover number of a problem instance is the sum of the strict cover
numbers of all given issues.

\Omit{
The corresponding
greedy algorithm would therefore choose to influence voter $v_i$ (with
$d_i$ dollars) in
%
the $i$th loop so that $v_i$ changes his or her opinion on some
referendum $r_j$ (possibly, there is a whole set $\rho_j$ of referenda
influenced this way), so that $\nicefrac{d_i}{|\rho_j|}$ is minimized.

We can now read the approximation estimate proof given for the
average-majority scenario nearly literally as before, by re-interpreting the
formulation ``influencing referendum $r$'' meaning now a complete
change of opinion for a certain voter (not just gaining one level
somehow).  This establishes the following result.
}

\begin{theorem}
\label{thm:plp-31-approximation}
$\MIN$-$\plp{3}{1}$
%
can be approximated within a factor of $\ln(N)+1$, where
$N$ is the strict cover number of the given instance.
\end{theorem}

Note that this result is in some sense stronger than
Theorem~\ref{thm:plp-32-approximation} (which refers to the
average-majority scenario), since the cover number of an instance
could be larger than the strict cover number.

This approximation result is complemented by a corresponding hardness
result.


\begin{corollary}
%
There is a constant $c>0$ such that %
$\MIN$-$\plp{3}{1}$ is not approximable within factor
$c\cdot \log(N)$ unless $\np\subset\dtime(N^{\log\log(N)})$, where
$N$ is the strict cover number of the given instance.
A fortiori, the same statement holds for $\MIN$-$\plpiw{3}{1}$.
\end{corollary}

Unfortunately, those greedy algorithms do not (immediately) transfer
to the case when issue weights are allowed. 
\Omit{These weights
might also influence the quality of approximation, but a simplistic
greedy algorithm might result in covering the ``wrong'' arguments.
Also, the proof of the approximation factor given above will not carry
over, since we need as one of the proof's basic ingredients that an
optimum solution can be interpreted as a partial one at some point.
%
%
Those problems tend to have a different
flavor.
%
%
}

%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

\Omit{The exact version of microbribery also admitted an $\FPT$-result, but
this cannot be interpreted as an approximation result, since the
entity that should be minimized has to be hit exactly(otherwise, we
have polynomial time).
}

\section{Conclusions}

We have studied six lobbying scenarios in a probabilistic
setting, both with and without issue weights.  Among the twelve
problems studied, we identified those that can be solved in polynomial
time, those that are $\np$-complete yet fixed-parameter tractable, and
those that are hard (namely, $\wtwo$-complete) in terms of their
parameterized complexity with suitable parameters.  It would be
interesting to study these problems in different
parameterizations.
%
%
%
%
%
%
Finally, we investigated the approximability of hard probabilistic
lobbying problems (without issue weights) and obtained both
approximation and inapproximability results.
A number of related results can be found in 
the full version~\cite{erd-fer-gol-mat-rai-rot:t:probabilistic-lobbying}.
An interesting open
question is whether one can find logarithmic-factor approximations
for voter bribery with issue weights.


%
%
%
%
%
%
%

{\small
%
%

\bibliographystyle{abbrv}
\bibliography{lobbying}
%
} %


\end{document}
