Online Sampling and Decision Making with Low Entropy

1 Introduction

Online decision making problems and their important part - sampling, heavily depend on randomness. Efficient sampling has a long history, since Knuth, Vitter and others [Knuth, 1981; Vitter, 1987], who studied how to generate a randomly ordered sample close to uniformly random. Since then, efficient and accurate sampling has become a fundamental problem in data science, see the recent survey by Mahmud et al. [Mahmud et al., 2020]. However, as indicated in several prominent sources, such as National Institute of Standards and Technology (NIST) [Turan et al., 2015] or Nature [Bierhorst et al., 2018], pure randomness is hard to get, thus in practice pseudo-randomness with a small entropy has to be used. Recently, the problem has brought more awareness and detailed analysis also in the online community [Buchbinder et al., 2023; Kesselheim et al., 2015a].

Prominent examples of the online decision problems are secretary and prophet-types problems. The most classical version of the secretary problems, introduced by statisticians in the 60s, asks for irrevocably hiring the best secretary among n rankable applicants and was analyzed in [Lindley, 1961; Dynkin, 1963; Chow et al., 1964; Gilbert and Mosteller, 1966; Bateni et al., 2013; Rubinstein, 2016; Rubinstein and Singla, 2017]. In the simplest problem's version, the goal is to find the best strategy when choosing from a sequence of randomly ordered applicants. A multiple-choice refers to the fact that the strategy is allowed to choose up to k applicants. The secretary problem has also played a fundamental role in advancing stopping theory, online algorithms, and various other fields [Babaioff et al., 2007; Babaioff et al., 2008; Hajiaghayi et al., 2004; Esfandiari et al., 2017; Hajiaghayi et al., 2007]. Recently, the problem has attracted attention from the learning communities who studied modifications in which the algorithm is given a prediction about the best among applicants [Antoniadis et al., 2020], a prediction interval for evaluation of each applicant [Jiang et al., 2021], or the objective is to rank all applicants rather than choosing best subset of them [Assadi et al., 2019].

Free-order secretary. We focus on a variant of the secretary problem called the free-order secretary problem. The free-order assumption reflects the fact that there is a third party that can decide the order of appearing applicants. This is in contrast to the original secretary problem where the order is uniformly random, but also generalizes the model as the third party can always randomly permute the applicants. On the other hand, the hardness of the problem remains in the fact that evaluations of candidates are still unknown to both the third party and an algorithm. For this model, different metrics for creating a fair order cheaper (i.e., an order for which there exist competitive algorithms) have been proposed. Kesselheim, Kleinberg, and Niazadeh [Kesselheim et al., 2015a] were the first to ask this question for secretary problems, showing how to construct in polynomial-time, a probability distribution on orders (permutations of size n), with entropy O(log logn) such that when the classic secretary algorithm (k = 1) is executed on this distribution, it is successful with probability close to the optimal probability 1e . They also prove that if this distribution has entropy o(log logn) then no 1-secretary algorithm can achieve constant success probability. When the evaluations of applicants are not deterministic, but rather follow some probabilistic distributions, Arsenis, Drosis, and Kleinberg [Arsenis et al., 2021] prove that a small set of orders can be pre-computed, such that for any collection of n distributions of evaluations, the classic secretary algorithm achieves a constant competitive ratio when sampled from the pre-computed distribution.

Despite efforts, previous work does not provide exhaustive answers to the following important questions:

What is the minimum entropy of a random order distribution that allows to sample and choose k elements in polynomial time with nearly-optimal competitive ratio? How large k could be?

We make a significant step to answer both questions. We show that in the free-order model, one can sample from a polynomially constructible distribution of orders with entropy O(log logn), achieving a competitive ratio 1 - ϵ(k), where ϵ(k) part is polynomially smaller than that in [Kesselheim et al., 2015a] and only √log k factor from the absolute bound Θ( 1 √k ) for any entropy [Kleinberg, 2005]. We prove that no smaller entropy could yield good competitiveness, for any k. Our construction lets us select up to k = O( logn log log n ) candidates, a doubly exponential improvement over k = O(log log logn) of [Kesselheim et al., 2015a]. Our results details are in Sec. 2, with overview in Table 1. For the full version of all sections, see [Hajiaghayi et al., 2024].

