Generative Social Choice: The Next Generation

We thank the reviewer for their feedback. We will improve the clarity of the proof of Theorem 3.1 and expand the discussion on its relation to Fish et al.; see also our response to Reviewer dWvn.

How do you justify your implementation of GEN queries in PROSE? Does your implementation still follow your theory?

Our theoretical results are agnostic to the implementation of the generative query. In this sense, we view different query implementations as approximate methods for solving the optimization problem defined by Equation (1).

In practice, we experimented with various implementations and ultimately adopted a two-step procedure. First, we identify agents $S' \subseteq S$ who are likely to approve the same statement at level $\ell$, using embeddings and clustering or nearest-neighbor techniques. Second, we prompt the LLM to generate a length-bounded statement that would be approved by all agents in $S'$. That is, we first identify a potential supporter group and then generate a statement intended to satisfy them. We adopted this approach because LLMs were unreliable at discovering such groups. Ultimately, when presented with a generative query, we always produce multiple candidate statements, from which we return the one with the highest number of supporters at level $\ell$.

Are there more general impossibility results where parameters are not fixed on special values?

Let us consider Theorem 3.4 as an example. The result is stated under the assumption of no error in how statements are evaluated (i.e., $\beta = \delta = 0$). Conditioned on this, the theorem shows that no algorithm can guarantee $(p,\frac{1}{\mu}\frac{|W|}{|W|\gamma+1})$-cBJR for any constant $p\in \mathbb{N}_0$.

The immediate implication of this is that such a guarantee is also impossible for any other value of $\beta$ and $\gamma$ (adding error will never help). One might ask whether Theorem 3.4 can be strengthened for non-zero $\beta$ or $\gamma$, but this seems unlikely: Increasing them intuitively only drives up $b$ in $(b,d)$-cBJR. However, Theorem 3.4. already shows that we cannot get a guarantee for any fixed $b$ even for $\beta=\gamma=0$. We will make this implication more explicit in the paper.

Do you think it is more reasonable to also take query costs into consideration?

This is an interesting point, but somewhat orthogonal to the primary focus of this paper. Our goal is to ensure that the output slate proportionally reflects user opinions – a challenging task in itself. That said, we agree this raises a possible direction for future work: one could consider imposing proportionality not only on the slate but also on the cost of the generation process. For example, one might impose that each agent "deserves" that $1 is spent on trying to generate consensus statements they like.

Does your theory also show something about the utility?

Yes and no. We do not provide formal guarantees on average utility across all instances. However, our BJR guarantees ensure that sufficiently large and cohesive agent groups are mapped to statements in the slate from which they derive a high utility. For highly homogeneous instances, this would imply a non-trivial average utility.

Why can the query output a statement with an accurate cost, but the comparison is made under $\mu$ error?

The role of the parameter $0 \leq \mu \leq 1$ is best understood in the absence of other errors. In this case, Equation (1) reduces to:

$\text{sup}(\alpha^*, S, \ell) \geq \max_{\alpha \in \mathcal{U} : c(\alpha) \leq \lceil \mu x \rceil} \text{sup}(\alpha, S, \ell)$

This means that the returned statement $\alpha^*$, even if it has cost $x$, must only be as well supported as any statement of cost up to $\mu x$.

We introduced this parameter because LLMs often undershoot the provided word budget in practice. Intuitively, the model would internally only search for statements in a more conservative space (shorter than allowed). As a result, we can only expect to identify the best statement among those of length at most $z$ (for some $z\leq x$). This behavior is captured by $\mu$, which quantifies this budget undershooting.

Is there any runtime evaluation on PROSE (and probably other benchmarks) and between different procedures in PROSE?

The runtime of PROSE is dominated by the response times of the LLM used in our query implementations. Our algorithm makes $\mathcal{O}(r \cdot n)$ generative queries and $\mathcal{O}(r \cdot n^2)$ discriminative queries. In our experiments, across the four datasets, PROSE used 9.6M–25.4M input and 53.5K–96.1K output tokens, with runtimes of 31–65 minutes on a single Intel i7-8565U CPU @ 1.80GHz. However, given the rapidly improving inference speeds of modern LLMs, we expect these runtimes to significantly decrease in the future.

