# An impossibility result for strongly group-strategyproof multi-winner
approval-based voting

Ioannis Caragiannis Aarhus University, email<EMAIL_ADDRESS>Rob LeGrand
Angelo State University, email<EMAIL_ADDRESS>Evangelos Markakis
Athens University of Economics and Business & Input Output Global, email:
<EMAIL_ADDRESS>Emmanouil Pountourakis Drexel University, email:
<EMAIL_ADDRESS>
###### Abstract

Multi-winner approval-based voting has received considerable attention
recently. A voting rule in this setting takes as input ballots in which each
agent approves a subset of the available alternatives and outputs a committee
of alternatives of given size $k$. We consider the scenario when a coalition
of agents can act strategically and alter their ballots so that the new
outcome is strictly better for a coalition member and at least as good for
anyone else in the coalition. Voting rules that are robust against this
strategic behaviour are called strongly group-strategyproof. We prove that,
for $k\in\\{1,2,…,m-2\\}$, strongly group-strategyproof multi-winner approval-
based voting rules which furthermore satisfy the minimum efficiency
requirement of unanimity do not exist, where $m$ is the number of available
alternatives. Our proof builds a connection to single-winner voting with
ranking-based ballots and exploits the infamous Gibbard-Satterthwaite theorem
to reach the desired impossibility result. Our result has implications for
paradigmatic problems from the area of approximate mechanism design without
money and indicates that strongly group-strategyproof mechanisms for minimax
approval voting, variants of facility location, and classification can only
have an unbounded approximation ratio.

##  1 Introduction

Approval voting offers a simple and easy-to-use format for running elections
on multiple issues with binary domains. This may involve either committee
elections among a set of candidates (which is the viewpoint adopted in this
work), or elections for a set of topics that need to be decided upon
simultaneously, often referred to as multiple referenda. Under such a voting
format, the voters are allowed to express approval preferences, i.e., each
voter can specify an approval set, with as many candidates as she likes, with
the interpretation that these are the candidates she is happy with, whereas
all other candidates are disapproved by her. In the last decades, many
scientific societies and organizations have adopted approval voting for their
council elections, including, among many others, the American Mathematical
Society and the Game Theory Society.

We are interested in the strategic behavior of voters in approval-based
elections. Namely, our work is centered around the design of mechanisms for
selecting a committee of a given (a priori fixed) size, which falls under the
broader umbrella of mechanism design without money. To begin with, the first
goal one would pursue is to obtain strategyproof mechanisms, where no voter
has an incentive to unilaterally misreport her approval preferences to her own
benefit. The famous Gibbard-Satterthwaite theorem Gibbard (1973);
Satterthwaite (1975) is not applicable in the approval voting domain, as it
requires a different space of preferences that express a strict ranking over
the set of candidates. Some known extensions of this theorem to weak rankings
—e.g., a result by Beja (1993)— are not applicable to approval voting either.
Thus, it is feasible to have strategyproof mechanisms (that are not
necessarily dictatorial), as already pointed out by Caragiannis et al. (2010).
As an example, for committees of size $k$, the minisum rule, which selects the
candidates with the $k$ highest approval scores, is strategyproof subject to
appropriate tie-breaking.

Going beyond strategyproofness, several works have also examined coalitional
manipulations, where a group of voters may benefit from a joint deviation.
This gives rise to two distinct notions of resilience, depending on how we
interpret what it means for a coalition to benefit from a joint deviation. In
particular, a standard class is that of weakly group-strategyproof (in short,
weakly GSP, or sometimes simply referred to as GSP) mechanisms, where no
deviation can make all members of a coalition strictly better off. A stronger
definition is that of strongly GSP mechanisms where no deviation makes one
member of the coalition better off without worsening the other members. Our
interest here is in the latter notion of strong group-strategyproofness. Even
though the definitions of weak and strong group-strategyproofness may not seem
to differ significantly at first sight, the current literature conveys a
different picture. There are positive results on the existence of weakly GSP
mechanisms with desirable properties (e.g., satisfying some form of economic
efficiency or approximating some social cost objective), both in voting
Caragiannis et al. (2010), but also in other fields of mechanism design
without money, such as in facility location problems Procaccia and Tennenholtz
(2013). On the contrary, many of these results do not generalize for strongly
GSP mechanisms, and in some cases it has remained an open problem whether
comparable results are possible with strongly GSP mechanisms. This is
precisely the focus of our work.

###  1.1 Our Results

We consider the problem of selecting a committee of a given fixed size, in
elections where voters submit approval ballots. Our main result is in Section
3, where we show that unanimous, strongly GSP mechanisms do not exist.
Unanimity is a very simple and minimal form of efficiency, requiring that if
all voters approve the same committee, this should also be the outcome of the
election. We view this as a severe impossibility result for strongly GSP
mechanisms. Our proof is based on a construction that exploits the Gibbard-
Satterthwaite theorem; even though we are interested in approval-based
elections, we essentially provide a reduction from appropriately defined
elections with ranking preferences, where the non-existence of strategyproof
mechanisms implies the impossibility of strongly GSP mechanisms in our
setting. We feel that our proof technique is of independent interest and could
have further applications. As a corollary, our result also yields an
incompatibility between Pareto-efficiency and strong group-strategyproofness
under the approval voting format. Finally, we stress that our results are not
based on any computational complexity assumption and, hence, hold for
exponential-time mechanisms as well.

We proceed in Section 4, by demonstrating some further implications of our
main result. Most importantly, we resolve one of the open questions posed by
Caragiannis et al. (2010), concerning the minimax approval voting rule,
proposed by Brams et al. (2007) as an alternative to the minisum rule. Namely,
we prove that there is no strongly GSP mechanism that achieves a finite
approximation for the minimax solution. Within the voting domain, we also
obtain an impossibility result for participatory budgeting under approval
ballots. Beyond voting, we also have implications for other related problems.
The first one is a special case of binary classification, where we seek a
classifier that labels a fixed number of points as positive and the remaining
ones as negative. Again, our main result translates to a lack of finite
approximations under strongly GSP mechanisms. Finally, the last implication is
for constrained facility location, where the facilities can be placed only in
particular locations.

###  1.2 Further Related Work

For a more complete exposition of approval voting elections and their
applications, we refer to the book of Lackner and Skowron (2023). Regarding
resistance to manipulation, there are several positive results for
strategyproof mechanisms that generalize to weakly GSP mechanisms. In fact,
this connection has been studied more thoroughly by Le Breton and Zaporozhets
(2009) and Barberà et al. (2010), where sufficient conditions have been
identified for domains in which strategyproof mechanisms coincide with weakly
GSP mechanisms. Regarding strongly GSP mechanisms in settings without monetary
payments, the literature is rather scarce. We are aware of characterization
results for the case of two alternatives by Manjunath (2012) and by Barberà et
al. (2011). In particular, for approval elections with two alternatives,
Manjunath identifies essentially two voting rules that are strongly GSP and
Pareto-efficient. On a slightly different direction, the work of Barberà et
al. (2011) establishes characterizations based on certain monotonicity
properties. Finally, in terms of impossibility results, Filos-Ratsikas et al.
(2017) show that there are no anonymous, strongly GSP mechanisms for a
facility location problem, where the goal is to place a facility on a line,
under double-peaked preferences. This is a quite different domain however, and
does not have any implications for our voting setting.

##  2 Definitions

We begin by introducing our notation. We let $N$ denote a set of $n$ voters
(or agents) and $A$ a set of $m$ candidates (or alternatives). We consider
elections where both the preferences and the ballots are approval-based, i.e.,
an agent’s ballot expresses his approval for each alternative in the subset
under consideration. Hence, a voting profile $P$ is a tuple
$P=(P_{1},\ldots,P_{n})$, where $P_{i}\subseteq A$ denotes the declared
preference of agent $i$. Under this notation, an approval election is
specified by a tuple $(N,A,P)$. Our focus is on multi-winner elections for
selecting a committee of some predetermined size. We let $k$ denote the
committee size. So, for any voting rule in our setting, the outcome must be
some set $S\subseteq A$, with $|S|=k$. To distinguish with the rules discussed
later in Section 2.2, we refer to them as multi-winner approval-based voting
rules.

We extend the notion of Hamming distance to subsets of $A$ as follows. We say
that the distance between two sets $Q$ and $T$ is the total number of
alternatives in which they differ, i.e.,

$d(Q,T)=|Q\setminus T|+|T\setminus Q|=|Q|+|T|-2|Q\cap T|.$

Note that this is precisely the Hamming distance of the sets when represented
as binary vectors, where the $i$th coordinate of each vector equals $1$ if the
$i$th alternative belongs to the set and equals $0$ otherwise.

###  2.1 Resistance to manipulation and other properties

We will assume that agents are strategic and may misreport their preferences
to the voting rule if this can be in their interest. We assume that each agent
prefers committees that include as many alternatives from their approval
preference as possible. Equivalently, agents evaluate a committee in terms of
its Hamming distance to their approval preference (with the smaller Hamming
distance, the better).

Hence, it is desirable for voting rules to be resistant to possible
manipulations by the agents. Given a profile $P$ and a voting rule $R$, we
denote by $R(P)$ the outcome of the voting rule on profile $P$. We also denote
by $P_{-i}$ the preferences of all agents besides $i$. Hence, we can also
write $P$ as $(P_{i},P_{-i})$. Our first property indicating resistance to
manipulation is strategyproofness, which requires that no agent $i$ has an
incentive to unilaterally change her preference so as to reduce the distance
of $P_{i}$ from the outcome of the voting rule.

######  Definition 1.

A voting rule $R$ is strategyproof (SP) if for any election $(N,A,P)$, any
agent $i\in N$, and any set of alternatives $P_{i}^{\prime}\subseteq A$, it
holds that

$d(P_{i},R(P_{i},P_{-i}))\leq d(P_{i},R(P_{i}^{\prime},P_{-i})).$

Moving on, we can also consider deviations by coalitions of agents and define
two analogous notions of resistance to manipulation. In particular, the first
such notion says that there is no deviation that can make all deviating agents
strictly better off. Given a profile $P$, in analogy to $P_{i}$ and $P_{-i}$,
we let $P_{S}$ and $P_{-S}$ denote the preferences of a set of agents $S$ and
of all agents except $S$, respectively.

######  Definition 2.

A voting rule $R$ is weakly group-strategyproof (weakly GSP) if for any
election $(N,A,P)$ and any coalition $S\subseteq N$ of agents, there is no
profile $P_{S}^{\prime}$ of the agents in $S$ such that

$d(P_{i},R(P_{S},P_{-S}))>d(P_{i},R(P_{S}^{\prime},P_{-S}))$

for every agent $i\in S$.

The notion that is the main focus of our work is a stronger requirement,
defined as follows.

######  Definition 3.

A voting rule $R$ is strongly group-strategyproof (strongly GSP) if for any
election $(N,A,P)$ and any coalition $S\subseteq N$ of agents, there is no
profile $P_{S}^{\prime}$ of the agents in $S$ such that

