acceptodds
Under review as a conference paper at ICLR 2027

Proportionality in Markov Temporal Elections

Abstract

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.

Primary area:
learning theory
Keywords:
Temporal voting, Proportionality, Markov decision processes, Nash welfare, Core stability

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_qpfbOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the problem of defining proportionality in a framework in which a set of agents is called to take multiple sequential decisions. In such frameworks, the early decisions affect the set of possible outcomes throughout the rest of the eliciting procedure.

Critical strengths

The paper handles a timely and relevant problem to the AI community: the problem of determining proportionality in a Markov temporal election is important and not trivial.

Critical weaknesses

While the subject is interesting and relevant to the AI community, I think that the paper suffers from two main weaknesses.

First, the motivation of the study is too vague to me. I think that the paper should find a real case in which this framework is useful and report the references to back the claim. In the current version of the paper the motivation for the work is only presented in the second paragraph of the introduction and does not refer to any existing work. Adding some relevant application would strengthen the paper.

Second, the paper is very dense, hard to follow, and not precise on the technical parts.

For example, the authors claim in the abstract that "Among separable welfare objectives, these claims uniquely select Nash welfare". The Nash welfare is a product of utilities, hence it is not the sum of the agents utilities as they claim at the beginning of section 4. This point is reinforced in section 4, where I read "[...] leads to Nash welfare, the product of voters’ utilities. The next result shows that Nash welfare is the unique separable objective inducing this update". The authors should formally define what they mean by Nash Welfare. Since it is the product of the utilities, I cannot see how this welfare function is separable.

Another less important imprecision: "Voters who can never receive positive utility can be included but not simply deleted". I do not understand the sentence. In the previous sentence it is stated that all the voters have positive utility, in this one I reported, it seems that you cannot remove agents that have null expected utility.

The subject of section 5 is continuation stability, but this concept is not introduced in the section nor in the introduction. Its presentation is only brief, descriptive and vague making it hard to grasp the meaning of the section as a whole.

The experimental section is not very informative to me. It should at least provide a table or some graphical representation of the results in the main body to have immediate access to the most relevant findings highlighted by the experiments. The current version relies on the reader going back and forth from the main body paper to the appendix.

Along these lines, the technical sections heavily rely on the appendix through the presentation, making it tedious to follow the argument put forward. The authors should make an effort to present in a concise and complete way a part of the results and defer the rest to the Appendix.

Lastly, certain sentences are ordered in a strange way and often times it is unclear what the subject is.

I give some examples

  • "A randomized Markov policy assigns, at each non terminal state s ∈ Sh, a distribution πh(· | s) ∈ ∆(Ch(s)) over its available alternatives. At the artificial initial state z0, the unique alternative is selected with probability one. Let Π denote the set of such policies."

As it stands \Pi seems to be referring to the possible initial states, not the set if random markov policies. Moreover, assuming \Pi contains the elements πh, it is not clear whether it refers to the whole policy or its possible conditioned versions.

  • The feasible occupacy set should be at least formally defined before its properties are claimed.

  • " Randomized Markov policies attain the same utility profiles as history-dependent policies (Derman & Strauch, 1966; Puterman, 1994; Altman,1999), in the layered form of Rosenberg & Mansour (2019). " this sentence seems to belong to the related works rather than to the model description. I do not see the point of introducing the "layered form of Rosenberg & Mansour (2019)" in the model section. Is this needed at some stage in the main body of the paper?

  • "The fractional Core in Definition 2.1 assigns each coalition S its population share |S|/n when evaluating the election as a whole." What is the criterion to evaluate the election as a whole?

Questions for authors
  • Is the "layered form of Rosenberg & Mansour (2019)" needed at some stage in the main body of the paper?

  • What does "evaluating the election as a whole" mean and how is this related to definition 2.1?

  • what is the "incompatibility" condition discussed at the beginning of section 3 and where is it defined? Similarly, what does it mean that the statewise extension "fails"? In the abstract it is said that you can use it, but it generates a degree of suboptimality, which one is precise conclusion?

  • If you cannot discard agents with null utility, how restrictive the assumption on the fact that every agent has positive utility is?

  • what is the "continuation stability"?

  • What do you mean with "Nash welfare is the unique separable objective inducing this update"? Does corollary 4.1 apply?


