- 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
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 , 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 . The alternative is to compare continuation utilities after a state 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 . 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 for every voter. A different policy, which satisfies the initial requirement, gives every voter . The ratio approaches .
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 , 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 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 and increase every remaining coalition's share , which can shrink the Core (Proposition D.1). For example, with alternatives and , the profile is in the fractional Core with three voters; after deleting voter 3, voter 1 alone has share and blocks, since . 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.
Response (3/3)
Q5. What is continuation stability? Fix positive weights and a state . Voter 's claim at is , and coalition 's share is . With the canonical weights , every claim is at the start, so the share equals there. Afterwards, each claim compares the utility the member can still expect from 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 if some continuation from gives for every member, with strict inequality for at least one. In words, the coalition may abandon the policy at and choose any continuation, but it receives only its share of what that continuation would give. A policy is continuation-stable at 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 , 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 . For positive utilities, the logarithm is strictly increasing, so maximizing the product is equivalent to maximizing , which has the separable form with . 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 still maximizes an objective of the same form from any state , with voter weights proportional to , where and are the ex-ante and continuation utilities. Corollary 4.1 asks which makes these weights proportional to , the initial weight scaled by the ratio of continuation utility to ex-ante utility. This forces to be constant, so . 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.
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.
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 exceeds the exact deviation ratio by less than 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.145 (middle half 0.096 to 0.178), and it increases in all 40 paired elections. On the path to a Nash optimum, the initial-state deviation ratio falls to a median of 1.025 by t=0.9. With sparse behaviour-policy sampling, the certificate exceeds the one from uniform sampling by paired medians of 0.419, 0.646, and 0.754 at 800, 4000, and 16000 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.