Problems and preliminaries. In the free order multiplechoice secretary problem, we are given integers k, n, 1 ≤ k ≤ n, and n boxes labeled [n] = {1, 2, , . . . , n} by an adversary, each i ∈ [n] containing a single number v(i), chosen by the adversary from an unknown distribution. The goal is to choose an order in which we will be sequentially opening these boxes. Each time we open the next box i in the chosen order, we learn the number v(i) and decide to accept v(i) or not. This decision is irrevocable, and we cannot revisit any box. We have to accept k of these numbers without necessarily opening all boxes, where the objective is to accept k largest among them, i.e., to accept k elements with maximum possible sum. Once we have accepted k of the numbers, we stop opening the remaining boxes, if any. If we have accepted j numbers so far and there are only k-j remaining boxes, we have to open all these boxes and accept their numbers. This problem is also called the free order k-secretary problem, and when k = 1, it is free order secretary problem.

Notation. Let Πn be the set of all n! permutations of the sequence (1, 2, . . . , n). A probability distribution p over Πn is a function p : Πn -→ [0, 1] s.t. ∑π∈Πn p(π) = 1. Shannon entropy, or simply, entropy, of the distribution p is H(p) = - ∑π∈Πn p(π) · log(p(π)), assuming 0 · log(0) = 0, and all log's have base 2. Given a distribution D on Πn, π ∼ D means that π is sampled from D. A special case of a distribution is given a (multi-)set L ⊆ Πn , and we write π ∼ L when a random order is selected uniformly at random (u.a.r.) from L. We abbreviate "random variable" to r.v.

Competitive ratio. As is common, [Jaillet et al., 2013], we quantify the performance of an algorithm A by the competitive ratio: A is α-competitive or has competitive ratio α ∈ (0, 1) if it accepts k numbers whose sum is at least α times the sum of the k largest numbers; the competitive ratio is usually in expectation using the random order randomness.

Wait-and-pick and threshold algorithms. An algorithm for the k-secretary problem is called wait-and-pick if it only observes the first m values (position m ∈ {1, 2, . . . , n-1} is a fixed checkpoint), selects one of the observed values x (x is a (value) threshold), and then selects every value of at least x received after checkpoint position m; however, it cannot select more than k values in this way, and it may also select the last i values (even if they are smaller than x) provided it selected only k-i values before that. An extension of wait-andpick algorithms, see [Gupta and Singla, 2020], allows partition of the order into consecutive phases, and selecting potentially different threshold value for each phase (other than 1) based on the values observed in previous phases. Thresholds are computed at checkpoints - last positions of phases. These thresholds could also be set based on statistics. We call such algorithms threshold algorithms, or multiple-threshold algorithms if there are more than two phases.

Related work. Our problem is directly related to the prophet inequality problem with order selection [Hill, 1983]. Namely, the free order 1-secretary problem is the Hill's problem where the numbers in the boxes are given by unknown single-point distributions, whereas the prophet inequality problem with order selection assumes arbitrary (un)known distributions. The free order k-secretary problem is also the free order matroid secretary problem in [Jaillet et al., 2013] with a uniform matroid. Recently, the free order (a.k.a., best order) variants have been studied extensively for the secretary and prophet problems, cf., [Abolhassani et al., 2017; Arsenis et al., 2021; Beyhaghi et al., 2021; Chawla et al., 2010; Correa et al., 2021; Jaillet et al., 2013; Liu et al., 2021a; Liu et al., 2021b; Peng and Tang, 2022]. The fundamental question this problem asks is: What is the best order to choose to maximize the chance of accepting the largest number?

2 Our Results and Techniques

Main contribution: algorithmic results. Our main result is a polynomial-time construction of a low-entropy distribution, guaranteeing an almost-tight competitive factor for the free order k-secretary problem.

Theorem 1. For any k < logn/ log logn, there exists a multi-set of n-element permutations Ln s.t. a deterministic multiple-threshold algorithm for the free order k-secretary achieves an expected (1 - 4√ log k k ) competitive ratio, using the order chosen uniformly at random from Ln. Ln is computable in time O(poly n) and the uniform distribution on it has O(log log n) entropy.

By using our framework we obtain the following fine-grained results for the classical secretary.

Theorem 2. There exists a multi-set of n-element permutations Ln s.t. the wait-and-pick algorithm with checkpoint ⌊n/e⌋ achieves 1e - 6 log log n e log1/2 n success probability for free order 1-secretary problem, when the adversarial elements are presented in order chosen uniformly from Ln. Ln is computable in time O(poly n) and the uniform distribution on it has O(log log n) entropy.

Lower bounds. We complement our results providing the first known lower bounds on entropy of multiple-choice secretary algorithms achieving any competitive ratio 1 - ϵ.

Theorem 3. Let k ≤ loga n for constant a ∈ (0, 1), and let ϵ ∈ (0, 1). Then, any algorithm (even fully randomized) solving k-secretary problem while drawing permutations from some distribution on Πn with an entropy H ≤ 1-ϵ 9 log logn, cannot achieve the expected competitive ratio of at least 1-ϵ for sufficiently large n.