minor questions

  • in the definition of the problem I read "C_h(s) need not to come from a common set", however if the sets are finite and the time horizon is finite, they always come from a common set, right? You can just take the union. Am I missing on something that the sentence is trying to convey?
3 comments
AuthorsOpenReview ↗

Response (1/3)

Thank you for the detailed comments, which led to most of the changes in the revision.

Motivation. The second paragraph of the introduction now describes concrete settings. In reservoir operation, a release changes the stored volume and, together with uncertain inflows, which releases are possible later; multi-objective reservoir operation has been studied with sequential decision models (Castelletti et al., Water Resources Research, 2010; Giuliani et al., Journal of Water Resources Planning and Management, 2016). The paragraph also cites group decisions in a shared Markov decision process (Alamdari et al., NeurIPS 2024) and the token-by-token generation of a consensus statement (Blair and Larson, AAMAS 2026), where each choice fixes what has been written so far. Finally, participatory budgeting is run repeatedly (Faliszewski et al., IJCAI 2023; Lackner, Maly, and Rey, IJCAI 2021), and funding one project can affect the resources or projects available later; the paper notes that the cited work documents repeated budgeting rather than this specific dependence.

Presentation.

  • Nash welfare and separability: now defined in Section 4 (Q6 in our third comment).
  • Voters with zero utility: the passage is rewritten (Q4 in our second comment).
  • Continuation stability: new Definition 5.1, placed before Theorem 5.1 and preceded by a plain statement of the stability question; the contributions also describe it in words (Q5).
  • Definition of Π\Pi: a policy is now the complete collection π=(πh(⋅∣s))h,s\pi=(\pi_h(\cdot\mid s))_{h,s}, Π\Pi is the set of such collections, and continuation policies are defined as restrictions of policies in Π\Pi.
  • Occupancy set: the flow constraints are written out in Section 2 before any property of the set is stated.
  • Rosenberg and Mansour, and the election as a whole: see Q1 and Q2.
  • Reliance on the appendix: Section 4 now gives the short argument behind Corollary 4.1; Section 3 states the content of its two theorems directly; Section 5 summarizes what the new Appendix E.3 proves about the choice of weights.

Experiments. Each paragraph of Section 8 states its main numbers and their interpretation in the text. Across five families of small elections, the certificate PFz\mathrm{PF}_z exceeds the exact deviation ratio by less than 13%13\% at the median, although its worst-case factor is roughly two. Under fully action-dependent transitions, the average deviation ratio increases by a median of 0.1450.145 (middle half 0.0960.096 to 0.1780.178), and it increases in all 4040 paired elections. On the path to a Nash optimum, the initial-state deviation ratio falls to a median of 1.0251.025 by t=0.9t=0.9. With sparse behaviour-policy sampling, the certificate exceeds the one from uniform sampling by paired medians of 0.4190.419, 0.6460.646, and 0.7540.754 at 800800, 40004000, and 1600016000 samples. We agree that a figure helps. We checked whether the action-dependence figure fits in the main text: the revised main text fills the ten pages, and a legible figure would need about a quarter page, which would mean removing explanations added in response to the reviews. We therefore kept the complete quantitative discussion in Section 8 and left the figure in Appendix H.10 (Figure 2), which Section 8 cites at the corresponding result.

AuthorsOpenReview ↗

Response (2/3)

Q1. Is the layered form of Rosenberg and Mansour (2019) needed in the main text? No. The occupancy representation is needed, because it makes the attainable utility set a convex polytope, which the welfare arguments of Section 4 use, and because it turns optimization over policies into linear programs, which we use to compute deviations. The citation only credited the layered form of the flow constraints. It now appears only in Appendix B, and Section 2 writes the constraints out.

Q2. What does evaluating the election as a whole mean? It means comparing policies by ex-ante utility Ui(π)U_i(\pi), each voter's expected total utility over the whole election, computed before the initial state is realized. Definition 2.1 is stated in these terms, with shares ∣S∣/n|S|/n. The alternative is to compare continuation utilities Viπ(z)V_i^\pi(z) after a state zz has been reached. Section 3 now opens with this distinction instead of the phrase you quoted.

