# Game theoretic modeling of helping behavior in emergency evacuations

Jaeyoung Kwak1<EMAIL_ADDRESS>Michael H. Lees2 Wentong Cai3 Ahmad
Reza Pourghaderi4,6 Marcus E.H. Ong5,6 1 Complexity Institute, Nanyang
Technological University, Singapore  2 Informatics Institute, University of
Amsterdam, The Netherlands  3 School of Computer Science and Engineering,
Nanyang Technological University, Singapore  4 Health Systems Research Center
(HSRC), Singapore Health Services, Singapore  5 Department of Emergency
Medicine, Singapore General Hospital, Singapore  6 Health Services and Systems
Research (HSSR), Duke-NUS Medical School, Singapore

###### Abstract

We study the collective helping behavior in a room evacuation scenario in
which two volunteers are required to rescue an injured person. We propose a
game theoretic model to study the evolution of cooperation in rescuing the
injured persons. We consider the existence of committed volunteers who do not
change their decision to help the injured persons. With the committed
volunteers, all the injured persons can be rescued depending on the payoff
parameters. In contrast, without the committed volunteers, rescuing all the
injured persons is not achievable on most occasions because some lonely
volunteers often fail to find peers even for low temptation payoff. We have
quantified various collective helping behaviors and summarized those
collective patterns with phase diagrams. In the context of emergency
evacuations, our study highlights the vital importance of the committed
volunteers to the collective helping behavior.

###### pacs:

89.40.-a, 89.65.-s, 05.65.+b

##  I Introduction

Emergency evacuation simulations have received much attention since Helbing et
al. [1] characterized collective phenomena in escape panic based on numerical
simulations of self-driven many-particles. Some studies have stated that when
people are escaping from the place of danger, they tend to move faster than
their normal speed and behave in an individualistic manner, which may lead to
people pushing each other [1, 2, 3, 4]. In the majority of studies, numerical
simulations of emergency evacuation were developed based on such assumptions.
In view of this, various pedestrian emergency evacuation studies were
performed, for instance, predicting total evacuation time in a class room [5]
and preparing an optimal evacuation plan for a large scale pedestrian facility
[6].

However, other studies have presented evidence that evacuees helped injured
persons to escape the place of danger, for instance, the WHO concert disaster
occurred on December 3, 1979 in Cincinnati, Ohio, United States [7] and the
2005 London bombings in United Kingdom [8]. Researchers have investigated
helping behavior in emergency evacuation by means of pedestrian simulations.
For instance, von Sivers et al. [9, 10] applied social identity theory to
pedestrian simulation in order to simulate helping behavior observed in the
2005 London bombings. In their studies, they assumed that all the evacuees
share the same social identify which makes them willing to help others rather
than be selfish.

Although several studies focused on simulating helping behavior in emergency
evacuations, little attention has been paid to the strategic interactions
among evacuees. When an evacuee is helping an injured person to escape, the
evacuee’s helping behavior can be seen as an attempt to increase a collective
good. This is especially true when there are not enough dedicated rescue
personnel, in such circumstances other evacuees may help one another. At the
same time, helping an injured person can be a costly behavior because the
volunteering evacuee spends extra time and takes a risk to assist the injured
person. If the evacuee feels that helping behavior is a costly behavior for
him, he might not help the injured person.

Game theory is a useful tool to predict how individuals decide their strategy
in response to others’ strategy. Under game theoretic assumptions, individuals
are likely to select a strategy in a way to maximize their own payoff. Various
game theoretical models have been applied for emergency evacuation
simulations, for example, prisoner’s dilemma game [11], snowdrift game [12],
spatial game [13, 14], and evolutionary game [15]. In our previous study [16],
we employed the volunteer’s dilemma game [17, 18] to study the impact of
volunteering cost on collective helping behavior in emergency evacuations. We
observed different patterns of collective helping behaviors by changing
volunteering cost parameter. Nevertheless, little is known about how the
existence of volunteers can lead to behavioral changes of bystanders. One can
imagine that, through strategic interactions, the presence of committed
volunteers may influence on other evacuees to also help injured people. In
this way one might observe a spread of helping behavior. On the other hand, in
situations where two volunteers are needed to help an injured person, an
individual volunteer might give up helping the injured person if he cannot
find a potential partner.

In this work, we propose an evolutionary game theoretic model to examine the
dynamics of evacuees behavior influenced by other evacuees. We perform
numerical simulations for a room evacuation scenario in which two volunteers
are required to move an injured person to the place of safety. In our
numerical simulations, each evacuee updates his strategy after strategic
interactions with other evacuees within his sensory range while the evacuee
moves in the room. Hence, the spatial formation of individuals and the
strategic interactions between the individuals are coupled together in our
numerical study. We consider the existence of committed volunteers who do not
change their decision to rescue the injured persons. We characterize the
collective helping behavior by systematically controlling the game payoff
parameters along with the altruism strength. By means of numerical
simulations, we observe different collective patterns of helping behavior in a
room emergency evacuation scenario depending on the existence of committed
volunteers and the value of control parameters. We quantify different
collective helping behaviors based on the simulation results. We then study
the well-mixed population model to better interpret the numerical simulation
results. The evolutionary game theoretic model and its numerical simulation
setups are explained in Section II. We then present and explain the simulation
results with phase diagrams in Section III. Finally, we discuss the findings
of this study in Section IV.

##  II Model

Our agent-based model consists of a game theoretical model and a movement
model. The game theoretical model evaluates the probability that a bystander
would turn into a volunteer helping an injured person. The evolutionary game
model enables us to reflect the behavioral changes of an individual based on
the behavior of other evacuees. The movement model calculates the sequence of
pedestrian positions for each simulation time step. In this section, we
explain the details of our game theoretical model and the numerical simulation
setup.

###  II.1 Evolutionary game model

Table 1: Payoff of a volunteer (C) and a bystander (D) in a two-player game. Here, $R$ is the reward for mutual cooperation, $P$ is the punishment for mutual defection, $T$ is the temptation to defect, and $S$ is the sucker’s payoff. The entities indicate the payoff for the row player. | Volunteer | Bystander
---|---|---
Volunteer (C) | $R$ | $S$
Bystander (D) | $T$ | $P$
Figure 1: Schematic representation of four different games on $(T,S)$ space:
the Harmony (H), the Snowdrift (SD), the Prisoner’s dilemma (PD), and the Stag
hunt (SH) games.

We employ an evolutionary game model to study the behavioral change of players
influenced by other players. As in our previous study [16], we consider two
strategies of ambulant pedestrians: volunteer (C) and bystander (D). A
volunteer (C) helps an injured person to evacuate while a bystander (D) does
not help the injured person. In line with the two-player game, the payoff of
individual $i$’s strategy can be presented in a payoff matrix in Table 1. When
individual $i$ meets individual $j$, there are four types of payoff depending
on strategy of each individual. If both the individuals are volunteers (C),
they receive a reward for mutual cooperation, denoted by $R$. When both of
them are bystanders (D), their payoff is $P$ which is punishment for mutual
defection. When bystander $i$ is a volunteer (C) and bystander $j$ is a
bystander (D), bystander $i$ receives the sucker’s payoff $S$ which is
associated with the unreciprocated cooperation cost [19]. At the same time,
bystander $j$ receives $T$ which reflects the temptation to defect. According
to previous work [20, 21, 22], the $(T,S)$ space can be divided into four
areas: the Harmony (H), the Snowdrift (SD), the Prisoner’s dilemma (PD), and
the Stag hunt (SH) games [see Fig. 1].

We assume that two volunteers are required to move an injured person from the
room to the place of safety. A lonely volunteer cannot move the injured person
by himself, so he will try to find another volunteer who will move the injured
person together. A bystander near the lonely volunteer might decide to become
a volunteer to help the lonely volunteer to move the injured person together.
In contrast, the lonely volunteer might give up finding another volunteer and
turn into a bystander.

In the presented evolutionary game, player $i$ considers not only his own
payoff but also player $j$’s payoff. As suggested by [21, 23], we express the
effective payoff of player $i$, $u_{i}$, as a linear combination of player
$i$’s and $j$’s payoffs:

$\displaystyle u_{i}=(1-Q)\pi_{i}+Q\pi_{j},$ (1)

where $\pi_{i}$ and $\pi_{j}$ denote the payoff of player $i$ and $j$
presented in Table 1, respectively. The altruism strength $Q$ reflects how
much player $i$ regards player $j$’s payoff, which is related to the degree of
inequality aversion [24]. For simplicity, all the players are assumed to have
the same $Q$ value. Table 2 shows the effective payoff of a volunteer (C) and
a bystander (D) according to Eq. 1.

Table 2: The effective payoff of a volunteer (C) and a bystander (D) in the presented evolutionary game. Here, $Q$ is the altruism strength reflecting how much player $i$ regards player $j$’s payoff [21, 23, 24]. The entities indicate the payoff for the row player. | Volunteer (C) | Bystander(D)
---|---|---
Volunteer (C) | $R_{e}=R$ | $S_{e}=(1-Q)S+QT$
Bystander (D) | $T_{e}=(1-Q)T+QS$ | $P_{e}=P$

In each round, ambulant pedestrian $i$ randomly selects a neighbor $j$ and
adopts the neighbor $j$’s strategy with the probability [25, 26, 27]:

$\displaystyle p(\Delta u_{ij})=\frac{1}{1+\exp(\Delta u_{ij}/k)},$ (2)

where $k$ reflects uncertainties in the game dynamics and $\Delta
u_{ij}=u_{i}-u_{j}$ is payoff difference. In case of $k=0$, the probability
$p(\Delta u_{ij})$ becomes $1$ if $u_{i}<u_{j}$, and $p(\Delta u_{ij})$ is $0$
when $u_{i}>u_{j}$. In case of $k\rightarrow\infty$, the probability $p(\Delta
u_{ij})$ becomes 0.5, indicating completely random decision making.

###  II.2 Social force model

We describe the movement of pedestrians based on the social force model [28].
The position and velocity of each pedestrian $i$ at time $t$, denoted by
$\vec{x}_{i}(t)$ and $\vec{v}_{i}(t)$, are updated according to the following
equations:

$\displaystyle\frac{\mathrm{d}\vec{x}_{i}(t)}{\mathrm{d}t}=\vec{v}_{i}(t)$ (3)

and

$\displaystyle\frac{\mathrm{d}\vec{v}_{i}(t)}{\mathrm{d}t}=\vec{f}_{i,d}+\sum_{j\neq
i}{\vec{f}_{ij}}+\sum_{B}{\vec{f}_{iB}}.$ (4)

In Eq. (4), the driving force term $\vec{f}_{i,d}$ describes the tendency of
pedestrian $i$ moving toward his destination. The repulsive force terms
$\vec{f}_{ij}$ and $\vec{f}_{iB}$ reflect his tendency to keep certain
distance from other pedestrian $j$ and the boundary $B$, e.g., wall and
obstacles. We refer the readers to Appendix A for further detailed description
of the presented social force model.

###  II.3 Numerical simulation setup

Figure 2: Schematic depiction of the numerical simulation setup. 100
pedestrians are placed in a 10m$\times$10m room indicated by a blue shade
area. Pedestrians are leaving the room through an exit corridor which is 5 m
long and 2 m wide. The place of safety is set on the right, outside of the
exit corridor.

Each pedestrian is modeled by a circle with radius $r_{i}=0.2$ m. We placed
$N_{0}=100$ pedestrians in a 10m$\times$10m room indicated by a blue shaded
area in Fig. 2. Pedestrians are leaving the room through an exit corridor
which is 5 m long and 2 m wide. The place of safety is set on the right,
outside of the exit corridor. The pedestrian movement is updated with the
social force model in Eq. (4) [see Appendix A for more details].

There are $N_{i}=10$ injured persons who need a help in escaping the room and
$N=N_{0}-N_{i}=90$ ambulant pedestrians who are either volunteers or
bystanders. In the beginning of numerical simulations, one volunteer is
selected for each injured person from the set of his neighboring pedestrians
within the sensory range $l_{s}$, thus there are $N_{c,0}=10$ initial
volunteers. As described in Section II.1, we assume that an injured person
needs two volunteers, thus the maximum number of volunteers is $20$. We have
performed numerical simulations for the cases without and with committed
volunteers. In the case without committed volunteers, the initial volunteers
can change their strategy in the simulations. In the other case, where the
initial volunteers are committed, the initial volunteers do not change their
strategy. The number of volunteers evolves according to the result of
strategic interaction with other evacuees.

Table 3: Game theoretic model parameters Model parameter | symbol | value
---|---|---
mutual cooperation payoff | $R$ | 1
mutual defection payoff | $P$ | 0
temptation payoff | $T$ | [0, 1]
sucker’s payoff | $S$ | [-1, 1]
altruism strength | $Q$ | [0, 0.5]
sensory range | $l_{s}$ | 3
uncertainty parameter | $k$ | 0.25

