More Web Proxy on the site http://driver.im/

research-article

Hiring a secretary from a poset

Authors:

Silvio Lattanzi,

Sergei Vassilvitskii,

Andrea VattaniAuthors Info & Claims

EC '11: Proceedings of the 12th ACM conference on Electronic commerce

Pages 39 - 48

https://doi.org/10.1145/1993574.1993582

Published: 05 June 2011 Publication History

Abstract

The secretary problem lies at the core of mechanism design for online auctions. In this work we study the generalization of the classical secretary problem in a setting where there is only a partial order between the elements and the goal of the algorithm is to return one of the maximal elements of the poset. This is equivalent to the auction setting where the seller has a multidimensional objective function with only a partial order among the outcomes. We obtain an algorithm that succeeds with probability at least k^-k/(k-1)((1 + log k^1/(k-1))^k - 1), where k is the number of maximal elements in the poset and is the only information about the poset that is known to the algorithm; the success probability approaches the classical bound of 1/e as k -> 1. On the other hand, we prove an almost matching upper bound of k^-1/(k-1) on the success probability of any algorithm for this problem; this upper bound holds even if the algorithm knows the complete structure of the poset.

References

[1]

M. Ajtai, N. Megiddo, and O. Waarts. Improved algorithms and analysis for secretary problems and generalizations. SIAM J. Discrete Math., 14(1):1--27, 2001.

Digital Library

[2]

M. Babaioff, M. Dinitz, A. Gupta, N. Immorlica, and K. Talwar. Secretary problems: Weights and discounts. In Proc. 20th SODA, pages 1245--1254, 2009.

Digital Library

[3]

M. Babaioff, N. Immorlica, and R. Kleinberg. Matroids, secretary problems, and online mechanisms. In Proc. 18th SODA, pages 434--443, 2007.

Digital Library

[4]

Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Online auctions and generalized secretary problems. SIGecom Exchanges, 7(2), 2008.

Digital Library

[5]

F. T. Bruss. Sum the odds to one and stop. Annals of Probability, 28:1384--1391, 2000.

[6]

N. Buchbinder, K. Jain, and M. Singh. Secretary problems via linear programming. In Proc. 14th IPCO, pages 163--176, 2010.

Digital Library

[7]

E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. Sov. Math. Dokl., 4:627--629, 1963.

[8]

T. Ferguson. Who solved the secretary problem. Statist. Sc., 4:282--296, 1989.

[9]

R. Freij and J. Wästlund. Partially ordered secretaries. Electronic Communication in Probability, 15:504--507, 2010.

[10]

N. Georgiou, M. Kuchta, M. Morayne, and J. Niemiec. On a universal best choice algorithm for partially ordered sets. Random Struct. Algorithms, 32(3):263--273, 2008.

Digital Library

[11]

A. V. Gnedin. Multicriteria extensions of the best choice problem: Sequential selection without linear order. Contemp. Math, 125:153--172, 1992.

[12]

A. Gupta, A. Roth, G. Schoenebeck, and K. Talwar. Constrained non-monotone submodular maximization: Offline and secretary algorithms. In Proc. 6th WINE, pages 246--257, 2010.

Digital Library

[13]

M. T. Hajiaghayi, R. Kleinberg, and D. C. Parkes. Adaptive limited-supply online auctions. In Proc. 5th EC, pages 71--80, 2004.

Digital Library

[14]

R. Kleinberg. A multiple-choice secretary problem with applications to online auctions. In Proc. 16th SODA, pages 630--631, 2005.

Digital Library

[15]

J. Kozik. Dynamic threshold strategy for universal best choice problem. In Proc. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms, pages 439--452, 2010.

[16]

G. Kubicki, J. Lehel, and M. Morayne. A ratio inequality for binary trees and the best secretary. Combinatorics, Probability, and Computing, 11:146--161, 2002.

Digital Library

[17]

M. Zadimoghaddam M. H. Bateni, M. T. Hajiaghayi. Submodular secretary problem and extensions. In Proc. 6th WINE, pages 39--52, 2010.

Digital Library

[18]

M. Morayne. Partial-order analogue of the secretary problem; the binary tree case. Discrete Math, 184:165--181, 1998.

Digital Library

[19]

J. Preater. The best-choice problem for partially ordered objects. Oper. Res. Lett, 25:187--190, 1999.

Digital Library

[20]

