# Scarce Resource Allocations That Rely On Machine Learning
Should Be Randomized

Shomik Jain  Kathleen Creel  Ashia Wilson

###### Abstract

Contrary to traditional deterministic notions of algorithmic fairness, this
paper argues that fairly allocating scarce resources using machine learning
often requires randomness. We address why, when, and how to randomize by
proposing stochastic procedures that more adequately account for all of the
claims that individuals have to allocations of social goods or opportunities.

fairness, randomness, systemic exclusion

##  1 Introduction

Sometimes resources or opportunities are scarce: jobs, welfare benefits, or
life-saving medicines cannot be divided among all those who deserve them.
Worse yet, it is often unclear which individuals are most deserving. Perhaps
they all are. Decision-makers hope to use algorithmic systems to allocate
scarce resources and goods fairly. But without careful attention, it is easy
for algorithms to replicate or amplify the biases and inequalities in their
training data.

The fair machine learning community has developed sophisticated theoretical
and formal tools to reduce algorithmic bias, increase fairness, and promote
justice. However, these tools are almost exclusively deterministic. For
example, employers with more qualified applicants than job openings often rely
on hiring algorithms to screen applicants for interviews (Raghavan et al.,
2020). These algorithms assign a score or ranking to candidates. Employers
then threshold these scores or rankings to deterministically pick candidates
to interview. Similarly, healthcare providers often have a limited supply of
life-saving medical resources such as ventilators, therapeutics, or organs.
Patients are often triaged based on algorithms that predict their survival
rate or life expectancy post-treatment (Chin et al., 2023). Most existing work
on algorithmic fairness relies on deterministic algorithms to incorporate
fairness. Once algorithmic bias has been reduced to the extent possible, the
algorithm allocates resources to the top candidate(s). If Alice is the top-
ranked candidate for every job or has the most expected quality-adjusted life-
years, she should deterministically receive the job offer or organ every time.

Recent works on arbitrariness and fairness suggest that even counterfactual
non-determinism can be unfair. If there exist many possible models with
similar predictive performance but slightly different decisions on
individuals, a state of affairs called “predictive multiplicity” (Marx et al.,
2020) or “model multiplicity” (Black et al., 2022), it is unfair to naively
pick one of the models for our decision-making algorithm (Hsu & Calmon, 2022).
Instead, we should reduce multiplicity by altering the training process to
reduce the variance that leads to diverging predictions (Cooper et al., 2023),
especially on under-represented individuals (Ganesh et al., 2023), iterate
until predictions agree about individuals (Roth et al., 2023) or even abstain
from making predictions on some people altogether (Cooper et al., 2023).

While sharing the goal of reducing bias and increasing fairness, this work
argues that the fair machine learning community has underutilized non-
determinism and randomization as tools to achieve fairness. In some settings
that involve algorithmic decision-making, we contend that non-determinism is
required for fair outcomes. In what follows, we first motivate why and when
fairness requires randomization. We adopt philosopher John Broome’s concept of
the value of lotteries in fairness to argue that randomization is needed in
scarce resource settings to respect the claims that individuals have to
resources, even if they do not receive them, by giving each person with a
claim a chance.

Second, we argue that because algorithmic predictions involve uncertainty, it
is unfair to those on whom we make mistakes to deterministically commit to
those mistakes. This is especially true in multi-shot contexts in which each
individual is affected by multiple decision-makers or a series of decisions
over time. Across an ecosystem of multiple decision-makers, consistently
allocating scarce resources and goods to the same candidate(s) can be sub-
optimal, as it prevents the decision-makers from learning (Kleinberg &
Raghavan, 2021; Peng & Garg, 2023), or unfair, as it means that many decision-
makers reject or make mistakes on the same individuals (Ajunwa, 2021; Creel &
Hellman, 2022; Bommasani et al., 2022; Toups et al., 2023; Jain et al., 2023).
And when individuals receive a series of decisions over time, biased early
allocations often affect the data available for the next decision-maker. An
initial negative judgement leads to a series of further negative judgements,
forming a “patterned inequality” or compounding injustice (Eidelson, 2021;
Hellman, 2018). For these reasons, deterministic judgements under uncertainty
can reinforce structural injustices. Therefore, we take the position that many
scarce resource allocations that rely on machine learning111We consider any
data-driven algorithmic decision-making process to be under the umbrella of
the term “machine learning”. should be randomized.

Having motivated randomizing allocations (section 3), we then formalize how to
randomize to bring about more fair outcomes. We consider two settings: when
claims are known (subsection 4.1), and when claims are uncertain (subsection
4.2). Finally, we discuss why existing deterministic methods may not be enough
to achieve both fair and efficient allocations (section 5).

##  2 Related Work

The idea that randomizing decisions might promote fairness when resources are
scarce is not new. Lotteries are used to admit students to public schools
(Hastings et al., 2006) and medical schools (Cohen-Schotanus et al., 2006). In
healthcare, lotteries have also been used to allocate COVID-19 treatments
(McCreary et al., 2023).

We build on work that extends this concept to machine learning and advocates
for using randomness to increase fairness in algorithmic decision-making.
Kleinberg & Raghavan (2021) find that in “algorithmic monocultures” in which
all decision-makers deterministically choose the same candidates, decision
quality suffers. And Peng & Garg (2023) offer a careful analysis of
monoculture in matching markets, showing that its benefit or harm varies
depending on the strength of the candidate. We similarly aim to address
algorithmic monoculture and the reduced quality (and unfair) decisions it
engenders by adding randomness. For example, concerned with decision quality
and the loss of diversity in the decision-making process that comes from
relying on machine learning, Grgić-Hlača et al. (2017) propose randomizing
among models in classifier ensembles obtained by retraining multiple times. We
second their concern, connecting it to the growing literature on the
homogenization of outcomes that results from automated decision-making
(Kleinberg & Raghavan, 2021; Ajunwa, 2021; Creel & Hellman, 2022; Bommasani et
al., 2022; Toups et al., 2023; Jain et al., 2023) and from the use of
foundation models (Bommasani et al., 2021). We extend the idea of randomizing
among models with similar performance to the setting of fair allocations based
on claims.

Agarwal & Deshpande (2022) are concerned with the loss of accuracy that
results when we impose fairness constraints and introduce a randomized
framework for classification to address this concern. We follow them in
demonstrating that many randomization procedures have minimal impact on
accuracy while improving fairness. Finally, Singh et al. (2021) argue that
evaluating candidate merit without accounting for uncertainty is unfair in
rankings. To address this unfairness, they introduce the notion of a
“posterior merit distribution,” suggesting that goods should be allocated
based on the probability that an individual is among the top $k$ candidates.
We agree that fairness sometimes requires quantifying uncertainty and extend
the argument to specify when and how to incorporate randomness based on
uncertainty.

##  3 Why and When To Randomize Allocations

In this section, we motivate randomization by arguing that (weighted)
lotteries better achieve fairness than deterministic allocation algorithms in
certain settings. We give two reasons. First, relying on John Broome’s
characterization of fairness (Broome, 1990), we show that when more
individuals deserve a good than can receive it, the best way to respect each
person’s claim to that good is to give them a chance to receive it by holding
a lottery.

Second, deterministic decision-making over-represents the certainty of our
predictions. Many ML-based social allocation problems have uncertain
parameters. We cannot be sure that we have formulated the problem-to-be-solved
well, that we have chosen appropriate variables or parameters, or that our
data is accurate (Passi & Barocas, 2019). Indeed, in many cases we suspect
that our problem formulation, variable choice, and data gathering all may have
been systematically skewed by social conditions. Our uncertainty leads us to
underestimate the claims of some to the good and overestimate the claims of
others, which has moral implications in situations when not all claims can be
satisfied.

###  3.1 Fairness and Individual Claims

To motivate why lotteries are sometimes needed to ensure fairness, we turn to
John Broome’s influential theory of fairness (Broome, 1990). Broome’s theory
is based on the moral concept of a “claim.” An individual has a claim to a
good, resource, or opportunity when she is owed it for reasons of fairness
(Broome, 1990, p.96). For example, if a kidney is being allocated and there
are two individuals who have been on the waiting list for an equal amount of
time and are in all other respects equivalent, both individuals have a claim
on the kidney.

Some claims stem from desert: the person deserves the good (Broome, 1990,
p.93). All claimants on kidneys deserve the chance at life, so all have a
claim, even if there is disagreement about what factors attenuate the strength
of their claims. While claims based on a right to life always exist, other
claims only arise when a good is being allocated (Broome, 1990, p.97). The
best candidate for a job does not have a claim to work at a company with no
openings, but once there is an opening she may have stronger claims than
others based on her merit. Desert, need, and merit can all ground claims.

Claims are different from both the more familiar utility calculations and
side-constraints such as rights. Utilities can be weighed against each other:
a kidney is allocated according to utilitarian principles such that its
allocation produces the greatest overall benefit. Once the allocation is
calculated, nothing remains to be said about the individual who did not
receive a kidney. Unlike utilities, however, claims linger. The otherwise-
identical individual who did not receive a kidney still had a claim to that
kidney, and she was not fairly treated if her claims was simply “overridden”
by a deterministic allocation (Broome, 1990, p.98). Claims are also unlike
side-constraints such as rights. If someone has a right to a good, that right
cannot be discharged or outweighed: it “directly … determines what ought to be
done” (Broome, 1990, p.91). Rights are not comparative between individuals:
they simply mandate what must be done to respect the right.

Claims, by contrast, are essentially comparative, as they are a matter of
fairness. If both people in need of a kidney are equal in all morally relevant
senses, then they have equally strong claims on the kidney. It would be unfair
to deterministically allocate the kidney to one person because doing so would
override or ignore the equivalent claim that the other patient has on the same
kidney (Broome, 1990, p.95). But what if Person $a$ has a slightly stronger
claim than Person $b$? Broome argues that if “fairness requires everyone to
have an equal chance when their claims are exactly equal, then it is
implausible it should require some people to have no chance at all when their
claims fall only a little below equality” (Broome, 1990, p.99). In other
words, $b$’s claim does not go away just because $a$’s claim is marginally
stronger. This motivates Broome’s proposal to allocate scarce and indivisible
goods using a lottery weighted by the strength of claims. A weighted lottery
allows stronger claims to have a proportionately stronger chance while not
overriding weak claims. By giving everyone with a claim a chance, lotteries
and other randomization techniques give a “surrogate satisfaction” to the
claimants – the next best thing to actually receiving the good (Broome, 1990,
p.99). In summary, according to Broome, the following two conditions should be
met in order for an allocation to be considered fair:

  1. BF.1

The chance of a positive outcome should be greater for those with stronger
claims.

  2. BF.2

Stronger claims should not completely override weaker claims.

###  3.2 Multi-Shot Contexts: Systemic Denial of Claims