All the ambulant pedestrians play the presented evolutionary game at each
$0.1$ second. Each ambulant pedestrian $i$ randomly selects pedestrian $j$
within the sensory range $l_{s}$ and then evaluates the probability of
switching to pedestrian $j$’s strategy according to Eq. (2). Once a bystander
interacts with a lonely volunteer and decides to cooperate with the lonely
volunteer to rescue an injured person, the bystander turns into a volunteer.
Next, the new volunteer shifts his desired walking direction vector toward the
position of injured person. After arriving at the injured person, the new
volunteer will evacuate the injured person with the peer volunteer after a
preparation time of 5 s. On the other hand, if a lonely volunteer decides to
become a bystander, then he changes his desired walking direction vector
toward the exit. To implement the presented game theoretic model, the
parameter values in Table 3 are selected based on the previous work [26, 29,
21]. Note that we control the game payoff parameters $T$ and $S$ along with
the altruism strength $Q$.

##  III Results and discussions

The presented game theoretic model is studied by means of numerical
experiments. We present the results from agent-based simulations. We then
study a well-mixed population model to interpret the presented results.

###  III.1 Agent-based simulations

Figure 3: Representative examples of individual strategy changes in the
numerical simulations. The individuals changing their strategy are indicated
by red dotted circle lines. Open black circles indicate the injured persons
and full dark circles denote the volunteers helping the injured persons. Green
circles represent the bystanders. The presented snapshots are captured from
pedestrian trajectories generated from the case without committed volunteers
with $T=0.1$, $S=0.1$, and $Q=0$. (a) A lonely volunteer (indicated by red
dotted circle 1) at simulation time $t=0.55$ s (left) turns into a bystander
at simulation time $t=0.6$ s (right). At the same time, two bystanders
indicated by red dotted circles 2 and 3 at simulation time $t=0.55$ s (left)
become volunteers at simulation time $t=0.6$ s (right), seemingly due to the
influence of nearby volunteers in red dotted circles 4 and 5, respectively.
(b) Similarly to (a), another lonely volunteer indicated by red dotted circle
6 at simulation time $t=0.75$ s (left) gives up rescuing an injured person and
become a bystander at simulation time $t=0.8$ s (right).

From the numerical experiments, we can see individuals who change their
strategy as a result of interaction with their neighbors, refer to Fig. 3. As
can be seen from Fig. 3(a), two bystanders become volunteers seemingly due to
the influence of volunteers near them. At the same time, a lonely volunteer
turns into a bystander after interacting with a nearby bystander. In Fig.
3(b), similarly to the observation presented in Fig. 3(a), one can see that a
lonely volunteer gives up rescuing an injured person and becomes a bystander
after interacting with a nearby bystander. In the case with committed
volunteers, one can also see the change of individual strategy as shown in
Fig. 3

To quantify the level of collective helping behavior, similarly to Ref. [11],
we define a normalized fraction of cooperators $n_{c}$ $\in$ $[-1,1]$ as

$\displaystyle n_{c}=\frac{N_{c}-N_{c,0}}{N_{c,0}},$ (5)

where $N_{c}$ and $N_{c,0}$ are the number of volunteers in the stationary
state and in the initial condition, respectively. A positive value of $n_{c}$
suggests that the number of volunteers $N_{c}$ is greater than the initial
one, $N_{c,0}$, inferring that some lonely volunteers successfully find peer
volunteers. In case of $n_{c}=1$, all the lonely volunteers eventually find
their peers, thus all the injured persons are rescued. A negative value
indicates that some lonely volunteers changed their mind to become bystanders.
In case of $n_{c}=-1$, all the lonely volunteers turn into bystanders, so none
of the injured persons are rescued. The stationary state values of $n_{c}$ in
the $(T,S)$ space are presented in Appendix B.

Figure 4: Representative time series of the fraction of cooperators $n_{c}$ in
the case without committed volunteers. (a) The $n_{c}$ curve (generated with
$T=0.1$, $S=0.95$, and $Q=0$) reaches to 1, indicating that all the lonely
volunteers successfully find peer volunteers, thus all the injured are
rescued. (b) The $n_{c}$ curve generated from the same parameter combination
of $T$, $S$, and $Q$ as (a), but with a different set of random seeds. The
value of $n_{c}$ increases in the course of time, but the stationary state
value is smaller than $1$. This implies that some lonely volunteers
successfully find peers while other lonely volunteers fail to o so, thus not
all the injured persons are rescued. (c) The stationary state value of $n_{c}$
is 0, showing that the number of volunteers is not increased in effect. The
presented curve is generated with $T=0.1$, $S=0.15$, and $Q=0$. (d) The
$n_{c}$ curve becomes negative, inferring that some lonely volunteers turn
into bystanders, thus some injured persons are not rescued. Here, the curve is
generated with $T=0.1$, $S=-0.15$, and $Q=0$. (e) The $n_{c}$ curve ($T=0.1$,
$S=-0.75$, and $Q=0$) decreases to $-1$, suggesting that none of the injured
are rescued because all the lonely volunteers turn into bystanders.

Representative time series of the fraction of cooperators $n_{c}$ in the case
without committed volunteers are presented in Fig. 4. The curves in Fig. 4(a)
and Fig. 4(b) are generated with the same parameter combination of $T$, $S$,
and $Q$ but different sets of random seeds. As can be seen from Fig. 4(a), the
stationary state value of $n_{c}$ is positive but smaller than $1$. In Fig.
4(b), the stationary state value of $n_{c}$ reaches to $1$, suggesting that
all the lonely volunteers successfully find peer volunteers, thus all the
injured are rescued. However, this complete rescue is not always possible in
that the number of volunteers in the stationary state is changing depending on
the random seeds. As shown in Fig. 4(c), the stationary state value of $n_{c}$
is 0, inferring that the number of volunteers is not increased in effect. In
Fig. 4(d), $n_{c}$ becomes negative, implying that some lonely volunteers turn
into bystanders, thus some injured persons are not rescued. Figure 4(e)
presents that $n_{c}$ decreases to $-1$, suggesting that none of the injured
are rescued because all the lonely volunteers turn into bystanders.

Figure 5: Same graphs as Figs. 4(a)-(c) but for the case with committed
volunteers. (a) When $T$ is low and $S$ is high for a given $Q$, the
stationary state value of $n_{c}$ is $1$, suggesting that all the lonely
volunteers successfully find peer volunteers, thus all the injured are
rescued. The presented curve is generated with $T=0.3$, $S=0.5$, and $Q=0$.
(b) For intermediate level of $T$ and $S$, the $n_{c}$ curve increases like in
(a) but the stationary state value is smaller than $1$, indicating that some
lonely volunteers successfully find peers while other lonely volunteers fail
to do that. The presented $n_{c}$ curve is obtained with $T=0.8$, $S=0.1$, and
$Q=0$. (c) If $T$ is high and $S$ is low, the value of $n_{c}$ curve does not
increase, denoting that the number of volunteers is not increased in effect.
The presented curve is generated with $T=1.7$, $S=-0.5$, and $Q=0$.

Figure 5 shows same graphs as Fig. 4(a)-(c) but for the case with committed
volunteers. As indicated by Fig. 5(a), the stationary state value of $n_{c}$
becomes $1$ when $T$ is low and $S$ is high for a given $Q$. That is, all the
lonely volunteers successfully find peer volunteers, thus all the injured are
rescued. For intermediate values of $T$ and $S$, the $n_{c}$ curve increases
as in Fig. 5(a) but the stationary state value is smaller than $1$. This
indicates that some lonely volunteers successfully find peers while other
lonely volunteers fail to do that, see Fig. 5(b). When $T$ is high and $S$ is
low, as can be seen from Fig. 5(c), the value of $n_{c}$ curve does not
increase.

Figure 6: Complete rescue probability $P_{r}$ in the case without committed
volunteers as a function of $S$ and $T$ for different values of $Q$: (a) $Q=0$
(low level) and (b) $Q=0.2$ (intermediate level). The case of high $Q$ is not
presented here because $P_{r}$ is always zero for the entire $(T,S)$ space,
implying that a complete rescue is not possible. For each parameter
combination of $(T,S)$, increasing $Q$ yields lower $P_{r}$. In the case
without committed volunteers, $P_{r}=1$ is not realized. Figure 7: Complete
rescue probability $P_{r}$ in the case with committed volunteers as a function
of $S$ and $T$ for different values of $Q$: (a) $Q=0$ (low level), (b) $Q=0.2$
(intermediate level), and (c) $Q=0.4$ (high level). Similarly to the case
without committed volunteers, $P_{r}$ increases against $S$ for a given $T$.
One can see $P_{r}=1$ for high $S$ with low $T$ and $Q$, but it is not
observable if $Q$ is above a certain value.

In the context of emergency evacuations, it is interesting to examine whether
all the injured persons are rescued. We characterize different patterns of
collective helping behavior by means of $P_{r}$ which denotes the probability
of complete rescue. We measure the value of $P_{r}$ by counting the occurrence
of complete rescue over 100 independent simulation runs for each parameter
combination $(T,S)$ along with a given value of $Q$. Based on the value of
$P_{r}$, we define three phases: full cooperation, partial cooperation, and
defection phases. The full cooperation phase is characterized by $P_{r}=1$,
suggesting that the complete rescue is always achievable regardless of random
seeds. One can identify the partial cooperation phase with $1>P_{r}>0$, in
which the complete rescue can be seen depending on random seeds. The defection
phase is characterized by $P_{r}=0$, implying that the complete rescue is not
observable from simulation results. In the case without committed volunteers
[see Fig. 6], the complete rescue probability $P_{r}$ is always $0$,
indicating that the full cooperation phase does not exist. In addition, the
value of $P_{r}$ becomes smaller as $Q$ grows for a given value of $(T,S)$. In
the case with committed volunteers [refer to Fig. 7], $P_{r}$ becomes $1$ with
high values of $S$ when $Q$ is at low level. This suggests the existence of
full cooperation phase, see Fig. 7(a). For high level of $Q$, the value of
$P_{r}$ tends to approach $1$, but $P_{r}$ is still smaller than $1$. This
implies that the full cooperation phase is not observable when $Q$ is high.

---
Figure 8: Phase diagrams summarizing the numerical results: (a) the case
without committed volunteers and (b) the case with committed volunteers. The
$(T,S)$ space is divided into different phases by means of the complete rescue
probability $P_{r}$. Here, D, PC, and FC indicate the defection, partial
cooperation, and full cooperation phases, respectively. Different symbols
represent the boundaries between different phases: red circles ($\bigcirc$)
for the boundary between FC and PC, and blue rectangles ($\square$) for the
boundary between PC and D. The full cooperation phase (i.e., $P_{r}=1$) is not
observed in the case without committed volunteers, but it can be seen in the
case without committed volunteers for high $S$ with low $T$ and $Q$. In the
case without committed volunteers, the area of partial cooperation (PC) phase
shrinks as $Q$ increases and is virtually disappeared when $Q=0.4$. In the
case with committed volunteers, in contrast, the area of partial cooperation
phase is expanding as $Q$ increases. In addition, the areas of full
cooperation (FC) and defection (D) phases shrink and then disappear as $Q$
increases.

Figure 8 summarizes numerical results of phase characterizations. The
parameter space of $(T,S)$ is divided into different phases by means of the
complete rescue probability $P_{r}$. In the case without committed volunteers
[see Figure 8(a)], if $Q$ is small, the partial cooperation phase can be
observed in a limited area of $(T,S)$ but the cooperation phase is not
observed. The area of partial cooperation phase is getting smaller as $Q$
increases and becomes invisible when $Q=0.4$. At the same time, the defection
phase is expanding in the $(T,S)$ space as $Q$ grows. From Figure 8(b), when
$Q$ is small, one can observe the full cooperation phase for high $S$ and low
$T$, corresponding to the Harmony (H) game. In addition, the defection phase
is widely observed in the Prisoner’s dilemma (PD) game and can be seen from
some $(T,S)$ combinations in the Snowdrift (SD) and the Stag hunt(SH) games.
As $Q$ grows, the area of partial cooperation phase is expanding while the
defection phase area is decreasing. At the same time, surprisingly, increasing
$Q$ eventually leads to the disappearance of full cooperation phase. This can
be understood that increasing $Q$ contributes to the spreading of cooperation,
but some lonely volunteers still fail to find a peer volunteer. This is
apparently because the altruism strength $Q$ reduces the payoff difference
between the cooperator and defector. Consequently, the probability that a
bystander switches to a volunteer is reduced. In terms of the two-player game,
increasing $Q$ makes all the games (i.e., H, SD, SH, and PD games) result in
the partial cooperation phase, thus the collective helping behavior becomes
insensitive to the values of $S$ and $T$.

###  III.2 Interpretation in terms of well-mixed population model

Some of the results presented in Section III.1 can be interpreted in terms of
the well-mixed population model. Based on the well-mixed population model, we
study the evolution of the number of cooperators $N_{C}$ without considering
the spatial formation of individuals. The evolution of $N_{C}$ is given as

$\displaystyle N_{C}(t+\Delta t)=N_{C}(t)+\frac{dN_{C}(t)}{dt}\Delta t,$ (6)

