11institutetext: 1Key Laboratory of High Confidence Software Technologies
(MOE), School of Computer Science, Peking University, China
11email: {lizhechen, caoyz<EMAIL_ADDRESS>22institutetext: Google LLC
22email<EMAIL_ADDRESS>33institutetext: Department of Computer Science,
Rensselaer Polytechnic Institute
33email<EMAIL_ADDRESS>44institutetext: School of Computer Science and
Cyber Engineering, Guangzhou University, China

# Trading Off Voting Axioms for Privacy

Zhechen Li 11 Ao Liu 22 Lirong Xia 33 Yongzhi Cao 11 Hanpin Wang 1144

###### Abstract

In this paper, we investigate tradeoffs among differential privacy (DP) and
several important voting axioms: Pareto efficiency, SD-efficiency, PC-
efficiency, Condorcet consistency, and Condorcet loser criterion. We provide
upper and lower bounds on the two-way tradeoffs between DP and each axiom. We
also provide upper and lower bounds on three-way tradeoffs among DP and every
pairwise combination of all the axioms, showing that, while the axioms are
compatible without DP, their upper bounds cannot be achieved simultaneously
under DP. Our results illustrate the effect of DP on the satisfaction and
compatibility of voting axioms.

###### Keywords:

Voting Differential Privacy Rank Aggregation Computational Social Choice

##  1 Introduction

Voting is a popular method for collective decision making. In a typical voting
process, voters express their preferences over the alternatives, and a winner
is determined according to a voting rule. In modern social choice theory,
voting rules are evaluated and compared by the axiomatic approach [26], w.r.t.
their satisfaction of various normative properties, known as voting axioms.
For instance, Pareto efficiency requires that any Pareto-dominated alternative
(i.e., an alternative considered worse than another alternative by all voters)
should never be selected as the winner.

_Differential privacy_ (DP) is a _de facto_ notion of privacy and is widely
used in the field of machine learning [1, 31, 28], data mining [15, 36], and
recommendation systems [6, 22], just to name a few. In recent years, privacy
has also become a major concern in voting schemes, prompting extensive
research on differential privacy in the context of voting and rank aggregation
[29, 17, 35, 24]. Those works focus on the privacy-utility tradeoff in voting
rules (or rank aggregations), where the utility usually is measured by
accuracy or mean square error. Even though some previous work [21, 23] has
explored the tradeoff between DP and certain voting axioms through several
mechanisms, the overall tradeoff between DP and voting axioms remains largely
unexplored. Besides, the relationship between voting axioms may be affected by
DP. For example, Condorcet criterion is compatible with Pareto efficiency in
social choice theory, where Condorcet criterion requires that the Condorcet
winner (the alternative defeats all components in pairwise comparison) must
win the election. However, when DP is required, Condorcet criterion and Pareto
efficiency are no longer compatible. At a high level, this is because DP
requires the voting rules to be random, i.e., all alternatives need to have a
non-zero probability to win. Thus, under DP, (better) Condorcet criterion
requires the Condorcet winner to win with a larger probability, while (better)
Pareto efficiency focus on the pairwise difference in winning probability
(Pareto-dominate alternative need to have a higher probability to win compared
to the Pareto-dominated alternative). Till now, the incompatibility between
axioms brought by DP has not been studied. Thus, the following question still
remains largely open.

What is the tradeoff among DP and voting axioms?

Since DP requires randomness in the voting rule, the (strict) axioms are
usually not compatible with DP [23]. Thus, we propose approximate voting
axioms and study the tradeoff among DP and those approximate axioms.

###  1.1 Our contributions

Our conceptual contribution involves proposing approximate versions of Pareto
efficiency, SD-efficiency, PC-efficiency, and Condorcet loser criterion
(Definitions 2-6)

Our theoretical contributions are two-fold. Firstly, we explore the 2-way
tradeoff between DP and a single (approximate) axiom. We provide tradeoff
theorems (with both upper and lower bounds) between DP and the approximate
Pareto, SD, and PC efficiencies (Propositions 1-5). For Condorcet criterion
and Condorcet loser criterion, we provide a tight bound for their tradeoffs
with DP (Propositions 6-8). We summarize this part of contributions in Fig. 1,
where the expressions displayed on the lines illustrate the bounds of the
approximate axioms under $\epsilon$-DP.

Figure 1: Tradeoff between $\epsilon$-DP and voting axioms.

Secondly, we explore the 3-way tradeoff between DP and two axioms (also called
tradeoff axioms under DP in this paper). Since even the approximate version of
PC-efficiency cannot be achieved under DP, we consider Condorcet criterion,
Condorcet loser criterion, Pareto efficiency, and SD-efficiency in 3-way
tradeoffs. We capture the lower bounds of 3-way tradeoffs through several
mechanisms, summarized by Table 2 in Section 4. Then we investigate all of
their pairwise tradeoff under DP by proving their upper bounds (Theorems
4.1-4.6). We show that there exists a tradeoff between each pair of these
axioms, though they are compatible without DP. This part of results is
summarized in Fig. 2, where the expressions displayed on the lines illustrate
the upper bounds of 3-way tradeoffs between the axioms.

Figure 2: Relations between voting axioms under $\epsilon$-DP.

Algorithmically, we propose a group of (randomized) voting rules able to make
smooth 2-way tradeoffs between DP and the axioms mentioned above (Mechanisms
Mechanism 1-Mechanism 4). For the 3-way tradeoffs, we propose a mechanism able
to flexibly tradeoff between Condorcet criterion and Condorcet loser criterion
(Mechanism Mechanism 5). Finally, we experimentally verified the tradeoffs in
the proposed mechanisms.

###  1.2 Related work and discussions

To the best of our knowledge, the application of DP to rank aggregations (a
generalized problem of voting) was first introduced in [29], which derived
upper bounds on error rate under DP. In a similar vein, Lee [21] proposed a
tournament voting rule that achieves both DP and robustness to strategic
manipulations. Hay et al. [17] used the Laplace mechanism and exponential
mechanism to enhance the privacy of Quicksort and Kemeny-Young methods. Kohli
and Laskowski [20] investigated DP, strategyproofness, and anonymity for
voting on single-peaked preferences. Torra [30] analyzed the privacy-
preserving level of the random dictatorship, a well-known randomized voting
rule, using DP. Their study examined the conditions under which random
dictatorship satisfies DP and proposed improvements to achieve it in general
cases. Wang et al. [33] analyzed the privacy of positional voting and proposed
a new noise-adding mechanism that outperforms the naive Laplace mechanism in
terms of accuracy. Yan et al. [35] addressed the tradeoff between accuracy and
privacy in rank aggregation by achieving local DP through Laplace mechanism
and randomized response. They explored mechanisms that strike a balance
between privacy and utility in the context of rank aggregation.

Most of the aforementioned works did not consider the tradeoff between privacy
and voting axioms. The privacy bounds in those works are usually not tight.
Liu et al. [24] introduced distributional DP [4] to voting and studied the
privacy level of several commonly used voting rules, but they did not provide
any approach to improve privacy. Li et al. [23] introduced a novel family of
voting rules that satisfy DP along with various voting axioms. They also
explored the tradeoff between DP and several axioms, including Pareto
efficiency, Condorcet criterion, and others. However, Li et al. [23] only
briefly discussed the general tradeoff between DP and certain axioms, and
their discussion was limited to Condorcet criterion and Pareto axioms. A more
comprehensive and in-depth analysis is still required in this regard. Beyond
social choice, DP has also been considered in other topics of economics, such
as mechanism design [25, 34], matching [18], and resource allocation [18, 19].

In the context of social choice theory, there is a large literature on the
analysis of randomized voting [11]. Most of them focused on assessing the
satisfaction of standard axiomatic properties, such as the complexity of
manipulation [32], strategyproofness [2, 3], Pareto efficiency [8, 16],
participation [9] and monotonicity [10]. In sortition, the fairness properties
have also been investigated [5, 14, 13]. For approximate axiomatic properties,
Procaccia [27] discussed how much a strategyproof randomized rule could
approximate a deterministic rule. Birrell and Pass [7] explored the
approximate strategyproofness for randomized voting rules. All those
approximate axioms are not natural in the context of DP because approximate
axioms adopt the difference in utility functions but DP focuses on ratios.

##  2 Preliminaries

Let $A=\\{a_{1},a_{2},\ldots,a_{m}\\}$ denote a set of $m\geqslant 2$
alternatives. For any $n\in\mathbb{N}$, let $N=\\{1,2,\ldots,n\\}$ be a set of
voters. For each $j\in N$, the vote of voter $j$ is a linear order
$\succ_{j}\in\mathcal{L}(A)$, where $\mathcal{L}(A)$ denotes the set of all
linear orders over $A$, i.e., all transitive, anti-reflexive, anti-symmetric,
and complete binary relations. $P=\\{\succ_{1},\succ_{2},\ldots,\succ_{n}\\}$
denotes the _(preference) profile_ , which is the collection of $n$ votes. For
any $j\in N$, let
$P_{-j}=\\{\succ_{1},\ldots,\succ_{j-1},\succ_{j+1},\ldots\succ_{n}\\}$ denote
the profile of removing the $j$-th vote from $P$.

Under the settings above, a (randomized) voting rule can be defined as a
mapping $f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$, where $\mathcal{R}(A)$
denotes the set of all random variables on $A$ (usually called lotteries in
social choice theory). Given a voting rule $f$ and a profile $P$, the winning
probability of alternative $a\in A$ is denoted by $\mathbb{P}[f(P)=a]$. A
voting rule $f$ is neutral if for any profile $P$ and any permutation $\sigma$
on $A$, $\sigma\cdot f(P)=f(\sigma\cdot P)$.

Differential privacy (DP111We use DP to represent either _differential
privacy_ or _differentially private_ throughout this paper., [12]). At a high
level, DP requires a function to have similar output (distribution) when
inputting neighboring databases. Here, we say two databases are _neighboring_
if one can be gotten by replacing no more than one entry from the other
database.

######  Definition 1 (Differential Privacy [12])

A mechanism $f:\mathcal{D}\to\mathcal{O}$ satisfies $\epsilon$-differential
privacy ($\epsilon$-DP for short) if for all $O\subseteq\mathcal{O}$ and each
pair of neighboring databases $P,P^{\prime}\in\mathcal{D}$,

$\displaystyle\mathbb{P}[f(P)\in O]\leqslant{\rm
e}^{\epsilon}\cdot\mathbb{P}[f(P^{\prime})\in O].$

The probability of the above inequality is taken over the randomness of the
mechanism. The smaller $\epsilon$ is, the better privacy guarantee can be
offered. In the context of social choice, the mechanism $f$ in Definition 1 is
a voting rule and its domain

$\displaystyle\mathcal{D}=\mathcal{L}(A)^{*}=\mathcal{L}(A)\cup\mathcal{L}(A)^{2}\cup\cdots.$

Further, the pair of neighboring databases $P,P^{\prime}$ are two profiles
differing on no more than one vote, i.e., there exists a voter $j\in N$ such
that $P_{-j}=P_{-j}^{\prime}$.

Axioms of voting. The axioms considered in the paper can be roughly divided
into two parts: axioms that only depend on preferences over alternatives and
axioms that depend on preferences over lotteries in $\mathcal{R}(A)$. We adopt
the notions in [11] here.

For clarity, we define the following notions before presenting the axioms.
Given a profile $P$ and two distinct alternatives $a,b\in A$, let $w_{P}[a,b]$
denote the majority margin of $a$ over $b$, which equals to the number of
voter that consider $a\succ b$ minus the number of voter that consider $b\succ
a$, i.e.,

$\displaystyle w_{P}[a,b]=|\\{j\in N:a\succ_{j}b\\}|-|\\{j\in
N:b\succ_{j}a\\}|.$

Here, we slightly abuse the notations and let $a\succ_{j}b$ represent that the
$j$-th voter prefers $a$ to $b$. Again, $\succ_{j}$ represents the $j$-th vote
(a linear order) when appearing alone. The Condorcet winner of $P$ (denoted as
$\operatorname{CW}(P)$) is an alternative $a\in A$ such that $w_{P}[a,b]>0$
for all $b\neq a$. Similarly, the Condorcet loser of $P$ (denoted as
$\operatorname{CL}(P)$) is the alternative $a\in A$ which satisfies
$w_{P}[a,b]<0$ for all $b\neq a$. Based on these notions, the first part of
the axioms are listed below.

  * •

Condorcet criterion: A voting rule $f$ satisfies Condorcet criterion if
$\mathbb{P}[f(P)=\operatorname{CW}(P)]=1$ holds for all profile $P$ that
$\operatorname{CW}(P)$ exists;

  * •

Condorcet loser criterion: A voting rule $f$ satisfies Condorcet loser
criterion if $\mathbb{P}[f(P)=\operatorname{CL}(P)]=0$ holds for all profile
$P$ that $\operatorname{CL}(P)$ exists;

  * •

Pareto efficiency: A voting rule $f$ satisfies Pareto efficiency if
$\mathbb{P}[f(P)=b]=0$ for all profile $P\in\mathcal{L}(A)^{n}$, where $b\in
A$ is Pareto dominated by some $a\in A$, i.e., $a\succ_{j}b$ for all $j\in N$.

The second part of axioms (efficiency notions except Pareto efficiency)
considers the relationship between lotteries. For clarity, we define the
following relationships before presenting the axioms.

Stochastic Dominance (SD): Given the $j$-th vote
$\succ_{j}\,\in\mathcal{L}(A)$ and two lotteries $\xi,\zeta\in\mathcal{R}(A)$,
$\xi$ is more desirable under SD for the $j$-th voter (denoted by
$\xi\succeq_{j}^{SD}\zeta$) if and only if for every $x\in A$, the probability
of $\xi$ selecting an alternative better than $x$ is no less than the
probability for $\zeta$ to select such an alternative, i.e.,

$\displaystyle\sum\limits_{x\succ
y}\mathbb{P}[\xi=x]\geqslant\sum\limits_{x\succ
y}\mathbb{P}[\zeta=x],\quad\text{for all }y\in A.$ (1)

We say $\xi$ is strictly more desirable than $\zeta$ by means of SD for the
$j$-th voter (denoted by $\xi\succ_{j}^{SD}\zeta$) if and only if
$\xi\succeq_{j}^{SD}\zeta$ holds and $\zeta\succ_{j}^{SD}\xi$ does not hold.

Pairwise Comparison (PC): Given the $j$-th vote $\succ_{j}\,\in\mathcal{L}(A)$
and two lotteries $\xi,\zeta\in\mathcal{R}(A)$, $\xi$ is more desirable under
PC for the $j$-th voter (denoted by $\xi\succeq_{j}^{PC}\zeta$) if and only if
the probability that $\xi$ yields a better alternative than $\zeta$ is no less
than the other way round, i.e.,

$\displaystyle\sum\limits_{x\succ
y}\mathbb{P}[\xi=x]\cdot\mathbb{P}[\zeta=y]\geqslant\sum\limits_{x\succ
y}\mathbb{P}[\zeta=x]\cdot\mathbb{P}[\xi=y].$ (2)

Similarly, $\xi$ is strictly more desirable than $\zeta$ by means of PC for
the $j$-th voter (denoted by $\xi\succ_{j}^{PC}\zeta$) if and only if
$\xi\succeq_{j}^{PC}\zeta$ holds and $\zeta\succ_{j}^{PC}\xi$ does not hold.

Based on SD and PC, the second part of axioms (SD-efficiency and PC-
efficiency) are defined as follows.

  * •

SD-Efficiency: A voting rule $f$ satisfies SD-efficiency if for all profile
$P\in\mathcal{L}(A)^{n}$, there does not exist $\xi\in\mathcal{R}(A)$
satisfying both of the following two conditions.

1\. For all $j\in N$, $\xi\succeq_{j}^{SD}f(P).$ 2\. There exists some $j\in
N$ that $\xi\succ_{j}^{SD}f(P)$.

  * •

PC-Efficiency:  A voting rule $f$ satisfies PC-efficiency if for all profile
$P\in\mathcal{L}(A)^{n}$, there does not exist $\xi\in\mathcal{R}(A)$
satisfying both of the following two conditions.

1\. For all $j\in N$, $\xi\succeq_{j}^{PC}f(P).$ 2\. There exists some $j\in
N$ that $\xi\succ_{j}^{PC}f(P)$.

The relationship among the notions of efficiency mentioned in our paper can be
visualized as the following diagram, where $a\to b$ indicates that $a$ implies
$b$.

$\displaystyle\text{(Strongest) PC-efficiency}\to\text{SD-
efficiency}\to\text{Pareto~{}efficiency (Weakest)}$

##  3 DP-Axioms Tradeoff

This section investigates the tradeoff between privacy and voting axioms
(2-way tradeoff). The axioms considered here can be divided into two parts,
efficiency (Pareto efficiency, SD-efficiency, and PC-efficiency), and
Condorcet consistency (Condorcet criterion and Condorcet loser criterion).
Table 1 summarizes the theoretical results of this section. As all five axioms
are not compatible with DP, we propose their approximate version (if has not
yet been proposed in literature). With the approximate axioms, we establish
both upper and lower bounds about their tradeoffs with DP, i.e., the upper and
lower bound of approximate axioms with a given privacy budget $\epsilon$. All
missing proofs of this section can be found in Appendix A.

Table 1: The tradeoff between DP and voting axioms, where ✗ indicates that the standard efficiency is incompatible with DP. The expressions in the table represent the level of satisfaction to approximate notions of efficiency under $\epsilon$-DP (approximate PC-efficiency is not achievable under DP, so there is no lower bound here). Voting axiom | Compatibility | Upper bound | Lower bound | Reference
---|---|---|---|---
Pareto efficiency | ✗ | ${\rm e}^{\frac{n\epsilon}{m-1}}$ | ${\rm e}^{\frac{n\epsilon}{2m-2}}$ | Propositions 1-2
SD-efficiency | ✗ | $\frac{(m-1){\rm e}^{n\epsilon}}{(m-1){\rm e}^{n\epsilon}+1}$ | $\frac{(m-1){\rm e}^{\epsilon}}{(m-1){\rm e}^{\epsilon}+1}$ | Propositions 3-4
PC-efficiency | ✗ | $0$ | — | Proposition 5
Condorcet criterion | ✗ |  ${\rm e}^{\epsilon}$ [23] | ${\rm e}^{\epsilon}$ | Proposition 6
Condorcet loser criterion | ✗ | ${\rm e}^{\epsilon}$ | ${\rm e}^{\epsilon}$ | Propositions 7-8

###  3.1 DP-Efficiency tradeoff

First of all, we discuss the tradeoff between DP and Pareto efficiency. Li et
al. [23] introduced the concept of probabilistic Pareto efficiency to address
the inherent incompatibility between DP and Pareto efficiency. Probabilistic
Pareto efficiency stipulates that each Pareto dominating alternative must have
a higher probability of winning compared to the dominated alternative
(standard Pareto efficiency requires “always winning” instead of “a higher
probability of winning”). We further extend this notion by introducing a
parameter $\beta$ to quantify the level of Pareto efficiency.

######  Definition 2 ($\beta$-Pareto Efficiency)

Given $\beta>0$, a voting rule $f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$
satisfies $\beta$-Pareto efficiency, if for each pair of alternatives $a,b\in
A$ that $a\succ_{j}b$ for all $j\in N$, it holds that

$\displaystyle\mathbb{P}[f(P)=a]\geqslant\beta\cdot\mathbb{P}[f(P)=b].$

In words, a voting rule satisfies $\beta$-Pareto efficiency if the winning
probability of each Pareto dominated alternative never exceeds $1/\beta$ of
the winning probability of its dominant alternative. Therefore, in Definition
2, a larger $\beta$ is more desirable and represents a higher level of Pareto
efficiency. It’s easy to check that $1$-Pareto efficiency is equivalent to the
probabilistic Pareto efficiency in [23] and $\infty$-Pareto efficiency is
equivalent to standard Pareto efficiency.

Next, we tradeoff Pareto efficiency with DP under the notion of $\beta$-Pareto
efficiency. The following proposition provides an upper bound of
$\beta$-Pareto efficiency under the constraint of $\epsilon$-DP.

######  Proposition 1 ($\beta$-Pareto Efficiency, Upper Bound)

There is no neutral rule $f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$ that
satisfies $\epsilon$-DP and $\beta$-Pareto efficiency with $\beta>{\rm
e}^{\frac{n\epsilon}{m-1}}$.

Proof Sketch. Let $f$ be a neutral rule satisfying $\epsilon$-DP and
$\beta$-Pareto efficiency. By $\epsilon$-DP and neutrality, we can prove that

$\displaystyle\mathbb{P}[f(P)=a]$ $\displaystyle\leqslant{\rm
e}^{n\epsilon}\cdot\mathbb{P}[f(P)=b],\quad\text{for all
}P\in\mathcal{L}(A)^{n}\text{ and }a,b\in A.$ (3)

Then, by considering the profile $P$ where all voters’ preferences are the
same, i.e., $a_{1}\succ_{j}a_{2}\succ_{j}\cdots\succ_{j}a_{m}$ for all $j\in
N$, we have

$\displaystyle\mathbb{P}[f(P)=a_{1}]$ $\displaystyle\leqslant{\rm
e}^{n\epsilon}\cdot\mathbb{P}[f(P)=a_{m}].$

Theorefore, we have $\beta^{m-1}\leqslant{\rm e}^{n\epsilon}$, i.e.,
$\beta\leqslant{\rm e}^{\frac{n\epsilon}{m-1}}$. Then Proposition 1 follows. ∎

Proposition 1 provides an upper bound on the achievable level of Pareto
efficiency when subject to the constraint of $\epsilon$-DP. Next, we propose a
mechanism (Mechanism Mechanism 1, Borda score exponential mechanism or
BordaEXP for short) to show a lower bound of the achievable approximate Pareto
efficiency under DP. Technically, Mechanism Mechanism 1 is an exponential
mechanism that employs the Borda score as the utility metric, where the Borda
score of an alternative $a\in A$ for a given profile $P$ is defined as
follows.

$\displaystyle\operatorname{\mathsf{Borda}}_{P}(a)=\sum\limits_{\succ_{j}\in
P}|\\{b\in A:a\succ_{j}b\\}|.$

Input: Profile $P$, Noise Level $\epsilon$

Output: Winning Alternative

2 Get Borda score $\operatorname{\mathsf{Borda}}_{P}(a)$ of each alternative
$a\in A$ for profile $P$;

3 Compute the probability distribution $p\in\Delta(A)$, such that
$p(a)\propto{\rm e}^{\operatorname{\mathsf{Borda}}_{P}(a)\epsilon/(2m-2)}$ for
all $a\in A$;

4 Sample $a_{win}\sim p$;

return _$a_{win}$_

Mechanism 1 Borda Score Exponential Mechanism (BordaEXP)

The following Proposition illustrates the lower bound of approximate Pareto
efficiency achieved by Mechanism Mechanism 1. Both upper and lower bound for
$\beta$-Pareto efficiency are $\exp(\Theta(n\epsilon/m))$. We plot both bounds
in Fig. 4, where we set $m=5,n=10$.

######  Proposition 2 ($\beta$-Pareto Efficiency, Lower Bound)

Given $\epsilon\in\mathbb{R}_{+}$, Mechanism Mechanism 1 satisfies
$\epsilon$-DP and ${\rm e}^{\frac{n\epsilon}{2m-2}}$-Pareto efficiency.

Figure 3: Upper and lower bounds of $\beta$-Pareto efficiency under
$\epsilon$-DP.

Figure 4: Upper and lower bounds of $\gamma$-SD-efficiency efficiency under
$\epsilon$-DP.

Secondly, we discuss the tradeoff between DP and SD-efficiency. As a notion
stronger than Pareto efficiency, SD-efficiency is also incompatible with DP.
In order to capture the incompatibility between DP and SD-efficiency, an
approximate version of SD-efficiency is needed. Li et al. [23] proposed
approximate SD-strategyproofness, where they introduced a parameter in
Inequality (1) (the definition of SD relationship). Their method inspires us
to consider the approximate version of SD relationship, which is defined as
follows.

Let $\xi,\zeta\in\mathcal{R}(A)$ be two lotteries and
$\succ\,\in\mathcal{L}(A)$ be a linear order on $A$. Then $\xi$ is said to
$\gamma$-stochastically dominate $\zeta$ (denoted by $\xi\succeq^{\gamma-
SD}\zeta$), if and only if222We use $1/\gamma$ to ensure that the property
becomes stronger as $\gamma$ increases.

$\displaystyle\sum\limits_{b\succ_{j}a}\mathbb{P}[\xi=b]\geqslant\frac{1}{\gamma}\cdot\sum\limits_{b\succ_{j}a}\mathbb{P}[\zeta=b].$

Then, we define $\gamma$-SD-efficiency as follows based on the approximate SD
relationship.

######  Definition 3 ($\gamma$-SD-Efficiency)

Given $\gamma\in\mathbb{R}_{+}$, a voting rule
$f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$ satisfies $\gamma$-SD-efficiency
if for all profile $P$, $f(P)$ is not $\gamma$-SD-dominated.

A larger value of $\gamma$ is more desirable because in the definition of
$\gamma$-SD, a larger $\gamma$ imposes stricter conditions for a lottery to
$\gamma$-SD-dominate another one. Consequently, achieving $\gamma$-SD-
efficiency becomes comparatively easier as $\gamma$ decreases. Especially,
when $\gamma=1$, $\gamma$-SD-efficiency reduces to the standard SD-efficiency.

Compared to the $\beta$-Pareto efficiency (Definition 2), the definition of
$\gamma$-SD-efficiency is a bit more sophisticated, which brings obstacles to
our exploration. Therefore, we develop a tool to help us judge whether a
voting rule satisfies $\gamma$-SD-efficiency with a given $\gamma$, as shown
in the following lemma.

###### Lemma 1

Given $\gamma>0$, a voting rule $f$ satisfies $\gamma$-SD-efficiency if and
only if

$\displaystyle\frac{1}{\gamma}\geqslant\sup\limits_{P\in\mathcal{L}(A)^{n},\;\xi\in\mathcal{R}(A)}\;\inf\limits_{j\in
N,\;y\in
A}\frac{\sum\limits_{x:x\succ_{j}y}\mathbb{P}[\xi=x]}{\sum\limits_{x:x\succ_{j}y}\mathbb{P}[f(P)=x]}.$

Using Lemma 1, we are ready to capture the upper bound of $\gamma$-SD-
efficiency under the constraint of $\epsilon$-DP, as shown in the following
proposition.

######  Proposition 3 ($\gamma$-SD-Efficiency, Upper Bound)

Given $\gamma\in\mathbb{R}_{+}$, there is no neutral voting rule
$f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$ satisfying $\epsilon$-DP and
$\gamma$-SD-efficiency with $\gamma>\frac{(m-1){\rm e}^{n\epsilon}}{(m-1){\rm
e}^{n\epsilon}+1}$.

Proof Sketch. Consider two profiles, $P_{1}$ and $P_{2}$, where all voters in
$P_{1}$ share the same preference order $a_{1}\succ a_{2}\succ\cdots\succ
a_{m}$. In contrast, in $P_{2}$, the voters’ preferences are
$a_{m}\succ^{\prime}a_{2}\succ^{\prime}a_{3}\succ^{\prime}\cdots\succ^{\prime}a_{m-1}\succ^{\prime}a_{1}$.
Then the unique SD-efficient lottery for $P_{1}$ and $P_{2}$ should be
$\mathbbm{1}_{a_{1}}$ and $\mathbbm{1}_{a_{m}}$, respectively. Here,
$\mathbbm{1}_{a_{1}}$ and $\mathbbm{1}_{a_{m}}$ represent indicator functions
defined as follows.

$\displaystyle\mathbb{P}[\mathbbm{1}_{a_{1}}=a]=\begin{cases}1&a=a_{1}\\\
0&\text{otherwise}\end{cases},\quad\mathbb{P}[\mathbbm{1}_{a_{m}}=a]=\begin{cases}1&a=a_{m}\\\
0&\text{otherwise}\end{cases}.$

Let $f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$ be any neutral voting rule
satisfying $\epsilon$-DP. Then, by Lemma 1, we have
$\frac{1}{\gamma}\geqslant\sup\limits_{P\in\mathcal{L}(A)^{n}}\sup\limits_{\xi\in\mathcal{R}(A)}\inf\limits_{y\in
A}\frac{\sum_{x\succ y}\mathbb{P}[\xi=x]}{\sum_{x\succ
y}\mathbb{P}[f(P)=x]}\geqslant\frac{(m-1){\rm e}^{n\epsilon}+1}{(m-1){\rm
e}^{n\epsilon}}$. Then Proposition 3 follows. ∎

Proposition 3 illustrates an upper bound of SD-efficiency under DP. Further,
based on a famous voting rule, random dictatorship333Select a voter randomly,
and then announce its top-ranked alternative as the winner. (RD), we propose a
mechanism (Mechanism Mechanism 2, Anti-Plurality exponential RD) to explore
the lower bound of the achievable approximate SD-efficiency under DP.
Technically, Mechanism Mechanism 2 replaces the dictatorial process in RD with
exponential mechanism adopting anti-plurality score as its utility measure,
where anti-plurality score is defined as

$\displaystyle\mathsf{Anti}_{\succ}(a)=\begin{cases}0,&a\text{ is the last-
ranked in }\succ\\\ 1,&\text{otherwise}\end{cases}.$

Input: Profile $P$, Noise Level $\epsilon$

Output: Winning Alternative

2 Select a ballot $\succ_{j}\in P$ randomly;

3 Get the last-ranked alternative of $\succ_{j}$, denoted by $a$;

4 Compute the probability distribution $p\in\Delta(A)$, where
$p(a)=\frac{1}{(m-1){\rm e}^{\epsilon}+1}$ and $p(b)=\frac{{\rm
e}^{\epsilon}}{(m-1){\rm e}^{\epsilon}+1}$, for all $b\in A\backslash\\{a\\}$;

5 Sample $a_{win}\sim p$;

return _$a_{win}$_

Mechanism 2 Anti-Plurality Exponential RD (RD-Anti)

Then the following proposition shows the lower bound of approximate SD-
efficiency under $\epsilon$-DP achieved by Mechanism Mechanism 2. Both the
upper bound and lower bound for $\gamma$-SD-efficiency are plotted in Fig. 4,
where we set $m=5,n=10$.

######  Proposition 4 ($\gamma$-SD-Efficiency, Lower Bound)

Mechanism Mechanism 2 satisfies $\epsilon$-DP and $\frac{(m-1){\rm
e}^{\epsilon}}{(m-1){\rm e}^{\epsilon}+1}$-SD-efficiency.

Proof Sketch. Let $\mathfrak{E}_{\mathsf{Anti}}$ denote Mechanism Mechanism 2.
For any neighboring profiles $P,P^{\prime}\in\mathcal{L}(A)^{n}$ that
$P_{-j}=P^{\prime}_{-j}$ and $\succ_{j}\neq\succ_{j}^{\prime}$, suppose that
the chosen ballot in the mechanism is $\succ_{i}$. We define

$\displaystyle C=\mathbb{P}[\mathfrak{E}_{\mathsf{Anti}}(P)=a~{}|~{}i\neq
j]=\mathbb{P}[\mathfrak{E}_{\mathsf{Anti}}(P^{\prime})=a~{}|~{}i\neq j]$

As a consequence, the DP-bound is given by the following inequality.

$\displaystyle\frac{\mathbb{P}[\mathfrak{E}_{\mathsf{Anti}}(P)=a]}{\mathbb{P}[\mathfrak{E}_{\mathsf{Anti}}(P^{\prime})=a]}\leqslant\frac{{\rm
e}^{\epsilon}\cdot\frac{1}{n}\mathbb{P}[\mathfrak{E}_{\mathsf{Anti}}(P^{\prime})=a~{}|~{}i=j]+\frac{n-1}{n}\cdot
C}{\frac{1}{n}\mathbb{P}[\mathfrak{E}_{\mathsf{Anti}}(P^{\prime})=a~{}|~{}i=j]+\frac{n-1}{n}\cdot
C}\leqslant{\rm e}^{\epsilon},$

For the bound of $\gamma$, we can prove that there is no lottery
$\xi\in\mathcal{R}(A)$ which satisfies $\xi\succ^{\gamma-
SD}_{i}\mathfrak{E}_{\mathsf{Anti}}(P)$ with $\gamma\geqslant\frac{(m-1){\rm
e}^{\epsilon}}{(m-1){\rm e}^{\epsilon}+1}$ for the selected $\succ_{i}$, which
completes the proof. ∎

Finally, we investigate the tradeoff between DP and PC-efficiency. Similar to
SD, the approximate version of PC relationship is also needed.

Given $\kappa>0$ and two lotteries $\xi,\zeta\in\mathcal{R}(A)$, $\xi$ is more
desirable than $\zeta$ by means of $\kappa\text{-}PC$ (denoted by
$\xi\succeq^{\kappa\text{-}PC}\zeta$) if and only if

$\displaystyle\sum\limits_{x\succ_{i}y}\mathbb{P}[\xi=x]\cdot\mathbb{P}[\zeta=y]\geqslant\frac{1}{\kappa}\cdot\sum\limits_{x\succ_{i}y}\mathbb{P}[\zeta=x]\cdot\mathbb{P}[\xi=y].$

Further, the approximate version of PC-efficiency can be defined.

######  Definition 4 ($\kappa$-PC-Efficiency)

Given $\kappa\in\mathbb{R}_{+}$, a voting rule
$f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$ satisfy $\kappa$-efficiency if
$f(P)$ is never $\kappa$-PC dominated for any profile
$P\in\mathcal{L}(A)^{n}$.

Similar to the case of SD, a larger $\kappa$ in Definition 4 is also more
desirable, and $1$-PC-efficiency also reduces to standard PC-efficiency. In
addition, our generalization of SD-efficiency and PC-efficiency keeps the
relationship between them (PC-efficiency implies SD-efficiency), shown as
follows.

###### Lemma 2

$\gamma$-PC-efficiency implies $\gamma$-SD-efficiency for all
$\gamma\in[0,1]$, .

Therefore, the upper bound of $\kappa$-PC-efficiency under DP must be smaller
than the upper bound of $\gamma$-SD-efficiency. However, the following
proposition shows that even the approximate version of PC-efficiency cannot be
achieved under DP.

######  Proposition 5 ($\kappa$-PC-Efficiency, Upper Bound)

Given any $\kappa,\epsilon\in\mathbb{R}_{+}$, there is no voting rule
$f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$ satisfying $\epsilon$-DP and
$\kappa$-PC-efficiency.

Proof Sketch. Consider the profile $P$, where all voters share the same
preference $a_{1}\succ a_{2}\succ\cdots\succ a_{m}$. Then
$\mathbbm{1}_{a_{1}}$ can $\kappa$-PC-dominate any $f(P)$. Then, Proposition 5
follows. ∎

Proposition 5 also implies that PC-efficiency is the limit of tradeoff between
DP and efficiency. Any notion stronger than PC-efficiency cannot be even
approximately achieved when DP is required.

###  3.2 DP-Condorcet consistency tradeoff

Condorcet winner and Condorcet loser are both important concepts in social
choice theory. Based on them, Condorcet consistency usually refers to two
axioms, i.e., Condorcet criterion and Condorcet loser criterion. However, DP
requires the support set of $f(P)$ equals to $A$ for all profile $P$, i.e.,
$\mathbb{P}[f(P)=a]\neq 0$ holds for all $P\in\mathcal{L}(A)^{n}$ and $a\in
A$, which indicates that neither of these axioms can be satisfied under the
constraint of DP. Li et al. [23] provided an approximate version of Condorcet
criterion ($\alpha$-pCondorcet) to describe the level of satisfaction of
Condorcet criterion. Further, they proved that if a voting rule satisfies
$\epsilon$-DP and $\alpha$-pCondorcet, then $\alpha\leqslant{\rm
e}^{\epsilon}$. Such an axiom is named $\alpha$-Condorcet criterion here, of
which the definition is shown as follows.

######  Definition 5 ($\alpha$-Condorcet Criterion [23])

Given $\alpha\in\mathbb{R}_{+}$, a voting rule
$f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$ satisfies $\alpha$-Condorcet
criterion if for all profiles $P$ such that $\operatorname{CW}(P)$ exists,

$\displaystyle\mathbb{P}[f(P)=\operatorname{CW}(P)]\geqslant\alpha\cdot\mathbb{P}[f(P)=a],\quad\text{for
all }a\in A\backslash\\{\operatorname{CW}(P)\\}.$

Next, we show the upper bound of approximate Condorcet criterion (${\rm
e}^{\epsilon}$-Condorcet criterion) is achievable under DP (see Proposition
6). Technically, we study Mechanism Mechanism 3 (abbreviated as CWRR), which
applies randomized response to $\mathbbm{1}_{\operatorname{CW}(P)}$.

Input: Profile $P$, Noise Level $\epsilon$

Output: Winning Alternative

2 if  _$\operatorname{CW}(P)$ exists_ then

3 $p(\operatorname{CW}(P))=\frac{{\rm e}^{\epsilon}}{{\rm e}^{\epsilon}+m-1}$;

4 $p(a)=\frac{1}{{\rm e}^{\epsilon}+m-1}$, for all $a\in
A\backslash\\{\operatorname{CW}(P)\\}$;

5

6else

7 $p(a)=\frac{1}{m}$, for all $a\in A$;

8

9Sample $a_{win}\sim p$;

return _$a_{win}$_

Mechanism 3 Condorcet Winner Randomized Response (CWRR)

######  Proposition 6 ($\alpha$-Condorcet Criterion, Lower Bound)

Mechanism Mechanism 3 satisfies both $\epsilon$-DP and ${\rm
e}^{\epsilon}$-Condorcet.

Similar to $\alpha$-Condorcet criterion, we propose the approximate Condorcet
loser criterion to measure the level of satisfaction of Condorcet loser
criterion.

######  Definition 6 ($\eta$-Condorcet Loser Criterion)

Given $\eta\in\mathbb{R}_{+}$, a voting rule
$f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$ satisfies $\eta$-Condorcet loser
criterion if for all profiles $P$ such that $\operatorname{CL}(P)$ exists,

$\displaystyle\mathbb{P}[f(P)=a]\geqslant\eta\cdot\mathbb{P}[f(P)=\operatorname{CL}(P)],\quad\text{for
all }a\in A\backslash\\{\operatorname{CL}(P)\\}.$

It is notable that the larger $\eta$ is more desirable in Definition 6, and
$\infty$-Condorcet loser criterion is equivalent to the standard version of
Condorcet loser criterion. Further, the following proposition shows an upper
bound of $\eta$ under DP.

######  Proposition 7 ($\eta$-Condorcet Loser Criterion, Upper Bound)

There is no voting rule satisfying $\epsilon$-DP and $\eta$-Condorcet loser
criterion with $\eta>{\rm e}^{\epsilon}$.

Proposition 8 shows the upper bound in Proposition 7 can be achieved by
Mechanism Mechanism 4 (Condorcet loser randomized response, CLRR), formally
stated as follows.

Input: Profile $P$, Noise Level $\epsilon$

Output: Winning Alternative

2 if  _$\operatorname{CL}(P)$ exists_ then

3 $p(\operatorname{CL}(P))=\frac{1}{(m-1){\rm e}^{\epsilon}+1}$;

4 $p(a)=\frac{{\rm e}^{\epsilon}}{(m-1){\rm e}^{\epsilon}+1}$, for all $a\in
A\backslash\\{\operatorname{CL}(P)\\}$;

5

6else

7 $p(a)=\frac{1}{m}$, for all $a\in A$;

8

9Sample $a_{win}\sim p$;

return _$a_{win}$_

Mechanism 4 Condorcet Loser Randomized Response (CLRR)

######  Proposition 8 ($\eta$-Condorcet Loser Criterion, Lower Bound)

Mechanism Mechanism 4 satisfies both ${\rm e}^{\epsilon}$-Condorcet loser
criterion and $\epsilon$-DP.

##  4 Tradeoff between Axioms under DP

This section investigates the 3-way tradeoffs among DP and voting axioms.
Concretely, we examine the distinction between the axiom tradeoffs in
classical social choice theory and the axiom tradeoffs under DP. Since even
the approximation of PC-efficiency cannot be achieved under DP, we only take
$\alpha$-Condorcet criterion, $\eta$-Condorcet loser criterion, $\beta$-Pareto
efficiency, and $\gamma$-SD-efficiency into consideration. On the one hand, we
capture the lower bounds of 3-way tradeoffs by proving the levels of
satisfaction to all the approximate axioms achieved by Mechanisms Mechanism
1-Mechanism 4, which are summarized in Table 2. All of the detailed results
and their proofs corresponding to Table 2 are shown in Appendix B.1.

Table 2: Lower bounds of 3-way tradeoff achieved by Mechanisms Mechanism 1-Mechanism 4. Voting rule |  $\beta$-Pareto efficiency |  $\gamma$-SD-efficiency |  $\alpha$-Condorcet criterion |  $\eta$-Condorcet loser criterion | Reference
---|---|---|---|---|---
BordaEXP | ${\rm e}^{\frac{n\epsilon}{2m-2}}$ | $\frac{{\rm e}^{\frac{n}{2}}+(m-2)\cdot{\rm e}^{\frac{n(m-2)}{4m-4}}}{{\rm e}^{\frac{n}{2}}+(m-1)\cdot{\rm e}^{\frac{n(m-2)}{4m-4}}}$ | ${\rm e}^{\left(\lfloor\frac{n}{2}\rfloor+1\right)\cdot\frac{m}{2m-2}-\frac{n}{2}}$ | ${\rm e}^{\frac{n}{2m-2}-\left(\lceil\frac{n}{2}\rceil-1\right)\frac{m}{2m-2}}$ | Mechanism Mechanism 1
RD-Anti | $1$ | $\frac{(m-1){\rm e}^{\epsilon}}{(m-1){\rm e}^{\epsilon}+1}$ | $\frac{\left(\lfloor\frac{n}{2}\rfloor-1\right){\rm e}^{\epsilon}+\lceil\frac{n}{2}\rceil+1}{n{\rm e}^{\epsilon}}$ | $\frac{\left(\lfloor\frac{n}{2}\rfloor-1\right){\rm e}^{\epsilon}+\lceil\frac{n}{2}\rceil+1}{n{\rm e}^{\epsilon}}$ | Mechanism Mechanism 2
CWRR | $1$ | $\frac{m-1}{m}$ | ${\rm e}^{\epsilon}$ | $1$ | Mechanism Mechanism 3
CLRR | $1$ | $\frac{(m-2){\rm e}^{\epsilon}+1}{(m-1){\rm e}^{\epsilon}+1}$ | $1$ | ${\rm e}^{\epsilon}$ | Mechanism Mechanism 4

On the other hand, we investigate the upper bounds of the 3-way tradeoff
between DP and each pairwise combination of the axioms. The results are listed
in Table 3. All of the missing proofs for the upper bounds in this section can
be found in Appendix B.2.

Table 3: Upper bounds of the 3-way tradeoffs among DP and axioms. Combination of axioms | Upper bounds | Reference
---|---|---
$\alpha$-Condorcet criterion - $\eta$-Condorcet loser criterion | $\alpha\cdot\eta\leqslant{\rm e}^{\epsilon}$ | Theorem 4.1
$\alpha$-Condorcet criterion - $\beta$-Pareto efficiency | $\alpha\cdot\beta^{m-2}\leqslant{\rm e}^{n\epsilon}$ | Theorem 4.2
$\eta$-Condorcet loser criterion - $\beta$-Pareto efficiency | $\eta\cdot\beta^{m-2}\leqslant{\rm e}^{n\epsilon}$ | Theorem 4.3
$\alpha$-Condorcet criterion - $\gamma$-SD-efficiency | $\gamma\leqslant\frac{\alpha+m-1-\alpha{\rm e}^{-n\epsilon}}{\alpha+m-1}$ | Theorem 4.4
$\eta$-Condorcet loser criterion - $\gamma$-SD-efficiency | $\gamma\leqslant\frac{{\rm e}^{n\epsilon}-\eta}{{\rm e}^{n\epsilon}}$ | Theorem 4.5
$\beta$-Pareto efficiency - $\gamma$-SD-efficiency | $\gamma\leqslant\frac{{\rm e}^{n\epsilon}-{\rm e}^{n\epsilon}\beta^{2-m}}{{\rm e}^{n\epsilon}-{\rm e}^{n\epsilon}\beta^{2-m}+\beta-1}$ | Theorem 4.6

Lower bounds of 3-way tradeoffs. In the previous section, we showed that
BordaExp, RD-Anti, CWRR, and CLRR currently reach the best achievable levels
of $\beta$-Pareto efficiency, $\gamma$-SD-efficiency, $\alpha$-Condorcet
criterion, and $\eta$-Condorcet loser criterion, respectively. Therefore,
these voting rules can provide the lower bounds of 3-way tradeoffs. For
example, CWRR satisfies $1$-Pareto efficiency and ${\rm
e}^{\epsilon}$-Condorcet criterion, which indicates that the 3-way tradeoff
among $\epsilon$-DP, $\beta$-Pareto efficiency, and $\alpha$-Condorcet
criterion has a lower bound, i.e., $\alpha={\rm e}^{\epsilon}$ and $\beta=1$.

Especially, the smoothed tradeoff between $\alpha$-Condorcet criterion and
$\eta$-Condorcet loser criterion can be achieved by the probability mixture
between CWRR (Mechanism Mechanism 3) and CLRR (Mechanism Mechanism 4),
presented in Mechanism Mechanism 5.

Input: Profile $P$, Noise Level $\epsilon$, Probability $\omega$

Output: Winning Alternative

2 Sample $x\sim\texttt{Bernouli}(\omega)$, i.e., $\mathbb{P}[x=1]=\omega$ and
$\mathbb{P}[x=0]=1-\omega$;

3 if  _$\omega=1$_ then

4 return $\text{CWRR}(P,\epsilon)$;

5

6else

7 return $\text{CLRR}(P,\epsilon)$;

8

Mechanism 5 Probability Mixture of CWRR and CLRR

Let $f_{\epsilon}^{\omega}(P)$ denote
$\omega\cdot\text{CWRR}(P,\epsilon)+(1-\omega)\cdot\text{CLRR}(P,\epsilon)$.
Then for any profile $P$,

$\displaystyle\mathbb{P}[f_{\epsilon}^{\omega}(P)=a]=\begin{cases}\frac{\omega\cdot{\rm
e}^{\epsilon}}{{\rm e}^{\epsilon}+m-1}+\frac{(1-\omega)\cdot{\rm
e}^{\epsilon}}{(m-1)\cdot{\rm e}^{\epsilon}+1},&a=\operatorname{CW}(P)\\\
\frac{\omega}{{\rm e}^{\epsilon}+m-1}+\frac{1-\omega}{(m-1)\cdot{\rm
e}^{\epsilon}+1},&a=\operatorname{CL}(P)\\\ \frac{\omega}{{\rm
e}^{\epsilon}+m-1}+\frac{(1-\omega)\cdot{\rm e}^{\epsilon}}{(m-1)\cdot{\rm
e}^{\epsilon}+1},&\text{otherwise}\end{cases}.$

Therefore, $f_{\epsilon}^{\omega}$ satisfies $\epsilon$-DP, $\alpha$-Condorcet
criterion, and $\eta$-Condorcet loser criterion, where

$\displaystyle\alpha=\frac{\frac{\omega\cdot{\rm e}^{\epsilon}}{{\rm
e}^{\epsilon}+m-1}+\frac{(1-\omega)\cdot{\rm e}^{\epsilon}}{(m-1)\cdot{\rm
e}^{\epsilon}+1}}{\frac{\omega}{{\rm
e}^{\epsilon}+m-1}+\frac{(1-\omega)\cdot{\rm e}^{\epsilon}}{(m-1)\cdot{\rm
e}^{\epsilon}+1}},\quad\eta=\frac{\frac{\omega}{{\rm
e}^{\epsilon}+m-1}+\frac{(1-\omega)\cdot{\rm e}^{\epsilon}}{(m-1)\cdot{\rm
e}^{\epsilon}+1}}{\frac{\omega}{{\rm
e}^{\epsilon}+m-1}+\frac{1-\omega}{(m-1)\cdot{\rm e}^{\epsilon}+1}}.$

In other words, $\alpha\eta={\rm e}^{\epsilon}$. Please refer to Appendix B.1
for the full results of lower bounds. In the rest of this section, we will
show the upper bounds of 3-way tradeoffs.

Tradeoff between Condorcet consistency. First of all, we discuss the tradeoff
between Condorcet criterion and Condorcet loser criterion. In fact, the
standard forms of these two axioms are compatible in standard social choice
theory (without DP), since for any given profile $P$, the Condorcet winner
$\operatorname{CW}(P)$ will never coincide with the Condorcet loser
$\operatorname{CL}(P)$. However, when DP is required, the best Condorcet
criterion ($\alpha={\rm e}^{\epsilon}$) is not compatible with the best
Condorcet loser criterion ($\eta={\rm e}^{\epsilon}$), since Condorcet winner
can sometimes be converted to Condorcet loser by reversing only one voter’s
vote (e.g., when $P_{-j}$ are tied, reversing $\succ_{j}$ exchanges Condorcet
winner and Condorcet loser). Formally, we have the following theorem.

###### Theorem 4.1

There is no voting rule satisfying $\epsilon$-DP, $\alpha$-Condorcet criterion
and $\eta$-Condorcet loser criterion with $\alpha\cdot\eta>{\rm
e}^{\epsilon}$.

Proof Sketch. Consider the profile $P$ ($n=2k+1$), where $k+1$ voters consider
$a_{1}\succ a_{2}\succ\cdots\succ a_{m}$ and $k$ voters consider $a_{m}\succ
a_{m-1}\succ\cdots\succ a_{1}$. Let $P^{\prime}$ be another profile
($n=2k+1$), where $k$ voters consider
$a_{1}\succ^{\prime}a_{2}\succ^{\prime}\cdots\succ^{\prime}a_{m}$, and $k+1$
voters consider $a_{m}\succ a_{m-1}\succ\cdots\succ a_{1}$. Then $P$ and
$P^{\prime}$ are neighboring, and
$\operatorname{CW}(P)=\operatorname{CL}(P^{\prime})$. By the definition of DP,
we have $\alpha\cdot\eta\leqslant{\rm e}^{\epsilon}$. ∎

Surprisingly, the upper bound shown in Theorem 4.1 coincides with the lower
bound achieved by the probability mixture of CWRR and CLRR. In other words,
this bound is tight for Condorcet criterion and Condorcet loser criterion,
which is visualized in Fig. 5. Note that this curve is only related to
$\epsilon$ and does not depend on $m$ or $n$ (number of alternatives and
voters).

Figure 5: The Tradeoff between Condorcet criterion and Condorcet loser
criterion under DP (upper bounds).

Condorcet consistency against Pareto efficiency. Secondly, we discuss the
3-way tradeoff between Condorcet consistency and Pareto efficiency. In
standard social choice theory, Pareto efficiency and Condorcet criterion are
compatible, since selecting the original Condorcet voting method (select
$\operatorname{CW}(P)$ as the winner with probability $1$) satisfies Pareto
efficiency. However, under the constraint of $\epsilon$-DP, $\alpha$-Condorcet
criterion only focuses on maximizing the winning probability of
$\operatorname{CW}(P)$, while $\beta$-Pareto efficiency requires us to
consider each pair of Pareto dominating and Pareto dominated alternatives. As
a result, when DP is required, the best Pareto efficiency and the best
Condorcet criterion may not be achieved simultaneously. Formally, the
following proposition illustrates their tradeoff under DP.

###### Theorem 4.2

There is no neutral voting rule $f\colon\mathcal{L}(A)^{n}\to A$ satisfying
$\epsilon$-DP, $\beta$-Pareto efficiency, and $\alpha$-Condorcet criterion
with $\alpha\beta^{m-2}>{\rm e}^{n\epsilon}$.

Proof Sketch. Let $P$ be a profile ($n=2k+1$), where $k+1$ voters consider
$a_{1}\succ a_{2}\succ\cdots\succ a_{m}$ and the rest $k$ voters consider
$a_{2}\succ\cdots\succ a_{m}\succ a_{1}$. Then $a_{1}$ is the Condorcet
winner, “dominating” any other alternatives, and each $a_{i}$ Pareto dominates
$a_{i+1}$, which can be visualized as follows.

$\displaystyle a_{1}\xrightarrow{\bf Condorcet~{}Winner}a_{2}\xrightarrow{\bf
Pareto}a_{3}\xrightarrow{\bf Pareto}\cdots\xrightarrow{\bf Pareto}a_{m}.$ (4)

Together with Equation (3), the proof can be completed. ∎

According to Proposition 1 and [23], the upper bounds of Pareto efficiency and
Condorcet criterion are ${\rm e}^{\frac{n}{m-1}}$ and ${\rm e}^{\epsilon}$,
respectively. Therefore, there is a natural upper bound of
$\alpha\beta^{m-2}$,

$\displaystyle\alpha\beta^{m-2}\leqslant\sup\alpha\cdot(\sup\beta)^{m-2}={\rm
e}^{\epsilon}\cdot{\rm e}^{\frac{n}{m-1}\cdot(m-2)}={\rm
e}^{1+n-\frac{n}{m-1}}.$ (5)

Then it follows that the upper bound in Proposition 4.2 is better than this
bound if and only if $n\leq m-1$. In fact, when $n>m-1$, Diagram (4) does not
suggest any incompatibility between Pareto efficiency and Condorcet criterion,
as the upper bound illustrated in Theorem 4.2 is even worse than the natural
bound shown in Equation (5).

Similarly, the same phenomenon also occurs to the Condorcet loser criterion.
Condorcet loser criterion is also compatible with Pareto efficiency in social
choice theory, since the Condorcet loser will never be a Pareto dominator.
However, due to the same reason as Condorcet criterion, the best
$\eta$-Condorcet loser criterion is not compatible with the best
$\beta$-Pareto efficiency under the same condition. Formally, we have the
following theorem, whose proof (as shown in Appendix B), is similar to
Proposition 4.2.

###### Theorem 4.3

There is no neutral voting rule $f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$
satisfying $\epsilon$-DP, $\beta$-Pareto efficiency, and $\alpha$-Condorcet
loser criterion with $\alpha\beta^{m-2}>{\rm e}^{n\epsilon}$.

Condorcet consistency against SD-efficiency. The relationship between SD-
efficiency and Condorcet criterion is also affected by $\epsilon$-DP. The next
proposition shows SD-efficiency is compatible with Condorcet criterion in
social choice theory. To simplify notations, we let Condorcet domain
$\mathcal{D}_{C}$ denote the set of all profiles $P$ where
$\operatorname{CW}(P)$ exists. We say a voting rule
$f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$ is a Condorcet method if it
satisfies $\mathbb{P}[f(P)=\operatorname{CW}(P)]=1$.

###### Proposition 9

Condorcet method satisfies SD-efficiency on $\mathcal{D}_{C}$.

Proof Sketch. Let $\mathsf{CM}$ denote Condorcet method. Given profile $P$,
suppose there is a lottery $\xi\in\mathcal{R}(A)$ that $\xi$ can SD-dominate
$\mathsf{CM}(P)$. Then, by the definition of SD, we can prove that
$\xi=\mathsf{CM}(P)$, a contradiction, which completes the proof. ∎

However, when DP is required, we can not achieve the best $\alpha$-Condorcet
criterion and $\gamma$-SD-efficiency simultaneously. The upper bound of this
tradeoff is shown in the following theorem.

###### Theorem 4.4

There is no neutral voting rule $f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$
satisfying $\epsilon$-DP, $\alpha$-Condorcet criterion, and $\gamma$-SD
efficiency with $\gamma>\frac{\alpha+m-1-\alpha{\rm
e}^{-n\epsilon}}{\alpha+m-1}$.

Proof Sketch. Consider the profile $P$, where all voters’ votes are exactly
the same, i.e., $a_{1}\succ_{j}a_{2}\succ_{j}\cdots\succ_{j}a_{m}$, for all
$j\in N$. Then $\operatorname{CW}(P)=a_{1}$, and the unique SD-efficient
lottery for $P$ is $\mathbbm{1}_{a_{1}}$. Further, $\mathbbm{1}_{a_{1}}$ can
$\frac{\alpha+m-1-\alpha{\rm e}^{-n\epsilon}}{\alpha+m-1}$-dominate any
$f(P)$, which completes the proof. ∎

The tradeoff curves between SD-efficiency and Condorcet criterion subject to
$\epsilon$-DP are shown in Fig. 7, where we set $m=5,n=10$.

Figure 6: Tradeoff curves between $\gamma$-SD-efficiency and
$\alpha$-Condorcet loser criterion (upper bounds).

Figure 7: Tradeoff curves between $\gamma$-SD-efficiency and $\eta$-Condorcet
loser criterion (upper bounds).

For Condorcet loser criterion, the situation is quite similar. On the one
hand, the compatibility between SD-efficiency and Condorcet loser criterion
without DP is proved via the maximal-lottery mechanism [11]. On the other
hand, there is little difference between optimizing the SD-efficiency and
minimizing the winning probability of the Condorcet loser under DP, which
leads to a 3-way tradeoff among them. Formally, we have the following theorem.

###### Theorem 4.5

There is no neutral voting rule $f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$
satisfying $\epsilon$-DP, $\eta$-Condorcet loser criterion, and $\gamma$-SD-
efficiency with $\gamma>\frac{{\rm e}^{n\epsilon}-\eta}{{\rm e}^{n\epsilon}}$.

Proof Sketch. Let $m>2$. Consider the profile $P$ with $k(m-2)$ voters
$(k\geqslant 1)$.

  * •

$k$ voters: $y\succ a_{1}\succ a_{2}\succ\cdots\succ x\succ a_{m-2}$,

  * •

$k$ voters: $y\succ a_{2}\succ a_{3}\succ\cdots\succ x\succ a_{1}$,

  * •

$k$ voters: $y\succ a_{3}\succ a_{4}\succ\cdots\succ x\succ a_{2}$,

  * •

$k$ voters: $\cdots$,

  * •

$k$ voters: $y\succ a_{m-2}\succ a_{1}\succ\cdots\succ x\succ a_{m-3}$.

Then $\mathbbm{1}_{y}$ can $\frac{{\rm e}^{n\epsilon}-\eta}{{\rm
e}^{n\epsilon}}$-SD-dominates $f(P)$, which completes the proof. ∎

The tradeoff curves between SD-efficiency and Condorcet loser criterion under
$\epsilon$-DP are shown in Fig. 7, where we set $m=5$ and $n=10$.

Pareto efficiency against SD-efficiency. Finally, we investigate the 3-way
tradeoff between Pareto efficiency, SD-efficiency, and DP. Although the
standard SD-efficiency implies the standard Pareto efficiency in social choice
theory, their best approximate bounds are incompatible under DP. Formally, we
have the following theorem.

###### Theorem 4.6

There is no neutral voting rule $f\colon\mathcal{L}(A)^{n}\to\mathcal{R}(A)$
satisfying $\epsilon$-DP, $\gamma$-SD-efficiency, and $\beta$-Pareto
efficiency with $\gamma>\frac{{\rm e}^{n\epsilon}-{\rm
e}^{n\epsilon}\beta^{2-m}}{{\rm e}^{n\epsilon}-{\rm
e}^{n\epsilon}\beta^{2-m}+\beta-1}$.

Proof Sketch. Consider the profile $P$, where
$a_{1}\succ_{j}a_{2}\succ_{j}\cdots\succ_{j}a_{m}$, for all $j\in N$. Then we
can show that any $f(P)$ will be $\frac{{\rm e}^{n\epsilon}-{\rm
e}^{n\epsilon}\beta^{2-m}}{{\rm e}^{n\epsilon}-{\rm
e}^{n\epsilon}\beta^{2-m}+\beta-1}$-SD-dominated by $\mathbbm{1}_{a_{1}}$ when
$f$ satisfies $\beta$-Pareto efficiency and $\epsilon$-DP, which completes the
proof. ∎

Figure 8: Tradeoff curves between $\beta$-Pareto efficiency and $\gamma$-SD-
efficiency under $\epsilon$-DP (upper bounds). Left: $m=5,n=10$. Right:
$m=5,n=20$.

The upper bounds proved in Theorem 4.6 are plotted in Fig. 8. From Fig. 5-8,
we found the following two observations.

  1. 1.

For Fig. 5-8, the curves with larger $\epsilon$ (which indicates a worse
privacy guarantee) are at the top-right of the curves with smaller $\epsilon$.
This indicates that the incompatibility between these axioms decreases when
the privacy guarantee gets worse.

  2. 2.

For Fig. 8, the curves with larger $n$ (more voters) are at the top-right of
the curves with smaller $n$. This indicates that the incompatibility decreases
as $n$ increases. The same conclusion also holds for other figures except Fig.
5, where the curves are irrelevant to $n$. Figures with different $n$’s for
other combinations of axioms are shown in Appendix C.

##  5 Conclusion and Future Work

This paper investigated the tradeoff between DP and varieties of voting
axioms, including Condorcet consistency and three efficiencies. We found that
DP is significantly incompatible with all of these axioms and quantified their
2-way tradeoffs against DP. Further, we explored the 3-way tradeoffs among DP
and these axioms. Our results show that the tradeoffs between axioms are
different with or without DP. It would be an interesting future direction to
study the tradeoffs between DP and other axioms. Besides, it’s also
interesting to develop tighter bounds for the tradeoffs.

## References

  * [1] Abadi, M., Chu, A., Goodfellow, I., McMahan, H.B., Mironov, I., Talwar, K., Zhang, L.: Deep learning with differential privacy. In: Proceedings of SIGSAC (2016)
  * [2] Aziz, H., Brandl, F., Brandt, F.: On the incompatibility of efficiency and strategyproofness in randomized social choice. In: Proceedings of AAAI (2014)
  * [3] Aziz, H., Brandl, F., Brandt, F.: Universal pareto dominance and welfare for plausible utility functions. Journal of Mathematical Economics 60, 123–133 (2015)
  * [4] Bassily, R., Groce, A., Katz, J., Smith, A.: Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In: Proceedings of FOCS (2013)
  * [5] Benadè, G., Gölz, P., Procaccia, A.D.: No stratification without representation. In: Proceedings of EC (2019)
  * [6] Berlioz, A., Friedman, A., Kaafar, M.A., Boreli, R., Berkovsky, S.: Applying differential privacy to matrix factorization. In: Proceedings of the 9th ACM Conference on Recommender Systems. pp. 107–114 (2015)
  * [7] Birrell, E., Pass, R.: Approximately strategy-proof voting. In: Proceedings of IJCAI (2011)
  * [8] Brandl, F., Brandt, F., Hofbauer, J.: Incentives for participation and abstention in probabilistic social choice. In: Proceedings of AAMAS (2015)
  * [9] Brandl, F., Brandt, F., Hofbauer, J.: Welfare maximization entices participation. Games and Economic Behavior 114, 308–314 (2019)
  * [10] Brandl, F., Brandt, F., Stricker, C.: An analytical and experimental comparison of maximal lottery schemes. In: Proceedings of IJCAI (2018)
  * [11] Brandt, F.: Rolling the Dice: Recent Results in Probabilistic Social Choice. In: Endriss, U. (ed.) Trends in Computational Social Choice, chap. 1. AI Access (2017)
  * [12] Dwork, C.: Differential privacy. In: Proceedings of ICALP (2006)
  * [13] Flanigan, B., Gölz, P., Gupta, A., Hennig, B., Procaccia, A.D.: Fair algorithms for selecting citizens’ assemblies. Nature 596(7873), 548–552 (2021)
  * [14] Flanigan, B., Gölz, P., Gupta, A., Procaccia, A.D.: Neutralizing self-selection bias in sampling for sortition. In: Proceedings of NeurlPS (2020)
  * [15] Friedman, A., Schuster, A.: Data mining with differential privacy. In: Proceedings of SIGKDD (2010)
  * [16] Gross, S., Anshelevich, E., Xia, L.: Vote until two of you agree: Mechanisms with small distortion and sample complexity. In: Proceedings of AAAI (2017)
  * [17] Hay, M., Elagina, L., Miklau, G.: Differentially private rank aggregation. In: Proceedings of SDM (2017)
  * [18] Hsu, J., Huang, Z., Roth, A., Roughgarden, T., Wu, Z.S.: Private matchings and allocations. SIAM Journal on Computing 45(6), 1953–1984 (2016)
  * [19] Kannan, S., Morgenstern, J., Rogers, R., Roth, A.: Private pareto optimal exchange. ACM Transactions on Economics and Computation 6(3-4), 1–25 (2018)
  * [20] Kohli, N., Laskowski, P.: Epsilon voting: Mechanism design for parameter selection in differential privacy. In: Proceedings of PAC (2018)
  * [21] Lee, D.T.: Efficient, private, and eps-strategyproof elicitation of tournament voting rules. In: Proceedings of IJCAI (2015)
  * [22] Li, T., Song, L., Fragouli, C.: Federated recommendation system via differential privacy. In: Proceedings of ISIT (2020)
  * [23] Li, Z., Liu, A., Xia, L., Cao, Y., Wang, H.: Differentially private condorcet voting. Proceedings of AAAI (2023)
  * [24] Liu, A., Lu, Y., Xia, L., Zikas, V.: How private are commonly-used voting rules? In: Proceedings of UAI (2020)
  * [25] Pai, M.M., Roth, A.: Privacy and mechanism design. ACM SIGecom Exchanges 12(1), 8–29 (2013)
  * [26] Plott, C.R.: Axiomatic social choice theory: An overview and interpretation. American Journal of Political Science 20(3), 511–596 (1976)
  * [27] Procaccia, A.D.: Can approximation circumvent gibbard-satterthwaite? In: Proceedings of AAAI (2010)
  * [28] Sarwate, A.D., Chaudhuri, K.: Signal processing and machine learning with differential privacy: Algorithms and challenges for continuous data. IEEE signal processing magazine 30(5), 86–94 (2013)
  * [29] Shang, S., Wang, T., Cuff, P., Kulkarni, S.R.: The application of differential privacy for rank aggregation: Privacy and accuracy. In: Proceedings of FUSION (2014)
  * [30] Torra, V.: Random dictatorship for privacy-preserving social choice. International Journal of Information Security 19(4), 1–9 (2019)
  * [31] Vasa, J., Thakkar, A.: Deep learning: Differential privacy preservation in the era of big data. Journal of Computer Information Systems 63(3), 608–631 (2023)
  * [32] Walsh, T., Xia, L.: Lot-based voting rules. In: Proceedings of AAMAS (2012)
  * [33] Wang, S., Du, J., Yang, W., Diao, X., Liu, Z., Nie, Y., Huang, L., Xu, H.: Aggregating votes with local differential privacy: Usefulness, soundness vs. indistinguishability. arXiv preprint arXiv:1908.04920 (2019)
  * [34] Xiao, D.: Is privacy compatible with truthfulness? In: Proceedings of ITCS (2013)
  * [35] Yan, Z., Li, G., Liu, J.: Private rank aggregation under local differential privacy. International Journal of Intelligent Systems 35(1), 1492–1519 (2020)
  * [36] Zhang, N., Li, M., Lou, W.: Distributed data mining with differential privacy. In: Proceedings of ICC (2011)

See pages 1-16 of appendix.pdf


# SLGPT: Using Transfer Learning to Directly Generate Simulink Model Files and
Find Bugs in the Simulink Toolchain

Sohil Lal Shrestha  Computer Science and Engineering DepartmentUniversity of
Texas at Arlington500 UTA BlvdArlingtonTexas76019USA and  Christoph Csallner
Computer Science and Engineering DepartmentUniversity of Texas at Arlington500
UTA BlvdArlingtonTexas76019USA

(2021)

###### Abstract.

Finding bugs in a commercial cyber-physical system (CPS) development tool such
as Simulink is hard as its codebase contains millions of lines of code and
complete formal language specifications are not available. While deep learning
techniques promise to learn such language specifications from sample models,
deep learning needs a large number of training data to work well. SLGPT
addresses this problem by using transfer learning to leverage the powerful
Generative Pre-trained Transformer 2 (GPT-2) model, which has been pre-trained
on a large set of training data. SLGPT adapts GPT-2 to Simulink with both
randomly generated models and models mined from open-source repositories.
SLGPT produced Simulink models that are both more similar to open-source
models than its closest competitor, DeepFuzzSL, and found a super-set of the
Simulink development toolchain bugs found by DeepFuzzSL.

Cyber-physical system development, Simulink, tool chain bugs, deep learning,
programming language modeling, GPT-2

††copyright: rightsretained††journalyear: 2021††conference: Evaluation and
Assessment in Software Engineering; June 21–23, 2021; Trondheim,
Norway††booktitle: Evaluation and Assessment in Software Engineering (EASE
2021), June 21–23, 2021, Trondheim, Norway††doi:
10.1145/3463274.3463806††isbn: 978-1-4503-9053-8/21/06††ccs: Software and its
engineering Software testing and debugging††ccs: Software and its engineering
Model-driven software engineering††ccs: Computing methodologies Transfer
learning††ccs: Information systems Language models

##  1\. Introduction

Finding bugs in a commercial cyber-physical system (CPS) development tool such
as Simulink is hard as its codebase contains millions of lines of code and
complete formal language specifications are not available. While deep learning
techniques promise to learn such language specifications from sample models,
deep learning needs a large number of training data to work well and the
closest related deep learning tool DeepFuzzSL (Shrestha et al., 2020) is
severely limited by the relatively small number of available training models.

Testing CPS development tools is important as engineers design and develop
dynamic safety-critical systems using these development tools. For example,
MathWorks’s Simulink is widely used in industry such as automotive, medical,
and aerospace (Zheng et al., 2017). Engineers use Simulink to design,
simulate, test, and generate embedded code from CPS models and deploy it to
end-user hardware. At worst a subtle bug in the Simulink tool chain could
result in unexpected behaviour in safety-critical applications such as in cars
or airplanes.

Given the complexity of the Simulink language, training a deep learning tool
such as DeepFuzzSL from scratch would require a very large number of training
models. However relatively few open source Simulink models are available.
While random model generators such as SLforge (Chowdhury et al., 2018) could
fill in some of these gaps, it is not clear how well SLforge can cover the
various features (and their combinations) of the Simulink language.

Given the limited amount of Simulink training models, this paper proposes to
use transfer learning for generating Simulink models. Transfer learning is a
promising alternative to learning from scratch, as it leverages a machine
learning model trained on a large set of related training data. We can then
use a relatively small set of Simulink-specific training data to fine-tune
such a pre-trained model for generating Simulink models.

Here, we fine-tune the Generative Pre-trained Transformer 2 (GPT-2) (Radford
et al., 2019) model using both randomly generated models and models we mined
from the open-source repositories GitHub and MATLAB Central. Our experimental
results suggest that GPT-2 generated Simulink models are of higher quality and
address the shortcomings of earlier deep learning approaches. SLGPT also found
a wider range of similar bugs found by DeepFuzzSL in Simulink versions R2018b,
R2019b, and R2020b confirmed by Mathworks Support. To summarize, the paper
makes the following contributions.

  * •

SLGPT is the first use of transfer learning for generating graphical block-
diagram models.

  * •

The paper implements SLGPT for Simulink, collects a training set of 400 open-
source Simulink models, and compares SLGPT with the closest related tool
DeepFuzzSL.

  * •

SLGPT-created models were more similar to open-source models and SLGPT found a
super-set of the Simulink development toolchain bugs DeepFuzzSL found.

  * •

The SLGPT implementation, parameter settings, and training sets are open-
source (Shrestha, 2021).

##  2\. Background

Simulink (MathWorks Inc., 2021) is a powerful commercial tool-chain for model-
based design and has become a de-facto standard in several domains such as
automotive and aerospace. An engineer typically designs a model via Simulink’s
graphical modeling environment. A Simulink model is a (potentially
hierarchical) _block diagram_ , where each block represents equations or
modeling components. A Simulink user can also define custom blocks in custom
“native” code using the S-function interface. Simulink typically stores a
model in its proprietary model file format, i.e., as a structured ASCII file
that contains keywords and parameter-value pairs (many of which are case-
sensitive) (Inc., 2007). Figure 1 shows a flat Simulink model and parts of its
model file representation.

Figure 1. Simulink model (left) and excerpt of its 1.1k line (Simulink-
generated) model file representation (right).

Depending on the block type, each block can accept input via input ports,
perform some operation on its inputs, and pass output via output ports to
other blocks through (directed) edges. Simulink users can add blocks from
various built-in libraries and toolboxes. A source block generates signals in
a Simulink model while a sink block is used to display or output
signals(MathWorks Inc, 2021). A model’s maximum source-to-sink path length is
the longest directed non-circular path from a source to a sink node (and
includes source and sink).

When a user opens a model, Simulink’s parser performs its checks and prevents
corrupt models from opening. Once opened, a user can compile and then simulate
the model, where the tool chain uses configurable solvers to iteratively solve
the model’s network of mathematical relations via numerical methods, yielding
for each output block a sequence of outputs. After simulation, the user may
use Simulink’s embedded code generation workflow for deployment on a target
platform.

###  2.1. Transfer Learning & NLP Language Models

_Transfer learning_ (Pan and Yang, 2009) is a promising technique for
generating Simulink models, as transfer learning can work well in scenarios
that suffer from relatively small amounts of training data. Transfer learning
achieves this by using a machine learning model trained for a source task or
domain (“pre-training”, e.g., programs in any programming language) as a
starting point to train on a different but related target task or domain
(“fine-tuning”, i.e., Simulink models). This works well if pre-training uses
huge amounts of training samples, learns features common to both tasks, and
fine-tuning can apply the learned knowledge on a target task. Successful
applications include computer vision, where large datasets such as ImageNet
(Deng et al., 2009) have been used to pre-train deep learning models that are
later fine-tuned for tasks such as image segmentation.

In natural language processing (NLP), language modeling is the use of
statistical techniques to determine the probability of a given word sequence.
A language model basically estimates the probability of a word based on the
words already observed in a sequence. An effective language model not only
understands language structure (syntax) but also long-term context
(semantics). For example, a Simulink language model should predict tokens that
are both syntactically correct and produce valid connections between blocks
(e.g., respecting Simulink language rules on define-before-use).

Transfer learning in natural language processing is relatively new. ULMFiT
presents a specific training schedule enabling transfer learning using LSTMs
(Howard and Ruder, 2018). GPT-2 uses transformer decoder as a building block
and trains a language model on the WebText dataset (Radford et al., 2019).
Using transformers instead of LSTMs allows longer-range context capture.
GPT-2’s byte pair encoded vocabulary also supports Unicode (and does not
require common pre-processing steps such as lower-casing and stemming). So
GPT-2 is a great candidate to learn Simulink model files.

##  3\. Overview and Design

Figure 2. SLGPT obtains Simulink models from a random generator and open-
source repositories, simplifies them, and uses them to adapt GPT-2 for finding
Simulink crashes.

Figure 2 gives an overview of SLGPT. To obtain a variety of Simulink models
for machine learning, we both ran the random model generator SLforge and mined
open-source repository sites, i.e., GitHub and MATLAB Central. Since GitHub
currently does not treat Simulink as a searchable language, we used the GitHub
API with ”Simulink” as search keyword. Since MATLAB Central does not provide
an API for downloading Simulink models, we used its RSS
feed111https://www.mathworks.com/company/rss.html to heuristically construct
Simulink project download links.

We want our training corpus to only contain valid Simulink models. So we
automate the process of checking if a Simulink model is compilable on
Simulink. The validity checker also helps detect any crashes caused by an
input Simulink model, which is then manually reviewed and reported to the
developers. To limit the number of Simulink language features in our training
data, we only used flat models that do not have additional toolbox or library
dependencies, yielding 400 valid open-source Simulink models for training.

###  3.1. Training Data Preparation: Simplification

SLGPT simplifies training models to (1) remove model features we currently
cannot handle given the limited number of training models and to (2)
restructure models to fit GPT-2’s learning style. While both simplification
types may change model semantics, SLGPT compensates for type-2 simplifications
(restructuring), by rewriting generated models into equivalent Simulink-
compliant style.

Figure 3. Figure 1 Simulink model and excerpt of its model file, after SLGPT
simplified it to 45 lines, by removing layout info, restructuring code via
BFS, etc.

Figure 4. Figure 3 Simulink model and excerpt of its 45 line model file, after
SLGPT restored it to Simulink-compliant style (plus manual layout changes for
readability).

Specifically, we pre-process the model file to remove macros, default
configuration settings, comments, duplicate white spaces, annotations, and
block-position information. We similarly rewrite model identifiers (e.g.,
block names) to short but unique names (a, b, c, …, aa, ab, ac, …), based on
their appearance order in our restructured model file.

The ASCII style in which Simulink saves its models to files is problematic for
state-of-the-art deep learning language models, as Simulink files are long and
verbose. Furthermore, these files also list all nodes before all edges. Taken
together, this is a poor fit for current language models, which model context
with a text window of limited size.

1

Require: $source\\_blks$ $(S)$, $other\\_blks$ $(B)$, $graph\\_info$ $(G)$

Result: BFS-rewrite of Simulink model file ($C_{BFS}$)

2 while  _S $\neq\emptyset$ and or $B\neq\emptyset$_ do

3 Q = empty queue

4 b = remove element from $(S\neq\emptyset)?S:B$

5 add b to back of Q

6 while  _Q $\neq\emptyset$_ do

7 $curb$ = pop element from front of $Q$

8 if  _$curb\notin C_{BFS}$_ then

9 add $curb$ to $C_{BFS}$

10 remove $curb$ from $B$

11 $B_{nei},E_{nei}$ = $curb$’s neighbour blocks, edges in $G$

12 forall  _$e\in E_{nei}$_ do

13 if  _ $e\notin$ $C_{BFS}$_ then

14 add $e$ to $C_{BFS}$

15 end if

16

17 end forall

18 forall  _$b\in B_{nei}$_ do

19 if  _ $b\notin$ $C_{BFS}$_ then

20 add $b$ to back of $Q$

21 end if

22

23 end forall

24

25 end if

26

27 end while

28

29 end while

Algorithm 1 Restructuring Simulink model. “Neighbour” refers to both incoming
and outgoing blocks and edges.222Changes from published version: In Algorithm
1, while condition in line 1 changed from “and“ to “or“

To make such files easier to learn, SLGPT’s Algorithm-1 rewrites these files
in a breath-first search (BFS) style. Specifically, we first parse the
Simulink model file and maintain an adjacency representation of the Simulink
model in the $graph\\_info$ map, which maintains two disjoint sets:
$source\\_blks$ has blocks with $in\\_degree=0$ and other $other\\_blks$ has
all remaining blocks. Algorithm-1’s outer loop iterates over both $S$ and $B$
as some Simulink models have dangling blocks (blocks that are not source
blocks and are not connected to any other block). Also some models (especially
from SLforge) have no source blocks because they have cycles.

###  3.2. Synthesizing Simulink Models with GPT-2

Given the complexity of the Simulink language, generating valid Simulink model
files is an ambitious task for unsupervised machine learning, especially given
our small amounts of training data. Instead of training from scratch, we thus
use the pre-trained language model GPT-2. GPT-2 is a good fit, as it employs
byte pair encoding to construct its vocabulary, meaning all tokens in a
Simulink model file can be mapped to the vocabulary set.

Second, GPT-2’s architecture is based on the transformer architecture (Vaswani
et al., 2017), which has benefits over a traditional LSTM architecture, as
transformers avoid recursive computation by processing sequences as a whole
and learning relationships between tokens by using multi-head attention
mechanisms and positional embeddings. This enables better prediction, which is
typically lost with LSTM over long-term dependencies in the text.

SLGPT’s Algorithm-2 iteratively samples from the fine-tuned language model to
generate Simulink model files. We seed the model with the sequence “Model {”
and then sample token by token. In this early project stage we followed the
best sampling techniques of DeepFuzzSL (nucleus or top-p sampling (Holtzman et
al., 2019)). Specifically, given a start text $S$, sampling parameters nucleus
$N$ and temperature $T$, the fine-tuned GPT-2 model $G$ computes the
probability mass function $PMF$ representing the probability distribution of
all tokens in the vocabulary. We normalize the $PMF$ after scaling with $T$ to
introduce randomness. To reduce the size of next plausible tokens, we select
the smallest subset of $PMF$ such that the sum of all values in the subset is
greater than $N$. The normalized subset $PMF$ is then used to perform a
multinomial experiment to choose the next token.

Require: Fine-tuned GPT-2 model $(G)$, temperature $(T)$, nucleus $(N)$

Result: Completed sample string S

1 $S$ = ”Model { ”

2 while  _¡endoftext¿ $\notin S$_ do

3 PMF = get_distribution_of_next_predicted_tokens$(G,S)$

4 Scale the obtained PMF by $T$

5 Sort PMF in descending order

6 Subset PMF such that the smallest possible set sum is greater than $N$

7 $R=$ Perform multinomial experiment on subset PMF

8 $S=S+R$

9

10 end while

Algorithm 2 Sampling a candidate Simulink model from a seed text.

Since the resulting Simulink model file $S$ is (as the training samples) in
BFS style (as Simulink expects block definitions before edge definitions in a
model file),

SLGPT restructures $S$ such that the model defines all blocks before defining
edges. To continue the Figure 1 example, if we assume Figure 3 shows a model
produced by Algorithm-2, SLGPT then reorders its element definitions to the
Simulink-friendly style of Figure 4.

In lieu of full differential testing, SLGPT just uses its validity checker to
detect crashes of the Simulink tool. We then manually investigate each crash,
judge if a crash is an example of a known bug, and report representatives of
the remaining crashes to MathWorks Customer Support.

##  4\. Initial Experience

While a full evaluation is future work, this paper compares SLGPT to its most
closely related competitor, i.e., DeepFuzzSL.

We first used DeepFuzzSL’s evaluation setup of a SLforge-generated training
corpus, in which each Simulink model has 5–57 blocks. SLGPT’s pre-processing
reduced the number of tokens by 75%, yielding 987 Simulink models with a total
of 0.5M lines. We ran a related experiment on the 400 open-source Simulink
models.

SLGPT’s pre-processing removed the 23 of the 400 models that only contained
annotation blocks, yielding 3.5k blocks represented in 87k lines.

OpenAI has released four different sizes of pre-trained GPT-2 models ranging
from 0.1 to 1.5 billion parameters. To limit computational resource needs, for
these initial experiments we used the smallest model. We fine-tuned the GPT-2
model remotely in the high performance Texas Advanced Computing Center
(TACC)’s Maverick 2 cluster (TACC at The University of Texas at Austin, 2021).
We ran our experiments on a single Maverick 2 GTX
node333https://portal.tacc.utexas.edu/user-guides/maverick2 of two 8-core 2.1
Ghz Intel Xeon processors, 128 GB RAM, and 4 NVidia 1080-TI GPUs.

As in DeepFuzzSL’s experimental setup we used the Adam optimizer (here to
fine-tune the GPT-2 model). We could not use a mini batch size of 64 as it
triggered out-of-memory errors on TACC. Instead, we used batch size of 1. To
compensate for the low batch size, we set the learning rate to 0.00002 (vs.
0.002) and trained SLGPT for 24 hours on SLforge-generated models and in a
separate experiment for 24 hours on the open-source models.

We trained DeepFuzzSL on the same hardware as SLGPT but otherwise as described
in its paper, i.e., for 400 epochs with mini batch size 64. While this “only”
took about 6.5 hours, DeepFuzzSL’s loss function tapered off after 100–150
epochs (so it was not learning much after that). While sampling, we let
DeepFuzzSL run until it either emits a terminating token or reached 15k tokens
(corresponding to the largest open-source training model). In the latter case
the resulting file typically contained several model-start sequences. When
opening such a file, Simulink and our counts just ignore all but the first
model. We use the following research questions.

RQ1:

Can SLGPT generate valid Simulink models? How does the structure of DeepFuzzSL
and SLGPT generated Simulink models compare to open-source models?

RQ2:

How do DeepFuzzSL and SLGPT compare in the bugs they find in the Simulink tool
chain?

###  4.1. SLGPT Can Generate Valid and More Realistic Simulink Models (RQ1)

Earlier approaches were evaluated in terms of the validity of generated models
and their bug-finding ability (e.g., in SLForge, SLEMI, and DeepFuzzSL
(Chowdhury et al., 2018, 2020; Shrestha et al., 2020)). In addition, to
evaluate the quality of a model generator, we compare structural properties of
the generated Simulink models against open-source Simulink models.
Specifically, we use the number of nodes in the generated Simulink model and
metrics based on the common notion of a connected subgraph (i.e., a subgraph
in which each node is connected to at least one other node in the subgraph).

To explore SLGPT’s ability to generate valid Simulink models, we continuously
generate Simulink models for 24 hours. Sampling the version trained on
SLforge-generated models yielded 2,912 Simulink models of which 43% compiled.
The version trained on open-source models yielded 709 Simulink models of which
47% compiled. The most frequent cause of compile errors include data type
mismatches between two connecting blocks and assigning an alphanumeric value
to a numeric block attribute. Most of these could be fixed easily by adding
data type conversion blocks to the model and changing alphanumeric to numeric
values.

We trained DeepFuzzSL on the same training sets as SLGPT and sampled around 1k
samples each with DeepFuzzSL’s sampling heuristics. To make the comparison
consistent we removed DeepFuzzSL’s output token bound and allowed DeepFuzzSL
to generate complete Simulink model files. Of around 1,200 DeepFuzzSL-
generated models trained on Slforge-generated models, 89% compiled, closely
aligning with the 90% validity rate reported in the DeepFuzzSL paper. On the
other hand, out of 1,024 DeepFuzzSL-generated Simulink models trained on open-
source models only 42% compiled.

The valid models generated by DeepFuzzSL were not as similar to the training
models as SLGPT-generated valid models. Figure 6 compares these models along
four metrics. For example, DeepFuzzSL-generated models tend to have many
subgraphs that only contain 2 blocks, many blocks have unconnected input and
output ports, and there is often no connection between source and sink.

###  4.2. SLGPT Found Superset of Bugs DeepFuzzSL Found (RQ2)

Trained on SLforge-generated Simulink models, from nearly 3k SLGPT-generated
models 13 crashed Simulink. Upon analysis these 13 instances belong to the
same two bug categories DeepFuzzSL found (MathWorks confirmed both types as
known bugs). The first issue is a Simulink crash while opening a model. The
second issue is Simulink opening a model but crashing while compiling the
model.

Trained on our open-source models, 30 DeepFuzzSL-generated and 14 SLGPT-
generated models crashed Simulink while compiling. 13 of the SLGPT-generated
(and all DeepFuzzSL-generated) models get rejected by Simulink R2018b but
crash version R2020b (case 04777147). The last one crashes R2018b but is
accepted by R2020b (case 04767975). Following are brief summaries of these two
cases.

####  4.2.1. Case 04777147 (Non-bug)

This SLGPT-generated Simulink model triggered an interesting behavior, where
Simulink R2018b rejects it as corrupt and the newer R2020b version crashes.
MathWorks told us that the way Simulink parses MDL files has changed since
R2020a, which may have caused the crash. As it is impossible to create this
model via Simulink’s graphical editor or standard API, MathWorks Support
marked it as a non-bug. DeepFuzzSL-generated models triggered similar Simulink
crashes.

####  4.2.2. Case 04767975 (Known bug)

Figure 5. Scope (left) and Floating Scope (right).

Figure 5 shows two types of Simulink scope blocks: Scope and Floating Scope.
Floating Scope does not have any physical ports while Scope does. A SLGPT-
generated model set floating parameter off (indicating that it is a normal
scope) while setting the ports attribute to 0 (instead of a vector), causing
the crash. Simulink’s graphical editor or standard API cannot create this
model. This issue exists in R2018b and has been fixed in later versions.
DeepFuzzSL did not trigger this bug.

Figure 6. Training models (top), DeepFuzzSL-generated models (middle), and
SLGPT-generated models (bottom). Left y-axis is for open-source training
models and right y-axis is for SLforge-generated training models. X-axis is
(valid) Simulink models sorted in ascending order for metric (from left to
right column): Blocks per model, connected subgraphs, blocks in largest
connected subgraph, maximum path length from a source to a sink block. Metrics
of SLGPT-generated models are overall closer to the training models than
DeepFuzzSL-generated models.

##  5\. Related Work

Small training datasets are a common problem in deep learning applications.
Researchers thus often use synthetic datasets (Fakhoury et al., 2018). Robbes
et. al. showed a promising avenue to alleviate the dataset problem by using
transfer learning (Robbes and Janes, 2019), i.e., that a small natural-
language software engineering dataset can be used to improve sentiment
analysis using pre-trained neural networks.

In the CPS domain, Chowdhury et al. developed a randomized differential
testing tool using semi-formal specifications to test the Simulink toolchain
(Chowdhury et al., 2018). Subsequently SLEMI generated semantic-preserving
mutants of a seed model for differential testing of the Simulink toolchain
(Chowdhury et al., 2020). While these approaches are tightly coupled with
Simulink, SLGPT is only loosely coupled and does not rely on explicit Simulink
language specifications.

Success of modeling natural language using deep learning has garnered interest
to model source code for program generation. Researchers have used language
models to improve software engineering task such as code completion and code
clone detection (Raychev et al., 2014; Hammad et al., 2020; Chen and Zhou,
2018). For compiler validation, DeepSmith (Cummins et al., 2018), DSmith (Xu
et al., 2020), and DeepFuzz (Liu et al., 2019) uses deep learning based
sequence modeling to model the OpenCL and C languages from real world programs
and found compiler bugs. All of these approaches target languages with
complete available specifications while we target Simulink, which does not
have such a specification publicly available.

The most closely related work DeepFuzzSL (Shrestha et al., 2020) use LSTM
architecture to model Simulink. However they only train on synthetic models,
citing the need for a larger training corpus. In contrast, we use a pre-
trained language model and fine-tune it with open-source Simulink models.

Transfer learning for source code modeling is relatively new. Benito et al.
studied the use of pre-trained models for source code generation and
completion (Cruz-Benito et al., 2021). Hussain et al. proposed a transfer-
learning based attention learner approach to improve code suggestions (Hussain
et al., 2020). While earlier work focused on traditional languages we focus on
a graphical CPS language.

##  6\. Conclusions

Testing a commercial CPS development tool such as Simulink is hard as its
codebase contains millions of lines of code and complete formal language
specifications are not available. While deep learning techniques promise to
learn such language specifications from sample models, deep learning needs a
large number of training data to work well. SLGPT addressed this problem by
using transfer learning, to leverage the powerful GPT-2 model that has been
pre-trained on a large set of training data. SLGPT adapted GPT-2 to Simulink
with both randomly generated models and models mined from open-source
repositories. SLGPT produced Simulink models that are both more similar to
open-source models than its closest competitor, DeepFuzzSL, and found a super-
set of the Simulink development toolchain bugs found by DeepFuzzSL.

###### Acknowledgements.

The authors acknowledge the Texas Advanced Computing Center (TACC) at The
University of Texas at Austin for providing HPC resources that have
contributed to the research results reported within this paper. Christoph
Csallner has a potential research conflict of interest due to a financial
interest with Microsoft and The Trade Desk. A management plan has been created
to preserve objectivity in research in accordance with UTA policy. This
material is based upon work supported by the National Science Foundation (NSF)
under Grant No. 1911017 and a gift from MathWorks.

## References

  * (1)
  * Chen and Zhou (2018) Qingying Chen and Minghui Zhou. 2018.  A neural framework for retrieval and summarization of source code. In _ASE 2018_.
  * Chowdhury et al. (2018) Shafiul Azam Chowdhury, Soumik Mohian, Sidharth Mehra, Siddhant Gawsane, Taylor T. Johnson, and Christoph Csallner. 2018.  Automatically finding bugs in a commercial cyber-physical system development tool chain with SLforge. In _Proc. 40th ACM/IEEE International Conference on Software Engineering (ICSE)_. 981–992.
  * Chowdhury et al. (2020) Shafiul Azam Chowdhury, Sohil L Shrestha, Taylor T. Johnson, and Christoph Csallner. 2020.  SLEMI: Equivalence modulo input (EMI) based mutation of CPS models for finding compiler bugs in Simulink. In _ICSE_. ACM, 335–346.
  * Cruz-Benito et al. (2021) Juan Cruz-Benito, Sanjay Vishwakarma, Francisco Martin-Fernandez, and Ismael Faro. 2021.  Automated Source Code Generation and Auto-Completion Using Deep Learning: Comparing and Discussing Current Language Model-Related Approaches.  _AI_ 2, 1 (2021), 1–16.  https://doi.org/10.3390/ai2010001
  * Cummins et al. (2018) Chris Cummins, Pavlos Petoumenos, Alastair Murray, and Hugh Leather. 2018.  Compiler fuzzing through deep learning. In _ISSTA 2018_.
  * Deng et al. (2009) J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. 2009.  ImageNet: A Large-Scale Hierarchical Image Database. In _CVPR09_.
  * Fakhoury et al. (2018) Sarah Fakhoury, Venera Arnaoudova, Cedric Noiseux, Foutse Khomh, and Giuliano Antoniol. 2018\.  Keep it simple: Is deep learning good for linguistic smell detection?. In _SANER’18_. IEEE, 602–611.
  * Hammad et al. (2020) Muhammad Hammad, Önder Babur, Hamid Abdul Basit, and Mark van den Brand. 2020.  DeepClone: Modeling Clones to Generate Code Predictions. In _ICSR 2020_.
  * Holtzman et al. (2019) Ari Holtzman, Jan Buys, Maxwell Forbes, and Yejin Choi. 2019\.  The Curious Case of Neural Text Degeneration.  _CoRR_ abs/1904.09751 (2019).  arXiv:1904.09751
  * Howard and Ruder (2018) Jeremy Howard and Sebastian Ruder. 2018.  Universal Language Model Fine-tuning for Text Classification. In _ACL 2018_. ACL, 328–339.
  * Hussain et al. (2020) Yasir Hussain, Zhiqiu Huang, Yu Zhou, and Senzhang Wang. 2020\.  Deep Transfer Learning for Source Code Modeling.  _Int. J. Softw. Eng. Knowl. Eng._ 30, 5 (2020).
  * Inc. (2007) MathWorks Inc. 2007\.  _Simulink® 7 Reference_.  Chapter 9, Pg. 9–2 – Pg.9–10.
  * Liu et al. (2019) Xiao Liu, Xiaoting Li, Rupesh Prajapati, and Dinghao Wu. 2019\.  DeepFuzz: Automatic Generation of Syntax Valid C Programs for Fuzz Testing. In _Proc. 33rd AAAI Conference on Artificial Intelligence (AAAI)_. AAAI, 1044–1051.
  * MathWorks Inc (2021) MathWorks Inc. 2021\.  _Block Libraries_.  Retrieved April 27, 2021 from https://www.mathworks.com/help/simulink/block-libraries.html
  * MathWorks Inc. (2021) MathWorks Inc. 2021\.  _MATLAB & Simulink_.  Retrieved April 27, 2021 from https://www.mathworks.com/products/simulink.html/
  * Pan and Yang (2009) Sinno Jialin Pan and Qiang Yang. 2009.  A survey on transfer learning.  _IEEE Transactions on knowledge and data engineering_ 22, 10 (2009), 1345–1359.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019\.  Language Models are Unsupervised Multitask Learners.  (2019).
  * Raychev et al. (2014) Veselin Raychev, Martin T. Vechev, and Eran Yahav. 2014\.  Code completion with statistical language models. In _PLDI 2014_. 419–428.
  * Robbes and Janes (2019) Romain Robbes and Andrea Janes. 2019.  Leveraging small software engineering data sets with pre-trained neural networks. In _Proc. 41st International Conference on Software Engineering: New Ideas and Emerging Results, ICSE (NIER)_. IEEE.
  * Shrestha (2021) Sohil L Shrestha. 2021\.  _50417/SLGPT_.  https://doi.org/10.5281/zenodo.4734223
  * Shrestha et al. (2020) Sohil Lal Shrestha, Shafiul Azam Chowdhury, and Christoph Csallner. 2020.  DeepFuzzSL: Generating models with deep learning to find bugs in the Simulink toolchain. In _DeepTest 2020_. ACM.
  * TACC at The University of Texas at Austin (2021) TACC at The University of Texas at Austin. 2021.  _Texas Advanced Computing Center - Homepage_.  Retrieved April 27, 2021 from https://www.tacc.utexas.edu/
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017\.  Attention is All you Need. In _30th Annual Conference on Neural Information Processing Systems_.
  * Xu et al. (2020) Haoran Xu, Yongjun Wang, Shuhui Fan, Peidai Xie, and Aizhi Liu. 2020.  DSmith: Compiler Fuzzing through Generative Deep Learning Model with Attention. In _2020 International Joint Conference on Neural Networks, IJCNN 2020_.
  * Zheng et al. (2017) Xi Zheng, Christine Julien, Miryung Kim, and Sarfraz Khurshid. 2017.  Perceptions on the State of the Art in Verification and Validation in Cyber-Physical Systems.  _IEEE Systems Journal_ 11, 4 (2017), 2614–2627.