{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T05:26:12Z","timestamp":1767245172259,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGecom Exch."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>We present generalized secretary problems as a framework for online auctions. Elements, such as potential employees or customers, arrive one by one online. After observing the value derived from an element, but without knowing the values of future elements, the algorithm has to make an irrevocable decision whether to retain the element as part of a solution, or reject it. The way in which the secretary framework differs from traditional online algorithms is that the elements arrive in uniformly random order.<\/jats:p>\n          <jats:p>Many natural online auction scenarios can be cast as generalized secretary problems, by imposing natural restrictions on the feasible sets. For many such settings, we present surprisingly strong constant factor guarantees on the expected value of solutions obtained by online algorithms. The framework is also easily augmented to take into account time-discounted revenue and incentive compatibility. We give an overview of recent results and future research directions.<\/jats:p>","DOI":"10.1145\/1399589.1399596","type":"journal-article","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T13:35:10Z","timestamp":1217943310000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":105,"title":["Online auctions and generalized secretary problems"],"prefix":"10.1145","volume":"7","author":[{"given":"Moshe","family":"Babaioff","sequence":"first","affiliation":[{"name":"Micosoft Research, Silicon Valley"}]},{"given":"Nicole","family":"Immorlica","sequence":"additional","affiliation":[{"name":"Centrum voor Wiskunde en Informatica (CWI) and Northwestern University"}]},{"given":"David","family":"Kempe","sequence":"additional","affiliation":[{"name":"University of Southern California"}]},{"given":"Robert","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Cornell University"}]}],"member":"320","published-online":{"date-parts":[[2008,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"BABAIOFF M. DINITZ M. GUPTA A. IMMORLICA N. AND TALWAR K. 2008. Secretary problems: Weights and discounts.  BABAIOFF M. DINITZ M. GUPTA A. IMMORLICA N. AND TALWAR K. 2008. Secretary problems: Weights and discounts.","DOI":"10.1137\/1.9781611973068.135"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_2"},{"key":"e_1_2_1_3_1","volume-title":"Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"BABAIOFF M.","year":"2007","unstructured":"BABAIOFF , M. , IMMORLICA , N. , AND KLEINBERG , R. 2007 . Matroids, secretary problems, and online mechanisms . In Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007). BABAIOFF, M., IMMORLICA, N., AND KLEINBERG, R. 2007. Matroids, secretary problems, and online mechanisms. In Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)."},{"volume-title":"Online Computation and Competitive Analysis","author":"BORODIN A.","key":"e_1_2_1_4_1","unstructured":"BORODIN , A. AND EL-YANIV , R. 1998. Online Computation and Competitive Analysis . Cambridge University Press . BORODIN, A. AND EL-YANIV, R. 1998. Online Computation and Competitive Analysis. Cambridge University Press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_61"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.15"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_33"},{"key":"e_1_2_1_8_1","unstructured":"DYNKIN E. B. 1963. The optimum choice of the instant for stopping a markov process. Sov. Math. Dokl. 4.  DYNKIN E. B. 1963. The optimum choice of the instant for stopping a markov process. Sov. Math. Dokl. 4 ."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177012493"},{"volume-title":"The dynamic assignment of heterogenous objects: A mechanism design approach. Tech. rep","author":"GERSHKOV A.","key":"e_1_2_1_10_1","unstructured":"GERSHKOV , A. AND MOLDOVANU , B. 2007. The dynamic assignment of heterogenous objects: A mechanism design approach. Tech. rep ., University of Bonn. GERSHKOV, A. AND MOLDOVANU, B. 2007. The dynamic assignment of heterogenous objects: A mechanism design approach. Tech. rep., University of Bonn."},{"key":"e_1_2_1_11_1","first-page":"735","volume-title":"Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA","author":"GOLDBERG A.","year":"2001","unstructured":"GOLDBERG , A. , HARTLINE , J. , AND WRIGHT , A. 2001 . Competitive auctions and digital goods . In Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA 2001). 735 - 744 . GOLDBERG, A., HARTLINE, J., AND WRIGHT, A. 2001. Competitive auctions and digital goods. In Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA 2001). 735-744."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988784"},{"key":"e_1_2_1_13_1","first-page":"630","volume-title":"Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"KLEINBERG R.","year":"2005","unstructured":"KLEINBERG , R. 2005 . A multiple-choice secretary problem with applications to online auctions . In Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005). 630 - 631 . KLEINBERG, R. 2005. A multiple-choice secretary problem with applications to online auctions. In Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005). 630-631."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.46.1.17"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.2307\/2985407"},{"key":"e_1_2_1_16_1","first-page":"179","volume-title":"Proc. 6th ACM-SIAM Symp. on Discrete Algorithms (SODA","author":"LUEKER G.","year":"1995","unstructured":"LUEKER , G. 1995 . Average-case analysis of off-line and on-line knapsack problems . In Proc. 6th ACM-SIAM Symp. on Discrete Algorithms (SODA 1995). 179 - 188 . LUEKER, G. 1995. Average-case analysis of off-line and on-line knapsack problems. In Proc. 6th ACM-SIAM Symp. on Discrete Algorithms (SODA 1995). 179-188."},{"key":"e_1_2_1_17_1","unstructured":"MAHDIAN M. MCAFFEE P. AND PENNOCK D. 2008. The secretary problem with durable employment. personal communication.  MAHDIAN M. MCAFFEE P. AND PENNOCK D. 2008. The secretary problem with durable employment. personal communication."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585758"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875567"},{"volume-title":"Matroid Theory","author":"OXLEY J. G.","key":"e_1_2_1_20_1","unstructured":"OXLEY , J. G. 1992. Matroid Theory . Oxford University Press . OXLEY, J. G. 1992. Matroid Theory. Oxford University Press."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01464274"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"}],"container-title":["ACM SIGecom Exchanges"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1399589.1399596","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1399589.1399596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:53Z","timestamp":1750255073000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1399589.1399596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1145\/1399589.1399596"],"URL":"https:\/\/doi.org\/10.1145\/1399589.1399596","relation":{},"ISSN":["1551-9031"],"issn-type":[{"type":"electronic","value":"1551-9031"}],"subject":[],"published":{"date-parts":[[2008,6]]},"assertion":[{"value":"2008-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}