Q3. What is incompatible, and what does the second theorem establish? Section 3 now names two requirements. The initial requirement is the fractional Core of Definition 2.1. The fixed-share continuation requirement applies the same test after a state is reached, using continuation utilities but the original shares ∣S∣/n|S|/n. Section 3 proves two separate results, for two different elections.

  • Theorem 3.1 (incompatibility): no policy satisfies both the initial requirement and the fixed-share continuation requirement at every reached state.
  • Theorem 3.2 (welfare loss): imposing the fixed-share requirement at every state after the first round can be satisfied, but only by the profile (K+n−1)/n2(K+n-1)/n^2 for every voter. A different policy, which satisfies the initial requirement, gives every voter K/nK/n. The ratio nK/(K+n−1)nK/(K+n-1) approaches nn.

So the fixed-share extension fails in two distinct ways: it can be incompatible with the initial requirement, and even on its own it can force a Pareto-dominated outcome. The abstract refers to the two elections in turn. The revised Section 3 introduces the second result as answering a separate question, namely whether the continuation requirement can be costly even when a policy satisfying it exists, and the statement of Theorem 3.2 now specifies that the requirement is imposed at every state in rounds 2,…,H2,\dots,H, which is how the proof uses it.

Q4. How restrictive is positivity, and why not delete voters with zero utility? The assumption is that each voter receives positive utility under some policy. It excludes only voters who receive zero utility under every policy. Because policies can be randomized, mixing the nn policies that serve each voter gives everyone positive utility at once (Lemma D.1). Voters with zero utility under every policy cannot strictly gain from any deviation, so they cannot help a coalition in which every member must strictly gain, and a Nash optimum over the other voters lies in the fractional Core of the full electorate (Lemma D.1). Deleting them would reduce nn and increase every remaining coalition's share ∣S∣/n|S|/n, which can shrink the Core (Proposition D.1). For example, with alternatives (2,0,0)(2,0,0) and (0,2,0)(0,2,0), the profile (0.8,1.2,0)(0.8,1.2,0) is in the fractional Core with three voters; after deleting voter 3, voter 1 alone has share 1/21/2 and blocks, since 12⋅2=1>0.8\frac12\cdot2=1>0.8. Section 4 now states the assumption and this boundary case in words instead of the sentence you quoted, and points to Appendix D.1 for the details.

AuthorsOpenReview ↗

Response (3/3)

Q5. What is continuation stability? Fix positive weights λi\lambda_i and a state zz. Voter ii's claim at zz is bi(z)=λiViπ(z)b_i(z)=\lambda_iV_i^\pi(z), and coalition SS's share is αz(S)=∑i∈Sbi(z)/∑j∈Nbj(z)\alpha_z(S)=\sum_{i\in S}b_i(z)/\sum_{j\in N}b_j(z). With the canonical weights λi=1/Ui(π)\lambda_i=1/U_i(\pi), every claim is 11 at the start, so the share equals ∣S∣/n|S|/n there. Afterwards, each claim compares the utility the member can still expect from zz with what the member expected at the start, so a coalition's share grows at states favourable to its members and shrinks at states that are not. A coalition blocks at zz if some continuation σ\sigma from zz gives αz(S)Viσ(z)≥Viπ(z)\alpha_z(S)V_i^\sigma(z)\ge V_i^\pi(z) for every member, with strict inequality for at least one. In words, the coalition may abandon the policy at zz and choose any continuation, but it receives only its share of what that continuation would give. A policy is continuation-stable at zz if no coalition blocks there, and it is in the continuation Core if this holds at every state, reached or not. This is now Definition 5.1, placed before Theorem 5.1. Compared with the fractional Core, the test is repeated at every state with that state's shares, and blocking requires only a weak improvement.

Q6. Why is Nash welfare separable, and what does Corollary 4.1 say? Separable refers to objectives ∑iwiϕ(Ui)\sum_iw_i\phi(U_i), which add transformed utilities across voters; it does not say that the Nash product itself is a sum of the original utilities. Nash welfare is the product ∏iUiwi\prod_iU_i^{w_i}. For positive utilities, the logarithm is strictly increasing, so maximizing the product is equivalent to maximizing ∑iwilog⁡Ui\sum_iw_i\log U_i, which has the separable form with ϕ=log⁡\phi=\log. Under our positivity assumption the Nash optimum gives every voter positive utility (Lemma D.1), so the two objectives have the same maximizers. The mathematics was therefore consistent, but we agree that the original wording should have stated this equivalence earlier and more explicitly; Section 4 now does so.