where $dN_{C}(t)/dt$ is the time derivative of the number of cooperators at
time $t$ and $\Delta t$ is the time step. At $t=0$, $N_{C}(t)$ is given as
$N_{C,0}$ denoting the initial number of cooperators. If $dN_{c}(t)/dt$ is
positive, the number of cooperators $N_{C}(t)$ is going to increase. Negative
$dN_{C}(t)/dt$ leads to the decrement of $N_{C}(t)$, so $N_{C}(t)$ in the
stationary state is likely smaller than $N_{C,0}$. Note that, in our study,
$dN_{C}(t)/dt$ is a function of payoff parameters $T$ and $S$ along with the
altruism strength $Q$. We refer the readers to Appendix C for further details
relate to Eq. (6).

In the case without committed volunteers, the majority of numerical
simulations result in the defection phase, see Fig. 8(a). According to Eq.
(6), this is seemingly because of the negative value of $dN_{C}(t)/dt$ in the
beginning of numerical simulations. Consequently, the number of cooperators
decreases in the course of time, leading to the loss of volunteers.

In the case with committed volunteers [see Fig. 8(b)], partial and full
cooperation phases are frequently observed over a larger area of $(T,S)$
space. This suggests that $dN_{C}(t)/dt$ is mostly positive in the beginning
of numerical simulations. In addition, due to the committed volunteers,
$dN_{C}(t)/dt$ does not become negative irregardless of payoff parameters $T$
and $S$, implying that the stationary state value of $N_{C}$ is equal or
larger than $N_{C,0}$.

It is generally accepted that the well-mixed population model often fails to
predict complex collective phenomena observed from numerical simulations due
to its major limitation. The well-mixed population model is not able to
consider the spatial formation of individuals, thus the heterogeneity in
spatial structure cannot be reflected in the evolutionary game analysis.
Previous studies [30, 31] have highlighted that the spatial structure is of
great importance to the onset of collective cooperation behaviors. Unlike
those previous studies, in this study, one can observe that the results from
the presented well-mixed population approach is in good agreement with those
from numerical simulations presented in Section III.1. This is seemingly
because the evacuation scenario is studied for a small fixed square room and
the mobility pattern of individuals is simple.

##  IV Conclusion

This paper presents a game theoretical model of helping behavior among
evacuees. We have numerically investigated the evolution of collective helping
behavior in a room evacuation scenario. In our numerical simulations, injured
persons were placed in the room and it was assumed that each injured person
needs the help of two volunteers during the evacuation. We assigned an initial
volunteer to each injured person in the beginning of numerical simulations.
The initial volunteers who do not changing their decision to rescue an injured
person are indicated as committed volunteers. In this study, we considered the
cases without and with committed volunteers. The initial volunteers can change
their strategy in the case without committed volunteers, but it is not allowed
in the case with committed volunteers. The number of volunteers evolved as a
result of strategic interactions between individuals.

By systematically controlling payoff parameters and altruism strength, we
characterized different collective helping behaviors. In the case without
committed volunteers, we observed the partial cooperation phase for low
temptation payoff $T$ and high sucker’s payoff $S$ with low altruism strength
$Q$. For high $Q$, the defection phase was widely observed in a wide area of
$(T,S)$ space, even in the Harmony game. However, different patterns were
observed in the case with committed volunteers. For high $S$ with low $T$ and
$Q$, the full cooperation phase was observed from the numerical simulations,
in which all the injured persons were rescued regardless of random seeds. As
$Q$ increases, it was observed that the area of partial cooperation phase was
expanding in the $(T,S)$ space. Consequently, when $Q$ was high, the whole
$(T,S)$ space became the partial cooperation phase, even in the Prisoner’s
dilemma game. It is suggested that the existence of committed volunteers can
contribute to the appearance of full cooperation phase in low $Q$ and
expansion of partial cooperation phase in high $Q$. Increasing the altruism
strength $Q$ reduced the payoff difference between the cooperator and
defector, leading to the spreading of defection phase in the case without
committed volunteers and partial cooperation phase in the case of committed
volunteers. Surprisingly, in the case with committed volunteers, increasing
$Q$ eventually also resulted in the disappearance of full cooperation phase.
This is seemingly because increasing $Q$ reduces the payoff difference between
the cooperator and defector, thus the probability that a bystander switches to
a volunteer is reduced.

The numerical simulation results of this study can be understood in line with
the well-mixed population model. In the case with committed volunteers, the
time derivative of the number of cooperators was mostly positive in the
beginning of simulations. Consequently, we could often observe the partial and
full cooperation phases. On the other hand, in the case without committed
volunteers, the time derivative of the number of cooperators was negative on
most occasions, leading to the loss of volunteers. In contrast to previous
studies [30, 31], the analysis based on the well-mixed population model
demonstrated a good agreement with our numerical simulation results. This is
seemingly due to the simple mobility patterns of evacuees in a small fixed
square room.

There are possible directions of future work addressing the limitations of
this study. To focus on the essential features of the strategic interactions
in helping behavior, this study has considered a simple room evacuation
scenario. The presented model needs to be tested with more complex geometry
conditions to further examine complex nature of strategic interactions among
individuals. In this study, the temptation payoff $T$ and the sucker’s payoff
$S$ were assumed to be same for the every evacuee. It would be interesting to
introduce different values of $T$ and $S$ to each evacuee. For instance, the
values of $T$ and $S$ can be given depending on the distance to the exit,
speed reduction factor $\alpha$, or the estimated extra evacuation time
incurred by helping the injured persons. In addition, it was assumed that each
individual interacts with a random neighbor within the sensory range.
According to Ref. [32], the emergence pattern of cooperation can be affected
by the selection of interaction rule for the evolutionary game. This is
apparently because changing to another interaction rule is likely to make a
difference in evaluating the payoff difference with the interaction partners.
One can consider other interaction rules, for instance, the stochastic
interaction by which individuals can interact with several different players
in each time step. Another possible direction of future work can be planned in
line with the number of committed volunteers. In this study, we observed that
the partial and full cooperation phases were widely spreading in the $(T,S)$
space as a result of introducing committed volunteers. This study presented
the difference between without and with committed volunteers, but did not
investigate under which conditions the committed volunteers contribute to the
appearance of system-wide cooperation. Previous studies [22, 33, 34] have
examined under what conditions the committed minorities play a pivotal role in
the emergence of cooperation in a well-mixed population and structured
networks. In the context of pedestrian evacuations, the results and analysis
from our approach can be extended to quantify the critical mass effect in
collective helping behavior in terms of the number of committed volunteers.

## Acknowledgements

This research is supported by National Research Foundation (NRF) Singapore,
GOVTECH under its Virtual Singapore Program Grant No. NRF2017VSG-
AT3DCM001-031. We thank Mr. Vinayak Teoh Kannappan for his help in
implementing the presented agent-based model with C++.

##  Appendix A Details of the social force model

In Section II.2, we presented a general form of the social force models [28,
35, 36]. This appendix provides further details of the presented social force
model.

The social force models describe the acceleration of pedestrian $i$ as a
superposition of driving and repulsive force terms according to the following
equation of motion:

$\displaystyle\frac{d\vec{v}_{i}(t)}{dt}=\vec{f}_{i,d}+\sum_{j\neq
i}{\vec{f}_{ij}}+\sum_{B}{\vec{f}_{iB}}.$ (7)

The driving force $\vec{f}_{i,d}$ is given as

$\displaystyle\vec{f}_{i,d}=\frac{v_{d}\vec{e}_{i}-\vec{v}_{i}(t)}{\tau},$ (8)

where ${v}_{d}$ is the desired speed and $\vec{e}_{i}$ is a unit vector
indicating the desired walking direction of pedestrian $i$. The relaxation
time $\tau$ controls how fast the pedestrian $i$ adapts its velocity to the
desired velocity.

The interpersonal repulsive force term $\vec{f}_{ij}$ is specified according
to the circular specification [35] which is the most simplistic form of the
interpersonal repulsive interaction. The explicit form of $f_{ij}$ can be
written as

$\displaystyle\vec{f}_{ij}$ $\displaystyle=$ $\displaystyle
C_{p}exp\left(\frac{r_{i}+r_{j}-d_{ij}}{l_{p}}\right)\vec{e}_{ij},$ (9)

where $\vec{e}_{ij}=\vec{d}_{ij}/d_{ij}$ is a unit vector pointing from
pedestrian $j$ to pedestrian $i$, and
$\vec{d}_{ij}\equiv\vec{x}_{i}-\vec{x}_{j}$ is the distance vector pointing
from pedestrian $j$ to pedestrian $i$. The strength and the range of repulsive
interaction between pedestrians are denoted by $C_{p}$ and $l_{p}$,
respectively. Instead of the circular specification, one might select a
different form of specifications such as elliptical specification I (ES-1)
[28] and elliptical specification II (ES-2) [36].

In addition to the interpersonal repulsive force term $\vec{f}_{ij}$ presented
in Eq. (9), the interpersonal elastic force term $\vec{g}_{ij}$ is added when
the distance $d_{ij}$ is smaller than the sum $r_{ij}=r_{i}+r_{j}$ of their
radii $r_{i}$ and $r_{j}$. We describe $\vec{g}_{ij}$ as Helbing [35]
suggested,

$\displaystyle\vec{g}_{ij}=h(r_{ij}-d_{ij})\left\\{k_{n}\vec{e}_{ij}+k_{t}[(\vec{v}_{j}-\vec{v}_{i})\cdot\vec{t}_{ij}]\vec{t}_{ij}\right\\},$
(10)

where $k_{n}$ and $k_{t}$ are the normal and tangential elastic constants,
respectively. A unit vector $\vec{e}_{ij}$ is pointing from pedestrian $j$ to
pedestrian $i$, and $\vec{t}_{ij}$ is a unit vector perpendicular to
$\vec{e}_{ij}$. The function $h(x)$ yields $x$ if $x>0$, while it gives $0$ if
$x\leq 0$.

The repulsive force from boundaries $\vec{f}_{iB}$ is given as

$\displaystyle\vec{f}_{iB}=C_{b}\exp\left(-\frac{d_{iB}}{l_{b}}\right)\vec{e}_{iB},$
(11)

where $d_{iB}$ is the perpendicular distance between pedestrian $i$ and wall,
and $\vec{e}_{iB}$ is the unit vector pointing from the wall $B$ to the
pedestrian $i$. The strength and range of repulsive interaction from
boundaries are denoted by $C_{b}$ and $l_{b}$.

Table 4: Social force model parameters Model parameter | symbol | value
---|---|---
interpersonal repulsion strength | $C_{p}$ | 3.0
interpersonal repulsion range | $l_{p}$ | 0.2
normal elastic constants | $k_{n}$ | 50.0
tangential elastic constants | $k_{t}$ | 25.0
boundary repulsion strength | $C_{b}$ | 10.0
boundary repulsion range | $l_{b}$ | 0.1

To implement the presented social force model, the parameter values in Table 4
are selected based on the previous studies [28, 37, 35, 38].

The ambulant pedestrians move with the initial desired speed
$v_{d}=v_{d,0}=1.2$ m/s and with relaxation time $\tau=0.5$ s, and their speed
cannot exceed $v_{\rm max}=2.0$ m/s. Until now, the speed of volunteers
rescuing the injured persons is often assumed by the modelers, like the work
of von Sivers et al. [9, 10]. We applied speed reduction factor $\alpha=0.5$
to the volunteers rescuing the injured persons, so they move with a reduced
desired speed $v_{d}=\alpha v_{d,0}=0.6$ m/s. Following previous studies [39,
40, 37], we discretized the numerical integration of Eq. (7) using the first-
order Euler method:

$\displaystyle\vec{v}_{i}(t+\Delta t)$ $\displaystyle=$
$\displaystyle\vec{v}_{i}(t)+\vec{a}_{i}(t)\Delta t,$ (12)
$\displaystyle\vec{x}_{i}(t+\Delta t)$ $\displaystyle=$
$\displaystyle\vec{x}_{i}(t)+\vec{v}_{i}(t+\Delta t)\Delta t.$ (13)

Here, $\vec{a}_{i}(t)$ is the acceleration of pedestrian $i$ at time $t$ which
can be obtained from Eq. (7). The velocity and position of pedestrian $i$ is
denoted by $\vec{v}_{i}(t)$ and $\vec{x}_{i}(t)$, respectively. The time step
$\Delta t$ is set as 0.05 s.

##  Appendix B Exploration of the (T, S) space

In Section III.1, we presented the representative time series of the fraction
of cooperators $n_{c}$: the case without committed volunteers [Fig. 4] and the
case wit committed volunteers [Fig. 5]. To complement the results presented in
Figs. 4 and 5, we evaluate the stationary state values of $n_{c}$ in terms of
the average and standard deviation of $n_{c}$, i.e., $\mu(n_{c})$ and
$\sigma(n_{c})$. The values of $\mu(n_{c})$ and $\sigma(n_{c})$ are measured
over 100 independent simulation runs for a parameter combination of $(T,S)$
with a fixed value of $Q$.

