acceptodds
Under review as a conference paper at ICLR 2027

The Trade-off Between Coordination and Stability in Randomized Decisions

Abstract

When a decision is implemented by a randomized rule, the rule usually commits to each individual's probability of an action but does not constrain how the actions are drawn together. For example, two members of one household can be served by independent coins, which often split them, or by one shared coin, which never does. Yet one coin shared across a batch also makes the number of actions taken, or a group's action rate, swing widely from one draw to the next. We ask for the best attainable balance between these two properties of the realized decisions over all joint distributions with the prescribed marginals. Stability is measured by the worst normalized variance of a bounded linear aggregate of the decisions. We show that this coordination–stability frontier is not determined by local summaries. Arrangement matters: two placements on a cycle have the same counts of each probability value and edge type, yet their optimal stability costs can differ by a factor that grows with batch size. On arbitrary graphs, equal-probability components provide a one-sided test for whether zero excess can meet a stability cap. Block and Gaussian implementations provide explicit caps and certified tails. On equalized-odds policies, dependence placed along graph edges yields lower disagreement than random placement at matched stability, and in village lotteries that select exactly people with balanced gender counts it keeps more families together than graph-blind sampling under the same certified cap.

Primary area:
learning theory
Keywords:
coupling design, marginal probabilities, coordination graphs, aggregate variance control, algorithmic fairness

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_9qVgOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the tradeoff between coordination (i.e. the extent to which similar entities are rounded together) and stability (i.e. worst-case variance of linear statistics with bounded coefficients) in randomized rounding. The setup specifies a weighted coordination graph in which high-weight edges correspond to pairs whose roundings should agree, and the coordination level of a rounding scheme is measured by the frequency with which such pairs disagree above the smallest possible baseline, a metric denoted as "excess." Within this framework, the authors (1) characterize the best achievable stability under zero excess for kk-cycle coordination graphs (k≥3k \geq 3) up to constant factors, (2) show that when excess is non-zero, optimal stability on a cycle depends on global coordination graph structure, (3) provide a lower bound on zero-excess stability for general graphs via a decomposition into connected components, and (4) give two rounding scheme implementations for which coordination and stability bounds are computable a priori.

Critical strengths

• The paper exactly characterizes optimal zero-excess stability on cycles up to constant factors.

Critical weaknesses

• Positioning. The paper does not clearly distinguish its setup and results from the existing literature on randomized rounding schemes, making it difficult to assess novelty. For example, the discussion of dependent rounding is limited to Yamin et al. (2025) despite extensive prior work on preserving marginals while satisfying combinatorial constraints and/or controlling correlations. Moreover, the design choices/metrics considered (e.g. weighted coordination graph for coordination, variance of bounded linear aggregates for stability) are presented without motivation or relationship to prior work.

• Scope. Per the intro, the goal of the paper is "...to characterize the best attainable trade-off between local coordination and aggregate stability..." in dependent rounding. However, the main results are much narrower in scope: Theorem 1 only characterizes one endpoint of the Pareto frontier (zero excess) for a restricted class of coordination graphs (kk-cycles), the lower bound for general graphs only applies to zero excess, and Theorem 2 expands the characterization to non-zero excess for only two particular cycle constructions. Without motivation for why zero excess is an important regime in real applications, the significance of these results is unclear.

Questions for authors

• In what sense do these results characterize the general tradeoff between coordination and stability in randomized rounding? Is the goal of this paper to initiate its study rather than characterize the full tradeoff? Beyond its mathematical structure, is the endpoint that is primarily considered (exact zero excess) an interesting regime operationally?

• Which aspects of the setup and results are new relative to prior work on randomized rounding? Do practical settings motivate this particular combination of graph disagreement and worst-case variance as the design objective?

Reviewer_yTbzOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies the problem of choosing a joint distribution on assignments to a population of n individuals that

  1. preserves a fixed (pre-specified) marginal assignment probability to individual,
  2. Preserves the excess pairwise difference in weighted assignment agreement, where an agreement weight is specified by an edge weight in a graph on the individuals, and the excess is computed relative to the optimal disagreement rate (i.e. the minimal disagreement rate on an optimal coupling of the marginal assignment probabilities), and
  3. subject to these constraints aims to minimize a very strong notion of variance. The notion is the variance of the signed random assignment (in which we assign signs +/- 1 to each assignment random variable), in the worst case over all 2^n sign assignments.