The perspective of individual fairness concerns whether each allocation
respects individual claims, but we should also consider whether the structure
of allocations as a whole is fair. Concerns of structural injustice arise when
certain individuals find their claims repeatedly denied, whether by multiple
decision-makers at the same time (systemic exclusion) or by multiple decision-
makers across time (patterned inequality). In conditions of systemic
exclusion, decision-makers across an ecosystem are correlated in their
decisions such that they make mistakes on the same people (Creel & Hellman,
2022; Bommasani et al., 2022; Toups et al., 2023). For example, different
companies attempting to hire candidates in the same sector often rely on the
same third-party vendors for their automated hiring tools. In fact, over 60%
of Fortune 100 companies use the same vendor (HireVue) (Nawrat, 2023). Relying
on the same vendor can lead to identical outcomes if different companies use
the same underlying model to rank candidates, or correlated outcomes if each
company personalizes their model. In either case, correlation between
decision-makers can lead to the same individuals being “algorithmically
blackballed” and excluded from opportunities (Ajunwa, 2021, 681).

Patterned inequality (Eidelson, 2021) is another form of systemic injustice.
It occurs when receiving one allocation increases your likelihood of receiving
future allocations (and likely also your claims to those allocations) such
that clear patterns in social inequality emerge as a result of initial
conditions. This situation is also referred to as the “Matthew effect,” in
which the rich (or otherwise advantaged) get richer over time due to their
starting condition of advantage. Patterned inequality is visible in domains
such as healthcare, where allocations of life-saving medical services are
often conditioned on projections of life expectancy or evaluations of current
health. Both of these, however, are influenced by past access to treatment and
health insurance, for which there are well-documented inequalities between
socioeconomic groups (Schmidt et al., 2021). Algorithmic decision-making can
exacerbate these inequalities by recognizing the current gap in health without
recognizing the unequal starting conditions of health, wealth, and stability
that gave rise to them (Eidelson, 2021; Hellman, 2018; Jain et al., 2023).
Though both these forms of structural injustice involve a myriad of dynamics,
we argue that randomization can help to address both concerns.

###  3.3 Inherent Uncertainties in Predicting Claims

While Broome argues that a lottery weighted on the strength of claims is fair,
he acknowledges that it is not always clear which particular reasons are
claims and which are not (Broome, 1990, p.93). This makes it difficult to
compare the strength of claims, leading some to reject the claims framework
altogether (Kirkpatrick & Eastwood, 2015). However, this so-called
“calculation objection” applies to any problem formulation for allocating
resources, including utilitarian and rights-based frameworks (Passi & Barocas,
2019; Mitchell et al., 2021). Given the inherent uncertainty in any problem
formulation, deterministic allocations on any basis will be unfair to some
individuals, especially if we acknowledge that claims exist and some will not
have been fairly calculated.

Let us assume there exists some problem formulation for the strength of claims
(e.g. worker productivity in hiring, life-expectancy in healthcare). Many
formulations require certainty about what an individual will do (e.g.
individual risk). However, individual future outcomes are fundamentally
unknowable, especially since the events in question are typically realized
only once (Dawid, 2017; Dwork et al., 2021; Roth et al., 2023). Instead,
decision-makers often must estimate what an individual is likely to do based
on their features and data about what other people with similar features have
done in the past. For instance, in the kidney allocation, we might determine
that a patient’s claim should be based on how much longer they are expected to
live. If we have data on prior patients, we could develop an algorithm to
gauge the strength of a patient’s claim based on features such as their age,
medical history, and lifestyle.

When posed as a supervised learning problem, the choice of features, training
data, and model class each contribute additional uncertainty to our estimates
of the strength of claims. First, a person’s features may or may not be
predictive of their claim or even measurable. In many social settings, the
vast majority of people remain inseparable on the basis of the features that
can be measured (also referred to as there being no “margin”). For example, in
the canonical New Adult Census dataset, 95% of individuals have feature
representations for which there exist examples in both prediction classes of
high and low income. An individual could have a strong claim that is predicted
to be weak because there were only a few examples of similar individuals in
the dataset and they all happened to have weak claims. Deterministically
picking the strongest predicted claims may constitute a kind of stereotyping
in this situation. Likewise, people may “look risky” because the features
measured in the data are not adequate to evaluate their claims. In both cases,
people are systemically denied opportunities they deserve. We argue that in
these situations randomizing can increase the fairness of allocations.

Moreover, the uncertainty in predictions of claims may be higher for some
individuals than for others. Consider the phenomenon of predictive
multiplicity, wherein there exist multiple models with similar accuracy that
yield different predictions for certain individuals (Marx et al., 2020; Black
et al., 2022). For individuals with high variance in their predictions, it
seems unfair to weight their chances based on the prediction of a naively
chosen model. The related concept of leave-one-out unfairness highlights how
some individuals can receive radically different predictions due to the
inclusion or removal of a single other person in the training data (Black &
Fredrikson, 2021; Broderick et al., 2020). This may be due to the fact that
some individuals are outliers based on the selected features or under-
represented in the training data. Uncertainty quantification methods such as
conformal prediction can help to identify these individuals (Angelopoulos &
Bates, 2021). As we describe further in subsection 4.2, these methods offer a
way to account for varying levels of uncertainty in a weighted lottery using
predicted claims.

##  4 How To Randomize Allocations

We now formalize how randomization can help to address the ethical demand of
satisfying individual claims in algorithmic decision-making. Specifically, we
propose different methods for randomization when claims are known or uncertain
and also show how these methods can help alleviate the structural concerns of
systemic exclusion and patterned inequality. We also discuss the potential
trade-off between randomization and accuracy and how to interpolate between
them when the trade-off exists.

###  4.1 When Claims Are Known

Consider a setting in which there are $n$ individuals and each individual $i$
is assigned a score $c_{i}\in[0,1]$ in perfect accordance with their claim. We
say that individual $i$ has a stronger claim than individual $j$ if
$c_{i}>c_{j}$. A decision-maker is tasked with allocating outcomes
$o_{i}\in\\{0,1\\}$ to each individual $i$. Importantly, there is scarcity in
that not all claims can be satisfied: only $k$ out of $n$ individuals can
receive positive outcomes with $k\ll n$, for a selection rate of $k/n$.

######  Definition 4.1.

An iterative weighted selection chooses one individual in each round $t$
without replacement until $k$ individuals are selected. Specifically, an
individual $i$ in round $t$ has probability $w_{i,t}$ of being selected. For
all rounds $t\in\\{1,\ldots,k\\}$, we require $\sum_{j=1}^{n-t+1}w_{j,t}=1$ so
that exactly one individual is selected per round.

Note that the formulation above encapsulates many kinds of selections. For
example, deterministically selecting the top $k$ claims222This is equivalent
to selecting all claims greater than or equal to the threshold $T=c_{(k)}$
where $c_{(k)}$ is the k-th largest claim. would take
$w_{i,t}=\mathds{1}[c_{i}=\max_{j\in\\{1...n-t+1)\\}}c_{j}]$. Recall that
Broome’s notion of fairness calls for weights that are chosen in proportion to
a claim’s strength.

######  Definition 4.2.

An allocation $A$ involves the assignment of outcomes $o_{i}$ through an
iterative weighted selection based on weights $w_{i,t}$ for each claim $c_{i}$
and each round $t$. It satisfies Broome-Fairness (BF) if for all rounds $t$
and all individuals $i,j$ not yet selected:

  1. 1.

$c_{i}>c_{j}\implies w_{i,t}>w_{j,t}\;$ (c.f. BF.1)

  2. 2.

$c_{i}>0\implies w_{i,t}>0\;$ (c.f. BF.2)

######  Example 4.3 (BF Lottery).

An allocation with $w_{i,t}=\frac{c_{i}}{C_{t}}$ satisfies BF, where $w_{i,t}$
is calculated among the remaining individuals $i$ in round $t$ and
$C_{t}=\sum_{j=1}^{n-t+1}c_{j}$ represents the sum over claims not selected in
previous rounds.

Importantly, deterministic allocations do not satisfy BF because some weights
are zero (violating BF.2) and no distinction is made among rejected claims of
varying strengths (violating BF.1). An unweighted lottery also violates BF.1
by assigning the same weight to all individuals: $w_{i,t}=\frac{1}{n-t+1}$.

####  4.1.1 Systemic Harms

A lottery weighted by the strength of claims can help to alleviate the
structural concerns of systemic exclusion and patterned inequality. Suppose
there are $m>1$ decision-makers conducting allocations either concurrently or
across time. Let $o_{i}^{(j)}$ denote the outcome for individual $i$ by
decision-maker $j$. Our concern is with the proportion of individuals (or
groups) who exclusively receive negative outcomes from all $m$ decision-
makers.

######  Definition 4.4.

The systemic exclusion rate (SER) (Bommasani et al., 2022) across $m>1$
decision-makers is:

$\textstyle\mathbb{E}_{i}\left[\prod_{j=1}^{m}\mathds{1}[o_{i}^{(j)}=0]\right]$

To illustrate why randomization can help reduce SER, we begin by introducing
and analyzing two stylized models of allocations. As our stylized models will
suggest, if the existing SER is sufficiently high across the $m$ decision-
makers or $m$ is sufficiently large, then randomization will help both
systemic exclusion (Example 4.5) and patterned inequality (Example 4.6) in
expectation.

######  Example 4.5 (Systemic Exclusion).

Suppose there are $m$ allocations at the same time and that there are many
more individuals with equally strong claims than available positive outcomes.
If the SER is sufficiently high for the existing set of allocations, than any
allocation satisfying BF will decrease the SER in expectation.

(a) Distributions of Claims (b) Reduction in SER using BF Lottery in Ex. 4.3

######  Example 4.6 (Patterned Inequality).

Suppose there are $m$ sequential allocations across time, and that receiving a
positive outcome increases an individual’s claim in the next allocation.
Assume also that in the first allocation, there are many more individuals with
similarly strong claims than available positive outcomes. Then any set of
sequential allocations satisfying BF will decrease the SER in expectation when
compared to a set of deterministic allocations if the benefit from a positive
outcome is sufficiently high.

In general, the ability of allocations satisfying BF to reduce the SER will
depend on the distribution of claims, correlation between allocations across
decision-makers, and selection rate ($k/n$). We simulate how much
randomization can reduce SER for various distributions of claims, when each
decision-maker has a noisy estimation of these claims
($\pm\,N(0,\sigma^{2})$). As Figure LABEL:sub@fig:claims_dist illustrates, we
consider the following distributions:

  * •

Uniform: all claims equally likely

  * •

Normal: more average claims

  * •

Inverted Normal: more strong and weak claims

  * •

Pareto: more weak claims

  * •

Inverted Pareto: more strong claims