The second lower bound on entropy is stronger as it holds for k < n/2, but it applies only to the class of the wait-andpick algorithms.

Theorem 4. Any wait-and-pick algorithm solving ksecretary problem, for k < n/2, with expected competitive ratio of at least (1 - ϵ) requires entropy Ω(min{log 1/ϵ, log n 2k }).

For a detailed discussion of our theorems 1-4, see Sec. 5.

Our techniques. We explain our framework on the ksecretary problem. Our goal is to compute a small (multi)set L ⊆ Πn, such that there is an algorithm A for the problem that chooses π ∼ L as its random order, achieving good expected competitive ratio. Let us start from a fully random permutation π ∼ Πn as the random order. Algorithm A faces adversarial values v(1) ≥ · · · ≥ v(n) with indices ind(k′ ) ∈ [n] for value v(k′ ), k′ ∈ [n], where (ind(1), . . . , ind(n)) is the adversarial permutation. Algorithm A considers these values sequentially in order (π(ind(1)), . . . , π(ind(n))).

Our building blocks are atomic events, in the uniform probability space (π ∼ Πn). Suppose that we are given a partition of the positions in π into t consecutive blocks (buckets) of positions and a mapping f of the k adversarial indices {ind(1), . . . , ind(k)} to the t buckets. Let σ be any ordering of the indices {ind(1), . . . , ind(k)}. Given f and σ, we define an atomic event as the event that contains all π ∈ Πn that obey the mapping f and preserve the ordering σ. Atomic events are appealing due to their symmetry, leading to simple algorithms and analysis. But, it might be impossible to preserve atomic events directly while keeping small entropy. Our new approach is to group atomic events into positive events, see Def. 2, that model success probability of threshold algorithms. We will now specify the technical details behind each step of our framework: 1

1. Probabilistic analysis and defining positive events. (Section 3.1 and 4.1) The first step is a probabilistic analysis of an algorithm A for the k-secretary problem, assuming that A uses a random order π ∼ Πn. We need an algorithm whose success probability (expected competitive ratio) can be analyzed by probabilistic events modelled by atomic events. We chose as A a modified multiple-threshold algorithm from the survey by Gupta and Singla [Gupta and Singla, 2020], see Algorithm 2. We use the probabilistic analysis from [Gupta and Singla, 2020], where they apply Chernoff bound to a collection of indicator random variables, which indicate if indices fall in an interval in a random permutation. These random variables are not independent, but they are negatively associated. We show an additional technical fact to justify the application of the Chernoff bound to these negatively-associated r.v.'s. This analysis lets us define positive events for Algorithm 2, meaning that the algorithm picks the itemwith ith largest adversarial value, for i ∈ [k].

2. Decomposing positive event into atomic events. (Section 3.1 and 4.2) We show how to define any positive event as union of atomic events. Once we prove that such a decomposition exists, it is easy to find it by complete enumeration over the space of atomic events, since the size of this space, tk · k!, basically only depends on k. Section 3.1 defines positive and atomic events abstractly. The decomposition of a positive event for Algorithm 2 for the k-secretary problem into atomic events is in Section 4.2.

1 Sections 3.1-3.3 present our techniques on the highest level of generality, but below we explain our framework on the k-secretary problem. Problem-specific application to the k-secretary problem is in Section 4.

3. Abstract derandomization of positive events via concentration bounds. (Section 3.2 and 4.3) Let each positive event Pγ, defined by atomic events A ∈ Atomic(Pγ), hold with probability pγ. We prove by Chernoff bound (Theorem 5) that there exists a small (multi)set L ⊆ Πn nearly preserving probabilities pγ of events Pγ , when Algorithm 2 uses π ∼ L as random order. We show how to derandomize this theorem by the method of conditional expectations with a special pessimistic estimator of failure probability, see Sec. 3.2. This estimator is derived from the proof of Chernoff bound, inspired by Young [Young, 1995]. Our derandomization Algorithm 1 uses algorithm from Lemma 2 to compute a decomposition of Pγ into atomic events. Algorithm 1 calls Prob(A) (defined in Appendix) to compute conditional probabilities. This crucially uses a symmetric nature of atomic events. Algorithm Prob(A) and its analysis are much simpler compared to directly computing conditional probabilities for positive events, and this also gives a promise for further applications.

