A joint explanation of infant and old age mortality

Peter Richmond1, Bertrand M. Roehner2

Preprint version of the paper which appeared as: “Journal of Biological
Physics” 47,131-141 (2021)

Abstract Infant deaths and old age deaths are very different. The former are
mostly due to severe congenital malformations of one or a small number of
specific organs. On the contrary, old age deaths are largely the outcome of a
long process of deterioration which starts in the 20s and affects almost all
organs. In terms of age-specific death rates, there is also a clear
distinction: the infant death rate falls off with age, whereas the adult and
old age death rate increases exponentially with age in conformity with
Gompertz’s law. An additional difference is that whereas aging and old age
death have been extensively studied, infant death received much less
attention. To our knowledge the two effects have never been inter-connected.
Clearly, it would be satisfactory to explain the two phenomena as being two
variants within the same explanatory framework. In other words, a mechanism
providing a combined explanation for the two forms of mortality would be
welcome. This is the purpose of the present paper. We show here that the same
biological effects can account for the two cases provided there is a
difference in their severity: death triggered by isolated lethal anomalies in
one case and widespread wear-out anomalies in the second. We show that quite
generally this mechanism leads indeed, respectively, to a declining and an
upgoing death rate. Moreover, this theoretical framework leads to the
conjecture that the severity of the death effects, whether in infancy or old
age, are higher for organisms which are comprised of a larger number of
organs. Finally, let us observe that the main focus of the paper is the
drastic difference of the age-specific death rates (i.e. decreasing versus
increasing) because this difference is found in many species, whereas the
question of the best fit (e.g. Gompertz versus Weibull) is rather specific to
human mortality.

1: School of Physics, Trinity College Dublin, Ireland. Email:
<EMAIL_ADDRESS>
2: Corresponding author. Institute for Theoretical and High Energy Physics
(LPTHE), Pierre and Marie Curie Campus, Sorbonne University, National Center
for Scientific Research (CNRS), Paris, France. Email<EMAIL_ADDRESS>
##  1 Introduction: infant versus old age mortality

In this paper we consider the shape of the curves of death rates111We use the
standard definitions of death rates, namely: $\mu(x)=\Delta y/(\Delta x\times
y)$ where $\Delta y$ is the number of deaths in a given age interval of size
$\Delta x$ and $y$ is the size of the population at the beginning of the age
interval under consideration. With this definition $\mu(x)$ is the probability
(per unit of time) that a person who has reached age $x$, will die in the
subsequent age interval, see appendix A.as a function of age.

Deaths in infancy versus old age death can be characterized in two ways [1,2]:
(i) their age-specific death rates (see Fig.1) (ii) the biological processes
which are at work (wear-in versus wear-out as discussed below.)

###  1.1 Shape of the age-specific death rate

In infancy the death rate decreases with age whereas in old age it increases
(Fig.1).

Fig.1: Infant versus old age human mortality. The data are for the US over the
period 1999-2016. Between birth and the age of 10 (note the log-log scale) the
infant mortality rate falls off as a power law: $\mu_{b}=A/x^{\gamma}$ where
the exponent $\gamma$ is usually of the order of 1. After the infant phase
comes the aging phase (note the lin-log scale) during which the death rate
increases exponentially $\mu(x)=\mu_{0}\exp(\alpha x)$ in agreement with
Gompertz’s law. Source: Wonder-CDC data base for detailed mortality.

In medical terminology infancy refers to new born under one year of age.
However, as the decrease of the death rate continues until the age of 10, it
seems appropriate to extend the meaning of the term to the whole age interval
over which the death rate is decreasing. This is what was done in the two
papers cited above and we use the same terminology here. For humans, the
increase of the death rate is described by the well-known law of Gompertz [3].
This law can be summarized by saying that the death rate doubles approximately
every 10 years of age.

###  1.2 Wear-in versus wear-out

In the terminology of reliability studies, infant mortality is described by a
wear-in process, that is to say a phase during which the organs of the new-
born start to work which results in the elimination of the organisms which are
beset with an organ which does not work appropriately. On the contrary, old
age death is described as a wear-out process in which all organs experience
damages due to continuous use. The lungs catch less oxygen, the bones become
more fragile, the arteries become less elastic, and so on. Death occurs
eventually due to the failure of a crucial organ (usually the heart and lungs)
but actually this failure is favored by the degradation of the whole organism.
For instance, when the arteries become less elastic, when the lungs become
less effective, it becomes more difficult for the heart to ensure blood
circulation. This means that a heart failure does not come about in isolation
but rather in relation with the wear of other organs.

The purpose of this article is to show how the feature (1) results from the
feature (2). However, before coming to that we wish to explain how our study
fits into the broad framework of aging and senescence studies.

Why do we think that infant mortality is an essential component in the
understanding of aging? There are several reasons that are developed below.

##  2 The key-role of congenital malformations

###  2.1 The real challenges of aging models

Not surprisingly, the modeling of aging and senescence has received great
attention. A comprehensive review can be found in two papers by Leonid
Gavrilov and and Natalia Gavrilova [4,5]. Readers will find in these papers a
comprehensive and very readable account of the literature of aging
models222Whereas these authors share our approach based on reliability
science, and whereas infant mortality is a standard notion in reliability,
they devote only one page (in a total of 58 for the two papers) to the
question of infant mortality. This disproportion reflects the overwhelming
predominance of aging and senescence studies.. In the following subsections we
explain why infant mortality is a simpler and more fundamental effect than old
age mortality.

###  2.2 Great diversity in the shape of the death rate in old age

Gompertz (1825) was the first to propose that the rapid rise in death rate of
humans as they aged prior to death followed and exponential law. Other authors
have since advocated a description based on Weibull functions. See for example
[6,7,8]. An interesting review of the implications can be found in Roberto
Ricklefs and Alex Scheuerlein [9]. Of especial note here is the proposal that
the Weibull form holds for death by particular causes whereas the Gompertz
form holds for death by all causes. We shall return to the point later.
However neither form predicts the hyperbolic fall in deathrate which happens
in early years. Neither the Weibull nor Gompertz forms yields insight into
data for species which exhibit a levelling off of the death rate at very high
ages.

Across species the hyperbolic decrease of the death rate in the infancy phase
appears to be a phenomenon that is more widespread than its exponential (i.e.
Gompertz-like) increase in adulthood. Indeed, there is much more diversity in
old age death rates than in infancy death rates; see in Berrut et al. (2016)
the graph based on zoo species.

In addition for some species documented in [5, p. 18 and 33] there is a marked
effect of leveling-off in old age. For instance, house flies have a maximum
life span of 40 days but around the age of 15 days the exponential growth of
the death rate is replaced by a section where it is practically flat.

In humans the dominant diseases in old age are not the same nowadays as one
century ago. Presently, there is a prevalence of heart, cancer and Alzheimer’s
disease whereas around 1900 infectious diseases were still common. Thus, with
organisms being confronted to different challenges, one should not be
surprised to see changes in the shape of the death rate in old age.

Finally, the individuals who reach old age were “filtered” and selected by the
diseases to which they were confronted. If one could observe the signature of
the immune system one would see that the immune system of persons of old age
is not the same in 2020 than in 1900, and also not the same in developing
countries than in developed countries.

###  2.3 Common characteristics of embryonic and infancy death rates

It has been shown recently [10] that for zebrafish333For a study of embryonic
death rates, zebrafish have two great advantages. (i) As for most species of
fish, fertilization of the eggs occurs outside of the body of the female (ii)
The shell of the eggs is transparent. Taken together, these two features imply
that one can observe the embryos immediately after fertilization, something
that is impossible either for humans, birds or rotifers. the embryonic death
rate is by far highest at the beginning of the embryogenesis, an observation
which suggests that most of these deaths are due to mistakes in the
manufacturing processes of the oocyte (femelle egg) and sperm cell. If instead
the deaths would be due to mutations during the embryogenesis they would be
uniformly distributed or even (through a cumulative effect) concentrated in
the late phase of embryogenesis.

For humans embryonic deaths would in medical terminology be referred to as
fetal deaths or still births. In statistical releases this pre-birth mortality
is treated apart from infant mortality mostly because there is a great
uncertainty about fetal death data. However, from a biological perspective,
infant mortality is nothing but the continuation of fetal death, albeit in
more severe form due to disconnection of the link with the organism of the
mother.

Similarly, the infant death rate is by far highest immediately after birth. By
the same argument, it appears that most of these deaths are due to faults in
the manufacuring of the embryo. For instance, in mamals lung malformations are
without consequence as long as the fetus receives its blood from the mother
but they will lead to death as soon as this connection is interrupted.
Embryonic and infant deaths along with the malformations which are not
immediately lethal give us global information about the underlying
manufacturing processes.

###  2.4 The effects of congenital defects and of aging occur jointly