For all these distributions and many different selection rates and noise
amounts, we observe a substantial reduction in SER if each decision-maker uses
the weighted lottery satisfying BF in Example 4.3 rather than
deterministically selecting their top $k$ claims. Figure
LABEL:sub@fig:claims_ser provides a snapshot of our results in the setting
where $k/n=0.5$ and $\sigma=0.025$ (see Appendix A.2 for other cases).

####  4.1.2 Utility and Randomization

Why might one want to allocate deterministically? From the viewpoint of risk-
averse decision-makers, the objective is to maximize their own utility. In
hiring, for instance, a company might predict a candidate’s utility by
estimating their future job performance. We simplify to the case where each
individual has some utility $o^{*}_{i}\in\\{0,1\\}$ (e.g. the job performance
of the candidate if hired).

######  Definition 4.7.

The utility of an allocation is
$\frac{1}{k}\sum_{i=1}^{n}o^{*}_{i}\cdot\mathds{1}\\{o_{i}=1\\}$, which is
simply the precision: i.e. the proportion of selected individuals $k$ that
provide utility.

Note that $o^{*}_{i}$ can only be observed if the individual receives the
resource being allocated ($o_{i}=1$), which motivates the idea of expected
utility.

######  Definition 4.8.

Suppose an individual’s chance of providing utility is
$p_{i}=\mathbb{P}(o^{*}_{i}=1)$. Accordingly, the expected utility of an
allocation is $\frac{1}{k}\sum_{i=1}^{n}p_{i}\cdot\mathds{1}\\{o_{i}=1\\}$.

Utility aligns with the strength of claims in some merit-based allocations.
The individuals with the strongest claims are those with the most “merit” or
closest fit between their skills and the needs of the role. These candidates
therefore are also the most likely to provide utility to the company.
Individuals may have other claims besides merit, such as claims based in
desert or entitlement. However, we adopt the decision-maker’s perspective
because it is the least favorable viewpoint to motivate randomization and
results in the worst-possible trade-offs between the decision-maker’s notion
of utility and desirable properties of randomization.

If claims are exactly the chance of providing utility, then deterministically
selecting the $k$ strongest claims will maximize the expected utility. But as
we discussed above, this overrides the most claims and violates both BF.1 and
BF.2. On the other hand, any amount of randomization will lead to some
probability of allocating resources to those who do not have the strongest
claims, resulting in some sacrifice of expected utility in favor of respecting
more claims. Figure LABEL:sub@fig:claims_utility illustrates the difference in
expected utility between the top $k$ allocation and BF lottery in Example 4.3
for the normal and inverted Pareto distributions (other distributions are
similar, see Appendix A.2). Note that this trade-off increases with scarcity
(i.e. low selection rates).

Balancing this trade-off requires a consideration of the fairness arguments on
each side. Consider two patients who both have a claim to a single kidney.
Patient $a$’s claim is based in their survival probability of 0.51, while
patient $b$ has a survival probability of 0.49. If we deterministically chose
to give the kidney to patient $a$, Broome would argue that this is unfair to
patient $b$ since they have no chance at all to receive the kidney despite
only having a slightly weaker claim (Broome, 1990, p.99). But what if we
instead compare patient $c$, who has a survival rate of 0.99, to patient $d$,
who only has a survival rate of 0.01? Brad Hooker points out in an objection
to Broome that “a great unfairness would occur” if we held a weighted lottery
and patient $d$ won given the comparative strength of patient $c$’s claim in
this case (Hooker, 2005).333Hooker’s objection considers one patient (here,
$c$) who would die without the medicine and another ($d$) who would only lose
a finger (Hooker, 2005). This motivates the idea of not randomizing some very
strong or weak claims while still conducting a weighted lottery for the
remaining claims.

(c) Utility Difference: Top $k$ v. BF Lotteries (d) Reduction in SER with a
Partial BF Lottery

######  Definition 4.9.

An allocation satisfies partial Broom-Fairness when the criteria BF.1 and BF.2
are met for:

  1. 1.

a subset of claims $C^{\prime}\subset[0,1]$

  2. 2.

a fewer number of available resources $k^{\prime}\in(0,k)$

######  Example 4.10 (Partial BF Lottery).

The following allocation satisfies partial BF: some $u<k$ individuals directly
receive $o_{i}=1$, some $l<(n-k)$ individuals directly receive $o_{i}=0$, and
the iterative weighted selection in Example 4.3 is conducted over the
remaining claims $C^{\prime}$ for the remaining resources $k^{\prime}$.

We show how a lottery satisfying partial BF can result in a much smaller
trade-off with expected utility, yet still substantially reduces SER. Figure
LABEL:sub@fig:claims_utility shows that the utility difference is $<$ 0.05 for
a partial BF lottery that uses $l=n-2k+u$ and $u=0.5k$. In other words, we
first allocate half the available resources to the top $u=0.5k$ claims, then
randomize over the next $k$ strongest claims for the $0.5k$ remaining
resources. Note that this has the effect of randomizing near the so-called
“decision-boundary,” which represents the $k$-th largest claim in our
framework.

Figure LABEL:sub@fig:claims_ser_partial illustrates that this still results in
a substantial reduction in SER when compared to deterministically picking the
top $k$ claims for the same setting as Figure LABEL:sub@fig:claims_ser where
$k/n=0.5$ and $\sigma=0.025$. Just a 2% difference in expected utility, for
instance, yields a 50% reduction in SER when there are $m>2$ decision-makers
and claims are normally distributed. See Appendix A.2 for many other examples
across different distributions of claims, selection rates, and amounts of
noise added for each decision-maker.

###  4.2 When Claims Are Uncertain

A fundamental assumption in machine learning is that the targets of interest
(in our case, claims) are predictable from a set of measurable features in
some domain ${\mathcal{X}}$. While $p_{i}=\mathbb{P}(o^{*}_{i}=1)$ might be
unknowable, the conditional probability
$p(x_{i})=\mathbb{P}(o^{*}_{i}=1\,|\,x_{i})$ can be estimated from data. The
validity of taking $p(x_{i})$ to be an estimate of $p_{i}$ depends on the
choice of features that are measured and predictability of the outcomes from
those features. Putting these concerns aside, a machine learning model
$\hat{p}:{\mathcal{X}}\rightarrow[0,1]$ maps an individual’s features
$x_{i}\in{\mathcal{X}}$ to a prediction $\hat{p}(x_{i})$, which estimates the
conditional probability $p(x_{i})=\mathbb{P}(o^{*}_{i}=1\,|\,x_{i})$. In a
healthcare allocation, $\hat{p}(x_{i})$ might represent a model’s estimate
based on prior patients in a hospital, whereas $p(x_{i})$ represents the
conditional probability if we could measure all possible patients represented
in feature space ${\mathcal{X}}$.

Standard practice in machine learning would be to deterministically assign
$o_{i}=1$ to the individuals with the $k$ highest value of $\hat{p}(x_{i})$.
While this doesn’t satisfy BF, it is unclear what implementable allocation
does due to the distinction between $\hat{p}(x_{i})$ and $p_{i}$. For example,
we could use the weighted lotteries in Example 4.3 or 4.10 by replacing
$c_{i}$ with $\hat{p}(x_{i})$. However, the estimation error in
$\hat{p}(x_{i})$ could be higher for certain individuals than others,
potentially violating BF.1.

####  4.2.1 Randomization Proposals

We take our working example to be the New Adult Census dataset444We subset to
the 2018 California data ($n=$196,604) and use an 80-20 train-test split
(results avg. from 5 repetitions). (Ding et al., 2021). Suppose an
individual’s true claim to a scarce resource such as a loan is based on their
income and that individuals provide utility to the decision-maker if they have
high-income ($>$$50,000). Assume we can only estimate an individual’s
probability of being high-income based on features such as their age,
education, employment type, place of birth, etc. Figure
LABEL:sub@fig:census_dist shows that predictions appear to follow an inverted
normal distribution for 3 different model classes: logistic regression, random
forests, and decision trees.

(e) Distribution of Predictions (f) Utility Difference: Top $k$ v. Partial BF
Lottery

We first consider the baseline method of using the partial weighted lottery in
Example 4.10 by replacing $c_{i}$ with $\hat{p}(x_{i})$. Recall that this has
the effect of randomizing near the decision-boundary or $k$-th largest
prediction. We again use $l=n-2k+u$ and $u=0.5k$, which randomizes half the
available resources across the people with predictions within $0.5k$ of the
decision-boundary on either side. Figure LABEL:sub@fig:census_utility shows
that the accuracy losses are smaller than losses from the standard practice of
choosing the top $k$ predictions.

In what follows, we propose using two different uncertainty quantification
methods to conduct a partial weighted lottery. We discuss how these methods
change how many resources (out of $k$) and what kinds of people (out of $n$)
are randomized, while maintaining almost negligible loss in utility.

Randomizing Using Variance.  A variety of methods exist to estimate the
variance of predictions (Black & Fredrikson, 2021; Cooper et al., 2023; Ganesh
et al., 2023). For example, Cooper et al. (2023) propose re-training on
bootstrapped sub-samples of the training data. Consider the set of predictions
$(\hat{p}_{(1)},\ldots,\hat{p}_{(m)})$ across $m$ bootstrapped models555Ganesh
et al. (2023) show how to efficiently estimate the variance in predictions by
changing the data order across epochs in a single training run.. We contend
that if any of these models placed an individual among the top $k$ claims,
then they should have a chance to receive $o_{i}=1$. Specifically, we propose
directly assigning $o_{i}=1$ to individuals placed in the top $k$ by all
models, and then conducting an iterative weighted lottery among the remaining
individuals, where the weights represent the proportion of models that placed
them in the top $k$.

(g) Utility Diff: Top $k$ v. Randomizing w/Variance (h) Randomization Rate:
Randomizing w/Variance

When compared to the baseline of randomizing near the decision-boundary, we
observe that randomizing using this estimation of variance results in a
smaller utility loss for all model classes. Figure
LABEL:sub@fig:bootstrap_utility shows the trade-off with utility is around 2%
or less when randomizing according to 11 bootstrapped models on 50% of the
training data. This is less than the up to 5% utility loss we observe when
randomizing near the decision-boundary in Figure LABEL:sub@fig:census_utility.
Depending on the selection rate and model class666As Cooper et al. (2023) also
found, logistic regression does not result in high variance, making it a poor
choice for this method., this method also sometimes randomizes more resources
(out of $k$) and people (out of $n$) than the baseline method, which only
randomizes half the resources over $k$ people. As Figure
LABEL:sub@fig:bootstrap_randomization shows, we can achieve these higher
randomization rates with lower utility loss for decision trees when the
selection rate is $>$0.2, and random forests when the selection rate is
$<$0.25.

(i) Utility Diff: Top $k$ v. Randomizing Outliers (j) Randomization Rate:
Randomizing Outliers

