Demo 1: Collecting Data About Algorithms

The K-Secretary Problem

Input: \(n\) items arrive in uniformly random order with a total ordering (only relative comparisons are observable). An algorithm has \(K\) quotas for selecting items, and decisions are irrevocable.

Goal: Maximize \(\mathbb{E}[\text{number of selected items among the } K \text{ best overall}]\)

K-Potential

An item arriving at step \(i\) is a \(k\)-potential if it ranks among the top \(k\) items seen so far (steps \(1, \ldots, i\)). This is the only information available to an ordinal algorithm.

Ordinal Algorithm

An ordinal algorithm makes selection decisions based solely on relative rankings, not cardinal values. It can only observe whether the current item is a 1-potential, 2-potential, ..., or K-potential.

Quotas

The algorithm has \(K\) quotas \(Q_1, Q_2, \ldots, Q_K\) for selecting items. Once a quota is used, it cannot be reused. The algorithm must decide at each step \(i\) whether to use a remaining quota to select the current item.

Decision Variables

For each quota \(Q_j\) (\(j = 1, \ldots, K\)), k-potential (\(k = 1, \ldots, K\)), and step \(i\) (\(i = 1, \ldots, n\)):

with bounds \(0 \leq z_{j|k}(i) \leq 1\) for all \(j, k, i\).

Objective Function

Maximize the expected number of selected items among the \(K\) best:

where \(\delta_{k|\ell}(i)\) is the probability that the item at step \(i\) is a \(k\)-potential given it is the \(\ell\)-th best overall:

Constraints

1. Consistency Constraints (for \(j = 1, \ldots, K-1\)):

For each quota \(Q_j\), k-potential, and step \(i\):

These constraints ensure that the probability of using quota \(Q_j\) at step \(i\) is consistent with having previously used quotas \(Q_{j+1}, \ldots, Q_K\) but not yet used \(Q_j\).

2. Final Quota Constraints (for \(j = K\)):

For the last quota \(Q_K\), at each step \(i\):

Interpretation

The LP encodes the optimal randomized online algorithm for the K-secretary problem. Each variable \(z_{j|k}(i)\) represents the conditional selection probability at step \(i\), conditioned on the item being a \(k\)-potential (i.e., among the top \(k\) items seen so far).

Algorithm Structure

The optimal solution to the LP defines a K-threshold algorithm: at each step \(i\), the algorithm observes the current item's k-potential status and randomly selects it with probability \(z_{j|k}(i)\) using quota \(Q_j\).

Key Properties

• Ordinal: Decisions depend only on relative rankings (k-potential), not cardinal values
• Randomized: Selection probabilities are fractional, requiring randomization
• Online: Irrevocable decisions made at each step without knowledge of future items
• Optimal: Achieves the best possible competitive ratio among all ordinal algorithms

Performance

For \(n = 30\) and \(K = 2\), the optimal LP solution achieves:

This means the algorithm selects approximately 50.6% of the top 2 items on average.

Analyzing the Class of Ordinal Algorithms

The LP solution finds a single, fully optimal algorithm. We can, however, analyze the class of ordinal algorithms by parameterizing them.

We formalize this by introducing an external agent ("nature") that has a "budget" \(B\). This budget allows the agent to choose \(B\) of the algorithm's decision variables and fix them to specific values \(\vec{c}\). This defines a subclass of algorithms, allowing us to analyze the performance spectrum.

Formalization

Let \(y \in \{0,1\}^{\text{vars}}\) be a binary vector indicating which variables nature fixes, with \(\sum_v y_v = B\). For simplicity, we consider the case where nature fixes variables to zero (\(\vec{c} = \vec{0}\)). The modified LP becomes:

Performance Bounds

Best-case performance:

Worst-case performance:

Computing \(V_{\text{worst}}(B)\) requires solving \(\binom{|\text{vars}|}{B}\) LPs (one for each choice of \(B\) variables). For small \(B\), this is feasible via enumeration. (For larger \(B\) we can later implement a dualized and combined formulation and/or decomposition techniques.)

Interference Parameter \(\alpha\)

The interference parameter \(\alpha \in [0,1]\) parameterizes the performance degradation threshold. For given budget \(B\) and interference level \(\alpha\), we identify which variable configurations \(y\) achieve performance:

Interpretation:

• \(\alpha = 0\): Only configurations with optimal performance (no degradation)
• \(\alpha \in (0,1)\): Configurations with intermediate performance degradation
• \(\alpha = 1\): All configurations, including the worst-case

The \(\alpha\)-Spectrum

By sweeping \(\alpha\) from 0 to 1, we obtain the \(\alpha\)-spectrum: a curve showing how performance degrades as we relax the quality threshold.

Immediate Insights: The spectrum directly reveals:

• How quickly does performance drop as \(\alpha\) increases?
• Which algorithm steps \(i\) are most vulnerable to interference?
• Which quotas \(Q_j\) and potentials \(k\) are most critical?

Connection to DIAL: Beyond these immediate observations, the \(\alpha\)-spectrum embodies the core principle of DIAL (Data-driven Interpretability of Algorithm Logic) introduced on the front page. By "turning the dial" from \(\alpha = 0\) (optimal) to \(\alpha = 1\) (worst-case), we systematically probe the algorithm's behavior under varying levels of interdiction. This traces the full performance spectrum and maps out a multi-dimensional response surface where performance is a direct function of the interdiction strategy. The broader purpose includes:

• Understanding the shape of the manifold describing how different interference configurations affect performance
• Applying statistical methods to identify patterns and structure in the performance landscape
• Comparing algorithms by analyzing their respective response surfaces