Figure 9: Stationary state values of $n_{c}$ in the case without committed
volunteers: (a) $Q=0$ (low level), (b) $Q=0.2$ (intermediate level), and (c)
$Q=0.4$ (high level). The average and standard deviation of the normalized
fraction of cooperators, i.e., $\mu(n_{c})$ and $\sigma(n_{c})$, are presented
in the left and right columns, respectively. Different symbols represent the
different values of $T$. Results are evaluated over 100 independent simulation
runs. For each given $Q$, $\mu(n_{c})$ grows as $S$ increases. The
$\sigma(n_{c})$ curves increase and then decrease if $Q$ is at low and
intermediate levels, but the change of $\sigma(n_{c})$ against $S$ is not
significant when $Q$ is high.
---
Figure 10: The stationary state values of $n_{c}$ for the case without
committed volunteers in the $(T,S)$ space: (a) average $\mu(n_{c})$ and (b)
standard deviation $\sigma(n_{c})$. Each panel corresponds to different values
of altruism strength $Q$. Results are averaged over 100 independent simulation
runs.

In the case without committed volunteers, $\mu(n_{c})$ grows as $S$ increases
for a given value of $Q$, indicating that high $S$ leads to the increment of
volunteers. The $\sigma(n_{c})$ curves increase and then decrease if $Q$ is at
low and intermediate levels, but the change of $\sigma(n_{c})$ against $S$ is
not significant when $Q$ is high. In Fig. 9(a), $\mu(n_{c})$ is almost $1$
when $S$ is high and $T$ is low, but $\sigma(n_{c})$ is not zero. This
suggests that the complete rescue of all the injured persons is not always
achievable, which is consistent with our observation from Fig. 4(a) and Fig.
4(b). In addition, if we increase $Q$, we can observe that the minimum value
of $\mu(n_{c})$ is increasing while its maximum value is decreasing for given
value of $T$. This is seemingly due to the increment of $\sigma(n_{c})$. In
Fig. 10, we present the average and standard deviation of the normalized
fraction of cooperators in the $(T,S)$ space. In line with the results in Fig.
9, the difference between minimum and maximum values of $\mu(n_{c})$ is
decreasing while the value of $\sigma(n_{c})$ is growing as we increase $Q$.

Figure 11: Same graph as Fig. 9 but for the case with committed volunteers:
(a) $Q=0$ (low level), (b) $Q=0.2$ (intermediate level), and (c) $Q=0.4$ (high
level). Similarly to the case without committed volunteers, for a given value
of $Q$, the $\mu(n_{c})$ curves show an increasing trend as $S$ increases.
However, $\mu(n_{c})$ is virtually 1 while $\sigma(n_{c})$ is small when $Q$
is high, which is different from the case without committed volunteers.
---
Figure 12: The stationary state values of $n_{c}$ for the case with committed
volunteers in the $(T,S)$ space: (a) average $\mu(n_{c})$ and (b) standard
deviation $\sigma(n_{c})$. Each panel corresponds to different values of
altruism strength $Q$. Results are averaged over 100 independent simulation
runs.

In the case with committed volunteers, the $\mu(n_{c})$ curves show an
increasing trend as $S$ increases for a given value of $Q$, similarly to the
case without committed volunteers. However, one can notice different patterns
of $\mu(n_{c})$ and $\sigma(n_{c})$ curves when $Q$ is high, see Fig. 11(c).
It can be seen that $\mu(n_{c})$ is virtually $1$ but smaller than $1$. In
addition, $\sigma(n_{c})$ is decreasing for increasing $Q$, but
$\sigma(n_{c})$ does not become $0$. This implies that the stationary state
values of $n_{c}$ is smaller than $1$ even for high $S$, thus the complete
rescue is not always possible. This is compatible with the results presented
in Fig. 8(b). Figure 12 presents the numerical results of $\mu(n_{c})$ and
$\sigma(n_{c})$ in the $(T,S)$ space.

##  Appendix C Details of the well-mixed population model description

In Section III.2, we interpreted the numerical simulation results from the
cases without and with committed volunteers. This appendix provides more
details of our interpretation, especially how the well-mixed population model
can explain the numerical simulation results.

Based on previous studies [22, 33, 34], we consider a well-mixed population
model with a finite population consisting of $N$ individuals. For the case
without committed volunteers, the evolution of the number of cooperators,
$dN_{C}(t)/dt$, can be described in terms of the increase rate $f_{+}$ and
decrease rate $f_{-}$,

$\frac{dN_{C}(t)}{dt}=f_{+}-f_{-}.$ (14)

The increase rate $f_{+}$ is equal to the product of the pair selection
probability $p_{s}$ and the strategy adaption probability $p(\Delta u_{DC})$:

$f_{+}=p_{s}p(\Delta
u_{DC})=\frac{N_{C}N_{D}}{N(N-1)}\frac{1}{1+\exp[(T_{e}-S_{e})/k]},$ (15)

where $N$ is the number of ambulant pedestrians and $N_{C}$ and
$N_{D}=N-N_{C}$ are the number of cooperators (i.e., volunteers) and defectors
(i.e., bystanders), respectively. With the pair selection probability, we
select a pair of players with different strategies, i.e., one player is a
cooperator ($C$) and the other one is a defector ($D$). Here, $\Delta
u_{DC}=u_{D}-u_{C}$ is payoff difference obtained by subtracting from $u_{D}$
to $u_{C}$. Note that the payoffs $u_{C}$ and $u_{D}$ are given as $S_{e}$ and
$T_{e}$, which are given in Table 1, respectively. Based on the strategy
adaption probability, player $i$ ($D$) updates his strategy to player $j$’s
one ($C$), i.e., switching from $D$ to $C$.

Likewise, the decrease rate $f_{-}$ is given as

$f_{-}=p_{s}p(\Delta
u_{CD})=\frac{N_{C}N_{D}}{N(N-1)}\frac{1}{1+\exp[(S_{e}-T_{e})/k]}.$ (16)

Next, we check the trend of the number of cooperators $N_{C}(t)$ in the course
of time by looking into the sign of its change rate $dN_{C}(t)/dt$. As
described in Section III.2, a positive value of $dN_{C}(t)/dt$ possibly leads
to the full or partial cooperation phases, while a negative value results in
the defection phase. Based on Eqs. (15) and (16), we rewrite Eq. (14) as

$\begin{split}\frac{dN_{C}(t)}{dt}=&\frac{N_{C}N_{D}}{N(N-1)}\left\\{\frac{1}{1+\exp[(T_{e}-S_{e})/k]}\right.\\\
&\left.-\frac{1}{1+\exp[(S_{e}-T_{e})/k]}\right\\}.\end{split}$ (17)

One can notice that the first term on the right-hand side is always positive
for $N>1$ and $N_{C}>0$, thus the sign of $dN_{C}(t)/dt$ exclusively depends
on the sign of $p(\Delta u_{DC})-p(\Delta u_{CD})$. Fig. 13(a) presents the
value of $dN_{C}(t)/dt$ in the $(T,S)$ space for different values of $Q$,
comparable to the results presented in Fig. 10(a). As $Q$ increases, the value
of $dN_{C}(t)/dt$ tends to decrease for a given value of $T$ and $S$,
suggesting the disappearance of partial cooperation phase and spreading of
defection phase.

---
Figure 13: $dN_{C}(t)/dt$ in the $(T,S)$ space computed in line with the well-
mixed population model [see Eq. (17)]: (a) the case without committed
volunteers and (b) the case with committed volunteers. The presented results
are generated with $N=90$ ambulant pedestrians, $N_{D}=80$ bystanders, and
$N_{C}=10$ volunteers for (a) and $N_{C0}=10$ committed volunteers for (b).
Each panel corresponds to different values of altruism strength $Q$.

Now we focus on the case with committed volunteers. Like the case without
committed volunteers, $dN_{C}(t)/dt$ is described in terms of the increase
rate $f_{+}$ and decrease rate $f_{-}$, i.e., $dN_{C}(t)/dt=f_{+}-f_{-}$ [Eq.
(14)]. Note that the committed volunteers do not update their strategy but
they can induce defectors to become cooperators. The increase rate $f_{+}$ is
same as Eq. (15), while the decrease rate $f_{-}$ has to be modified. The
sampling rate $p_{s}$ is given as

$\displaystyle p_{s}=\frac{(N_{C}-N_{C,0})N_{D}}{N(N-1)},$ (18)

where $N_{C,0}$ is the initial number of volunteers. In the case with
committed volunteers, all the initial volunteers are committed volunteers.
Accordingly, $(N_{C}-N_{C,0})$ denotes the number of volunteers who are not
initial volunteers, indicating the number of volunteers who can change their
strategy depending on the outcome of strategic interactions. The decrease rate
$f_{-}$ is modified as

$\displaystyle
f_{-}=\frac{(N_{C}-N_{C,0})N_{D}}{N(N-1)}\frac{1}{1+\exp[(S_{e}-T_{e})/k]}.$
(19)

In the beginning of our numerical simulations, $N_{C}$ is same as $N_{C,0}$,
implying the decrease rate $f_{-}$ becomes zero. The time derivative of
$N_{C}$ should read

$\begin{split}\frac{dN_{C}(t)}{dt}=&\frac{N_{C}N_{D}}{N(N-1)}\frac{1}{1+\exp[(T_{e}-S_{e})/k]}\\\
&-\frac{(N_{C}-N_{C,0})N_{D}}{N(N-1)}\frac{1}{1+\exp[(S_{e}-T_{e})/k]}.\end{split}$
(20)

Note that, for $N_{C,0}>0$, Eq. (20) is always larger than Eq. (17), meaning
that $dN_{C}(t)/dt$ of the case with committed volunteers is higher than that
of the case without committed volunteers. Furthermore, the value of
$dN_{C}(t)/dt$ is positive in the beginning of our numerical simulations,
likely leading to the increment of $N_{C}$. Figure 13(b) shows $dN_{C}(t)/dt$
in $(T,S)$ space for different values of $Q$, showing qualitatively the same
results as those presented in Fig. 12(a). As $Q$ increases, the value of
$dN_{C}(t)/dt$ tends to decrease for high $S$ and low $T$ but increase for the
rest of $(T,S)$ space. This implies that the area of partial cooperation phase
is expanding.

