article

Online auctions and generalized secretary problems

Authors:

Moshe Babaioff,

Nicole Immorlica,

Robert KleinbergAuthors Info & Claims

ACM SIGecom Exchanges, Volume 7, Issue 2

Article No.: 7, Pages 1 - 11

https://doi.org/10.1145/1399589.1399596

Published: 01 June 2008 Publication History

Abstract

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.

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.

References

[1]

BABAIOFF, M., DINITZ, M., GUPTA, A., IMMORLICA, N., AND TALWAR, K. 2008. Secretary problems: Weights and discounts.

[2]

BABAIOFF, M., IMMORLICA, N., KEMPE, D., AND KLEINBERG, R. 2007. A knapsack secretary problem with applications. In Proc. 10th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2007).

Digital Library

[3]

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).

Digital Library

[4]

BORODIN, A. AND EL-YANIV, R. 1998. Online Computation and Competitive Analysis. Cambridge University Press.

Digital Library

[5]

BUCHBINDER, N. AND NAOR, J. 2005. Online primal-dual algorithms for covering and packing problems. In Proc. 13th European Symp. on Algorithms (ESA 2005).

Digital Library

[6]

DEAN, B., GOEMANS, M., AND VONDRÁK, J. 2004. Approximating the stochastic knapsack problem: The benefit of adaptivity. In Proc. 45th IEEE Symp. on Foundations of Computer Science (FOCS 2004). 208-217.

Digital Library

[7]

DIMITROV, N. AND PLAXTON, C. G. 2008. Competitive weighted matching in transversal matroids. In Proc. 35th Intl. Colloq. on Automata, Languages and Programming (ICALP 2008).

Digital Library

[8]

DYNKIN, E. B. 1963. The optimum choice of the instant for stopping a markov process. Sov. Math. Dokl. 4.

[9]

FERGUSON, T. S. 1989. Who solved the secretary problem? Statist. Sci. 4, 3, 282-289.

[10]

GERSHKOV, A. AND MOLDOVANU, B. 2007. The dynamic assignment of heterogenous objects: A mechanism design approach. Tech. rep., University of Bonn.

[11]

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.

Digital Library

[12]

HAJIAGHAYI, M. T., KLEINBERG, R., AND PARKES, D. 2004. Adaptive limited-supply online auctions. In Proc. 5th ACM conference on Electronic commerce. ACM Press, 71-80.

Digital Library

[13]

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.

Digital Library

[14]

KLEYWEGT, A. J. AND PAPASTAVROU, J. D. 1998. The dynamic and stochastic knapsack problem. Operations Research 46, 1, 17-35.

Digital Library

[15]

LINDLEY, D. V. 1961. Dynamic programming and decision theory. Applied Statistics 10, 39-51.

[16]

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.

Digital Library

[17]

MAHDIAN, M., MCAFFEE, P., AND PENNOCK, D. 2008. The secretary problem with durable employment. personal communication.

[18]

MARCHETTI-SPACCAMELA, A. AND VERCELLIS, C. 1995. Stochastic on-line knapsack problems. Mathematical Programming 68, 73-104.

Digital Library

[19]

MEYERSON, A. 2001. Online facility location. In IEEE Symposium on Foundations of Computer Science (FOCS) 2001. 426-431.

Digital Library

[20]

OXLEY, J. G. 1992. Matroid Theory. Oxford University Press.

[21]

RASMUSSEN, W. T. AND PLISKA, S. R. 1975/76. Choosing the maximum from a sequence with a discount function. Appl. Math. Optim. 2, 3, 279-289.

[22]

SPIELMAN, D. AND TENG, S.-H. 2004. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM 51, 385-463.

Digital Library

Cited By

Kesselheim TPsomas AVardi S(2024)Technical Note—On Hiring Secretaries with Stochastic DeparturesOperations Research10.1287/opre.2023.247672:5(2076-2081)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1287/opre.2023.2476
Rios IGhosh P(2024)Competition in Optimal Stopping: Behavioral InsightsManufacturing & Service Operations Management10.1287/msom.2022.062126:6(2256-2273)Online publication date: Nov-2024
https://doi.org/10.1287/msom.2022.0621
Perez-Salazar SSingh MToriello A(2024)Robust Online Selection with Uncertain Offer AcceptanceMathematics of Operations Research10.1287/moor.2023.0210Online publication date: 29-Aug-2024
https://doi.org/10.1287/moor.2023.0210
Show More Cited By

