Introduction
Group scheduling is a ubiquitous coordination challenge, often characterized by the "Doodle fatigue" phenomenon. In typical scenarios, an organizer proposes a set of potential time slots, and participants indicate their availability. However, as the number of participants and slots increases, the process becomes increasingly burdensome. Traditional scheduling tools treat every participant and every time slot as equally unknown, ignoring the prior knowledge organizers often possess regarding participant habits (e.g., "Alice is rarely available on Monday mornings").
This paper formalizes group scheduling as a Probabilistic Matrix Inspection task. By modeling availability as a matrix of Bernoulli random variables, the authors derive a polynomial-time algorithm to determine the optimal sequence of queries—an inspection policy—that minimizes the expected number of questions required to find a consensus meeting time.
Problem Formalization
The problem is represented as an $n \times m$ matrix where rows correspond to participants and columns correspond to time slots. Each cell $(r, c)$ contains a Bernoulli random variable $X_{r,c} \in \{0, 1\}$, where $1$ indicates availability and $0$ indicates a conflict. The probability $p_{r,c} = P(X_{r,c} = 1)$ is assumed to be known a priori.
The objective is to identify a column $c$ such that $X_{r,c} = 1$ for all $r \in \{1, \dots, n\}$. An "inspection" involves querying a specific cell to reveal its value. Each inspection carries a unit cost. The goal is to find an inspection policy—a decision tree of queries—that minimizes the total expected cost to either find a successful column or prove that no such column exists.
The Optimal Inspection Policy
The researchers decompose the general matrix problem into simpler cases to identify the structural properties of an optimal strategy. This reveals a fundamental tension between two strategies:
- Succeed Fast (The 1-Row Case): If only one participant is involved across multiple slots, the optimal strategy is greedy: inspect the slots with the highest $p_{r,c}$ first to find a '1' as quickly as possible.
- Fail Fast (The 1-Column Case): If only one slot is considered across multiple participants, the strategy flips: inspect the participant least likely to be free first. This allows the organizer to abandon a non-viable time slot at the minimum possible cost.
The General Algorithm
For the general $n \times m$ matrix, the authors prove three critical theorems that define the optimal policy:
- Column-wise Persistence: An optimal policy should complete the inspection of a single column (time slot) before moving to another. Interleaving queries between different columns is mathematically suboptimal.
- Internal Ascending Order: Within any given column, participants must be queried in increasing order of their "free" probability ($p_{r,c}$). This ensures the "fail-fast" condition is met for every slot.
- The Sorting Metric: The columns themselves should be ordered according to a specific metric: $\frac{\mu_c(1 - s_c)}{s_c}$. Here, $s_c$ is the probability that the entire column consists of 1s ($s_c = \prod p_{r,c}$), and $\mu_c$ is the expected number of questions needed to find a 0 in that column (or confirm it is all 1s).
By combining these properties, the authors provide a greedy algorithm that reduces a potentially exponential search space—$(nm)!$ possible query sequences—into a simple sorting task that runs in polynomial time.
Empirical Context and Insights
While the paper is primarily theoretical, the authors ground their probabilistic assumptions in real-world data. They reference large-scale behavioral studies from Doodle, encompassing over 340,000 polls and 1.5 million date/time options. This data suggests that availability is not random but follows predictable patterns based on day-of-the-week effects and cultural demographics, justifying the use of prior probabilities ($p_{r,c}$).
A key insight of the work is the rejection of "naive greed." A common intuition might be to simply pick the column with the highest probability of success ($s_c$). However, the authors demonstrate that this is suboptimal because it ignores the "cost of failure" ($\mu_c$). The optimal policy is the mathematical "sweet spot" that accounts for both the likelihood of success and the expected cost of investigating a slot that might eventually fail.
Results and Limitations
The authors successfully prove that their algorithm finds the absolute minimum expected number of inspections. In practical terms, this makes the optimal scheduling sequence computationally trivial to calculate for any real-world scenario. In a 2x2 matrix example, the optimal policy reduced the expected inspections from 2.428 (standard greedy) to 2.407. While the margin is modest in small matrices, the efficiency gains scale significantly as the number of participants and slots grows.
Future Directions
Several avenues for future research remain:
- Probability Estimation: The model assumes $p_{r,c}$ is known. Future work must address how to accurately estimate these probabilities in dynamic human environments.
- Correlated Availability: The current model assumes independence between cells. In reality, factors like company holidays or shared meetings create correlations that could be integrated into more complex models.
- Variable Costs: The unit cost assumption (every query costs "1") could be expanded to reflect hierarchical costs, where querying a high-level executive carries a higher "cost" than querying a peer.
- Batching: Investigating the cost-effectiveness of asking one participant about multiple slots simultaneously versus sequential querying.
Summary updated