4. Dimension reduction and lifting positive events. (Section 3.3 and 4.4) The above abstract derandomization has time complexity Θ(nk ), being polynomial only for nonconstant k. To make it polynomial, we design dimension reductions from n to poly log(n). We build on the idea of using Reed-Solomon (RS) codes from [Kesselheim et al., 2015a], with two changes. First, we only use one RS code; they use a product of 2 or 3 such codes. Second, we replace their second step based on complete enumeration by our derandomization step 3. To define the dimension reduction, we propose in Lemma 1, a new technical ingredient: an algebraic construction of a family of functions that have bounded number of collisions and their preimages are of almost same sizes up to additive 1. We prove it by carefully using algebraic properties of polynomials. Our construction significantly improves and simplifies the constructions in [Kesselheim et al., 2015a] by adding the constraint on sizes of preimages and using only one RS code. The last step of is to lift the lower-dimensional permutations back to the original dimension, i.e., to prove that we lose only slightly on the probability of positive events when going from the low-dimensional permutations back to dimension n, see Sections 3.3 and 4.4.

3 Generic Construction for Threshold Algorithms

3.1 Probabilistic Atomic and Positive Events for Threshold Algorithms

Let Ω = (Πn, µ) denote the probabilistic space of all n! permutations of n elements with uniform probabilities: Pr[π ∈ Πn] = µ(π) = 1/n!. We will define atomic events in space Ω. Given any integer t ∈ {2, 3, . . . , n}, let B := B1,B2, . . . ,Bt, be a bucketing of the sequence (1, . . . , n), i.e., partition of sequence (1, . . . , n) into t disjoint subsets (buckets) of consecutive numbers whose union is the whole sequence. Formally, there are indices τ1 < τ2 < · · · < τt-1 < τt = n, ∀j ∈ [t - 1] : τj ∈ [n], such that B1 = {1, . . . , τ1}, and Bj = {τj-1 + 1, . . . , τj}, for j ∈ {2, 3, . . . , t}.

Definition 1 (Atomic events). Let σ = (σ1, . . . , σk) = (σ(1), . . . , σ(k)) be any k-tuple of set [n], i.e., injection σ : [k] -→ [n]. Let f : [k] → [t] be a non-decreasing mapping of elements from the sequence into t buckets of the bucketing B. Then an atomic event in probability space Ω for the chosen σ and f is defined as:

The family Ak,B of all atomic events, parameterized by k and B, is defined as Ak,B = ⋃σ,f Aσ,f .

Definition 2 (Positive events). A positive event P is any subset of the atomic family Ak,B, denoted Atomic(P) ⊆ Ak,B, such that every two atomic events from P are disjoint, P =

·⋃A∈Atomic(P) A. Any set of positive events is called a positive family of events.

We will propose in Sec. 4 a positive events family capturing behavior of an optimal algorithm for the k-secretary problem, showing how to express the positive events by atomic events.

3.2 Derandomization of Positive Events via Concentration Bounds: Theorem 5

Let Ω = (Πn, µ) be the probabilistic space of n-element permutations with uniform probabilities. Given integer t ∈ {2, 3, . . . , n}, let B = B1,B2, . . . ,Bt, be a bucketing of the sequence (1, . . . , n). We will prove the following probabilistic result and its derandomization in Theorem 5.

Theorem 5. Let k ∈ [n], k > 2 and Ak,B be the family of atomic events in the space Ω, where bucketing B has t buckets. Let P = {P1, . . . , Pq} be a family of positive events based on Ak,B, for some integer q > 1, such that for any Pγ ∈ P, γ ∈ [q], we have Prπ∼Πn [Pγ] ≥ pγ > 0 for some pγ ∈ (0, 1). Let p0 = min{p1, p2 . . . , pq}, and for any Pγ ∈ P, Atomic(Pγ) be the set of atomic events that define Pγ. Then, for any δ ∈ (0, 1), there exists a multi-set L of permutations with |L| ≤ ℓ = 2 log q δ2 p0 , such that Prπ∼L[Pγ] ≥ (1 - δ) · pγ, for each Pγ ∈ P, and L can be computed by Algorithm 1 in deterministic time O (ℓn3 q · t2k · (k!)2 · (n+kk! +k log2 n)) .

In the reminder of Section 3.2 we present the proof of Theorem 5; missing details appear in [Hajiaghayi et al., 2024].

Preliminaries. To derandomize the Chernoff argument in Theorem 5, we will derive a special conditional expectations method with a pessimistic estimator. We will model an experiment to choose u.a.r. a permutation πj ∈ Πn by independent "index" r.v.'s Xi j : Pr[Xi j ∈ {1, 2, . . . , n - i + 1}] = 1/(n - i + 1), for i ∈ [n], to define π = πj ∈ Πn "sequentially": π(1) = X1 j , π(2) is the X2 j -th element in I1 = {1, 2, . . . , n} \ {π(1)}, π(3) is the X3 j -th element in I2 = {1, 2, . . . , n} \ {π(1), π(2)}, etc, where elements are increasingly ordered.

