The Submodular Secretary Problem: Tight 1-1/e for Monotone Objectives, and Strictly Between 1/e and 1/2 in General
summary
The gist
The paper addresses the submodular secretary problem with a cardinality constraint, where n elements arrive in a uniformly random order…
In short
The paper studies selecting at most $k$ items from $n$ arriving elements to maximize a submodular function. It finds that for monotone objectives, the optimal competitive ratio is exactly $1 - 1/e$. For general objectives, the best achievable ratio lies strictly between $1/e$ and approximately 0.497053, showing limitations imposed by non-monotonicity.
Key concepts
- Submodular Secretary Problem with Cardinality Constraint
- This problem involves a sequence of $n$ items arriving randomly. The goal is to select at most $k$ items from this sequence to maximize the total value derived from them, where the value function exhibits submodularity. Each item must be accepted or rejected irrevocably.
- Monotone Objectives
- In this context, a monotone objective means that adding more items to a chosen set never decreases the total value. This property simplifies analysis significantly, allowing for an exact competitive ratio of $1 - 1/e$ as $k$ grows.
- Eligibility Attenuation (AttenuatedPricing)
- This is a specific algorithmic technique where an element passing a price test at time $t$ is accepted with probability $e - au$. Here, $ au$ represents the total time during which that element could have passed. This mechanism precisely controls the probability of having already selected an item.
- Competitive Ratio ($ ho_k$)
- The competitive ratio measures how close an algorithm's performance is to the optimal solution. A ratio of $1/e$ means the algorithm achieves at least that fraction of the optimal value. The paper shows this ratio depends heavily on whether the objective is monotone or general.
Terminology used across episodes
This episode discusses
- The Submodular Secretary Problem: Tight 1-1/e for Monotone Objectives, and Strictly Between 1/e and 1/2 in General · Paper Radio
- As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single-Sample Matroid Prophet · Paper Radio
- An improved algorithm for the submodular secretary problem with a cardinality constraint
- Cardinality constrained submodular maximization for random streams
- Improved Submodular Secretary Problem with Shortlists
The paper
The Submodular Secretary Problem: Tight 1-1/e for Monotone Objectives, and Strictly Between 1/e and 1/2 in General · Read on arXiv
Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Danny Mittal
University of Maryland, College Park
In the submodular secretary problem with a cardinality constraint, n elements arrive in uniformly random order, and an algorithm must irrevocably accept or reject each one on arrival so as to maximize a nonnegative submodular function over sets of at most k elements. For monotone objectives we settle the problem: the optimal competitive ratio tends to exactly 1-1/e as k to infinity, and its worst case over all budgets k is exactly 1/e. The bound 1-1/e cannot be exceeded even with unlimited computation, and it is achieved by a single algorithm with at most 4n+1 value queries; previously the best ratio without a shortlist was 1/e-o(1), with exponentially many queries. For general objectives, where the best known ratio was about 0.107, we show that the optimal limiting ratio lies strictly between 1/e and 1/2: we achieve 1/e+3.5 times10-6 for large k, and no algorithm achieves more than 0.497053. We also achieve 0.2677 at every budget. The main new ingredient of our algorithm is eligibility attenuation: an element that passes the price test at time t is accepted with probability e-τ, where τ is the total earlier time during which it would have passed, which makes the probability that it has already been selected exactly 1-e-τ.
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "The Submodular Secretary Problem".
Jane: Here's the gist of the paper. The paper addresses the submodular secretary problem with a cardinality constraint, where n elements arrive in a uniformly random order, and an algorithm must irrevocably accept or reject each element to maximize a non-negative submodular function over sets of at most k elements.
Tom: For monotone objectives, the optimal competitive ratio converges exactly to 1 - 1/e as k to infinity, and the worst-case ratio over all budgets is exactly 1/e.
Jane: This bound is achievable by a single algorithm using at most 4n + 1 value queries.
Tom: For general objectives, where previous best results were around 0.107, the optimal limiting ratio lies strictly between 1/e and 1/2.
Title and authors: Tom: So we're looking at this paper today called "The Submodular Secretary Problem: Tight one-one/e for Monotone Objectives, and Strictly Between one/e and one/two in General <ref:2611.17292#pg1,The Submodular Secretary Problem: Tight 1-1/e for Monotone Objectives, and>." It tackles this problem where you get n elements one by one, and you have to pick the best ones up to a budget of k. The title is pretty precise about what it does with monotone functions versus general ones.
Jane: That's right, Tom. And what's interesting is that for monotone objectives, they settle the problem completely: the best possible competitive ratio goes exactly to one minus one over e as the budget k gets bigger than infinity. But for general objectives, things are a bit more nuanced because the ratio stays strictly between one over e and zero point five as k grows.
Lu: The paper sets up a lot of hard limits here. For monotone functions, they find that even with unlimited computation, you can't do better than one minus one over e in the long run, and this worst case is reached when you only have a budget of k equals one. But for general functions, they show that the optimal limit isn't zero point five; it's somewhere right above one over e.
Meng: From my side, I’m curious about how much computation we need to actually achieve those bounds. The paper mentions that for monotone objectives, you can get that one minus one over e ratio with at most four n plus one value queries, which sounds pretty efficient for a complex problem like this. But what about when the functions are general?
Lalam: For the general case, they show an algorithm exists that only needs to know n and k and makes polynomially many value queries, and this gives a ratio of at least one over e plus three point five times ten to the negative six for any non-negative function when k is large enough. This is a big improvement over previous results which were way worse.
Tom: That's a tiny constant improvement, but it's still a concrete number that gives us something to work with for general cases. Jane, how does that compare to what we used to think was possible before this paper?
Jane: Before this paper, the best known ratios for general objectives were hovering around zero point one zero seven for the limit when k was large. This new result shows that the optimal limit is strictly between one over e and zero point five, which is a significant gap in our understanding of what's achievable.
Lu: The authors also found a specific ratio they can guarantee at every budget level k, which is zero point two six seven seven when k equals twenty-six or so. That shows that even for small budgets, there's a solid floor we can expect, rather than just relying on asymptotic limits.
Title and authors: Meng: That floor sounds more practical for deployment because it gives you a guarantee across all scales of your budget constraint. But what about the practical cost of getting that zero point two six seven seven ratio in real-world scenarios? Is it feasible to run that kind of algorithm when the input size n is really massive?
Lalam: The paper mentions a specific algorithm called eligibility attenuation, which is a key part of their method, and they show it can get close to one over e for large budgets k. This mechanism involves accepting an element based on whether it passed a price test at an earlier time and how long ago that was.
Tom: Eligibility attenuation sounds like a sophisticated way to handle the online decision-making process under these constraints. So, if you're driving and you see something interesting, this algorithm tries to figure out if it's better than what you already saw without having to look at everything again.
Jane: Exactly. And when we look at the specific mechanism they describe in eligibility attenuation, it ensures that the probability of an element already being selected is exactly one minus e minus tau, where tau is the total time during which it would have passed before. That sounds like a very tight probabilistic control over acceptance decisions.
Lu: What I find compelling about their approach for general objectives is how they distinguish between monotone and general functions, showing that attenuation isn't even necessary for monotone objectives because the ratio there is determined exactly by that offline benchmark of one minus e plus or minus a small term.
Meng: That makes sense. If the structure of the function doesn't change, you don't need this complex probabilistic mechanism to get near optimal performance; it’s more deterministic. But when things get general, the non-monotonic parts are what force us into that gap between one over e and zero point five.
Lalam: And they found that for general objectives, no algorithm can actually achieve a ratio better than approximately zero point four nine seven zero five three when k is large. This sets a hard ceiling on what's possible with current methods, which is important for setting realistic expectations in the field.
Tom: That ceiling number is pretty sobering when you think about how much work it takes to push past it. But then they showed that their specific randomized algorithm for general objectives achieves one over e plus three point five times ten to the negative six for every non-negative function, no matter what.
Jane: So the improvement they show isn't just in the asymptotic limit, but a concrete guarantee of being slightly better than one over e plus that small constant for large budgets k. That gives us a much more reliable expectation when we are dealing with larger budget constraints.
Title and authors: Lu: And they also provided some hardness results, which is always useful. They showed that for every budget k greater than or equal to two and any small positive number epsilon, there's an instance of a monotone coverage problem where the ratio is at most one minus one over k times k plus epsilon.
Meng: Hardness results are important because they tell us exactly how hard the problem is to solve, which helps us know where our efforts should be focused. The bound they showed for large k, that one minus one over e plus O log log k over log k, suggests that as the budget grows very big, getting closer to the ideal limit becomes progressively harder.
Lalam: It seems like this paper really solidifies the understanding of where the theoretical limits lie for both monotone and general submodular secretary problems with a cardinality constraint. The main contribution is providing explicit guarantees across different budgets, moving beyond just asymptotic results that only apply when k goes to infinity.
Tom: So, to wrap up on "The Submodular Secretary Problem: Tight one-one/e for Monotone Objectives, and Strictly Between one/e and one/two in General," we have established tight bounds for both function types and shown that eligibility attenuation is a strong tool for general objectives <ref:2611.17292#pg1,The Submodular Secretary Problem: Tight 1-1/e for Monotone Objectives, and>. It gives us concrete ratios like zero point two six seven seven at every budget level k.
Jane: Exactly. For the listener, it means if you're designing a system that needs to select a small set of items from an incoming stream, you can now have a much clearer idea of what performance you can actually expect based on the function type and how large your selection budget is.
Lu: It’s about understanding that there are fundamental structural differences between monotone and general problems that dictate the achievable competitive ratios. The work highlights that for general problems, the non-monotonicity is a real barrier we have to contend with.
Meng: For me, it’s about knowing what to expect when I’m building something at scale. Knowing that there’s a ceiling of zero point four nine seven zero five three for the best known algorithms gives me a realistic target when trying to deploy a solution.
Lalam: And the algorithm itself, eligibility attenuation, is a mechanism we can actually use in practice to get close to the theoretical limits, especially when k is large. It’s not just abstract math; it’s a tool.
Tom: So that's where we are with this paper. We have bounds for monotone problems settled exactly at one minus one over e and a better lower bound for general problems, and we have an algorithm that gets us close to those limits with concrete performance guarantees across various budgets k. That's the gist of "The Submodular Secretary Problem: Tight one-one/e for Monotone Objectives, and Strictly Between one/two in General <ref:2611.17292#pg1,The Submodular Secretary Problem: Tight 1-1/e for Monotone Objectives, and>."
The paper's summary: Tom: So, we just talked about how this paper settles the theoretical limits for picking items when you have to pick up to a certain number of them from an incoming stream.
Jane: Yeah, so basically, they’re saying that for problems where the value function is monotone—meaning adding more items never hurts—they found the absolute best possible ratio is exactly one minus one over e. That's a very tight bound.
Lu: And for those monotone problems, they show you can actually hit that one minus one over e limit using just about four times the number of items in your stream, which is quite efficient computationally.
Meng: That sounds great theoretically, but what does that mean for me when I'm actually running this on a live system? Does "four times the number of items" mean anything practical with millions of incoming data points?
Lalam: The paper suggests a specific strategy called eligibility attenuation. It’s a way to make the decision at each step based on how long ago an item was available, and it keeps that ratio locked onto one minus one over e for large budgets.
Tom: So, for monotone objectives, the method is pretty straightforward—use that attenuation rule and you get near-perfect performance asymptotically as the budget gets huge. But then they switch gears to general objectives—where the value function can go up and down.
Jane: That’s where things get interesting because for general functions, they say you can't hit that perfect one minus one over e limit in the same way; the best ratio stays strictly between one over e and zero point five as the budget size grows.
Meng: So even with a huge budget, you can't guarantee that perfect performance if your value function isn't monotone? That sounds like a big deal for deployment—it means we have to accept some gap.
Lu: Exactly. They show that their randomized algorithm for general objectives achieves one over e plus a very tiny constant, three point five times ten to the negative six, every time you test it on any non-negative function as long as your budget size is big enough.
Lalam: And they also gave us some hard limits on what’s possible with current techniques; no algorithm can ever beat a ratio of zero point four nine seven zero five three when the budget is large. That sets a very clear ceiling on performance for general problems right now.
Tom: It sounds like the paper gives us two different answers depending on the function type: perfect performance if it's monotone, and an improved but still bounded performance for everything else.
Jane: And they showed that there are specific rules, like the eligibility attenuation strategy, that work well for general problems, even if they can't hit the absolute best theoretical limit.
Lu: The main thing to watch is how those hard limits change as you look at different budget sizes; the performance gap between one over e and zero point five gets smaller as you increase the budget size significantly.
Meng: It’s helpful to know that there’s a solid floor, like zero point two six seven seven for small budgets, so we don't expect total failure when we start out with a small selection limit.
Lalam: So it turns out that even though general problems are harder, the structure of the problem still lets you get close to one over e if you use the right probabilistic mechanism.
Tom: This paper really clarifies that for any online selection problem with a budget constraint, you need to know if your objective is monotone or not because those two scenarios have fundamentally different theoretical answers.
Jane: And it points us toward using tools like eligibility attenuation as a robust way to handle the uncertainty in general objectives.
The paper's improvements: Tom: So we've talked about the paper’s main results—that monotone objectives hit that perfect one minus one over e limit, while general objectives get stuck somewhere between one over e and zero point five.
Jane: Yeah, so the paper points out a few ways they can push these results even further, especially for those general problems where things are messy.
Lu: They suggest using eligibility attenuation as a primary ingredient because it’s a very strong tool for controlling the acceptance probability in those complex settings.
Meng: Eligibility attenuation is that mechanism where you decide whether to take something based on how long ago it was available, and they show this helps you get closer to one over e for large budgets.
Tom: That sounds like a practical improvement because it gives us a concrete algorithm instead of just an asymptotic theoretical limit.
Jane: Exactly, and they also look at variants of that rule, like the uniform variant or the insured price policy, to see which ones work best for different kinds of general functions.
Lu: They even show that for monotone problems, you don't even need attenuation because the ratio is determined exactly by an offline benchmark of one minus e plus some small term.
Meng: That’s a nice simplification; if the function structure doesn't change, you can rely on a simpler approach instead of running a complex probabilistic test every time.
Tom: The paper also provides some new hardness results that show exactly how hard it is to solve these problems for certain budget sizes and function types.
Jane: These hardness results give us the numbers we need to understand the difficulty, showing how close you can get to one minus one over k times k for monotone problems when the budget size is small.
Lu: And they also showed that for larger budgets, like when the budget is bigger than sixty four, it gets progressively harder to get closer to that ideal limit of one minus e plus a little correction term.
Meng: So, if you're trying to build something for a real application, knowing these hardness results helps you understand the trade-off between how good your algorithm is and how much computing time or data you have.
Tom: The authors also show that their specific randomized algorithm for general objectives gets us one over e plus three point five times ten to the negative six for any non-negative function when the budget size is large enough.
Jane: That tiny constant improvement means that even with those messy general functions, you can be almost as good as the best possible monotone case once your budget is quite large.
Lu: It’s a lot of work to prove those explicit guarantees across all budgets, but they lay out a solid framework for how to approach these secretary problems systematically.
Meng: So what this means for us is that we have better tools now—a clearer understanding of the limits and an algorithm that actually performs well in the general case, even if it’s not perfect.
Conclusion: Tom: So we’re wrapping up on "The Submodular Secretary Problem: Tight one-one/e for Monotone Objectives, and Strictly Between one/two in General." Basically, this paper gives us the tightest bounds ever we've seen for selecting items when you have a budget constraint.
Jane: Right, so to recap it’s about showing that monotone problems are perfect at one minus one over e and general problems get stuck somewhere between one over e and zero point five.
Lu: The paper really highlights the structural difference between those two types of functions because that difference dictates everything about what competitive ratio is achievable.
Meng: It changes things for deployment because it tells us exactly how much performance gap we have to plan for depending on whether our data stream has a predictable structure or not.
Lalam: I’m pretty sure this result, especially the explicit guarantees across all budget sizes, means we can start designing systems with more confidence about their worst-case performance.
Tom: It does sound like it gives us a better roadmap for building those selection models that really balances theoretical perfection against practical performance on real traffic.
Jane: I think the biggest thing is how they connected the abstract math to things like eligibility attenuation, which is a mechanism we can actually use in practice to get near optimal results for general problems.
Lu: That's a key part of it; it’s not just finding a number, it’s giving you a concrete tool to use when you have those non-monotone functions.
Meng: I'm still worried about the computational cost of running that attenuation rule on massive streams, but knowing it pushes us closer to one over e is worth the effort.
Tom: It is; and it sets a new benchmark for what we consider achievable when dealing with online selection under constraints.
Jane: So this paper really solidifies where we stand on this problem, moving us past just vague guesses about performance limits.
Lu: It opens up a lot of avenues for future work, especially looking at how these results might apply to different types of data structures or maybe even more complex selection scenarios.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game