Randomizing Outliers.  Many out-of-the-box methods exist for outlier
detection, which quantify the uncertainty in a prediction that stems from a
lack of similar individuals in the training data (Pimentel et al., 2014). For
example, in New Adult there exists an individual $i$ (and $i^{\prime}$) with
very high (and very low) predicted value across all bootstrapped models
$\min_{j}\hat{p}_{(j)}(x_{i})=.99$ (and
$\max_{j}\hat{p}_{(j)}(x_{i^{\prime}})=.01$), but with $o_{i}=0$ (and
$o_{i^{\prime}}=1$). Conformal prediction offers a way to assign a confidence
measure to outlier detection methods, and produces low p-values for both
individuals ($<$0.01). This motivates the use of conformal prediction to flag
outliers (Angelopoulos & Bates, 2021) and then deploy a lottery for the
resources that would have gone to “outliers individuals” based on a top $k$
allocation.

Specifically, consider the pool of individuals that we believe are outliers
with high confidence ($\text{p-value}\leq\alpha$) for some small $\alpha$. If
some of these individuals fall in the top $k$, then we propose to randomize
those resources over the entire pool of “outlier” individuals using an
unweighted lottery. Note that the pool of individuals that we believe are
outliers is model-agnostic, since it is computed based on the features. How
many of these “outlier” individuals would have ended up in the top $k$ depends
on the model.

Figure LABEL:sub@fig:conformal_utility shows the trade-off with utility for
$\alpha=0.1$, which for selection rates $>$ 0.2, is smaller than the baseline
method of randomizing near the decision-boundary. However, Figure
LABEL:sub@fig:conformal_random shows that we are only randomizing around 10%
of the available resources over 10% of the total people (note this directly
corresponds to our choice of $\alpha=0.1$). As our example above suggests,
individuals being randomized based on outlier detection can be different than
those near the decision-boundary or with high variance in predictions.

Lastly, we turn to how much our randomization proposals could reduce the
systemic exclusion rate (SER). Similar to the experiments in Section 4.1.1, we
simulate the predictions from multiple decision-makers by adding noise to the
predictions from a single model ($\pm\,N(0,\sigma^{2})$). Figure
LABEL:sub@fig:census_homogenization demonstrates our results for the decision-
tree model class in the setting where $k/n=0.5$ and $\sigma=0.025$ (see
Appendix A.3 for other cases). Both methods still result in a substantial
reduction in SER despite having a lower utility loss than randomizing near the
decision-boundary.

(k) Reduction in SER ea. Randomization Proposal

##  5 Discussion

We argued in section 3 that sometimes fairness requires randomizing
allocations of scarce resources or opportunities, and in section 4 we provide
randomization techniques that respect many claims while not losing significant
predictive performance. We now extend the argument and explore implications of
these findings.

Utility.  When claims are known, randomization sometimes trades off against
expected utility or predictive success. Although some may find this tradeoff
hard to endorse, we suggest two things. First, a claims-based moral framework
holds that people’s claims must be satisfied (or acknowledged by the surrogate
satisfaction of a lottery). Some reject claims and take utility to be the only
currency of moral concern. However, anyone who agrees that it is more fair for
a qualified candidate to have a chance than to never have had a chance can
consider claims as an objective within a broader utility-maximization
framework, such that overall utility can be improved by satisfying more
claims. Second, our exploration of uncertainty suggests that what appears to
be a tradeoff is, at times, a movement to a different point within the same
bounds of uncertainty. Over-optimizing for apparent utility ignores our true
uncertainty about the facts and moral claims of the case. Thus the utility we
appear to give up in order to honor applicants’ valid claims may be illusory:
there may be no tradeoff at all.

Human Randomness.  How does the intentional randomness we propose in this work
compare to the natural variance of human decision-making? For example, despite
being extensively trained in decision-making, judges who evaluate the same
case (Ludwig & Mullainathan, 2021) often disagree, and judges disagree with
their past selves evaluating similar cases over time (Collins, 2008). This
property should make human decision-making less homogeneous than algorithmic
decision-making (Creel & Hellman, 2022). However, we do not find human
randomness to be a satisfactory substitute for intentional randomization.
Although human decision-making is not consistent, its outcomes are not
guaranteed to be distributed across people in accordance with their claims, as
social biases concentrate bad outcomes on individuals from marginalized groups
in many situations. Furthermore, we have showed above that fairness requires
selecting the most appropriate form of randomness given the problem
description and the underlying distribution of data. Human inconsistency is
not subject to these matching constraints.

Scope.  We do not think that randomization is fair in all settings. For
example, criminal justice is served by respecting the procedural rights of
defendants and attempting to determine whether the accusations they face are
true. Criminal justice is not a matter of comparative claims: each defendant
must be evaluated separately, not in comparison to others. To randomize the
outcomes would be unfair. However, we affirm the value of randomization in
settings in which scarce resources must be fairly allocated on the basis of
uncertain information. Since this encompasses many algorithmic decision-making
contexts, we encourage the field of fair machine learning to consider
randomization as an important element of fairness.

##### Impact Statement.

This paper contributes to the literature on algorithmic fairness in two ways.
(1) As a position paper, it encourages others to reconsider whether
deterministic algorithms are always the right choice for fairness, arguing
that randomization techniques are to be preferred in some settings. (2) In
support of these arguments, the paper also presents concrete techniques that
can be used to randomize and shows how they reduce systemic exclusion and
patterned inequality. As such, we hope that it will have a positive impact in
reducing bias and unfairness.

However, it is also possible that a decision-maker might use the tools
presented here to randomize outcomes in a domain that the authors warn would
be unjust or inappropriate, such as the domain of criminal justice, and in
doing so wrong decision subjects. Since all of the randomization techniques
that form the basis of the paper’s experiments are well established and easily
implementable, the paper does not make improper use of these tools easier than
it would have been before. But it is possible that its existence will suggest
the idea to someone who might not have otherwise had it.

The authors have attempted to prevent this outcome by making it clear which
uses of randomization they believe are appropriate or inappropriate.

## References

  * Agarwal & Deshpande (2022) Agarwal, S. and Deshpande, A.  On the power of randomization in fair classification and representation.  In _Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency_ , pp. 1542–1551, 2022.
  * Ajunwa (2021) Ajunwa, I.  An auditing imperative for automated hiring systems.  _Harvard Journal of Law & Technology_, 34(2), 2021.
  * Angelopoulos & Bates (2021) Angelopoulos, A. N. and Bates, S.  A gentle introduction to conformal prediction and distribution-free uncertainty quantification.  _arXiv preprint arXiv:2107.07511_ , 2021.
  * Black & Fredrikson (2021) Black, E. and Fredrikson, M.  Leave-one-out unfairness.  In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , pp. 285–295, 2021.
  * Black et al. (2022) Black, E., Raghavan, M., and Barocas, S.  Model multiplicity: Opportunities, concerns, and solutions.  In _Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency_ , pp. 850–863, 2022.
  * Bommasani et al. (2021) Bommasani, R., Hudson, D. A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M. S., Bohg, J., Bosselut, A., Brunskill, E., et al.  On the opportunities and risks of foundation models.  _arXiv preprint arXiv:2108.07258_ , 2021.
  * Bommasani et al. (2022) Bommasani, R., Creel, K. A., Kumar, A., Jurafsky, D., and Liang, P. S.  Picking on the same person: Does algorithmic monoculture lead to outcome homogenization?  In _Advances in Neural Information Processing Systems_ , volume 35, pp. 3663–3678, 2022.
  * Broderick et al. (2020) Broderick, T., Giordano, R., and Meager, R.  An automatic finite-sample robustness metric: when can dropping a little data make a big difference?  _arXiv preprint arXiv:2011.14999_ , 2020.
  * Broome (1990) Broome, J.  Fairness.  In _Proceedings of the Aristotelian Society_ , volume 91, pp. 87–101, 1990.
  * Chin et al. (2023) Chin, M. H., Afsar-Manesh, N., Bierman, A. S., Chang, C., Colón-Rodríguez, C. J., Dullabh, P., Duran, D. G., Fair, M., Hernandez-Boussard, T., Hightower, M., et al.  Guiding principles to address the impact of algorithm bias on racial and ethnic disparities in health and health care.  _Journal of the American Medical Association_ , 6(12), 2023\.
  * Cohen-Schotanus et al. (2006) Cohen-Schotanus, J., Muijtjens, A. M. M., Reinders, J. J., Agsteribbe, J., van Rossum, H. J. M., and van der Vleuten, C. P. M.  The predictive validity of grade point average scores in a partial lottery medical school admission system.  _Medical Education_ , 40(10):1012–1019, October 2006.  ISSN 1365-2923.
  * Collins (2008) Collins, P. M.  The consistency of judicial choice.  _The Journal of Politics_ , 70(3):861–873, July 2008.  ISSN 1468-2508.
  * Cooper et al. (2023) Cooper, A. F., Barocas, S., De Sa, C., and Sen, S.  Variance, self-consistency, and arbitrariness in fair classification.  _arXiv preprint arXiv:2301.11562_ , 2023.
  * Creel & Hellman (2022) Creel, K. and Hellman, D.  The algorithmic leviathan: Arbitrariness, fairness, and opportunity in algorithmic decision-making systems.  _Canadian Journal of Philosophy_ , 52(1):26–43, 2022.  doi: 10.1017/can.2022.3.
  * Dawid (2017) Dawid, P.  On individual risk.  _Synthese_ , 194(9):3445–3474, 2017.
  * Ding et al. (2021) Ding, F., Hardt, M., Miller, J., and Schmidt, L.  Retiring adult: New datasets for fair machine learning.  _Advances in neural information processing systems_ , 34:6478–6490, 2021.
  * Dwork et al. (2021) Dwork, C., Kim, M. P., Reingold, O., Rothblum, G. N., and Yona, G.  Outcome indistinguishability.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pp. 1095–1108, 2021.
  * Eidelson (2021) Eidelson, B.  Patterned inequality, compounding injustice, and algorithmic prediction.  _American Journal of Law and Equality_ , 1:252–276, 2021\.
  * Ganesh et al. (2023) Ganesh, P., Chang, H., Strobel, M., and Shokri, R.  On the impact of machine learning randomness on group fairness.  In _Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency_ , pp. 1789–1800, 2023.
  * Grgić-Hlača et al. (2017) Grgić-Hlača, N., Zafar, M. B., Gummadi, K. P., and Weller, A.  On fairness, diversity and randomness in algorithmic decision making.  _arXiv preprint arXiv:1706.10208_ , 2017.
  * Hastings et al. (2006) Hastings, J., Kane, T., and Staiger, D.  Preferences and heterogeneous treatment effects in a public school choice lottery, 2006.  URL http://dx.doi.org/10.3386/w12145.
  * Hellman (2018) Hellman, D.  Indirect discrimination and the duty to avoid compounding injustice.  _Foundations of Indirect Discrimination Law, Hart Publishing Company_ , pp. 2017–53, 2018.
  * Hooker (2005) Hooker, B.  Fairness.  _Ethical theory and moral practice_ , 8:329–352, 2005.
  * Hsu & Calmon (2022) Hsu, H. and Calmon, F.  Rashomon capacity: A metric for predictive multiplicity in classification.  In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), _Advances in Neural Information Processing Systems_ , volume 35, pp. 28988–29000. Curran Associates, Inc., 2022.
  * Jain et al. (2023) Jain, S., Suriyakumar, V., Creel, K., and Wilson, A.  Algorithmic pluralism: A structural approach towards equal opportunity.  _arXiv preprint arXiv:2305.08157_ , 2023.
  * Kirkpatrick & Eastwood (2015) Kirkpatrick, J. R. and Eastwood, N.  Broome’s theory of fairness and the problem of quantifying the strengths of claims.  _Utilitas_ , 27(1):82–91, 2015.
  * Kleinberg & Raghavan (2021) Kleinberg, J. and Raghavan, M.  Algorithmic monoculture and social welfare.  _Proceedings of the National Academy of Sciences_ , 118(22):e2018340118, 2021.
  * Ludwig & Mullainathan (2021) Ludwig, J. and Mullainathan, S.  Fragile algorithms and fallible decision-makers: lessons from the justice system.  _Journal of Economic Perspectives_ , 35(4):71–96, 2021.
  * Marx et al. (2020) Marx, C., Calmon, F., and Ustun, B.  Predictive multiplicity in classification.  In _International Conference on Machine Learning_ , pp. 6765–6774. PMLR, 2020.
  * McCreary et al. (2023) McCreary, E. K., Essien, U. R., Chang, C.-C. H., Butler, R. A., Pathak, P., Sönmez, T., Ünver, M. U., Steiner, A., Chrisman, M., Angus, D. C., and White, D. B.  Weighted lottery to equitably allocate scarce supply of covid-19 monoclonal antibody.  _JAMA Health Forum_ , 4(9):e232774, September 2023\.  ISSN 2689-0186.  doi: 10.1001/jamahealthforum.2023.2774.  URL http://dx.doi.org/10.1001/jamahealthforum.2023.2774.
  * Mitchell et al. (2021) Mitchell, S., Potash, E., Barocas, S., D’Amour, A., and Lum, K.  Algorithmic fairness: Choices, assumptions, and definitions.  _Annual Review of Statistics and Its Application_ , 8:141–163, 2021.
  * Nawrat (2023) Nawrat, A.  Inside hirevue’s acquisition of modern hire.  https://www.unleash.ai/hr-technology/inside-hirevues-acquisition-of-modern-hire/, 2023\.
  * Passi & Barocas (2019) Passi, S. and Barocas, S.  Problem formulation and fairness.  In _Proceedings of the conference on fairness, accountability, and transparency_ , pp. 39–48, 2019.
  * Peng & Garg (2023) Peng, K. and Garg, N.  Monoculture in matching markets.  _arXiv preprint arXiv:2312.09841_ , 2023.
  * Pimentel et al. (2014) Pimentel, M. A., Clifton, D. A., Clifton, L., and Tarassenko, L.  A review of novelty detection.  _Signal processing_ , 99:215–249, 2014.
  * Raghavan et al. (2020) Raghavan, M., Barocas, S., Kleinberg, J., and Levy, K.  Mitigating bias in algorithmic hiring: Evaluating claims and practices.  In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , pp. 469–481, 2020.
  * Roth et al. (2023) Roth, A., Tolbert, A., and Weinstein, S.  Reconciling individual probability forecasts.  In _Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency_ , pp. 101–110, 2023.
  * Schmidt et al. (2021) Schmidt, H., Roberts, D. E., and Eneanya, N. D.  Rationing, racism and justice: advancing the debate around “colourblind” COVID-19 ventilator allocation.  _Journal of Medical Ethics_ , 2021.
  * Singh et al. (2021) Singh, A., Kempe, D., and Joachims, T.  Fairness in ranking under uncertainty.  In _Advances in Neural Information Processing Systems_ , volume 34, pp. 11896–11908, 2021.
  * Toups et al. (2023) Toups, C., Bommasani, R., Creel, K., Bana, S., Jurafsky, D., and Liang, P.  Ecosystem-level analysis of deployed machine learning reveals homogeneous outcomes.  In _Advances in Neural Information Processing Systems_ , 2023.