Input: Positive integers n, k ≤ n, ℓ ≥ 2, such that log k ≥ 8. Output: Multi-set L ⊆ Πn of size ℓ. /* Function Prob(A) is defined in Appendix. */ 1 π1 := (1, 2, . . . , n); L := {π1}; Let P = {P1, . . . , Pq} be the set of all positive events. 2 for γ ∈ {1, . . . , q} do w(Pγ) := 1 - δ · ϕ1(Pγ) 3 for s = 1 . . . ℓ -1 do 4 for r = 1 . . . n do 5 for γ ∈ {1, . . . , q} do 6 for τ ∈ [n] \ {πs+1(1), πs+1(2), . . . , πs+1(r - 1)} do 7 for A ∈ Atomic(Pγ ) do 8 Pr[A | πs+1(1), . . . , πs+1(r - 1), πs+1(r) = τ ] := Prob(A) 9 E[ϕs+1(Pγ) | πs+1(r) = τ ] := ∑A∈Atomic(Pγ ) Pr[A | πs+1(1), . . . , πs+1(r - 1), πs+1(r) = τ ] 10 Choose πs+1(r) = τ for τ ∈ [n] \ {πs+1(1), πs+1(2), . . . , πs+1(r - 1)} to minimize ∑qγ=1 ω(ℓ, s, γ) · w(Pγ) · (1 - δ · E[ϕs+1(Pγ) | πs+1(r) = τ ]). 11 L := L∪ {πs+1}; for γ ∈ {1, . . . , q} do w(Pγ) := w(Pγ) · (1- δ · ϕs+1(Pγ))

Suppose random permutations L = {π1, . . . , πℓ} are generated using X1 j ,X2 j , . . . ,X n j for j ∈ [ℓ]. Given a positive event Pγ ∈ P, γ ∈ [q], let Xj(Pγ) = 1 if event Pγ holds for random permutation πj , j ∈ [ℓ], and Xj(Pγ) = 0 otherwise. For X(Pγ) = X1(Pγ) + · · · + Xℓ(Pγ) and δ ∈ (0, 1), we have that E[X(Pγ)] ≥ pγℓ and by Chernoff bound we have Pr[X(Pγ) < (1 - δ) · pγℓ] < exp(-δ2pγℓ/2), and so (Pr[∃Pγ ∈ P : X(Pγ) < (1- δ)pγℓ] < 1 if ℓ ≥ 2 log q δ2 p0 ) . We call the positive event Pγ ∈ P not well-covered if X(Pγ) < (1 - δ) · pγℓ (then a new r.v. Y (Pγ) = 1), and well-covered otherwise (then Y (Pγ) = 0). Let Y = ∑P∈P Y (P). By the above argument E[Y ] = ∑P∈P E[Y (P)] < 1 if ℓ ≥ 2 log q δ2 p0 . We will keep the expectation E[Y ] below 1 in each step of the derandomization, and these steps will sequentially define the permutations in L.

Derandomization outline. We will choose permutations {π1, π2, . . . , πℓ} sequentially, with π1 = (1, 2, . . . , n). For some s ∈ [ℓ - 1] let permutations π1, . . . , πs have already been chosen ("fixed"). We will choose a "semi-random" permutation πs+1 position by position using Xis+1 . Suppose πs+1(1), πs+1(2), ..., πs+1(r) are already chosen for some r ∈ [n - 1], where all πs+1(i) (i ∈ [r - 1]) are fixed and final, except πs+1(r) which is fixed but not final yet. We will vary πs+1(r) ∈ [n] \ {πs+1(1), πs+1(2), ..., πs+1(r - 1)} to choose the best value for πs+1(r), assuming that πs+1(r + 1), πs+1(r + 2), ..., πs+1(n) are random. Permutations πs+2, . . . , πn are "fully-random".

Conditional probabilities. Given Pγ ∈ P, r ∈ [n - 1], note that Xs+1(Pγ) depends only on πs+1(1), πs+1(2), . . . , πs+1(r). We define Pr[Xs+1(Pγ) = 1 | πs+1(1), πs+1(2), . . . , πs+1(r)] = Pr[Xs+1(Pγ) = 1] when r = 0. We will show how to compute the conditional probabilities Pr[Xs+1(Pγ) = 1 | πs+1(1), πs+1(2), . . . , πs+1(r)], where randomness is over random positions πs+1(r+1), πs+1(r+2), . . . , πs+1(n), see Theorem 6 and [Hajiaghayi et al., 2024] for details.