Having defined this problem, the authors give several simple results about special cases.

  1. They define a quantity that characterizes (up to constant factors) the value of their constrained optimization problem in the special case in which the graph is a cycle.
  2. They observe that how marginal probabilities are arranged along the cycle matters for the solution. In particular if we have low and high marginal probabilities, the cycle arranged as LHLHLHLHLHLHLH... can obtain much smaller variance than a cycle arranged as LLLL....HHHH despite the same number of L and H assignments.
  3. An extremely elementary lower bound for general graphs, driven by the observation that if a connected component has entirely vertices with identical marginal probabilities, then at zero excess discrepancy, all outcomes must be perfectly correlated. This is essentially immediate.
Critical strengths

The paper gives a well defined model, and as far as I can tell, all of the results are correct.

Critical weaknesses

The paper is very poorly written, as if it were written entirely by AI. I had difficulty understanding the text, which caused me to run it through pangram, and indeed (unsurprisingly) it comes back as 100% AI generated. I trust that the idea for the project is due to the authors, but they have put very little care into writing the paper --- the value of the paper is in what it can explain to the reader.

The results themselves are of limited significance. Theorem 1 (the cycle characterization) is nontrivial --- but of limited conceptual importance, both because it is limited to cycles, and because it relies on the very strong/unusual notion of variance which maximizes over worst-case sign assignments. I suspect that the choice of this unusual metric may be so as to make Theorem 1 work out. The other theorems are much more immediate.

For both of these reasons I don't think the paper crosses the bar for publication. The problem itself is interesting and could be developed into an interesting paper if the authors put more effort into it.

Questions for authors

N/A

Reviewer_RRJFOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The question in this paper is the following: There are nn people, and each person ii must receive a positive decision with probability pip_i. There is also a weighted relation graph, where each edge ijij means that the people at its endpoints should receive the same decision as often as possible, and this edge has weight wijw_{ij}. Let Zi∈0,1Z_i\in{0,1} be the decision for person ii. The goal is to choose a joint distribution PP over these decisions while keeping every probability pip_i unchanged.

The paper measures disagreement using the excess disagreement:

\left(\Pr_P(Z_i\ne Z_j)-|p_i-p_j|\right), \qquad W=\sum_{ij\in E}w_{ij}.$$ Here, $|p_i-p_j|$ is the minimum possible disagreement between the endpoints. Therefore, smaller excess means better coordination, and zero excess means that every edge reaches its minimum possible disagreement. Another important parameter is aggregate stability: $$\Lambda(P)= \frac{\displaystyle\max_{a\in[-1,1]^n} \operatorname{Var}_P\left(\sum_i a_iZ_i\right)} {\displaystyle\sum_i p_i(1-p_i)}.$$ This measures the largest variance of a bounded weighted sum of decisions, normalized by the variance of the total count under independent sampling. Smaller values mean more stable outcomes, and independent sampling gives $\Lambda=1$. The paper studies the best trade-off between these two parameters over all joint distributions preserving the probabilities. On cycles, it characterizes the best stability at zero excess up to constant factors. It also shows that rearranging the same probabilities can change this optimum by a factor of order $n$, even when the probability counts and edge-type counts remain unchanged. The separation also persists at a small positive excess. For general graphs, it gives a lower bound at zero excess and block and Gaussian constructions with stability and concentration guarantees. Finally, it considers lotteries selecting exactly $K$ people and evaluates the methods on randomized fairness policies and village allocation.
Critical strengths

S1. The cycle results give matching bounds up to constant factors. A clear construction also shows the importance of probability placement, with an asymptotically large separation.

S2. The paper provides block and Gaussian constructions with explicit stability and concentration guarantees, and the experiments show improvements over the tested baselines. The paper also has a clean presentation and is easy to follow.

Critical weaknesses

W1. The main theoretical results are limited to cycles. Even on cycles, the characterization for arbitrary probabilities only considers zero excess, while the positive-excess results concern two specific placements. For general graphs, the paper provides only a one-sided lower bound at zero excess and constructions without guarantees on how close they are to the optimal trade-off.

W2. In Section 3.3 (lines 281–283), the authors claim that if Λ(P)≤4\Lambda(P)\le 4, then the standard deviation of every bounded aggregate is at most twice its standard deviation under independent sampling. However, consider 10 people with pi=1/2p_i=1/2. The first 5 people share one fair coin, while the remaining 5 use independent coins. Then Λ(P)=3≤4\Lambda(P)=3\le 4, but the variance of the number selected among the first 5 people is 25/425/4, compared with 5/45/4 under independent sampling. Therefore, the ratio of their standard deviations is 5>2\sqrt{5}>2, contradicting the claim. The issue seems fixable and does not appear to affect the main theorems.

Questions for authors

Q1. The block and Gaussian constructions seem to mainly build on existing techniques. Could the authors clarify what is technically new in these constructions compared with prior work? This would help me better understand the technical novelty of the general-graph results.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.