Theorem 4.1 shows that a policy maximizing ∑iwiϕ(Ui)\sum_iw_i\phi(U_i) still maximizes an objective of the same form from any state zz, with voter weights proportional to wiϕ′(ui)/ϕ′(vi)w_i\phi'(u_i)/\phi'(v_i), where uiu_i and viv_i are the ex-ante and continuation utilities. Corollary 4.1 asks which ϕ\phi makes these weights proportional to wivi/uiw_iv_i/u_i, the initial weight scaled by the ratio of continuation utility to ex-ante utility. This forces xϕ′(x)x\phi'(x) to be constant, so ϕ(x)=alog⁡x+c\phi(x)=a\log x+c. So yes, Corollary 4.1 applies, and it singles out Nash welfare through its logarithmic form. Its statement now makes the hypothesis precise (for every voter with positive continuation utility, at every state, in every election), and Section 4 notes that the separate axiomatic derivation of the update relies on claim conservation (see also our reply to Reviewer 5G7k).

Q7. Can the alternative sets not always be embedded in a common set? Yes, their finite union is a common set. The sentence was meant to say that the available sets may differ across states and rounds, so no alternative needs to be available everywhere. Section 2 now says that the sets may differ across states and rounds.

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

The paper studies repeated group decisions where today’s choice changes future options, modelled as a Markov decision process. It shows that keeping population shares fixed over time can be infeasible or badly inefficient. It instead proposes that a voter’s claim scale with the share of their expected benefit still ahead of them, and argues this singles out Nash welfare. Nash-optimal plans cannot be blocked by any group at any state. Exact checking of a given plan is NP-hard, so the paper gives a cheap score that bounds deviations, extended to unknown transitions. Experiments use small synthetic elections.

Critical strengths
  1. Development of rigourous model for the repeated group decision making.
  2. Verification under unknown transitions is the most original part: uncertainty affects both the deviations and the fair shares themselves, and the paper handles both together.
  3. The proofs are careful and appear correct, including tight bounds for the cheap score.
Critical weaknesses
  1. The guarantee is close to self-referential.
  • Claims are defined by the plan being evaluated, and the stability theorem holds for any positive voter weighting. So essentially any Pareto-optimal plan counts as stable under its own claims.
  • Voters the plan stops serving get zero claim. The impossibility in Section 3 is resolved by removing the claims that caused it, a normative choice presented as a derivation.
  1. The characterization of Nash welfare is nearly tautological. The claim-conservation axiom amounts to linearity, and Theorem D.3 shows that without it a whole family of rules fits. “Uniquely selects Nash” therefore rests on one axiom that gets one sentence of justification.
Questions for authors
  1. With free voter weights, how does the continuation Core differ from Pareto optimality? With canonical weights, does it say anything beyond Nash optimality?
  2. Why should a voter the plan leaves with nothing have zero claim? What independently justifies claim conservation?
2 comments
AuthorsOpenReview ↗

Response (1/2)

Thank you for the careful review. You are right about freely chosen weights, and the revision now states this as a result. The distinction matters because the unrestricted theorem permits choosing the weights after selecting a policy, whereas the canonical weights are fixed by that policy's own ex-ante utilities. The canonical rule gives every voter the same initial claim and yields a definite statewise test, and the computational results allow that test to be assessed even for policies that are not Nash-optimal.

Free weights. The attainable utility set is a polytope (Lemma B.1). The new Proposition E.1 shows by LP duality that a profile is Pareto optimal (no attainable profile is at least as good for all voters and better for one) if and only if it maximizes ∑iλiUi\sum_i\lambda_iU_i for some strictly positive λ\lambda. After completion at off-support states (Lemma D.3), such a policy is λ\lambda-tight and hence, by Theorem 5.1, in the continuation Core for those weights. The converse also holds for positive-utility policies: continuation stability under some positive weights rules out a Pareto improvement, because the grand coalition has share one at the initial state and would otherwise weakly block. Thus, allowing the weights to depend on the policy makes continuation-Core membership (after off-support completion) equivalent to Pareto optimality, not a separate selection criterion. Its initial shares are then proportional to λiUi\lambda_iU_i rather than equal to ∣S∣/n|S|/n. So the limitation you describe is exact: if weights may be chosen separately for each Pareto-optimal policy, the theorem covers all such policies after off-support completion. It does not follow that one fixed, externally specified weight vector certifies every Pareto-optimal policy, or that the canonical weights do. Section 5 now says this directly after Theorem 5.1.