By contrast, PROSE-UnitCost required around five times fewer resources: between 2.1M and 4.4M input tokens and 15.4K to 20.2K output tokens, with runtimes between 7 and 12 minutes.

We thank the reviewer for their comments! We will revise the paper to include a detailed discussion of the limitations of our experimental setup and LLM-based query implementations. We will also add a dedicated section elaborating on the relationship to Fish et al. (2024).

for the drug review datasets, why artificially rebalance the dataset to make the score distribution uniform or highlight extreme and central ratings?

The main reason for this design decision is that the original score distributions are quite degenerate, e.g., in the obesity dataset, over 70% of users give a score of 9 or 10. This skewness makes the summarization task quite simple, as nearly all users would support the same kind of statements.

Any reason why the budgets were 160 in the drug review experiments and 164 in the Bowling Green experiment?

The budget in each case was chosen to be divisible by the number of agents (n = 80 for drugs and n = 41 for Bowling Green). This avoids rounding artifacts in the Clustering baseline.

The measurement of correlation (line 1113-1117) is very strange and hard to interpret. Some more intuitive measures that I would have liked to see: the inter-rater reliability score, the fractions of agent-statement pairs where the difference in labels is 0 and 1, and most comprehensive, the full distribution of label discrepancies for each agent-statement pair.

