{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,25]],"date-time":"2026-05-25T09:04:23Z","timestamp":1779699863845,"version":"3.53.1"},"reference-count":40,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>Fairness in Online Selection Problems<\/jats:p>\n                  <jats:p>Two of the most studied models in online decision making are the secretary problem and the prophet inequality problem. Both capture the challenge of making irrevocable choices under uncertainty. But, what happens when candidates come from different groups and fairness enters the picture? In \u201cFairness and bias in online selection,\u201d Jos\u00e9 Correa, Andr\u00e9s Cristi, Paul D\u00fctting, and Ashkan Norouzi-Fard introduce and analyze multicolor variants of these problems. In these models, each candidate belongs to a \u201ccolor,\u201d and comparisons are only meaningful within the same color. This captures real-world situations where crossgroup rankings are unreliable or biased\u2014for instance, when evaluating students from different schools or job applicants from diverse backgrounds. For the multicolor secretary problem, the authors characterize the optimal online algorithm. In contrast to the offline optimum\u2014which always selects from the most promising group\u2014the optimal online algorithm is inherently fairer. For the multicolor prophet inequality, they design algorithms that enforce target selection probabilities across groups, ensuring equitable treatment.<\/jats:p>","DOI":"10.1287\/opre.2021.0662","type":"journal-article","created":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T18:34:57Z","timestamp":1758738897000},"page":"1539-1561","source":"Crossref","is-referenced-by-count":0,"title":["Fairness and Bias in Online Selection"],"prefix":"10.1287","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3012-7622","authenticated-orcid":false,"given":"Jos\u00e9","family":"Correa","sequence":"first","affiliation":[{"name":"Departamento de Ingenieria Industrial, Universidad de Chile, Santiago 8370439, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1227-2092","authenticated-orcid":false,"given":"Andr\u00e9s","family":"Cristi","sequence":"additional","affiliation":[{"name":"College of Management of Technology, Ecole Polytechnique F\u00e9d\u00e9rale de Laussane, 1015 Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0635-6812","authenticated-orcid":false,"given":"Paul","family":"D\u00fctting","sequence":"additional","affiliation":[{"name":"Google Research, 8002 Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2336-9826","authenticated-orcid":false,"given":"Ashkan","family":"Norouzi-Fard","sequence":"additional","affiliation":[{"name":"Google Research, 8002 Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1137\/120878422"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2015.2377"},{"key":"B3","doi-asserted-by":"crossref","unstructured":"Arsenis M, Kleinberg R (2022) Individual fairness in prophet inequalities.\n                      Proc. 23rd ACM Conf. Econom. Comput. (EC)\n                      (ACM, New York), 245.","DOI":"10.1145\/3490486.3538301"},{"key":"B4","doi-asserted-by":"crossref","unstructured":"Azar P, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information.\n                      Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA)\n                      (SIAM, Philadelphia).","DOI":"10.1137\/1.9781611973402.100"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1145\/3212512"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.7208\/chicago\/9780226041049.001.0001"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1287\/deca.2014.0298"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0604"},{"key":"B9","volume-title":"Great Expectations: The Theory of Optimal Stopping","author":"Chow YS","year":"1971"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1167"},{"key":"B11","doi-asserted-by":"crossref","unstructured":"Correa J, Cristi A, Feuilloley L, Oosterwijk T, Tsigonias-Dimitriadis A (2021a) The secretary problem with independent sampling.\n                      Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA)\n                      (SIAM, Philadelphia).","DOI":"10.1137\/1.9781611976465.122"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2020.1105"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1037\/0033-2909.95.1.134"},{"key":"B14","doi-asserted-by":"crossref","unstructured":"D\u00fctting P, Kesselheim T, Lucier B (2020a) An\n                      O\n                      (log log\n                      m\n                      ) prophet inequality for subadditive combinatorial auctions.\n                      Proc. IEEE Sympos. Foundations Comput. Sci. (FOCS)\n                      (SIAM, Philadelphia), 306\u2013317.","DOI":"10.1109\/FOCS46700.2020.00037"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323850"},{"key":"B16","doi-asserted-by":"crossref","unstructured":"D\u00fctting P, Lattanzi S, Paes Leme R, Vassilvitskii S (2021) Secretaries with advice.\n                      Proc. 22nd ACM Conf. Econom. Comput. (EC)\n                      (ACM, New York), 409\u2013429.","DOI":"10.1145\/3465456.3467623"},{"key":"B17","doi-asserted-by":"crossref","unstructured":"Dwork C, McSherry F, Nissim K, Smith A (2006) Calibrating noise to sensitivity in private data analysis.\n                      Proc. Theory Cryptography Conf. (TCC)\n                      (Springer, Berlin, Heidelberg), 265\u2013284.","DOI":"10.1007\/11681878_14"},{"key":"B18","doi-asserted-by":"crossref","unstructured":"Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids.\n                      Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA)\n                      (SIAM, Philadelphia), 700\u2013714.","DOI":"10.1137\/1.9781611975031.46"},{"key":"B19","doi-asserted-by":"crossref","unstructured":"Ezra T, Feldman M, Gravin N, Tang ZG (2020) Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models.\n                      Proc. ACM Conf. Econom. Comput. (EC)\n                      (ACM, New York), 769\u2013787.","DOI":"10.1145\/3391403.3399513"},{"key":"B20","doi-asserted-by":"crossref","unstructured":"Feldman M, Tennenholtz M (2012) Interviewing secretaries in parallel.\n                      Proc. ACM Conf. Electronic Commerce (EC)\n                      (ACM, New York), 550\u2013567.","DOI":"10.1145\/2229012.2229053"},{"key":"B21","doi-asserted-by":"crossref","unstructured":"Feldman M, Gravin N, Lucier B (2015a) Combinatorial auctions via posted prices.\n                      Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA)\n                      (SIAM, Philadelphia), 123\u2013135.","DOI":"10.1137\/1.9781611973730.10"},{"key":"B22","doi-asserted-by":"crossref","unstructured":"Feldman M, Svensson O, Zenklusen R (2015b) A simple\n                      O\n                      (log log(rank))-competitive algorithm for the matroid secretary problem.\n                      Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA)\n                      (SIAM, Philadelphia), 1189\u20131201.","DOI":"10.1137\/1.9781611973730.79"},{"key":"B23","doi-asserted-by":"crossref","unstructured":"Feldman M, Svensson O, Zenklusen R (2016) Online contention resolution schemes.\n                      Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA)\n                      (SIAM, Philadelphia), 1014\u20131033.","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20192"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1966.10502008"},{"key":"B26","doi-asserted-by":"crossref","unstructured":"Gravin N, Wang H (2019) Prophet inequality for bipartite matching: Merits of being simple and non adaptive.\n                      Proc. ACM Conf. Econom. Comput. (EC)\n                      (ACM, New York), 93\u2013109.","DOI":"10.1145\/3328526.3329604"},{"key":"B27","unstructured":"Joseph M, Kearns M, Morgenstern JH, Roth A (2016) Fairness in learning: Classic and contextual bandits.\n                      Proc. Conf. Neural Inform. Processing Systems (NIPS)\n                      (Curran Associates Inc., Red Hook, NY), 325\u2013333."},{"key":"B28","doi-asserted-by":"crossref","unstructured":"Kaplan H, Naori D, Raz D (2020) Competitive analysis with a sample and the secretary problem.\n                      Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA)\n                      (SIAM, Philadelphia), 2082\u20132095.","DOI":"10.1137\/1.9781611975994.128"},{"key":"B29","volume-title":"The Ethical Algorithm: The Science of Socially Aware Algorithm Design","author":"Kearns M","year":"2019"},{"key":"B30","doi-asserted-by":"crossref","unstructured":"Kesselheim T, Radke K, T\u00f6nnis A, V\u00f6cking B (2013) An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions.\n                      Proc. Eur. Sympos. Algorithms (ESA)\n                      (Springer, Berlin, Heidelberg), 589\u2013600.","DOI":"10.1007\/978-3-642-40450-4_50"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1287\/stsy.2018.0017"},{"key":"B32","doi-asserted-by":"crossref","unstructured":"Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities.\n                      Proc. ACM Sympos. Theory Comput. Conf. (STOC)\n                      (ACM, New York), 123\u2013136.","DOI":"10.1145\/2213977.2213991"},{"key":"B33","doi-asserted-by":"crossref","unstructured":"Kumar R, Lattanzi S, Vassilvitskii S, Vattani A (2011) Hiring a secretary from a poset.\n                      Proc. ACM Conf. Electronic Commerce (EC)\n                      (ACM, New York), 39\u201348.","DOI":"10.1145\/1993574.1993582"},{"key":"B34","unstructured":"Lee E, Singla S (2018) Optimal online contention resolution schemes via ex-ante prophet inequalities.\n                      Proc. Eur. Sympos. Algorithms (ESA)\n                      , vol. 57 (Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 1\u201314."},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2013.1244"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(99)00053-X"},{"key":"B37","unstructured":"Rubinstein A, Wang JZ, Weinberg SM (2020) Optimal single-choice prophet inequalities from samples.\n                      Proc. Innovations Theoret. Comput. Sci. (ITCS)\n                      (Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 60:1\u201360:10."},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2023.4926"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993150"},{"key":"B40","volume-title":"Affirmative Action Around the World: An Empirical Study","author":"Sowell T","year":"2004"}],"container-title":["Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/opre.2021.0662","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,25]],"date-time":"2026-05-25T08:18:10Z","timestamp":1779697090000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/opre.2021.0662"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/opre.2021.0662"],"URL":"https:\/\/doi.org\/10.1287\/opre.2021.0662","relation":{},"ISSN":["0030-364X","1526-5463"],"issn-type":[{"value":"0030-364X","type":"print"},{"value":"1526-5463","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}