##  Appendix A Appendix

###  A.1 Conformal Prediction Methodology

We use conformal prediction to assign a confidence measure to outlier
detection methods (Angelopoulos & Bates, 2021). Specifically, we use the
following procedure:

  1. 1.

Suppose we have a novelty score $s:{\mathcal{X}}\rightarrow\mathbb{R}$, where
larger values indicate more abnormality from the training data. For example,
we use average Euclidean distance to the training data.

  2. 2.

We want to find $q:\mathbb{P}(s(x)>q)\leq\alpha$ if
$x\sim{\mathcal{X}}_{\text{train}}$, where $\alpha$ represents the bound on
the false positive rate

  3. 3.

Reserve a calibration dataset ${\mathcal{X}}_{\text{cal}}$. For each
$x_{\text{cal}}^{j}\in{\mathcal{X}}_{\text{cal}}$, compute the novelty score
$s(x_{\text{cal}}^{j})$ with respect to ${\mathcal{X}}_{\text{train}}$.

  4. 4.

Compute $\hat{q}=\text{quantile}\left(s_{\text{cal}}^{1}\ldots
s_{\text{cal}}^{n};\frac{\lceil(n_{\text{cal}}+1)(1-\alpha)\rceil}{n_{\text{cal}}}\right)$

  5. 5.

If $s(x_{i})>\hat{q}$, then we consider individual $i$ to be an outlier.

  6. 6.

Specifically, we take the p-value associated with outlier detection to be:
$\frac{1}{n_{\text{cal}+1}}\cdot(1+\sum_{i=1}^{n_{\text{cal}}}\mathds{1}\\{s(x_{i})\leq
s_{\text{cal}}^{i}\\})$

###  A.2 When Claims Are Known Simulations

We simulate 5 different distributions of claims and compare 3 different
allocation types: (1) deterministic selection of the top $k$ claims, (2) the
BF lottery in Example 4.3, and (3) the partial BF lottery in Example 4.10.
Specifically, we analyze the trade-off between utility and reduction in SER
under various selection rates and levels of noise. We simulate 1000
individuals and average the results over 1000 iterations for each experiment.
We consider the following distributions:

  * •

Normal: more average claims (Figure 1)

  * •

Inverted Normal: more strong and weak claims (Figure 2)

  * •

Pareto: more weak claims (Figure 3)

  * •

Inverted Pareto: more strong claims (Figure 4)

  * •

Uniform: all claims equally likely (Figure 5)

For each distribution, we illustrate the following (letters correspond to sub-
figures for each distribution):

  1. (a)

Distribution of Claims: Density under 3 different parameter choices for all
distribution types except uniform (i.e. different $\sigma$ for normal or
$\alpha$ for pareto)

  2. (b)

Difference in Expected Utility between the top $k$ selection and BF lottery in
Example 4.3. We consider each parameter choice in (a).

  3. (c)

Difference in Expected Utility between the top $k$ selection and partial BF
lottery in Example 4.10. We consider 3 different choices of $u$ under
$l=n-2k+u$. We now use a fixed parameter choice ($\sigma=0.15$ for normal and
$\alpha=2$ for pareto) in this sub-figure and all subsequent sub-figures.

  4. (d)

Reduction in SER for 3 different selection rates ($k/n$). We simulate the
setting where each decision-maker has a noisy estimation of the true claims
($\pm\,N(0,\sigma^{2})$). In this sub-figure, we used a fixed noise
$\sigma=0.025$. We compare the SER for the top $k$ selection, BF lottery, and
partial BF lottery. We now use a fixed choice of $u=0.5$ for the partial BF
lottery.

  5. (e)

Reduction in SER for 3 different noise levels. Similar to (d), but we now
consider a fixed selection rate of $k/n=0.5$ and vary the amount of noise
added to each decision-maker’s estimation of claims.

###  A.3 SER Census Experiment for All Model Classes

Figure 6 replicates the SER experiment in Section 4.2.1 for all model classes:
decision trees, random forest, and logistic regression. We simulate the
predictions from multiple decision-makers by adding noise to the predictions
from a single model ($\pm\,N(0,\sigma^{2})$). Specifically, we use
$\sigma=0.025$ following the experiments in Section A.2. For all model
classes, we observe the most reduction in SER from randomizing near the
decision-boundary. However, we emphasize that our other randomization
proposals have lower utility loss while still achieving a substantial
reduction in SER. Note that the reduction in SER from each method varies by
model class. In particular, we achieve the highest reduction in SER when using
decision trees and random forests, and little reduction in SER for the
logistic regression model class unless we randomize near the decision-
boundary.

(l) Distribution of Claims

(m) Utility Difference for Top $k$ v. BF Lottery
in Example 4.3 (n) Utility Difference for Top $k$ v. Partial BF Lottery
in Example 4.10

(o) Reduction in SER for Varying Selection Rates ($k/n$) (p) Reduction in SER
for Varying Noise ea. Decision-Maker

Figure 1: Normal Distribution of Claims

(a) Distribution of Claims

(b) Utility Difference for Top $k$ v. BF Lottery
in Example 4.3 (c) Utility Difference for Top $k$ v. Partial BF Lottery
in Example 4.10

(d) Reduction in SER for Varying Selection Rates ($k/n$) (e) Reduction in SER
for Varying Noise ea. Decision-Maker

Figure 2: Inverted Normal Distribution of Claims

(a) Distribution of Claims

(b) Utility Difference for Top $k$ v. BF Lottery
in Example 4.3 (c) Utility Difference for Top $k$ v. Partial BF Lottery
in Example 4.10

(d) Reduction in SER for Varying Selection Rates ($k/n$) (e) Reduction in SER
for Varying Noise ea. Decision-Maker

Figure 3: Pareto Distribution of Claims

(a) Distribution of Claims

(b) Utility Difference for Top $k$ v. BF Lottery
in Example 4.3 (c) Utility Difference for Top $k$ v. Partial BF Lottery
in Example 4.10

(d) Reduction in SER for Varying Selection Rates ($k/n$) (e) Reduction in SER
for Varying Noise ea. Decision-Maker

Figure 4: Inverted Pareto Distribution of Claims

(a) Distribution of Claims

(b) Utility Difference for Top $k$ v. BF Lottery
in Example 4.3 (c) Utility Difference for Top $k$ v. Partial BF Lottery
in Example 4.10

(d) Reduction in SER for Varying Selection Rates ($k/n$) (e) Reduction in SER
for Varying Noise ea. Decision-Maker

Figure 5: Uniform Distribution of Claims

(a) Decision Tree

(b) Random Forest

(c) Logistic Regression

