# Multi-winner Approval Voting Goes Epistemic

Tahar Allouche1111Contact Author Jérome Lang1&Florian Yger1
1LAMSADE, CNRS, PSL, Université Paris-Dauphine
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Epistemic voting interprets votes as noisy signals about a ground truth. We
consider contexts where the truth consists of a set of objective winners,
knowing a lower and upper bound on its cardinality. A prototypical problem for
this setting is the aggregation of multi-label annotations with prior
knowledge on the size of the ground truth. We posit noise models, for which we
define rules that output an optimal set of winners. We report on experiments
on multi-label annotations (which we collected).

##  1 Introduction

The epistemic view of voting assumes the existence of a ground truth which,
usually, is either an alternative or a ranking over alternatives. Votes
reflect opinions or beliefs about this ground truth; the goal is to aggregate
these votes so as to identify it. Usual methods define a noise model
specifying the probability of each voting profile given the ground truth, and
output the alternative that is the most likely state of the world, or the
ranking that is most likely the true ranking.

Now, there are contexts where the ground truth does not consist of a single
alternative nor a ranking, but of a set of alternatives. Typical examples are
multi-label crowdsourcing (find the items in a set that satisfy some property,
e.g. the sport teams appearing on a picture) or finding the objectively $k$
best candidates (best papers at a conference, best performance in artistic
sports, $k$ patients with highest probabilities of survival if being assigned
a scarce medical resource).

These alternatives that are truly in the ground truth are called ‘winning’
alternatives. Depending on the context, the number of winning alternatives can
be fixed, unconstrained, or more generally, constrained to be in a given
interval. This constraint expresses some prior knowledge on the cardinality of
the ground truth. Here are some examples:

  * •

Picture annotation via crowdsourcing: participants are shown a picture taken
from a soccer match and have to identify the team(s) appearing in it. The
ground truth is known to contain one or two teams.

  * •

Guitar chord transcription: voters are base classifier algorithms Nguyen et
al. (2020) which, for a given chord, select the set of notes constitute it.
The true set of notes can contain three to six alternatives.

  * •

Jury: participants are members of a jury which has to give an award to three
papers presented at a conference: the number of objective winners is fixed to
three. (In a variant, the number of awards would be at most three.)

  * •

Resource allocation: participants are doctors and alternatives are Covid-19
patients in urgent need of intensive care; there is a limited number $k$ of
intensive care units. The ground truth consists of those patients who most
deserve to be cured (for example those with the $k$ highest probabilities of
survival if cured).

We assume that voters provide a simple form of information: approval ballots,
indicating which alternatives they consider plausible winners. These approval
ballots are not subject to any cardinality constraint: a voter may approve a
number of alternatives, even if it does not lie in the interval bearing on the
output. This is typically the case for totally ignorant voters, who are
expected to approve all alternatives.

Sometimes, the aggregating mechanism has some prior information about the
likelihood of alternatives and the reliability of voters. We first study a
simple case where this information is specified in the input: in the noise
model, each voter has a probability $p_{i}$ (resp. $q_{i})$ of approving a
winning (resp. non-winning) alternative, and each alternative has a prior
probability to be winning. This departs from classical voting, where voters
are usually treated equally (anonymity), and similarly for alternatives
(neutrality).

This simple case serves as a building component for the more complex case
where these parameters are not known beforehand but estimated from the votes:
votes allow to infer information about plausibly winning alternatives, from
which we infer information about voter reliabilities, which leads to revise
information about winning alternatives, and so on until the process converges.
Here we move back to an anonymous and neutral setting, since all alternatives
(resp. voters) are treated equally before votes are known.

After discussing related work (Section 2), we introduce the model (Section 3)
and give an estimation algorithm (Section 4), first in the case where the
parameters are known, and then in the case where they are estimated from the
votes. In Section 5 we present a data gathering task and analyse the results
of the experiments. Section 6 concludes.

##  2 Related Work

##### Epistemic social choice

It studies how a ground truth can be recovered from noisy votes, viewing
voting rules as maximum likelihood estimators. Condorcet’s jury theorem
Condorcet (1785) considers $n$ independent, equally reliable voters and two
alternatives that are a priori equally likely, and states that if every voter
votes for the correct alternative with probability $p>\frac{1}{2}$, then the
majority rule outputs the correct decision with a probability that increases
with $n$ and tends to 1 when $n$ grows to infinity. See Nitzan and Paroush
(2017) and Dietrich (2008) for proofs and discussion.

The framework was later generalized to more than two alternatives Young
(1988), to voters with different competences Shapley and Grofman (1984);
Drissi-Bakhkhat and Truchon (2004), to a nonuniform prior over alternatives
Ben-Yashar and Nitzan (1997); Ben-Yashar and Paroush (2001), to various noise
models Conitzer and Sandholm (2005); Conitzer et al. (2009), to correlated
votes Pivato (2013, 2017), and to multi-issue domains Xia et al. (2010). Meir
et al. (2019) define a method to aggregate votes weighted according to their
average proximity to the other votes as an estimation of their reliability. A
review of the field can be found in Elkind and Slinko (2016).

Epistemic voting with approval ballots has scarcely been considered. Procaccia
and Shah (2015) study noise models for which approval voting is optimal given
$k$-approval votes, in the sense that the objectively best alternative gets
elected, the ground truth being a ranking over all alternatives. Allouche et
al. (2022) do a similar work for a ground truth consisting of a single
candidate. Caragiannis and Micha (2017) prove that the number of samples
needed to recover the ground truth ranking over alternatives with high enough
probability from approval ballots is exponential if ballots are required to
approve $k$ candidates, but polynomial if the size of the ballots is
randomized.

##### Multi-winner voting rules

They output a set of alternatives (of fixed cardinality or not) from a set of
votes (approvals or rankings). There have been a lot of recent developments in
the field (a recent survey is Faliszewski et al. (2017)), mostly concerning
the classical (non-epistemic) view of social choice, where votes express
preferences.

Multi-winner epistemic voting has received only little attention. Procaccia et
al. (2012) assume a ground truth ranking over alternatives, and identify rules
that output the $k$ alternatives maximizing the likelihood to contain the best
alternative, or the likelihood to coincide with the top-$k$ alternatives. The
last section of Xia and Conitzer (2011) defines a noise model where the ground
truth is a set of $k$ alternatives (and the reported votes are partial
orders). The only work we know where the noise models produce random approval
votes from a ground truth consisting of a set of alternatives is Caragiannis
et al. (2020). They define a family of distance-based noise models, whose
prototypical instance generates approval votes selecting an alternative in the
ground truth (resp. not in the ground truth) with probability $p$ (resp.
$1-p$); as we see further, this is a specific case of our noise model.

##### Crowdsourcing

Kruger et al. (2014); Qing et al. (2014) give a social choice-theoretic study
of collective annotation tasks. Shah and Zhou (2020) design mechanisms for
incentive-compatible elicitation with approval ballots in crowdsourcing
applications. Beyond social choice, collective multi-label annotation was
first addressed in Nowak and Rüger (2010), which studies the agreement between
experts and non-experts in some multi-labelling tasks, and in Deng et al.
(2014), where a scalable aggregation method is presented to solve the multi-
label estimation problem.

##  3 The Model

Let $\mathcal{N}=\\{1,\dots,n\\}$ be a set of voters, and
$\mathcal{A}=\\{a_{1},\dots,a_{m}\\}$ a set of alternatives (possible objects
in images, notes in chords, papers, patients…). Consider a set of $L$
instances: an instance $z$ consists of an approval profile
$A^{z}=(A_{1}^{z},\dots,A_{n}^{z})$ where $A_{i}^{z}\subseteq\mathcal{A}$ is
an approval ballot for every $i\in\mathcal{N}$. For example, in a
crowdsourcing context, a task usually contains multiple questions, and an
instance comprises the voters’ answers to one of these questions.

For each instance $z\in L$, there exists an _unknown_ ground truth $S^{*}_{z}$
belonging to $\mathcal{S}=2^{\mathcal{A}}$, which is the set of objectively
correct alternatives in instance $z$. It is common knowledge that the number
of alternatives in each of them lies in the interval $[l,u]$:
$S^{*}_{z}\in\mathcal{S}_{l,u}=\\{S\in\mathcal{S},l\leq|S|\leq u\\}$, for
given bounds $0\leq l\leq u\leq m$.

Our goal is to unveil the ground truth for each of these instance using the
votes and the prior knowledge on the number of winning alternatives. We define
a noise model consisting of two parametric distributions, namely, a
conditional distribution of the approval ballots given the ground truth, and a
prior distribution on the ground truth. Here we depart from classical noise
models in epistemic social choice, as we suppose that the parameters of these
distributions may be unknown and thus need to be estimated.

For each voter $i\in\mathcal{N}$, we suppose that there exist two unknown
parameters $(p_{i},q_{i})$ in $(0,1)$ such that the approval ballot
$A_{i}^{z}$ on an instance $z\in L$ is drawn according to the following
distribution: for each $a\in{\cal A}$,