Canonical weights. The reciprocal weights λi=1/Ui(π)\lambda_i=1/U_i(\pi) remove this freedom. Every voter's initial claim is 11, so the initial shares are the population shares ∣S∣/n|S|/n; only the evolution of claims afterwards depends on the policy. The new Proposition E.2 shows that, with these weights, a positive-utility policy is λ\lambda-tight if and only if it maximizes Nash welfare and is scalar-optimal at the states it does not reach. Because the Nash-optimal utility profile is unique (Lemma D.1), a Pareto-optimal policy with any other profile is not tight under its own canonical weights.

Second part of Question 1: does the canonical version say more than Nash optimality? As a property, it says less. A Nash-optimal policy, completed off the support, is in the canonical continuation Core, but the converse fails. The new Example E.1 has one round, two voters, and alternatives (1,0)(1,0), (0,1)(0,1), (3/5,3/5)(3/5,3/5). The profile (0.64,0.54)(0.64,0.54) is Pareto optimal and both canonical singleton shares are 1/21/2, so no coalition blocks, even under weak blocking; yet its Nash product is 0.3456<0.360.3456<0.36. Theorem 5.1 is therefore a guarantee that Nash-optimal policies satisfy, not a characterization of them. The example in Appendix E.3 also establishes strict separations: Nash optimality implies canonical continuation stability (after completion at off-support states), but not conversely; canonical continuation stability implies Pareto optimality, but not conversely (the Pareto-optimal profile (0.8,0.3)(0.8,0.3) of the same example is blocked by voter 2 under canonical weights). Thus, with canonical weights, continuation stability is a distinct requirement rather than a restatement of either optimality notion. The initial-state part is classical. What is new is that the guarantee holds at every later state, reached or not, with explicit state-dependent shares, which Section 3 shows cannot be obtained by carrying the population shares forward.

Why the measures matter beyond Nash optimality. Sections 6 and 7 do not assume Nash optimality. Exact verification is hard: deciding whether a coalition of a given size has an improving deviation is NP-complete. PFz\mathrm{PF}_z and Certz\mathrm{Cert}_z instead bound the strongest deviation for any positive-utility policy, which matters when the policy is constrained or approximate, or when transitions are unknown and Nash optimality cannot be checked. On the path to a Nash optimum in Section 8, the median initial-state deviation ratio falls to 1.0251.025 by t=0.9t=0.9, yet only 44 of 590590 policies have deviation ratio 11 at every state with positive scalar value.

What the paper derives, and what it assumes. We agree that replacing fixed shares is a normative choice. Section 3 does not claim that a unique replacement follows from the impossibility results; it shows why the fixed-share extension is problematic. The proportional update is then supported by two separate arguments, dynamic consistency of separable welfare and an axiomatic derivation using claim conservation (see our next comment).

AuthorsOpenReview ↗

Response (2/2)

Is the characterization tautological? No. Claim conservation is a substantive axiom, but it does not assume Nash welfare or refer to welfare maximization. The axioms of Theorem D.2 constrain only how claims change from one state to the next. Given the boundary axiom, conservation is equivalent to the claims being linear in the continuation utilities for fixed initial weights and ex-ante utilities (proof of Theorem D.2), and it is the condition that separates the proportional update from the other candidates: Theorem D.3 shows that replacing it by separability, unit invariance, and path independence leaves the family wi(vi/ui)pw_i(v_i/u_i)^p with p>0p>0, each member corresponding to an isoelastic welfare transformation. Theorem 4.1 and Corollary 4.1 then separately identify which separable welfare objective is dynamically consistent with the proportional update. The two arguments start from different premises and arrive at the same rule, which is why we regard the result as conditional but not circular. The abstract, contributions, Section 4, and conclusion say that, among separable objectives, only Nash welfare induces the proportional update; the contributions and Section 4 add that the axiomatic derivation relies on claim conservation. Corollary 4.1 now states its hypothesis precisely.