Figure 6: Census Experiment SER for each randomization method and model class
(c.f. Figure LABEL:sub@fig:census_homogenization in main text)


# A d’Alembert type functional equation on semigroups

Youssef Aserrar and Elhoucien Elqorachi  Ibn Zohr University, Faculty of
sciences, Department of mathematics,
Agadir, Morocco<EMAIL_ADDRESS><EMAIL_ADDRESS>
(Date: January 1, 2004)

###### Abstract.

We treat two related trigonometric functional equations on semigroups. First
we solve the $\mu$-sine subtraction law

$\mu(y)k(x\sigma(y))=k(x)l(y)-k(y)l(x),\quad x,y\in S,$

for $k,l:S\rightarrow\mathbb{C}$, where $S$ is a semigroup and $\sigma$ an
involutive automorphism, $\mu:S\rightarrow\mathbb{C}$ is a multiplicative
function such that $\mu(x\sigma(x))=1$ for all $x\in S$, then we determine the
complex-valued solutions of the following functional equation

$f(xy)-\mu(y)f(\sigma(y)x)=g(x)h(y),\quad x,y\in S,$

on a larger class of semigroups.

###### Key words and phrases:

Semigroups, Prime ideal, Involutive automorphism, Multiplicative function,
d’Alembert’s equation.

###### 1991 Mathematics Subject Classification:

39B52, 39B32

##  1\. Introduction

Ebanks and Stetkaer [9] solved the functional equation

$f(xy)-f(\sigma(y)x)=g(x)h(y),\quad x,y\in M,$ (1.1)

for $f,g,h:M\rightarrow\mathbb{C}$, where $M$ is a group or a monoid generated
by its squares and $\sigma:M\rightarrow M$ is an involutive automorphism. That
is $\sigma(xy)=\sigma(x)\sigma(y)$ and $\sigma(\sigma(x))=x$ for all $x,y\in
M$.
In [3], Bouikhalene and Elqorachi determined the complex-valued solutions of
the functional equation

$f(xy)-\mu(y)f(\sigma(y)x)=g(x)h(y),\quad x,y\in M,$ (1.2)

on groups and monoid generated by its squares, where
$\mu:M\rightarrow\mathbb{C}$ is a multiplicative function such that
$\mu(x\sigma(x))=1$ for all $x\in M$. Moreover, the solutions of (1.2) on a
semigroup generated by its squares are also known (See Ajebbar and Elqorachi
[2]). Recently, Ebanks [7] solved (1.1) on a larger class of monoids that
contains the class of monoids generated by their squares, and regular monoids.
There are some results about solutions of Equation (1.1) on abelian groups in
the literature. The case of $G=\mathbb{R}$ is treated by Kannappan [11,
Equation (vs) in section 3.4.9]. Stetkaer [12, Corollary 3.5] derives the
solution formulas for the functional equation (1.1) on abelian groups. The
method used in [2, 3, 7, 9] proceeds from the starting point of the
trigonometric functional equation

$\mu(y)k(x\sigma(y))=k(x)l(y)-k(y)l(x),\quad x,y\in S.$ (1.3)

The solutions of (1.3) (with $\mu=1$) on a general monoid was given recently
by Ebanks [6, Theorem 4.2] in terms of multiplicative and additive functions.
In the present paper, we treat the functional equation (1.2) on a general
class of semigroups.
The contributions of the present work to the knowledge about solutions of
(1.2) are the following :

  1. (1)

The setting has $S$ to be a semigroup, not necessarily generated by its
squares, or a monoid.

  2. (2)

We solve Equation (1.3) on semigroups.

  3. (3)

We relate the solutions of (1.2) to the functional equation (1.3) on
semigroups, and find explicit formulas for the solutions on a larger class of
semigroups.

The outline of the paper is as follows : In the next section we give notations
ans terminology. In the third section we solve the functional equation (1.3)
on semigroups, and we obtain the explicit formulas for the solutions of
Equation (1.2) on a larger class of semigroups $S$.

##  2\. Notations and Terminology

Throughout this paper $S$ denotes a semigroup.
A function $A:S\rightarrow\mathbb{C}$ is additive if $A(xy)=A(x)+A(y)$ for all
$x,y\in S$.
A function $\chi:S\rightarrow\mathbb{C}$ is multiplicative if
$\chi(xy)=\chi(x)\chi(y)$ for all $x,y\in S$.
A function $f:S\rightarrow\mathbb{C}$ is central if $f(xy)=f(yx)$ for all
$x,y\in S$, and $f$ is abelian if $f$ is central and $f(xyz)=f(xzy)$ for all
$x,y,z\in S.$
If $S$ is a semigroup, we define the nullspace

$\mathcal{N}_{\mu}(\sigma,S):=\left\\{\theta:S\rightarrow\mathbb{C}\mid\theta(xy)-\mu(y)\theta(\sigma(y)x)=0,\quad
x,y\in S\right\\}.$

For any subset $T\subseteq S$ we define $T^{2}:=\\{xy\ |\ x,y\in T\\}$. If
$\chi:S\rightarrow\mathbb{C}$ is a multiplicative function and $\chi\neq 0$,
we define the sets

$I_{\chi}:=\\{x\in S\mid\chi(x)=0\\}$ $P_{\chi}:=\\{p\in I_{\chi}\backslash
I_{\chi}^{2}\ |up,pv,upv\in I_{\chi}\backslash I_{\chi}^{2}\ \text{for all}\
u,v\in S\backslash I_{\chi}\\}.$

Notice that $I_{\chi}$ is a subsemigroup of $S$ and a prime ideal of $S$.

For any function $f:S\rightarrow\mathbb{C}$ we define the function
$f^{*}(x)=\mu(x)f(\sigma(x))$,
$x\in S$, we call $f^{e}:=\frac{f+f^{*}}{2}$ the even part of $f$ and
$f^{\circ}:=\frac{f-f^{*}}{2}$ its odd part. The function $f$ is said to be
even if $f=f^{*}$, and $f$ is said to be odd if $f=-f^{*}$. If
$g,h:S\rightarrow\mathbb{C}$ are two functions we define the function

$(g\otimes h)(x,y):=g(x)h(y),\ x,y\in S.$

For a topological semigroup $S$ let $C(S)$ denote the algebra of continuous
functions from $S$ into $\mathbb{C}$.

##  3\. Main result

The following Lemma will be used later.

######  Lemma 3.1.

Let $k,l:S\rightarrow\mathbb{C}$ be a solution of the functional equation
(1.3) with $k\neq 0$. Then

  1. (1)

$k(xy)=-k^{*}(yx)$ for all $x,y\in S$.

  2. (2)

If $k=k^{*}$, then $k(xyz)=0$ for all $x,y,z\in S$.

###### Proof.

(1) Let $x,y\in S$ be arbitrary. By interchanging $x$ and $y$ in (1.3) we get
that $\mu(y)k\left(x\sigma(y)\right)=-\mu(x)k\left(y\sigma(x)\right)$, and if
we apply this identity to the pair $\left(x,\sigma(y)\right)$, we get
$\mu\left(\sigma(y)\right)k\left(xy\right)=-\mu(x)k\left(\sigma(yx)\right)$.
Multiplying this by $\mu(y)$ and by using that $\mu:S\rightarrow\mathbb{C}$ is
a multiplicative function such that $\mu\left(y\sigma(y)\right)=1$ for all
$y\in S$, we get $k(xy)=-k^{*}(yx)$ for all $x,y\in S$.
(2) By using (1), we get

$k(xyz)=-k^{*}(zxy)=k(yzx)=-k^{*}(xyz),\quad\text{for all}\quad x,y,z\in S.$

So if $k=k^{*}$, we get that $k(xyz)=-k(xyz)$ for all $x,y,z\in S$. This
implies that $k(xyz)=0$. This completes the proof of Lemma 3.1. ∎

In the following proposition we extend the results obtained by Ajebbar and
Elqorachi [2, Proposition 3.3] on semigroups generated by their squares and by
Ebanks [6, Theorem 4.2] on monoids to general semigroups.

######  Proposition 3.2.

The solutions of the functional equation (1.3) with $k\neq 0$ are the
following pairs :

  1. (1)

$k$ is any non-zero function such that $k=0$ on $S^{2}$ and $l=ck$, where
$c\in\mathbb{C}$ is a constant.

  2. (2)

$k=c_{1}\dfrac{\chi-\chi^{*}}{2}\quad\text{and}\quad
l=\dfrac{\chi+\chi^{*}}{2}+c_{2}\dfrac{\chi-\chi^{*}}{2},$

where $\chi:S\rightarrow\mathbb{C}$ is a multiplicative function such that
$\chi^{*}\neq\chi$ and
$c_{1}\in\mathbb{C}\backslash\\{0\\},c_{2}\in\mathbb{C}$ are constants.

  3. (3)