$P(a\in A_{i}^{z}|S^{*}_{z}=S)=\left\\{\begin{array}[]{ll}p_{i}&\mbox{if }a\in
S\\\ q_{i}&\mbox{if }a\notin S\end{array}\right.$

where $p_{i}$ (resp. $q_{i}$) is the (unknown) probability that voter $i$
approves a correct (resp. incorrect) alternative. Then we make the following
assumptions:

  * (1)

A voter’s approvals of alternatives are mutually independent given the ground
truth and parameters $(p_{i},q_{i})_{i\in\mathcal{N}}$.

  * (2)

Voters’ ballots are mutually independent given the ground truth.

  * (3)

Instances are independent given the parameters
$(p_{i},q_{i})_{i\in\mathcal{N}}$ and the ground truths.

To model the prior probability of any set $S$ to be the ground truth $S^{*}$,
we define parameters $t_{j}=P(a_{j}\in S^{*})$. $t_{j}$ can be understood as
the prior probability of $a_{j}$ to be in the ground truth set $S^{*}$ before
the cardinality constraints are taken into account. These, together with an
independence assumption on the events $\\{a_{j}\in S^{*}\\}$, gives
$P(S=S^{*})=\prod\limits_{a_{j}\in S}t_{j}\prod\limits_{a_{j}\notin
S}1-t_{j}$. Note that the choice of the parameters $t_{j}$ is not crucial when
running the algorithm for estimating the ground truth: we will see in Section
4.3 that it converges whatever their values. The distribution conditional to
the prior knowledge on the size of the ground truth can be seen as a
projection on the constraints followed by a normalization:

$\tilde{P}(S)=P(S^{*}=S|l\leq|S^{*}|\leq
u)=\frac{P(S^{*}=S\cap|S^{*}|\in[l,u])}{P(|S^{*}|\in[l,u])}$

It follows:

$\tilde{P}(S)=\left\\{\begin{array}[]{ll}\frac{1}{\beta(l,u,t)}\prod\limits_{a_{j}\in
S}t_{j}\prod\limits_{a_{j}\notin S}(1-t_{j})&\mbox{if
}S\in\mathcal{S}_{l,u}\\\ 0&\mbox{if
}S\notin\mathcal{S}_{l,u}\end{array}\right.$

where $\beta(l,u,t)=\sum\limits_{S\in\mathcal{S}_{l,u}}\prod\limits_{a_{j}\in
S}t_{j}\prod\limits_{a_{j}\notin S}(1-t_{j})$.

The ground truths associated with different instances are assumed to be
mutually independent given the parameters.

Two particular cases are worth discussing. First, when $(l,u)=(0,m)$, the
problem is unconstrained and we have $\beta(0,m,t)=P(|S^{*}|\in[0,m])=1$, so
$\tilde{P}(S)=P(S=S^{*})$. In this case the problem degenerates into a series
of independent binary label-wise estimations (see Subsection 4.1).

Second, in the single-winner case $(l,u)=(1,1)$, we have
$\tilde{P}(\\{a_{j}\\})=\frac{t_{j}\prod_{h\neq j}1-t_{h}}{\beta(1,1,t)}$,
therefore, for any approval profile $A$,
$P(S^{*}=\\{a_{j}\\}|A,|S^{*}|=1)\propto\frac{t_{j}}{1-t_{j}}P(A|S^{*}=\\{a_{j}\\})$.
We recover the same estimation problem if we simply introduce
$\alpha_{j}=P(S^{*}=\\{a_{j}\\})$ with $\sum\alpha_{j}=1$ as in Ben-Yashar and
Paroush (2001), in which case we have
$P(S^{*}=\\{a_{j}\\}|A,|S^{*}|=1)\propto\alpha_{j}P(A|S^{*}=\\{a_{j}\\})$.

##  4 Estimating the Ground Truth

Our aim is the intertwined estimation of the ground truth and the parameters
via maximizing the total likelihood of the instances:

$\displaystyle\mathcal{L}(A,S,p,q,t)$
$\displaystyle=\prod_{z=1}^{L}\tilde{P}(S_{z})\prod_{i=1}^{n}P(A_{i}^{z}|S_{z})$

where:

$P(A_{i}^{z}|S_{z})=p_{i}^{|A_{i}^{z}\cap
S_{z}|}q_{i}^{|A_{i}^{z}\cap\overline{S_{z}}|}(1-p_{i})^{|\overline{A_{i}^{z}}\cap
S_{z}|}(1-q_{i})^{|\overline{A_{i}^{z}}\cap\overline{S_{z}}|}$

To this aim, we will introduce an iterative algorithm whose main two steps
will be presented in sequence, in the next subsections, before the main
algorithm is formally defined and its convergence shown. These two steps are:

  * •

Estimating the ground truths given the parameters.

  * •

Estimating the parameters given the ground truths.

Simply put, the algorithm consists in iterating these two steps until it
converges to a fixed point.

###  4.1 Estimating the Ground Truth Given the Votes and the Parameters

Since instances are independent given the parameters, we focus here on one
instance with ground truth $S^{*}$ and profile $A=(A_{1},\dots,A_{n})$. Before
diving into maximum likelihood estimation (MLE), we introduce some notions and
prove some lemmas. In this subsection, we suppose that the parameters
$(p_{i},q_{i})_{i\in\mathcal{N}}$ and $(t_{j})_{j\in\mathcal{A}}$ are known
(later on, these parameters will be replaced by their estimations at each
iteration of the algorithm). Thus, all in all, input and output are as
follows:

  * •

Input: approval profile $A$; parameters $(p_{i},q_{i})_{i\in\mathcal{N}}$ and
$(t_{j})_{j\in\mathcal{A}}$.

  * •

Output: MLE of the ground truth $S^{*}$.

######  Definition 1 (weighted approval score).

Given an approval profile $(A_{1},\dots,A_{n})$, noise parameters
$(p_{i},q_{i})_{1\leq i\leq n}$ and prior parameters $(t_{j})_{1\leq j\leq
m}$, define:

$app_{w}(a_{j})=ln\left(\frac{t_{j}}{1-t_{j}}\right)+\sum_{i:a_{j}\in
A_{i}}ln\left(\frac{p_{i}(1-q_{i})}{q_{i}(1-p_{i})}\right)$

The scores $app_{w}(a_{j})$ can be interpreted as weighted approval scores for
a $(n+m)$-voter profile where:

  * •

for each voter $1\leq i\leq n$: $i$ has a weight
$w_{i}=ln\left(\frac{p_{i}(1-q_{i})}{q_{i}(1-p_{i})}\right)$ and casts
approval ballot $A_{i}$.

  * •

for each $1\leq j\leq m$: there is a virtual voter with weight
$w_{j}=ln\left(\frac{t_{j}}{1-t_{j}}\right)$ who casts approval ballot
$A_{j}=\\{a_{j}\\}$.

While the weight of each voter $i\in\mathcal{N}$ depends on her reliability,
each prior information on an alternative plays the role of a virtual voter who
only selects the concerned alternative, with a weight that increases as the
prior parameter increases.

From now on, we suppose without loss of generality that the alternatives are
ranked according to their score:

$app_{w}(a_{1})\geq app_{w}(a_{2})\geq\dots\geq app_{w}(a_{m})$

######  Definition 2 (threshold and partition).

Define the threshold:

$\tau_{n}=\sum_{i=1}^{n}ln\left(\frac{1-q_{i}}{1-p_{i}}\right)$

and the partition of the set of alternatives in three sets:

$\left\\{\begin{array}[]{ll}S_{max}^{\tau_{n}}&=\left\\{a\in
A,app_{w}(a)>\tau_{n}\right\\}\\\ S_{tie}^{\tau_{n}}&=\left\\{a\in
A,app_{w}(a)=\tau_{n}\right\\}\\\
S_{min}^{\tau_{n}}&=\mathcal{A}\backslash(S_{max}^{\tau_{n}}\cup
S_{tie}^{\tau_{n}})\end{array}\right.$

and let
$k_{max}^{\tau_{n}}=|S_{max}^{\tau_{n}}|,k_{tie}^{\tau_{n}}=|S_{tie}^{\tau_{n}}|,k_{min}^{\tau_{n}}=|S_{min}^{\tau_{n}}|$.

The next result characterizes the sets in $\mathcal{S}$ that are MLEs of the
ground truth given the parameters.

######  Theorem 1.

$\tilde{S}\in\operatorname*{arg\,max}_{S\in\mathcal{S}}\mathcal{L}(A,S,p,q,t)$
if and only if there exists $k\in[l,u]$ such that $\tilde{S}$ is the set of
$k$ alternatives with the highest $k$ values of $app_{w}$ and:

$\left\\{\begin{array}[]{cl}|\tilde{S}\cap
S_{max}^{\tau_{n}}|&=\min(u,k_{max}^{\tau_{n}})\\\ |\tilde{S}\cap
S_{min}^{\tau_{n}}|&=\max(0,l-k_{tie}^{\tau_{n}}-k_{max}^{\tau_{n}})\end{array}\right.$
(1)

So the estimator $\tilde{S}$ is made of some top-$k$ alternatives, where the
possible values of $k$ are determined by Eq. (1). The first equation imposes
that $\tilde{S}$ includes as many elements as possible from
$S_{max}^{\tau_{n}}$ (without exceeding the upper-bound $u$), whereas the
second one imposes that $\tilde{S}$ includes as few elements as possible from
$S_{min}^{\tau_{n}}$ (without getting below the lower-bound $l$). An example
is included in the appendix.

###### Proof.

Since $\tilde{P}(S)>0\iff S\in\mathcal{S}_{l,u}$, we have that
$\operatorname*{arg\,max}_{S\in\mathcal{S}}L(S)=\operatorname*{arg\,max}_{S\in\mathcal{S}_{l,u}}L(S)$.
Moreover, we have that for any $S\in\mathcal{S}_{l,u}$:

$\displaystyle L(S)$
$\displaystyle=\tilde{P}(S)\prod_{i=1}^{n}p_{i}^{|A_{i}\cap
S|}q_{i}^{|A_{i}\cap\overline{S}|}(1-p_{i})^{|\overline{A_{i}}\cap
S|}(1-q_{i})^{|\overline{A_{i}}\cap\overline{S}|}$
$\displaystyle=\tilde{P}(S)\prod_{i=1}^{n}p_{i}^{|A_{i}\cap
S|}q_{i}^{|A_{i}|-|A_{i}\cap S|}(1-p_{i})^{|S|-|A_{i}\cap S|}$
$\displaystyle\mbox{~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}}(1-q_{i})^{|\overline{A_{i}}|-|S|+|A_{i}\cap
S|}$
$\displaystyle\propto\tilde{P}(S)\prod_{i=1}^{n}\left[\frac{1-p_{i}}{1-q_{i}}\right]^{|S|}\left[\frac{p_{i}(1-q_{i})}{q_{i}(1-p_{i})}\right]^{|A_{i}\cap
S|}$ $\displaystyle\propto\frac{1}{\beta}\prod_{a_{j}\in
S}t_{j}\prod_{a_{j}\notin
S}(1-t_{j})\prod_{i=1}^{n}\left[\frac{1-p_{i}}{1-q_{i}}\right]^{|S|}\left[\frac{p_{i}(1-q_{i})}{q_{i}(1-p_{i})}\right]^{|A_{i}\cap
S|}$ $\displaystyle\propto\prod_{a_{j}\in
S}\frac{t_{j}}{1-t_{j}}\prod_{i=1}^{n}\left[\frac{1-p_{i}}{1-q_{i}}\right]^{|S|}\left[\frac{p_{i}(1-q_{i})}{q_{i}(1-p_{i})}\right]^{|A_{i}\cap
S|}$

Thus the log-likelihood reads:

$\displaystyle l(S)$ $\displaystyle=\sum_{a_{j}\in
S}\ln\frac{t_{j}}{1-t_{j}}+\sum_{i=1}^{n}|S|\ln\frac{1-p_{i}}{1-q_{i}}+|A_{i}\cap
S|\ln\frac{p_{i}(1-q_{i})}{q_{i}(1-p_{i})}$ $\displaystyle=\sum_{a_{j}\in
S}\left[\overbrace{\underbrace{\ln\frac{t_{j}}{1-t_{j}}+\sum_{i:a_{j}\in
A_{i}}\ln\frac{p_{i}(1-q_{i})}{q_{i}(1-p_{i})}}_{app_{w}(a_{j})}-\underbrace{\sum_{i=1}^{n}\ln\frac{1-q_{i}}{1-p_{i}}}_{\tau_{n}}}^{l(a_{j})}\right]$

This means that $a\in S_{max}^{\tau_{n}}$ if and only if $l(a)>0$ , $a\in
S_{min}^{\tau_{n}}$ if and only if $l(a)<0$ and $a\in S_{tie}^{\tau_{n}}$ if
and only if $l(a)=0$. Now, let $S_{M}$ be a maximizer of the likelihood. Since
$l(a_{j})\geq l(a_{h})\iff app_{w}(a_{j})\geq app_{w}(a_{h})$ we have that
$S_{M}$, which maximizes $\sum_{a_{j}\in S}l(a_{j})$, is made of top-$k$
alternatives for some $k\in[l\mathinner{\ldotp\ldotp}u]$.

Furthermore, $|S_{M}\cap
S_{min}^{\tau_{n}}|=\max(0,l-k_{tie}^{\tau_{n}}-k_{max}^{\tau_{n}})$. Start by
noticing that $|S_{M}\cap
S_{min}^{\tau_{n}}|\geq\max(0,l-k_{tie}^{\tau_{n}}-k_{max}^{\tau_{n}})$, since
$|S_{M}\cap S_{min}^{\tau_{n}}|\geq l-|S_{M}\cap
S_{max}^{\tau_{n}}|-|S_{M}\cap S_{tie}^{\tau_{n}}|\geq
l-k_{max}^{\tau_{n}}-k_{tie}^{\tau_{n}}$. Suppose that $|S_{M}\cap
S_{min}^{\tau_{n}}|>\max(0,l-k_{tie}^{\tau_{n}}-k_{max}^{\tau_{n}})$. Then we
have that $|S_{M}|>l$ because otherwise, if $|S_{M}|=l$, then $|S_{M}\cap
S_{max}^{\tau_{n}}|+|S_{M}\cap S_{tie}^{\tau_{n}}|=l-|S_{M}\cap
S_{min}^{\tau_{n}}|<k_{max}^{\tau_{n}}+k_{tie}^{\tau_{n}}$, which would mean
that there are elements in $S_{tie}^{\tau_{n}}$ and $S_{max}^{\tau_{n}}$ which
are not in $S_{M}$, which is a contradiction since $|S_{M}\cap
S_{min}^{\tau_{n}}|>0$ and $S_{M}$ is a top-$k$ set. Now consider $a\in
S_{M}\cap S_{min}^{\tau_{n}}$, we have that $|S_{M}\backslash\\{a\\}|\geq l$
and $l(S_{M})=l(S_{M}\backslash\\{a\\})+l(a)<l(S_{M}\backslash\\{a\\})$ which
is a contradiction.

With the same idea we can prove that $|S_{M}\cap
S_{max}^{\tau_{n}}|=\min(u,k_{max}^{\tau_{n}})$.

Conversely, consider an admissible set $S$ of top-$k$ alternatives that
verifies the constraints (1). Let $S_{M}$ be a MLE which, by the first part of
the proof, is a top-$k^{\prime}$ set that also satisfies the same constraints
(1). Thus we have that $|S_{M}\cap S_{max}^{\tau_{n}}|=|S\cap
S_{max}^{\tau_{n}}|=\min(u,k_{max}^{\tau_{n}})$, and since $S$ and $S_{M}$ are
top-$k$ and top-$k^{\prime}$ sets, we have that $S\cap
S_{max}^{\tau_{n}}=S_{M}\cap S_{max}^{\tau_{n}}$. Similarly we have that
$S\cap S_{min}^{\tau_{n}}=S_{M}\cap S_{min}^{\tau_{n}}$. This suffices to
prove that $l(S)=l(S_{M})$ is maximal. ∎

Notice that when $(l,u)=(0,m)$, the problem degenerates into a collection of
label-wise problems, one for each alternative: $a_{j}$ is selected if
$a_{j}\in S_{max}^{\tau_{n}}$, rejected if $a_{j}\in S_{min}^{\tau_{n}}$, and
those that are on the fence can be arbitrarily selected or not.

######  Example 1.

Consider $5$ alternatives $\mathcal{A}=\\{a,b,c,d,e\\}$ and $10$ voters
$\mathcal{N}$ all sharing the same parameters $(p,q)=(0.7,0.4)$. We thus have
that all voters share the same weight
$w=ln\left(\frac{p(1-q)}{q(1-p)}\right)=1.25$ and
$\tau_{n}=\sum_{i=1}^{n}ln\left(\frac{1-q}{1-p}\right)=6.93$. We consider the
constraints $(l,u)=(1,4)$

First, suppose that $t_{d}=0.6$ and that $t_{j}=0.5$ for all the remaining
candidates. Consider also the approval counts (and weighted approval scores)
in the table below.

Candidate | a | b | c | d | e
---|---|---|---|---|---
Approval count | 9 | 8 | 7 | 5 | 5
$app_{w}$ | 11.25 | 10 | 8.75 | 6.65 | 6.25

We can easily check, by Theorem 1 that
$\tilde{S}=\operatorname*{arg\,max}_{S\in\mathcal{S}}P(S=S^{*}|A)=\\{a,b,c\\}$.
We have that $S_{max}^{\tau_{n}}=\\{a,b,c\\},S_{tie}^{\tau_{n}}=\emptyset$ and
$S_{min}^{\tau_{n}}=\\{d,e\\}$. We know that there exists some $k\in[1,4]$
such that $\tilde{S}$ would consist of the top $k$ alternatives. We also have
that:

$\left\\{\begin{array}[]{cl}|\tilde{S}\cap
S_{max}^{\tau_{n}}|&=\min(u,k_{max}^{\tau_{n}})=3\implies\\{a,b,c\\}\subseteq\tilde{S}\\\
|\tilde{S}\cap
S_{min}^{\tau_{n}}|&=\max(0,l-k_{tie}^{\tau_{n}}-k_{max}^{\tau_{n}})=0\implies
d,e\notin\tilde{S}\end{array}\right.$

So the only possibility is $\tilde{S}=\\{a,b,c\\}$.

###  4.2 Estimating the Parameters Given the Ground Truth

####  4.2.1 Estimating the prior parameters over alternatives

Once the ground truths are estimated at one iteration of the algorithm, the
next step consists in estimating the prior parameters
$(t_{j})_{j\in\mathcal{A}}$, with the ground truths being given (in Subsection
4.3 the ground truth will be replaced by its estimation at each iteration).
The next proposition explicits the closed-form expression of the MLE of the
prior parameter of each alternative given the ground truth of each instance
$S^{*}_{z}$ once the prior parameters of all other alternatives are fixed.

  * •

Input: Approval profile $(A_{1},\dots,A_{n})$, ground truths $S^{*}_{z}$, and
all but one prior parameters $(t_{h})_{h\neq j}$.

  * •

Output: MLE of $t_{j}$.

######  Proposition 2.

For every $a_{j}\in\mathcal{A}$:

$\operatorname*{arg\,max}_{t\in(0,1)}\mathcal{L}(A,S,p,q,t,t_{-j})=\frac{occ(j)\overline{\alpha}_{j}}{(L-occ(j))\underline{\alpha}_{j}+occ(j)\overline{\alpha}_{j}}$
$\mbox{where:
}\left\\{\begin{array}[]{lll}\overline{\alpha}_{j}&=\sum\limits_{\begin{subarray}{c}S\in\mathcal{S}_{l,u}\\\
a_{j}\in S\end{subarray}}\prod\limits_{\begin{subarray}{c}a_{h}\in S\\\ h\neq
j\end{subarray}}t_{h}\prod\limits_{a_{h}\notin S}(1-t_{h})\\\
\underline{\alpha}_{j}&=\sum\limits_{\begin{subarray}{c}S\in\mathcal{S}_{l,u}\\\
a_{j}\notin S\end{subarray}}\prod\limits_{a_{h}\in
S}t_{h}\prod\limits_{\begin{subarray}{c}a_{h}\notin S\\\ h\neq
j\end{subarray}}(1-t_{h})\\\ occ(j)&=\left|z\in\\{1,\dots,L\\},a_{j}\in
S_{z}\right|\end{array}\right.$

Notice that $\overline{\alpha}_{j}=P(l\leq|S^{*}|\leq u|a_{j}\in S^{*})$ and
$\underline{\alpha}_{j}=P(l\leq|S^{*}|\leq u|a_{j}\notin S^{*})$ so
$\beta=\overline{\alpha}_{j}t_{j}+\underline{\alpha}_{j}(1-t_{j})$. $occ(j)$
is the number of instances whose ground truth contains $a_{j}$.

###### Proof.

Fix all sets $S_{z}\in\mathcal{S}_{l,u}$ and all the noise parameters
$(p_{i},q_{i})_{i}$ and all the prior parameters $t_{h}$ but for one $t_{j}$
for some $j\leq m$, and let $t\in(0,1)$:

$\begin{split}\mathcal{L}(S,t,t_{-j})&\propto\prod_{z=1}^{L}\frac{1}{\beta(l,u,t)}\prod_{a_{h}\in
S_{z}}t_{h}\prod_{a_{h}\notin S_{z}}(1-t_{h})\\\
&\propto\prod_{z=1}^{L}\frac{1}{\beta(l,u,t,t_{-j})}\prod_{a_{h}\in
S_{z}}t_{h}\prod_{a_{h}\notin S_{z}}(1-t_{h})\\\
&\propto\left(\frac{1}{\beta(l,u,t,t_{-j})}\right)^{L}\underbrace{\prod_{z:a_{j}\in
S_{z}}t}_{t^{occ(j)}}\underbrace{\prod_{z:a_{j}\notin
S_{z}}(1-t)}_{(1-t)^{L-occ(j)}}\\\ \end{split}$

Taking the log we can write the function as:

$\ell(t)=-L\log\beta+occ(j)\log t+(L-occ(j))\log(1-t)$

Its derivative reads:

$\frac{\partial l}{\partial
t}=-L\frac{\underline{\alpha}_{j}-\overline{\alpha}_{j}}{\underline{\alpha}_{j}t+\overline{\alpha}_{j}(1-t)}+occ(j)\frac{1}{t}+(occ(j)-L)\frac{1}{1-t}$

Canceling it, we obtain:

${t=\frac{occ(j)\overline{\alpha}_{j}}{(L-occ(j))\underline{\alpha}_{j}+occ(j)\overline{\alpha}_{j}}}$

The derivative vanishes in a single point in $(0,1)$ and $\lim_{t\to
0}\ell(t)$ $=\lim_{t\to 1}\ell(t)=-\infty$ thus $\ell$ reaches a unique
maximum. ∎

We will see later that the algorithm applies Proposition 2 sequentially to
estimate the alternatives’ parameters one by one (see Example 2).

####  4.2.2 Estimating the voter parameters

Once the ground truths are known (or estimated), we can estimate the voters’
parameters $(p,q)$.

  * •

Input: Instances $(A^{1},\dots,A^{L})$, ground truths
$(S^{*}_{1},\dots,S^{*}_{L})$.

  * •

Output: MLE of voter reliabilities $(p,q)$.

The next result simply states that the maximum likelihood estimator of $p_{i}$
of some voter is the fraction of alternatives that the voter approves and that
actually belong to the ground truth; the estimation of $q_{i}$ is similar. See
Example 2.

######  Proposition 3.

Fix sets $S_{z}\in\mathcal{S}_{l,u}$ and prior parameters $t_{j}$. Then:

$\operatorname*{arg\,max}_{(p,q)\in(0,1)^{2n}}\mathcal{L}(A,S,p,q,t)=(\hat{p},\hat{q})$

where: $\hat{p}_{i}=\frac{\sum_{z\in L}|A_{i}^{z}\cap{S}_{z}|}{\sum_{z\in
L}|{S}_{z}|},\hat{q}_{i}=\frac{\sum_{z\in
L}|A_{i}^{z}\cap\overline{{S}_{z}}|}{\sum_{z\in L}|\overline{{S}_{z}}|}$

The (simple) proof is omitted; it is in the Appendix.

###  4.3 Alternating Maximum Likelihood Estimation

Algorithm 1 AMLE procedure

$\begin{array}[]{ll}\textbf{Input:}&\mbox{Approval ballots $(A_{i}^{z})_{1\leq
z\leq L,i\in\mathcal{N}}$}\\\ &\mbox{Initial parameters
$\hat{\theta}^{(0)}$},\mbox{Bounds $(l,u)$},\mbox{Tolerance $\varepsilon$}\\\
\textbf{Output:}&\mbox{Estimations
$(\hat{S}_{z}),(\hat{p}_{i},\hat{q}_{i}),(\hat{t}_{j})$}\end{array}$

repeat

for $z=1\dots L$ do

Compute $\hat{S}_{z}^{(v+1)}=\\{a_{1},\dots,a_{k}\\}$ with $k\in[l,u]$ and:
$\left\\{\begin{array}[]{cl}|\hat{S}_{z}^{(v+1)}\cap
S_{max,z}^{(v)}|&=\min(u,k_{max,z}^{(v)})\\\ |\hat{S}_{z}^{(v+1)}\cap
S_{min,z}^{(v)}|&=\max(0,l-k_{tie,z}^{(v)}-k_{max,z}^{(v)})\end{array}\right.$

end for

for $i=1\dots\mathcal{N}$ do

Update the parameters $(p_{i},q_{i})$ given $\hat{S}^{(v+1)}$:
$\hat{p}_{i}^{(v+1)}=\frac{\sum\limits_{z\in
L}|A_{i}^{z}\cap\hat{S}_{z}^{(v+1)}|}{\sum\limits_{z\in
L}|\hat{S}_{z}^{(v+1)}|},\hat{q}_{i}^{(v+1)}=\frac{\sum\limits_{z\in
L}|A_{i}^{z}\cap\overline{\hat{S}_{z}^{(v+1)}}|}{\sum\limits_{z\in
L}|\overline{\hat{S}_{z}^{(v+1)}}|}$

end for

for $j=1\dots m$ do

Update $\hat{t}_{j}^{(v+1)}$ by:
$\hat{t}_{j}^{(v+1)}=\frac{occ^{(v+1)}(j)\overline{\alpha}_{j}^{(v+1)}}{occ^{(v+1)}(j)\overline{\alpha}_{j}^{(v+1)}+(L-occ^{(v+1)}(j))\underline{\alpha}_{j}^{(v+1)}}$
where :
$\left\\{\begin{array}[]{ll}occ^{(v+1)}(j)&=\sum_{z=1}^{L}\mathds{1}\\{a_{j}\in\hat{S}_{z}^{(v+1)}\\}\\\
\overline{\alpha}_{j}^{(v+1)}&=\beta((l-1)^{+},u-1,\hat{t}^{(v+1)}_{<j},\hat{t}^{(v)}_{>j})\\\
\underline{\alpha}_{j}^{(v+1)}&=\beta(l,u,\hat{t}^{(v+1)}_{<j},\hat{t}^{(v)}_{>j})\end{array}\right.$

end for

until $||\hat{\theta}^{(v+1)}-\hat{\theta}^{(v)}||\leq\varepsilon$

Now the estimation of the ground truths and that of the parameters are
intertwined to maximize the overall likelihood $\mathcal{L}(A,S,p,q,t)$ by the
_Alternating Maximum Likelihood Estimation algorithm_. AMLE is an iterative
procedure similar to the Expectation-Maximization procedure introduced in
Baharad et al. (2011) but with a coordinate-steepest-ascent-like iteration,
whose aim is to intertwinedly estimate the voter reliabilities, the
alternatives’ prior parameters and the instances’ ground truths. The idea
behind this estimation consists in alternating a MLE of the ground truths
given the current estimate of the parameters, and an updating of these
parameters via a MLE based on the current estimate of the ground truths.222In
case of ties between subsets when estimating the ground truth, a tie-breaking
priority over subsets is used. No ties occurred in our experiments. Each of
these steps have been discussed in the previous subsections and are now
incorporated into Algo. 1.

The algorithm continues to run until a convergence criterion is met in the
form of a bound on the norm of the change in the parameters’ estimations. In
practice we chose $\ell_{\infty}$, but any other norm could be used in
Algorithm 1 as in finite dimensions, all norms are equivalent (if a sequence
converges according to one norm then it does so for any norm).

We define the vector of parameters
$\hat{\theta}^{(v)}=(\hat{p}^{(v)},\hat{q}^{(v)},\hat{t}^{(v)})$ containing
the voters’ estimated noise parameters as well as the prior information
estimated parameters at iteration $v$. In particular $\hat{\theta}^{(0)}$ is
the input initial values. The choice of the exact initial values depends on
the application at hand.

Note that at convergence, only local optimality is guaranteed, as classical in
optimization.

######  Theorem 4.

For any initial values $\hat{\theta}^{(0)}$, AMLE converges to a fixed point
after a finite number of iterations.

###### Proof.

First we have by Theorem 1 that
$\mathcal{L}(A,\hat{S}^{(v+1)},\hat{\theta}^{(v)})=\max_{S\in\mathcal{S}}\mathcal{L}(A,S,\hat{\theta}^{(v)})$,
and we have in particular that:

$\mathcal{L}(A,\hat{S}^{(v+1)},\hat{\theta}^{(v)})\geq\mathcal{L}(A,\hat{S}^{(v)},\hat{\theta}^{(v)})$

To prove that
$\mathcal{L}(A,\hat{S}^{(v+1)},\hat{\theta}^{(v+1)})\geq\mathcal{L}(A,\hat{S}^{(v+1)},\hat{\theta}^{(v)})$
we use the fact that we update $(p,q,t)$ by their MLE. By Proposition 3 we
have that
$(\hat{p}^{(v+1)},\hat{q}^{(v+1)})=\operatorname*{arg\,max}_{(p,q)}\mathcal{L}(A,\hat{S}^{(v+1)},p,q,\hat{t}^{(v)})$.
Also by Proposition 2, and since we apply it sequentially to update $t_{j}$ we
have:

$\mathcal{L}(A,\hat{S}^{(v+1)},\hat{\theta}^{(v+1)})\geq\mathcal{L}(A,\hat{S}^{(v+1)},\hat{\theta}^{(v)})$

To prove convergence, it suffices to show that $\hat{S}^{(v)}=\hat{S}^{(v+1)}$
for some $v$ (which guarantees the estimators staying unchanged hereafter).
Notice that the ground truth has a finite number of possible values (exactly
$2^{mL}$), leading the algorithm to cycle at some iteration. For the sake of
simplicity, suppose that this cycle is of length $2$, in other words, suppose
that $\hat{S}^{(v+2)}=\hat{S}^{(v)}$ for some $v$; this also implies that
$\hat{\theta}^{(v+2)}=\hat{\theta}^{(v)}$. So:

$\mathcal{L}(A,\hat{S}^{(v)},\hat{\theta}^{(v)})=\mathcal{L}(A,\hat{S}^{(v+2)},\hat{\theta}^{(v+2)})\geq\mathcal{L}(A,\hat{S}^{(v+1)},\hat{\theta}^{(v)})$

By optimality of $\hat{S}^{(v+1)}$, we have also that:

$\mathcal{L}(A,\hat{S}^{(v+1)},\hat{\theta}^{(v)})\geq\mathcal{L}(A,\hat{S}^{(v)},\hat{\theta}^{(v)})$

Hence, we get that:

$\mathcal{L}(A,\hat{S}^{(v+1)},\hat{\theta}^{(v)})=\mathcal{L}(A,\hat{S}^{(v)},\hat{\theta}^{(v)})$

and thus,
$\hat{S}^{(v+1)}=\hat{S}^{(v)}=\operatorname*{arg\,max}_{S\in\mathcal{S}_{l,u}}\mathcal{L}(A,S,\hat{\theta}^{(v)})$
and the estimators will remain the same after any number of iterations
following $v$. ∎

Because
$\mathcal{L}(A,\hat{S}^{(v+1)},\hat{\theta}^{(v+1)})\geq\mathcal{L}(A,\hat{S}^{(v+1)},\hat{\theta}^{(v)})\geq\mathcal{L}(A,\hat{S}^{(v)},\hat{\theta}^{(v)})$,
the likelihood increases at each step of the algorithm. This guarantees that
whenever the execution stops, the likelihood is closer to the maximum than it
initially was. Therefore the algorithm can not only be run until convergence,
but it can also be run as an anytime algorithm.

######  Example 2.

Take $n=3$, $m=5$, $l=1$, $u=2$, $L=4$, and the following profile and initial
parameters:

| $A^{1}$ | $A^{2}$ | $A^{3}$ | $A^{4}$
---|---|---|---|---
Voter $1$ | $\\{a_{1},a_{4}\\}$ | $\\{a_{1}\\}$ | $\\{a_{3}\\}$ | $\\{a_{1}\\}$
Voter $2$ | $\\{a_{2}\\}$ | $\\{a_{5}\\}$ | $\\{a_{4}\\}$ | $\\{a_{1}\\}$
Voter $3$ | $\\{a_{2},a_{3},a_{4}\\}$ | $\\{a_{2},a_{3},a_{5}\\}$ | $\\{a_{2},a_{3}\\}$ | $\\{a_{3}\\}$

$\left\\{\begin{array}[]{lll}\hat{p}_{1}^{(0)}=0.5&\hat{p}_{2}^{(0)}=0.5&\hat{p}_{3}^{(0)}=0.5\\\
\hat{q}_{1}^{(0)}=0.44&\hat{q}_{2}^{(0)}=0.41&\hat{q}_{3}^{(0)}=0.32\\\
\hat{t}_{1}^{(0)}=\dots=\hat{t}_{5}^{(0)}&=0.5\end{array}\right.$

##### Estimating the ground truth:

The first step is the application of Theorem 1 to estimate the ground truth of
the instances given the initial parameters, yielding
${\hat{S}_{1}^{(1)}=\\{a_{2},a_{4}\\},\hat{S}_{2}^{(1)}=\\{a_{2},a_{5}\\},\hat{S}_{3}^{(1)}=\\{a_{2},a_{3}\\},\hat{S}_{4}^{(1)}=\\{a_{1},a_{3}\\}}$.

##### Estimating the voter reliabilities:

In the next step we use these estimates of the ground truths to compute the
MLEs of the voter reliabilities. For instance, voter $1$ has 2 false positive
labels from a total of $12$ negative labels so
$\hat{q}_{1}^{(1)}=\frac{2}{12}=0.17$ and she has 3 true positive labels out
of 8 positive ones so $\hat{p}_{1}^{(1)}=\frac{3}{8}=0.38$. In the end, we
get:

$\left\\{\begin{array}[]{lll}\hat{p}_{1}^{(1)}=0.38&\hat{p}_{2}^{(1)}=0.38&\hat{p}_{3}^{(1)}=0.88\\\
\hat{q}_{1}^{(1)}=0.17&\hat{q}_{2}^{(1)}=0.08&\hat{q}_{3}^{(1)}=0.17\end{array}\right.$

##### Estimating the prior parameters:

The final step of this iteration consists in updating the estimations of the
prior parameters by applying Proposition 2 sequentially. First we estimate
$\hat{t}_{1}^{(1)}$ given $\hat{S}^{(1)}$ and
$\hat{t}_{2}^{(0)},\dots,\hat{t}_{5}^{(0)}$ by maximum likelihood estimation.
We first compute $\overline{\alpha}_{1}$, $\underline{\alpha}_{1}$ and
$occ(a_{1})$:

$\left\\{\begin{array}[]{ll}\overline{\alpha}_{1}&=\beta(0,1,t_{2},\dots,t_{5})=0.3125\\\
\underline{\alpha}_{1}&=\beta(1,2,t_{2},\dots,t_{5})=1\\\
occ(a_{1})&=1\end{array}\right.$

Then the maximum likelihood estimation of $t_{1}$ is:

$\hat{t}_{1}=\frac{occ(a_{1})\overline{\alpha}_{1}}{(L-occ(a_{1}))\underline{\alpha}_{1}+occ(a_{1})\overline{\alpha}_{1}}=0.09$

The next steps are to estimate $\hat{t}_{2}^{(1)}$ given
$\hat{t}_{1}^{(1)},\hat{t}_{3}^{(0)},\hat{t}_{4}^{(0)},\hat{t}_{5}^{(0)}$ and
so on. Finally, we get:

$\hat{t}_{1}^{(1)}=0.09,\hat{t}_{2}^{(1)}=0.56,\hat{t}_{3}^{(1)}=0.28,\hat{t}_{4}^{(1)}=0.14,\hat{t}_{5}^{(1)}=0.20$

Fix $\varepsilon=10^{-5}$. We repeat all steps until convergence (according to
$\ell_{\infty}$), after $5$ full iterations. In the fixed point, the
estimations of the ground truths are:

$\hat{S}_{1}=\\{a_{2},a_{3}\\},\hat{S}_{2}=\\{a_{2},a_{3}\\},\hat{S}_{3}=\\{a_{2},a_{3}\\},\hat{S}_{4}=\\{a_{3}\\}$

##  5 Experiments

###  5.1 Experiment Design and Data Collection

We designed an image annotation task as a football quiz.333The annotations
dataset and the code are available at:
https://github.com/taharallouche/Football-Quiz-Crowdsourcing. We selected $15$
pictures taken during different matches between two of the following teams:
Real Madrid, Inter Milan, Bayern Munich, Barcelona, Paris Saint-Germain. In
each picture, it may be the case that players from both teams appear, or
players from only one team, therefore $l=1$ and $u=2$. Each participant is
shown the instances one by one, and is each time asked to select all the teams
she can spot (see Figure 1). We designed a simple incentive for participants,
consisting in ranking them according to the following principle:

  * •

The participants get one point whenever their answer contains all correct
alternatives for a picture. They are then ranked according to their cumulated
points.

  * •

To break ties, the participant who selected a smaller number of alternatives
overall is ranked first.

We gathered the answers of $76$ participants (only two of them spammed by
simply selecting all the alternatives).

Figure 1: Example of Annotation Task

###  5.2 Anna Karenina’s Initialization

Inspired by the _Anna Karenina Principle_ in Meir et al. (2019), we assign
more weight to voters who are _closer_ to the others on average, initializing
the precision parameters $(p_{i},q_{i})$ accordingly. This suits our context,
where voter competence is highly polarized: some voters are experts and cast
similar answers close to the ground truth, the others are less reliable and
their answers are dispersed among all combinations. Details on the heuristic
are in the Appendix.

###  5.3 Results

To assess the importance of prior information on the size of the ground truth,
we tested the AMLE algorithm with free bounds $(l,u)=(0,m)$ (will be referred
to as $\mbox{AMLE}_{f}$) and the $\mbox{AMLE}_{c}$ algorithm with
$(l,u)=(1,2)$. We also apply the modal rule Caragiannis et al. (2020) which
outputs the subset of alternatives that most frequently appears as an approval
ballot
$\operatorname*{arg\,max}_{S\in\mathcal{S}}\left|i\in\mathcal{N},S=A_{i}\right|$,
and a variant of label-wise majority rule which outputs the subset of
alternatives $S$ such that $a\in S\iff\left|i\in\mathcal{N},a\in
A_{i}\right|>\frac{n}{2}$. If this subset is empty it is replaced by the
alternative with highest approval count, and if it has more than two
alternatives then we only keep the top-2 alternatives.

We took $20$ batches of $n=10$ to $n=74$ randomly drawn voters and applied the
four methods to all of them (see Figure 2,2). As classically done in the
literature Nguyen et al. (2020), we use the Hamming accuracy
$\frac{1}{mL}\sum_{z=1}^{L}|S^{*}_{z}\cap\hat{S}^{z}|+|\overline{S^{*}_{z}}\cap\overline{\hat{S}^{z}}|$
and the 0/1 accuracy
$\frac{1}{L}\sum_{z=1}^{L}\mathds{1}\\{S^{*}_{z}=\hat{S}^{z}\\}$ as metrics
and report their 0.95 confidence intervals.

(a) Hamming accuracy

(b) 0/1 accuracy

Figure 2: Accuracies of different aggregation methods

We notice that the majority and the modal rule are outperformed by AMLE, which
can be explained by the fact that they do not take into account the voters’
reliabilities. Comparing the performances of $\mbox{AMLE}_{c}$ and
$\mbox{AMLE}_{f}$ emphasizes the importance of the prior knowledge on the
committee size to improve the quality of the estimation.

##  6 Conclusion

We study multi-winner approval voting from an epistemic point of view. We
propose a noise model that incorporates the prior belief about the size of the
ground truth. Then we derive an iterative algorithm to intertwinedly estimate
the ground truth labels, the voter noise parameters and the prior belief
parameters and we prove its convergence. Our algorithm is based on a
simplification of Expectation-Maximization (EM), and its simple steps are more
easily explainable to voters than EM and other similar statistical learning
approaches.

Although we mainly considered a general multi-instance task that fits the
collective annotation framework, where each voter answers several questions on
the same set of alternatives, we can nonetheless apply the same algorithm to
single-instance problems (such as the allocation of scarce medical resources)
where only one question is answered. In this case, the prior parameters cannot
be updated and it suffices to fix them once and for all and alternate between
the estimation of the ground truth and the voter parameters.

In some contexts (e.g., patients in a hospital), alternatives and votes are
not observed at once but streamed. To cope with this online setup we consider
extending our AMLE algorithm in the spirit of Cappé and Moulines (2009).

## References

  * Allouche et al. [2022] Tahar Allouche, Jérôme Lang, and Florian Yger.  Truth-tracking via approval voting: Size matters.  In AAAI, 2022.
  * Baharad et al. [2011] Eyal Baharad, Jacob Goldberger, Moshe Koppel, and Shmuel Nitzan.  Distilling the wisdom of crowds: weighted aggregation of decisions on multiple issues.  Autonomous Agents and Multi-Agent Systems, 2011.
  * Ben-Yashar and Nitzan [1997] Ruth C. Ben-Yashar and Shmuel I. Nitzan.  The optimal decision rule for fixed-size committees in dichotomous choice situations: The general result.  International Economic Review, 1997.
  * Ben-Yashar and Paroush [2001] Ruth Ben-Yashar and Jacob Paroush.  Optimal decision rules for fixed-size committees in polychotomous choice situations.  Soc. Choice Welf., 18(4):737–746, 2001.
  * Cappé and Moulines [2009] Olivier Cappé and Eric Moulines.  On-line expectation–maximization algorithm for latent data models.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 71(3):593–613, 2009.
  * Caragiannis and Micha [2017] Ioannis Caragiannis and Evi Micha.  Learning a ground truth ranking using noisy approval votes.  In IJCAI, 2017.
  * Caragiannis et al. [2020] Ioannis Caragiannis, Christos Kaklamanis, Nikos Karanikolas, and George A. Krimpas.  Evaluating approval-based multiwinner voting in terms of robustness to noise.  In IJCAI, 2020.
  * Condorcet [1785] Condorcet.  Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix.  1785\.
  * Conitzer and Sandholm [2005] Vincent Conitzer and Tuomas Sandholm.  Common voting rules as maximum likelihood estimators.  In UAI, 2005.
  * Conitzer et al. [2009] Vincent Conitzer, Matthew Rognlie, and Lirong Xia.  Preference functions that score rankings and maximum likelihood estimation.  In IJCAI, 2009.
  * Deng et al. [2014] Jia Deng, Olga Russakovsky, Jonathan Krause, Michael S. Bernstein, Alexander C. Berg, and Fei-Fei Li.  Scalable multi-label annotation.  In CHI Conference on Human Factors in Computing Systems, 2014\.
  * Dietrich [2008] Franz Dietrich.  The premises of condorcet’s jury theorem are not simultaneously justified.  Episteme, 2008.
  * Drissi-Bakhkhat and Truchon [2004] Mohamed Drissi-Bakhkhat and Michel Truchon.  Maximum likelihood approach to vote aggregation with variable probabilities.  Social Choice and Welfare, 2004.
  * Elkind and Slinko [2016] Edith Elkind and Arkadii Slinko.  Rationalizations of voting rules.  In Handbook of Computational Social Choice. 2016.
  * Faliszewski et al. [2017] Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon.  Multiwinner voting: A new challenge for social choice theory.  In Trends in Computational Social Choice. 2017.
  * Kruger et al. [2014] Justin Kruger, Ulle Endriss, Raquel Fernández, and Ciyang Qing.  Axiomatic analysis of aggregation methods for collective annotation.  In AAMAS, 2014.
  * Lackner and Skowron [2020] Martin Lackner and Piotr Skowron.  Approval-based committee voting: Axioms, algorithms, and applications.  CoRR, abs/2007.01795, 2020.
  * Meir et al. [2019] Reshef Meir, Ofra Amir, Gal Cohensius, Omer Ben-Porat, and Lirong Xia.  Truth discovery via proxy voting.  arXiv:1905.00629, 2019.
  * Nguyen et al. [2020] Vu-Linh Nguyen, Eyke Hüllermeier, Michael Rapp, Eneldo Loza Mencía, and Johannes Fürnkranz.  On aggregation in ensembles of multilabel classifiers.  In Discovery Science, 2020.
  * Nitzan and Paroush [2017] Shmuel Nitzan and Jacob Paroush.  Collective decision making and jury theorems.  The Oxford Handbook of Law and Economics, 1, 2017.
  * Nowak and Rüger [2010] Stefanie Nowak and Stefan M. Rüger.  How reliable are annotations via crowdsourcing: a study about inter-annotator agreement for multi-label image annotation.  In MIR, 2010.
  * Pivato [2013] Marcus Pivato.  Voting rules as statistical estimators.  Social Choice and Welfare, 2013.
  * Pivato [2017] Marcus Pivato.  Epistemic democracy with correlated voters.  Journal of Mathematical Economics, 2017.
  * Procaccia and Shah [2015] Ariel D. Procaccia and Nisarg Shah.  Is approval voting optimal given approval votes?  In NIPS, 2015.
  * Procaccia et al. [2012] Ariel D. Procaccia, Sashank Jakkam Reddi, and Nisarg Shah.  A maximum likelihood approach for selecting sets of alternatives.  In UAI, 2012.
  * Qing et al. [2014] Ciyang Qing, Ulle Endriss, Raquel Fernández, and Justin Kruger.  Empirical analysis of aggregation methods for collective annotation.  In COLING, 2014.
  * Shah and Zhou [2020] Nihar B. Shah and Dengyong Zhou.  Approval voting and incentives in crowdsourcing.  ACM Transactions on Economics and Computation, 2020.
  * Shapley and Grofman [1984] Lloyd Shapley and Bernard Grofman.  Optimizing group judgmental accuracy in the presence of interdependencies.  Public Choice, 1984.
  * Xia and Conitzer [2011] Lirong Xia and Vincent Conitzer.  A maximum likelihood approach towards aggregating partial orders.  In IJCAI, 2011.
  * Xia et al. [2010] Lirong Xia, Vincent Conitzer, and Jérôme Lang.  Aggregating preferences in multi-issue domains by using maximum likelihood estimators.  In AAMAS, 2010.
  * Young [1988] H. Peyton Young.  Condorcet’s theory of voting.  American Political science review, 1988.

Appendix

## Data collection and incentives

To see how the participants behave given the ranking incentives that we
defined in the football quiz, we plotted the histogram of the sizes of the
answers (see Figure 3). It appears that although the platform enables to
select every alternative, only two voters did so for all the questions.
Moreover, figures 3(b) and 3(a) show that the majority of the voters tend to
select exactly the number of teams that appear in an image.

(a) Two-winner instances

(b) Single-winner instances

Figure 3: Histogram of the ballots’ sizes

## Initializing Voters’ Reliabilities

Inspired by the _Anna Karenina Principle_ in Meir et al. [2019], we devised an
initialisation strategy for the voters’ reliabilities. In his book, Leo
Tolstoi stated that ”Happy families are all alike; every unhappy family is
unhappy in its own way”. In the same spirit, it seems reasonable to make the
hypothesis that accurate users tend to make similar answers, whereas
inaccurate users have each their own way of being inaccurate.

We use the following heuristic (see Algorithm 2) for the initialization. We
used the Jaccard distance given by:

$d_{Jacc}(A,B)=\frac{|\overline{A}\cap B|+|A\cap\overline{B}|}{|A\cup B|}$

Algorithm 2 Initializing $(p_{i},q_{i})_{i}$

$\begin{array}[]{ll}\textbf{Input:}&\mbox{Approval ballots
$(A_{i}^{z})_{z,i}$}\\\ \textbf{Output:}&\mbox{Initialization
$(\hat{p}^{(0)}_{i},\hat{q}^{(0)}_{i})$}\end{array}$

-Compute $w_{max}=\frac{n}{1+n},w_{min}=\frac{1}{1+n}$

-Compute $d_{i}=\sum_{j\neq i}d_{Jacc}(A_{i},A_{j})$

-Compute $d_{max}=\max d_{i},d_{min}=\min d_{i}$

-Compute $w_{i}=(w_{max}-w_{min})\left(\frac{\frac{1}{d_{i}}-\frac{1}{d_{max}}}{\frac{1}{d_{min}}-\frac{1}{d_{max}}}\right)+w_{min}$

-Fix $\hat{p}^{(0)}_{i}=\frac{1}{2}$ and $\hat{q}^{(0)}_{i}=\frac{1-\frac{e^{w_{i}}-1}{e^{w_{i}}+1}}{2}$

######  Remark.

The formulas in Algorithm 4 guarantee that a voter’s parameters
$(\hat{p}^{(0)}_{i},\hat{q}^{(0)}_{i})$ are such that her initial weight is
equal to $w_{i}$, and that $\frac{w_{max}}{w_{min}}=n$ which means that
initially, the voter closest in average to the other voters counts $n$ times
the voter with biggest average distance.

######  Example 3.

Consider following the approval profile (Table 1) for $3$ voters, $5$
alternatives and $4$ Instances.

| $A^{1}$ | $A^{2}$ | $A^{3}$ | $A^{4}$
---|---|---|---|---
Voter $1$ | $\\{a_{1},a_{4}\\}$ | $\\{a_{1}\\}$ | $\\{a_{3}\\}$ | $\\{a_{1}\\}$
Voter $2$ | $\\{a_{2}\\}$ | $\\{a_{5}\\}$ | $\\{a_{4}\\}$ | $\\{a_{1}\\}$
Voter $3$ | $\\{a_{2},a_{3},a_{4}\\}$ | $\\{a_{2},a_{3},a_{5}\\}$ | $\\{a_{2},a_{3}\\}$ | $\\{a_{3}\\}$
Table 1: Approval Ballots of 3 Voters on 4 Instances

Here we have that:

$w_{max}=\frac{n}{n+1}=0.75,w_{min}=\frac{1}{n+1}=0.25$

First, compute the mean Jaccard distance of all voters:
$d_{1}=1.71,d_{2}=1.69,d_{3}=1.65$. So $d_{max}=d_{1}=1.71$ and
$d_{min}=d_{3}=1.65$, which means that voter $3$ (the closest in average to
all the voters) will get the biggest weight $w_{3}=w_{max}=0.75$ and voter $1$
gets the smallest weight $w_{1}=w_{min}$. Next, compute the weight that will
be assigned to each voter, for instance:

$w_{2}=(w_{max}-w_{min})\frac{\frac{1}{d_{2}}-\frac{1}{d_{max}}}{\frac{1}{d_{min}}-\frac{1}{d_{max}}}+w_{min}=0.38$

Now we can set the initial values for the reliability parameters accordingly:

$\hat{p}^{(0)}_{2}=\frac{1}{2},\hat{q}^{(0)}_{2}=\frac{1-\frac{e^{w_{2}}-1}{e^{w_{2}}+1}}{2}$

We can check that these parameters are such that:

$ln\left[\frac{p_{2}(1-q_{2})}{q_{2}(1-p_{2})}\right]=w_{2}$

After proceeding in the same fashion with all the voters, we get the initial
parameters:

$\left\\{\begin{array}[]{lll}\hat{p}_{1}^{(0)}=0.5&\hat{p}_{2}^{(0)}=0.5&\hat{p}_{3}^{(0)}=0.5\\\
\hat{q}_{1}^{(0)}=0.44&\hat{q}_{2}^{(0)}=0.41&\hat{q}_{3}^{(0)}=0.32\\\
\end{array}\right.$

Since the AMLE only guarantees convergence to a local maximum, which makes the
result depending on the initial point, we compared the results of this
initialization (Anna Karenina) to other procedures to motivate its choice, see
Figure 4, namely we tested:

  * •

Uniform weights: Initially all the voters in the batch are given the same
weight.

  * •

Random weights: Initially, for each voter in the batch, $p_{i}$ is randomly
picked from $(0.5,1)$ and $q_{i}$ is randomly picked from $(0,0.5)$.

We can notice that these two baseline procedures show very similar
performances, and that they are both outperformed by the Anna Karenina
initialization.

(a) 0-1 accuracy

(b) Hamming accuracy

Figure 4: Accuracies of different initializations

## Time Complexity of AMLE

We assessed the execution time of the AMLE algorithm with and without
constraints (refered to as AMLE and AMLEf), run on Intel Core i7-10610U CPU
@1.80Ghz 4 cores, 8 threads and 32Gb RAM. Results are show in Figure 5. We can
see that whereas the number of iteration does not seem to grow as the number
of voter increases, the execution time of AMLE does, especially around $40$
voters.

(a) Execution time of AMLE

(b) Number of iterations of AMLE

Figure 5: Time complexity of AMLE

## Losses

### Hamming, Harmonic and 0-1 Subset Metrics

In addition to the Hamming and 0-1 subset accuracies, we introduced a new
metric which can be considered as an intermediate one. The Hamming metric
considers each label independently and the 0-1 subset loss considers them
jointly in a strict fashion, whereas the harmonic accuracies that we
introduced considers all the instance’s labels jointly but with different
convex weights depending on the number of correctly predicted ones:

$T(S,S^{*})=\sum_{k=1}^{|S\cap S^{*}|}\frac{1}{6-k}$

So out of the 5 labels:

  * •

if 0 labels are correct then $T=0$.

  * •

if 1 labels is correct then $T=\frac{1}{5}$.

  * •

if 2 labels are correct then $T=\frac{1}{5}+\frac{1}{4}$.

  * •

if 3 labels are correct then $T=\frac{1}{5}+\frac{1}{4}+\frac{1}{3}$.

  * •

if 4 labels are correct then
$T=\frac{1}{5}+\frac{1}{4}+\frac{1}{3}+\frac{1}{2}$.

  * •

if 5 labels are correct then
$T=\frac{1}{5}+\frac{1}{4}+\frac{1}{3}+\frac{1}{2}+1$.

Defined as such, this accuracy favours the estimators that are able to
correctly estimate most of the instance’s labels without being as rigid as the
0-1 subset accuracy.

This metric is reminiscent of the Proportional Approval Voting rule for
multiwinner elections, which defines the score of a subset of candidates $W$
for a voter as $1+\frac{1}{2}+\ldots+\frac{1}{j}$, where $j$ is the number of
candidates in $W$ approved by the voter. We could consider more generally a
class of metrics defined by a vector $\vec{w}$, such that
$T(S,S^{*})=w_{|S\cap S^{*}|}$. This class generalizes Hamming, 0-1 and
Harmonic and is reminiscent of the class of Thiele rules (see for instance
Lackner and Skowron [2020] for an extended presentation of multiwinner
approval-based committee rules).

### Results

We show in Table 2 the accuracies of the considered methods when applied to
the entire annotation dataset. In Figure 6 we show the evolution of the
Harmonic accuracies when the number of randomly picked voters in each batch
increase.

| $\mbox{AMLE}_{c}$ | $\mbox{AMLE}_{f}$ | Modal | Majority
---|---|---|---|---
Hamming | 0.88 | 0.86 | 0.84 | 0.80
Harmonic | 0.78 | 0.74 | 0.69 | 0.61
0/1 | 0.60 | 0.53 | 0.46 | 0.26
Table 2: Hamming and 0/1 accuracy for entire dataset Figure 6: Normalized
Harmonic accuracy


# Topological unidirectional guided resonances emerged from interband coupling

Xuefan Yin  Department of Electronic Science and Engineering, Kyoto
University, Kyoto-Daigaku-Katsura, Nishikyo-ku, Kyoto 615-8510, Japan  Takuya
Inoue  Department of Electronic Science and Engineering, Kyoto University,
Kyoto-Daigaku-Katsura, Nishikyo-ku, Kyoto 615-8510, Japan  Chao Peng
<EMAIL_ADDRESS>State Key Laboratory of Advanced Optical Communication
Systems and Networks, School of Electronics, $\&$ Frontiers Science Center for
Nano-optoelectronics, Peking University, Beijing, 100871, China  Peng Cheng
Laboratory, Shenzhen 518055, China  Susumu Noda<EMAIL_ADDRESS>Department of Electronic Science and Engineering, Kyoto University, Kyoto-
Daigaku-Katsura, Nishikyo-ku, Kyoto 615-8510, Japan

###### Abstract

Unidirectional guided resonances (UGRs) are optical modes in photonic crystal
(PhC) slabs that radiate towards one side without the need for mirrors on the
other, represented from a topological perspective by the merged points of
paired, single-sided, half-integer topological charges. In this work, we
report a mechanism to realize UGRs by tuning the interband coupling effect
originating from up-down symmetry breaking. We theoretically demonstrate that
a type of polarization singularity, the circular-polarized states (CPs),
emerge from trivial polarization fields owing to the hybridization of two
unperturbed states. By tuning structural parameters, two half-charges carried
by CPs evolve in momentum space and merge to create UGRs. Our findings show
that UGRs are ubiquitous in PhC slabs, and can systematically be found from
our method, thus paving the way to new possibilities of light manipulation.

††preprint:

Unidirectional emission is of fundamental interest in research fields
including non-Hermitian physics [bergholtz2021exceptional, leykam2017edge,
shen2018topological] and singular optics [dennis2009singular, Soskin_2016,
gbur_singular_2016], and can benefit many realistic applications such as on-
chip lasers [streifer1976analysis1, meier1999laser, imada1999coherent,
Matsubara_GaN_2008, hirose2014watt, yoshida_double-lattice_2019,
sakata_dually_2020, morita2021photonic] and energy-efficient grating couplers
[Wang_compact_slant_grating, Roelkens:07, Mekis_coupler_2011,
markwade_grating_coupler, sun2015single, michaels2018inverse]. While most
existing methods use mirrors made of metals or photonic-bandgap materials
[Roncone93_grating_coupler, Taillaert:04, Zhu:17], or by utilizing the non-
resonant blazing effect [streifer1976analysis2, Miller:97] to forbid the
radiation of light towards unnecessary ports, recent findings of
unidirectional guided resonances (UGRs) [Zhou_2016_single_side,
yin_observation_2020] revealed that an eigenstate itself can radiate towards
only a single side of the photonic crystal (PhC) slab without the need for a
mirror on the other. From the view of topological photonics
[lu_topological_2014, khanikaev_two-dimensional_2017, ozawa_topological_2019,
wang_topological_2020], the UGRs were connected to polarization singularities
[nye1983lines, Flossmann_polarization_2008, thomas_observation_2015,
F_sel_2017, Bliokh_2019, chen2019singularities,
shilei_polarization_singularity_2021, yuri_singularity_review_2021,
wang_polarization_2021, yuri_topological_2021] in momentum space, represented
by topological charges [zhen_topological_2014, bulgakov2017bound,
shilei_observation_2018, alu_experimental_2018, liuwei_global_charge,
zeng_dynamic_2021]: they are the merged $V$ points (vortex center of
polarization fields) from paired $C$ points (circular-polarized states) that
carry the same signed half-integer topological charges on a single side. As
reported, such half-charges can originate from splitting an integer charge
carried by a bound state in the continuum (BIC) [von_neuman_uber_1929,
marinica2008bound, zhen_topological_2014, hsu_bound_2016] as $q=1\rightarrow
1/2+1/2$ [shilei_circular, yin_observation_2020, ye_singular_2020,
yoda_generation_2020], or they can be spawned from “the void” as
$q=0\rightarrow 1/2+(-1/2)$ [zeng_dynamic_2021]. Both cases obey the
conservation law of topological charges [zhen_topological_2014,
hsu_bound_2016, liuwei_global_charge].

From such a topological view, the key to realizing UGRs is to create paired
circular-polarized states (CPs). Although splitting from an integer charge of
a BIC has been shown as a fairly intuitive example, it is still unclear how to
deterministically separate and merge the CPs from the trivial polarization
field, namely the void. Considering that the UGRs intrinsically do not depend
on any symmetry, their realization is a formidable engineering challenge,
especially when no appropriate BICs can be found as a starting point.

Figure 1: UGR raised by interband coupling. a, schematic of a PhC slab, with
slab thickness $h/a=0.48$, radius $r/a=0.238$. b, profiles of TMA
($\varphi_{1}$) and TEC ($\varphi_{2}$) modes. c, band structures of original
resonances $\varphi_{1,2}$ (gray and gray dashed lines) and perturbed
resonances $\varphi_{+,-}$ (yellow and purple lines) along the M-$\Gamma$-X
direction, with a UGR at $(k_{x}=0.063,k_{y}=0)$ in $\varphi_{+}$. d,e,
profiles of $\varphi_{1,2}$ and $\varphi_{+,-}$ at $(k_{x}=0.063,k_{y}=0)$. f,
asymmetric radiation ratio $\eta$ of $\varphi_{+,-}$.

In this letter, we report a mechanism to realize UGRs without the premise of
BICs. Specifically, we find that the interband couplings raised from up-down
mirror symmetry breaking can be utilized as an effective degree of freedom
(DOF) to hybridize the orthogonal bands in an unperturbed system. As a result
of interband coupling, the paired CPs with opposite half-charge of $q=\pm 1/2$
are spawned from the void of $q=0$ and evolve in momentum space by adjusting
the interband coupling strength. In the case of a system also possessing in-
plane mirror symmetry, a pair of mirror-positioned half-charges with the same
sign in single-sided radiation can merge at the high-symmetry lines in
momentum space, thus generating UGRs.

To be more specific, we focus on a two-dimensional (2D) square-latticed PhC
slab with symmetric upper and lower claddings. We break the up-down mirror
symmetry of the PhC slab by isotropically tilting the sidewalls of the air
holes. Consequently, interband coupling occurs between two crossing bands
which are originally orthogonal to each other. When the interband coupling is
strong enough, it could give rise to two perturbed eigenstates with nontrivial
topology upon the radiation: a CP pair with oppositely-signed half-charges. By
tuning the tilting angle, the half-charges continuously move and merge in the
$\Gamma-X$ or $\Gamma-M$ directions, creating multiple UGRs. Our investigation
shows that the UGRs are even more ubiquitous than expected, because band-
crossing and corresponding interband coupling are quite common in PhC slabs
regardless of their specific material and geometry, such as refractive-index
contrast, slab thickness, and hole shape.

We start from a free-standing Si3N4 slab patterned with square-lattice air
holes. The sidewalls of the air holes can be either perfectly vertical or
isotropically tilted, measured by an angle $\theta$ (Fig. 1a). According to
Bloch’s theorem, the eigenstates are in the form of
$U_{x,y,z}=E_{x,y,z}(\bm{r})e^{-i\bm{k}_{\varparallel}\cdot\bm{r}}e^{i\omega
t}$ with in-plane wavevector $\bm{k}_{\varparallel}=(k_{x},k_{y})\beta_{0}$
characterizing $k_{\varparallel}$-momentum space, where $\beta_{0}=2\pi/a$ and
$a$ is the lattice constant. For vertical sidewalls, we focus on the TMA mode
(denoted as $\varphi_{1}$) and TEC mode (denoted as $\varphi_{2}$) around the
2nd-$\Gamma$ point (Fig. 1b). Note that in the band structures (Fig. 1c, gray
lines and gray dashed lines), $\varphi_{1}$ and $\varphi_{2}$ cross at
$(k_{x}=0.064,k_{y}=0)$ and $(k_{x}=0.035,k_{y}=0.035)$, respectively. Due to
the up-down mirror symmetry, both $\varphi_{1}$ and $\varphi_{2}$ are
eigenfunctions of parity operator $\mathbf{\hat{P_{z}}}$, but with opposite
eigenvalues: $\varphi_{1}$ is odd with $\sigma_{z}=-1$; $\varphi_{2}$ is even
with $\sigma_{z}=1$ (Fig. 1c). Therefore, the orthogonality forbids any
interband coupling between them during the band crossing.

Then, we slightly tilt the sidewalls, turning the cylindrical air holes into
truncated cones with $\theta=6^{\circ}$. Owing to up-down mirror symmetry
breaking, $\varphi_{1}$ and $\varphi_{2}$ couple and give rise to two
perturbed eigenstates $\varphi_{+}$ and $\varphi_{-}$
[tanaka_theoretical_2003]. As shown in Fig. 1c, the real parts of their
frequencies cross while imaginary parts anti-cross. As confirmed in Fig. 1e,
$\varphi_{+,-}$ no longer preserve definite $z$-parity, and thus the radiation
becomes up-down asymmetric, characterized by an asymmetric radiation ratio
$\eta=\gamma_{t}/\gamma_{b}$, where $\gamma_{t,b}$ are decay rates towards the
top and bottom. A UGR is found at $(k_{x}=0.063,k_{y}=0)$ upon $\varphi_{+}$
band near one of the crossing points, with an asymmetric ratio of $70$ dB
(Fig. 1h).

To investigate the details of interband coupling, we derive a two-level model
from perturbation theory. Specifically, we start from a up-down symmetric
system, in which $\varphi_{1}$ and $\varphi_{2}$ are two eigenstates of the
unperturbed Hamiltonian
$\hat{\mathbf{H}}_{0}=1/\varepsilon_{0}(x,y)\nabla\times\nabla\times$ with
eigenvalues $\lambda_{1,2}$ (other eigenstates are neglected). With the
tilting, a perturbation $\Delta\hat{\mathbf{H}}$ is added as
$\hat{\mathbf{H}}=\hat{\mathbf{H}}_{0}+\Delta\hat{\mathbf{H}}$. The detailed
formulation of $\hat{\mathbf{H}}$ and $\Delta\hat{\mathbf{H}}$ can be found in
Supplementary Section 1.

Accordingly, the unperturbed eigenstates $\varphi_{1,2}$ can be utilized as a
set of bases of subspace $(\varphi_{1},\varphi_{2})$ to depict the perturbed
Hamiltonian $\hat{\mathbf{H}}$ in a form of a 2$\times$2 matrix:

$\displaystyle\mathcal{H}=\left[\begin{array}[]{cc}\left<\varphi_{1}\mid\Delta\hat{\mathbf{H}}\mid\varphi_{1}\right>+\lambda_{1}&\left<\varphi_{1}\mid\Delta\hat{\mathbf{H}}\mid\varphi_{2}\right>\\\
\left<\varphi_{2}\mid\Delta\hat{\mathbf{H}}\mid\varphi_{1}\right>&\left<\varphi_{2}\mid\Delta\hat{\mathbf{H}}\mid\varphi_{2}\right>+\lambda_{2}\end{array}\right]$
(3)

and the hybrid eigenstates can be written as

$\displaystyle\varphi_{+,-}(\bm{k}_{\varparallel})=a_{+,-}(\bm{k}_{\varparallel})\varphi_{1}(\bm{k}_{\varparallel})+b_{+,-}(\bm{k}_{\varparallel})\varphi_{2}(\bm{k}_{\varparallel})$
(4)

with the superposition coefficients given by the eigenvectors
$[a,b]^{T}_{+,-}$ of $\mathcal{H}$. According to Eq. S6, the perturbation
$\Delta\hat{\mathbf{H}}$ is proportional to the odd function $\tan\theta\cdot
z$, and thus the inner-product terms in matrix $\mathcal{H}$ can be simplified
as:

$\displaystyle\left<\varphi_{j}\mid\Delta\hat{\mathbf{H}}\mid\varphi_{k}\right>\propto\left<\varphi_{j}\mid
z\mid\varphi_{k}\right>\tan\theta=\kappa_{jk}\tan\theta$ (5)

As a result, only the eigenstates with opposite $z$-parity can couple to each
other through the anti-diagonal coupling terms. As illustrated in Fig. 1d,
$\varphi_{1,2}$ fulfill this prerequisite.

Accordingly, the eigenvalues of $\mathcal{H}$ can be derived as:

$\displaystyle\lambda_{+,-}=\frac{\lambda_{1}+\lambda_{2}}{2}\pm\sqrt{\frac{(\lambda_{1}-\lambda_{2})^{2}}{4}+\kappa_{12}\kappa_{21}\tan\theta^{2}}$
(6)

. Obviously, there exists a critical angle $\theta_{c}$ with proper
$\bm{k}_{\varparallel}$ for which
$(\lambda_{1}-\lambda_{2})^{2}/4+\kappa_{12}\kappa_{21}\tan{\theta_{c}}^{2}=0$,
namely at which the complex eigenvalues $\lambda_{+,-}$ are degenerate. Such
points are known as the exceptional points (EPs) [heiss2012physics,
dembowski2001experimental, zhen2015spawning, doppler2016dynamically,
zhou_observation_2018, miri2019exceptional, bergholtz2021exceptional]: the
complex crossing points of eigenvalues in parameter space
$(\theta,\bm{k}_{\varparallel})$. We obtain $\theta_{c}=6.9^{\circ}$ along the
$\Gamma$-$X$ direction ($\bm{k}_{\varparallel}=k_{x}$) for the PhC shown in
Fig. 1. We further plot the complex band structures of $\varphi_{+,-}$ in
parameter space $(\theta,k_{x})$, as presented in Fig. 2a. An isolated EP is
found at $(\theta=6.9^{\circ},k_{x}=0.064)$.

Figure 2: Interband coupling scenario. a, band structures of perturbed
resonances $\varphi_{+,-}$ in parameter space $(\theta,k_{x})$ with $k_{y}$
fixed to zero. Red dot denotes EP. b,c, examples of type-I and type-II
crossings when $\theta=7.5^{\circ}/6.5^{\circ}$.

As marked in Fig. 2a, the critical angle $\theta_{c}$ divides the parameter
space $(\theta,k_{x})$ into two different regions [keck2003unfolding]:

Type-I crossing

for $\theta>\theta_{c}$, the real parts of $\lambda_{+,-}$ anti-cross and the
imaginary parts cross (green region).

Type-II crossing

for $\theta<\theta_{c}$, the real parts of $\lambda_{+,-}$ cross and the
imaginary parts anti-cross (blue region).

By continuously increasing $\theta$ from zero, the crossing type first belongs
to type-II, and then transitions to type-I when passing by the EP at
$\theta_{c}=6.9^{\circ}$. In fact, similar transitions can be found not only
along the $\Gamma$-$X$ direction, but also along arbitrary
$\bm{k}_{\varparallel}$ directions in the Brillouin zone (BZ) due to $C_{4}$
symmetry. In Supplementary Section 2, we present the interband coupling
scenario along $k_{y}=k_{x}/2$ direction as an example, for which the EP
resides at $(\theta_{c}=7.15^{\circ},k_{x}=0.0517)$.

We further elaborate on the possibilities of creating polarization
singularities from interband coupling. Eq. 4 shows that $\varphi_{+,-}$ are
hybridized from $\varphi_{1,2}$. Accordingly, the far-field polarization of
$\varphi_{+,-}$ also correlate to the polarization of $\varphi_{1,2}$ denoted
by $d^{s}_{1,2}=c_{y;1,2}^{s}/c_{x;1,2}^{s}$. Here $c^{s}_{x,y;1,2}$ are the
complex radiation amplitudes of $\varphi_{1,2}$ towards the top and bottom
sides, marked by superscripts $s\in\\{t,b\\}$. From the two-level model, the
polarization of $\varphi_{+,-}$ can be derived as:

$\displaystyle
d^{s}_{+,-}=m^{s}_{+,-}d^{s}_{1}+(1-m^{s}_{+,-})d^{s}_{2},~{}~{}~{}~{}s\in\\{t,b\\}$
(7)

where $m_{+,-}^{s}$ are complex coefficients representing the interband
coupling (a detailed discussion is provided in Supplementary Section 3).
Obviously, the intrinsic radiation characteristics of perturbed eigenstates
$\varphi_{+,-}$ are modified by the interband coupling effect. Once the
polarization $d^{s}_{1,2}$ are linearly independent, polarization
$d^{s}_{+,-}$ can be arbitrary values in principle if appropriate
$m^{s}_{+,-}$ are applied.

Figure 3: CPs carrying half-charges emerged from interband coupling. a,
downward polarization and ellipticity $\rho$ of $\varphi_{1,2}$. b, left
panel: downward polarization and ellipticity of perturbed resonance
$\varphi_{+}$ when $\theta=5.65^{\circ}$, where two CPs (green and orange
circles) with ellipticity of $-1$ emerge. right panels: zoom-in windings of
polarization orientation around the CPs.

Here we focus on a type of polarization singularity: CPs. Without loss of
generality, we focus on the downward radiation of $\varphi_{+}$. The condition
of CP becomes $d^{b}_{+}=m^{b}_{+}(d^{b}_{1}-d^{b}_{2})+d^{b}_{2}=\pm i$.
Clearly, two DOFs are necessary to fulfill this condition. In other words, the
CPs can emerge in 2D parameter space, i.e. 2D $k_{\varparallel}$-momentum
space, by optimizing complex coefficient $m_{+}^{b}$ (which also has 2 DOFs)
from interband coupling even though $d^{b}_{1,2}$ themselves are trivial in
polarization.

We plot the polarization ellipses and ellipticity $\rho$ (colored map)
[Mcmaster1954Polarization] of $d^{b}_{1,2}$ in Fig. 3a, showing that both
$\varphi_{1}$ and $\varphi_{2}$ are independent but near-linearly polarized
with $\rho\approx 0$, namely no polarization singularities such as CPs are
found. Then by tilting the sidewalls, complex coefficient $m^{b}_{+}$ is
induced from interband coupling, modifying the polarization of $\varphi_{+}$.
For a small $\theta$, the coupling strength is not strong enough to create any
CPs from trivial near-linear polarization, which we refer to as the void. When
$\theta$ is increased to $\theta_{v}\sim 5.65^{\circ}$, a pair of CPs emerges
simultaneously at $(k_{x}=0.0554,k_{y}=0.0212)$ and
$(k_{x}=0.0588,k_{y}=0.0159)$ (Fig. 3b). It is noteworthy that the ellipticity
of both CPs are identical as $\rho=-1$ (dark blue), showing that they are both
left-handed CP (LCP).

The windings of polarization orientation [zhen_topological_2014] in the
vicinity of two CPs are plotted in the right panel of Fig. 3b, showing that
the two CPs carry half-charges with opposite polarity ($q=\pm 1/2$). Recalling
the fact that when interband coupling is absent or sufficiently weak,
$\varphi_{+}$ has no polarization singularity ($q=0$), we conclude that the
charge evolves as paired, opposite half-charges ($q=\pm 1/2$) carried by two
LCPs spawned from the void ($q=0$) as $0\rightarrow 1/2+(-1/2)$. Obviously,
such an evolution obeys the conservation law of topological charges.

Next, we investigate how to merge two half-charges to create the UGRs. Before
discussing the details, it is worthwhile to discuss the symmetry of system. As
explained previously, under up-down mirror symmetry breaking, the polarization
singularity of CPs, which appears for downward radiation of $\varphi_{+}$,
cannot coincide at the same $k_{\varparallel}$ point for upward radiation, and
thus we can remain focused on $d_{+}^{b}(k_{\varparallel})$. Owing to $C_{4}$
symmetry, a pair of opposite half-charges in one quadrant of momentum space
would duplicate themselves to the other three quadrants, and evolve together
under the constraint of $C_{4}$ symmetry. Notice that, to create UGRs, two
half-charges with the same sign should be merged, which must come from
different void points. Here, the in-plane mirror symmetries ensures paired
mirror-positioned voids with respect to high-symmetry lines, providing the
same signed half-charges pairs.

The detailed charge evolution of $d_{+}^{b}$ is illustrated in Fig. 4a. Here
we plot the right-half of momentum space. Owing to $y$-mirror symmetry, two
pairs of CPs are spawned from two mirror-positioned voids when
$\theta>\theta_{v}=5.65^{\circ}$, and start to evolve from
$(k_{x}=0.057,k_{y}=\pm 0.0186)$ (marked by stars), respectively. The CPs
spawned from the same void have the same helicity but carry opposite half-
charges. Recall that as a type of topological invariant, half-charges are
robust in momentum space. By further increasing $\theta$, the negative half-
charges ($q=-1/2$) depart towards the far-end of the $\pm k_{y}$ directions,
respectively (green lines), while the positive half-charges ($q=+1/2$) which
originate from two different voids move towards each other (orange lines). At
$\theta=6^{\circ}$, the two positive half-charges meet on the $k_{x}$ axis at
$(k_{x}=0.063,k_{y}=0)$, and merge into an integer topological charge as
$1/2+1/2\rightarrow+1$ (red U marker). Consequently, the downward radiation of
$\varphi_{+}$ is completely forbidden and an upward radiating UGR emerges. For
$\theta$ exceeding $6^{\circ}$, the integer charge $q=+1$ splits again into a
pair of half-charges as $+1\rightarrow 1/2+1/2$. Then, the half-charges depart
away from each other and the UGR disappears.

The map of asymmetric ratio $\eta$ for the UGR in $d_{+}^{b}$ is plotted in
Fig. 4b. The ratio reaches $70$ dB at $(k_{x}=0.063,k_{y}=0)$, which confirms
the existence of UGR. As shown in the inset of Fig. 4b, a vortex is clearly
observed in the polarization orientation fields of downward radiation, giving
rise to an integer topological charge of $q=+1$ as expected.

Figure 4: UGRs emerged from interband coupling. a, Evolution of half-charges
in $d_{+}^{b}$ in right half of momentum space when $\theta$ is varied. b,
Asymmetric radiation ratio (map) and the polarization orientation (arrows)
around the UGR. c, Asymmetric radiation ratio (map) and the polarization
orientation (arrows) in a quarter of momentum space. Inset: charge
configuration in whole momentum space.

The role of in-plane mirror symmetry in creating UGRs is clearly shown in Fig.
4a: the trajectories of half-charges spawned from two mirror-positioned voids
are symmetric with respect to the $k_{x}$ axis, protected by $y$-mirror
symmetry. Therefore, two positive half-charges steadily evolve toward each
other and then merge at the $k_{x}$ axis, creating UGRs along the $\Gamma-X$
direction. Similarly, $x$-mirror symmetry protects the trajectories with
respect to the $k_{y}$ axis, leading to the creation of UGRs along the
$\Gamma-Y$ direction (Fig. 4c). Owing to $C_{4}$ symmetry, the $\Gamma-X$ and
$\Gamma-Y$ directions are equivalent, and 4 UGRs emerge simultaneously in
total as shown in the inset of Fig. 4c.

Besides the $\Gamma-X$ and $\Gamma-Y$ directions, $\Gamma-M$ directions are
also high-symmetry lines owing to $C_{4}$ symmetry, and thus the UGRs can be
similarly found from merging two positive half-charges spawned from paired
mirror-positioned voids with respect to the $\Gamma-M$ axes. However, recall
the fact that the UGR in $\varphi_{+}$ is a result by hybridizing
$\varphi_{1}$ and $\varphi_{2}$. As shown in Fig. 1c, although the dispersion
of $\varphi_{1}$ is fairly isotropic with respect to BZ center, the dispersion
of $\varphi_{2}$ is considerably anisotropic. As a result, the condition of
realizing UGRs in the $\Gamma-X$ and $\Gamma-M$ directions could be slightly
different with respect to $\theta$. In other words, when two positive half-
charges merge in the $\Gamma-X$ direction, another pair of positive half-
charges are close to but do not exactly arrive at the high-symmetry line in
the $\Gamma-M$ direction (Fig. S3a). Consequently, the asymmetric radiation
ratio is high but not infinite (Fig. S3b). We refer this kind of state as a
“quasi-UGR”. A more detailed discussion can be found in Supplementary Section
4.

As shown in Fig. 4c, the UGRs emerge in the $\Gamma-X$ direction at
$\theta=6^{\circ}$ with $\eta=70$ dB. For the same parameters, the highest
asymmetric radiation ratio in the $\Gamma-M$ direction is $\eta=25.8$ dB (Fig.
S3b). As illustrated by the topological charge configuration (inset, Fig. 4c),
there exist 1 BIC ($\Gamma$), 4 UGRs ($\Gamma$-$X$,$Y$), and 4 quasi-UGRs
($\Gamma$-$M$) in the BZ. Moreover, a high-asymmetric-radiation ring (colored
map, Fig. 4c) emerges that connects those UGRs and quasi-UGRs.

It is noteworthy that $C_{4}$ symmetry is crucial for multiple UGRs, but it is
not necessary for creating UGRs in general. In Supplementary Section 5, we
reduce the in-plane symmetry from $C_{4}$ to $y$-mirror only, by changing the
circular air holes to triangular ones (Fig. S5). As a result, a single
isolated UGR is found at the $k_{x}$ axis of $(k_{x}=0.04,k_{y}=0)$ with
$\eta=68.3$ dB.

Until now, we have focused on the TMA and TEC modes as unperturbed bases
$(\varphi_{1},\varphi_{2})$ as shown in Fig. 1, and the band-crossing belongs
to type-II when UGRs appear at $\theta=6^{\circ}$. Given that any two modes
with opposite $z$-parity are possible to couple, we turn to investigate
another set of unperturbed bases, namely TMC mode (denoted as $\varphi_{1}$)
and TED mode (denoted as $\varphi_{2}$) near the 2nd-$\Gamma$ point (left
panel, Fig. 5a). It is readily confirmed that these modes fulfill the parity
requirement of interband coupling.

Specifically, at a tilting angle of $\theta=1.72^{\circ}$, type-I crossing can
be identified from the complex band structures of Fig. 5a. An upward radiating
UGR can be found upon the hybrid eigenstate $\varphi_{+}$ at
$(k_{x}=0.0172,k_{y}=0)$. The asymmetric radiation ratio $\eta$ and charge
configuration are presented in Fig. 5b. Clearly, 4 UGRs (red U markers) co-
exist in the $\Gamma-X$ and $\Gamma-Y$ directions with $\eta$ exceeding $70$
dB, and together they form a high-asymmetric-radiation ring (upper panel of
Fig. 5b). Further, we calculate the electric field profiles of two UGRs
residing on the $+k_{x}$ and $+k_{y}$ axes (blue and green boxes in the lower
panel of Fig. 5b) and plot them in Fig. 5c. Such UGRs are either $y$\- or
$x$-polarized, correspondingly.

Protected by in-plane mirror symmetry, the UGRs can robustly exist and
continuously evolve along the high-symmetry lines [yin_observation_2020]
(detailed discussions are provided in Supplementary Section 6). For instance,
by tuning the slab thickness $h$ and hole radius $r$ while fixing the tilting
angle $\theta=1.72^{\circ}$, the 4 off-$\Gamma$ UGRs in Fig. 5b move towards
the BZ center in an isotropic manner. With $h/a\to 0.665$ and $r/a\to 0.217$,
the UGRs merge at the $\Gamma$ point, and the high-asymmetric-radiation ring
shrinks into a point, as shown in Fig. 5d. As a result, the unidirectional
radiation becomes vertical for both $E_{x}$ and $E_{y}$ components (Fig. 5d).

Figure 5: Merging UGRs. a, left panels: profiles of TMC ($\varphi_{1}$) and
TEC ($\varphi_{2}$) modes. right panels: band structures of original
resonances $\varphi_{1,2}$ (gray and gray dashed lines) and perturbed
resonances $\varphi_{+,-}$ (yellow and purple lines), with a UGR at
$(k_{x}=0.0172,k_{y}=0)$ in $\varphi_{+}$ when $h/a=0.65$, $r/a=0.219$ and
$\theta=1.72^{\circ}$. b, asymmetric radiation ratio and charge configuration
of $\varphi_{+}$. c, profiles of UGRs in $\varphi_{+}$ at
$(k_{x}=0.0172,k_{y}=0)$ (blue box) and $(k_{x}=0,k_{=}0.0172)$ (green box),
respectively. d,e, asymmetric radiation ratio, charge configuration and
profiles of merging UGRs in $\varphi_{+}$ at $\Gamma$ point.

It is noteworthy that, although the UGRs raised from interband coupling
involve two unperturbed eigenstates, their unidirectional emission behavior is
an intrinsic characteristics of one perturbed eigenstate, which does not
originate from the interference between two independently excited resonances
[suh2004temporal, chang2012high]. Furthermore, since the UGRs selectively
close one of the radiation channels, they exhibit interesting and abnormal
phenomena under external excitation [Zhang_observation_2021], leading to
various applications for light manipulation.

In conclusion, we have proposed a systematic method to realize UGRs in PhC
slab by coupling two unperturbed eigenstates from up-down mirror symmetry
breaking. We find that the CPs carrying paired, opposite-signed topological
half-integer charges are spawned from the void through interband coupling and
can be controlled to merge only at one side of PhC slab, thus creating a UGR.
Our findings shed light upon new possibilities for creating and utilizing
polarization singularities in momentum space, providing a vivid picture for
manipulating the optical radiation [Yin_pr_2020] in various applications such
as light trapping [jin_topologically_2019, Kang_off_Gamma_merging_2021,
CHEN2021], generation of vortex beams [shen_optical_2019,
huang_ultrafast_2020, yang_spin-momentum-locked_2020, wang_generating_2020,
zhang_tunable_2020] and polarization conversion [guo2017topologically].

###### Acknowledgements.

The authors are grateful to Prof. B.S. Song, Dr. J. Gelleta, Dr. Z. Zhang and
Dr. Y. Hu for helpful discussions. This work was partially supported by Grant-
in-Aid for JSPS Research Fellow (21F20356). C. Peng was supported from
National Natural Science Foundation of China (61922004 and 62135001), National
Key Research and Development Program of China (2020YFB1806405) and Major Key
Project of PCL (PCL2021A04 and PCL2021A14). X. Yin was supported by Research
Fellowships of the Japan Society for Promotion of Science.