Why conservation is a useful requirement. It says that a chance event which only reveals which state comes next should not, by itself, change a voter's expected claim. More precisely, suppose a decision-free chance event selects a successor state without awarding utility. Before the event, each voter has an expected amount of utility remaining; this equals the probability-weighted average of the amounts remaining in the successor states. Claim conservation asks for the same accounting rule for representation claims. In particular, a payoff-irrelevant coin flip leaves expected claims unchanged. This prevents the mere resolution of uncertainty from increasing or decreasing the expected representation attributed to a voter. It is a substantive and independently motivated choice, not a restatement of Nash optimality.

The alternative power updates make the distinction concrete. With initial utility ui=1u_i=1 and continuation utilities 00 or 22 after a fair coin flip, the power rule wi(vi/ui)pw_i(v_i/u_i)^p assigns claim wiw_i before the flip but expected claim 2p−1wi2^{p-1}w_i afterwards. For p=2p=2, the expected claim doubles even though no collective choice or utility occurred. The proportional rule p=1p=1 preserves it. Conservation also makes the claims bi(z)=λiViπ(z)b_i(z)=\lambda_iV_i^\pi(z) add up to the scalar continuation value used in Theorem 5.1. Other normative rules remain possible; the characterization identifies the proportional rule under conservation, rather than asserting that conservation is unavoidable.

Question 2: why can a voter have zero claim? Three cases should be kept apart, and Appendix D.7 now does so.

  • A voter with zero utility under every policy is treated in Lemma D.1 and stays in the electorate.
  • A voter with Ui(π)=0U_i(\pi)=0: the reciprocal weight 1/Ui(π)1/U_i(\pi) is undefined, so the case is excluded from the canonical analysis. Under the positivity assumption, a Nash-optimal policy gives every voter positive ex-ante utility.
  • A voter with Ui(π)>0U_i(\pi)>0 but Viπ(z)=0V_i^\pi(z)=0 at some state has zero claim at zz. This is the case you raise.

Consider the election of Theorem 3.2. The policy that serves voter jj at the state favoring jj gives every voter K/nK/n ex ante, through the chance of reaching their own state. At the state favoring jj, the other voters have zero claim because the policy provides nothing further to them there. Giving each of them share 1/n1/n at that state is the fixed-share requirement, which by Theorem 3.2 lowers every voter's utility to (K+n−1)/n2(K+n-1)/n^2. A zero claim describes what the evaluated policy still provides from a state; it does not remove the voter from the electorate, and under weak blocking the voter can still be the member whose strict gain makes a deviation blocking. It is the ex-post side of an ex-ante proportional policy. Applications that require a minimum ex-post share for every voter would need an additional normative condition, and Section 3 shows why simply keeping the original shares can be costly.

Reviewer_19tNOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

Core Problem: In Markov temporal elections (where current decisions reshape future state spaces and opportunities), reusing static initial population shares at continuation states is infeasible or causes severe system inefficiency (up to an O(N)O(N) welfare drop).

Proposed Solution: The paper derives state-dependent proportional claims that track remaining representation opportunities, which uniquely select Nash welfare among separable welfare objectives and guarantee statewise stability against coalitional deviations.

Computational & Practical Challenge: Exact deviation checking is NP-complete, so the authors develop an efficiently computable scalar certificate (PFzPF_z) that extends to unknown transitions and robust offline settings, though its informativeness heavily depends on data coverage.

Critical strengths

This work develop novel theoretical formulation of dynamic proportionality: The paper identifies and addresses a fundamental flaw in temporal voting—namely, that reusing static population shares across dynamic Markov states is either infeasible or causes an O(N)O(N) welfare drop. By introducing state-dependent proportional claims that uniquely select Nash welfare, the paper provides a principled, theoretically rigorous foundation for multi-period representation where current decisions reshape future opportunities. This is consequential because it successfully bridges static social choice theory with dynamic MDPs, opening a robust path for handling path dependency in collective decision-making.
It establishes novel theoretical formulation of dynamic proportionality: The paper identifies and addresses a fundamental flaw in temporal voting—namely, that reusing static population shares across dynamic Markov states is either infeasible or causes an O(N)O(N) welfare drop. By introducing state-dependent proportional claims that uniquely select Nash welfare, the paper provides a principled, theoretically rigorous foundation for multi-period representation where current decisions reshape future opportunities. This is consequential because it successfully bridges static social choice theory with dynamic MDPs, opening a robust path for handling path dependency in collective decision-making.