Theorem 6. Suppose πs+1(1), πs+1(2), . . . , πs+1(r) have already been fixed for some r ∈ {0} ∪ [n]. There is a deterministic algorithm to compute Pr[Xs+1(Pγ) = 1 | πs+1(1), πs+1(2), . . . , πs+1(r)], for any positive event Pγ , where the random event is a random choice of the semirandom permutation πs+1 conditioned on its first r elements already being fixed. This algorithm calls function Prob(A) for A ∈ Atomic(Pγ), and has running time O(|Atomic(Pγ)| · (n2 + nk(k! + log2 n))) .

Pessimistic estimator. For Pγ ∈ P, let E[Xj(Pγ)] = Pr[Xj(Pγ) = 1] = µγj for each j ∈ [ℓ], and E[X(Pγ)] = ∑ℓj=1 µγj = µγ. By assumption in Theorem 5, µγj ≥ pγ, for j ∈ [ℓ]. We use Raghavan's proof of Hoeffding bound, see [Young, 1995], for any δ > 0, using that µγj ≥ pγ:

where b(x) = (1 + x) ln(1 + x) - x and the last inequality follows by b(-x) > x2 /2. By the union bound:

Inequality (1) helps us derive a pessimistic estimator of this failure probability. Let ϕj(Pγ) = 1 if πj makes event Pγ true, and ϕj(Pγ) = 0 otherwise. The resulting pessimistic estimator is Φ = ∑qγ=1 ω(ℓ, s, γ)· (∏sj=1 (1 - δ · ϕj (Pγ))) · (1 - δ · E[ϕs+1(Pγ)]), where ω(ℓ, s, γ) = (1-δpγ)ℓ-s+1 (1-δ)(1-δ)pγℓ .

3.3 A Polynomial Time Construction of a Dimension-Reduction Set

A set G of functions g : [n] → [ℓ] is called a dimensionreduction set with parameters (n, ℓ, d) if the following two conditions hold:

(1) the number of functions that have the same value on any element of the domain is bounded:

(2) for each function, the elements of the domain are almost uniformly partitioned into the elements of the image: ∀i∈[ℓ],g∈G : nℓ ≤ |g-1 (i)| ≤ nℓ + o(ℓ).

The dimension-reduction set of functions is key in finding low-entropy probability distribution that implies high probability of positive events. It reduces the size of permutations from n to ℓ. [Kesselheim et al., 2015a] were first to use such reduction for secretary problems. Our refinement is the new condition (2) above, which significantly strengthens the reduction. We show a general pattern for constructing a set of functions that reduce the dimension from n to q < n by using refined Reed-Solomon codes.

Lemma 1. There exists a set G of functions g : [n] -→ [q], for some prime integer q ≥ 2, such that for any two distinct indices i, j ∈ [n], i ̸= j, we have

where 1 ≤ d < q is an integer such that n ≤ qd+1 . Moreover, |G| = q and set G can be constructed in deterministic polynomial time in n, q, d.

Corollary 1. Observe that setting q ∈ Ω(log n), d ∈ Θ(q) in Lemma 1 results in a dimension-reduction set of functions G with parameters (n, q, √q). Moreover, set G has size q and as long as q ∈ O(n), it can be computed in polynomial time in n.

4 Generic Construction Applied to Free Order Multiple-Choice Secretary

For ℓ = Θ(poly log(n)), we define atomic events with respect to the bucketing on ℓ-element permutations. We employ a refined version of an algorithm from [Gupta and Singla, 2020], see Algorithm 2, with permutation distribution D = Πℓ. Then we show that the algorithm's success can be described by atomic events. Even for such small ℓ, the family of atomic events is too rich to support the construction of a low-entropy distribution preserving all atomic events' probabilities. So we group atomic events into positive events, that have larger probabilities. Derandomization from Section 3.2 is used to construct such low-entropy distribution Lℓ supporting positive events' probabilities. Doing so on ℓ-element permutations, makes it computable in polynomial time in n, if ℓ is sufficiently small. This results in our derandomized algorithm Algorithm 2 that uses our low entropy distribution D = Lℓ. To lift the constructed distribution back to size npermutations, we use dimension-reduction from Section 3.3.

4.1 Positive Events and Probabilistic Analysis

We show a lower bound on the measure of a positive event in the space Ωℓ. Let a random permutation π ∼ Πℓ. Let