Index Terms

Online auctions and generalized secretary problems

Recommendations

Adaptive limited-supply online auctions
EC '04: Proceedings of the 5th ACM conference on Electronic commerce

We study a limited-supply online auction problem, in which an auctioneer has k goods to sell and bidders arrive and depart dynamically. We suppose that agent valuations are drawn independently from some unknown distribution and construct an adaptive ...
Online learning in online auctions
Special issue: Online algorithms in memoriam, Steve Seiden

We consider the problem of revenue maximization in online auctions, that is, auctions in which bids are received and dealt with one-by-one. In this paper, we demonstrate that results from online learning can be usefully applied in this context, and we ...
On the efficiency of equilibria in generalized second price auctions
EC '11: Proceedings of the 12th ACM conference on Electronic commerce

In sponsored search auctions, advertisers compete for a number of available advertisement slots of different quality. The auctioneer decides the allocation of advertisers to slots using bids provided by them. Since the advertisers may act strategically ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGecom Exchanges

ACM SIGecom Exchanges Volume 7, Issue 2

June 2008

60 pages

EISSN:1551-9031

DOI:10.1145/1399589

Issue’s Table of Contents

Copyright © 2008 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2008

Published in SIGECOM Volume 7, Issue 2

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

135
Total Citations
View Citations
782
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)5

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kesselheim TPsomas AVardi S(2024)Technical Note—On Hiring Secretaries with Stochastic DeparturesOperations Research10.1287/opre.2023.247672:5(2076-2081)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1287/opre.2023.2476
Rios IGhosh P(2024)Competition in Optimal Stopping: Behavioral InsightsManufacturing & Service Operations Management10.1287/msom.2022.062126:6(2256-2273)Online publication date: Nov-2024
https://doi.org/10.1287/msom.2022.0621
Perez-Salazar SSingh MToriello A(2024)Robust Online Selection with Uncertain Offer AcceptanceMathematics of Operations Research10.1287/moor.2023.0210Online publication date: 29-Aug-2024
https://doi.org/10.1287/moor.2023.0210
El Hassouny AEl Bouanani FQaraqe K(2024)Mathematical Modeling and Optimal Stopping Theory-Based Extra Layers for 30-Day Rate Risk Prediction of Readmission to Intensive Care UnitsIEEE Transactions on Artificial Intelligence10.1109/TAI.2023.33301365:6(2723-2738)Online publication date: Jun-2024
https://doi.org/10.1109/TAI.2023.3330136
Chen XHu XWang CWu XZhang M(2024)Algorithms for maximum social welfare of online random tradingDiscrete Applied Mathematics10.1016/j.dam.2023.12.002354(229-240)Online publication date: Sep-2024
https://doi.org/10.1016/j.dam.2023.12.002
Hassin RPuerto J(2024)Pricing heterogeneous products to heterogeneous customers who buy sequentiallyAnnals of Operations Research10.1007/s10479-024-06133-yOnline publication date: 3-Jul-2024
https://doi.org/10.1007/s10479-024-06133-y
Schlag KZapechelnyuk A(2023)Fair Sequential SearchSSRN Electronic Journal10.2139/ssrn.4386194Online publication date: 2023
https://doi.org/10.2139/ssrn.4386194
Kawase Y(2023)STOCHASTIC INPUT MODELS FOR ONLINE COMPUTINGJournal of the Operations Research Society of Japan10.15807/jorsj.66.9566:2(95-111)Online publication date: 30-Apr-2023
https://doi.org/10.15807/jorsj.66.95
Ivashko ASafonov G(2023)Machine Learning Model for Determination of the Optimal Strategy in an Online AuctionМодель машинного обучения для определения оптимальной стратегии в онлайн-аукционеInformatics and AutomationИнформатика и автоматизация10.15622/ia.22.1.622:1(146-167)Online publication date: 27-Jan-2023
https://doi.org/10.15622/ia.22.1.6
Mishra PMoustafa A(2023)Reinforcement learning based monotonic policy for online resource allocationFuture Generation Computer Systems10.1016/j.future.2021.09.023138:C(313-327)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.future.2021.09.023
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents