Approval voting, Median voting and $L^p$-deepest voting

Léo Dort, Jean-Baptiste Aubin, Irène Gannaz, Samuela Leoni, Antoine Rolland

► To cite this version:

Léo Dort, Jean-Baptiste Aubin, Irène Gannaz, Samuela Leoni, Antoine Rolland. Approval voting, Median voting and $L^p$-deepest voting. 2025. hal-05039251

HAL Id: hal-05039251

https://hal.science/hal-05039251v1

Preprint submitted on 18 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Approval voting, Median voting and $L^p$-deepest voting

by

Léo Dort, Jean-Baptiste Aubin, Irène Gannaz, Samuela Leoni & Antoine Rolland

**Abstract** — We consider $L^p$-deepest voting process bases on 0-1 grades. We show that depending on the value of p, it corresponds to known voting procedures : approval voting if $p \in ]1, \infty[$ and median voting if $p \in ]0, 1]$. It is also shown that the extreme case $p = \infty$ corresponds to unanimity voting.

**Keywords:** Approval voting, Median voting, Deepest voting, Weighted $L^p$-depth functions.

<figure><img src="image_2.png" /><figcaption>**Figure 1** — Trajectories of centers of $L^p$-depths in case of approval voting for $n = 20$ voters and 2 candidates. Each axes corresponds to the grades of each candidate. Each curve gives to the deepest points for a fixed grading matrix, obtained with weighted $L^p$ depths, with a varying value of p, $p > 1$. The two plot display the same graph, with different colors. On the left, the colour corresponds to the value of p. On the right, the color is given by the difference of approvals given to candidate 1 ($n_1$) and candidate 2 ($n_2$). The graph on the right shows that the winner (when it exists) in the approval voting is the winner given by the $L^p$-deepest voting, since the deepest points are in the diagonal triangle where the highest coordinate corresponds to the candidate with the highest number of grades 1.</figcaption></figure>
As an alternative to voting processes based on ranking, grading-based votes offer a more refine way to express preferences. These voting processes encompass the methods of majority judgment (Balinski and Laraki, 2007), range voting (Smith, 2000), and approval voting (Brams and Fishburn, 2007), the three most common voting techniques based on evaluations.

Aubin et al. (2022) provided a unified framework for grading-based voting processes. This family of social choice decision is based on the notions of statistical depth functions, provides center-outward ordering of a scatter plot, and their related deepest point. The idea is to represent the voters as points in $\mathbb{R}^d$, whose coordinates are the grades given by voter v for each of the d candidates. The winner of the election is then defined as the preferred candidate of the deepest point (voter) of the scatter plot. The deepest point is obtained by the maximization of a depth function.

In this paper, we focus on the case where the grades are only 0 or 1. In this context, we show that a specific weighted $L^p$-deepest voting procedure gives the same (set of) winner(s) as approval voting or median judgement depending on whether p is lower or higher than 1, whatever the number of candidates and numbers of voters.

**Notations.** Let consider in the following n voters, $v_1, \dots, v_n$, and d candidates, $c_1, \dots, c_d$. Each voter $v_j$ gives a grade to each candidate $c_i$. We denote $\Phi_n(i, j)$ the corresponding grade. Let $\Lambda$ be the set of all possible grades $\Phi_n(i, j)$. Without loss of generality, we suppose that these grades are in $\Lambda \subseteq [0, 1]$. The grading is summarized in a $d \times n$ grading matrix $\Phi_n = \{\Phi_n(i, j), i = 1, \dots, d, j = 1, \dots, n\} \in \Lambda^{d \times n}$. Any collection of d grades is called a *profile*. A grading-based voting process is then a function G, called *method of grading* in Balinski and Laraki (2007), assigning a profile to any matrix $\Phi_n$. The function G is defined from $\Lambda^{d \times n}$ with values in the subsets of $[0, 1]^d$. The approval voting corresponds to the special case $\Lambda = \{0, 1\}$.

Let us now focus on the context of 0-1 evaluations (that is, $\Lambda = \{0, 1\}$). We introduce several voting procedures in this context:

**Definition 1 (Voting procedures).**

* **Approval Voting:** The candidate with the highest number of approvals is elected.

* **Median Voting:** A candidate is elected if they are the only one with more than half of the approvals.

* **Unanimity Voting:** The elected candidate is the only one receiving unanimous approval.

Note that median voting and unanimity voting elect candidates less frequently than standard approval voting. However, whenever they do, the winner is the same as the one that approval voting would have elected.

Let us now define deepest voting and introduce a depth function. Among the various depth functions, we are interested in the class of weighted $L^p$-depth, $p > 0$, introduced by Zuo (2004). It is based on the $L^p$ norm on $\mathbb{R}^d$ and given by

$$wL^pD(x, F) = (1 + \mathbb{E}w(\|x - X\|_p))^{-1},$$