At first sight it may seem that the infant death rate can be easily described
and explained through the process of elimination of individuals with
malformations. Clinical data show that in the first weeks after birth most of
the deaths are due to congenital anomalies (percentage data are given in [1].
When the most serious malformations have been eliminated the rest of the
cohort is less likely to die.

However, the previous explanation is not really satisfactory for the following
reason. In fact, deaths due to congenital anomalies are not limited to young
age but continue during the whole life. For instance, a congenital defect of
heart valves may be of no consequence until the age of 60 or 70 when the
defect becomes more serious because the valve’s leaflets become stiffer, see
[11].

In other words, the wear-in and wear-out processes should not be seen as
occurring successively but rather simultaneously; it is their strength, not
their existence, which changes in the course of time. Immediately after birth,
wear-in is completely dominant, whereas in old age it is wear-out which is
predominant. I short, taken alone the elimination of congenital malformations
cannot explain the decrease of the death rate. In order to make it work we
need to define both wear-in and wear-out more precisely.

In the next section we will use the feature already mentioned above, namely
that the infant mortality is usually due to a congenital defect in one
important organ (e.g. heart, lung, brain, liver, and so on) whereas the wear-
out is due to parallel degradation of various important organs.

##  3 Modeling the wear-in and wear-out processes

###  3.1 Decomposition into vital organs

The first step is to decompose any organism into its vital organs. For
instance, Fig.2 shows a decomposition into 4 organs, that could be heart,
lung, brain and temperature regulation.

Fig.2 Decomposition of an organism into vital organs and difference between
wear-in and wear-out mechanisms. The first line shows a wear-in death. It is
the consequence of the failure of a single vital organ. The second line shows
a wear-out death as the consequence of uniform deterioration of all vital
organs. The graphs on the right-hand side show the implications of these
mechanisms in terms of age-specific death rates: decreasing for wear-in as
observed in infant death, increasing for wear-out as seen in old-age death.

###  3.2 Description of the organs’ state by random variables

Secondly, we must find a way to describe mathematically whether each organ (as
well as the whole organism) is alive. We do this by defining for each part a
random variable $X_{i}$ which is its age at failure. In the case of humans we
could make this description fairly realistic by giving to the $X_{i}$ values
from interval $(0,125)$ for it should be remembered that 125 years is an upper
bound of human life444This was shown to be a consequence of Gompertz’s law in
[12].. However, as we do not wish to restrict ourselves to only the human
species, we will normalize the interval of the $X_{i}$ to $(0,1)$ where 1
represents the maximum life span of the species.

Now comes the most important step which is to describe the wear-in and wear-
out mechanisms. Let us begin with the simplest case which is the wear-out
mechanism.

###  3.3 Wear-out

The fact that the death of an individual occurs when the last surviving organ
fails is expressed by saying that if $X_{1}=0.5,\ X_{2}=0.3,\ X_{3}=0.7,\
X_{4}=0.1$ (the $X_{i}$ denote the age at death of vital organs as shown in
Fig.2), then the age of death represented by the random variable $Z$ will be
$Z=0.7$, in other words:

$Z=\hbox{Max}(X_{1},X_{2},X_{3},X_{4})$

For the sake of simplicity we assume that the $X_{i}$ are independent and
identically distributed random variables. This assumption has the merit of
making the analytical derivation possible. However, in specific applications
one can take realistic distributions based on clinical data.

$\bullet$ If $f(x)$ and $F(x)$ respectively represent the density function and
the cumulative distribution function of the $X_{i}$, what will be the density
function, $f_{Z}(x)$, of $Z$?

Let us first consider the case of only two organs.

$F_{Z}(x)=P\\{Z\leq x\\}=P\\{\hbox{Max}(X_{1},X_{2})\leq x\\}=P\\{X_{1}\leq
x\hbox{ and }X_{2}\leq x\\}$

Now, the fact that $X_{1}$ and $X_{2}$ are independent means that:

$P\\{X_{1}\in A\hbox{ and }X_{2}\in B\\}=P\\{X_{1}\in A\\}P\\{X_{2}\in B\\}$

where $A$ and $B$ are two subsets of the set of real numbers. Therefore:

$F_{Z}(x)=P\\{X_{1}\leq x\\}P\\{X2\leq x\\}=\left[F(x)\right]^{2}$

which, by differentiation leads to the density function of $Z$:

$f_{Z}(x)=2F^{\prime}(x)F(x)=2f(x)F(x)$

For $p$ parts instead of only two, one gets similarly:

$F_{Z}(x)=\left[F(x)\right]^{p}\Rightarrow
f_{Z}(x)=pf(x)\left[F(x)\right]^{p-1}$ (1)

In order to see what is the shape of this function we consider the simple case
of a random variable with a uniform density over the interval $(0,1)$; in this
case:

$\hbox{for }x\in(0,1):\ f(x)=1,\ F(x)=x$

Thus,

$\hbox{for }x\in(0,1):\ f_{Z}(x)=px^{p-1}$

This function is shown in Fig.3b for $p=2,4,8,15$ We see that it is a fast
increasing function of age. According to the analytical expression $f_{Z}(x)$
is a power law function. This is consistent with a Weibull distribution but
when $p$ becomes large it has the shape of an exponential (as shown in Fig.2b
for $p=15$), a result which is qualitatively consistent with Gompertz’s law
according to which the probability of death increases exponentially with age.

At this point it is interesting to recall earlier comments that the Weibull
form appears consistent with deaths from particular causes. Here we find that
the more elements are present the closer the death rate approaches a Gompertz
exponential form. There are ways this prediction could be checked. One is to
assess death rates from increasingly complex synthetic systems; another albeit
more difficult could be to explore death rates of increasingly complex
biological systms from single cell upwards. This may however be difficult
since complexity in biology brings in multiple organisms but examining death
rates from all causes should lead ultimately to the Gompertz form.

###  3.4 Wear-in

For the example considered above wear-in death would mean that the age of
death is: $W=0.1$, i.e.:

$W=\hbox{Min}(X_{1},X_{2},X_{3},X_{4})$

For the distribution fonction $F_{W}(x)$ we can write:

$F_{W}(x)=P\\{W\leq
x\\}=1-P\\{W>x\\}=1-P\\{\hbox{Min}(X_{1},X_{2})>x\\}=1-P\\{X_{1}>x\hbox{ and
}X_{2}>x\\}$

Again using the independence property, one gets:

$F_{W}(x)=1-P\\{X_{1}>x\\}P\\{X_{2}>x\\}=1-\left[1-F(x)\right]^{2}$

Then, as above, this result generalizes to:

$F_{W}(x)=1-\left[1-F(x)\right]^{p}\Rightarrow
f_{W}(x)=pf(x)\left[1-F(x)\right]^{p-1}$ (2)

For the case of uniform random variables, one gets:

$\hbox{for }x\in(0,1):\ f_{W}(x)=p(1-x)^{p-1}$

which means that the probability of death is a decreasing function of age,
consistent with what is expected for infant mortality. The decrease is
ilustrated in Fig.3a for $p=2,4,8,15$.

###  3.5 Special cases

One can gain an intuitive understanding of the theoretical framework by
considering a number of special cases.

Firstly, we can consider the extreme case of an organism with a high number of
components, say one million or if you prefer a number $p$ which tends to
infinity. Then, intuitively, the wear-in assumption gives a probability of
death equal to 1 because for such a large number of components there will
always be one which will fails almost immediately. For the same reason the
wear-out assumption gives a probability of death equal to zero for almost all
ages because it will take a very long time to eliminate all and any
components.

The other extreme case is an organism with only one vital component. Then,
obviously, the two assumptions should give the same result. Indeed, the
formulas (1) and (2) give: $f_{W}(x)=f_{Z}(x)=f(x)$. Here the shape of $f_{W}$
and $f_{Z}$ is completely determined by $f(x)$ which can have any shape,
whether increasing or decreasing.

As the number $p$ of components increases the factor $(1-F)^{p}$, which is a
decreasing function will become more and more predominant. Similarly, for old
age, the factor $F^{p}$, which is an increasing function, will become
predominant when $p$ increases.

In summary, this discussion makes clear that equations (1) and (2) do not
describe only one model but, by playing with $p$ and $f(x)$, they can describe
a whole spectrum of cases. It is in this sense that the model is really
predictive.

###  3.6 Graphs of infancy and old age death rates

The density functions of the variables $W$ and $Z$ give the infant and old age
death rates respectively (Fig.3a,b).

Fig.3a,b Graph of the density functions of the Min and Max of a set of random
variables.which represent the age-specific death rate in young and old age
respectively. When the number of organs becomes large, the death rates become
exponential.

The graphs suggest the conjecture that the larger the number of components,
the steeper the death rates with respect to age. When $p\rightarrow\infty$ it
can be seen directly on the formulas that $f_{W}$ falls vertically from
$pf(0)$ to zero, whereas $f_{Z}$ jumps vertically from zero to $pf(1)$.

As technical systems have often many well-defined, separate components it
should be possible to test our conjecture. For instance microprocessors
comprising a large number of chips should have steeper death rate curves than
those with only a small number.of chips. Unfortunately, for such technical
systems there are almost no life-time data publicly available, probably for
reasons of commercial confidentiality.

##  4 Conclusions

We have proposed two paradigms of death: (i) single-organ death which occurs
through the failure (e.g. due to congenital malformation) of one crucial
organ, (ii) multi-organ death which comes about through the deterioration of
almost all organs.

At this point a distinction should be made between the underlying cause of
death (e.g. cancer or an infectious disease) and the immediate cause of death.
It is the former which is of interest and is reported in the death statistics
by cause of death. On the contrary, the immediate cause of death is almost
always the same, namely a heart failure. For instance, a liver cancer will
lead to blood poisening which makes the heart unable to perform its function
properly. It is because other organs (e.g. the kidneys) are also in poor shape
that the partial defect of the liver eventually proves fatal. It is in this
sense that death occurs as as a kind of overall collapse.

The model predicts that the slope of the death rate is higher (whether for
fall or increase) when the number of organs is larger. Can this conjecture be
tested on biological systems? The answer is “yes” and “no”. “Yes”, because a
comparison of various species shows that there are indeed great differences in
the number of organs. For instance, rotifers (a small swimming animal about
200 micrometers in length) have no heart, no blood, no lungs, no kidneys. In
short, they have much less organs than fish. “No” because there is a serious
obstacle, namely the great difference in lifetimes. Whereas rotifers live
about 5 days, zebrafish live about 5 years. Unless one knows how to normalize
the respective times there can be no meaningfull comparison for, needless to
say, age normalization affects the measurement of the slope.

##  Appendix A Appendix A. Statistical versus probabilistic descriptions of
the death process

In this appendix we discuss some particular aspects of the theoretical
framework. The first subsection clarifies the connection between age and
time.in aging processes. The second subsection establishes the important
connection between the density function of the ages of death and its frequency
counterpart commonly refered to as the death rate.

###  A.1 Age versus time

Should we use age (noted $x$) or time (noted $t$)? At first sight, the
question may seem irrelevant for if time is counted from the moment of birth
the two variables are identical. It is not so simple however, as shown by the
fact that in our min-max argument we had to introduce as many age of death
variables $X_{1},X_{2},\ldots$ as there are vital organs. Moreover, for any
organ, its real age is the time elapsed since it was created. For instance, in
zebrafish the heart appears and starts to beat some 20 hours after
fertilization. Most vital organs are created during embryogenesis which means
that their age is not identical with time (measured after birth which for fish
means hatching of the eggs). That is why $X$ was a more appropriate.variable
than time.

However, in this appendix our perspective is different for we wish to consider
the evolution of a whole population or more precisely of a cohort of
individuals born at the same moment. Taking this moment as origin of the time
axis makes the age of each individual numerically identical with the time
given by an external clock.

Actually, to describe the evolution of a cohort, time seems a better variable
than its age. Why? Although the population exists at any time, for external
observers, it becomes real only when we can know its size and that occurs only
when a census (or a survey) takes place. Censuses are conducted at specific
time intervals (e.g. in the US every decade) and concern simultaneously all
cohorts. That is why in this part calendar time seems to be the natural
variable. Age will play a role only if we wish to consider different age
groups.

###  A.2 Death rate versus probability density

As always, the tricky point is the relationship between the probabilistic
notions and their statistical counterpart. The goal of this appendix is to
recall the main notions and how they are related.

Let $t$ denote the age of individuals in a cohort Let $y(t)$ denote the size
of the cohort at time $t$ We wish to describe the decrease of the population
in the course of time.

The probability that an individual would die in the time interval
$(t_{1},t_{2})$ (which is also an age interval) is:

$\hbox{(Number of those who die)}/\hbox{(number of those alive
initially)}=[y(t_{1})-y(t_{2})]/y(t_{1})$

to get the probability of dying per unit of time we must divide by the length
of the time interval $\Delta t=t_{2}-t_{1}$.

$\mu(t)=(1/\Delta t)\ \left[\left(y(t_{1})-y(t_{2})\right)/y(t)\right]$

Note that $\mu(t)$ represents what is usually called the death rate, sometimes
also called the hazard rate or the force of death. Note also that:
$y(t_{1})-y(t_{2})=-\Delta y$.

Now, let us consider the case of a constant probability of dying. One is led
to: $(1/y)(dy/dt)=-a$ which gives: $y(t)=y_{0}\exp(-at)$. In other words, the
survival function is a decreasing exponential.

Now let us consider a random variable $T$ which represents the age of death of
an individual. Its density function, defined by: $f(t)dt=P\\{t<T<t+dt\\}$, is
the derivative of the distribution function: $F(t)=P\\{T\leq t\\}$. $f(t)dt$
is the probability that the death of the individual occurs in the age interval
$(t,t+dt)$ ; $f(t)$ is the probability per unit of time.

Note that: $f(t)\sim\mu(t)$. In words, $\mu(t)$ is the statistical counterpart
of the probability density function of $T$.

If we consider again the case of a constant probability of dying (for ages in
a bounded interval and zero elsewhere), it means: $f(t)=\mu(t)=a$. Then, the
distribution function is: $F(t)=at$, at least until $at$ is equal to 1. The
decreasing distribution function is:

$G(t)=P\\{T>t\\}=1-F(t)=1-at$

Note that $G(t)$ is different from the survival function.

Ethical statement

1 The authors did not receive any funding.

2 The authors do not have any conflict of interest.

3 The study is purely theoretical and does not involve any experiment with
animals that would require ethical approval.

4 The study does not involve any participants that would have to give their
informed consent.

References

1\. Berrut,S., Pouillard,V., Richmond,P.,Roehner,B.M.: Deciphering infant
mortality. Physica A 463, 400-426 (2016).

2\. Bois,A., Garcia-Roger,E.M., Hong,E., Hutzler,S., Irannezhad,A.,
Mannioui,A., Richmond,P., Roehner,B.M., Tronche,S.: Infant mortality across
species. A global probe of congenital abnormalities. Physica A 535,
122308,1-33 (2019).

3\. Gompertz,B.: On the nature of the function expressive of the law of human
mortality, and on the mode of determining the value of life contengencies.
Philosophical Transactions of the Royal Society 115,5,513-585 (1825).

4\. Gavrilov,L.A., Gavrilova,N.S.: The reliability theory of aging and
longevity. Journal of Theoretical Biology 213,527-545 (2001).

5\. Gavrilov,L.A., Gavrilova,N.S.: Reliability theory of aging and longevity.
Chapter 1 (p.3-42) of: Masoro,E.J., Austad,S.N. editors: Handbook in the
biology of aging. Elsevier Academic Press, San Diego (CA) (2006).

6\. Baione,F., Levantesi,S.: Pricing critical illness insurance from
prevalence rates: Gompertz versus Weibull. North American Actuarial Journal,
22,2,270-288 (2018).

7\. Belayet,H.: Maternal empowerment and child malnutrition in Bangladesh.
Applied Economics 52,14,1566-1581 (2020).

8\. Elmahdy,E.E.: A new approach for Weibull modeling for reliability life
data analysis. Applied Mathematics and Computation 250,708-720.

9\. Ricklefs,R.E., Scheuerlein,A.: Biological implications of the Weibull and
Gompertz models of aging. The Journals of Gerontology 57,2,1,B69-B76 (2002).

10\. Chen,Q., Di,Z., Garcia-Roger,E.M., Li,H., Richmond,P., Roehner,B.M.:
Magnitude and significance of the peak of early embryonic mortality. Journal
of Biological Physics 17 August (2020).

11\. Bois,A., Garcia-Roger,E.M., Hong,E., Hutzler,S., Irannezhad,A.,
Mannioui,A., Richmond,P., Roehner,B.M., Tronche,S.: Physical models of infant
mortality: implications for defects in biological systems. Journal of
Biological Physics 46,371-394 (2020).

12\. Richmond,P., Roehner,B.M.: Predictive implications of Gompertz’s law.
Physica A 447,446 (2016).


# Incentive-Compatible Selection for One or Two Influentials

Yuxin Zhao  Yao Zhang&Dengji Zhao ShanghaiTech University {zhaoyx5, zhangyao1,
<EMAIL_ADDRESS>
###### Abstract

Selecting influentials in networks against strategic manipulations has
attracted many researchers’ attention and it also has many practical
applications. Here, we aim to select one or two influentials in terms of
progeny (the influential power) and prevent agents from manipulating their
edges (incentive compatibility). The existing studies mostly focused on
selecting a single influential for this setting. Zhang et al. Zhang et al.
(2021) studied the problem of selecting one agent and proved an upper bound of
$1/(1+\ln 2)$ to approximate the optimal selection. In this paper, we first
design a mechanism to actually reach the bound. Then, we move this forward to
choosing two agents and propose a mechanism to achieve an approximation ratio
of $(3+\ln 2)/(4(1+\ln 2))$ ($\approx 0.54$).

##  1 Introduction

Consider the scenario where we want to select influential agents in a network
constructed by referral relationships (e.g., the following relationships in
Twitter, the citations between academic papers, etc.). The selected agents may
be rewarded with prizes or benefits (e.g., job opportunities Kotturi et al.
(2020)). Hence, agents have the incentive to manipulate their relationships to
make themselves selected. Therefore, selection mechanisms that can prevent
agents from strategic manipulations (which is referred to as the property of
incentive compatibility) are highly demanded Alon et al. (2011).

Many studies have investigated incentive-compatible selection mechanisms on
different influence measurements for different purposes (see Olckers and Walsh
(2022) for a complete survey). In this paper, we focus on the setting where an
agent’s influential power is measured by her progeny (the number of all agents
who directly or indirectly follow her). For this setting, two studies have
been conducted before. Babichenko et al. Babichenko et al. (2020b) proposed
the first single agent selection mechanism for progeny maximization that can
prevent agents from adding or hiding their out-edges. Their mechanism reaches
an approximation ratio of about $1/3$ (i.e., the expected progeny of the
chosen agent is about $1/3$ of the largest). However, their mechanism only
works in forests. Therefore, Zhang et al. Zhang et al. (2021) further studied
the same problem in directed acyclic graphs (DAGs) with restricting
manipulations in the scope of hiding edges (agents cannot add new edges).
Their proposed mechanism achieves an approximation ratio of $1/2$. Moreover,
they proved an upper bound $1/(1+\ln 2)$ of the approximation ratio for any
incentive-compatible and fair selection mechanism in the DAG setting.

In this paper, we follow the DAG setting of Zhang et al. (2021) and make the
following contributions:

  * •

For selecting one agent, we close the gap between the known approximation
ratio of $1/2$ and the upper bound of $1/(1+\ln 2)$. We propose a mechanism to
achieve the exact upper bound.

  * •

For selecting two agents, we show that, for the class of mechanisms that only
select agents from the $1$-influential set111$1$-influential set contains all
agents each of whom has the largest progeny by hiding her out-edges. (most of
the existing mechanisms belong to this class), the approximation ratio cannot
exceed $1/2$ if the target is to select at most two agents. Moreover, we
provide a deterministic mechanism in this class that exactly reaches the
approximation ratio of $1/2$.

  * •

We then propose a new incentive-compatible mechanism based on a
$2$-influential set for selecting two agents. The new mechanism achieves a
higher approximation ratio of $(3+\ln 2)/(4(1+\ln 2))$ ($\approx 0.54$). We
also provide a general upper bound ($23/27$) of any incentive-compatible
mechanism for selecting two agents.

###  1.1 Other Related Work

Many studies on incentive-compatible selection mechanisms use in-degrees to
measure agents’ influential power, which is also referred to as peer
selection. For the in-degree measurement, Alon et al. Alon et al. (2011)
firstly proposed an incentive-compatible peer selection mechanism by a
randomized partition method, which divides agents into two groups and chooses
the agents according to their in-degrees from the other group. Following this
work, there are two major directions. One is to characterize incentive-
compatible peer selection mechanisms with axioms, which is initiated by
Holzman and Moulin Holzman and Moulin (2013). Mackenzie Mackenzie (2015)
continued this study by adding symmetric axiomizations. The other direction is
to improve the approximation ratios of the existing incentive-compatible peer
selection mechanisms. Fischer and Klimm Fischer and Klimm (2014) extended the
idea of the partition mechanism to a permutation mechanism, which achieves the
optimal approximation ratio ($1/2$) for selecting one agent with in-degree.
Then, Bousquet et al. Bousquet et al. (2014) characterized a class of networks
where the permutation mechanism selects an agent close to the optimal. Bjelde
et al. Bjelde et al. (2017) generalized the permutation mechanism for
selecting multiple agents, and gave both lower and upper bounds of the
approximation ratio. Recent studies also started to consider an alternative
evaluation called additive approximation, which focuses on the expected
difference from the optimal rather than the worst-case ratio Caragiannis et
al. (2021, 2022); Cembrano et al. (2022). There are also extensions on the
networks, including a weighted network, where the influential power is a
weighted in-degree Kurokawa et al. (2015); Wang et al. (2018); Babichenko et
al. (2020a), and rank aggregation, where each agent assigns a rank to others
Kahng et al. (2018); Mattei et al. (2020).

There is also a rich body of work focusing on different measurements of
influential power. Ghalme et al. Ghalme et al. (2018) designed a naturally
strategy-proof score function to measure the popularity of agents, thereby
simplifying the selection. In contrast, Babichenko et al. Babichenko et al.
(2018) targeted a PageRank-like centrality Page et al. (1999) and offered a
two-path mechanism which achieves a good approximation ratio of $2/3$.
Moreover, Babichenko et al. Babichenko et al. (2020b) focused on the progeny
of the selected agent and proposed a mechanism with an approximation ratio of
$1/(4\ln 2)$ in forests. Zhang et al. Zhang et al. (2021) then proposed a
geometric mechanism with an approximation ratio of $1/2$ in DAGs, which is
what we follow here.

##  2 Preliminaries

Let $\mathcal{G}_{n}$ be the set of all directed acyclic graphs (DAGs) with
$n$ nodes and $\mathcal{G}=\bigcup_{n\in\mathbb{N}^{+}}\mathcal{G}_{n}$ be the
set of all DAGs. Consider a network represented by a graph
$G=(N,E)\in\mathcal{G}$, where $N=\\{1,2,\dots,n\\}$ is the node set and $E$
is the edge set. Each node $i\in N$ represents an agent, and each edge
$(i,j)\in E$ represents that agent $i$ follows (votes for, or quotes) agent
$j$. Let $E_{i}=\\{(i,j)\mid(i,j)\in E,j\in N\\}$ be the set of all edges from
$i$. We say an agent $j$ is influenced by the agent $i$ if there exists a path
from $j$ to $i$ in $G$. Let $P(i,G)$222or simply $P(i)$ if no ambiguity.
Additionally, for the sake of tidiness, the notation of the set also indicates
its size if no ambiguity. be the set of agents who are influenced by agent $i$
(including $i$ herself), which is referred to as the progeny of agent $i$.

Our goal is to select a group of agents in the network as delegates with
larger progeny. Let $\mathcal{S}_{k}=\\{S\mid S\subseteq N,|S|=k\\}$ be the
set of all subsets with $k$ agents, and $\mathcal{S}_{\leq
k}=\bigcup_{t=0}^{k}\mathcal{S}_{t}$. A _$k$ -selection mechanism_ decides how
to choose up to $k$ agents as delegates.

######  Definition 1.

A $k$-selection mechanism for $\mathcal{G}$ is a family of functions
$f:\mathcal{G}_{n}\rightarrow[0,1]^{\mathcal{S}_{\leq k}}$ for all
$n\in\mathbb{N}^{+}$, that maps each graph to a probability distribution on
all subsets with no more than $k$ agents.

For a given graph $G\in\mathcal{G}$ and a $k$-selection mechanism $f$, denote
$x_{S}(G)=(f(G))_{S}$ as the probability of the subset $S\in\mathcal{S}_{\leq
k}$ being selected, and $x_{i}(G)=\sum_{S\in\mathcal{S}_{\leq k}\text{ and
}i\in S}x_{S}(G)$ as the probability of the agent $i$ being selected.

For an agent $i\in N$, she wants her probability to be selected ($x_{i}$) as
large as possible, while for the owner of the mechanism, we want the
influential power of the selected group (the sum of the progeny) as large as
possible. Unfortunately, if we simply choose an optimal subset with $k$
agents, i.e., $S^{*}_{k}\in\arg\max_{S\in\mathcal{S}_{k}}\sum_{i\in
S}|P(i,G)|$, then agents will have incentives to hide their edges to increase
their ranks to be selected. We want to avoid such a manipulation, which
requires the mechanism to be _incentive-compatible_.

######  Definition 2.

A $k$-selection mechanism for $\mathcal{G}$ is incentive-compatible (IC) if
for every $n\in\mathbb{N}^{+}$, and every two graphs $G=(N,E)$,
$G^{\prime}=(N,E^{\prime})\in\mathcal{G}_{n}$, such that $E\setminus
E_{i}=E^{\prime}\setminus E^{\prime}_{i}$ and $E_{i}\supseteq E_{i}^{\prime}$
for $i\in N$, we have $x_{i}(G)\geq x_{i}(G^{\prime})$.

Intuitively, incentive compatibility implies that no matter how other agents
follow each other, it is an undominated strategy for any agent not to hide her
out-edges. Since an incentive-compatible $k$-selection mechanism cannot always
choose a group with the highest influential power, we seek the approximation
of the optimum, which guarantees a worst-case ratio between the expected
progeny of the selected group and an optimal group for all DAGs.

######  Definition 3.

An incentive-compatible $k$-selection mechanism is $\alpha$-optimal if

$\inf_{G\in\mathcal{G}}\frac{\mathbb{E}_{S\sim x_{S}(G)}[\sum_{i\in
S}P(i,G)]}{\sum_{i\in S_{k}^{*}}P(i,G)}\geq\alpha.$

For convenience, we can characterize an optimal group by defining a strict
order of agents as follows.

######  Definition 4.

For a graph $G=(N,E)\in\mathcal{G}$, and agents $i$, $j\in N$, $i\neq j$, we
say $i\succ j$ if either $P(i,G)>P(j,G)$ or $P(i,G)=P(j,G)$ with $i>j$.

Let $i_{t}^{*}$ be the agent with rank $t$ such that $|\\{j\mid j\succ
i_{t}^{*}\\}|=t-1$, which must be unique since the order is strict. Then, we
can order all the agents as the _ranking sequence_ $i_{1}^{*}\succ
i_{2}^{*}\succ\dots\succ i_{n}^{*}$. Apparently,
$\\{i_{1}^{*},\cdots,i_{k}^{*}\\}$ is an optimal set for selecting $k$ agents.
Hence, for our strategic setting, we will pay attention to agents who can
pretend to be the first $k$ agents in the ranking sequence by hiding their
out-edges.

######  Definition 5.

For a graph $G=(N,E)$, an agent $i$ belongs to the $k$-influential set
$S^{\mathsf{inf.}}_{k}(G)$ if $|\\{j\mid j\succ i\\}|<k$ holds in the graph
$G^{\prime}=(N,E\setminus E_{i})$.

In this paper, we mainly focus on the cases for $k\in\\{1,2\\}$. Hence, we use
some observations about $S^{\mathsf{inf.}}_{1}(G)$ and
$S^{\mathsf{inf.}}_{2}(G)$. To make it easy to follow, we present the
observations about $S^{\mathsf{inf.}}_{1}(G)$ below as preparation and present
the observations of $S^{\mathsf{inf.}}_{2}(G)$ in Section 4.2.

######  Observation 1 (Zhang et al. (2021)).

For any graph $G$, the set $S^{\mathsf{inf.}}_{1}(G)$ can be written as
$\\{i_{1},i_{2},\cdots,i_{m}\\}$, where $m\geq 1$, $i_{1}=i_{1}^{*}$, and
$i_{t+1}\in P(i_{t})\setminus\\{i_{t}\\}$ for all $t<m$.

Intuitively, the agent $i_{1}^{*}$ who ranks the first is naturally in the
1-influential set. Furthermore, if there are more than one agent in the set,
the agent who has a lower rank must be in the progeny of those who have higher
ranks; otherwise, she will still have a lower rank when deleting her out-
edges. Hence, in other words, we can find a path in $G$ that passes through
all agents in the set with the order of their ranks.

######  Observation 2 (Zhang et al. (2021)).

For any graph $G$, if the set
$S^{\mathsf{inf.}}_{1}(G)=\\{i_{1},i_{2},\cdots,i_{m}\\}$ has more than one
agent, i.e., $m>1$, then for any $1<t\leq m$, $2P(i_{t})\geq P(i_{1})$.

Inferred from Observation 1, if there is another agent except for $i_{1}^{*}$
is in the 1-influential set, she should hold at least half of $i_{1}^{*}$’s
progeny to make herself rank the first after removing her out-edges.

##  3 Select One Agent

In this section, we present our result for only selecting $k=1$ agent. Not
only does it help us understand the proposed methods in the following section
for $k=2$, but also fills the gap between the existing mechanisms and the
upper bound of approximation ratios for IC 1-selection mechanisms, which is
$1/(1+\ln 2)$ confirmed by Zhang et al. Zhang et al. (2021).

Formally, our method can be viewed as a general variant of the modified
Babichenko’s mechanism Babichenko et al. (2020b).

$\beta$-logarithmic Mechanism ($\beta$-LM)

  1. 1.

Given a network $G=(N,E)$, find the 1-influential set
$S^{\mathsf{inf.}}_{1}(G)=\\{i_{1},\dots,i_{m}\\}$, where $i_{t}\succ i_{t+1}$
for all $1\leq t<m$.

  2. 2.

Assign the probability of each agent to be selected as follows:

$\displaystyle x_{j}=\begin{cases}\beta,&j=i_{m}\\\
(1-\beta)\log_{2}\frac{P(i_{t})}{P(i_{t+1})},&j=i_{t},t\neq m\\\ 0,&j\notin
S^{\mathsf{inf.}}_{1}(G).\end{cases}$

The total probability of selecting one agent in $\beta$-LM is at most
$\beta+(1-\beta)\log_{2}(P(i_{1})/P(i_{m}))\leq 1$ by the fact in Observation
2. Hence, the probabilities assigned by the mechanism are valid as long as
$0\leq\beta\leq 1$. Then, we show the mechanism is IC when $\beta\geq 1/2$.

######  Theorem 1.

A $\beta$-logarithmic mechanism is IC if $\beta\geq 1/2$.

###### Proof.

For any graph $G\in\mathcal{G}$, let
$S^{\mathsf{inf.}}_{1}(G)=\\{i_{1},\dots,i_{m}\\}$. Then, we consider three
different types of agents.

  1. 1.

For an agent $i\notin S^{\mathsf{inf.}}_{1}(G)$, by definition, she can never
pretend to be the agent with rank 1 by hiding her out-edges. Hence, she will
always not belong to the 1-influential set and will have 0 probability to be
chosen.

  2. 2.

For an agent $i_{t}\in S^{\mathsf{inf.}}_{1}(G)$ such that $t<m$, no matter
how she hides her out-edges, $i_{t+1}$ will always belong to the 1-influential
set because $i_{t+1}\in P(i_{t})$ (Observation 1) and her progeny cannot be
decreased. Hence, the probability of $i_{t}$ to be chosen will not change.

  3. 3.

For the agent $i_{m}\in S^{\mathsf{inf.}}_{1}(G)$, if she hides some of her
out-edges, there may happen two cases. (i) If there is no agent in $P(i_{m})$
occurs in the new 1-influential set, the probability of $i_{m}$ to be chosen
will remain $\beta$. (ii) If there exists at least one agent in $P(i_{m})$
that occurs in the new 1-influential set, let $i_{1}^{\prime}$ be the first
agent in the new set. Let $i_{m+1}$ be the one with the highest rank after
$i_{m}$ in the new set. Then, the probability of $i_{m}$ to be chosen will
become
$(1-\beta)\log_{2}(P(i_{m})/P(i_{m+1}))\leq(1-\beta)\log_{2}(P(i_{1}^{\prime})/P(i_{m+1}))\leq(1-\beta)\leq\beta$
by the fact of $\beta\geq 1/2$ and Observation 2.

Taking all the above together, no agent can increase her probability to be
chosen by hiding her out-edges. ∎

Now we can compute the approximation ratios of IC $\beta$-LMs, from which we
can find that the optimal $\beta$-LM is also an optimal IC selection mechanism
for $k=1$.

######  Theorem 2.

An IC $\beta$-logarithmic mechanism ($1/2\leq\beta\leq 1$) is
$\left(\min\left\\{\frac{1}{2}\left(\beta+\frac{1-\beta}{\ln
2}\right),\beta\right\\}\right)$-optimal.

###### Proof.

For any graph $G\in\mathcal{G}$, let
$S^{\mathsf{inf.}}_{1}(G)=\\{i_{1},\dots,i_{m}\\}$. If $m=1$, then we have

$\mathbb{E}_{i\sim
x_{i}}[P(i)]/P(i_{1}^{*})=x_{i_{1}}P(i_{1})/P(i_{1})=\beta.$

If $m>1$, then we have

$\displaystyle\mathbb{E}_{i\sim x_{i}}[P(i)]/P(i_{1}^{*})$ $\displaystyle=$
$\displaystyle\
\frac{1-\beta}{P(i_{1}^{*})}\sum_{t=1}^{m-1}P(i_{t})\log_{2}\frac{P(i_{t})}{P(i_{t+1})}+\beta\frac{P(i_{m})}{P(i_{1}^{*})}$
$\displaystyle=$ $\displaystyle\ \frac{1-\beta}{\ln{2}\cdot
P(i_{1}^{*})}\sum_{t=1}^{m-1}P(i_{t})\int_{P(i_{t+1})}^{P(i_{t})}\frac{\mathrm{d}z}{z}+\beta\frac{P(i_{m})}{P(i_{1}^{*})}$
$\displaystyle\geq$ $\displaystyle\ \frac{1-\beta}{\ln{2}\cdot
P(i_{1}^{*})}\sum_{t=1}^{m-1}\int_{P(i_{t+1})}^{P(i_{t})}\mathrm{d}z+\beta\frac{P(i_{m})}{P(i_{1}^{*})}$
$\displaystyle=$ $\displaystyle\ \frac{1-\beta}{\ln{2}\cdot
P(i_{1})}\sum_{t=1}^{m-1}(P(i_{t})-P(i_{t+1}))+\beta\frac{P(i_{m})}{P(i_{1})}$
$\displaystyle=$ $\displaystyle\ \frac{1-\beta}{\ln
2}+\left(\beta-\frac{1-\beta}{\ln 2}\right)\frac{P(i_{m})}{P(i_{1})}$
$\displaystyle\geq$ $\displaystyle\ \frac{1}{2}\left(\beta+\frac{1-\beta}{\ln
2}\right).$

Therefore, the mechanism is
$\left(\min\left\\{\frac{1}{2}\left(\beta+\frac{1-\beta}{\ln
2}\right),\beta\right\\}\right)$-optimal. ∎

It is not hard to find out that when $\beta=1/(1+\ln 2)$, the value
$\min\left\\{\frac{1}{2}\left(\beta+\frac{1-\beta}{\ln
2}\right),\beta\right\\}$ takes it maximum as $1/(1+\ln 2)$, i.e., the optimal
$\beta$-LM is $(1/(1+\ln 2))$-LM, which is $(1/(1+\ln 2))$-optimal. Recall
that Zhang et al. Zhang et al. (2021) has proved that no IC and
fair333Fairness is a quite weak property for single agent selection that only
requires $i_{1}^{*}$ has the same probability to be chosen if the
1-influential set and the structure formed by $P(i_{1}^{*})$ remain the same.
It is clear to see that $\beta$-LM satisfies this fairness. selection
mechanism can be $\alpha$-optimal with $\alpha>1/(1+\ln 2)$. Hence, we can
infer the optimality of $(1/(1+\ln 2))$-LM.

######  Corollary 1.

There is no other IC and fair selection mechanism for $k=1$ that can have a
higher approximation ratio than $(1/(1+\ln 2))$-LM.

At the end of this section, we give a running example of $(1/(1+\ln 2))$-LM.

######  Example 1.

Consider the network depicted in Figure 1, where
$S^{\mathsf{inf.}}_{1}(G)=\\{i_{1},i_{2},i_{3},i_{4}\\}$. For the last agent
$i_{4}$ in the set, her selection probability $x_{i_{4}}$ is $1/(1+\ln
2)\approx 0.59$. For the agents $i_{3}$, $i_{2}$ and $i_{1}$, their selection
probabilities are

$\displaystyle x_{i_{3}}$ $\displaystyle=\frac{\ln 2}{1+\ln
2}\log_{2}\frac{P(i_{3})}{P(i_{4})}=\frac{\ln 2}{1+\ln
2}\log_{2}\frac{5}{4}\approx 0.13;$ $\displaystyle x_{i_{2}}$
$\displaystyle=\frac{\ln 2}{1+\ln
2}\log_{2}\frac{P(i_{2})}{P(i_{3})}=\frac{\ln 2}{1+\ln
2}\log_{2}\frac{6}{5}\approx 0.11;$ $\displaystyle x_{i_{1}}$
$\displaystyle=\frac{\ln 2}{1+\ln
2}\log_{2}\frac{P(i_{1})}{P(i_{2})}=\frac{\ln 2}{1+\ln
2}\log_{2}\frac{7}{6}\approx 0.09.$

Figure 1: An example of the network, where the marked agents have the
relationship as $i_{1}\succ i_{2}\succ i_{3}\succ i_{4}\succ j$. The
1-influential set is represented by a dashed border.

##  4 Select Two Agents

We start to consider selecting up to $k=2$ agents as delegates. To select
agents with larger progeny, one possible approach is to find the second
delegate from the 1-influential set as well. However, this limits the
performance of IC mechanisms.

###  4.1 Limitation of the 1-influential Set

The limitation of selecting agents from the 1-influential set for $k=2$ mainly
comes from the fact that there may be only a single agent in the set.

######  Theorem 3.

If an IC 2-selection mechanism only selects agents in the 1-influential set,
then it cannot be $\alpha$-optimal with $\alpha>1/2$.

###### Proof.

Consider a two-star graph shown in Figure 2. Suppose $P(i_{1})=P(j)=y$ and
$i_{1}>j$. Then the 1-influential set of this graph $S^{\mathsf{inf.}}_{1}(G)$
only contains $i_{1}$. Therefore, even if the mechanism can always select
agent $i_{1}$ with probability $1$, the approximation ratio in this graph is
only $(1\cdot y)/(y+y)=1/2$. Hence, if only selecting agents in the
1-influential set, an IC 2-selection mechanism cannot achieve an approximation
ratio of more than $1/2$. ∎

Figure 2: A two-star network where the hubs satisfy $i_{1}\succ j$. Thus, the
1-influential set only contains $i_{1}$.

We can also show that the limitation described in Theorem 3 is tight by
providing the following mechanism.

Least Deterministic Mechanism (LDM)

  1. 1.

Given a network $G=(N,E)$, find the 1-influential set
$S^{\mathsf{inf.}}_{1}(G)=\\{i_{1},\dots,i_{m}\\}$, where $i_{t}\succ i_{t+1}$
for all $1\leq t<m$.

  2. 2.

Assign the probability of each agent to be selected as follows:

$\displaystyle x_{j}=\begin{cases}1,&j=i_{m},\text{or }j=i_{m-1}\\\
0,&j=i_{t},t<m-1,\text{or }j\notin S^{\mathsf{inf.}}_{1}(G).\\\ \end{cases}$

Intuitively, LDM deterministically selects the last two agents in the
1-influential set or it selects the only agent in the set if
$|S^{\mathsf{inf.}}_{1}(G)|=1$.

######  Example 2.

We take the networks shown in Figure 1 and Figure 2 as running examples. In
Figure 1, there are four agents, $i_{1}$, $i_{2}$, $i_{3}$, and $i_{4}$, in
the 1-influential set. Hence, LDM deterministically selects the last two
agents $i_{4}$ and $i_{3}$, i.e., $x_{i_{4}}=x_{i_{3}}=1$. In Figure 2, there
is a single agent $i_{1}$ in the 1-influential set. Hence, LDM
deterministically selects the agent $i_{1}$ only.

Now we prove that LDM is incentive-compatible and $1/2$-optimal as follows.

######  Theorem 4.

LDM is an IC 2-selection mechanism.

###### Proof.

For any graph $G\in\mathcal{G}$, suppose that
$S^{\mathsf{inf.}}_{1}(G)=\\{i_{1},\dots,i_{m}\\}$. Then we consider the
following cases.

  1. 1.

For an agent $i\notin S^{\mathsf{inf.}}_{1}(G)$, same as the first point in
the proof of Theorem 1, she always has no chance to be chosen by hiding her
out-edges.

  2. 2.

If $m\leq 2$, the agents in $S^{\mathsf{inf.}}_{1}(G)$ will be
deterministically selected. Hence, they have no incentive to hide their out-
edges.

  3. 3.

If $m>2$, first, for agents $i_{m}$ and $i_{m-1}$ who will be
deterministically selected, they have no incentive to hide their out-edges.
Then, for any agent $i_{t}\in S^{\mathsf{inf.}}_{1}(G)$ with $i<m-1$, no
matter how she hides her out-edges, $i_{m}$ and $i_{m-1}$ will always belong
to the 1-influential set because $\\{i_{m},i_{m-1}\\}\subseteq P(i_{t})$
(Observation 1) and their progeny cannot be decreased. Hence, the probability
of $i_{t}$ to be chosen will remain to be 0.

Taking all the above together, no agent can increase her probability to be
chosen by hiding her out-edges. Therefore, the mechanism is IC. ∎

######  Theorem 5.

LDM is $1/2$-optimal.

###### Proof.

For any graph $G\in\mathcal{G}$, if $|S^{\mathsf{inf.}}_{1}(G)|=1$, then LDM
deterministically selects the agent $i_{1}^{*}$. Therefore, in this case, we
have

$\frac{\mathbb{E}_{S}[\sum_{i\in S}P(i)]}{\sum_{i\in
S_{2}^{*}}P(i)}=\frac{P(i_{1}^{*})}{P(i_{1}^{*})+P(i_{2}^{*})}\geq\frac{P(i_{1}^{*})}{P(i_{1}^{*})+P(i_{1}^{*})}=\frac{1}{2}.$

If $|S^{\mathsf{inf.}}_{1}(G)|\geq 2$, then LDM deterministically selects the
agent $i_{m}$ and $i_{m-1}$. By Observation 2, in this case, we have

$\displaystyle\frac{\mathbb{E}_{S}[\sum_{i\in S}P(i)]}{\sum_{i\in
S_{2}^{*}}P(i)}$
$\displaystyle=\frac{P(i_{m})+P(i_{m-1})}{P(i_{1}^{*})+P(i_{2}^{*})}$
$\displaystyle\geq\frac{P(i_{m})+P(i_{m-1})}{2P(i_{1})}$
$\displaystyle=\frac{1}{2}\left(\frac{P(i_{m})}{P(i_{1})}+\frac{P(i_{m-1})}{P(i_{1})}\right)$
$\displaystyle\geq\frac{1}{2}\left(\frac{1}{2}+\frac{1}{2}\right)=\frac{1}{2}.$

Therefore, LDM is $1/2$-optimal. ∎

If we consider general IC 2-selection mechanisms, we may have a higher upper
bound of the approximate ratio. This suggests the limitation of only selecting
agents from the 1-influential set when we target up to two delegates.

######  Theorem 6.

There is no IC 2-selection mechanism that can be $\alpha$-optimal with
$\alpha>23/27$.

###### Proof.

Consider three networks with four agents shown in Figure 3. Applying a generic
IC 2-selection mechanism on these graphs, suppose the probabilities of each
agent $i$ being chosen in the three graphs are $x_{i}^{(a)}$, $x_{i}^{(b)}$
and $x_{i}^{(c)}$. Notice that network (b) can be obtained by agent 2 or 4 in
network (a) hiding their out-edges (corresponding to agent 2 or 1 in network
(b)), while network (c) can be obtained by agent 3 hiding her out-edge
(corresponding to agent 1 or 3 in network (c)). Since the selection mechanism
is IC, we have the following constraints:

$\displaystyle x_{2}^{(b)}\leq x_{2}^{(a)},\quad$ $\displaystyle
x_{1}^{(b)}\leq x_{4}^{(a)};$ (1) $\displaystyle x_{3}^{(c)}\leq
x_{3}^{(a)},\quad$ $\displaystyle x_{1}^{(c)}\leq x_{3}^{(a)}.$ (2)

Moreover, the mechanism selects at most 2 agents. Hence,

$\displaystyle\sum_{i=1}^{4}x_{i}^{(a)}\leq
2,\quad\sum_{i=1}^{4}x_{i}^{(b)}\leq 2,\quad\sum_{i=1}^{4}x_{i}^{(c)}\leq 2.$
(3)

The approximation ratio of the mechanism must be no more than the least ratio
in these three graphs, i.e.,

$\begin{split}\alpha\leq\min&\left\\{\frac{4x_{1}^{(a)}+3x_{2}^{(a)}+2x_{3}^{(a)}+x_{4}^{(a)}}{7},\right.\\\
&\quad\frac{x_{1}^{(b)}+3x_{2}^{(b)}+2x_{3}^{(b)}+x_{4}^{(b)}}{5},\\\
&\quad\left.\frac{2x_{1}^{(c)}+x_{2}^{(c)}+2x_{3}^{(c)}+x_{4}^{(c)}}{4}\right\\}\end{split}$

With constraints (1) - (3), we can calculate the highest value of the minimum.
Therefore, we have $\alpha\leq 23/27$ and the equations holds when

$\displaystyle
x_{1}^{(a)}=2/3,x_{2}^{(a)}=17/27,x_{3}^{(a)}=19/27,x_{4}^{(a)}=0;$
$\displaystyle
x_{1}^{(b)}=0,x_{2}^{(b)}=17/27,x_{3}^{(b)}=1,x_{4}^{(b)}=10/27;$
$\displaystyle
x_{1}^{(c)}=19/27,x_{2}^{(c)}=16/27,x_{3}^{(c)}=19/27,x_{4}^{(c)}=0.$

∎

Figure 3: Three networks with four agents where (b) and (c) can be obtained by
one of the agents in (a) hiding her out-edge. The probabilities of each agent
being chosen by a generic IC 2-selection mechanism are attached beside the
node.

###  4.2 Utilizing the 2-influential Set

To break through the limitation of the 1-influential set, one natural idea is
to consider the 2-influential set. We first characterize the set by following
observations.

######  Observation 3.

For any graph $G$, $S^{\mathsf{inf.}}_{1}(G)\subseteq
S^{\mathsf{inf.}}_{2}(G)$.

######  Observation 4.

For any graph $G$, $\\{i_{1}^{*},i_{2}^{*}\\}\subseteq
S^{\mathsf{inf.}}_{2}(G)$.

According to Definition 5, agents who can pretend to be the first in the
ranking sequence are definitely in the 2-influential set. The agents
$i_{1}^{*}$ and $i_{2}^{*}$ who rank first and second are also naturally in
the 2-influential set. Based on the relationship between $i_{1}^{*}$ and
$i_{2}^{*}$, the 2-influential set will have different forms.

######  Observation 5.

For any graph $G$, if $i_{2}^{*}\in P(i_{1}^{*})$, the set
$S^{\mathsf{inf.}}_{2}(G)$ can be written as $\\{i_{1},i_{2},\cdots,i_{m}\\}$,
where $i_{1}=i_{1}^{*}$, $i_{2}=i_{2}^{*}$, and $i_{t+1}\in P(i_{t})$ for all
$t<m$.

###### Proof.

When there is another agent $i_{3}$, except for $i_{1}^{*}$ and $i_{2}^{*}$,
is in the 2-influential set, she must have the ability to decrease $i_{1}^{*}$
or $i_{2}^{*}$’s progeny by hiding her out-edges, i.e., at least one of
$i_{3}\in P(i_{1}^{*})$ and $i_{3}\in P(i_{2}^{*})$ is satisfied. If
$i_{2}^{*}\in P(i_{1}^{*})$, we will show $i_{3}$ must belong to
$P(i_{2}^{*})$ by contradiction as follows.

If $i_{3}\notin P(i_{2}^{*})$, then she cannot decrease $i_{2}^{*}$’s progeny
by hiding her out-edges. Since $i_{2}^{*}\notin P(i_{3})$, $i_{2}^{*}\in
P(i_{1}^{*})$ is always satisfied no matter how $i_{3}$ hides her out-edges.
Hence, in order to rank first or second after hiding out-edges, $i_{3}\succ
i_{2}^{*}$ must be satisfied, which contradicts that $i_{2}^{*}$ is with rank
2. Therefore, $i_{3}\in P(i_{2}^{*})$.

Similarly, when there is another agent $i_{4}\prec i_{3}$ in the 2-influential
set, she must belong to $P(i_{3})$, and this pattern extends to subsequent
agents in the 2-influential set. ∎

######  Observation 6.

For any graph $G$, if $i_{2}^{*}\notin P(i_{1}^{*})$, the set
$S^{\mathsf{inf.}}_{2}(G)$ can be written as $\\{i_{1},i_{2},\cdots,i_{m}\\}$,
where $i_{1}=i_{1}^{*}$, $i_{2}=i_{2}^{*}$, and for others, at least one of
the below is true:

  * •

$i_{3}\in P(i_{1})$, $i_{t+1}\in P(i_{t})$ for all $3\leq t<m$;

  * •

$i_{3}\in P(i_{2})$, $i_{t+1}\in P(i_{t})$ for all $3\leq t<m$.

###### Proof.

When there is another agent $i_{3}$, except for $i_{1}^{*}$ and $i_{2}^{*}$,
is in the 2-influential set, at least one of $i_{3}\in P(i_{1}^{*})$ and
$i_{3}\in P(i_{2}^{*})$ is satisfied.

We first assume $i_{3}\in P(i_{1}^{*})$. Then, when there is another agent
$i_{4}\prec i_{3}$ in the 2-influential set, we show that $i_{4}\in P(i_{3})$
by contradiction as follows. If $i_{4}\notin P(i_{3})$, she cannot decrease
$i_{3}$’s progeny by hiding her out-edges. Since $i_{3}\notin P(i_{4})$,
$i_{3}\in P(i_{1}^{*})$ is always satisfied no matter how $i_{4}$ hides her
out-edges. Hence, $i_{4}\succ i_{3}$ must be satisfied to make $i_{4}$ be in
the 2-influential set, which makes a contradiction. Therefore, $i_{4}\in
P(i_{3})$. Similarly, when there is another agent $i_{5}\prec i_{4}$ in the
2-influential set, she must belong to $P(i_{4})$, and this pattern extends to
subsequent agents in the 2-influential set. The same results can also be
obtained similarly if $i_{3}\in P(i_{2}^{*})$. ∎

From the above observations, we can see that the structure of the
2-influential set is much more complex than that of the 1-influential set.
Furthermore, the progeny of the last agent in the 2-influential set might be
much smaller than $P(i_{1}^{*})$ since $P(i_{2}^{*})$ might be small. These
are the main difficulties to utilize the 2-influential set. Extending the idea
of LDM and $\beta$-LM, we propose the following mechanism.

Logarithm After Least Deterministic (LALD)

  1. 1.

Given a network $G=(N,E)$, find the 1-influential set
$S^{\mathsf{inf.}}_{1}(G)$ and the 2-influential set
$S^{\mathsf{inf.}}_{2}(G)$.

  2. 2.

If $S^{\mathsf{inf.}}_{2}(G)\setminus S^{\mathsf{inf.}}_{1}(G)=\emptyset$,
then
$S^{\mathsf{inf.}}_{1}(G)=S^{\mathsf{inf.}}_{2}(G)=\\{i_{1},i_{2}\dots,i_{m}\\}$,
where $i_{t}\succ i_{t+1}$ for all $1\leq t<m$. Then, assign the probability
of each agent to be selected as follows:

$\displaystyle x_{j}=\begin{cases}1,&j=i_{m}\\\ \frac{1}{1+\ln
2},&j=i_{m-1}\\\ \frac{\ln 2}{1+\ln
2}\log_{2}\frac{P(i_{t})}{P(i_{t+1})},&j=i_{t},t<m-1\\\ 0,&j\notin
S^{\mathsf{inf.}}_{2}(G).\end{cases}$

  3. 3.

If $S^{\mathsf{inf.}}_{2}(G)\setminus S^{\mathsf{inf.}}_{1}(G)\neq\emptyset$,
suppose $S^{\mathsf{inf.}}_{2}(G)=\\{i_{1},\dots,i_{m}\\}$ where $i_{t}\succ
i_{t+1}$ for all $1\leq t<m$. First, deterministically select the agent
$i_{m}$, i.e., $x_{i_{m}}=1$. Then, select the second agent by applying
$(1/(1+\ln 2))$-LM on $G$.

Intuitively, LALD first deterministically selects the last agent in the
2-influential set. Then, it uses the same probability distribution as
$(1/(1+\ln 2))$-LM to select another agent among the remaining agents in the
1-influential set.

######  Example 3.

We take the networks shown in Figure 1 and Figure 4 as running examples.

In Figure 1, suppose $j<i_{2}$. Then,
$S^{\mathsf{inf.}}_{2}(G)=S^{\mathsf{inf.}}_{1}(G)=\\{i_{1},i_{2},i_{3},i_{4}\\}$.
Hence, LALD first deterministically selects agent $i_{4}$, i.e.,
$x_{i_{4}}=1$. For the remaining agents in $S^{\mathsf{inf.}}_{1}(G)$, LALD
assigns the probabilities as $x_{i_{3}}=1/(1+\ln 2)\approx 0.59$,
$x_{i_{2}}=\ln 2/(1+\ln 2)\log_{2}(P(i_{2})/P(i_{3}))\approx 0.11$, and
$x_{i_{1}}=\ln 2/(1+\ln 2)\log_{2}(P(i_{1})/P(i_{2}))\approx 0.09$.

In Figure 4, suppose $i_{2}>i_{3}$ and $i_{4}>j$. Then,
$S^{\mathsf{inf.}}_{1}(G)=\\{i_{1}\\}$ and
$S^{\mathsf{inf.}}_{2}(G)=\\{i_{1},i_{2},i_{3},i_{4}\\}$. Hence, LALD first
deterministically selects agent $i_{4}$, i.e., $x_{i_{4}}=1$. LALD then runs
$(1/(1+\ln 2))$-LM, which assigns the probabilities among
$S^{\mathsf{inf.}}_{1}(G)$. Here, it assigns that $x_{i_{1}}=1/(1+\ln
2)\approx 0.59$.

Figure 4: An example of the network, where the marked agents have the
relationship as $i_{1}\succ i_{2}\succ i_{3}\succ i_{4}\succ j$. The
1-influential set and the 2-influential set are represented by dashed borders.

######  Theorem 7.

LALD is an IC 2-selection mechanism.

###### Proof.

For any graph $G\in\mathcal{G}$, We consider three different types of agents.

  1. 1.

For an agent $i\notin S^{\mathsf{inf.}}_{2}(G)$, by definition, she can never
be in the set by hiding her out-edges. Hence, she will always have 0
probability to be chosen.

  2. 2.

For an agent $i\in S^{\mathsf{inf.}}_{2}(G)\setminus S^{\mathsf{inf.}}_{1}(G)$
when $S^{\mathsf{inf.}}_{2}(G)\setminus
S^{\mathsf{inf.}}_{1}(G)\neq\emptyset$, there are two cases. (i) If $i$ is the
last agent in the 2-influential set, her probability to be chosen is 1. Hence,
she has no incentive to manipulate. (ii) If $i$ is not the last agent, no
matter how she hides her out-edges, both the last agent and herself are still
in the set $S^{\mathsf{inf.}}_{2}(G)\setminus S^{\mathsf{inf.}}_{1}(G)$.
Hence, her probability to be chosen remains 0.

  3. 3.

For an agent $i\in S^{\mathsf{inf.}}_{1}(G)$, suppose
$S^{\mathsf{inf.}}_{1}(G)=\\{i_{1},\dots,i_{q}\\}$ with $i_{t}\succ i_{t+1}$
for all $1\leq t<q$. There are three cases. (i) If $i$ is the last agent
$i_{q}$ in the 1-influential set, she has no incentive to manipulate when
$S^{\mathsf{inf.}}_{2}(G)\setminus S^{\mathsf{inf.}}_{1}(G)=\emptyset$ since
$x_{i}=1$. When $S^{\mathsf{inf.}}_{2}(G)\setminus
S^{\mathsf{inf.}}_{1}(G)\neq\emptyset$, no matter how $i$ hides her out-edges,
agents in the set $S^{\mathsf{inf.}}_{2}(G)\setminus S^{\mathsf{inf.}}_{1}(G)$
will still be in the 2-influential set (even may be in the 1-influential set).
After $i$ hides some out-edges, if $S^{\mathsf{inf.}}_{2}(G^{\prime})\setminus
S^{\mathsf{inf.}}_{1}(G^{\prime})\neq\emptyset$, then $i$ cannot have higher
probability by Theorem 1; if $S^{\mathsf{inf.}}_{2}(G^{\prime})\setminus
S^{\mathsf{inf.}}_{1}(G^{\prime})=\emptyset$, then $i$ can have at most
$1/(1+\ln 2)$ probability since she will no longer be the last agent in
$S^{\mathsf{inf.}}_{1}(G^{\prime})$, which equals to her original probability.
(ii) If $i=i_{q-1}$, she has no incentive to manipulate when
$S^{\mathsf{inf.}}_{2}(G)\setminus S^{\mathsf{inf.}}_{1}(G)=\emptyset$. It is
because $i_{q}$ will always be in the 1-influential set no matter how $i$
hides her out-edges, which makes increasing her probability to be chosen
impossible. When $S^{\mathsf{inf.}}_{2}(G)\setminus
S^{\mathsf{inf.}}_{1}(G)\neq\emptyset$, it is almost the same condition as
that for $i=i_{q}$. Hence, she cannot increase her probability by
manipulation, either. (iii) If $i=i_{t}$ with $t<q-1$, no matter how she hides
her out-edges, $i_{q}$ and $i_{q-1}$ are always in the 1-influential set.
Hence, $i$’s probability to be chosen will not change.

Taking all the above together, we can conclude that the mechanism is IC. ∎

######  Theorem 8.

LALD is $\frac{3+\ln 2}{4(1+\ln 2)}$-optimal.

###### Proof.

Suppose $S^{\mathsf{inf.}}_{2}(G)=\\{i_{1},i_{2},\cdots,i_{m}\\}$ for any
graph $G\in\mathcal{G}$,. There are two different cases that need
consideration.

  1. 1.

If $S^{\mathsf{inf.}}_{2}(G)\setminus S^{\mathsf{inf.}}_{1}(G)=\emptyset$,
then according to Observation 1 and Theorem 2, we have

$\displaystyle\frac{\mathbb{E}_{S}[\sum_{i\in S}P(i)]}{\sum_{i\in
S_{2}^{*}}P(i)}$ $\displaystyle\geq\frac{P(i_{m})+\frac{1}{1+\ln
2}P(i_{1}^{*})}{P(i_{1}^{*})+P(i_{2}^{*})}$
$\displaystyle\geq\frac{\left(\frac{1}{2}+\frac{1}{1+\ln
2}\right)P(i_{1})}{P(i_{1})+P(i_{2})}$
$\displaystyle\geq\frac{\frac{1}{2}+\frac{1}{1+\ln 2}}{2}=\frac{3+\ln
2}{4(1+\ln 2)}.$

  2. 2.

If $S^{\mathsf{inf.}}_{2}(G)\setminus S^{\mathsf{inf.}}_{1}(G)\neq\emptyset$,
we first consider the progeny $P(i_{m})$. When $i_{2}^{*}\in P(i_{1}^{*})$,
the structure of the 2-influential set is characterized by Observation 5. Then
after deleting $i_{m}$’s out-edges, $i_{1}\succ i_{2}$ holds. Hence,
$P(i_{m})\geq P(i_{2})-P(i_{m})$ which implies $2P(i_{m})\geq P(i_{2})$. When
$i_{2}^{*}\notin P(i_{1}^{*})$, the structure of the 2-influential set is
characterized by Observation 6. Hence, at least one of $2P(i_{m})\geq
P(i_{1})$ and $2P(i_{m})\geq P(i_{2})$ is satisfied, which all imply that
$2P(i_{m})\geq P(i_{2})$. Therefore, let $P(i_{2})/P(i_{1})=\rho$ and we have

$\displaystyle\frac{\mathbb{E}_{S}[\sum_{i\in S}P(i)]}{\sum_{i\in
S_{2}^{*}}P(i)}$ $\displaystyle\geq\frac{P(i_{m})+\frac{1}{1+\ln
2}P(i_{1}^{*})}{P(i_{1}^{*})+P(i_{2}^{*})}$
$\displaystyle\geq\frac{\frac{1}{2}P(i_{2})+\frac{1}{1+\ln
2}P(i_{1})}{P(i_{1})+P(i_{2})}$ $\displaystyle=\frac{\rho/2+1/(1+\ln
2)}{1+\rho}$ $\displaystyle=\frac{\frac{1}{2}(1+\rho)+\frac{1-\ln 2}{2(1+\ln
2)}}{1+\rho}$ $\displaystyle=\frac{1}{2}+\frac{1-\ln 2}{2(1+\ln
2)}\cdot\frac{1}{1+\rho}$ $\displaystyle\geq\frac{1}{2}+\frac{1-\ln 2}{4(1+\ln
2)}=\frac{3+\ln 2}{4(1+\ln 2)}.$

Therefore, we can conclude that the mechanism is $\frac{3+\ln 2}{4(1+\ln
2)}$-optimal. ∎

##  5 Discussion

In this paper, we investigate the incentive-compatible selection mechanisms
for one or two influentials, where an agent’s influential power is defined by
her progeny. The goal is to select agents with progeny as large as possible
and to prevent them from hiding their out-edges at the same time. Based on the
idea of assigning possibilities of being selected to those agents who can
pretend to be the one with the largest or second largest progeny, we first
propose the $1/(1+\ln 2)$-LM mechanism for selecting one agent, which is
optimal among all IC and fair single-agent selections. We then propose the
LALD mechanism for selecting up to two influentials, which has an
approximation ratio of $(3+\ln 2)/(4(1+\ln 2))$ ($\approx 0.54$). To the best
of our knowledge, this is the first work to select more than one agent for
progeny maximization. There are several interesting future directions worth
investigating, and we provide some brief discussions here.

One direction is to narrow the gap between the current lower bound (given by
our proposed mechanism) and the current upper bound ($23/27$ as we proved) of
the approximation ratio for an optimal IC 2-selection mechanism. For the side
of upper bounds, notice that our provided upper bound does not require
additional properties like fairness defined in Zhang et al. (2021). This is
because the fairness for selecting a single agent does not apply in selecting
multiple agents (e.g., in LALD, the probability of choosing $i_{1}^{*}$ may be
also related to the structure of the 2-influential set). If we extend the
definition of fairness to $k$-fairness like

######  Definition 6 (sketch).

$i_{1}^{*}$ (or also with $i_{2}^{*}$ to $i_{k}^{*}$) has the same probability
to be chosen when the $k$-influential set and the structure formed by
$P(i_{1}^{*})$ (or also with $P(i_{2}^{*})$ to $P(i_{k}^{*})$) remain the
same.

Then, we can observe that $k$-fairness will become weaker when $k$ becomes
larger. Zhang et al. Zhang et al. (2021) conjectured that dropping
(1-)fairness will not affect the upper bound they characterized. If it can be
proven to be true, then we can also draw a corollary that introducing
$k$-fairness will not affect the upper bounds of approximation ratios for IC
$k$-selection mechanisms. For the side of improving lower bounds, one may
consider to utilize more agents in the 2-influential set but not in the
1-influential set. The main difficulty here is these agents may have too small
progeny when $P(i_{2}^{*})\ll P(i_{1}^{*})$.

The other direction is to extend the mechanisms for selecting more agents
($k\geq 3$). Similar to the case of selecting two agents, only selecting
agents in the $k^{\prime}$-influential set with $k^{\prime}<k$ may limit the
performance. A natural idea is to select $k$ agents in the $k$-influential
set. The main difficulty here is that the structure of the $k$-influential set
will become more and more complex when $k$ becomes larger. Intuitively, the
structure of the $k$-influential set depends on the relationships among agents
$i_{1}^{*}$, $\dots$, $i_{k}^{*}$. The number of different cases of the
structure will grow exponentially with $k$, which is roughly $2^{O(n^{2})}$. A
possible way to handle this challenge may be recursively considering the
influential set with lower $k$.

Finally, in terms of other applications, such as recruiting agents to promote
some advertisements, designing selection mechanisms to maximize the expected
cardinality of the union of progeny is also a promising future direction.

## Acknowledgements

This work is supported by Science and Technology Commission of Shanghai
Municipality (No. 22ZR1442200 and No. 23010503000), and Shanghai Frontiers
Science Center of Human-centered Artificial Intelligence (ShangHAI).

## References

  * Alon et al. [2011] Noga Alon, Felix Fischer, Ariel Procaccia, and Moshe Tennenholtz.  Sum of us: Strategyproof selection from the selectors.  In Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, pages 101–110, 2011.
  * Babichenko et al. [2018] Yakov Babichenko, Oren Dean, and Moshe Tennenholtz.  Incentive-compatible diffusion.  In Proceedings of the 2018 World Wide Web Conference, pages 1379–1388, 2018.
  * Babichenko et al. [2020a] Yakov Babichenko, Oren Dean, and Moshe Tennenholtz.  Incentive-compatible classification.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7055–7062, 2020.
  * Babichenko et al. [2020b] Yakov Babichenko, Oren Dean, and Moshe Tennenholtz.  Incentive-compatible selection mechanisms for forests.  In Proceedings of the 21st ACM Conference on Economics and Computation, pages 111–131, 2020.
  * Bjelde et al. [2017] Antje Bjelde, Felix Fischer, and Max Klimm.  Impartial selection and the power of up to two choices.  ACM Transactions on Economics and Computation (TEAC), 5(4):1–20, 2017.
  * Bousquet et al. [2014] Nicolas Bousquet, Sergey Norin, and Adrian Vetta.  A near-optimal mechanism for impartial selection.  In International Conference on Web and Internet Economics, pages 133–146. Springer, 2014.
  * Caragiannis et al. [2021] Ioannis Caragiannis, George Christodoulou, and Nicos Protopapas.  Impartial selection with prior information.  arXiv preprint arXiv:2102.09002, 2021.
  * Caragiannis et al. [2022] Ioannis Caragiannis, George Christodoulou, and Nicos Protopapas.  Impartial selection with additive approximation guarantees.  Theory of Computing Systems, pages 1–22, 2022.
  * Cembrano et al. [2022] Javier Cembrano, Felix A. Fischer, David Hannon, and Max Klimm.  Impartial selection with additive guarantees via iterated deletion.  In EC ’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022, pages 1104–1105. ACM, 2022\.
  * Fischer and Klimm [2014] Felix Fischer and Max Klimm.  Optimal impartial selection.  In Proceedings of the fifteenth ACM conference on Economics and computation, pages 803–820, 2014.
  * Ghalme et al. [2018] Ganesh Ghalme, Sujit Gujar, Amleshwar Kumar, Shweta Jain, and Y Narahari.  Design of coalition resistant credit score functions for online discussion forums.  In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 95–103, 2018.
  * Holzman and Moulin [2013] Ron Holzman and Hervé Moulin.  Impartial nominations for a prize.  Econometrica, 81(1):173–196, 2013.
  * Kahng et al. [2018] Anson Kahng, Yasmine Kotturi, Chinmay Kulkarni, David Kurokawa, and Ariel Procaccia.  Ranking wily people who rank each other.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
  * Kotturi et al. [2020] Yasmine Kotturi, Anson Kahng, Ariel Procaccia, and Chinmay Kulkarni.  Hirepeer: Impartial peer-assessed hiring at scale in expert crowdsourcing markets.  In Proceedings of the AAAI Conference on Artificial Intelligence, pages 2577–2584, 2020.
  * Kurokawa et al. [2015] David Kurokawa, Omer Lev, Jamie Morgenstern, and Ariel D Procaccia.  Impartial peer review.  In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
  * Mackenzie [2015] Andrew Mackenzie.  Symmetry and impartial lotteries.  Games and Economic Behavior, 94:15–28, 2015.
  * Mattei et al. [2020] Nicholas Mattei, Paolo Turrini, and Stanislav Zhydkov.  Peernomination: Relaxing exactness for increased accuracy in peer selection.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 393–399. ijcai.org, 2020.
  * Olckers and Walsh [2022] Matthew Olckers and Toby Walsh.  Manipulation and peer mechanisms: A survey.  arXiv preprint arXiv:2210.01984, 2022.
  * Page et al. [1999] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd.  The pagerank citation ranking: Bringing order to the web.  Technical report, Stanford InfoLab, 1999.
  * Wang et al. [2018] Yufeng Wang, Hui Fang, Chonghu Cheng, and Qun Jin.  Tsp: Truthful grading-based strategyproof peer selection for moocs.  In 2018 IEEE International Conference on Teaching, Assessment, and Learning for Engineering (TALE), pages 679–684. IEEE, 2018.
  * Zhang et al. [2021] Xiuzhen Zhang, Yao Zhang, and Dengji Zhao.  Incentive compatible mechanism for influential agent selection.  In International Symposium on Algorithmic Game Theory, pages 79–93. Springer, 2021.