  Prophet inequalities are performance guarantees for online algorithms (a.k.a.
stopping rules) solving the following "hiring problem": a decision maker
sequentially inspects candidates whose values are independent random numbers
and is asked to hire at most one candidate by selecting it before inspecting
the values of future candidates in the sequence. A classic result in optimal
stopping theory asserts that there exist stopping rules guaranteeing that the
decision maker will hire a candidate whose expected value is at least half as
good as the expected value of the candidate hired by a "prophet", i.e. one who
has simultaneous access to the realizations of all candidates' values.
  Such stopping rules have provably good performance but might treat individual
candidates unfairly in a number of different ways. In this work we identify two
types of individual fairness that might be desirable in optimal stopping
problems. We call them identity-independent fairness (IIF) and time-independent
fairness (TIF) and give precise definitions in the context of the hiring
problem. We give polynomial-time algorithms for finding the optimal IIF/TIF
stopping rules for a given instance with discrete support and we manage to
recover a prophet inequality with factor $1/2$ when the decision maker's
stopping rule is required to satisfy both fairness properties while the prophet
is unconstrained. We also explore worst-case ratios between optimal selection
rules in the presence vs. absence of individual fairness constraints, in both
the online and offline settings. Finally, we consider a framework in which the
decision maker doesn't know the distributions of candidates' values but has
access to independent samples from each distribution. We provide
constant-competitive IIF/TIF algorithms using one sample per distribution in
the offline setting and two samples per distribution in the online setting.