$d(P_{i},R(P_{S},P_{-S}))\geq d(P_{i},R(P_{S}^{\prime},P_{-S}))$

for every agent $i\in S$, with strict inequality for at least one agent of
$S$.

The rationale behind this last concept is that we demand the voting rule to be
resistant to coalitions in which some of the agents may change their
preference profile in order to help other members of the coalition (without
necessarily gaining something for themselves). Clearly, strong group-
strategyproofness is a stronger notion than weak group-strategyproofness.

Apart from resistance to manipulation, we will examine two properties related
to the efficiency of voting rules. The first is a very natural axiom for our
setting.

######  Definition 4.

We say that a voting rule $R$ for selecting a committee of size $k$ is
unanimous if whenever all agents approve the same set $S$ of $k$ alternatives
(and nothing else), $R$ outputs $S$ as the selected committee.

######  Definition 5.

A voting rule $R$ is Pareto-efficient if, for every input profile $P$, it
outputs a set $S$ of $k$ alternatives, such that there is no other committee
$S^{\prime}$ of size $k$, with at least one agent being closer to $S^{\prime}$
than $S$, and all other agents not being further off.

###  2.2 Voting by ranking ballots

Although our main focus is on approval voting, the proof of our main result is
based on a construction that involves elections where the ballot of each agent
is a strict ranking of the alternatives in decreasing order of preference.
Hence, a preference profile in ranking-based voting is given by a tuple
$(\succ_{1},\cdots,\succ_{n})$, where $\succ_{i}$ is the ranking of agent $i$
on the set of alternatives $A$. For brevity, we use $\succ$ to denote the
entire preference profile $(\succ_{1},\cdots,\succ_{n})$. Furthermore, for two
alternatives $p,q\in A$, we will use $p\succ_{i}q$ to denote that agent $i$
prefers $p$ to $q$ (and, hence, $p$ appears higher than $q$ in the ranking of
$i$).

Given a set of agents $N$, a set of alternatives $A$, and a preference profile
$\succ$, a ranking-based election is specified by a tuple $(N,A,\succ)$. We
will consider single-winner ranking-based voting rules, which return a single
alternative as an outcome when applied to a ranking profile. Hence, for a
voting rule $T$, we let $T(\succ)$ denote the winning alternative of $T$ when
given the preference profile $\succ$ as input.

In analogy to Definition 1, we can also define the notion of strategyproofness
in this setting as well. In the definition below, for a profile $\succ$, we
denote by $\succ_{-i}$ the preference profile of all agents except $i$.

######  Definition 6.

A ranking-based voting rule $T$ is strategyproof (SP) if for any ranking-based
election $(N,A,\succ)$, any agent $i\in N$, and any ranking
$\succ_{i}^{\prime}$ of the alternatives in $A$, it holds that

$T(\succ)\succ_{i}T(\succ_{i}^{\prime},\succ_{-i}).$

The classic impossibility result due to Gibbard and Satterthwaite, states that
any SP and onto single-winner ranking-based voting rule for elections with at
least three alternatives is a dictatorship. Here, a voting rule $T$ is onto
if, for every alternative $p\in A$, there exists a profile $\succ$ such that
$T(\succ)=p$. A voting rule $T$ is a dictatorship if there exists an agent $i$
such that for every profile $\succ$, the outcome $T(\succ)$ is the top choice
of agent $i$.

######  Theorem 1 (Gibbard 1973; Satterthwaite 1975).

Any single-winner ranking-based voting rule for ranking-based elections with
at least three alternatives, which is SP and onto, must be dictatorial.

##  3 Our Impossibility Result

Before we embark on our impossibility result, it is instructive to start with
a discussion on the existence of SP and weakly GSP voting rules. If we care
only about strategyproofness, the minisum voting rule (with appropriate
deterministic tie-breaking) is SP. When it comes to coalitional manipulations,
it would be expected that some form of dictatorial mechanisms would be weakly,
or even strongly GSP. One crucial issue here with defining a dictatorial rule
is that the outcome cannot always coincide exactly with the dictator’s
preferences, due to the constraint on the size of the committee being exactly
$k$. Therefore, a voting rule is dictatorial in our setting if it falls within
the following class of voting rules (referred to as $k$-completion by LeGrand
et al. (2007)).

> Dictatorial $k$-completion: Pick an agent $i$ as the dictator. If
> $|P_{i}|<k$, then output the union of $P_{i}$ together with $k-|P_{i}|$
> alternatives from $A\setminus P_{i}$ (selected according to some tie-
> breaking order); else if $|P_{i}|>k$, then output a subset of $P_{i}$ of
> size $k$ (again, according to some tie-breaking order); else return $P_{i}$.

The $k$-completion rules do indeed satisfy some form of resistance to
coalitional manipulation, but they are still not strongly GSP.

######  Theorem 2 (Caragiannis et al. 2010).

Any $k$-completion voting rule is weakly GSP but not strongly GSP.

The reason a $k$-completion rule is not always strongly GSP is that, dependent
on the tie-breaking rule used, the dictator could help some other agent by
changing his approval ballot and steer the rule to select a committee that
makes some agents better off, while the dictator is not worse off.

A natural question, posed already a while ago by Caragiannis et al. (2010), is
whether non-trivial strongly GSP voting rules exist. Our main result is the
following theorem, where we obtain a negative answer, as long as we demand the
additional and seemingly harmless property of unanimity.

######  Theorem 3.

Consider approval elections with $m$ alternatives, where the outcome must
always be a committee of size $k$, with $k\in[m-2]$. Then, there is no multi-
winner approval-based voting rule that is both strongly GSP and unanimous.

The remaining section is devoted to the proof of this result. We start with
the following lemma, which connects unanimity, strongly group-
strategyproofness, and Pareto-efficiency.

######  Lemma 4.

Any strongly GSP and unanimous multi-winner approval-based voting rule is
Pareto-efficient.

###### Proof.

Assume that the voting rule is not Pareto-efficient. Then, there exists an
approval election $(N,A,P)$, for which the voting rule returns a $k$-sized
committee of alternatives $K$, while there exists another $k$-sized committee
$K^{\prime}$ such that $d(K^{\prime},P_{i^{*}})<d(K,P_{i^{*}})$ for some agent
$i^{*}\in N$ and $d(K^{\prime},P_{i})\leq d(K,P_{i})$ for any other agent
$i\in N$. But then, all agents have an incentive to form a coalition and
misreport their preferences by simply reporting the set of alternatives
$K^{\prime}$. In that case, by the unanimity property, $K^{\prime}$ should be
selected as the outcome. The agent $i^{*}$ would then become strictly better
off, and the rest of the agents would not be worse off. This would contradict
the fact that our voting rule is strongly GSP. ∎

Using Lemma 4, we will prove Theorem 3 by showing that no Pareto-efficient
multi-winner approval-based voting rule is strongly GSP. We first provide a
high-level outline of our proof. We believe that the technique can be of
independent interest, potentially useful for establishing other impossibility
results as well. The backbone of the proof is a reduction that transforms a
ranking-based election (as defined in Section 2.2) into an approval election,
so that any Pareto-efficient multi-winner approval-based voting rule for the
latter is mapped naturally to a single-winner ranking-based voting rule for
the former. We show that if the multi-winner approval-based voting rule is
furthermore strongly GSP, then the single-winner ranking-based voting rule is
SP and onto. Then, the Gibbard-Satterthwaite theorem (Theorem 1) implies
certain “dictatorship-like” properties for the multi-winner voting rule,
eventually leading to a contradiction.

######  Definition 7.

[Construction of an approval election from a ranking-based election] Given a
parameter $k$ and a ranking-based election $I=(N,A,\succ)$ with $|N|=n$ and
$|A|=m$, we construct a corresponding approval election
$=(N^{\prime},A^{\prime},P(\succ))$, as follows:

  * •

For every agent $i\in N$, we introduce $m-1$ different copies of agents,
indexed as $(i,1),\dots,(i,m-1)$. Hence, the approval-based election has a
total of $(m-1)\cdot n$ agents.

  * •

The set of alternatives is $A^{\prime}=A\cup D$, where $D$ consists of $k-1$
dummy alternatives. Hence, the approval election has a total of
$|A^{\prime}|=m+k-1$ alternatives.

  * •

For $i\in[n]$ and $j\in[m-1]$, agent $(i,j)$ has the approval ballot
$P_{(i,j)}$ defined as

$P_{(i,j)}=\\{\text{top $j$ ranked alternatives in $\succ_{i}$}\\}\cup D$

Hence, the approval profile is given by
$P(\succ)=\\{P_{(i,j)}\\}_{i\in[n],j\in[m-1]}$.

######  Example 1.

Before we proceed, we demonstrate the construction with a simple example, when
$n$ and $m$ are small. Consider the ranking-based election $(N,A,\succ)$ with
$N=\\{1,2\\}$, $A=\\{x,y,z\\}$, and with $\succ$ defined as
$x\succ_{1}y\succ_{1}z$ and $y\succ_{2}z\succ_{2}x$. The reduction of
Definition 7 for $k=2$ gives an approval election with four agents
$N^{\prime}=\\{(1,1),(1,2),(2,1),(2,2)\\}$, and four candidates
$A^{\prime}=\\{x,y,z,d_{1}\\}$. Here, we have only one dummy candidate. The
approval ballots are: $P_{(1,1)}=\\{x,d_{1}\\}$, $P_{(1,2)}=\\{x,y,d_{1}\\}$,
$P_{(2,1)}=\\{y,d_{1}\\}$, and $P_{(2,2)}=\\{y,z,d_{1}\\}$.

Now, let $(N,A,\succ)$ be a ranking-based election and let
$(N^{\prime},A^{\prime},P(\succ))$ be the corresponding approval election
defined by our reduction in Definition 7. Also, let $R$ be a Pareto-efficient
multi-winner approval-based voting rule which outputs the committee
$R(P(\succ))$ of size $k$ when applied on the profile $P(\succ)$. We will show
that $R(P(\succ))\setminus D$ is a singleton and will use it to define a
corresponding single-winner ranking-based voting rule for the ranking-based
election.

######  Lemma 5.

If the multi-winner approval-based voting rule $R$ is Pareto-efficient, then
$R(P(\succ))\setminus D$ is a singleton.

###### Proof.

For the sake of contradiction, assume that $|R(P(\succ))\setminus D|\geq 2$.
Note that for every agent $i\in N$, agent $(i,1)$ of $N^{\prime}$ approves
exactly one alternative outside $D$. Hence, there is at least one alternative
in the outcome $R(P(\succ))$, say $a^{*}$, that this agent does not approve.
Moreover, each alternative in $D\setminus R(P(\succ))$ is approved by all
agents. Now, consider replacing $a^{*}$ in the outcome of $R$ by some
alternative in $D\setminus R(P(\succ))$. Agent $(i,1)$ is strictly better off
now, and all other agents are not worse off. Hence, $R$ is not Pareto-
efficient, a contradiction. ∎

