Proportionality in Markov Temporal Elections

Temporal voting assumes that the alternative selected in one round does not affect the alternatives available later. We present _Markov temporal elections_, where the selected alternative instead determines the next state and changes future voting opportunities. We ask how proportionality should be defined when earlier decisions affect the opportunities for representation that remain. We show that the population shares used at the initial state cannot simply be reused at every later state: this can make proportionality impossible or force a Pareto-dominated policy that makes every voter worse off by a factor approaching the number of voters. We instead derive state-dependent proportional claims that account for the remaining representation opportunities. Among separable welfare objectives, these claims uniquely select Nash welfare, whose optimal policies satisfy a proportionality guarantee against coalitional deviations at every state. We show that deciding whether a coalition of a given size has an improving deviation is NP-complete, so we develop an efficiently computable certificate that bounds such deviations without enumerating coalitions. We extend the certificate to unknown transitions, where the proportional claims must also be inferred from data. Even unlimited on-policy data can leave the consequences of unchosen alternatives unidentified, making valid certificates highly conservative under limited coverage. Experiments show that action-dependent transitions increase the deviations available to coalitions against a fixed policy and that the certificate is much tighter than its worst-case guarantee on the tested instances. With unknown transitions, how informative the certificate is depends on coverage and uncertainty in the proportional claims.