Individual Fairness in Prophet Inequalities

Individual Fairness in Prophet Inequalities (via Zoom)

Abstract: 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 may indeed 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. We prove an impossibility result showing that there is no prophet inequality with a non-zero factor for either IIF or TIF stopping rules when we further constrain the decision maker to make a hire with probability 1. We finally consider a setting in which the decision maker doesn't know the distributions of candidates' values but has access to a bounded number of independent samples from each distribution. We provide constant-competitive algorithms that satisfy both TIF and IIF, using one sample from each distribution in the offline setting and two samples from each distribution in the online setting.

This is based on joint work, currently under review, with his advisor Robert Kleinberg.

Bio: Makis is a 5th year PhD student at Cornell's CS department being advised by Professor Robert Kleinberg. He is interested broadly in the design of Online and Randomized Algorithms, focusing on problems with applications to Mechanism Design.