The Trade-off Between Coordination and Stability in Randomized Decisions

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 $K$ people with balanced gender counts it keeps more families together than graph-blind sampling under the same certified cap.