We now define the single-winner ranking-based voting rule $T$, which returns
the alternative contained in $R(P(\succ))\setminus D$ on input the profile of
rankings $\succ$. We will show that if the multi-winner approval-based voting
rule $R$ is both Pareto-efficient and strongly GSP, the rule $T$ satisfies the
premises of the Gibbard-Satterthwaite theorem (Theorem 1).

######  Lemma 6.

If $R$ is a strongly GSP and Pareto-efficient multi-winner approval-based
voting rule, the induced single-winner ranking-based voting rule $T$ is onto
and SP.

###### Proof.

We first prove that $T$ is onto, i.e., for every alternative $a\in A$, there
exists $\succ$ such that $T(\succ)=a$. We construct $\succ$ such that $a$ is
the top alternative in every agent’s ranking. Note that, in the corresponding
approval voting profile $P(\succ)$ defined by our reduction in Definition 7,
the only Pareto-efficient committee of size $k$ is $D\cup\\{a\\}$. Hence, this
must be the outcome of $R$, and this means that $T$ is equal to the single
alternative in $R(\succ)\setminus D$, i.e., alternative $a$.

Second, we show that $T$ is SP. Assume towards a contradiction that $T$ is not
SP, i.e., there exists a preference profile $\succ$, some agent $i$, and some
ranking of alternatives $\succ^{\prime}_{i}$ such that

$T(\succ^{\prime}_{i},\succ_{-i})\succ_{i}T(\succ_{i},\succ_{-i}).$ (1)

By our reduction, the approval ballots of the profiles
$P(\succ_{i},\succ_{-i})$ and $P(\succ^{\prime}_{i},\succ_{-i})$ differ only
in the agents $(i,1),\dots,(i,m-1)$. Hence, the main idea is to show that the
unilateral deviation to $\succ^{\prime}_{i}$ by agent $i$ in the ranking-based
election corresponds to successful deviations by the coalition of agents
$(i,1),\dots,(i,m-1)$ in the approval-based election, from profile $P(\succ)$
to profile $P(\succ^{\prime}_{i},\succ_{-i})$.

Let $a=T(\succ_{i},\succ_{-i})$ and $b=T(\succ^{\prime}_{i},\succ_{-i})$.
Suppose that according to $\succ_{i}$, alternative $a$ is in position $r$ and
$b$ is in position $r^{\prime}$. Observe that Equation (1) implies
$r^{\prime}<r$. Since we assumed that, under rule $T$, $b$ is the winner in
profile $(\succ^{\prime}_{i},\succ_{-i})$ and $a$ is the winner in profile
$\succ$, this means that the outcome of rule $R$ in the approval voting
election is $D\cup\\{a\\}$ for profile $P(\succ)$ and $D\cup\\{b\\}$ for
profile $P(\succ^{\prime}_{i},\succ_{-i})$. Note that the agents $(i,j)$ with
$r^{\prime}\leq j<r$ approve alternative $b$ but do not approve alternative
$a$. Hence, their distance from the outcome of $R$ decreases in profile
$P(\succ^{\prime}_{i},\succ_{-i})$ compared to profile $P(\succ)$. The
remaining agents in the coalition are indifferent, since either they approve
both $a$ and $b$ (this holds for agents $(i,j)$ with $j\geq r$, if any), or
they approve neither of them (this holds for agents $(i,j)$ with
$j<r^{\prime}$, if any). Hence, we have constructed a deviation, where at
least one member of the coalition is better off, and some are indifferent.
This contradicts the assumption that the multi-winner approval-based voting
rule $R$ is strongly GSP. Therefore, the single-winner ranking-based voting
rule $T$ is SP. ∎

Notice that, according to our reduction in Definition 7, if the number of
alternatives in the approval election is at least $k+2$, then the number of
alternatives in the ranking-based election is at least $3$. Thus, by Lemmas 5,
6, and Theorem 1, we get the following corollary.

######  Corollary 7.

Let $R$ be a Pareto-efficient and strongly GSP multi-winner approval-based
voting rule for approval elections with $m\geq 3$ alternatives and
$k\in[m-2]$. Then, the induced single-winner ranking-based voting rule $T$ is
a dictatorship, i.e., there exists an agent $i^{*}$ such that for every
profile $\succ$, $T(\succ)$ is the top preference of agent $i^{*}$.

The fact that $T$ is a dictatorship implies that $R$ also has some
dictatorship-like attributes. We show that this contradicts the fact that $R$
is strongly GSP, which implies that the intersection of strongly GSP and
Pareto-efficient multi-winner approval-based voting rules is empty, completing
the proof of Theorem 3.

Consider a unanimous (and, by Lemma 4, Pareto-efficient) and strongly GSP
multi-winner approval-based voting rule $R$ which outputs committees of size
$k\in[m^{\prime}-2]$ for elections with $m^{\prime}\geq 3$ alternatives.
Consider the reduction of Definition 7, with parameters $k$, $n=3$, and
$m=m^{\prime}-k+1$, with $m\geq 3$, and let $T$ be the single-winner ranking-
based voting rule induced by $R$. By Corollary 7, $T$ is a dictatorship, and
without loss of generality, let us assume that the dictator is agent $1$.

Now, let $x$ and $y$ be two specific alternatives of $A$ and consider the
rankings $\succ^{x}$ and $\succ^{y}$ of the alternatives of $A$, which differ
only in the two top positions, defined as follows. Ranking $\succ^{x}$ has
alternative $x$ first, alternative $y$ second, and then the alternatives of
$A\setminus\\{x,y\\}$ in some arbitrary order. Ranking $\succ^{y}$ has
alternative $y$ first, alternative $x$ second, and then the alternatives of of
$A\setminus\\{x,y\\}$ in the same order with $\succ^{x}$. Based on these, we
will construct three distinct approval profiles and argue about their outcome
under $R$, that will eventually lead to a contradiction.

Consider first the ranking profiles $(\succ^{x},\succ^{x},\succ^{y})$ and
$(\succ^{y},\succ^{x},\succ^{y})$. The corresponding approval profiles
$P_{x}=P(\succ^{x},\succ^{x},\succ^{y})$ and
$P_{y}=P(\succ^{y},\succ^{x},\succ^{y})$ differ only in the ballot of agent
$(1,1)$, which is $\\{x\\}\cup D$ in $P_{x}$ and $\\{y\\}\cup D$ in $P_{y}$.
Among the remaining agents in profiles $P_{x}$ and $P_{y}$, the ones that are
of interest for the arguments below are agent $(2,1)$ with approval ballot
$\\{x\\}\cup D$ and agent $(3,1)$ with approval ballot $\\{y\\}\cup D$. By the
definition of our reduction, the fact that $T$ is a dictatorship of agent $1$,
and the relation between the voting rules $R$ and $T$, we have that
$R(P_{x})=\\{x\\}\cup D$ and $R(P_{y})=\\{y\\}\cup D$.

Now, consider a third approval profile $P_{xy}$, differing from $P_{x}$ and
$P_{y}$ only in the ballot of agent $(1,1)$ which is now $\\{x,y\\}\cup D$.
For convenience, the three profiles are depicted in Table 1, when $m=3$. We
remark that this profile is not produced by our reduction. Still, the Pareto-
efficiency of voting rule $R$, implies that $D\subset R(P_{xy})$, since the
alternatives in $D$ appear in the approval ballot of all agents in $P_{xy}$.
We distinguish between two cases regarding the single alternative in
$R(P_{xy})\setminus D$.

First, if $R(P_{xy})\setminus D\not=\\{x\\}$, then the agents $(1,1)$ and
$(2,1)$, with ballots $\\{x,y\\}\cup D$ and $\\{x\\}\cup D$ under $P_{xy}$,
have Hamming distance at least $1$ and exactly $2$ respectively, from the
$k$-sized committee $R(P_{xy})$. The deviation of these two agents to approval
ballots $\\{x\\}\cup D$ for both yields the approval profile $P_{x}$, for
which rule $R$ outputs the committee $\\{x\\}\cup D$. Its Hamming distance
from the approval ballots of agents $(1,1)$ and $(2,1)$ in profile $P_{xy}$ is
only $1$ and $0$, respectively, implying the existence of a successful
deviating coalition that contradicts the assumption that voting rule $R$ is
strongly GSP.

It remains to consider the case $R(P_{xy})=\\{x\\}\cup D$. Then, the agents
$(1,1)$ and $(3,1)$, with ballots $\\{x,y\\}\cup D$ and $\\{y\\}\cup D$ under
$P_{xy}$, have Hamming distance $1$ and $2$ from the committee $R(P_{xy})$
respectively. Their deviation to ballot $\\{y\\}\cup D$ for both yields the
approval profile $P_{y}$, for which the rule $R$ outputs the $k$-sized
committee $\\{y\\}\cup D$. Hence, this will yield a Hamming distance of $1$
and $0$ from the approval ballots of agents $(1,1)$ and $(3,1)$ in the
approval profile $P_{xy}$. This again implies the existence of a successful
deviating coalition, contradicting the assumption that $R$ is strongly GSP.

We conclude that $R$ cannot be Pareto-efficient (and, hence, unanimous) and
strongly GSP, completing the proof of Theorem 3.

Table 1: An example of the profiles used in the final step of the proof of Theorem 3, when the ranking-based election we start from has $m=3$ alternatives. The profiles differ only in the approval ballot of agent $(1,1)$ and any Pareto-efficient outcome of the rule $R$ (i.e., either $\\{x\\}\cup D$ or $\\{y\\}\cup D$) on profile $P_{xy}$ violates strong group-strategyproofness.  agent | $P_{x}$ | $P_{y}$ | $P_{xy}$
---|---|---|---
$(1,1)$ | $\\{x\\}\cup D$ | $\\{y\\}\cup D$ | $\\{x,y\\}\cup D$
$(1,2)$ | $\\{x,y\\}\cup D$ | $\\{x,y\\}\cup D$ | $\\{x,y\\}\cup D$
$(2,1)$ | $\\{x\\}\cup D$ | $\\{x\\}\cup D$ | $\\{x\\}\cup D$
$(2,2)$ | $\\{x,y\\}\cup D$ | $\\{x,y\\}\cup D$ | $\\{x,y\\}\cup D$
$(3,1)$ | $\\{y\\}\cup D$ | $\\{y\\}\cup D$ | $\\{y\\}\cup D$
$(3,2)$ | $\\{x,y\\}\cup D$ | $\\{x,y\\}\cup D$ | $\\{x,y\\}\cup D$
outcome | $\\{x\\}\cup D$ | $\\{y\\}\cup D$ | ?

##  4 Implications

We now discuss some implications of our impossibility result in other
settings. We begin by answering a question by Caragiannis et al. (2010) about
the “approximability” of the minimax approval voting rule. Then, we discuss
three problems, which are just generalizations of multi-winner approval-based
voting (even though some may seem different at first glance).

###  4.1 Approximating minimax approval voting

Minimax approval voting has been proposed by Brams et al. (2007), who argued
about its use in comparison to the minisum rule that is mostly adopted in
practice. In particular, the $k$-minimax approval voting rule takes as input a
profile of approval ballots and returns a $k$-sized committee of alternatives
that minimizes the maximum Hamming distance from the ballots. Unfortunately,
as proved by LeGrand et al. (2007), the rule has two important drawbacks. The
first is that computing the winning committee is an NP-hard problem, and the
second is that the rule is not SP.

