1 The Setting

You are presented with a sequence of n values V1,…,Vn. In period i, you are shown vi, and must make an irrevocable decision to keep or dismiss it. You can keep at most k values, and earn a reward equal to the sum of kept values. You do not initially know {Vi}ni=1, but know that they are drawn independently from distributions F={Fi}ni=1. We assume that the Fi are continuous distributions with finite mean, although all ideas can be extended to the case where the Fi are discrete.

Although one could solve for the optimal policy using dynamic programming, we will instead focus on a class of much simpler policies.

Static Threshold Policies. Set a static threshold t. Keep item i if and only if Vi>t and fewer than k items have been kept so far. Let STtk(F) denote the expected performance of this policy.

We will benchmark these policies against a “prophet” who knows the values Vi in advance, and keeps the k highest.

Omniscient Benchmark. Let OMNk(F) denote the expected sum of the k highest values.

We wish to know, if we choose the threshold t well, how much worse can a static threshold policy be than the omniscient solution? In other words, we want to compute infFsuptSTtk(F)OMNk(F).

Computing this value is hard, so this paper gives a lower bound by (i) proposing an elegant way to choose t, and (ii) analyzing the resulting performance.

2 What Was Already Known?

The most studied case is k=1. In that case, it is well-known that a suitable static threshold guarantees half of the omniscient value. (This is actually a pretty amazing fact, when you think about it.) No better guarantee is possible, as the following simple example shows that even the optimal policy guarantees only half of the omniscient value. Let V1 be deterministically equal to 1, and let V2 be 1/ϵ with probability ϵ, and 0 otherwise. Any optimal policy obtains expected reward of 1, whereas the omniscient policy obtains expected reward of 2−ϵ.

There are several ways to choose the threshold t to guarantee 1/2 of omniscient. One especially elegant method from Samuel-Cahn (1984) is the “median strategy”: take t to be the median of the distribution of the maximum of the Vi. Another approach is the “mean strategy” of Kleinberg and Weinberg (2012): take t to be half of the mean of the distribution of the maximum of the Vi.

The latter approach generalizes to the case k>1, producing an identical guarantee of 1/2. However, this guarantee is far from optimal. When k is large, the law of large numbers kicks in, and you can do pretty well by choosing a threshold t such that the expected number of items with value above t is just a bit below k. Hajiaghayi, Kleinberg and Sandholm (2007) show that static threshold policies can achieve a fraction of OMN that is 1−O(√log(k)/k). Note in particular that this guarantee goes to 1 as k→∞. However, the constants established in that work are such that for k≤20, the best known guarantee is 1/2.

3 Their Algorithm and Results

The goal of the paper is to generalize the median strategy to arbitrary k>1.

delta_binom = function(n,k,p){
  return(pbinom(k-1,n,p))
}
mu_binom = function(n,k,p){
  prob = dbinom(0:(k-1),n,p)
  prob = c(prob,1-sum(prob))
  return(sum(prob*c(0:k))/k)
}
guarantee_at_p = function(n,k){
  return(Vectorize(function(p){return(min(delta_binom(n,k,p),mu_binom(n,k,p)))}))
}
guarantee_finite = Vectorize(function(n,k){
  return(optimize(guarantee_at_p(n,k),interval=c(0,1),maximum=TRUE)$objective)
})
kVals = c(2:4)
colors = rainbow(length(kVals))
nMax = 10 
plot(NULL,xlim=c(2,nMax),ylim=c(0.5,0.75),las=1,xlab='n',ylab='',main='Performance Guarantee')
for(i in 1:length(kVals)){
  lines(c(kVals[i]:nMax),guarantee_finite(c(kVals[i]:nMax),kVals[i]),col=colors[i])
}
legend(2,.58,col=colors,lty=rep('solid',length(kVals)),legend = kVals)

delta_pois = function(lambda,k){return(ppois(k-1,lambda))}
mu_pois = function(lambda,k){
  prob = dpois(0:(k-1),lambda)
  prob = c(prob,1-sum(prob))
  return(sum(prob*c(0:k))/k)
}
guarantee_at_lambda = function(k){
  return(Vectorize(function(lambda){
    return(min(delta_pois(lambda,k),mu_pois(lambda,k)))
  }))
}
guarantee_pois = Vectorize(function(k){
  return(optimize(guarantee_at_lambda(k),interval=c(0,k),maximum=TRUE)$objective)
})
kVals = c(1:10)
round(guarantee_pois(kVals),3)

##  [1] 0.500 0.586 0.631 0.660 0.682 0.699 0.713 0.724 0.734 0.742

4 Closing Thoughts

What do I like about this paper?

1. It asks a clean question: I appreciate the simplicity of static threshold policies.
2. It offers a simple policy. Although the optimal threshold depends on the order in which the Vi are presented, the authors’ proposed choice of t does not.
3. The analysis is elegant:
   • The first step offers clear intuition about balancing the risks of setting the threshold too high and too low.
   • The second step leverages the fact that their bound depends only on the values 1−Fi(ti), rather than the full distributions Fi.
4. The final result is a tight analysis of the performance of their policy.
5. The paper is written exceptionally clearly throughout, and is a joy to read.

The authors seem to have found the “right” generalization of the Samuel-Cahn median strategy, which is not at all obvious: Kleinberg and Weinberg (2012) write “it is hard to surpass the elegance of Samuel-Cahn’s proof”, but argue that the advantage of their approach is that “it generalizes to arbitrary matroids.” Meanwhile, these lecture notes call the median strategy “beautiful,” but “somewhat mysterious, and difficult to generalize.”

One special case of interest is when the Vi are iid. Although this seems like an easier setting, simple examples show that their algorithm’s performance may match the lower bound of γk,n even with iid values. In this follow-up post, I explore a simple algorithm that improves upon this guarantee.