Submodular Secretary Problem and Extensions
Online auction is an essence of many modern markets, particularly networked markets, in which information about goods, agents, and outcomes is revealed over a period of time, and the agents must make irrevocable decisions without knowing future information. Optimal stopping theory, especially the cl...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Published: |
2010
|
| Online Access: | http://hdl.handle.net/1721.1/51336 |
| _version_ | 1826192210765283328 |
|---|---|
| author | Zadimoghaddam, Morteza Hajiaghayi, MohammadTaghi Bateni, MohammadHossein |
| author2 | Erik Demaine |
| author_facet | Erik Demaine Zadimoghaddam, Morteza Hajiaghayi, MohammadTaghi Bateni, MohammadHossein |
| author_sort | Zadimoghaddam, Morteza |
| collection | MIT |
| description | Online auction is an essence of many modern markets, particularly networked markets, in which information about goods, agents, and outcomes is revealed over a period of time, and the agents must make irrevocable decisions without knowing future information. Optimal stopping theory, especially the classic "secretary problem", is a powerful tool for analyzing such online scenarios which generally require optimizing an objective function over the input. The secretary problem and its generalization the "multiple-choice secretary problem" were under a thorough study in the literature. In this paper, we consider a very general setting of the latter problem called the "submodular secretary problem", in which the goal is to select k secretaries so as to maximize the expectation of a (not necessarily monotone) submodular function which defines efficiency of the selected secretarial group based on their overlapping skills. We present the first constant-competitive algorithm for this case. In a more general setting in which selected secretaries should form an independent (feasible) set in each of l given matroids as well, we obtain an O(l log^2 r)-competitive algorithm generalizing several previous results, where r is the maximum rank of the matroids. Another generalization is to consider l knapsack constraints instead of the matroid constraints, for which we present an O(l)-competitive algorithm. In a sharp contrast, we show for a more general setting of "subadditive secretary problem, there is no o~(sqrt(n))-competitive algorithm and thus submodular functions are the most general functions to consider for constant competitiveness in our setting. We complement this result by giving a matching O(sqrt(n))-competitive algorithm for the subadditive case. At the end, we consider some special cases of our general setting as well. |
| first_indexed | 2024-09-23T09:07:55Z |
| id | mit-1721.1/51336 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:07:55Z |
| publishDate | 2010 |
| record_format | dspace |
| spelling | mit-1721.1/513362019-04-10T17:06:32Z Submodular Secretary Problem and Extensions Zadimoghaddam, Morteza Hajiaghayi, MohammadTaghi Bateni, MohammadHossein Erik Demaine Theory of Computation Online auction is an essence of many modern markets, particularly networked markets, in which information about goods, agents, and outcomes is revealed over a period of time, and the agents must make irrevocable decisions without knowing future information. Optimal stopping theory, especially the classic "secretary problem", is a powerful tool for analyzing such online scenarios which generally require optimizing an objective function over the input. The secretary problem and its generalization the "multiple-choice secretary problem" were under a thorough study in the literature. In this paper, we consider a very general setting of the latter problem called the "submodular secretary problem", in which the goal is to select k secretaries so as to maximize the expectation of a (not necessarily monotone) submodular function which defines efficiency of the selected secretarial group based on their overlapping skills. We present the first constant-competitive algorithm for this case. In a more general setting in which selected secretaries should form an independent (feasible) set in each of l given matroids as well, we obtain an O(l log^2 r)-competitive algorithm generalizing several previous results, where r is the maximum rank of the matroids. Another generalization is to consider l knapsack constraints instead of the matroid constraints, for which we present an O(l)-competitive algorithm. In a sharp contrast, we show for a more general setting of "subadditive secretary problem, there is no o~(sqrt(n))-competitive algorithm and thus submodular functions are the most general functions to consider for constant competitiveness in our setting. We complement this result by giving a matching O(sqrt(n))-competitive algorithm for the subadditive case. At the end, we consider some special cases of our general setting as well. 2010-02-02T23:30:07Z 2010-02-02T23:30:07Z 2010-02-01 http://hdl.handle.net/1721.1/51336 MIT-CSAIL-TR-2010-002 Creative Commons Attribution 3.0 Unported http://creativecommons.org/licenses/by/3.0/ 19 p. application/pdf |
| spellingShingle | Zadimoghaddam, Morteza Hajiaghayi, MohammadTaghi Bateni, MohammadHossein Submodular Secretary Problem and Extensions |
| title | Submodular Secretary Problem and Extensions |
| title_full | Submodular Secretary Problem and Extensions |
| title_fullStr | Submodular Secretary Problem and Extensions |
| title_full_unstemmed | Submodular Secretary Problem and Extensions |
| title_short | Submodular Secretary Problem and Extensions |
| title_sort | submodular secretary problem and extensions |
| url | http://hdl.handle.net/1721.1/51336 |
| work_keys_str_mv | AT zadimoghaddammorteza submodularsecretaryproblemandextensions AT hajiaghayimohammadtaghi submodularsecretaryproblemandextensions AT batenimohammadhossein submodularsecretaryproblemandextensions |