As a relaxation, LeGrand et al. (2007), Caragiannis et al. (2010), and Byrka
and Sornat (2014) studied approximate mechanisms for $k$-minimax approval
voting. Given an approval election $(N,A,P)$ and a $k$-sized committee $C$,
let $D(C,P)=\max_{i\in N}{d(C,P_{i})}$ denote the maximum Hamming distance of
$C$ from the approval ballots of $P$. Also, let
$C^{*}\in\operatorname*{arg\,min}_{K}{D(K,P)}$ be a $k$-sized committee that
would be returned by the $k$-minimax approval voting rule on input the
election $(N,A,P)$. A voting rule $R$ approximates the $k$-minimax solution
within a factor of $\rho\geq 1$, if $D(R(P),P)\leq\rho\cdot D(C^{*},P)$ for
every profile $P$. The quantity $\rho$ is called the approximation ratio of
mechanism $R$.

The papers by LeGrand et al. (2007) and Caragiannis et al. (2010) present SP
and weakly GSP voting rules, which approximate $k$-minimax approval voting
within a factor of $3-\frac{2}{k+1}$. Among them, the minisum rule with
appropriate tie-breaking is SP, whereas the class of $k$-completion voting
rules, presented in Section 3, is weakly GSP. The question of whether such an
approximation factor can be achieved by a strongly GSP mechanism was left
open.

To resolve this open question using our impossibility result, we make first
the following claim.

######  Claim 1.

A non-unanimous voting rule has an infinite approximation ratio for
$k$-minimax approval voting.

###### Proof.

Consider such a non-unanimous rule. Non-unanimity implies that there is a
profile $P$ in which all agents approve the same $k$-sized committee of
alternatives, say $C^{*}$, but the rule returns some different committee, say
$C$. Clearly, $D(C^{*},P)=0$, i.e., the minimax solution has a Hamming
distance of $0$ to all voters, whereas $D(C,P)>0$ in this case. This means
that the rule has an infinite approximation ratio. ∎

The following statement now follows due to Theorem 3.

######  Theorem 8.

Any strongly GSP approval-based multi-winner voting rule in elections with
$m\geq 3$ alternatives, $k\in[m-2]$, and $n\geq 6$ agents has an infinite
approximation ratio for $k$-minimax approval voting.

###  4.2 Participatory budgeting with an approval voting format

An important application of approval-based voting is in participatory
budgeting Aziz and Shah (2021); Rey and Maly (2023). In the most typical
scenario, a municipality has a fixed budget and considers implementing several
projects. Each project has a known cost, but the total cost of all projects
exceeds the available budget. Thus, only a subset of projects can be selected
for implementation. Participatory budgeting is used to delegate the selection
of projects to the citizens. Each participating citizen casts a ballot with
their preferences, and the municipality has to select, using a predefined
mechanism, a subset of projects that are within the budget and reflect the
citizens’ preferences. Among other formats that have been used for eliciting
the citizens’ preferences, approval ballots seem to be very popular, not only
within municipalities, but also in programs offered by blockchain communities
or decentralized autonomous organizations (DAOs); e.g., see the recent related
survey by Talmon (2023).

Let us focus now on the case of projects with equal costs, so that for some
integer $k$, all subsets of $k$ projects are the maximal sets of projects that
are within the budget111In fact, for our purposes, the project costs do not
need to be the same, as long as any set of $k$ projects is budget feasible,
and any superset is infeasible.. This setting can be easily seen to be
equivalent to multi-winner approval voting. In particular, we say that a
mechanism is maximal if it always returns a maximally feasible set of projects
for funding (the addition of any other project violates the budget
constraint). For the case we are considering, a maximal mechanism would have
to select a set of exactly $k$ projects (which can be viewed as a committee of
size $k$ in the approval voting election). Assuming that each citizen aims to
have as many of her favourite projects selected, our impossibility result
implies that unanimity and strong group-strategyproofness are not compatible
for participatory budgeting mechanisms that are maximal.

######  Theorem 9.

Unanimous and strongly GSP maximal mechanisms for participatory budgeting with
an approval ballot format do not exist.

We remark that Theorem 9 applies to mechanisms which allow citizens to cast
ballots with arbitrarily many projects, even if their total cost exceeds the
available budget. This is not an unusual practice today.222The website
https://en.wikipedia.org/wiki/List_of_participatory_budgeting_votes has
information about the format of participatory budgeting votes held in the last
ten years. Whether Theorem 9 carries over for inputs, where each agent’s
ballot respects the budget restriction is an interesting open problem.

###  4.3 Classification with shared inputs

An important problem in supervised learning is, given a set of training
examples that maps points from an input space to labels, to select a
classifier from a concept class that is as close to the data in the training
example as possible. Meir et al. (2012) study strategic issues in binary
classification by considering the following multi-agent setting with an input
space $\mathcal{X}$, a concept class $\mathcal{H}$ and $n$ agents. The concept
class contains classifiers; each classifier $h\in\mathcal{H}$ is a function
mapping each point of $\mathcal{X}$ to a label from $\\{+,-\\}$. The training
set consists of a set of points $X\subseteq\mathcal{X}$ and data provided by
$n$ agents, where agent $i$ provides a labeling $Y_{i}:X\rightarrow\\{+,-\\}$
of the points in $X$.

A classifier is evaluated by each agent $i\in[n]$ using the agent’s loss
function $\ell_{i}$, which returns the number of data points for which the
labeling of the classifier and the labeling provided by agent $i$ differ.
i.e., for the classifier $h\in\mathcal{H}$ and agent $i$,

$\displaystyle\ell_{i}(h,Y_{i})$ $\displaystyle=\sum_{x\in
X}{\mathbb{I}\\{h(x)\not=Y_{i}(x)\\}}.$

Furthermore, each agent $i\in[n]$ has a positive weight $w_{i}$, so that
$\sum_{i\in[n]}{w_{i}}=1$, indicating the importance of the agent for the
classification task. A classification mechanism takes as input the dataset
$Y=(Y_{1},Y_{2},...,Y_{n})$, which consists of the labelings provided by the
agents, along with their weight vector $\mathbf{w}=(w_{1},w_{2},...,w_{n})$,
and returns a classifier from the concept class $\mathcal{H}$. The outcome of
the classification mechanism, say $h\in\mathcal{H}$, is evaluated using the
global risk $L(h,Y,\mathbf{w})$, defined as

$\displaystyle L(h,Y,\mathbf{w})$
$\displaystyle=\sum_{i\in[n]}{w_{i}\cdot\ell_{i}(h,Y_{i})}.$

The well-known empirical risk minimization (ERM) algorithm selects a
classifier minimizing the global risk, i.e.,

$\displaystyle\text{erm}(Y,\mathbf{w})$
$\displaystyle\in\operatorname*{arg\,min}_{h\in\mathcal{H}}{L(h,Y,\mathbf{w})}.$

Meir et al. (2012) assume that agents are strategic and may decide to
misreport their private data to the classification mechanism if the outcome of
the mechanism incurs a smaller loss to them. Adapting the notions of
strategyproofness and strong group-strategyproofness to this setting, we say
that a classification mechanism $M$ taking as input the weight vector
$\mathbf{w}$ and the private labelings of the agents, $Y=(Y_{1},...,Y_{n})$,
for the set of points $X\subseteq\mathcal{X}$, is SP if there is no agent
$i\in[n]$ and labeling $Y^{\prime}_{i}:X\rightarrow\\{+,-\\}$ so that
$\ell_{i}(M(Y,\mathbf{w}),Y_{i})>\ell_{i}(M((Y_{-i},Y^{\prime}_{i}),\mathbf{w}),Y_{i})$.
The mechanism is strongly GSP if there is no subset of agents $S\subseteq[n]$,
agent $i^{*}\in S$, and labelings $Y^{\prime}_{i}:X\rightarrow\\{+,-\\}$ for
$i\in S$, so that
$\ell_{i}(M(Y,\mathbf{w}),Y_{i})\geq\ell_{i}(M((Y_{-S},Y^{\prime}_{S}),\mathbf{w}),Y_{i})$
for each $i\in S$ and
$\ell_{i^{*}}(M(Y,\mathbf{w}),Y_{i^{*}})>\ell_{i^{*}}(M((Y_{-S},Y^{\prime}_{S}),\mathbf{w}),Y_{i^{*}})$.
A universally SP (resp., strongly GSP) randomized mechanism is a probability
distribution over deterministic SP (resp., deterministic strongly GSP)
mechanisms.

Meir et al. (2012) observe that ERM is not SP and aim to design SP mechanisms
which approximate the global risk of ERM. A (possibly randomized)
$\rho$-approximate mechanism $M$ in this context satisfies
$\operatorname*{\mathbb{E}}[L(M(Y,\mathbf{w}),Y,\mathbf{w})]\leq\rho\cdot
L(\text{erm}(Y,\mathbf{w}),Y,\mathbf{w})$ for every dataset $Y$. They present
an $O(n)$-approximate SP mechanism, which is also proved to be almost best
possible among all deterministic SP mechanisms. A randomized version of this
mechanism, which first selects an agent proportionally to the agents’ weights
and then selects the classifier of minimum loss to the selected agent, is
universally SP and has an approximation ratio of $3-\frac{2}{n}$. This bound
was proved to be best possible for randomized SP mechanisms by Meir et al.
(2011).

By exploiting the relation of binary classification with shared inputs to
approval voting and our impossibility result, we can show a negative result as
well. Consider a set of $m$ points $X\subseteq\mathcal{X}$ and the concept
class $\mathcal{H}$ consisting of the classifiers that label $k$ points of $X$
with $+$ and the remaining with $-$, where $k\in[m-2]$. Such classifiers can
make sense in scenarios where there is a fixed number of points that can
receive one of the two labels, due to capacity constraints. For example,
classifiers for school admission or bank loan applications fit under this
framework (where only a predetermined number of the applicants will be
admitted). Another natural example can be seen with taking $k=n/2$, where the
goal is to separate the points into an upper and lower half. We can then think
of each point as an alternative, classifiers as $k$-sized committees
(containing the alternatives that the classifier labels with $+$), and input
data provided by the agents as approval ballots, where the approval set
corresponds to the alternatives labeled as $+$ by the agent. Notice that under
this definition, the loss $\ell_{i}(h,Y_{i})$ of agent $i$ for classifier $h$
is the Hamming distance between the $k$-sized committee corresponding to the
classifier $h$ and the approval ballot corresponding to agent $i$. Thus,
classification for this particular concept class with agents aiming at
minimizing their loss is equivalent to multi-winner approval voting with
agents aiming at minimizing their Hamming distance to the winning committee.