Critical weaknesses

Strong Real-World Applicability vs. High Technical Barrier: While the framework of Markov temporal elections provides a powerful model for path-dependent decision-making, the mechanics rely heavily on strict underlying assumptions (such as complete knowledge of or accurate estimation for state transitions, well-defined cardinal/approval preferences, and bounded state spaces). In complex, large-scale real-world deployments—such as digital economic platforms or political legislature—estimating true state-transition dynamics and preventing data coverage bottlenecks (as noted in Section 7) can be severely challenging. This is consequential because it highlights a potential gap between theoretical elegance and practical, out-of-the-box deployability when the transition kernel is heavily misspecified or poorly observed.

Questions for authors

In Section 7, the paper brilliantly shows that even unlimited on-policy data can leave unchosen alternatives indistinguishable, making certificates conservative or uninformative under limited coverage. Could the authors elaborate on practical, online data-collection strategies or active-learning mechanisms that could safely explore these rarely chosen or unchosen alternatives without violating the fairness and stability guarantees required during live deployment?

2 comments
AuthorsOpenReview ↗

Response (1/2)

Thank you for the constructive review. We agree that moving from a finite model to a large deployment raises difficult questions, and we do not claim an immediately deployable system. Section 7 addresses an important part of your concern, namely uncertainty about transitions and limited coverage of alternatives, and the revision states its scope more explicitly.

Applications. The introduction now names concrete settings in which a collective decision changes later options. In reservoir operation, releasing water changes the stored volume and, together with uncertain inflows, the releases possible later; multi-objective reservoir operation has been studied with sequential decision models (Castelletti et al., 2010; Giuliani et al., 2016). Similar dependencies arise in collective decisions over a shared Markov decision process (Alamdari et al., 2024) and in consensus-statement generation, where each selected token fixes the prefix for the remaining text (Blair and Larson, 2026). Participatory budgeting is run repeatedly (Faliszewski et al., 2023; Lackner, Maly, and Rey, 2021), and funding a project can affect the resources or projects available in later rounds; the paper says explicitly that the cited work establishes repeated budgeting, not this particular dependence. These examples motivate the model; we do not claim that our method has been deployed in them.

What the certificate measures. Devz\mathrm{Dev}_z is the strongest proportional deviation available to a coalition at state zz, but computing it requires a search over coalitions (Section 6 shows that a related decision problem is NP-complete). PFz\mathrm{PF}_z compares the best scalarized continuation available from zz with the scalarized continuation value of the evaluated policy. It is computed by one policy evaluation and one Bellman pass, always upper-bounds Devz\mathrm{Dev}_z, and equals 11 exactly when the policy is optimal for the weights from zz. Certz\mathrm{Cert}_z is a robust upper bound on PFz\mathrm{PF}_z when the transitions, and therefore the canonical weights, are uncertain. Neither quantity is a general safety guarantee.

What Section 7 guarantees. For each state and alternative, the model has a transition row: the probability distribution of the next state when that alternative is chosen in that state. Theorem 7.1 uses an ambiguity set, a collection of transition models consistent with the available information, together with intervals for the weights. Its bound is valid whenever the true model lies in that set and the weights lie in those intervals; it does not require every row to be estimated accurately. Theorem G.2 builds such a set from unevenly and adaptively collected data and assigns the whole probability simplex to unvisited rows. A valid bound can nevertheless be too conservative to guide a decision, or infinite, and with canonical weights the procedure may report insufficient coverage. Proposition G.1 shows that this is a limit of identification, not of our estimator: two elections can generate the same data distribution under the behaviour policy at every sample size while having deviation ratios 11 and RR at a reached state. What is not covered is error outside the model: a wrong state description, non-Markov dynamics, transition probabilities that change while data are collected, or misspecified utilities. The analysis is also tabular, so the number of rows, and the data needed to estimate them, can grow quickly with the size of the system. The last paragraph of Section 7 now states these points.