## References

  * Helbing  _et al._ [2000] D. Helbing, I. Farkas, and T. Vicsek, Simulating dynamical features of escape panic, Nature 407, 487 (2000).
  * Mintz [1951] A. Mintz, Non-adaptive group behavior, The Journal of Abnormal and Social Psychology 46, 150 (1951).
  * Kelley  _et al._ [1965] H. Kelley, J. Condry Jr, A. Dahlke, and A. Hill, Collective behavior in a simulated panic situation, Journal of Experimental Social Psychology 1, 20 (1965).
  * Braga and Moita [2017] H. Braga and G. Moita, On the Boate Kiss fire and the Brazilian safety legislation: what we can learn, Collective Dynamics 2, 1 (2017).
  * Guo  _et al._ [2012] R. Guo, H. Huang, and S. Wong, Route choice in pedestrian evacuation under conditions of good and zero visibility: Experimental and simulation results, Transportation Research Part B: Methodological 46, 669 (2012).
  * Abdelghany  _et al._ [2014] A. Abdelghany, K. Abdelghany, H. Mahmassani, and W. Alhalabi, Modeling framework for optimal evacuation of large-scale crowded pedestrian facilities, European Journal of Operational Research 237, 1105 (2014).
  * Johnson [1987] N. Johnson, Panic at “The Who concert stampede”: an empirical assessment, Social Problems 3, 362 (1987).
  * Drury  _et al._ [2009] J. Drury, C. Cocking, and S. Reicher, The nature of collective resilience: survivor reactions to the 2005 London bombings, International Journal of Mass Emergencies and Disaster 27, 66 (2009).
  * von Sivers  _et al._ [2014] I. von Sivers, A. Templeton, G. Köster, J. Drury, and A. Philippides, Humans do not always act selfishly: Social identity and helping in emergency evacuation simulation, in  _The Conference on Pedestrian and Evacuation Dynamics 2014 (PED 2014)_, edited by W. Daamen, D. Duives, and S. Hoogendoorn (Delft, The Netherlands, 2014) pp. 585–593.
  * von Sivers  _et al._ [2016] I. von Sivers, A. Templeton, F. Künzner, G. Köster, J. Drury, A. Philippides, T. Neckel, and H. Bungartz, Modelling social identification and helping in evacuation simulation, Safety Science 89, 288 (2016).
  * Bouzat and Kuperman [2014] S. Bouzat and M. Kuperman, Game theory in models of pedestrian room evacuation, Physical Review E 89, 032806 (2014).
  * Shi and Wang [2013] D. Shi and B. Wang, Evacuation of pedestrians from a single room by using snowdrift game theories, Physical Review E 87, 022802 (2013).
  * Heliövaara  _et al._ [2013] S. Heliövaara, H. Ehtamo, D. Helbing, and T. Korhonen, Patient and impatient pedestrians in a spatial game for egress congestion, Physical Review E 87, 012802 (2013).
  * Mitsopoulou  _et al._ [2019] M. Mitsopoulou, N. Dourvas, G. Sirakoulis, and K. Nishinari, Spatial games and memory effects on crowd evacuation behavior with cellular automata, Journal of Computational Science 32, 87 (2019).
  * Hao  _et al._ [2011] Q. Hao, R. Jiang, M. Hu, B. Jia, and Q. Wu, Pedestrian flow dynamics in a lattice gas model coupled with an evolutionary game, Physical Review E 84, 036107 (2011).
  * Kwak  _et al._ [2020] J. Kwak, M. Lees, W. Cai, and M. Ong, Modeling helping behavior in emergency evacuations using volunteer’s dilemma game, in  _Lecture Notes in Computer Science_ , Vol. 12137, edited by V. Krzhizhanovskaya, G. Závodszky, M. Lees, J. Dongarra, P. Sloot, S. Brissos, and J. Teixeira (Amsterdam, The Netherlands, 2020) pp. 513–523.
  * Diekmann [1985] A. Diekmann, Volunteer’s dilemma, Journal of Conflict Resolution 29, 605 (1985).
  * Diekmann and Przepiorka [2016] A. Diekmann and W. Przepiorka, “Take one for the team!” Individual heterogeneity and the emergence of latent norms in a volunteer’s dilemma, Social Forces 94, 1309 (2016).
  * Smaldino  _et al._ [2013] P. Smaldino, J. Schank, and R. McElreath, Increased cost of cooperation help cooperators in the long run, The American Naturalist 181, 451 (2013).
  * Helbing and Johansson [2010] D. Helbing and A. Johansson, Cooperation, norms, and revolutions: a unified game-theoretical approach, PLOS ONE 5, e12530 (2010).
  * Szabo and Szolnoki [2012] G. Szabo and A. Szolnoki, Selfishness, fraternity, and other-regarding preference in spatial evolutionary games, Journal of Theoretical Biology 299, 81 (2012).
  * Cardillo and Masuda [2020] A. Cardillo and N. Masuda, Critical mass effect in evolutionary games triggered by zealots, Physical Review Research 2, 023305 (2020).
  * Grund  _et al._ [2013] T. Grund, C. Waloszek, and D. Helbing, How natural selection can create both self-and other-regarding preferences and networked minds, Scientific Reports 3, 1 (2013).
  * Tricomi  _et al._ [2010] E. Tricomi, A. Rangel, C. Camerer, and J. O’Doherty, Neural evidence for inequality-averse social preferences, Nature 463, 1089 (2010).
  * Szabó and Tőke [1998] G. Szabó and C. Tőke, Evolutionary prisoner’s dilemma game on a square lattice, Physical Review E 58, 69 (1998).
  * Amaral and Javarone [2018] M. Amaral and M. Javarone, Heterogeneous update mechanisms in evolutionary games: mixing innovative and imitative dynamics, Physical Review E 97, 042305 (2018).
  * Wang  _et al._ [2011] W. Wang, Y. Lai, C. Grebogi, and J. Ye, Network reconstruction based on evolutionary-game data via compressive sensing, Physical Review X 1, 021021 (2011).
  * Helbing and Molnár [1995] D. Helbing and P. Molnár, Social force model for pedestrian dynamics, Physical Review E 51, 4282 (1995).
  * Wang and Perc [2010] Z. Wang and M. Perc, Aspiring to the fittest and promotion of cooperation in the prisoner’s dilemma game, Physical Review E 82, 021115 (2010).
  * Wu and Yang [2014] Z. Wu and H. Yang, Social dilemma alleviated by sharing the gains with immediate neighbors, Physical Review E 89, 012109 (2014).
  * Yang  _et al._ [2015] H. Yang, Z. Wu, Z. Rong, and Y. Lai, Peer pressure: Enhancement of cooperation through mutual punishment, Physical Review E 91, 022121 (2015).
  * Woelfing and Traulsen [2009] B. Woelfing and A. Traulsen, Stochastic sampling of interaction partners versus deterministic payoff assignment, Journal of Theoretical Biology 257, 689 (2009).
  * Masuda [2012] N. Masuda, Evolution of cooperation driven by zealots, Scientific Reports 2, 646 (2012).
  * Nakajima and Masuda [2015] Y. Nakajima and N. Masuda, Evolutionary dynamics in finite populations with zealots, Journal of Mathematical Biology 70, 465 (2015).
  * Helbing [2001] D. Helbing, Traffic and related self-driven many-particle systems, Reviews of Modern Physics 73, 1067 (2001).
  * Johansson  _et al._ [2007] A. Johansson, D. Helbing, and P. Shukla, Specification of the social force pedestrian model by evolutionary adjustment to video tracking data, Advances in Complex Systems 10, 271 (2007).
  * Kwak  _et al._ [2017] J. Kwak, H.-H. Jo, T. Luttinen, and I. Kosonen, Jamming transitions induced by an attraction in pedestrian flow, Physical Review E 96, 022319 (2017).
  * Kwak  _et al._ [2013] J. Kwak, H.-H. Jo, T. Luttinen, and I. Kosonen, Collective dynamics of pedestrians interacting with attractions, Physical Review E 88, 062810 (2013).
  * Zanlungo  _et al._ [2011] F. Zanlungo, T. Ikeda, and T. Kanda, Social force model with explicit collision prediction, EPL (Europhysics Letters) 93, 68005 (2011).
  * Zanlungo  _et al._ [2014] F. Zanlungo, T. Ikeda, and T. Kanda, Potential for the dynamics of pedestrians in a socially interacting group, Physical Review E 89, 012811 (2014).


Approximate Discrete Entropy Monotonicity for Log-Concave Sums
Lampros Gavalakis
This project has received funding from the European Union's Horizon 2020 research and innovation program
under the Marie Sklodowska-Curie grant agreement No 101034255.

It is proved that for any $n \geq 1,$ if $X_1,\ldots,X_n$ are i.i.d. integer-valued, log-concave random variables then

h(X_1+\ldots+X_n + U_1+\ldots+U_n) = H(X_1+\ldots+X_n) + o(1),

as $H(X_1) \to \infty$, where $h$ stands for the differential entropy, $H$ dentoes the (discrete) Shannon entropy and $U_1,\ldots,U_n$ are independent continuous uniforms on $(0,1)$. As a corollary, it is shown that a conjecture of Tao (2010) holds true for log-concave random variables on the integers:

H(X_1+\ldots+X_{n+1}) \geq  H(X_1+\cdots+X_{n}) + \frac{1}{2}\log{\Bigl(\frac{n+1}{n}\Bigr)} - o(1)

as $H(X_1) \to \infty$. Explicit bounds for the $o(1)$-terms are provided.

Keywords —
entropy, monotonicity,
log-concavity, entropy power inequality,
central limit theorem, concentration,
sumset inequalities

2020 Mathematics subject classification —
94A17; 60E15

§ INTRODUCTION

§.§ Monotonic Increase of Differential Entropy

Let $X, Y$ be two independent random variables with densities in $\mathbb{R}$. The differential entropy of $X$, having density $f$, is

h(X) = -\int_{\mathbb{R}}{f(x)\log{f(x)}dx}