The inter-rater reliability score (via Cohen's kappa) for the two implementations is 0.41. For 39/51 users (76%), both implementations return higher mean scores on upvoted statements than downvoted statements; for 8/51 users (16%), one implementation returns higher mean scores and the other lower mean scores on upvoted statements (each implementation is correct 4/8 times). Disaggregating by user and looking at all 1275=51*5*5 (agent, upvoted statement, downvoted statement) pairs, both queries agree on 53% of pairs, CoT is correct and PROSE is incorrect on 12% of pairs, PROSE is correct and CoT is incorrect on 13% such pairs, and both are incorrect on 21% such pairs.

Differences in democratic processes compared to Fish et al. (2024) and missing experimental comparison

Our democratic process is related to the one of Fish et al. but differs in several aspects:

1. We account for statements having varying costs (e.g., word lengths).
2. Fish et al.’s generative query, given a set of agents $S$ and an integer $r$, returns the statement maximizing the $r$-th highest utility among users in $S$. In contrast, our query takes a utility threshold $\ell$ and returns a statement approved by the maximum number of agents in $S$ at level $\ell$.
3. Related to 2., our algorithm iteratively considers decreasing utility levels to decide which statement to add next, which is important for deriving our proportionality guarantees under approximate queries.

As for the absence of a direct experimental comparison: unfortunately, the implementation by Fish et al. (2024) is not applicable to our datasets, as it requires highly structured user input (e.g., ratings of predefined statements and answers to survey questions). By contrast, our work focuses on settings with unstructured textual input.

We opted not to reimplement their queries for unstructured data, as this would introduce substantial ambiguity due to subjective implementation choices. Instead, we included the PROSE-UnitCost baseline, which aligns with the core assumption of Fish et al. (2024) – namely unit-cost of statements – but uses our own query implementations to ensure comparability.

As a side note, we highlighted that PROSE does not require hyperparameter tuning because it flexibly adapts to varying problem instances without requiring dataset-specific adjustments (such as setting the number of output statements, clustering granularity, or query wording). However, we agree that the term is misleading and we will reword it.

In other words, I feel like the unit cost version of the model makes more sense, but with the addition that statements should be labeled with the proportion of agents who support them at some meaningful level $\ell$.

We appreciate this suggestion and believe that the answer is dependent on the intended application. Our model is particularly well-suited for settings where the reader’s attention is limited. For instance, in online democratic deliberation platforms (c.f. Bowling Green dataset), larger groups may reasonably expect a more detailed representation of their opinions: That is, a greater share of the limited attention budget of the reader is devoted to articulating their positions in more depth. Moreover, controlling the total slate length while leaving the number of statements flexible is a more general advantage of our approach.

That said, we note that our theoretical framework also applies to the proposed model. Further, PROSE could be adapted to return, along with each statement, a support value, and then use that value to define the cost of the statement.

We thank the reviewer for their review.

How do you quantify the tolerance and error made by Chat GPT 4o output? How do you measure the accuracy from the language?

The general approach taken in this paper is to design a mechanism (Algorithm 1) that is agnostic to the specific implementation of the underlying queries. Crucially, we show that the mechanism continues to satisfy an approximate notion of proportional representation even when the answers to the queries are subject to error. Importantly, these theoretical guarantees hold without the mechanism needing to know the magnitude of the error in the query answers.

Turning to the empirical evaluation of our implementation using GPT-4o: we assess the quality of the discriminative query implementation in Appendix D.5. Specifically, we use a dataset in which users have written comments and cast upvotes or downvotes on comments written by others. We provide our discriminative query implementation with access to a user’s own comments and task it with predicting how the user rated comments they voted on. This allows us to measure prediction accuracy against known ground truth.

Unfortunately, a direct evaluation of the generative query is more challenging, as it would require knowledge of the optimal statement among a virtually infinite set of possibilities – a task that is infeasible in practice.

Finally, we assess the quality of the resulting slates–which represent the ultimate output of our process–through experimental comparison with baselines (see Table 1). Here, we report (i) the average utility that agents derive from their assigned statement in the slate and (ii) the fraction of BJR violations, which serves as a proxy for the number of underrepresented groups.

Their application is about social choice but their study can be potentially applied for unethical reasons. E.g. I would not leave a political decision be taken or summarized by an LLMs. But for what they are showing this could be very much happening. However, I am not saying they are promoting that.

Thank you for raising this concern. As we mention in our impact statement, "the use of LLMs to rate and generate statements introduces specific risks that must be carefully addressed before deployment in real-world settings," including "bias," (lack of) "transparency," and "manipulation." This is doubly true in the context of political decision-making, and we will expand the impact statement to make this absolutely clear.

We thank the reviewer for their review.

Regarding the evaluation method: Using total user utility as the main metric in evaluation does not immediately come across as the best way to quantify democracy, but neither was I sure how to make it better –underrepresented groups are still going to be largely neglected in final result generation and their voices deserve to be heard.

We fully agree that giving minorities a voice is a fundamental aspect of democratic decision-making. This is precisely why our algorithm is explicitly designed with proportional representation in mind – if a group of agents constitutes x% of the electorate, it should be able to exert control over x% of the slate. For example, if the budget allows for 200 words and we have 100 agents, even a minority group of 5 agents will control 10 words, thereby ensuring that a brief summary of their perspective will be present in the final slate.

To formally capture this ideal, we adopt the axiom of Balanced Justified Representation (BJR). Our theoretical analysis demonstrates that our method satisfies an approximate form of this axiom, even under noisy query implementations (Theorem 3.2). In our experimental evaluation, we measure both total utility but also the frequency of BJR violations (see Table 1, fourth column), which can be interpreted as the fraction of groups whose voices are not adequately reflected in the produced slate, i.e., they are "underrepresented". Across all datasets, PROSE consistently yields fewer BJR violations than the baselines, empirically confirming its ability to give a proportional voice to all groups.

Also want to learn how the algorithm addresses moral dilemmas such as would it choose to kill one to save a hundred. I understand the design of such metrics would never be perfect but still want to learn the trade offs being considered here and how does the pareto surface look like.

Our algorithm does not impose any specific normative stance on moral dilemmas. Instead, it aims to proportionally summarize the diversity of user opinions, even if these are mutually contradictory. For instance, if the electorate is divided on whether it is ever justifiable to harm one person to save many, the resulting slate might include both: “Harming a person is never ethically justified.” and “Saving many can justify harming an individual.” In this sense, our method captures the full spectrum of views rather than resolving ethical trade-offs by adhering to a particular notion.

In AI for governance works we need to think very critically with regard to what kind of value coordinates are we essentially subjecting the AI to because at the end of the day that's the core added value from human if one day say 99% of the work are automated by AIs.

We fully share the concern about normative alignment in AI systems. In our setting, however, PROSE is not designed to encode or enforce specific value judgments; rather, it is a tool for faithfully summarizing the input opinions. In particular, the quality and normative content of the output slate largely depend on the user-provided statements. (Broader concerns regarding bias in the underlying LLMs used for query answering are important and discussed in our impact statement.)