AuthorsOpenReview ↗

Response (2/2)

Online data collection and safe exploration. Appendix G.11 separates three questions: whether transition estimates remain reliable when data collection is adaptive; how to test a proposed exploration policy against our proportionality guarantee; and what can be said about adding a rarely chosen alternative to an existing policy.

1. Learning transitions adaptively. A transition row is the probability distribution over next states after selecting one alternative in one state. The learner may choose which alternatives to try using previous observations. The statistical assumption is that, whenever the same state--alternative pair is sampled, its next state is drawn afresh from the same fixed distribution. Theorem G.2 handles this sampling model when the number of observations is bounded in advance. Proposition G.2 also provides anytime confidence sets: with probability at least 1−δ1-\delta, they contain the true transition probabilities at every collection time, even if sampling continues for an unknown duration. This is why a policy chosen using the collected data can still be assessed by Theorem 7.1; no separate confidence correction for each proposed policy is needed.

2. Checking an exploration policy before deployment. The new Proposition G.4 gives a conditional way to preserve the paper's formal coalitional guarantee. Begin with a baseline policy π0\pi_0 (the policy used before exploration) that passes the test described below. At the start of an episode, propose a policy that sometimes chooses an under-observed alternative. Using the current uncertainty set, recompute that candidate's possible total expected utilities, its reciprocal voter weights, and its robust certificate Certz\mathrm{Cert}_z: a computable worst-case upper bound on proportional improvements available to coalitions. Deploy the candidate only if its own certificate satisfies Certz≤1+τ\mathrm{Cert}_z\le1+\tau at every state where protection is required, and its lower utility bounds are positive. Otherwise retain a fallback that passes the same test. Here τ≥0\tau\ge0 is the allowed tolerance. On the simultaneous confidence event, Theorem 7.1 implies PFz≤1+τ\mathrm{PF}_z\le1+\tau for the true transitions and Devz≤1+τ\mathrm{Dev}_z\le1+\tau wherever the exact deviation ratio is defined. Thus Certz\mathrm{Cert}_z is the admission test; the other two inequalities are its guarantees, not quantities that must be computed before deployment. The policy must be followed throughout the episode to which the test applies. With probability at least 1−δ1-\delta, the guarantee holds simultaneously for every policy the rule deploys, however the candidates were chosen. If a candidate's pessimistic denominator is zero at a protected state while the optimistic numerator is positive, its certificate is infinite and the candidate is rejected.

3. What a small exploration change costs. The new Proposition G.3 gives a separate, simpler bound. Let πε\pi_\varepsilon agree with the baseline π0\pi_0 except at one state, where it selects an exploratory alternative with probability ε\varepsilon and otherwise uses π0\pi_0's action distribution. For nonnegative rewards and any fixed nonnegative voter weights ww, the weighted continuation utility at every state is at least 1−ε1-\varepsilon times its baseline value:

∑iwiViπε(z)≥(1−ε)∑iwiViπ0(z).\sum_i w_iV_i^{\pi_\varepsilon}(z)\ge(1-\varepsilon)\sum_i w_iV_i^{\pi_0}(z).

With strictly positive fixed weights, a fixed uncertainty set, and a positive baseline pessimistic value, the corresponding robust certificate increases by at most a factor 1/(1−ε)1/(1-\varepsilon). This does not prove safety under the paper's canonical proportional claims: those claims use reciprocal total utilities, which change when the policy changes. Proposition G.4 addresses this by recomputing the candidate's claims and checking its certificate directly.

Limits. Passing the test guarantees only the paper's coalitional-deviation bound under the model and confidence assumptions; it does not establish physical or legal safety. A candidate may fail because an unobserved alternative leaves too much uncertainty, and a certified fallback is not guaranteed to exist. The procedure also does not ensure that exploration improves coverage, that the confidence sets shrink monotonically, or that the certificate becomes informative. A reliable simulator could sample rarely chosen alternatives without changing the live policy, although its accuracy would itself need justification. Finding a procedure that guarantees both informative exploration and continued certified deployment remains open.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.