and similarly for $Y$. Throughout $`\log$' denotes the natural logarithm.

The Entropy Power Inequality (EPI) plays a central role in information theory. It goes back to Shannon [15] and was first proven in full generality by Stam [16].
It asserts that

\begin{equation} \label{EPI}
N(X+Y) \geq N(X) + N(Y),
\end{equation}

where $N(X)$ is the entropy power of $X$:

N(X) = \frac{1}{2 \pi e}e^{2h(X)}.

If $X_1,X_2$ are identically distributed, (<ref>) can be rewritten as

\begin{equation} \label{EPIlogarithmic}
h(X_1+X_2) \geq h(X_1) + \frac{1}{2}\log{2}.
\end{equation}

The EPI is also connected with probability theory, mainly because of the following generalisation due to Artstein et al. [1]: If $\{X_i\}_{i=1}^{n+1}$ are i.i.d. then

\begin{equation} \label{abbn}
h\Bigl(\frac{1}{\sqrt{n+1}}\sum_{i=1}^{n+1}{X_i}\Bigr) \geq h\Bigl(\frac{1}{\sqrt{n}}\sum_{i=1}^{n}{X_i}\Bigr).
\end{equation}

This is the monotonic increase of entropy along the central limit theorem [2].

§.§ Sumset theory for Entropy

There has been interest in formulating discrete analogues of the EPI from various perspectives [7, 8, 9, 20]. It is not hard to see that the exact statement (<ref>) can not hold for all discrete random variables by considering deterministic (or even close to deterministic) random variables.

Suppose $G$ is an additive group and $X$ is a random variable supported on a discrete (finite or countable) subset $A$ of $G$ with probability mass function (p.m.f.) $p$ on $G$.
The Shannon entropy, or simply entropy of $X$ is

\begin{equation} \label{entropynatsequation}
H(X) = -\sum_{x \in A}{p(x)\log{p(x)}}.
\end{equation}

Tao [17] proved that if $G$ is torsion-free and $X$ takes finitely many values then

\begin{equation} \label{taofirststatement}
H(X_1+X_2) \geq H(X_1) + \frac{1}{2}\log{2} - o(1),
\end{equation}

where $X_1, X_2$ are independent copies of $X$ and the $o(1)$-term vanishes as the entropy of $X$ tends to infinity.
That work explores the connection between additive combinatorics and entropy, which was identified by Tao and Vu in the unpublished notes [18] and by Ruzsa [14].
The main idea is that random variables in $G$ may be associated with subsets $A$ of $G$: By the asymptotic equipartition property [4], there is a set $A_n$ (the typical set) such that if $X_1,\ldots,X_n$ are i.i.d. copies of $X$, then $X_1^n$ is approximately uniformly distributed on $A_n$ and $|A_n| = e^{n(H(X) + o(1))}.$ Hence, given an inequality involving cardinalities of sumsets, it is natural to guess that a counterpart statement holds true for random variables if the logarithm of the cardinality is replaced by the entropy.

Exploring this connection, Tao [17] proved an inverse theorem for entropy, which characterises random variables for which the addition of an independent copy does not increase the entropy by much. This is the entropic analogue of the inverse Freiman theorem [19] from additive combinatorics, which characterises sets for which the sumset is not much bigger than the set itself. The discrete EPI (<ref>) is a consequence of the inverse theorem for entropy.

Furthermore, it was conjectured in [17] that for any $n \geq 2$ and $\epsilon > 0$

\begin{equation} \label{taosoriginalconj}
H(X_1+\cdots+X_{n+1}) \geq  H(X_1+\cdots+X_{n}) + \frac{1}{2}\log{\Bigl(\frac{n+1}{n}\Bigr)} - \epsilon,
\end{equation}

provided that $H(X)$ is large enough depending on $n$ and $\epsilon$, where $\{X_i\}_{i=1}^n$ are i.i.d. copies of $X$.

We will prove that the conjecture (<ref>) holds true for log-concave random variables on the integers.
An important step in the proof of (<ref>) is reduction to the continuous setting by approximation of the continuous density with a discrete p.m.f.; we briefly outline these key points from that proof in Section <ref> below as we are going to take a similar approach.

A discrete entropic central limit theorem was recently established in [6]. A discussion relating the above conjecture to the convergence of Shannon entropy to its maximum in analogy with (<ref>) may be found there.

It has also been of interest to establish finite bounds for the $o(1)$-term [7, 20]. Our proofs yield explicit rates for the $o(1)$-terms, which are exponential in $H(X_1)$.

The class of discrete log-concave distributions has been considered recently by Bobkov et al. [3] in connection with the EPI. In particular, discrete analogues of (<ref>) were proved for this class.
In addition, sharp upper and lower bounds on the maximum probability of discrete log-concave random variables in terms of their variance were provided, which we are going to use in the proofs (see Lemma <ref> below). Although log-concavity is a strong assumption in that it implies, for example, connected support set and moments of all orders, many important distributions are log-concave, e.g. Bernoulli, Poisson, geometric, negative binomial and others.

§.§ Main results and proof ideas

The first step in the proof method of <cit.> is to assume that $H(X_1+X_2) \leq H(X_1) + \frac{1}{2}\log{2} - \epsilon.$ Then, because of <cit.>, proving the result for random variables $X$ that can be expressed as a sum $Z+U$, where $Z$ is a random variable with entropy $O(1)$ and $U$ is a uniform on a large arithmetic progression, say $P$, suffices to get a contradiction. Such random variables satisfy, for every $x$,

\begin{equation} \label{taoprobs}
\mathbb{P}(X = x) \leq \frac{C}{|P|}
\end{equation}

for some absolute constant $C$.
Using tools from the theory of sum sets, it is shown that it suffices to consider random variables that take values in a finite subset of the integers. For such random variables that satisfy (<ref>), the smoothness property

\begin{equation} \label{tvproperty}
\|p_{X_1+X_2} - p_{X_1+X_2+1}\|_{\rm TV} \to 0
\end{equation}

as $H(X) \to \infty$ is established, where $p_{X_1+X_2}, p_{X_1+X_2+1}$ are the p.m.f.s of $X_1+X_2$ and $X_1+X_2+1$ respectively and $\|\cdot\|_{\mathrm{TV}}$ is the total variation distance defined in (<ref>) below.
Using this, it is shown that

\begin{equation} \label{introentropyapprox}
h(X_1+X_2+U_1+U_2) = H(X_1+X_2) + o(1),
\end{equation}

as $H(X) \to \infty,$ where $U_1,U_2$ are independent continuous uniforms on $(0,1).$  The EPI for continuous random variables is then invoked.

The tools that we use are rather probabilistic– our proofs lack any additive combinatorial arguments as we already work with random variables on the integers, which have connected support set. An important technical step in our case is to show that any log-concave random variable $X$ on the integers satisfies

\|p_X- p_{X+1}\|_{\rm TV} \to 0

as $H(X) \to \infty$. Using this we show a generalisation of (<ref>), our main result:

Let $n \geq 1$ and suppose $X_1,\ldots,X_n$ are i.i.d. log-concave random variables on the integers with common varianace $\sigma^2.$ Let $U_1,\ldots,U_n$ be continuous i.i.d. uniforms on $(0,1).$ Then

\begin{equation} \label{mainequation}
h(X_1+\cdots+X_n+U_1+\cdots+U_n) = H(X_1+\cdots+X_n) + o(1),
\end{equation}

where the $o(1)$-term vanishes as $\sigma^2 \to \infty$ depending on $n$. In fact, this term can be bounded absolutely by

\begin{equation} \label{nsigmarate}
2^{n+6} e^{-(\sqrt{n}\sigma)^{1/5}} (\sqrt{n}\sigma)^{3} + \frac{2^{n+2}}{\sigma\sqrt{n}}\log(2^{n+2}\sigma\sqrt{n}) +\frac{\log{\ns}}{8\ns},
\end{equation}

provided that $\sigma > \max\{2^{n+2}/\sqrt{n},3^7/\sqrt{n}\}$.

Note that $H(X) \to \infty$ implies $\sigma^2 \to \infty.$ For the class of log-concave random variables these two statements are actually equivalent.

Our main tools are first, to approximate the density of the log-concave sum convolved with the sum of $n$ continuous uniforms with the discrete p.m.f. (Lemma <ref>) and second, to show a type of concentration for the “information density”, $-\log{p(S_n)},$ using Lemma <ref>. It is a standard argument to show that log-concave p.m.f.s have exponential tails, since the sum of the probabilities is convergent. Lemma <ref> is a slight improvement in that it provides a bound for the ratio depending on the variance.

By an application of the generalised EPI for continuous random variables, we show that the conjecture (<ref>) is true for log-concave random variables on the integers, with an explicit dependence between $H(X)$ and $\epsilon:$

Let $n \geq 1$ and $\epsilon > 0$. Suppose $X_1,\ldots,X_n$ are i.i.d. log-concave random variables on the integers. Then if
$H(X_1)$ is sufficiently large depending on $n$ and $\epsilon$,

\begin{equation} \label{mainequation}
H(X_1+\cdots+X_{n+1}) \geq  H(X_1+\cdots+X_{n}) + \frac{1}{2}\log{\Bigl(\frac{n+1}{n}\Bigr)} - \epsilon.
\end{equation}

In fact, for (<ref>) to hold it suffices to take $H(X_1) \geq \log{\frac{2}{\epsilon}} + \log{\log{\frac{2}{\epsilon}}} + n + 27.$

The proofs of Theorem <ref> and Corollary <ref> are given in Section <ref>. Before that, in Section <ref> below, we prove some preliminary facts about discrete, log-concave random variables.

For $n=1,$ the lower bound for $H(X_1)$ given by Corollary <ref> for the case of log-concave random variables on the integers is a significant improvement on the lower bound that can be obtained from the
proof given in [17] for discrete random variables in a torsion free group, which is $\Omega\Bigl({\frac{1}{\epsilon}}^{{\frac{1}{\epsilon}}^{\frac{1}{\epsilon}}}\Bigr)$.

Finally, let us note that Theorem <ref> is a strong result: Although we suspect that the assumption of log-concavity may be relaxed, we do not expect it to hold in much greater generality; we believe that some structural conditions on the random variables should be necessary.

§ NOTATION AND PRELIMINARIES

For a random variable $X$ with p.m.f. p on the integers denote

\begin{equation} \label{qdef}
q := \sum_{k \in \mathbb{Z}}\min\{p(k),p(k+1)\}.
\end{equation}

The parameter $q$ defined above plays an important role in a technique known as Bernoulli part decomposition, which has been used in [5, 12, 13] to prove local limit theorems. It was also used in [6] to prove the discrete entropic CLT mentioned in the Introduction.

In the present article, we use $1-q$ as a measure of smoothness of a p.m.f. on the integers.
In what follows we will also write $q(p)$ to emphasise the dependence on the p.m.f..

For two p.m.f.s on the integers $p_1$ and $p_2$, we use the notation

$$\|p_1 - p_2\|_{1} := \sum_{k \in \mathbb{Z}}{|p_1(k)-p_2(k)|}$$

for the $\ell_1$-distance between $p_1$ and $p_2$ and

\begin{equation} \label{tvdef}
\|p_1 - p_2\|_{\rm TV} := \frac{1}{2}\|p_1 - p_2\|_{1}
\end{equation}

for the total variation distance.

Suppose $X$ has p.m.f. $p_X$ on $\mathbb{Z}$ and let $q = \sum_{k \in \mathbb{Z}}{\min{\{p_X(k),p_X(k+1)\}}}$. Then

$$\|p_X - p_{X+1}\|_{\rm TV} = (1-q).$$

Note first that

\sum_{k \in \mathbb{Z}}{\min{\{p_X(k),p_X(k+1)\}}} + \sum_{k\in \mathbb{Z}}{\max{\{p_X(k),p_X(k+1)\}}} = 2.

\begin{align*}
\|p_X - p_{X+1}\|_{\rm 1}
%&= \sum_{k\in \mathbb{Z}}{|p_X(k) - p_X(k-1)|}\\
&= \sum_{k\in \mathbb{Z}}{|p_X(k) - p_X(k+1)|}\\
&= \sum_{k:p_X(k) > p_X(k+1)}{p_X(k)} - \sum_{k:p_X(k) > p_X(k+1)}{p_X(k+1)} \\
&+ \sum_{k:p_X(k) \leq p_X(k+1)}{p_X(k+1)} - \sum_{k:p_X(k) \leq p_X(k+1)}{p_X(k)} \\
&= \sum_{k\in \mathbb{Z}}{\max{\{p_X(k),p_X(k+1)\}}} - q = 2 - q - q = 2(1-q).
\end{align*}

A consequence of Proposition <ref> is that the parameter $q$, defined in (<ref>), does not decrease on convolution:

Let $p_1,p_2$ be two p.m.f.s on the integers. Then

q(p_1*p_2) \geq \max{\{q(p_1),q(p_2)\}}.

By Proposition <ref> and the convolution inequality for the total variation distance, we have

\begin{align*}
q(p_1*p_2) &= 1 - \|p_{(X_1+X_2)} - p_{(X_1 + X_2 + 1)}\|_{\rm TV} \\
&\geq 1 - \|p_{X_1} -p_{ X_1}\|_{\rm TV} - \|p_{X_2} - p_{(X_2 + 1)}\|_{\rm TV} \\
&= q(p_2)
\end{align*}

and similarly $q(p_1*p_2) \geq q(p_1).$

A p.m.f. $p$ on $\mathbb{Z}$ is called log-concave, if for any $k \in \mathbb{Z}$

\begin{equation} \label{logconcavity}
p(k)^2 \geq p(k-1)p(k+1).
\end{equation}

If a random variable $X$ is distributed according to a log-concave p.m.f. we say that $X$ is log-concave.
Throughout we suppose that $X_1,\ldots,X_n$ are i.i.d. random variables having a log-concave p.m.f. on the integers, $p$, common variance $\sigma^2$ and denote their sum with $S_n$.
Also, we denote

\pmax = \pmax(X) := \sup_k{\mathbb{P}(X = k)}

and write

\begin{equation} \label{Nmaxdef}
\nmax = \nmax(X) := \max\{k \in \mathbb{Z}: p(k) = \pmax\},
\end{equation}

i.e. $\nmax$ is the last $k \in \mathbb{Z}$ for which the maximum probability is achieved.
We will make use of the following bound from [3]:

Suppose $X$ has discrete log-concave distribution with $\sigma^2 = \Var{(X)} \geq 1.$ Then

\begin{equation} \label{bobkovbound}
\frac{1}{4\sigma} \leq \pmax \leq \frac{1}{\sigma}.
\end{equation}

Follows immediately from <cit.>.

Let $X$ be a log-concave random variable on the integers with mean $\mu \in \mathbb{R}$ and variance $\sigma^2$, and let $\delta >0$. Then,
if $\sigma > 4^{1/2\delta},$

\begin{equation} \label{nmaxsigma2bound}
\mu-\sigma^{3/2+\delta}-1 < \nmax< \mu+\sigma^{3/2+\delta} +1
\end{equation}

Suppose for contradiction that $\nmax \geq \mu+\sigma^{3/2+\delta}+1$. Then, using (<ref>),

\mathbb{P}(X > \mu+ \sigma^{3/2+\delta}) \geq p(\nmax) \geq \frac{1}{4\sigma}.

But Chebyshev's inequality implies

\mathbb{P}(X > \mu+ \sigma^{3/2+\delta}) \leq \frac{1}{\sigma^{1 + 2\delta}} < \frac{1}{4\sigma}.

Similarly, $\nmax > \mu-\sigma^{3/2+2\delta}-1.$

Below we show that for any integer-valued random variable, $q \to 1$ implies $H(X) \to \infty$.
It is not hard to see that the converse is not alway true, i.e. $H(X) \to \infty$ does not necessarily imply $q \to 1$: Consider a random variable with a mass of $\frac{1}{2}$ at zero and all other probabilities equal on an increasingly large subset of $\mathbb{Z}$.
Nevertheless, using Lemma <ref>, we show that if $X$ is log-concave this implication is true.

Suppose that the random variable $X$ has p.m.f. $p_X$ on the integers and let $q = q(p_X)$ as above. Then

*  $e^{-H(X)} \leq 1-q.$

*  If $p_X$ is log-concave, then
$1 - q = \pmax \leq \frac{1}{\sigma} .$

For <ref>, recall the definition of $\nmax$. Then we can write

\begin{align*}
q &=\sum_{k < \nmax - 1}{\min{\{p_X(k),p_X(k+1)\}}}  + \sum_{k \geq \nmax + 1}{\min{\{p_X(k),p_X(k+1)\}}} \\
&+ \min{\{p_X(\nmax-1),p_X(\nmax)\}} + \min{\{p_X(\nmax),p_X(\nmax + 1)\}}\\
&= \sum_{k < \nmax - 1}{\min{\{p_X(k),p_X(k+1)\}}}  + \sum_{k \geq \nmax + 1}{\min{\{p_X(k),p_X(k+1)\}}} +p_X(\nmax-1)
+ p_X(\nmax+1)\\
&\leq \sum_{k < \nmax - 1}{p_X(k)}  + \sum_{k \geq \nmax + 1}{p_X(k)} +p_X(\nmax-1) + p_X(\nmax+1)\\
&= 1 - p_X(\nmax).
\end{align*}

The bound <ref> follows since
$H(X) = \mathbb{E}\bigl({\log{\frac{1}{p_X(X)}}\bigr)} \geq \log{\frac{1}{\max_k{p_X(k)}}}.$

For <ref>, note that (<ref>) is equivalent to the sequence $\{\frac{p_X(k+1)}{p_X(k)}\}_{k \in \mathbb{Z}}$ being non-increasing.
Thus, $\frac{p_X(k+1)}{p_X(k)} \geq 1$ for all $k < \nmax$ and $\frac{p_X(k+1)}{p_X(k)} \leq 1$ for all $k \geq \nmax$.
Therefore, we have

\begin{align} \nonumber
q &=\sum_{k < \nmax}{\min{\{p_X(k),p_X(k+1)\}}}  + \sum_{k \geq \nmax}{\min{\{p_X(k),p_X(k+1)\}}} \\ \nonumber
&= \sum_{k < \nmax}{p_X(k)}  + \sum_{k \geq \nmax}{p_X(k+1)} \\ \label{qexprpmax}
&= 1 - p_X(\nmax).
\end{align}

<ref> follows from the upper bound in (<ref>).

§ PROOFS OF THEOREM <REF> AND COROLLARY <REF>

Let $U^{(n)} := \sum_{i=1}^n{U_i},$ where $U_i$ are i.i.d. continuous uniforms on $(0,1).$ Let $f_{S_n+\Un}$ denote the density of $S_n+\Un.$ We approximate $f_{S_n+U^{(n)}}$ with the p.m.f., say $p_{S_n}$, of $S_n$.

We recall that the class of discrete log-concave distributions is closed under convolution [10] and hence the following lemma may be applied to $S_n$.

Let $S$ be a log-concave random variable on the integers with variance $\sigma^2 = \Var{(S)}$ and, for any $n \geq 2,$ denote by $f_{S+U^{(n)}}$ the density of $S + U^{(n)}$ on the real line. Then for any $n \geq 2$, each $k \in \mathbb{Z}$ and $x \in [k,k+1)$,

\begin{equation} \label{densityapprox}
f_{S+\Un}(x) = p_{S}(k) + g(k),
\end{equation}

\begin{equation} \label{gkbounds}
\sum_{\p{k} \in \mathbb{Z}}|g(\p{k})| \leq (2^{n} -2)\frac{1}{\sigma}.
\end{equation}

We proceed by induction on $n$.

For the case $n=2$ we have

f_{S+U^{(2)}}(x) = p_{S}(k) + (1-x+k)(p_{S}(k-1) - p_{S}(k)).

and thus

f_{S+U^{(2)}}(x) = p_{S}(k) + g_2(k),

where, by Propositions <ref> and <ref>.<ref>,

\sum_{\p{k} \in \mathbb{Z}}|g_2(\p{k})| \leq \|p_{X_1 + X_2} - p_{(X_1 + X_2 +1)}\|_{1} \leq \frac{2}{\sigma}.

Next, we have

\begin{align} \nonumber
f_{S+U^{(n+1)}}(x) &= \int_{(0,1)}{f_{S+U^{(n)}}(x-u)du} \\ \label{twointegrals}
&= \int_{(0,1)\cap(x-k-1,x-k)}{f_{S+U^{(n)}}(x-u)du} + \int_{(0,1)\cap(x-k,x-k+1)}{f_{S+U^{(n)}}(x-u)du}.
\end{align}

Using the inductive hypothesis, (<ref>) is equal to

\begin{equation}
\lambda p_S(k) + (1-\lambda) p_S(k-1) + \int_{(0,1)\cap(x-k-1,x-k)}{g_{n}(k,u)du} + \int_{(0,1)\cap(x-k,x-k+1)}{g_n(k-1,u)du}
\end{equation}

for some $\lambda \in (0,1)$, with $g_n(k,u)$ satisfying (<ref>). Thus, we can write

\begin{align} \nonumber
f_{S+U^{(n+1)}}(x) & = p_S(k) + (1-\lambda)(p_S(k-1) - p_S(k)) \\
&+ \int_{(0,1)\cap(x-k-1,x-k)}{g_{n}(k,u)du} + \int_{(0,1)\cap(x-k,x-k+1)}{g_n(k-1,u)du} \\
&= p_S(k) +g_{n+1}(k),
\end{align}

\begin{equation}
\sum_{\p{k} \in \mathbb{Z}}|g_{n+1}(\p{k})| \leq  \frac{2}{\sigma} + 2(2^{n} -2)\frac{1}{\sigma}  = (2^{n+1} - 2)\frac{1}{\sigma}.
\end{equation}

Let $X$ be a log-concave random variable on the integers with p.m.f. $p$, mean zero and variance $\sigma^2,$ and let  $0<\epsilon < 1/2$. If $\sigma \geq \max{\{3^{1/\epsilon},(12e^3)^{1/(1-2\epsilon)}\}},$ there is an $N_0 \in \{\nmax,\ldots,\nmax+2\lceil\sigma^2\rceil\}$ such that, for each $k \geq N_0,$

\begin{equation} \label{exponentiallysmallprobs}
p(k+1) \leq \biggl(1-\frac{1}{\sigma^{2-\epsilon}}\biggr) p(k).
\end{equation}

Similarly, there is an $N_0^- \in \{\nmax-2\lceil\sigma^2\rceil,\ldots,\nmax\}$ such that, for each $k \leq N_0,$

$$p(k-1) \leq \biggl(1-\frac{1}{\sigma^{2-\epsilon}}\biggr) p(k).$$

Let $\theta = (1-\frac{1}{\sigma^{2-\epsilon}}).$ It suffices to show that there is an $N_0 \in \{\nmax,\ldots,\nmax+2\lceil\sigma^2\rceil\}$ such that $p(N_0+1) \leq \theta p(N_0),$ since then, for each $k \geq N_0, \frac{p(k+1)}{p(k)} \leq \frac{p(N_0+1)}{p(N_0)} \leq \theta$ by log-concavity.

Suppose for contradiction that $p(k+1) \geq \theta p(k)$ for each $ k \in \{\nmax,\ldots,\nmax+2\lceil\sigma^2\rceil\}$.
Then, we have, using (<ref>)

\begin{align}
\sigma^2 &= \sum_{-\infty}^{\infty}{k^2p(k)} \geq \sum_{k = \nmax}^{\nmax+2\lceil\sigma^2\rceil}{k^2p(k)} \geq \sum_{k = \nmax}^{\nmax+2\lceil\sigma^2\rceil}{k^2\theta^{k-\nmax}\frac{1}{4\sigma}} \\  \label{nmaxmtheta}
&= \sum_{m=0}^{2\lceil\sigma^2\rceil}(\nmax+m)^2\theta^m\frac{1}{4\sigma} \geq \sum_{m=\max\{0,-\nmax\}}^{2\lceil\sigma^2\rceil}(\nmax+m)^2\theta^m\frac{1}{4\sigma}.
\end{align}

Now we use Proposition <ref> with $\delta >0$ to be chosen later. Thus, the right-hand side of (<ref>) is at least

\begin{align}\nonumber
&\sum_{m=\lceil\sigma^{3/2+\delta}+1\rceil}^{2\lceil\sigma^2\rceil}(\nmax+m)^2\theta^m\frac{1}{4\sigma} \\
&\geq \sum_{m=\lceil\sigma^{3/2+\delta}\rceil+1}^{2\lceil\sigma^2\rceil}(m - \lceil\sigma^{3/2+\delta}\rceil-1)^2\theta^m\frac{1}{4\sigma} \\
&= \sum_{k=0}^{2\lceil\sigma^2\rceil - \lceil\sigma^{3/2+\delta}\rceil-1}k^2\theta^{k+\lceil\sigma^{3/2+\delta}\rceil+1}\frac{1}{4\sigma} \\ \label{suboptimal}
\theta^{\lceil\sigma^{3/2+\delta}\rceil+1}\frac{1}{4\sigma}\sum_{k=1}^{\lceil\sigma^2\rceil -1 }k\theta^{k}  \\  \label{thetasexpr} %%%HERE
&= \frac{\theta^{\lceil\sigma^{3/2+\delta}\rceil+1}}{4\sigma}\Bigl[\theta \frac{1-\theta^{\lceil\sigma^2\rceil}}{(1-\theta)^2} - \lceil\sigma^2\rceil\frac{\theta^{\lceil\sigma^2\rceil}}{(1-\theta)} \Bigr].
\end{align}

Using the elementary bound $(1-x)^y \geq e^{-2xy},$ for $x < \frac{\log{2}}{2},y>0$, we see that

\theta^{\lceil\sigma^{3/2+\delta}\rceil+1} = (1-\frac{1}{\sigma^{2-\epsilon}})^{\lceil\sigma^{3/2+\delta}\rceil+1} \geq e^{-2\frac{\sigma^{3/2+\delta}+2}{\sigma^{2-\epsilon}}} \geq e^{-3},

where the last inequality holds as long as $\epsilon+\delta < 1/2.$ Choosing $\delta = 1/4-\epsilon/2,$ we see that the assumption of Proposition <ref> is satisfied for $\sigma>16^{1/(1-2\epsilon)}$ and thus for $\sigma>(12e^3)^{1/(1-2\epsilon)}$ as well.
Furthermore, using $(1-x)^y \leq e^{-xy}, x,y >0,$ we get $\theta^{\sigma^2} \leq e^{-\sigma^{\epsilon}}.$ Thus, the right-hand side of (<ref>) is at least

\begin{align} \nonumber
&\frac{1}{4e^3\sigma}\Bigl[\Bigl(1-\frac{1}{\sigma^{2-\epsilon}}\Bigr) \bigl(1-e^{-\sigma^{\epsilon}}\bigr)\sigma^{4-2\epsilon} - \sigma^{4-\epsilon}e^{-\sigma^{\epsilon}} - \sigma^{2-\epsilon}e^{-\sigma^{\epsilon}}\Bigr] \\ \nonumber
&\geq \frac{\sigma^{3-2\epsilon}}{4e^3}\Bigl[1-2\frac{\sigma^{\epsilon}}{e^{\sigma^\epsilon}} -\frac{1}{\sigma^{2-\epsilon}}\Bigr] \\ \label{3tothe1overeps}
&> \sigma^2\frac{\sigma^{1-2\epsilon}}{12e^3} \\ \label{geqsigma2}
&\geq \sigma^2,
\end{align}

where (<ref>) holds for $\sigma > 3^{\frac{1}{\epsilon}}$, since then $\frac{\sigma^{\epsilon}}{e^{\sigma^{\epsilon}}} \leq \frac{1}{4}$ and $\sigma^{-2+\epsilon} < \sigma^{-1} < \frac{1}{9}$. Finally, (<ref>) holds for $\sigma > (12e^3)^{\frac{1}{1-2\epsilon}},$ getting the desired contradiction.

For the second part, apply the first part to the log-concave random variable $-X$.

The bound (<ref>) may be improved due to the suboptimal step (<ref>); it is, however, sufficient for our purpose.

We are now ready to give the proof of our main result.

Assume without loss of generality that $X_1$ has zero mean.
Let $F(x) = x\log{\frac{1}{x}}, x>0$ and note that $F(x)$ is non-decreasing for $x \leq 1/e$. As before denote $S_n = \sum_{i=1}^n{X_i},$  $\Un = \sum_{i=1}^n{U_i}$ and let $f_{S_n+\Un}$ be the density of $S_n+\Un$ on the reals. We have

\begin{align} \nonumber
&h(X_1+\cdots+X_n+U_1+\cdots+U_n)\\ \label{sumbreak}
&= \sum_{k \in (-5\ns,5\ns)}{\int_{[k,k+1)}{F(f_{S_n+\Un}(x)) dx}} + \sum_{|k| \geq 5\ns}{\int_{[k,k+1)}{F(f_{S_n+\Un}(x)) dx}}.
\end{align}

First we will show that the “entropy tails", i.e. the second term in (<ref>), vanish as $\sigma^2$ grows large.

For $k \geq 5\ns,$ we have $p_{S_n}(k+1) \leq p_{S_n}(k),$ since by Proposition <ref> applied to the log-concave random variable $S_n$, $\nmax \leq \ns+1$ as long as $\sqrt{n}\sigma>4$.
Thus, proceeding as in the proof of Lemma <ref>, we can show that for $k\geq 5\ns$ and $x \in[k,k+1),$ $f_{S_n+\Un}(x) \leq 2^n\ps(k-n+1)$.
Hence, for

\begin{equation} \label{pmaxsmall}
\sigma > \frac{2^{n}}{\sqrt{n}}e,
\end{equation}

we have

\begin{align}
0 &\leq \sum_{k \geq 5\ns}{\int_{[k,k+1)}{F(f_{S_n+\Un}(x)) dx}} \leq \sum_{k \geq 5\ns}{F\bigl(2^n p_{S_n}(k-n+1)\bigr) } \\ \label{ctsdiscretetails}
&= \sum_{k \geq 5\ns}{2^np_{S_n}(k-n+1)\log{\frac{1}{2^np_{S_n}(k-n+1)}}} \\ \label{thetalemmasigmacondition}
&\leq 2^n\frac{1}{\sqrt{n}\sigma} \sum_{k \geq 5\ns}{\theta^{k-4\nsceil}\log{\frac{\sqrt{n}\sigma}{2^n\theta^{k-4\nsceil}}}} \\
&=  2^n\frac{\log{\frac{1}{\theta}}}{\sqrt{n}\sigma} \sum_{k \geq \ns}{m\theta^{m}} +  2^n\frac{\log{\frac{\sqrt{n}\sigma}{2^n}}}{\sqrt{n}\sigma} \sum_{k \geq \ns}{\theta^{m}}\\
&\leq 2^{n+1} \frac{\log{\sqrt{n}\sigma}}{\sqrt{n}\sigma}     \Bigl[ \frac{\theta^{\nsceil+1}}{(1-\theta)^2} +\nsceil \frac{\theta^{\nsceil}}{1-\theta} +\frac{\theta^{\nsceil}}{1-\theta}      \Bigr] \\
&\leq 2^{n+1} \frac{\log{\sqrt{n}\sigma}}{\sqrt{n}\sigma}e^{-(\sqrt{n}\sigma)^{\epsilon}}  \Bigl[ (\sqrt{n}\sigma)^{4-2\epsilon} + (n\sigma^2+1)(\sqrt{n}\sigma)^{2-\epsilon} + (\sqrt{n}\sigma)^{2-\epsilon}    \Bigr]  \\ %%%%% CHECK THE LAST TWO LINES AGAIN
&\leq 2^{n+3} \frac{\log{\sqrt{n}\sigma}}{\sqrt{n}\sigma}e^{-(\sqrt{n}\sigma)^{\epsilon}} (\sqrt{n}\sigma)^{4-\epsilon} \\ \label{tailfinalbound}
&\leq 2^{n+4} e^{-(\sqrt{n}\sigma)^{1/5}} (\sqrt{n}\sigma)^{3}.
\end{align}

Here (<ref>) holds for

\begin{equation} \label{sigma3tothe7} %%% IS SQRT{N} OK ???
\sqrt{n}\sigma > 3^7
\end{equation}

with $\theta = 1-\frac{1}{(\sqrt{n}\sigma)^{2-\epsilon}}=1-\frac{1}{(\sqrt{n}\sigma)^{9/5}}$, where we have used Lemma <ref> with $\epsilon = 1/5$ (which makes the assumption approximately minimal). In particular, repeated application of (<ref>) yields

$p_{S_n}(k-n+1) \leq \theta^{k-4\nsceil}p_{S_n}\bigl(4\nsceil-n+1\bigr) \leq \frac{\theta^{k-4\nsceil}}{\sqrt{n}\sigma}.$

The left tail can be bounded above by (<ref>) in the same way, using the second part of Lemma <ref>.

On the other hand, the first term in (<ref>) is equal to

\begin{align} \nonumber
& \log{\ns}\mathbb{P}\bigl(S_n+\Un \in  (-5\ns,5\ns)\bigr) \\ \label{minusaddns}
&+ \sum_{k \in  (-5\ns,5\ns)}{\int_{[k,k+1)}{F(f_{S_n+\Un}(x)) - f_{S_n+\Un}(x)\log{\ns}dx}}.
\end{align}

Now we will apply the estimate of Lemma <ref>, which is stated and proved in the Appendix, with $\mu = \frac{1}{\sigma\sqrt{n}}, D = 2^n\sqrt{n}\sigma, M = \ns, a = f_{S_n+\Un}(x)$ and $b=p_{S_n}(k).$
Thus, using Lemma <ref>, we obtain that (<ref>) is equal to

\begin{align} \label{importantterms}
& \log{\ns}\mathbb{P}\bigl(S_n+\Un \in  (-5\ns,5\ns)\bigr)
+ \sum_{k \in  (-5\ns,5\ns)}{F(p_{S_n}(k)) - p_{S_n}(k)\log{\ns}}
\end{align}

plus a term, which can be bounded absolutely by

\begin{align} \label{errorterm}
&\frac{2\log{(\sigma\sqrt{n})}}{\sigma^3n\sqrt{n}} + \sum_k{g(k)}\Bigl(\log{(\sigma\sqrt{n})} + \log(e2^n\sigma\sqrt{n})\Bigr) \\
&\leq \frac{2\log{(\sigma\sqrt{n})}}{\sigma^3n\sqrt{n}} + \frac{2^{n+1}}{\sigma\sqrt{n}}\log(e2^n\sigma\sqrt{n}) \\
&\leq \frac{2^{n+2}}{\sigma\sqrt{n}}\log(2^{n+2}\sigma\sqrt{n}),
\end{align}

where $g(k)$ is given by Lemma <ref> applied to the log-concave random variable $S_n$ and therefore
$\sum_k{g(k)} \leq \frac{2^n}{\sigma\sqrt{n}}.$

Finally, (<ref>) is equal to

\begin{align} \nonumber
&+ \log{\ns}\Bigl[\mathbb{P}\bigl(S_n+\Un \in  (-5\ns,5\ns)\bigr) - \mathbb{P}\bigl(S_n \in  (-5\ns,5\ns)\bigr)\Bigr]  - \sum_{|k| > 5\ns}{F(p_{S_n}(k))},
\end{align}

where the discrete entropy tails, i.e. the last term, can be bounded above in a similar way as the continuous tails (see (<ref>)) by two times the upper bound in (<ref>). Moreover, both probabilities in the brackets can be bounded below crudely, using Chebyshev's inequality, by

\begin{equation} \label{probsbychebs}
\end{equation}

Putting all these together we obtain that

\begin{align}
\bigl|h(S_n+\Un) - H(S_n)\bigr| \leq 2^{n+6} e^{-(\sqrt{n}\sigma)^{1/5}} (\sqrt{n}\sigma)^{3} + \frac{2^{n+2}}{\sigma\sqrt{n}}\log(2^{n+2}\sigma\sqrt{n}) +\frac{\log{\ns}}{8\ns}%%% 2X each tail bound !!!!
\end{align}

as long as $\sigma > \max\{2^{n+2}/\sqrt{n},3^7/\sqrt{n}\}$.

The exponent in (<ref>) can be improved due to the suboptimal step (<ref>) in Lemma <ref>. However, this is only a third-order term and therefore the rate in Theorem <ref> would still be of the same order.

Let $U_1,\ldots,U_n$ be continuous i.i.d. uniforms on $(0,1).$ Then by the generalised entropy power inequality for continuous random variables [1, 11]

\begin{equation}
h\Bigl(\frac{X_1+\cdots+X_{n+1}+U_1+\cdots+U_{n+1}}{\sqrt{n+1}}\Bigr) \geq h\Bigl(\frac{X_1+\cdots+X_{n}+U_1+\cdots+U_{n}}{\sqrt{n}}\Bigr),
\end{equation}

but by the scaling property of differential entropy [4] this is equivalent to

\begin{equation}
h(X_1+\cdots+X_{n+1} + U_1+\cdots+U_{n+1}) \geq  h(X_1+\cdots+X_{n} + U_1+\cdots+U_{n}) + \frac{1}{2}\log{\Bigl(\frac{n+1}{n}\Bigr)}.
\end{equation}

Now, since [4]

\begin{equation} \label{rate2}
H(X_1) = h(X_1 + U_1) \leq \frac{1}{2}\log{(2\pi e(\sigma^2 +1/12))},
\end{equation}

we have $e^{H(X_1)} \leq 6\sigma.$ Thus, if $H(X_1) \geq 26$ then $\sigma > 50^6$ and the error-term in (<ref>) is
at most $ 2^n144\frac{\log{\sqrt{n}\sigma}}{\sigma \sqrt{n}}.$
Hence, taking $H(X_1) \geq \log{\frac{2}{\epsilon}} + \log{\log{\frac{2}{\epsilon}}} + n + 27,$ we have by Theorem <ref>

\begin{equation} \label{rate1}
H(X_1+\cdots+X_{n+1}) \geq  H(X_1+\cdots+X_{n}) + \frac{1}{2}\log{\Bigl(\frac{n+1}{n}\Bigr)} - \epsilon.
\end{equation}

§ AN ELEMENTARY LEMMA

Here we prove the following Taylor-type estimate that we used in the proof of Theorem <ref>. A similar estimate was used in [17].

Let $D, M \geq 1$ and, for $x > 0,$ consider $G(x) = F(x) -x\log{M}$, where $F(x) = -x\log{x}.$
Then, for $0 \leq a,b \leq \frac{D}{M}$ and any $0 < \mu < \frac{1}{e},$
we have the estimate

\begin{equation}
|G(b) - G(a)| \leq  \frac{2\mu}{M}\log{\frac{1}{\mu}} + |b-a|\bigl[\log{\frac{1}{\mu}} + \log{(eD)}\bigr].
\end{equation}

Note that $\p{G}(x) = -\log{x} - 1 - \log{M}$ , which is non-negative for $x < \frac{1}{eM}$.

We will consider two cases separately.

The first case is when either $a < \frac{\mu}{M}$ or $b < \frac{\mu}{M}$. Assume without loss of generality that $a < \frac{\mu}{M}$. Then if $b < \frac{\mu}{M}$ as well, we have $|G(b) - G(a)| \leq G(a) + G(b) \leq \frac{2\mu}{M}\log{\frac{1}{\mu}},$ since then $\p{G} \geq 0$.
On the other hand, if $b \geq \frac{\mu}{M}> a$ then $G(a) \geq a\log{\frac{1}{\mu}}$ and $G(b) \leq b\log{\frac{1}{\mu}}$.

But then, either $G(b) > G(a),$ whence $|G(b) - G(a)| \leq |b-a|\log{\frac{1}{\mu}}$ or $G(b) < G(a),$ whence $|G(b)-G(a)| \leq |b-a|\log{(eD)},$ since we must have $G(a) - G(b) = (a-b)G^{\prime}(\xi),$ for some $\xi \in (\frac{1}{eM},\frac{D}{M}]$.

Thus, in the first case, $|G(b) - G(a)| \leq \frac{2\mu}{M}\log{\frac{1}{\mu}} + |b-a|\bigl[\log{\frac{1}{\mu}} + \log(eD)\bigr]$.

The second case, is when both $a,b \geq  \frac{\mu}{M}$. Then $G(b) - G(a) = (b-a)\p{G}(\xi)$, for some $\frac{D}{M} \geq \xi \geq \mu\frac{1}{M}$.

Since then $|\p{G}(\xi)| \leq \log{\frac{1}{\mu}} + \log{D}+1$,
we have $|G(b) - G(a)| \leq |b-a|(\log{\frac{1}{\mu}} + \log{(eD)})$.

In any case, $|G(b) - G(a)| \leq  \frac{2\mu}{M}\log{\frac{1}{\mu}} + |b-a|\bigl[\log{\frac{1}{\mu}} + \log{(eD)}\bigr].$

§ ACKNOWLEDGEMENTS

The author is indebted to Ioannis Kontoyiannis for many useful suggestions and comments.

[1]
S. Artstein, K. Ball, F. Barthe, and A. Naor, “Solution of Shannon’s
problem on the monotonicity of entropy,” Journal of the American
Mathematical Society, vol. 17, no. 4, pp. 975–982, 2004.

[2]
A. R. Barron, “Entropy and the central limit theorem,” The Annals of
probability, pp. 336–342, 1986.

[3]
S. G. Bobkov, A. Marsiglietti, and J. Melbourne, “Concentration functions and
entropy bounds for discrete log-concave distributions,” Combinatorics,
Probability and Computing, vol. 31, no. 1, pp. 54–72, 2022.

[4]
T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley
Series in Telecommunications and Signal Processing).1em plus 0.5em
minus 0.4emNew York, NY, USA: Wiley-Interscience, 2006.

[5]
B. Davis and D. McDonald, “An elementary proof of the local central limit
theorem,” Journal of Theoretical Probability, vol. 8, no. 3, pp.
693–701, 1995.

[6]
L. Gavalakis and I. Kontoyiannis, “Entropy and the discrete central limit
theorem,” arXiv preprint arXiv:2106.00514, 2021.

[7]
S. Haghighatshoar, E. Abbe, and E. Telatar, “Adaptive sensing using
deterministic partial hadamard matrices,” in 2012 IEEE International
Symposium on Information Theory Proceedings.1em plus 0.5em minus
0.4emIeee, 2012, pp. 1842–1846.

[8]
S. Haghighatshoar, E. Abbe, and I. E. Telatar, “A new entropy power inequality
for integer-valued random variables,” IEEE transactions on information
theory, vol. 60, no. 7, pp. 3787–3796, 2014.

[9]
P. Harremoés, C. Vignat et al., “An entropy power inequality for
the binomial family,” JIPAM. J. Inequal. Pure Appl. Math, vol. 4,
no. 5, p. 93, 2003.

[10]
S. Hoggar, “Chromatic polynomials and logarithmic concavity,” Journal
of Combinatorial Theory, Series B, vol. 16, no. 3, pp. 248–254, 1974.

[11]
M. Madiman and A. Barron, “Generalized entropy power inequalities and
monotonicity properties of information,” IEEE Transactions on
Information Theory, vol. 53, no. 7, pp. 2317–2329, 2007.

[12]
D. R. McDonald, “On local limit theorem for integer-valued random variables,”
Theory of Probability & Its Applications, vol. 24, no. 3, pp.
613–619, 1980.

[13]
J. Mineka, “A criterion for tail events for sums of independent random
variables,” Zeitschrift für Wahrscheinlichkeitstheorie und
Verwandte Gebiete, vol. 25, no. 3, pp. 163–170, 1973.

[14]
I. Z. Ruzsa, “Sumsets and entropy,” Random Structures & Algorithms,
vol. 34, no. 1, pp. 1–10, 2009.

[15]
C. E. Shannon, “A mathematical theory of communication,” The Bell
system technical journal, vol. 27, no. 3, pp. 379–423, 1948.

[16]
A. J. Stam, “Some inequalities satisfied by the quantities of information of
Fisher and Shannon,” Information and Control, vol. 2, no. 2, pp.
101–112, 1959.

[17]
T. Tao, “Sumset and inverse sumset theory for Shannon entropy,”
Combinatorics, Probability and Computing, vol. 19, pp. 603–639, 07

[18]

T. Tao and V. H. Vu, “Entropy methods,” 2005. [Online]. Available:
<http://www.math.ucla.edu/ tao/>

[19]
——, Additive Combinatorics, ser. Cambridge Studies in Advanced
Mathematics.1em plus 0.5em minus 0.4emCambridge University
Press, 2006.

[20]
J. O. Woo and M. Madiman, “A discrete entropy power inequality for uniform
distributions,” in 2015 IEEE International Symposium on Information
Theory (ISIT).1em plus 0.5em minus 0.4emIEEE, 2015, pp.