Two-Choice Rounding for Multi-Track, Time-Zone-Aware Conference Schedules

Virtual and hybrid conferences have to decide which talks run at which hours for an audience spread across every time zone. The best current method, mFairConf, handles this by solving a relaxed linear program (a version of the scheduling problem in which each talk may be split fractionally across time slots) and then rounding the fractional answer back into a real schedule. That method is limited to a single track. It treats speakers and attendees as separate people, so it ignores the author who presents in one session and wants to attend another. It is also built to be solved once, before the event, and never revised. Real multi-track programs break all three assumptions. Talks run in parallel, so two talks that the same Asia-Pacific audience cares about can collide in the one slot that audience can attend. Speakers double as attendees. The schedule keeps changing as talks are withdrawn and registrations arrive.

We propose to keep the linear program as the carrier of global fairness information and replace its rounding step with the power of two choices. The power of two choices is the classic load-balancing trick: each item probes two random bins and joins the less loaded one, which cuts the worst-case pile-up from roughly $\log n/\log\log n$ to $\log\log n$. In our version, each talk draws two candidate slots from its fractional LP solution. It then joins whichever candidate creates fewer interest-weighted collisions among the attendees who can actually be awake for that slot. Every placement is a local, constant-cost decision, so the same rule can repair a live schedule after a withdrawal without re-solving anything. The claim to be tested is that this matches exact dependent rounding on fairness and beats it on parallel-session collisions and schedule stability at ICML scale. We state in advance the experiments that would show the idea is unnecessary.

Core Claim

Our main prior work is Scheduling Virtual Conferences Fairly. It formalizes participant satisfaction, speaker satisfaction and total expected participation across time zones. It scales its integer program with two heuristics: Repeated Rounding of Fractional Solutions (RRFS), which solves and rounds the LP in stages, and Participant Clustering, which groups attendees into representative clusters. It is evaluated on FATREC, RECSYS and ICML. Its predecessor, On Fair Virtual Conference Scheduling, introduced these metrics on synthetic data only. Both papers motivate this proposal, and the second also supplies our metrics. Neither handles parallel tracks, dual roles, or incremental revision.

In the multi-track setting, the quantity that hurts minority time zones is not how many talks sit in a slot. Slot capacity is a degree constraint, and existing rounding schemes can enforce it exactly. The harmful quantity is a quadratic collision term. Let slot $s$ currently hold the set of talks $S_s$, let $w_{p,t}$ be attendee $p$'s interest in talk $t$, and let $a_{p,s}\in[0,1]$ be $p$'s availability at slot $s$ in their local time. Placing talk $t$ into $s$ then costs

$$L_s(t) = \sum_{t' \in S_s} \sum_{p} a_{p,s}\, w_{p,t}\, w_{p,t'},$$

which is the interest mass forced to choose between $t$ and a parallel talk it could have attended. The cost is set to infinity if a speaker of $t$ presents or moderates in $S_s$.

Our rule samples two slots $s_1, s_2$ independently from the LP marginals $x^*_{t,\cdot}$ and places $t$ in whichever has the smaller $L_s(t)$, subject to slot capacity. The LP decides which region of the schedule a talk belongs in, for fairness reasons. The two-choice comparison fixes the collisions that the LP's linear objective cannot see.

The load deliberately excludes talk popularity. The Fluid Mechanics of Liquid Democracy shows that when two-choice decisions are biased toward already-popular options, concentration gets worse rather than better. This result constrains our design: a load that rewarded crowd size would pull popular talks into majority-time-zone slots. We will test that failure mode directly.

Research Program

The work has three parts.

The first part is the formulation. We extend the mFairConf integer program to $K$ parallel tracks and add dual-role hard constraints. We also add a group-level term that bounds the gap in mean satisfaction between geographic regions, which answers the open "individual versus group fairness" problem. The LP relaxation of this program is the only global solve.

The second part is the rounding rule and its analysis. The rule has three variants: the offline version described above; an online repair version, which re-places only affected talks when a talk is withdrawn or an attendee registers; and a $d$-choice generalization. The analysis target is modest. We aim to bound the excess collision load relative to the LP when marginals are bounded away from very uneven, using the potential-function style of Talwar et al., who give a clean proof that two-choice gaps stay $O(\log\log n)$ under heavy load. We expect the bound to fail for very skewed marginals. Wieder shows that non-uniform bin probabilities can make $d=2$ insufficient, so $d$ is an experimental axis rather than a fixed choice.

The third part is an empirical package that responds to the validation gap common in this literature. Fairness in Resource Allocation and Slowed-down Dependent Rounding and the nearly-linear submodular knapsack algorithm both provide rounding theory with no implementation. Skowron and Rzadca analyze pairwise gossip balancing across geographically spread data centers but leave evaluation to future work. We will release multi-track, dual-role versions of FATREC, RECSYS and ICML, together with wall-clock measurements for every method.