ˆ S = {j1, . . . , jk}, called a k-tuple, be an ordered subset {j1, . . . , jk} ⊆ [ℓ]. ˆ S models the positions in the adversarial permutation of the k largest adversarial values v(1) ≥ . . . ≥ v(k), i.e., ji ∈ [ℓ] is the position of value v(i) in π. Let K be the set of all such k-tuples.

Let us first define the following events: Hj = {τj ≥ min{v(i) : i = 1, ..., k} = v(k)}, and Lj = {τj ≤ v((1 - 2εj)k)}. Now, event Ci means that item ji with value v(i) will be chosen by the above algorithm for i ∈ {1, 2, . . . , (1 - δ)k}. Assuming that (1 - 2εj)k = 1 for j = -1, we can define for each j ∈ {-1, 0, 1, ..., log 1/δ-1} and for each i ∈ {(1 - 2εj)k, . . . , (1 - 2εj+1)k}:

We define a positive event corresponding to the k-tuple ˆ S and any i ∈ {1, 2, . . . , (1 - δ)k} as Pˆ S,i = (⋂j∈[0,log 1/δ] (Lj ∩Hj)) ∩ Ci. By refining the analysis in [Gupta and Singla, 2020] using Hoeffding-Chernoff bounds for negatively associated r.v.'s, we can prove that Prπ∼Πℓ [P ˆ S,i ] ≥ (1 - log(k)/k) · (1 - 2j+1 · δ).

4.2 Decomposing Positive Event into Atomic Events

We will design an algorithm to express each positive event as a union of disjoint atomic events. We also give an algorithm to compute conditional probabilities.

Let us define the following bucketing B1: B1 = {1, 2, . . . , ℓ0}, Bj = {ℓj-2 + 1, ℓj-2 + 2, . . . , ℓj-1}, for j = 2, 3, . . . , log(1/δ) + 1. We will now define all atomic events that define a given positive event Pi for some i. The bucketing has t = log(1/δ) + 1 buckets, so we will use the mappings f : [k] -→ [t], that fulfil (1), (2), (3) below; it can easily be shown that such mappings exist:

(3) : f(ji) > j +2, i.e., item ji arrives after time ℓj+1 .

Let FCi , for i ∈ {1, 2, . . . , (1 - δ)k}, be the family of all mappings f : [k] -→ [t] s.t. (1), (2), (3) hold. Given any f ∈ FCi , define a set of permutations Σf of the sequence ˆ S = (j1, . . . , jk) consistent with f, i.e., σ ∈ Σf if ∀i, i′ ∈ [k], i ̸= i′ : f(i) < f(i′ ) ⇐⇒ σ-1 (ji) < σ-1 (ji′). We express the positive events Pˆ S,i as follows:

Family PG-S of positive events of interest of Algorithm 2 is PG-S = {Pˆ S,i : ˆ S ⊆ [ℓ], i ∈ [(1 - δ)k]}.

Lemma 2. For any k-tuple ˆ S and any positive event Pˆ S,i , i ∈ {1, 2, . . . , (1 - δ)k}, for the Algorithm 2 for the multiple-choice secretary problem, we can compute the set Atomic(P ˆ S,i ) of all atomic events defining Pˆ S,i in time O(tk · k! · ℓ), where t = log(1/δ).

Algorithm 2: Multiple-choice secretary algorithm with adaptive thresholds and permutation distribution D ∈ {Πℓ, Lℓ}.

Input: Integers ℓ ≥ 2, k ≤ ℓ; sequence of ℓ items each with an adversarial value; π s.t. π ∼ D.

Output: Selected k items from the input sequence.

• 1 Set δ := √ log k k . Consider the ℓ items in the order given by the random permutation π.
• 2 Denote ℓj := 2j δℓ and ignore the first ℓ0 = δℓ items.
• 3 for j ∈ [0, log 1/δ), phase j runs on arrivals in windowWj := (ℓj, ℓj+1] do
• 4 Let kj := (k/ℓ)ℓj and let εj := √3δ/2j .
• 5 Set threshold τj to be the (1- εj)kjth-largest value among the first ℓj items.
• 6 Choose any item in windowWj with value above τj (until budget k is exhausted).

4.3 Derandomization of Positive Events via Concentration Bounds

The derandomization from Section 3.2 implies the existence of multi-set Lℓ of ℓ-element permutations where the uniform distribution on Lℓ preserves probabilities of positive events:

Lemma 3. There is (multi)set Lℓ ⊆ Πℓ with entropy O(log ℓ) of the uniform distribution on Lℓ s.t.

for any positive event Pˆ S,i ∈ PG-S. The (multi)set Lℓ can be computed in O(ℓ10 · t2k · (k!)3 ) time.