We will use now an argument similar to Claim 1 in Section 4.1, so as to obtain
a negative result that extends also for randomized mechanisms. Consider a
universally strongly GSP randomized mechanism $M$ which has a strongly GSP
deterministic mechanism $M_{R}$ (corresponding to the multi-winner voting rule
$R$) in its support, i.e., it calls mechanism $M_{R}$ with positive
probability. Then, Theorem 3 implies that $R$ is not unanimous, and hence,
there is an approval ballot profile in which all agents agree on $k$
alternatives, but the rule $R$ returns another $k$-sized committee.
Equivalently, this means that there exists a dataset $Y=(Y_{1},...,Y_{1})$
consisting of $n$ copies of the same labeling $Y_{1}$ by all agents, so that
when the classification mechanism $M_{R}$ takes as input $Y$, it returns a
classifier $h$, producing a labeling that is different from $Y_{1}$, i.e.,
$\ell_{i}(M_{R}(h,Y,\mathbf{w}),Y_{i})>0$ and
$L(M_{R}(Y,\mathbf{w}),Y,\mathbf{w})=\sum_{i\in[n]}{w_{i}\cdot\ell_{i}(M_{R}(Y,\mathbf{w}),Y_{1})}>0$
and hence, $\operatorname*{\mathbb{E}}[L(M(Y,\mathbf{w}),Y,\mathbf{w})]>0$. In
contrast, the concept class $\mathcal{H}$ contains the classifier $h^{*}$
which agrees with the labeling $Y_{1}$ on the points of $X$ and thus,
$L(\text{erm}(Y,\mathbf{w}),Y,\mathbf{w})=0$. Therefore, we obtain that
mechanism $M$ has infinite approximation ratio.

######  Theorem 10.

Any universally strongly GSP randomized mechanism for binary classification
with shared inputs has an infinite approximation ratio.

We remark that we have silently assumed that the classification mechanism may
take as input datasets that are not necessarily realizable. This means that
the labeling of the points in $X$ provided by some agent may not coincide with
the labeling of any classifier from the concept class. This is crucial for
proving Theorem 10. If the labeling provided by each agent is realizable by a
classifier in the concept class, then the two mechanisms presented by Meir et
al. (2012) are strongly GSP and universally strongly GSP, respectively. A
realizable dataset corresponds to an approval voting setting in which the
outcome can be any committee of alternatives. Clearly, any dictatorship is
strongly GSP in this setting. For realizable datasets, the mechanisms of Meir
et al. (2012) correspond to such dictatorships.

###  4.4 Constrained facility location in networks

Facility location has played a key role in the field of approximate mechanism
design with money Procaccia and Tennenholtz (2013). The simplest version of
the problem aims to locate a single facility on the line when strategic agents
report their private location and have single-peaked preferences. These
results usually exploit a famous result by Moulin (1980), which characterizes
the class of SP mechanisms. The results on the line have been extended to
multiple dimensions Barberà et al. (1993), multiple facilities Lu et al.
(2010), facility location in networks Schummer and Vohra (2002); Alon et al.
(2010), and have addressed constrained versions of the problem; e.g., see
Kyropoulou et al. (2019), Sui and Boutilier (2015), and Walsh (2021).

We focus on the constrained version as well, regarding the allowed locations
for placing a facility, and explain how our main result implies an
impossibility in discrete metric spaces. In particular, the problem we
consider is how to locate a facility at a node of a graph, taking into account
reports by agents for their private locations in the graph. Our objective is
to locate a facility at a node selected from a predefined subset of allowable
nodes so that the maximum or the total shortest-path distance of the facility
from all agents is minimized. A strongly GSP mechanism here means that if
misreporting by any coalition of agents results in an agent from the coalition
coming closer to the facility, some other agent in the coalition will be
strictly further off. We evaluate the outcome of such a mechanism in terms of
the maximum or the total shortest-path distance compared against the optimal
solution. We have the following negative result.

######  Theorem 11.

Strongly GSP mechanisms for constrained facility location in graphs has
infinite approximation ratio with respect to both the maximum and the total
cost objectives.

###### Proof.

Again, we resort to an argument analogous to Claim 1. Consider instances,
where the graph is the $m$-dimensional hypercube and all nodes with $k$ 1s
($k\in[m-2]$) in their binary representation is the allowable set of nodes for
placing the facility. Then, the $m$ dimensions correspond to alternatives,
each node in the allowable set corresponds to a $k$-sized committee, and each
agent’s location in the graph corresponds to an approval ballot. Clearly, the
shortest-path distance between two nodes in the hypercube is equal to the
Hamming distance of the corresponding approval ballots to committees. Theorem
3 then implies that every strongly GSP mechanism for locating the facility is
non-unanimous. Hence, there exists an instance in which all agents have the
same preference, i.e., they are all located in the same node of the allowable
set, but the mechanism returns another node of the allowable set as an
outcome. Hence, the optimal solution has zero cost, both for the maximum and
for the total cost objective, while the mechanism returns a solution with
positive cost. ∎

Clearly, it is again the restriction of the allowable set of nodes that leads
to the impossibility. When the allowable set contains all graph nodes,
dictatorships are strongly GSP and have a finite approximation ratio.

##  5 Discussion

Let us conclude by mentioning very briefly the few cases that escape from our
impossibility. First, notice that our construction has at least six agents. On
the other hand, we can easily see that the serial dictatorship mechanism
—which returns a $k$-sized committee that has minimum distance from agent $2$
among the $k$-sized committees of minimum distance from agent $1$— is strongly
GSP for approval elections with two agents. The case of three, four, and five
agents is left open. Furthermore, our construction creates profiles with
$m\geq 3$ alternatives and uses committee size $k\in[m-2]$. Also, recall that,
for two alternatives, Manjunath (2012) provides a positive result with his
consensus voting rules. So, the case $m\geq 3$ and $k=m-1$ is left
mysteriously open. Exploring whether our impossibility carries over even for
the simplest among these cases with three alternatives and committees of size
$2$ would require a different construction. Of course, the possibility of a
positive result here should not be excluded.

## References

  * (1)
  * Alon et al. (2010) Noga Alon, Michal Feldman, Ariel D. Procaccia, and Moshe Tennenholtz. 2010.  Strategyproof approximation of the minimax on networks.  _Mathematics of Operations Research_ 35, 3 (2010), 513–526.
  * Aziz and Shah (2021) Haris Aziz and Nisarg Shah. 2021.  Participatory budgeting: Models and approaches.  In _Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations_ , Tamás Rudas and Gábor Péli (Eds.). Springer International Publishing, 215–236.
  * Barberà et al. (2010) Salvador Barberà, Dolors Berga, and Bernardo Moreno. 2010\.  Individual versus group strategy-proofness: When do they coincide?  _Journal of Economic Theory_ 145, 5 (2010), 1648–1674.
  * Barberà et al. (2011) Salvador Barberà, Dolors Berga, and Bernardo Moreno. 2011\.  Group strategy-proof social choice functions with binary ranges and arbitrary domains: Characterization results.  _International Journal of Game Theory_ 41 (2011), 791–808.
  * Barberà et al. (1993) Salvador Barberà, Faruk Gul, and Ennio Stacchetti. 1993\.  Generalized median voter schemes and committees.  _Journal of Economic Theory_ 61, 2 (1993), 262–289.
  * Beja (1993) Avraham Beja. 1993\.  Arrow and Gibbard-Satterthwaite revisited: Extended domains and shorter proofs.  _Mathematical Social Sciences_ 25, 3 (1993), 281–286.
  * Brams et al. (2007) Steven J. Brams, D. Marc Kilgour, and M. Remzi Sanver. 2007\.  A minimax procedure for electing committees.  _Public Choice_ 132, 3/4 (2007), 401–420.
  * Byrka and Sornat (2014) Jaroslaw Byrka and Krzysztof Sornat. 2014.  PTAS for minimax approval voting. In _Proceedings of the 10th International Conference on Web and Internet Economics (WINE)_. 203–217.
  * Caragiannis et al. (2010) Ioannis Caragiannis, Dimitris Kalaitzis, and Evangelos Markakis. 2010.  Approximation algorithms and mechanism design for minimax approval voting. In _Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI)_. 737–742.
  * Filos-Ratsikas et al. (2017) Aris Filos-Ratsikas, Minming Li, Jie Zhang, and Qiang Zhang. 2017.  Facility location with double-peaked preferences.  _Autonomous Agents & Multi Agent Systems_ 31, 6 (2017), 1209–1235.
  * Gibbard (1973) Allan Gibbard. 1973\.  Manipulation of voting schemes.  _Econometrica_ 41, 4 (1973), 587–602.
  * Kyropoulou et al. (2019) Maria Kyropoulou, Carmine Ventre, and Xiaomeng Zhang. 2019\.  Mechanism design for constrained heterogeneous facility location. In _Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT)_. 63–76.
  * Lackner and Skowron (2023) Martin Lackner and Piotr Skowron. 2023.  _Multi-Winner Voting with Approval Preferences_.  Springer.
  * Le Breton and Zaporozhets (2009) Michel Le Breton and Vera Zaporozhets. 2009.  On the equivalence of coalitional and individual strategy-proofness properties.  _Social Choice and Welfare_ 33, 2 (2009), 287–309.
  * LeGrand et al. (2007) Rob LeGrand, Evangelos Markakis, and Aranyak Mehta. 2007\.  Some results on approximating the minimax solution in approval voting. In _Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)_. 1193–1195.
  * Lu et al. (2010) Pinyan Lu, Xiaorui Sun, Yajun Wang, and Zeyuan Allen Zhu. 2010\.  Asymptotically optimal strategy-proof mechanisms for two-facility games. In _Proceedings 11th ACM Conference on Electronic Commerce (EC)_. 315–324.
  * Manjunath (2012) Vikram Manjunath. 2012\.  Group strategy-proofness and voting between two alternatives.  _Mathematical Social Sciences_ 63, 3 (2012), 239–242.
  * Meir et al. (2011) Reshef Meir, Shaull Almagor, Assaf Michaely, and Jeffrey S. Rosenschein. 2011.  Tight bounds for strategyproof classification. In _Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_. 319–326.
  * Meir et al. (2012) Reshef Meir, Ariel D. Procaccia, and Jeffrey S. Rosenschein. 2012\.  Algorithms for strategyproof classification.  _Artificial Intelligence_ 186 (2012), 123–156.
  * Moulin (1980) Herve Moulin. 1980\.  On strategy-proofness and single peakedness.  _Public Choice_ 35, 4 (1980), 437–455.
  * Procaccia and Tennenholtz (2013) Ariel D. Procaccia and Moshe Tennenholtz. 2013.  Approximate mechanism design without money.  _ACM Transactions on Economics and Computation_ 1, 4 (2013), 18:1–18:26.
  * Rey and Maly (2023) Simon Rey and Jan Maly. 2023.  The (computational) social choice take on indivisible participatory budgeting.  _CoRR_ abs/2303.00621 (2023).
  * Satterthwaite (1975) Mark Allen Satterthwaite. 1975\.  Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions.  _Journal of Economic Theory_ 10, 2 (1975), 187–217.
  * Schummer and Vohra (2002) James Schummer and Rakesh V. Vohra. 2002.  Strategy-proof location on a network.  _Journal of Economic Theory_ 104, 2 (2002), 405–428.
  * Sui and Boutilier (2015) Xin Sui and Craig Boutilier. 2015.  Approximately strategy-proof mechanisms for (constrained) facility location. In _Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_. 605–613.
  * Talmon (2023) Nimrod Talmon. 2023\.  Social choice around decentralized autonomous organizations: On the computational social choice of digital communities. In _Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_. 1768–1773.
  * Walsh (2021) Toby Walsh. 2021\.  Strategy proof mechanisms for facility location at limited locations. In _Proceedings of the 18th Pacific Rim International Conference on Artificial Intelligence (PRICAI)_. 113–124.