where $w: [0, \infty) \to \mathbb{R}_+$ is a non-decreasing and continuous function with $w(\infty) = \infty$, $X \sim F$ is a random variable with law F lying in some set of probability measures $\mathcal{F}$. This weighted $L^p$-depth function satisfies the desirable properties of general statistical depth functions introduced by Serfling and Zuo (2000). It is permutation invariant, translation invariant, maximized at the center of symmetric distribution, quasi-concave, and vanishing at infinity. We refer to Aubin et al. (2022, Definition 1) for a formal definition of depth function.
In this note, we focus on the specific weight $w: x \mapsto x^p$ and a specific law $F$ which is the empirical distribution $\Phi_n$ of a given set of $n$ points $\Phi_n(\cdot, 1), \dots, \Phi_n(\cdot, n)$. In that case, the associated depth function is denoted $L^p D$,

$$L^p D(x, \Phi_n) = \frac{1}{1 + \frac{1}{n} \sum_{j=1}^{n} \sum_{i=1}^{d} |\Phi_n(i, j) - x_i|^p},$$

and will be called $L^p$-depth.

For $p = \infty$, let us also define

$$L^\infty D(x, \Phi_n) = \frac{1}{1 + \frac{1}{n} \sum_{j=1}^{n} \max_{i=1, \dots, d} |\Phi(i, j) - x_i|}.$$

Thanks to this notion of depth function, we can now define the associated method of grading called *deepest voting*. In this context, let $F$ be the empirical measure of $n$ points in $[0, 1]^d$.

**Definition 2 (L$^p$-deepest voting).** Consider a grading matrix $\Phi_n$. Denote

$$\chi_p^* := \{x \in \mathbb{R}^d : L^p D(x, \Phi_n) = \sup\{L^p D(\cdot, \Phi_n)\}\}$$

the set of deepest points of $L^p D$ with respect to $\Phi_n$. Let $G_p: \Phi_n \to \chi_p^*$ be the method of grading with respect to the depth $L^p D$. Let

$$i_p := \underset{1 \le i \le d}{\operatorname{argmax}} \{x_{p,i}^*, x_p^* = (x_{p,1}^*, \dots, x_{p,d}^*) \in \chi_p^*\}.$$

The L$^p$-deepest voting process with respect to the depth L$^p$D is defined as the function which maps $\{\Phi_n(i, j), i = 1, \dots, d, j = 1, \dots, n\}$ to $i_p \subseteq \{1, \dots, d\}$.

If $i_p$ is unique, then the winner of the election is the candidate $c_{i_p}$. If $i_p$ is not unique, there is no unique winner of the election.

The intuitive key idea of deepest voting is enriched by a large choice of depth functions. For instance, this class of L$^p$-voting includes the usual majority judgment introduced by Balinski and Laraki (2007) and range voting introduced by Smith (2000), which correspond to $p = 1$ and $p = 2$ respectively.

In the very special case $\Lambda = \{0, 1\}$, we are able to identify the L$^p$-deepest voting process with known voting processes.

**Theorem 3 (Phase transitions for L$^p$-deepest voting process).** Assume $\Lambda = \{0, 1\}$. The L$^p$-deepest voting process gives the same set of winners as

(i) median voting, if $0 < p \le 1$.

(ii) approval voting, if $1 < p < \infty$.

(iii) unanimity voting, if $p = \infty$.

Visually, each voter can be represented in the space $\mathbb{R}^d$ where each coordinate along axis $i$ corresponds to the score (0 or 1) they assign to candidate $c_i$. All voters are thus positioned at the vertices of the hypercube in $\mathbb{R}^d$ with one vertex at the origin, another at $(1, 1, \dots, 1)$ and edges of length 1.

L$^p$-deepest voting method associates with this set of points the point that minimizes the sum of the L$^p$-distances to all these points. The candidate corresponding to the highest coordinate of this central point is then elected.
In a two-candidates election with 20 voters, Figure 1 illustrates the position of the deepest point. On the left, each line represents a configuration $(n_1, n_2)$ where $n_i$ denotes the number of approvals received by candidate $c_i$, with $p$ varying along each trajectory from 1 -with $p > 1$- (outermost point) to 10 (closer to the point with coordinates $(0.5, 0.5)$). On the right, every blue (resp. red) curve corresponds to a configuration where $n_2 > n_1$ (resp. $n_1 > n_2$). The fact that all blue points (resp. red points) are located above (respectively below) the line $y = x$ indicates that there is an equivalence between approval voting and $L^p$ deepest voting.