4.4 Lifting Lower-Dimension Permutations Distribution Satisfying Positive Events

We apply a dimension-reduction from Section 3.3, to turn a set Lℓ of ℓ-element permutations to a set Ln of n-element permutations such that the competitive ratio of Algorithm 2 executed on the uniform distribution over Lℓ is carried to the ratio of this algorithm on the uniform distribution over Ln.

That is, we use a dimension-reduction set G from Corollary 1 with parameters (n, ℓ, √ℓ), and Lℓ from Lemma 3. For given g ∈ G, π ∈ Lℓ, let π ◦g : [n] → [n] be any permutation σ ∈ Πn obtained as follows: function g ∈ G, g : [n] → [ℓ] assigns each element from [n] to one of ℓ blocks; permutation π ∈ Lℓ determines the order of the blocks; and permutation σ is obtained by listing elements from the blocks according to π where order of elements inside blocks is irrelevant. The final set Ln is defined as Ln = {π ◦ g : π ∈ Lℓ, g ∈ G}.

Lemma 4. Let ALGG-S(π) be the output of Algorithm 2 on the permutation π. Assuming ℓ2 < nℓ , one can compute a multi-set of n-element permutations Ln s.t.

where v∗ = v(1) + . . . + v(k) is the sum of k largest adversarial elements. Given Lℓ we can construct Ln in O(n · k2 log(ℓ)) time and the entropy of the uniform distribution over Ln is O(log ℓ + log |Lℓ|).

Theorem 7. For any k < logn log log n , there exists a multi-set of n-element permutations Ln s.t. Algorithm 2 has 1 - 4√ log k k expected competitive ratio for the free order k-secretary problem, when elements are presented in order chosen uniformly from Ln. Ln is computable in time O(poly (n)) and uniform distribution over Ln has entropy O(log k) = O(log log n).

Proof. Set k, k < logn/ log logn, ℓ := k8 , then the claim follows by applying Lemma 3 and 4 to the parameters. The running time follows because if k < log n/ log log n, the time of the construction by Lemma 3 is O(ℓ10 · t2k · (k!)3 ) = poly(n), as the dominant time is k! ≤ kk = poly(n).

5 Discussion and Conclusions

Theorem 3 uses a non-trivial extension of semitone sequences from [Kesselheim et al., 2015a]. One of technical challenges we had to overcome is that the algorithm picks k values, instead of one, creating additional probabilistic dependencies.

By Theorem 3, entropy Ω(log logn) is necessary for any algorithm to achieve even a constant competitive ratio 1 - ϵ, for k = O(loga n), a < 1, for k-secretary problem, implying that our upper bound in Thm. 1 is tight. Thm. 4 implies that entropy Ω(log log n) is necessary for any wait-and-pick algorithm to get a close-to-optimal competitive ratio 1 -Ω( 1 ka ), for any k < n2 , where a ≤ 12 . Moreover, the entropy Ω(log k) is necessary, which could be Ω(log n) for k = poly(n).

Theorem 1 implies an (almost) 2 optimal competitive ratio 1 - O(√log k/k), with minimal entropy O(log log n), when k < logn/ log logn, for k-secretary in non-uniform arrival model. This improves over competitive ratio (1 - O(1/k1/3 ) - o(1)) of [Kesselheim et al., 2015a], who used entropy O(log log n) and constructed the distribution for k = O((log log logn)ϵ ) only. We improve the range of working values k exponentially. Entropy optimality follows by our new lower bounds in Thm. 3 and 4. Such lower bounds were unknown before for the k-secretary problem, for k > 1. For 1-secretary, Thm. 2 improves, over doubly-exponentially, on the additive error to 1e of ω( 1 (log log log(n))c ) by [Kesselheim et al., 2015b], which holds for any constant c ∈ [0, 1], by a polynomial-time construction with additive error Θ( log log n log1/2 n ).

We have applied our new derandomization techniques to two different secretarial problems: 1-secretary and multiplechoice secretary problems. Further promising candidates are the online bipartite matching and matroid secretary problems, see [Gupta and Singla, 2020].

2 The competitive ratio is optimal up to a factor of √log k, see [Kleinberg, 2005; Gupta and Singla, 2020; Agrawal et al., 2014] for a matching lower bound.

Acknowledgements

The work is partially supported by DARPA QuICC, NSF AF:Small #2218678, NSF AF:Small #2114269, and NSF AF:Small #2347322, ONR MURI 2024 award on Algorithms, Learning, and Game Theory, Army-Research Laboratory (ARL) grant W911NF2410052, and Royal Society grant IES\R2\222170.