# Quantum non-demolition measurements of moving target states

Anton L. Andersen<EMAIL_ADDRESS>Center for Complex Quantum
Systems, Department of Physics and Astronomy, Aarhus University, Ny Munkegade
120, DK-8000 Aarhus C, Denmark  Klaus Mølmer<EMAIL_ADDRESS>Aarhus
Institute of Advanced Studies, Aarhus University, Høegh-Guldbergs Gade 6B,
DK-8000 Aarhus C, Denmark
Center for Complex Quantum Systems, Department of Physics and Astronomy,
Aarhus University, Ny Munkegade 120, DK-8000 Aarhus C, Denmark

###### Abstract

We present a protocol for probing the state of a quantum system by its
resonant coupling and entanglement with a meter system. By continuous
measurement of a time evolving meter observable, we infer the evolution of the
entangled systems and, ultimately, the state and dynamics of the system of
interest. The photon number in a cavity field is thus resolved by simulated
monitoring of the time dependent excited state population of a resonantly
coupled two-level system, and we propose to regard this as an extension of
quantum non-demolition measurements with potential applications in quantum
metrology and quantum computing.

††preprint: APS/123-QED

Introduction. In most studies and applications of quantum systems, it is
required to perform precise measurements of a physical observable to either
detect its value in a given state or changes of its value due to physical
interactions. So-called quantum non-demolition (QND) observations play a
special role: these are observations where the interaction with the
measurement apparatus does not change the value of the observable of interest
or any other property of the system that may subsequently cause changes of
that value [1, 2, 3]. QND observables permit practical detection schemes where
a sequence of weak measurements accumulates measurement statistics and
gradually approaches a projective measurement with the outcome distribution
given by Born’s rule. QND measurements are useful for the high precision
monitoring of perturbations or dissipative state changes of quantum systems
and sensors [4, 3, 5, 6].

The degree of excitation of a quantum system commutes with the system
Hamiltonian and constitutes a QND observable, which can be probed by a
dispersive interactions that induce a complex phase rotation on, e.g., a qubit
or field probe. Repeated or continuous measurements with such probes gradually
project the system of interest on an energy eigenstate [7, 8, 9, 10, 11, 12,
13, 14, 15], and they may be used to identify, quantum jumps in its excitation
dynamics [16, 17, 18, 19, 20, 21, 22, 23].

Figure 1:  (a) Unconditioned dynamics of the excited state population
$\langle\hat{\sigma}_{ee}\rangle$, showing collapses and revivals due to its
composition by quantum Rabi oscillations with different frequencies and
constant weight factors $p_{n}$, shown in (b). (c) The stochastic dynamics of
the expectation value $\langle\hat{\sigma}_{ee}\rangle$, conditioned on weak
continuous measurement of $\hat{\sigma}_{ee}$. (d) The continuous probing of
$\hat{\sigma}_{ee}$ gradually identifies a single Rabi oscillation frequency
and hence collapses the system from a thermal ensemble with mean excitation
$\langle\hat{n}\rangle=3$ into a single energy subspace as shown by the
evolution of the subspace probabilities $p_{n}$.

Variants of QND measurements include stroboscopic QND measurements, such as
brief position measurements carried out around times $t_{n}=n\pi/\omega$ of an
harmonic oscillator with frequency $\omega$ [24, 25, 26], to enable the study
of periodically evolving properties of quantum systems, and emergent QND
measurements, which probe a physical observable very weakly and effectively,
over time, extract its expectation value in one of the energy eigenstates [27,
28]. Other strategies employ additional degrees of freedom to evade back
action and thereby reach ultimate sensitivity with quantum probes [29, 30, 31,
32, 33].

Probing by resonant Rabi dynamics. In this Letter we propose a different
approach for the measurement of the excitation of an oscillator system,
relying on resonant interactions and a deliberate exchange of quanta of energy
with a qubit meter system. Fig.1(a) shows how a mixture or superposition of
oscillator eigenstates leads to the so-called damped and revived Rabi
oscillations appearing as oscillations in a two-level resonant probe with
different $n$-dependent frequencies, demonstrated, e.g., with trapped ions
[34] and superconducting qubits [35]. In this situation, the total, shared
number of excitations is a conserved quantity and QND observable, and we
suggest to measure its value by a weak continuous monitoring of the
oscillating qubit meter excited state population in stead of the final state
projective and destructive measurements applied in [34, 35]. Fig.1(c) shows
the conditioned excited state population dynamics as the measurement gradually
resolves the frequency (and phase) of the coherent exchange of energy between
the quantum oscillator and the qubit. Panel (d) shows the associated collapse
of the system on a moving target state with a definite total number of
excitations. We argue that this measurement is faster and may thus enable
detection of dynamics and oscilator quantum jumps that cannot be resolved by
the dispersive probing.

Weak continuous measurements. We consider a harmonic oscillator resonantly
coupled to a qubit with states $\ket{g}$ and $\ket{e}$, via the resonant
Jaynes-Cummings Hamiltonian,

$\displaystyle
H=\omega(\hat{a}^{\dagger}\hat{a}+\hat{\sigma}_{ee})+g(\hat{a}^{\dagger}\hat{\sigma}_{ge}+\hat{a}\hat{\sigma}_{eg}),$
(1)

where $\hbar=1$ such that $\omega$ is the energy spacing of the oscillator and
the qubit, $\hat{a}^{\dagger}$ ($\hat{a}$) is the creation (annihilation)
operator of the oscillator, $\hat{\sigma}_{ij}=\ket{i}\\!\bra{j}$ and $g$ is
the coupling strength. The Jaynes-Cummings coupling will drive oscillations
between product states $\ket{n,e}\leftrightarrow\ket{n+1,g}$ with angular
frequency $2g\sqrt{n+1}$, as is seen in Fig. 1.

We imagine that the qubit is a real or artificial atom with further excited
states and that the qubit observable $\hat{\sigma}_{ee}$ can be continuously
measured by phase sensitive, homodyne detection of a classical probe field
coupling $\ket{e}$ off-resonantly to an excited state. While this probing is
taking place, the dynamics of the system is governed by the stochastic master
equation (SME) [36, 37],

$\displaystyle d\rho=-i[H,\rho]dt+k\mathcal{D}[\hat{\sigma}_{ee}]\rho
dt+\sqrt{2k}\eta\mathcal{H}[\hat{\sigma}_{ee}]\rho dW,$ (2)

where $dW$ represents the Gaussian noise on the phase quadrature of the probe
field with mean zero and variance equal to $dt$, $k$ denotes the measurement
strength and $\eta$ is the detection efficiency. In this work we will assume
$\eta=1$ for simplicity, but our approach works also for non-unit optical
detection efficiencies. The first term in Eq. (2) describes the normal time
evolution including the Rabi oscillation dynamics. The second term in Eq. (2)
contains the dissipation superoperator

$\displaystyle\mathcal{D}[\hat{O}]\rho=2\hat{O}\rho\hat{O}^{\dagger}-\\{\hat{O}^{\dagger}\hat{O},\rho\\},$
(3)

describing decoherence due to the disturbance caused by the measurement. The
final term in Eq. (2) contains the superoperator

$\displaystyle\mathcal{H}[\hat{O}]\rho=\hat{O}\rho+\rho\hat{O}^{\dagger}-\langle\hat{O}+\hat{O}^{\dagger}\rangle_{\rho},$
(4)

where $\langle\hat{O}\rangle_{\rho}=\text{Tr}[\hat{O}\rho]$. This term
describes the back action of the stochastic information gain by the
measurement process. The Wiener noise increment $dW$ is given by the
difference between the random measurement outcome obtained in the experiment,
$dY(t)$, and its expected mean value,

$\displaystyle
dY(t)=\langle\hat{\sigma}_{ee}\rangle_{\rho}dt+\frac{dW}{\sqrt{8k}}.$ (5)

$dW$ can be simulated in numerical studies, while one obtains the conditioned
dynamics of an experimentally monitored system by solving Eq. (2) with $dW$
extracted from Eq. (5). Numerical solutions to the stochastic master equation
are obtained using the QuTiP toolbox [38, 39].