*Proof of Theorem 3.* Let us first consider the case $p \in ]0, \infty[$. For each candidate $c_i$, $1 \le i \le d$, denote $n_i$ the number of votes for $c_i$. We recall that we are in the case $\Lambda = \{0, 1\}$ where the voters can give only 0 or 1 (approval) to the candidates. We can then write

$$L^p D(x) = \frac{1}{1 + \frac{1}{n} \sum_{i=1}^{d} (n_i |1 - x_i|^p + (n - n_i)x_i^p)}$$

so that for all $1 \le i \le d$, we have

$$x_i^* = \underset{x_i \in [0,1]}{\operatorname{argmin}} (n_i |x_i - 1|^p + (n - n_i)x_i^p).$$

It remains to analyze the function $f_i : x \in [0,1] \mapsto n_i|1-x|^p + (n-n_i)x^p$. First, if $n_i = 0$, then it is straightforward that $x_i^* = 0$. Consider now the case $n_i > 0$.

* Assume first that $p > 1$.

From Aubin et al. (2022, Proposition 7), the deepest point is unique and it is not hard to show that the unique minimizer of $f_i$ is

$$x_i^* = \frac{1}{1 + \left(\frac{n}{n_i} - 1\right)^{1/(p-1)}}.$$

Recall that the winner of the $L^p$-deepest voting procedure is the one which maximizes $x_1^*, \dots, x_d^*$. From the closed form of $x_i^*$, we deduce that the set of winners $i_p$ consists of the (possibly non unique) candidates $c_i$ for which $n_i$ is the greatest, that is, the candidates with the most votes. This corresponds to the approval voting.

* Assume now that that $p \le 1$.

In the case, the deepest point is not necessarily unique (see Aubin et al. (2022, Proposition 7)). A simple analysis of the function $f_i$ leads to

$$x_i^* = \begin{cases} 0 & \text{if } n_i < \frac{n}{2} \\ 1 & \text{if } n_i > \frac{n}{2} \\ [0, 1] & \text{if } n_i = \frac{n}{2} \text{ and } p = 1 \\ \{0, 1\} & \text{if } n_i = \frac{n}{2} \text{ and } p < 1. \end{cases}$$

If the numbers of votes for a candidate $c_i$ is greater or equal (resp. strictly less) than $n/2$, then $x_i^*$ is equal to 1 (resp. 0) which corresponds exactly to the median of the notes of the voters for this candidate. Hence $L^p$-deepest voting is the median voting in the case $p \in ]0, 1]$.

* Consider at least the extreme case $p = \infty$.
In that case, the deepest point is also unique and its coordinates are the mean of their best and worst grades (see Aubin et al. (2022, Proposition 9)). This implies that they are only three possibilities. If all voters give grade 1 (resp 0) to candidate $c_i$, then $x_i^* = 1$ (resp. $x_i^* = 0$). If they are at least one grade 1 and one grade 0, then $x_i^* = 1/2$. This corresponds to unanimity voting procedure and ends the proof. ☐

Note that the case $p=0$ is not treated here, as the $L^0$-"norm" is not a norm. Indeed, the function $L^0D$ is not a depth function (Serfling and Zuo, 2000).

## References

Jean-Baptiste Aubin, Irène Gannaz, Samuela Leoni, and Antoine Rolland. Deepest voting: A new way of electing. *Mathematical Social Sciences*, 116:1–16, 2022.

Michel Balinski and Rida Laraki. A theory of measuring, electing and ranking. *Proceedings of the National Academy of Sciences*, 104(21):8720–8725, 2007.

Steven J. Brams and Peter C. Fishburn. *Approval voting*. Springer, second edition, 2007.

Robert Serfling and Yijun Zuo. General notions of statistical depth function. *The Annals of Statistics*, 28(2):461–482, 2000. doi: 10.1214/aos/1016218226. URL https://doi.org/10.1214/aos/1016218226.

Warren D. Smith. Range voting. http://rangevoting.org/RangeVoting.html, 2000. Accessed: 2023-06-01.

Yijun Zuo. Robustness of weighted L$^p$-depth and L$^p$-median. *Allgemeines Statistisches Archiv*, 88(2): 215–234, 2004. ISSN 1614-0176. doi: 10.1007/s101820400169.

LÉO DORT
UNIVERSITÉ BOURGOGNE EUROPE, INSTITUT AGRO, INRAE, UMR 1347 AGROÉCOLOGIE
21000 DIJON, FRANCE

Email: leo.dort@institut-agro.fr

JEAN-BAPTISTE AUBIN
UNIV. LYON, INSA-LYON, INSTITUT CAMILLE JORDAN, UMR 5208
69621 VILLEURBANNE, FRANCE

Email: jean-baptiste.aubin@insa-lyon.fr

IRÈNE GANNAZ
UNIV. GRENOBLE ALPES, CNRS, GRENOBLE INP, G-SCOP
38000 GRENOBLE, FRANCE

Email: irene.gannaz@grenoble-inp.fr

SAMUELA LEONI
UNIV. LYON, INSA-LYON, INSTITUT CAMILLE JORDAN, UMR 5208
69621 VILLEURBANNE, FRANCE

Email: samuela.leoni@insa-lyon.fr

ANTOINE ROLLAND
LABORATOIRE ERIC UMR 3083, UNIVERSITÉ DE LYON, UNIVERSITÉ LUMIÈRE LYON 2
5 PIERRE MENDÈS FRANCE, 69596 BRON CEDEX, FRANCE

Email: antoine.rolland@univ-lyon2.fr