$k=\left\\{\begin{matrix}\chi A&on&S\backslash{{I}_{\chi}}\\\
0&on&{{I}_{\chi}}\backslash{{P}_{\chi}}\\\ \rho&on&{{P}_{\chi}}\\\
\end{matrix}\right.\quad\text{and}\quad
l=\left\\{\begin{matrix}\chi(1+cA)&on&S\backslash{{I}_{\chi}}\\\
0&on&{{I}_{\chi}}\backslash{{P}_{\chi}}\\\ c\rho&on&{{P}_{\chi}}\\\
\end{matrix}\ ,\right.$

where $c\in\mathbb{C}$ is a constant, $\chi:S\rightarrow\mathbb{C}$ is a non-
zero multiplicative function and $A:S\backslash I_{\chi}\rightarrow\mathbb{C}$
is a non-zero additive function such that $\chi^{*}=\chi$, $A\circ\sigma=-A$,
and $\rho:P_{\chi}\rightarrow\mathbb{C}$ is the restriction of $k$ to
$P_{\chi}$ such that $\rho^{*}=-\rho$. In addition we have the following
conditions:
(I): If $x\in\left\\{up,pv,upv\right\\}$ for $p\in P_{\chi}$ and $u,v\in
S\backslash I_{\chi}$, then $x\in P_{\chi}$ and we have respectively
$\rho(x)=\rho(p)\chi(u)$, $\rho(x)=\rho(p)\chi(v)$, or
$\rho(x)=\rho(p)\chi(uv)$.
(II): $k(xy)=k(yx)=0$ for all $x\in S\backslash I_{\chi}$ and $y\in
I_{\chi}\backslash P_{\chi}$.

Conversely, if $(k,l)$ are given by the formulas in (1), (2) or (3) with
conditions (I) and (II) holding and if $k$ is abelian in case (3), then
$(k,l)$ satisfies (1.3).

Furthermore, if $S$ is a topological semigroup and $k\in C(S)$, then
$\chi,\chi^{*}\in C(S)$, $A\in C(S\backslash I_{\chi})$, and $\rho\in
C(P_{\chi})$.

###### Proof.

We check by elementary computations that if $k$ and $l$ are of the forms
(1)–(3) then $(k,l)$ is a solution of (1.3).

Conversely, we will discuss two cases according to whether $k$ and $l$ are
linearly dependent or not.
First case : $k$ and $l$ are linearly dependent. There exists $c\in\mathbb{C}$
such that $l=ck$. From (1.3) we get

$\mu(y)k(x\sigma(y))=ck(x)k(y)-ck(y)k(x)=0,\quad\text{for all}\quad x,y\in S.$
(3.1)

Since $\mu(y\sigma(y))=1$ for all $y\in S$, we deduce from (3.1) that $k=0$ on
$S^{2}$. This occurs in (1) of Proposition 3.2.
Second case : $k$ and $l$ are linearly independent. Since $\mu(y\sigma(y))=1$
for all $y\in S$, we multiply (1.3) by $\mu(\sigma(y))$ and we get

$k(x\sigma(y))=\mu(\sigma(y))k(x)l(y)-\mu(\sigma(y))k(y)l(x),\quad\text{for
all}\quad x,y\in S.$ (3.2)

By using the associativity of the semigroup operation, we can compute
$k(x\sigma(y)\sigma(z))$ first as $k((x\sigma(y))\sigma(z))$ and then as
$k(x(\sigma(y)\sigma(z)))$ under the identity (3.2) and compare the results to
obtain

$-k(z)l(x\sigma(y))=k(x)\left[\mu(\sigma(y))l(yz)-\mu(\sigma(y))l(y)l(z)\right]+\\\
l(x)\left[\mu(\sigma(y))k(y)l(z)-\mu(\sigma(y))k(yz)\right].$ (3.3)

Since $k\neq 0$, there exists $z_{0}\in S$ such that $k(z_{0})\neq 0$, and
then we deduce from the identity above that

$l(x\sigma(y))=k(x)f(y)+l(x)g(y),$ (3.4)

where

$f(y)=\dfrac{-1}{k(z_{0})}\left[\mu(\sigma(y))l(yz_{0})-\mu(\sigma(y))l(y)l(z_{0})\right],$

and

$g(y)=\dfrac{1}{k(z_{0})}\left[\mu(\sigma(y))k(yz_{0})-\mu(\sigma(y))k(y)l(z_{0})\right].$
(3.5)

By substituting (3.4) into (3.3), we get

$\displaystyle
k(x)(-k(z)f(y))+l(x)(-k(z)g(y))=k(x)\left[\mu(\sigma(y))l(yz)-\mu(\sigma(y))l(y)l(z)\right]+$
$\displaystyle l(x)\left[\mu(\sigma(y))k(y)l(z)-\mu(\sigma(y))k(yz)\right].$

Using the linear independence of $k$ and $l$, we obtain

$\mu(\sigma(y))l(yz)=\mu(\sigma(y))l(y)l(z)-k(z)f(y),$

and

$\mu(\sigma(y))k(yz)=\mu(\sigma(y))k(y)l(z)+k(z)g(y).$ (3.6)

From (1.3) and (3.5) we deduce that the function $g(y)$ can be written as

$g(y)=\alpha\mu(\sigma(y))k(y)+\beta\mu(\sigma(y))l(y),$

where

$\alpha=\dfrac{\mu(\sigma(z_{0}))l(\sigma(z_{0}))-l(z_{0})}{k(z_{0})}\quad\text{and}\quad\beta=\dfrac{-\mu(\sigma(z_{0}))k(\sigma(z_{0}))}{k(z_{0})}.$

From the last form of $g(y)$ and taking into account that $\mu(y\sigma(y))=1$
for all $y\in S$, equation (3.6) can be written as follows

$k(yz)=k(y)\left[l(z)+\alpha k(z)\right]+\beta k(z)l(y).$ (3.7)

On the other hand from equation (3.2) we get

$k(yz)=k(y)l^{*}(z)-k^{*}(z)l(y),$ (3.8)

then by comparing (3.7) and (3.8) and using the linear independence of $k$ and
$l$ we obtain

$l(z)+\alpha k(z)=l^{*}(z),$ (3.9) $\beta k(z)=-k^{*}(z),\quad\text{for
all}\quad z\in S.$ (3.10)

Since $k\neq 0$, then we get from (3.10) that $\beta\neq 0$ and $\beta^{2}=1$.
This means that $k=k^{*}$ or $k=-k^{*}$. If $k=k^{*}$ then according to Lemma
3.1 (2), $k(xyz)=0$ for all $x,y,z\in S$. This implies that

$k(x)l(yz)=k(yz)l(x),\quad\text{for all}\quad x,y,z\in S.$ (3.11)

Since $k$ and $l$ are linearly independent, then $k\neq 0$ on $S^{2}$, so
there exists $y_{0},z_{0}\in S$ such that $k(y_{0}z_{0})\neq 0$. By letting
$y=y_{0}$ and $z=z_{0}$ in (3.11), we obtain $l=bk$ for some constant
$b\in\mathbb{C}$. This contradicts the fact that $k$ and $l$ are linearly
independent. Now if $k=-k^{*}$ then by using the same computations as in the
proof of [3, Theorem 2.1], we get $l^{\circ}=ck$ where $c\in\mathbb{C}$ is a
constant and that the pair $(k,l^{e})$ satisfies the sine addition law

$k(xy)=k(x)l^{e}(y)+k(y)l^{e}(x),\quad x,y\in S.$

Hence according to [8, Theorem 3.1] and taking into account that $k\neq 0$,
the pair falls into two categories:
(i) $k=c_{1}\dfrac{\chi_{1}-\chi_{2}}{2}$ and
$l^{e}=\dfrac{\chi_{1}+\chi_{2}}{2}$ , where
$\chi_{1},\chi_{2}:S\rightarrow\mathbb{C}$ are different multiplicative
functions and $c_{1}\in\mathbb{C}\backslash\\{0\\}$ is a constant. Since
$l=l^{e}+l^{\circ}$ and $k=-k^{*}$ we deduce that

$k=c_{1}\dfrac{\chi-\chi^{*}}{2}\quad\text{and}\quad
l=\dfrac{\chi+\chi^{*}}{2}+c_{2}\dfrac{\chi-\chi^{*}}{2},$

where $\chi:S\rightarrow\mathbb{C}$ is a multiplicative function such that
$\chi^{*}\neq\chi$ and
$c_{1}\in\mathbb{C}\backslash\\{0\\},c_{2}\in\mathbb{C}$ are constants. This
occurs in part (2) of Proposition 3.2.
(ii)

$k=\left\\{\begin{matrix}\chi A&on&S\backslash{{I}_{\chi}}\\\
0&on&{{I}_{\chi}}\backslash{{P}_{\chi}}\\\ \rho&on&{{P}_{\chi}}\\\
\end{matrix}\right.\quad\text{and}\quad l^{e}=\chi\ ,$

where $\chi:S\rightarrow\mathbb{C}$ is a non-zero multiplicative function and
$A:S\backslash I_{\chi}\rightarrow\mathbb{C}$ is a non-zero additive function
such that $\chi^{*}=\chi$, $A\circ\sigma=-A$, and
$\rho:P_{\chi}\rightarrow\mathbb{C}$ is the restriction of $k$ to $P_{\chi}$
such that $\rho^{*}=-\rho$ and we have the conditions (I) and (II). Since
$l=l^{e}+l^{\circ}$ and $l^{\circ}=ck$, we can see that

$l=\left\\{\begin{matrix}\chi(1+cA)&on&S\backslash{{I}_{\chi}}\\\
0&on&{{I}_{\chi}}\backslash{{P}_{\chi}}\\\ c\rho&on&{{P}_{\chi}}\\\
\end{matrix}\ .\right.$

This is part (3).

The topological statements are easy to verify. This completes the proof of
Proposition 3.2. ∎

Now we solve the functional equation (1.2) on a t-compatible semigroup. A
notion which was recently introduced by Ebanks [10, Definition 4.2].

######  Definition 3.3.

Let $S$ be a semigroup. We will say that $S$ is compatible, if $S^{2}=S$ and
for every prime ideal $I\subset S$ the following condition holds.

$\text{For each}\quad q\in I\quad\text{there exists}\quad w_{q}\in S\backslash
I\quad\text{such that}\quad qw_{q}\in I^{2}.$ (3.12)

We say that a topological semigroup $S$ is t-compatible, if $S=S^{2}$ and
condition (3.12) holds for every prime ideal $I$.

The following result shows that the solutions of (1.2) on a t-compatible
semigroup have the same forms found in [2, Theorem 4.3] for semigroups
generated by their squares.

######  Theorem 3.4.

Let $S$ be a t-compatible semigroup, and suppose that $f,g,h\in C(S)$ satisfy
(1.2). Then $f,g,h$ belong to one of the four families below. In addition
$\chi,\chi^{*},\theta\in C(S)$, and $A\in C(S\backslash I_{\chi})$.

  1. (1)

$f=\theta$, $g=0$ and $h$ is arbitrary, where
$\theta\in\mathcal{N}_{\mu}(\sigma,S)$.

  2. (2)

$f=\theta$, $g$ is arbitrary and $h=0$, where
$\theta\in\mathcal{N}_{\mu}(\sigma,S)$.

  3. (3)

$f=\theta+\alpha\dfrac{\chi+\chi^{*}}{2}+\beta\dfrac{\chi-\chi^{*}}{2}$ and
$g\otimes
h=2\left(\beta\dfrac{\chi+\chi^{*}}{2}+\alpha\dfrac{\chi-\chi^{*}}{2}\right)\otimes\dfrac{\chi-\chi^{*}}{2}$,
where $\alpha,\beta\in\mathbb{C}$ are constants,
$\theta\in\mathcal{N}_{\mu}(\sigma,S)$ and $\chi:S\rightarrow\mathbb{C}$ is a
multiplicative function such that $\left(\alpha,\beta\right)\neq(0,0)$ and
$\chi\neq\chi^{*}$.

  4. (4)

$\left\\{\begin{array}[]{l}f=\theta+\dfrac{\alpha}{2}\chi
A+\dfrac{\beta}{4}\chi A^{2},\quad g=\alpha\chi+\beta\chi A,\quad h=\chi
A,\quad\text{ on }\quad S\backslash I_{\chi}\\\ f=\theta,\quad g=0,\quad
h=0\quad\text{ on }\quad I_{\chi},\end{array}\right.$

where $\alpha,\beta\in\mathbb{C}$ are constants,
$\theta\in\mathcal{N}_{\mu}(\sigma,S)$ and $\chi:S\rightarrow\mathbb{C}$ is a
non-zero multiplicative function such that
$\left(\alpha,\beta\right)\neq(0,0)$, $\chi=\chi^{*}$ and $A:S\backslash
I_{\chi}\rightarrow\mathbb{C}$ is a non-zero additive function such that
$A\circ\sigma=-A$.

###### Proof.

We check by elementary computations that if $f$, $g$ and $h$ are of the forms
(1)–(4) then $(f,g,h)$ is a solution of (1.2).
Let $f,g,h:S\rightarrow\mathbb{C}$ satisfy the functional equation (1.2). If
$g=0$ then $h$ is arbitrary and $f=\theta$ where
$\theta\in\mathcal{N}_{\mu}(\sigma,S)$. If $h=0$ then $g$ will be arbitrary
and $f=\theta$ where $\theta\in\mathcal{N}_{\mu}(\sigma,S)$. So from now on we
assume that $g\neq 0$ and $h\neq 0$. According to [2, Lemma 4.2 (1)], there
exists a function $l:S\rightarrow\mathbb{C}$ such that

$h(xy)=g^{*}(x)l(y)-g(y)l^{*}(x),\quad\text{for all}\quad x,y\in S.$

This implies that $h(xy)=-h^{*}(yx)$, so

$h(xyz)=-h^{*}(zxy)=h(yzx)=-h^{*}(xyz),$

for all $x,y,z\in S$. Since $S^{2}=S$ we deduce that $h=-h^{*}$ and then
accordding to [2, Lemma 4.2 (6)], there exists a constant $b\in\mathbb{C}$
such that $g^{\circ}=bh$, so we discuss the two cases : $b=0$ and $b\neq 0$.
First case : $b\neq 0$. According to the proof of [2, Theorem 4.3 case A]
there exists a function $m:S\rightarrow\mathbb{C}$ and a constant
$c_{3}\in\mathbb{C}$ such that the pair $(h,m)$ satisfies the $\mu$-sine
subtraction law (1.3), and $g^{e}=c_{3}m^{e}$, then according to Proposition
3.2 and taking into account that $h$ is a non-zero odd function, the pair
$(h,m)$ falls into the categories:
(i) $h=c_{1}\dfrac{\chi-\chi^{*}}{2}$ and
$m=\dfrac{\chi+\chi^{*}}{2}+\alpha\dfrac{\chi-\chi^{*}}{2}$ where
$c_{1}\in\mathbb{C}\backslash\\{0\\},\alpha\in\mathbb{C}$ are constants and
$\chi:S\rightarrow\mathbb{C}$ is a multiplicative function such that
$\chi\neq\chi^{*}$, then by using similar computations to the ones of the
proof of [2, Theorem 4.3 case A (i)], we get that

$g=c_{3}\dfrac{\chi+\chi^{*}}{2}+c_{2}\dfrac{\chi-\chi^{*}}{2}\quad\text{and}\quad
f=\theta+\dfrac{c_{1}}{2}\left(c_{2}\dfrac{\chi+\chi^{*}}{2}+c_{3}\dfrac{\chi-\chi^{*}}{2}\right),$

where $c_{2}=bc_{1}\in\mathbb{C}$ is a constant and
$\theta\in\mathcal{N}_{\mu}(\sigma,S)$. This occurs in part (3) with
$\alpha=\dfrac{c_{1}c_{2}}{2}$ and $\beta=\dfrac{c_{1}c_{3}}{2}$.
(ii)

$h=\left\\{\begin{matrix}\chi A&on&S\backslash{{I}_{\chi}}\\\
0&on&{{I}_{\chi}}\backslash{{P}_{\chi}}\\\ \rho&on&{{P}_{\chi}}\\\
\end{matrix}\right.\quad\text{and}\quad
m=\left\\{\begin{matrix}\chi(1+cA)&on&S\backslash{{I}_{\chi}}\\\
0&on&{{I}_{\chi}}\backslash{{P}_{\chi}}\\\ c\rho&on&{{P}_{\chi}}\\\
\end{matrix}\ ,\right.$

where $c\in\mathbb{C}$ is a constant, $\chi:S\rightarrow\mathbb{C}$ is a non-
zero multiplicative function and $A:S\backslash I_{\chi}\rightarrow\mathbb{C}$
is a non-zero additive function such that $\chi^{*}=\chi$, $A\circ\sigma=-A$,
and $\rho:P_{\chi}\rightarrow\mathbb{C}$ is a function such that
$\rho^{*}=-\rho$ and $\rho$ satisfy the condition (I) from Proposition 3.2.
Let $y\in I_{\chi}$. Since $I_{\chi}$ is a prime ideal (if nonempty) and $S$
is t-compatible, then either $y\in I_{\chi}^{2}$ or there exists $w_{y}\in
S\backslash I_{\chi}$ such that $yw_{y}\in I_{\chi}^{2}$. It follows from
condition (I) that $h(y)=0$. Proceeding exactly as in the proof of [2, Theorem
4.3 case A (ii)], we find that

$g=c_{3}\chi+c_{2}\chi A\quad\text{on}\quad S\backslash
I_{\chi}\quad\text{and}\quad g=0\quad\text{on}\quad I_{\chi},$

and

$f=\theta+\dfrac{c_{3}}{2}\chi A+\dfrac{c_{2}}{4}\chi A^{2}\quad\text{on}\quad
S\backslash I_{\chi}\quad\text{and}\quad f=\theta\quad\text{on}\quad
I_{\chi},$

where $c,c_{2},c_{3}\in\mathbb{C}$ are constants,
$\chi:S\rightarrow\mathbb{C}$ is a non-zero multiplicative function and
$A:S\backslash I_{\chi}\rightarrow\mathbb{C}$ is a non-zero additive function
such that $\chi^{*}=\chi$, $A\circ\sigma=-A$ and
$\theta\in\mathcal{N}_{\mu}(\sigma,S)$. This is part (4) of Theorem 3.4 with
$\alpha=c_{3}$ and $\beta=c_{2}$.
Second case : $b=0$. According to the proof of [2, Theorem 4.3 case B] there
exists a constant $\lambda\in\mathbb{C}\backslash\\{0\\}$ such that the pair
$\left(h,\dfrac{\lambda}{2}g\right)$ satisfies the sine addition law

$h(xy)=h(x)\left(\dfrac{\lambda}{2}g(y)\right)+h(y)\left(\dfrac{\lambda}{2}g(x)\right),$
(3.13)

for all $x,y\in S$. Then according to [8, Theorem 3.1] and taking into account
that $h$ is a non-zero odd function and $g$ is even, we have the following
possibilities:
(i) $h=c_{1}\dfrac{\chi-\chi^{*}}{2}$ and $g=c_{2}\dfrac{\chi+\chi^{*}}{2}$,
where $c_{1},c_{2}\in\mathbb{C}\backslash\\{0\\}$ are constants and
$\chi:S\rightarrow\mathbb{C}$ is a multiplicative function such that
$\chi\neq\chi^{*}$, then we get by using the same computations as in the proof
of [2, Theorem 4.3 case B (i)] that

$f=\theta+\dfrac{c_{1}c_{2}}{2}\dfrac{\chi-\chi^{*}}{2},$

where $\theta\in\mathcal{N}_{\mu}(\sigma,S)$. This is part (3) with $\alpha=0$
and $\beta=\dfrac{c_{1}c_{2}}{2}$.
(ii)

$h=\left\\{\begin{matrix}\chi A&on&S\backslash{{I}_{\chi}}\\\
0&on&{{I}_{\chi}}\backslash{{P}_{\chi}}\\\ \rho&on&{{P}_{\chi}}\\\
\end{matrix}\right.\quad\text{and}\quad g=c_{1}\chi\ ,$

where $c_{1}\in\mathbb{C}\backslash\left\\{0\right\\}$ is a constant,
$\chi:S\rightarrow\mathbb{C}$ is a non-zero multiplicative function and
$A:S\backslash I_{\chi}\rightarrow\mathbb{C}$ is a non-zero additive function
such that $\chi^{*}=\chi$, $A\circ\sigma=-A$, and
$\rho:P_{\chi}\rightarrow\mathbb{C}$ is a function such that $\rho^{*}=-\rho$
and the condition (I) is holding.
Proceeding exactly as in the previous case we show that $h=0$ on $I_{\chi}$.
Then by using similar computations to the ones of the proof of [2, Theorem 4.3
case B (ii)], we get that

$f=\theta+\dfrac{c_{1}}{2}\chi A\quad\text{on}\quad S\backslash I_{\chi},$

where $\theta\in\mathcal{N}_{\mu}(\sigma,S)$. This occurs in part (4) with
$\beta=0$ and $\alpha=\dfrac{c_{1}}{2}$. This completes the proof of Theorem
3.4. ∎

######  Remark 3.5.

Note that if the semigroup $S$ is not t-compatible, d’Alembert’s equation
(1.2) may have nontrivial solutions taking arbitrary values at some points
(See [7, Example 5.3]).

### Acknowledgment

## References

  * [1] Aczél, J., Dhombres, J., Functional equations in several variables with applications to mathematics, Information theory and to the natural and social sciences. Encyclopedie of Mathematics and its Applications, vol. 31, Cambridge University Press, Cambridge (34B40) MR1004465 (90h: 39001) (1989).
  * [2] Ajebbar, O., Elqorachi, E., D’Alembert’s other functional equation on semigroups. Aequat.Math, 94 913–930 (2020).
  * [3] Bouikhalene, B., Elqorachi, E., A class of functional equations of type d’Alembert on monoids. In : Anastassiou, G., Rassias, J.M. (eds.) Frontiers in Functional Equations and Analytic Inequalities pp 219–235. Springer, Berlin (2019).
  * [4] D’Alembert, J., Recherche sur la courbe que forme une corde tendue mise en vibration. History of the Academy, vol I, 1747, Berlin pp 214–219 (1747).
  * [5] D’Alembert, J., Recherche sur la courbe que forme une corde tendue mise en vibration. History of the Academy, vol II, 1747, Berlin pp 220–249 (1747).
  * [6] Ebanks, B., The sine addition and subtraction formulas on semigroups. Acta Math. Hungar, 164(2) 533–555 (2021).
  * [7] Ebanks, B., D’Alembert’s other functional equation on monoids revisited. Publ. Math. Debrecen, (2021).
  * [8] Ebanks, B., Around the sine addition law and d’Alembert’s equation on semigroups. Results Math, 77, 11 (2022). https://doi.org/10.1007/s00025-021-01548-6
  * [9] Ebanks, B., Stetkaer, H., D’Alembert’s other functional equation on monoids with involution. Aequat.Math, 89 187–206 (2015).
  * [10] Ebanks, B., The Cosine-Sine functional equation on semigroups. Ann. Math, vol.36, no.1, 2022, pp 30-52. https://doi.org/10.2478/amsil-2021-0012
  * [11] Kannappan, Pl., Functional equations and inequalities with applications. Springer monographs in Mathematics, Springer, New York, (2009) https://doi.org/10.1007/987-0-387-89492-8
  * [12] Stetkaer, H., Functional equations on Groups. World scientific Publishing CO, Singapore (2013).