Figure 2:  Simulated dynamics with the harmonic oscillator prepared initially
in a thermal state with mean excitation number $\langle\hat{n}\rangle=3$ and
the qubit prepared in the excited state. The upper panels show the
probabilities for the total (integer) number of excitations, while the lower
panels show the qubit excited state population for weak probing ($k=0.1g$,
panels (a) and (b)), strong probing ($k=g$, panels (c) and (d), and very
strong probing ($k=10g$, panels (e) and (f)).

To observe how the continuous measurement of $\hat{\sigma}_{ee}$ reveals the
oscillator dynamics, we will consider a situation where the qubit is initially
prepared in the state $\ket{e}$, while the harmonic oscillator is in a mixed
state described by $\rho_{HO}=\sum_{n}p_{n}(t=0)\ket{n}\\!\bra{n}$. Results of
simulations are presented in Fig. 2 for $\eta=1$, and they show that the
system converges to states with a definite total number of excitations. For
the case of weak probing we see that the definite value of $n$ occurs together
with a definite harmonic evolution of the excited state population (at
frequency $2g\sqrt{n+1}$), while intermediate probing strengths $k$ also
identify $n$ but continuously disturb the phase of the Rabi oscillations. For
even stronger probing, a Zeno effect prevents the coherent Rabi oscillations
and makes the distinction harder between different values of $n$ [40].

Optimal probing. In order to assess the time needed for the continuous
measurements to determine the degree of excitation of the system by the
corresponding frequency of the Rabi oscillations, we study the convergence
towards unity of the purity $P$ of the conditional density matrix
Tr$(\rho^{2})$. As seen in Fig. 3, we can fit its mean value over many
trajectories with the model $P(t)=1-(1-P(t=0))e^{-t/\tau}$, and repeating this
procedure for different probing strengths we observe in the insert of Fig. 3
that the time needed to perform the QND measurement is smallest in the
intermediate strength probing regime, $k\simeq g$.

Figure 3:  The average purity $\langle P\rangle_{dW}$ from 200 simulated
trajectories in the weak probing regime (k=0.1g). The gray shaded area
corresponds to values within one standard deviation from the mean. The average
time $\tau$, needed to perform the measurement of the energy, is extracted by
fitting the model $P(t)=1-(1-P(t=0))e^{-t/\tau}$. The harmonic oscillator is
prepared with an initial thermal distribution with $\langle\hat{n}\rangle=3$
and the qubit is initially prepared in the excited state. The insert shows the
average time of purification and distinction of the excitation of the harmonic
oscillator as function of probing the strength $k$.

This result can be explained qualitatively, since probing with a small value
of $k$ only yields an appreciable signal-to-noise when accumulated over times
$\propto 1/k$. During that time the system undergoes one or several Rabi
oscillations, and despite the white noise component in the weak probe signal
it is possible to discern a single leading harmonic component and hence reveal
the value of $n$.

While increasing $k$ increases the data extraction rate, when $k$ becomes of
the order of the value of $g$ the back action of the qubit excited state
measurements causes significant disturbance of the Rabi oscillations.
Discerning different $n$-values by the frequency of the Rabi oscillations, is
gradually hampered by these disturbances when $k$ exceeds $g$. Ultimately,
when $k$ is very large, the measurements effectively project the qubit in its
energy eigenbasis and thus freezes the Rabi oscillations by the Quantum Zeno
mechanism [40], see Fig. 2(f).

We note that the moderate and strong measurement back action do not invalidate
the QND property with respect to distinction of Rabi subspaces, they only
cause stochastic modifications of the harmonic population oscillation within
the subspaces as shown in Fig.3, and hence they make the distinction between
different subspaces less effective.

Observation of Quantum Jumps. Our probing may be applied to mechanical
oscillators, quantized fields, photons and magnons, which are all systems
where there has been an interest in demonstrating the quantized nature of
their interactions [17, 8, 10, 11, 12, 13, 14, 9, 41, 15, 28], and dynamical
features such as quantum jumps [16, 19, 20, 21, 22, 23]. The latter
experiments are often hampered by the time between jumps being comparable to
the time needed to detect the change of $n$ in an experiment. For this, our
scheme may be particularly useful, and we now discuss how to incorporate
thermal quantum jumps in the formalism and how well they are inferred from a
measurement record.

If the the harmonic oscillator is connected to a thermal reservoir with an
average number of excitations $n_{T}$ and coupling rate where $\gamma$, Eq.
(2) is modified into

$\displaystyle d\rho=$
$\displaystyle-i[H,\rho]dt-\frac{\gamma}{2}(n_{T}+1)\mathcal{D}[\hat{a}]\rho
dt-\frac{\gamma}{2}n_{T}\mathcal{D}[\hat{a}^{\dagger}]\rho dt$ (6)
$\displaystyle+k\mathcal{D}[\hat{\sigma}_{ee}]\rho
dt+\sqrt{2k}\eta\mathcal{H}[\hat{\sigma}_{ee}]\rho dW.$

The terms involving $\mathcal{D}[\hat{a}]$ and
$\mathcal{D}[\hat{a}^{\dagger}]$ are responsible for the loss or absorption of
excitations to or from the bath.

Figure 4. shows a simulation of the dynamics described by Eq. (6). For this
particular simulation, we assumed that no quanta were emitted into or absorbed
from the bath until $gt=25$ where we simulated an incoherent heating event.
The blue curve in the lower panel shows the mean excitation of the oscillator,
inferred by a hypothetical observer of both the probing dynamics and the
occurrence of the energy exchange between the oscillator and the heat bath,
while the orange curve shows the mean excitation of the oscillator inferred by
an observer having only access to the continuous probing record. In the upper
panel, the change in $n$ accompanies a change in the Rabi oscillation
frequency appearing instantly in the regular blue curve inferred by the
hypothetical observer. The more erratic orange curve reveals the uncertainty
of the real observer who realizes the change of state and agrees with the
hypothetical observer only after the signal-to-noise ratio has accumulated to
permit distinction of the different $n$-values.

In Fig. 5 we show a longer measurement record with multiple jumps inferred as
the rapid transfer of near unit probability weights on different values of
$n$. A long time average of these probabilities would reveal the Boltzmann
distribution, while the measurements act like a Maxwell demon and turn the
probabilities into random almost certain knowledge about the state of the
system. We note that, as in [42, 18], it is possible to use the entire
measurement record and not only previous data for the theoretical estimation
of the state at any given time and that would improve the agreement between
the inferred and the true jumps in Figs. 4 and 5.

Figure 4:  Observation of a quantum jump. The orange curve in the upper
(lower) panel shows the excited state population (average excitation of the
oscillator) inferred from weak continuous measurements on the qubit meter. The
oscillator is subject to a single quantum jump occurring at $gt=25$, and the
blue curves show the inferred qubit excited state population and oscillator
number of quanta, assuming the added knowledge of when the jump happened.
Parameters used for the simulation are $k=0.1g$, $\gamma=10^{-3}g$,
$\langle\hat{n}\rangle=n_{T}=3$. Figure 5:  Observation of multiple quantum
jumps. The harmonic oscillator starts in a thermal distribution with mean
excitation number $\langle\hat{n}\rangle=3$. The probing strength $k=g$, such
that it is close to the optimal value. The coupling to the bath is
$\gamma=10^{-3}g$ and its mean excitation is $n_{T}=3$.

General picture. The characteristic property of our emergent subspace QND
procedure is the convergence and subsequent restriction of the system to
follow trajectories within single degenerate subspaces of a certain operator
$\hat{A}$ which commutes with the Hamiltonian, $[\hat{A},\hat{H}]=0$. An
interaction term in the Hamiltonian $\hat{H}$ causes a time evolution of a
meter observable $\hat{B}$, which commutes with $\hat{A}$, and the temporal
outcome of measurements of $\hat{B}$ may gradually collapse the system on a
state that is evolving in a definite eigenspace of $\hat{A}$. For this
detection to work, it is important that the characteristic measurement records
differ when the system occupies different such subspaces. In our example,
$\hat{A}$ is the total number of excitations and $\hat{B}$ is the qubit meter
excitation, and the Rabi oscillation frequencies, indeed, have distinct values
in each eigenspace of $\hat{A}$. Notably, the measurements both reveal the
subspace (of $\hat{A}$) and the actual time dependent entangled state of the
system and meter from which we infer the separate system dynamics. While our
analysis used the example of system and meter entangled state dynamics, the
commutator requirements between $\hat{H}$ and $\hat{A}$ and between $\hat{A}$
and $\hat{B}$ suffice for our scheme to resolve the value of $\hat{A}$ by the
measurement of $\hat{B}$ in any quantum system, e.g., pertaining to the
population of subspaces of a single multi-level quantum system.

If we assume unit detector efficiency, and an initial mixture of pure states
$\ket{\psi_{n}(t)}$, each occupying a single degenerate subspace of $\hat{A}$,

$\displaystyle\rho(t)=\sum_{n}p_{n}(t)\ket{\psi_{n}(t)}\\!\bra{\psi_{n}(t)},$
(7)

we may generalize (2) to the measured observable $\hat{B}$

$\displaystyle d\rho=-i[H,\rho]dt+k\mathcal{D}[\hat{B}]\rho
dt+\sqrt{2k}\eta\mathcal{H}[\hat{B}]\rho dW.$ (8)

The ansatz in Eq.(7) then leads to the following equations

$\displaystyle
dp_{n}=\sqrt{8k}p_{n}\Big{(}\bra{\psi_{n}(t)}\hat{B}\ket{\psi_{n}(t)}-\langle\hat{B}\rangle_{\rho(t)}\Big{)}dW,$
(9)

and we observe that, if only one state $\ket{\psi_{n}}$ is populated,
$p_{n}=1$, $\bra{\psi_{n}}\hat{B}\ket{\psi_{n}}=\langle\hat{B}\rangle_{\rho}$,
and the stochastic noise terms does not affect the future evolution of the
unit value of $p_{n}(t)$, while the state $\ket{\psi_{n}(t)}$ may still evolve
within the given occupied subspace.

To further understand why the system collapses on a single subspace, we note
that the purity of the system is $P(t)=\sum_{n}p_{n}^{2}(t)$, and applying
Itô’s rule for $d(p_{n}^{2})$ yields

$\displaystyle\begin{split}dP=\sum_{n}\Big{[}&8kp_{n}^{2}\Big{(}\bra{\psi_{n}}\hat{B}\ket{\psi_{n}}-\langle\hat{B}\rangle_{\rho}\Big{)}^{2}dt\\\
&+\sqrt{32k}p_{n}^{2}\Big{(}\bra{\psi_{n}}\hat{B}\ket{\psi_{n}}-\langle\hat{B}\rangle_{\rho}\Big{)}dW\Big{]}.\end{split}$
(10)

The average of $dW$ is zero and hence the average evolution of the purity
obeys

$\displaystyle d\langle P\rangle_{dW}=\sum_{n}8k\left\langle
p_{n}^{2}\Big{(}\langle\hat{B}\rangle_{n}-\langle\hat{B}\rangle_{\rho}\Big{)}^{2}\right\rangle_{dW}dt,$
(11)

which is positive and causes $\langle P\rangle_{dW}$ to increase until the
time evolution of $\langle\hat{B}\rangle_{\rho}$ is indistinguishable from the
one in just one of the subspaces $\langle\hat{B}\rangle_{n}$. If several
subspaces display the same evolution, they are not distinguished and our
measurement is emergent QND with respect to their union, but we may populate a
mixed state in that union.

Conclusion and Outlook. We have presented a new principle for continuous QND
measurements which does not project the system on the eigenstate of the QND
observable but rather on a still evolving state within a subspace of states.
These subspaces are discerned by the characteristic frequency of the evolution
of the mean value of the observed quantity, which may be monitored faster than
the accumulation of dispersive phase shifts in the more usual QND setting. If
$\Delta$ is the detuning and $g$ is the resonant coupling strength between a
harmonic oscillator and a two-level system, their dispersive coupling is given
by $g^{2}/\Delta$ [43]. To avoid transfer of excitation, the detuning should
be much larger than the coupling strength $g\ll\Delta$, and the timescale on
which the conventional QND measurement takes place is longer by a factor of
order $\Delta/g\gg 1$ compared to our resonant proposal. Our method may pave
the way to monitor thermal quantum jumps in real time and use measurements and
feedback for rapid state preparation and control.

Acknowledgment. The authors acknowledge support from the Danish National
Research Foundation through the Center of Excellence for Complex Quantum
Systems (Grant agreement No. DNRF156). KM acknowledges discussions with Dr.
Faezeh Pirmoradian in the early stages of the project.

## References

  * Braginsky  _et al._ [1980] V. B. Braginsky, Y. I. Vorontsov, and K. S. Thorne, Quantum Nondemolition Measurements, Science 209, 547 (1980).
  * Caves  _et al._ [1980] C. M. Caves, K. S. Thorne, R. W. P. Drever, V. D. Sandberg, and M. Zimmermann, On the measurement of a weak classical force coupled to a quantum-mechanical oscillator. I. Issues of principle, Rev. Mod. Phys. 52, 341 (1980).
  * Braginsky and Khalili [1990] V. B. Braginsky and F. J. Khalili, Gravitational wave antenna with QND speed meter, Physics Letters A 147, 251 (1990).
  * Braginskii and Khalili [1988] V. B. Braginskii and F. I. Khalili, Frequency-anticorrelated quantum states, Zh. Eksp. Teor. Fiz. 94, 151 (1988), [Sov. Phys. JETP 67, 84 (1988)].
  * Braginsky and Khalili [1996] V. B. Braginsky and F. Y. Khalili, Quantum nondemolition measurements: the route from toys to tools, Rev. Mod. Phys. 68, 1 (1996).
  * Bocko and Onofrio [1996] M. F. Bocko and R. Onofrio, On the measurement of a weak classical force coupled to a harmonic oscillator: experimental progress, Rev. Mod. Phys. 68, 755 (1996).
  * Brune  _et al._ [1994] M. Brune, P. Nussenzveig, F. Schmidt-Kaler, F. Bernardot, A. Maali, J. M. Raimond, and S. Haroche, From Lamb shift to light shifts: Vacuum and subphoton cavity fields measured by atomic phase sensitive detection, Phys. Rev. Lett. 72, 3339 (1994).
  * Johnson  _et al._ [2010] B. R. Johnson, M. D. Reed, A. A. Houck, D. I. Schuster, L. S. Bishop, E. Ginossar, J. M. Gambetta, L. DiCarlo, L. Frunzio, S. M. Girvin, and R. J. Schoelkopf, Quantum non-demolition detection of single microwave photons in a circuit, Nature Phys 6, 663 (2010).
  * Lachance-Quirion  _et al._ [2017] D. Lachance-Quirion, Y. Tabuchi, S. Ishino, A. Noguchi, T. Ishikawa, R. Yamazaki, and Y. Nakamura, Resolving quanta of collective spin excitations in a millimeter-sized ferromagnet, Sci Adv 3 (2017).
  * Neuman  _et al._ [2020] T. Neuman, D. S. Wang, and P. Narang, Nanomagnonic Cavities for Strong Spin-Magnon Coupling and Magnon-Mediated Spin-Spin Interactions, Phys. Rev. Lett. 125, 247702 (2020).
  * Satzinger  _et al._ [2018] K. J. Satzinger, Y. P. Zhong, H. S. Chang, G. A. Peairs, A. Bienfait, M.-H. Chou, A. Y. Cleland, C. R. Conner, É. Dumur, J. Grebel, I. Gutierrez, B. H. November, R. G. Povey, S. J. Whiteley, D. D. Awschalom, D. I. Schuster, and A. N. Cleland, Quantum control of surface acoustic-wave phonons, Nature 563, 661 (2018).
  * Chu  _et al._ [2018] Y. Chu, P. Kharel, T. Yoon, L. Frunzio, P. T. Rakich, and R. J. Schoelkopf, Creation and control of multi-phonon fock states in a bulk acoustic-wave resonator, Nature 563, 666 (2018).
  * Arrangoiz-Arriola  _et al._ [2019] P. Arrangoiz-Arriola, E. A. Wollack, Z. Wang, M. Pechal, W. Jiang, T. P. McKenna, J. D. Witmer, R. Van Laer, and A. H. Safavi-Naeini, Resolving the energy levels of a nanomechanical oscillator, Nature 571, 537 (2019).
  * Sletten  _et al._ [2019] L. R. Sletten, B. A. Moores, J. J. Viennot, and K. W. Lehnert, Resolving Phonon Fock States in a Multimode Cavity with a Double-Slit Qubit, Phys. Rev. X 9, 021056 (2019).
  * Lachance-Quirion  _et al._ [2020] D. Lachance-Quirion, S. P. Wolski, Y. Tabuchi, S. Kono, K. Usami, and Y. Nakamura, Entanglement-based single-shot detection of a single magnon with a superconducting qubit, Science 367, 425 (2020).
  * Gleyzes  _et al._ [2007] S. Gleyzes, S. Kuhr, C. Guerlin, J. Bernu, S. Deléglise, U. Busk Hoff, M. Brune, J.-M. Raimond, and S. Haroche, Quantum jumps of light recording the birth and death of a photon in a cavity, Nature 446, 297 (2007).
  * Guerlin  _et al._ [2007] C. Guerlin, J. Bernu, S. Deléglise, C. Sayrin, S. Gleyzes, S. Kuhr, M. Brune, J.-M. Raimond, and S. Haroche, Progressive field-state collapse and quantum non-demolition photon counting, Nature 448, 889 (2007).
  * Rybarczyk  _et al._ [2015] T. Rybarczyk, B. Peaudecerf, M. Penasa, S. Gerlich, B. Julsgaard, K. Mølmer, S. Gleyzes, M. Brune, J. M. Raimond, S. Haroche, and I. Dotsenko, Forward-backward analysis of the photon-number evolution in a cavity, Phys. Rev. A 91, 062116 (2015).
  * Vijay  _et al._ [2011] R. Vijay, D. H. Slichter, and I. Siddiqi, Observation of Quantum Jumps in a Superconducting Artificial Atom, Phys. Rev. Lett. 106, 110502 (2011).
  * Delteil  _et al._ [2014] A. Delteil, W.-b. Gao, P. Fallahi, J. Miguel-Sanchez, and A. Imamoğlu, Observation of Quantum Jumps of a Single Quantum Dot Spin Using Submicrosecond Single-Shot Optical Readout, Phys. Rev. Lett. 112, 116802 (2014).
  * Minev  _et al._ [2019] Z. K. Minev, S. O. Mundhada, S. Shankar, P. Reinhold, R. Gutiérrez-Jáuregui, R. J. Schoelkopf, M. Mirrahimi, H. J. Carmichael, and M. H. Devoret, To catch and reverse a quantum jump mid-flight, Nature 570, 200 (2019).
  * Peil and Gabrielse [1999] S. Peil and G. Gabrielse, Observing the Quantum Limit of an Electron Cyclotron: QND Measurements of Quantum Jumps between Fock States, Phys. Rev. Lett. 83, 1287 (1999).
  * Sun  _et al._ [2014] L. Sun, A. Petrenko, Z. Leghtas, B. Vlastakis, G. Kirchmair, K. M. Sliwa, A. Narla, M. Hatridge, S. Shankar, J. Blumoff, L. Frunzio, M. Mirrahimi, M. H. Devoret, and R. J. Schoelkopf, Tracking photon jumps with repeated quantum non-demolition parity measurements, Nature 511, 444 (2014).
  * Vasilakis  _et al._ [2011] G. Vasilakis, V. Shah, and M. V. Romalis, Stroboscopic Backaction Evasion in a Dense Alkali-Metal Vapor, Phys. Rev. Lett. 106, 143601 (2011).
  * Vasilakis  _et al._ [2015] G. Vasilakis, H. Shen, K. Jensen, M. Balabas, D. Salart, B. Chen, and E. S. Polzik, Generation of a squeezed state of an oscillator by stroboscopic back-action-evading measurement, Nature Physics 11, 389 (2015).
  * Wade  _et al._ [2015] A. C. J. Wade, J. F. Sherson, and K. Mølmer, Squeezing and Entanglement of Density Oscillations in a Bose-Einstein Condensate, Phys. Rev. Lett. 115, 060401 (2015).
  * Yang  _et al._ [2018] D. Yang, C. Laflamme, D. Vasilyev, M. Baranov, and P. Zoller, Theory of a Quantum Scanning Microscope for Cold Atoms, Phys. Rev. Lett. 120, 133601 (2018).
  * Dellantonio  _et al._ [2018] L. Dellantonio, O. Kyriienko, F. Marquardt, and A. S. Sørensen, Quantum nondemolition measurement of mechanical motion quanta, Nature Communications 9, 3621 (2018).
  * Tsang and Caves [2010] M. Tsang and C. M. Caves, Coherent Quantum-Noise Cancellation for Optomechanical Sensors, Phys. Rev. Lett. 105, 123601 (2010).
  * Wasilewski  _et al._ [2010] W. Wasilewski, K. Jensen, H. Krauter, J. J. Renema, M. V. Balabas, and E. S. Polzik, Quantum Noise Limited and Entanglement-Assisted Magnetometry, Phys. Rev. Lett. 104, 133601 (2010).
  * Tsang and Caves [2012] M. Tsang and C. M. Caves, Evading Quantum Mechanics: Engineering a Classical Subsystem within a Quantum Environment, Phys. Rev. X 2, 031016 (2012).
  * Wimmer  _et al._ [2014] M. H. Wimmer, D. Steinmeyer, K. Hammerer, and M. Heurs, Coherent cancellation of backaction noise in optomechanical force measurements, Phys. Rev. A 89, 053836 (2014).
  * Polzik and Hammerer [2015] E. S. Polzik and K. Hammerer, Trajectories without quantum uncertainties, Annalen der Physik 527, A15 (2015).
  * Meekhof  _et al._ [1996] D. M. Meekhof, C. Monroe, B. E. King, W. M. Itano, and D. J. Wineland, Generation of Nonclassical Motional States of a Trapped Atom, Phys. Rev. Lett. 76, 4 (1996).
  * Hofheinz  _et al._ [2008] M. Hofheinz, E. M. Weig, M. Ansmann, R. C. Bialczak, E. Lucero, M. Neeley, A. D. O’Connell, H. Wang, J. M. Martinis, and A. N. Cleland, Generation of fock states in a superconducting quantum circuit, Nature 454, 310 (2008).
  * Howard M. Wiseman and Milburn [2010] Howard M. Wiseman and G. J. Milburn,  _Quantum Measurement and Control_ (Cambridge University Press, 2010).
  * Blattmann and Mølmer [2016] R. Blattmann and K. Mølmer, Conditioned quantum motion of an atom in a continuously monitored one-dimensional lattice, Phys. Rev. A 93, 052113 (2016).
  * Johansson  _et al._ [2012] J. R. Johansson, P. D. Nation, and F. Nori, QuTiP: An open-source Python framework for the dynamics of open quantum systems, Computer Physics Communications 183, 1760 (2012).
  * Johansson  _et al._ [2013] J. R. Johansson, P. D. Nation, and F. Nori, QuTiP 2: A Python framework for the dynamics of open quantum systems, Computer Physics Communications 184, 1234 (2013).
  * Schulman [1998] L. S. Schulman, Continuous and pulsed observations in the quantum Zeno effect, Phys. Rev. A 57, 1509 (1998).
  * O’Connell  _et al._ [2010] A. D. O’Connell, M. Hofheinz, M. Ansmann, R. C. Bialczak, M. Lenander, E. Lucero, M. Neeley, D. Sank, H. Wang, M. Weides, J. Wenner, J. M. Martinis, and A. N. Cleland, Quantum ground state and single-phonon control of a mechanical resonator, Nature 464, 697 (2010).
  * Gammelmark  _et al._ [2013] S. Gammelmark, B. Julsgaard, and K. Mølmer, Past Quantum States of a Monitored System, Phys. Rev. Lett. 111, 160401 (2013).
  * Gerry and Knight [2008] C. C. Gerry and P. L. Knight,  _Introductory Quantum Optics_ (Cambridge University Press, 2008).