J. A. Soto. Matroid secretary problem in the random assignment model. In Proc. 22nd SODA, pages 1275--1284, 2011.

Digital Library

Cited By

Assadi SBalkanski ELeme RWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Secretary ranking with minimal inversionsProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3454382(1051-1063)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3454382
Babaioff MImmorlica NKempe DKleinberg R(2018)Matroid Secretary ProblemsJournal of the ACM10.1145/321251265:6(1-26)Online publication date: 19-Nov-2018
https://dl.acm.org/doi/10.1145/3212512
Kaźmierczak W(2016)The best choice problem for posets; colored complete binary treesJournal of Combinatorial Optimization10.1007/s10878-014-9705-531:1(13-28)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1007/s10878-014-9705-5
Show More Cited By

Index Terms

Hiring a secretary from a poset
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Beyond matroids: secretary problem and prophet inequality with general constraints
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

We study generalizations of the ``Prophet Inequality'' and ``Secretary Problem'', where the algorithm is restricted to an arbitrary downward-closed set system. For 0,1 values, we give O(n)-competitive algorithms for both problems. This is close to the ...
A simple O(log log(rank))-competitive algorithm for the matroid secretary problem
SODA '15: Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms

Only recently progress has been made in obtaining o(log(rank))-competitive algorithms for the matroid secretary problem. More precisely Chakraborty and Lachish (2012) presented a O([EQUATION]log(rank))-competitive procedure, and Lachish (2014) recently ...
A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem

Only recently, progress has been made in obtaining o(log(rank))-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a O((log(rank))^1/2)-competitive procedure, and Lachish (2014) later ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '11: Proceedings of the 12th ACM conference on Electronic commerce

June 2011

384 pages

ISBN:9781450302616

DOI:10.1145/1993574

General Chair:
Yoav Shoham
Stanford University, USA
,
Program Chairs:
Yan Chen
University of Michigan, USA
,
Tim Roughgarden
Stanford University, USA

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '11

Sponsor:

SIGecom

EC '11: ACM Conference on Electronic Commerce

June 5 - 9, 2011

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
207
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Assadi SBalkanski ELeme RWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Secretary ranking with minimal inversionsProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3454382(1051-1063)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3454382
Babaioff MImmorlica NKempe DKleinberg R(2018)Matroid Secretary ProblemsJournal of the ACM10.1145/321251265:6(1-26)Online publication date: 19-Nov-2018
https://dl.acm.org/doi/10.1145/3212512
Kaźmierczak W(2016)The best choice problem for posets; colored complete binary treesJournal of Combinatorial Optimization10.1007/s10878-014-9705-531:1(13-28)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1007/s10878-014-9705-5
Buchbinder NJain KSingh M(2014)Secretary Problems via Linear ProgrammingMathematics of Operations Research10.1287/moor.2013.060439:1(190-206)Online publication date: Feb-2014
https://doi.org/10.1287/moor.2013.0604
Sun XZhang JZhang J(2014)Solving Multi-choice Secretary Problem in Parallel: An Optimal Observation-Selection ProtocolAlgorithms and Computation10.1007/978-3-319-13075-0_52(661-673)Online publication date: 8-Nov-2014
https://doi.org/10.1007/978-3-319-13075-0_52
Kamierczak W(2013)The best choice problem for a union of two linear orders with common maximumDiscrete Applied Mathematics10.1016/j.dam.2013.06.026161:18(3090-3096)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1016/j.dam.2013.06.026
Feldman MTennenholtz MFaltings BLeyton-Brown KIpeirotis P(2012)Interviewing secretaries in parallelProceedings of the 13th ACM Conference on Electronic Commerce10.1145/2229012.2229053(550-567)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.1145/2229012.2229053
Sulkowska M(2012)The best choice problem for upward directed graphsDiscrete Optimization10.1016/j.disopt.2012.04.0019:3(200-204)Online publication date: Aug-2012
https://doi.org/10.1016/j.disopt.2012.04.001
Garrod BMorris R(2012)The secretary problem on an unknown posetRandom Structures & Algorithms10.1002/rsa.2046643:4(429-451)Online publication date: 5-Nov-2012
https://doi.org/10.1002/rsa.20466
Salem JGupta S(undefined)Closing the GAP: Group-Aware Parallelization for Online Selection of Candidates with Biased EvaluationsSSRN Electronic Journal10.2139/ssrn.3444283
https://doi.org/10.2139/ssrn.3444283

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 Table of Contents