Two-choice schemes in other domains supply the design pattern but not the problem. Automating Food Drop chooses between two geographically defined food banks using cumulative allocation. DualMap hashes each prompt to two servers to trade cache locality against load. Neither draws its candidates from an LP solution, and neither models human availability.

Baselines

The naive reference point is Social Welfare Maximization: the same program with fairness weights set to zero, rounded by the same machinery. The file reports that it starves minority time zones.

The strongest existing method is mFairConf with RRFS and Participant Clustering from Patro et al.. We extend it to $K$ tracks by adding slot-capacity and dual-role constraints to its integer program, and otherwise use the authors' procedure. For reported numbers, the file gives only qualitative claims. On FATREC with $\lambda_1=\lambda_2=0.5$, mFairConf "significantly reduced participant and speaker unfairness with only marginal losses." On synthetic data, FairConf loses "often less than 5-10%" of total attendance relative to Social Welfare Maximization. No reported numeric result was found on Lacuna for mFairConf on RECSYS or ICML. We will therefore reproduce mFairConf ourselves on single-track instances and require our reproduction to recover these qualitative findings before running any multi-track comparison.

The most direct technical competitor is bipartite dependent rounding of the identical LP solution. This is swap or pipage-style rounding, which moves fractional mass between pairs of variables so that slot capacities hold exactly and marginals stay unbiased. Its use under hard budgets appears in Herlihy et al., and a fairness-preserving variant is SRDR. Independent rounding of the same LP is also included as a weak reference. On small instances, an exact integer-program solver with a time budget gives the optimum or a certified gap.

Two ablations isolate our key ingredients. The first draws two candidates uniformly at random instead of from the LP, which tests whether the LP carries useful information. The second uses the single most likely LP slot with no comparison ($d=1$), which tests whether the second choice matters.

Fairness of comparison is enforced in three ways. All rounding methods consume the same LP solution. All methods get the same wall-clock budget per instance. Each randomized method is run for 50 seeds, and we report medians and spreads. Our method wins if it matches dependent rounding on participant, speaker and group unfairness within seed noise while cutting interest-weighted collisions. Online, it must also move substantially fewer talks than re-solving for the same fairness.

Why not just…?

Why not just give the multi-track integer program to a commercial solver? On FATREC-sized instances this may simply work, and we will say so if it does. The file shows, though, that even single-track mFairConf needed RRFS and clustering to reach ICML scale. Adding $K$ tracks and a quadratic collision term makes the program larger and nonlinear. The solver's gap at a fixed time budget on ICML-scale instances will settle whether this is a real threat. It remains one for small workshops.

Why not just use dependent rounding, which already enforces capacities exactly? Offline, it preserves exactly the linear constraints, and that is its limit. It is blind to the collision term, so any collision reduction must come from what the LP encodes, which is nothing about pairwise overlaps. Online, it has no notion of a local repair: a withdrawal means re-rounding, which may reshuffle the schedule that attendees have already planned around. If collisions under dependent rounding match ours offline, the offline claim falls, and the contribution reduces to online stability. The experiments report the two separately for that reason.

Why not just run greedy two-choice or local search without the LP? Uniform-candidate two-choice is our first ablation. Our expectation that it loses on group fairness rests on one fact: nothing in a collision load steers talks toward slots that minority regions can attend. If the ablation matches the full method, the LP is unnecessary and we will report that.

Proposed Experiments

The first experiment is single-track reproduction. It checks that our mFairConf implementation reproduces the reported qualitative trade-offs on FATREC and the synthetic power-law interest / cosine availability benchmark. The same benchmark lets us generate time-zone mixes with controlled skew.

The second experiment is the main multi-track comparison on FATREC, RECSYS and ICML with $K\in\{2,4,8\}$. Dual roles are inferred by treating authors as attendees with interest profiles. The metrics are:

  • the gap between best- and worst-off participants on Normalized Cumulative Gain (participant satisfaction);
  • the same gap on Normalized Expected Crowd (speaker satisfaction);
  • Total Expected Participation;
  • the minimum regional mean satisfaction;
  • total collision load $\sum_s\sum_{t\in S_s} L_s(t)$;
  • dual-role violations, which must be zero;
  • wall-clock time.

The third experiment is online revision. We replay streams of 5–20% withdrawals and late registrations and measure fairness drift and talks moved per update. It compares repair against re-solving plus dependent rounding.

The fourth experiment is stress testing. We sweep $d$ and the skew of the time-zone distribution to find where two choices stop sufficing, as Wieder predicts. A popularity-weighted load variant is included to check whether the liquid-democracy concentration effect appears: popular talks clustering in majority-zone slots.

The idea is falsified outright under three conditions: dependent rounding equals our collision numbers offline, uniform two-choice equals our fairness numbers, and repair offers no stability advantage over re-solving. Any one of these outcomes by itself also narrows the claim.