Policy Aggregation
Authors: Parand A. Alamdari
Soroush Ebadian
Ariel D. Procaccia
Venue: NeurIPS 2024 poster (2024)
Keywords: Markov decision process
reinforcement learning
AI alignment
Primary area: algorithmic_game_theory

Abstract: We consider the challenge of AI value alignment with multiple individuals that have different reward functions and optimal policies in an underlying Markov decision process. We formalize this problem as one of *policy aggregation*, where the goal is to identify a desirable collective policy. We argue that an approach informed by social choice theory is especially suitable. Our key insight is that social choice methods can be reinterpreted by identifying ordinal preferences with volumes of subsets of the *state-action occupancy polytope*. Building on this insight, we demonstrate that a variety of methods — including approval voting, Borda count, the proportional veto core, and quantile fairness — can be practically applied to policy aggregation.

Policy Aggregation
Parand A. Alamdari University Toronto Vector Institute parand@cs.toronto.cc
Soroush Ebadian"
University of Toronto soroushêcs. toronto. edu
toronto. edu
Ariel D. Procaccia
Harvard University
arielpro@seas harvard.edu
Abstract
We consider the challenge of Al value alignment with multiple individuals that have different reward functions and optimal policies an underlying Markov decision process. We formalize this problem one of policy aggregation, where the goal is to identify desirable collective policy. We argue that an approach informed by social choice theory especially suitable. Our key insight that social choice methods can be reinterpreted by identifying ordinal preferences with volumes of subsets of the state aacten occupancy polytope. Building on this insight, we demonstrate that a variety of methods including approval voting, Borda count, the proportional veto core, and quantile fairness can practically applied policy aggregation.
Introduction
Early discussion of AI value alignment had often focused on learning desirable behavior from an individual teacher, for example, through inverse reinforcement learning [27, 1]. But, in recent years, the conversation has shifted towards aligning AI models with large groups of people or even entire societies. This shift is exemplified a policy level by OpenAl's "democratic inputs to Al" program [41] and Meta's citizens' assembly on Al governance [8], and at technical level by the ubiquity of reinforcement learning from human feedback [30] as a method for fine-tuning large language models.
We formalize the challenge of value alignment with multiple individuals problem that view poddamental-polic aggregation. Our starting point is the common assumption that the environment be represented Markov decision process (MDP). While the states, actions and transition functions are shared by all agents, their reward functions - which incorporate values, priorities or subjective beliefs beliefs-mas may be different. In particular, each agent has its own optimal policy in the underlying MDP. Our question is this: How should we aggregate the individual policies into desirable collective policy?
naïve answer is to define a new reward function that is the sum of the agents' reward functions (for each state-action pair separately) and compute optimal policy for this aggregate reward function; such a policy would guarantce maximum utilitarian social welfare. This approach has a major shortcoming, however, in that it is sensitive affine transformations of rewards, so, for example, if we doubled one of the reward functions, the aggregate optimal policy may change. This is an issue because each agent's individual optimal policy is invariant to (positive) affine transformations of rewards, so while it is possible to recover a reward function that induces an agent's optimal policy by
"Equal contribution. Authors are listed alphabetically.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

observing their actions over time," it is impossible to distinguish between reward functions that are affine transformations of each other. More broadly, economists and moral philosophers have long been skeptical about interpersonal comparisons of utility [19] due to the lack of universal scale - an issue that is especially pertinent in our context. Therefore, aggregation methods that are invariant to affine transformations are strongly preferred.
Our approach. To develop such aggregation methods, we look social choice theory, which typically deals with the aggregation of ordinal preferences. To take a canonical example, suppose agents report rankings over m alternatives. Under the Borda count rule, each voter gives m points to the alternative they rank in the k'th position, and the alternative with most points overall is selected.
The voting approach can be directly applied to our setting. For each agent, it is (in theory) possible to compute the value of every possible (deterministic) policy, and rank them all by value. Then, any standard voting rule, such as Borda count, can be used to aggregate the rankings over policies and single out desirable policy. The caveat, of course, is that this method is patently impractical, because the number of policies is exponential in the number of states of the MDP.
The main insight underlying our approach is that ordinal preferences over policies have much more practical volumetric interpretation in the state-action occupancy polytope O. Roughly speaking, a point in the date-nction occupancy polytope represents (stochastic) policy through the frequency it is expected to visit different state-action pairs. If a policy is preferred by an agent to a subset of policies O', its "rank" is the volume of O' as fraction of the volume of O. The "score" of a policy under Borda count, for example, can be interpreted as the sum of these "ranks" over all agents.
Our results. We investigate two classes of rules from social choice theory, those that guarantee notion of fairness and voting rules. By mapping ordinal preferences to the state-action occupancy polytope, we adapt the different rules to the policy aggregation problem.
The former class is examined in Section 5. As a warm-up we start from the notion of proportional veto core; it follows from recent work by Chaudhury et al. [7] that a volumetric interpretation of this notion is nonempty and can be computed efficiently. We then turn to quantile fairness, which was recently introduced by Babichenko et al. [4]; we prove that the volumetric interpretation of this notion yields guarantees that are far better than those known for the original, discrete setting, and we design computationally efficient algorithm to optimize those guarantees.
The latter class is examined in Section 6; we focus on volumetric interpretations of a-approval (including the ubiquitous plurality rule, which is the special case of a 1) and the aforementioned Borda count. In contrast to the rules studied in Section 5, existence is a nonissue for these voting rules, but computation is a challenge, and indeed we establish several computational hardness results. To overcome this obstacle, we implement voting rules for policy aggregation through mixed integer linear programming, which leads to practical solutions.
Finally, our experiments in Section 7 evaluate the policies returned by different rules based on their fairness; the results identify quantile faimess as especially appealing. The experiments also illustrate the advantage of our approach over rules that optimize measures of social welfare (which are sensitive to affine transformations of the rewards).
2 Related Work
Noothigattu al. [28] consider a setting related to ours, in that different agents have different reward functions and different policies that must be aggregated. However, they assume that the agents' reward functions are noisy perturbations of ground-truth reward function, and the goal is to learn an optimal policy according to the ground-truth rewards. In social choice terms, our work is akin to the typical setting where subjective preferences must be aggregated, whereas the work of Noothigattu et al. [28] is conceptually similar to the setting where votes are seen as noisy estimates of ground-truth ranking [39,9 9, 6].
Chaudhury et al. [7] study a problem completely different from ours: fairness in federated learning. However, their technical approach served as an inspiration for ours. Specifically, they consider the proportional veto core and transfer it to the federated learning setting using volumetric arguments, by
2 And we assume this is done accurately, in order focus the essence of the policy aggregation problem.

---

considering volumes of subsets in the space of models. Their proof that the proportional veto core is nonempty carries over to our setting, as we explain in Section 5.
There is a body of work on multi-objective reinforcement learning (MORL) and planning that uses a scalarization function to reduce the problem to single-objective one [32, 21]. Other solutions to MORL focus on developing algorithms to identify set of policies approximating the problem's 's Pareto frontier [38]. A line of work more closely related ours focuses on fairness sequential decision making, often taking the scalarization approach to aggregate agents' preferences by maximizing a (cardinal) social welfare function, which maps the vector of agent utilities to a single value. Ogryczak et al. [29] and Siddique et al. [34] investigate generalized Gini social welfare, and Mandal and Gan [25], Fan al. [13] and Ju et al. [23] focus on Nash and egalitarian social welfare. Alamdari et al. [3] study this problem in a non-Markovian setting, where fairness depends on the history of actions over time, and introduce concepts to assess different fairness criteria at varying time intervals. shortcoming of these solutions is that they are not invariant to affine transformations of rewards- - a property that is crucial our setting, as discussed earlier.
Our work is closely related to the pluralistic alignment literature, aiming to develop AI systems that reflect the values and preferences of diverse individuals [35, 10]. Alamdari al. [2] propose framework in reinforcement learning in which an agent learns to act in way that is considerate of the values and perspectives of humans within a particular environment. Concurrent work explores reinforcement learning from human feedback (RLHF) from a social choice perspective. where the reward model based on pairwise human preferences, often constructed using the Bradley-Tery model [5]. Zhong et al. [42] consider the maximum Nash and egalitarian welfare solutions, and Swamy et [36] propose a method based on maximal lotteries due to Fishburn [14].
3 Preliminaries
For / E N, let = (1,2,...... For a closed set S, let A denote the probability simplex over the set S. We denote the dot product of two vectors (zr, y) = E Ze Y/ for 2; y R A halfspace in Rd determined by E Rd and b E R is the set of points satisfying {a E R (z, w) < b}. A polytope O C Rd is the intersection of finite number of halfspaces, i.e., convex subset of the d-dimensional space g determined by a set of linear constraints {xr Ax & b} where A E BR- is a matrix of coefficients of & linear inequalities and b R
3.1 Multi-Objective Markov Decision Processes
multi-objective Markov decision process (MOMDP) is a tuple defined as M = PI,.,., R.,) for the average-reward case and (S, . P, RI...., Rn, 7) for the discounted-rewart case, where S is a finite set of states, A is a finite set of actions, and P (S x A) - (SS) is the transition probability distribution. (( Qg, $1+1) is the probability of transitioning to state 81+1 by taking action a in st. For E [n]. R, x A > IR is the reward function the ith agent, the initial state is sampled from d ASS), and 7 E (0, 1] is the discount factor.
(Markovian) policy (a)ss) ) is a probability distribution over the actions a E A given the state & E S. A policy is deterministic if at each state one action is selected with probability of 1, and otherwise it is stochastic. The expected average return of agent for a policy π and the expected discounted defined over infinite time horizon as
return of agent i for policy
1 B...
T
Ri(ss, an) [T( = (1-7)
J. lim
Ri si
T-
where the expectation is over the sate-action pairs time t based on both the policy and the transition function P.
Definition 1 (state-action occupancy measure). Let Pt be the probability measure over states at time t under policy π. The state-action occupancy measure for state s and action a is defined as
1 E
Σ r-1 P).() ((((s((a)s)) (s) = 7) Σ (s)(((s
(s, a)
lim T
-
For both the average and discounted cases, we can rewrite the expected return as the dot product of the state-action occupancy measures and rewards, that is, (TT) E(,,)) d, (s,a) as, =
3

---

Rd). In addition, the policy can be calculated given the oceupancy measure as T(als) = d ds d=(s, if (s) > O, and x x(ass) 1/|A| otherwise.
Definition 2 (state-action occupancy polytope [31, 40]). For a MOMDP M in the average-reward case, the space of valid state-uction occupancies is the polylope
Jave
gavg d
0,
B (8,a) = -, d (8,
Σ
Σ Ep's, (, s'
5,8
We similarly define this polytope for the discounted- reward case in Appendix A.
A mechanism receives MOMDP and aggregates the agents' preferences into policy. An economical efficiency axiom in the social choice literature is that of Pareto optimality.
Definition (Pareto optimality). For a MOMDP M and > 0, a policy π is e-Pareto optimal if there does not exist another policy Tt' such that J:(T'') b J=(T) + e for all i E N, with strict inequality for at least one agent. For e = 0. we simply call such policies Pareto optimal.
We call a mechanism Pareto optimal if it always returns a Pareto optimal policy. In special cases where all agents unanimously agree on an optimal policy, Pareto optimality implies that the mechanism will return one such policy. We discuss Pareto optimal implementations of all mechanisms in this work.
3.2 Voting and Social Choice Functions
In the classical social choice setting, we have a set of n agents and a set C of m alternatives. The preferences of voter E [n] is represented as a strict ordering over the alternatives 0, [m] - C equal to (1) 7; (2) > ... >; (m), where Ci >; C2 denotes agent prefers e₁ over o2 for , E C. A (possibly randomized) voting rule aggregates agents' preferences and returns an alternative or a distribution over the alternatives as the collective decision.
Positional Scoring Rules. A positional scoring rule with scoring vector 3 (81 ($1...., 8m) such that 81 E $2 3. 2 Sm works as follows. Each agent gives a score of $1 to their top choice, a score of 32 to their second choice, and so on. The votes are tallied and an alternative with the maximum total score is selected. A few of the well-known positional scoring rules are: Plurality: (1, 0, Ol.,.....), Borda: (m- 1, m 2...., 1, 0), k-approval: (I...., 1,0..... 0) with & ones.
4 Occupancy Polytope as the Space of Alternatives
In a MOMDP M, each agent i incorporates their values and preferences into their respective reward function RG Agent prefers π over ' if and only if π achieves higher expected return, J₁(x) J; J=(').. and is indifferent between two policies π and n' if and only if (T(T) = J((x'). As discussed before, given a state-action occupancy measure dz in the state-action occupancy polytope O we can recover the corresponding policy Therefore, we can interpret O as the domain of all possible alternatives over which the n agents have heterogeneous weak preferences (with ties). Agent prefers dz to dz in O if and only if they prefer ı to x². We study the policy aggregation problem through this lens; specifically, we design or adapt voting mechanisms where the (continuous) space of alternatives is O and agents have weak preferences over them determined by their reward functions R2,
Affine transformation and reward normalization. A particular benefit of this interpretation, as mentioned before, is that all positive affine transformations of the reward functions, i.e., aR; + b for all E R2 and E R. yield the same weak ordering over the polytope. Hence, we can assume without loss of generality that J₁(T) E [0, 1]. Further, we can ignore agents that are indifferent between all policies, i.e., ming J,(T) max, JT(),, and normalize reward functions R& 6- R, m,n (xxx)
J=(=)- (i(m)-miig min. J[( such that min, J((T) 0 and max, J;(TT) = 1. The relative ordering of the policies does not change since for all points d, E O have Σ.a d=(s)))= 1.
Volumetric definitions. A major difference between voting over a continuous space of alternatives and the classical voting setting is that the domain of alternatives is infinite and not all voting mechanisms can be directly applied to the policy aggregation problem. In particular, various voting rules require reasoning about the rank of an alternative or the size of some subset of alternatives. For instance, the Borda count of an alternative over a finite set of alternatives is defined as the number

---

(or fraction) of candidates ranked below In the continuous setting, for almost all of the mechanisms that we discuss later, we use the measure or volume of a subset of alternatives to refer to their size. For measurable subset O' S O, let vol(O") denote its measure. The ratio vol(O')/vol(() is the fraction of alternatives that lie in O' A probabilistic interpretation is that for a uniform distribution over the polytope O, vol(O")/ (O) denotes the probability that policy uniformly sampled from O lies in O', We can also define the expected return distribution of an agent over O as a random variable that maps a policy to its expected return, i.c., one that maps dz O to (da, R&). The pdf and edf of this r.v. defined below.
Definition 4 (expected return distribution). For a MOMDP M and v E R, the expected return distribution of agent i E [n] is defined as
8(v - (z, R.)) dx, F((v) F((D== =(0)=={-
Ja=- f((x) dr vol n (I, Ra) < u))
f((v) vol(O) JEO
vol(O)
where and F; the pdf and edf of the expected return distribution and 8(.) is the Dirac delta function indicating u (x, R.).
useful observation about fi. the pdf, is that it is unimodal, i.e., increasing up its mode mode(fi) arg wa (v) and decreasing afterwards, which follows from the Brunn-Moe Miinn--knkkkkki inequality [17]. Since fi (pdf) is the derivative of F; (cdf), the unimodality of f; implies that F; is convex function in (-oc, mode(f.) fi)l and concave in (mode(ft), co).
In our algorithms, use subroutine that measures the volume of polytope, which denote by vol-comp( { (Ax & b}). Dyer et al. [12] designed a fully polynomial time randomized approximation scheme (FPRAS) for computing the volume of polytopes. We report the running time of algorithms in terms of the number of calls to this oracle.
5 Fairness in Policy Aggregation
In this section, we utilize the volumetric interpretation of the state-action occupancy polytope to extend fairness notions from social choice to policy aggregation, and we develop algorithms to compute stochastic policies provably satisfying these notions.
5.1 Proportional Veto Core
The proportional veto was first proposed by Moulin [26] in the classical social choice setting with a finite set of alternatives where agents have full (strict) rankings over the alternatives. For simplicity, suppose the number of alternatives m is multiple of n. The idea of the proportional veto core is that 2% the agents should be able to veto =% of the alternatives. More precisely. for an alternative to be in the proportional veto core, there should not exist coalition S that "block" using their proportional veto power of S1/n.. S blocks if they can unanimously suggest m(1 - ISl/n) candidates that they prefer
For instance, if is in the proportional veto core, it cannot be the case that a coalition of 60% of the agents unanimously prefer 40% of the alternatives to c.
Chaudhury et al. [7] extended this notion to continuous domain of alternatives in the federated learning setting. We show that such an extension also applics to policy aggregation.
Definition 5 (proportional veto core). Let e e (0, 1/n). For coalition of agents S S. [n]. let veto(S) = Sllfn be their veto power. A point d= E O is blocked by a coalition S if there exists subset O' C O of measure vol(O") (vvl() > veto(S) + c such that all agents in prefer all points in O' to dz, ie., dxy ii dz for all d E O' and i E S. A point dz is in the c-proportional veto core if it is not blocked by any coalition.
A candidate in the proportional veto core satisfies desirable properties that are extensively discussed in prior work [26, 7, 24, 22]. It is worth mentioning that any candidate in the c- e-prpoortooall veto core, besides the fairness aspect, is also economically efficient it satisfies c-Pareto optimality. This holds since the grand coalition 5 = [n] can veto any c-Pareto dominated alternative.
Moulin [26] proved that the proportional veto core is nonempty in the discrete setting and Chaudhury al. [7] proved for the continuous setting. The following result is corollary of Theorem 1 of Chaudhury et al. [7].
5

---

ALGORITHM I: Seq. c- c-Prop. Veto Core [7]
ALGORITHM 2: c-Max Quantile Fairness
Oo 5 O, 8 5 m+1
Procedure www.aatttl---esbbleeleeee
0, { E O (r. Ra) á F.) E [v]]
for = to do
if O is a feasible linear program then return
Using binary search find of E [0. 1] s.t.
True else return False
vol(O;-1n ((z, Ra) E ot R 6. vol(())
Using binary search find maximum g E [0, q- q-quantile sesiileffaasee feasible() is feasible
1] s.t.
O, + 0.-1 ((x, R.) e vf) return a welfare maximizing point du On
return welfare maximizing point d,, E C,2
Theorem I. Let e E (0, 1/n). For a policy aggregation problem, the e-proportional veto core is nonempty, Furthermore, such policies can be found in polynomial time using (llog(//e) many calls per agent to vol-comp.
We refer the reader to the paper of Chaudhury et al. [7] for the complete proof, and provide a high-level description of Algorithm 1, which finds a point in the proportional veto core. Algorithm I iterates over the agents and lets the ith agent "eliminate" roughly 1/n vol(O) of the remaining space
of alternatives. That is, agent finds the hyperplane H; = { (1x, Ra) & ot such that its intersection with 0;-1 (the remaining part of O at the ith iteration) has a volume of approximately vol(O)/n. This value, for each agent, can be found by doing a binary search over of to a precision of [og - c, v,] by ((log(1/e)) calls to the volume estimating subroutine vol-comp."
Pareto optimality. We briefly discuss why Algorithm is Pareto optimal. During the ith iteration, the space of policies is contracted by adding linear constraint of the form J:(T) > of_ If the returned policy æ (derived from dz) is Pareto dominated by another policy x', then x' ) 2 J((T) > oz with the earlier inequality being strict for at least one agent. Therefore, dx E On and n' achieves a higher social welfare, which is a contradiction. The same argument can be used to establish the Pareto optimality of other mechanisms discussed later; each of these mechanisms searches for a policy that satisfies certain lower bounds on agents' utilities, from which celfare-maximizing Pareto optimal policy can be selected.
would satisfy all these linear constraints as J,(T))
5.2 Quantile Fairness
Next, we consider an egalitarian type of fairness based on the occupancy polytope, building on very recent work by Babichenko et al. [4] in the discrete setting; surprisingly, we show that it is possible to obtain stronger guarantees in the continuous setting.
Babichenko et al. [4] focus the fair allocation of set of m indivisible items among agents, where each item must be fully allocated to a single agent. They quantify the extent an allocation A is fair to an agent by the fraction of allocations over which prefers A (note that the number of all discrete allocations is )) In other words, if one randomly samples an allocation, the fairness is measured by the probability that A is preferred to the random allocation. An allocations is q-quantile fair for E [o, 1] if all agents consider this allocation among their top q-quantile allocations. Babichenko al. [4] aim to find a universal value q such that for any fair division instance. a q-quantile fair allocation exists. They make an interesting connection between q-quantile fair allocations and the Erdōs Matching Conjecture, and show under the assumption that the conjecture holds, /quanilue fair allocations exist for all instances.*
We ask the same question for policy aggregation, and again, key difference is that our domain of alternatives is continuous. The notion of q-quantile fairness extends well to our setting. Agents assess the fairness of policy based on the fraction of the occupancy polytope (i.e., the set of all policies) to which they prefer n, or equivalently, the probability that they prefer the chosen policy to a randomly sampled policy.
Definition 6 (g-quantile fairness). For a MOMDP M and E [0, 1], a policy n is q-quantile fair ffr every agent i [ni]. is among i's top q-fraction of policies, vol(Ont (x, R.) < J.(T))) > vo)).
II is important check the non-emptyness of the search space O as over-estimation of et could lead an empty feasible region. "This result is for arbitrary monotone valuations. For additive valuations, they show 0.14 quantile fair allocations always exist without any assumptions.

---

We show that a (1/e) Lquantile fair policy always exist and that this ratio is tight; note that this bound twice as good as that of Babichenko et al. [4], and it unconditional. We prove this by making a connection to an inequality due to Grünbaum [17]. The centroid of a polytope P is defined as centroid( P)
Jeep do Jecp1de
Lemma (Grunbaum's 's Inequality), Let P be a polytope and w direction in R.. For the halfspace f 0}, it holds that
H = {ol (w, ( P))
d a vol(P d
d
d
<
<
a1+1)
vol(P)
d dd+1
e
Furthermore, this is tight for the n-dimensional simplex.
Theorem 2. For every MOMDP M, there always exist q-quantile fair policy where q ( and ( [S] |A]. Note that q 3
7%. Furthermore, this bound is tight: For any E, there an instance with a single state and actions where no q q-quantile fair policy exists for any q > (Z
Proof. First, show that the centroid of the occupancy polytope policy for the aformentioned g. Since O is a subset of the (n - 1) )--smpee (see Definition 2), O has nonzero volume in some lower dimensional space l' & |S| [A| [A|-1. 1. By invoking Grunbaum's inequality (Lemma 1) with w; being equal to RG projected to the e' ('-dimensional subspace for all
(entroid(O)) ( q-quantile fair
agents E [n], we have that vol(O n H.) > (F4T)) )² vol(()) where H; {(- wx) > 0}
{(c, Ra) > J.())). Since l' E 1, we have (E44)* )e >> (-) which completes the proof.
To show tightness, take a MOMDP with a single state S = {s} hence a constant transition function P(.)
and l actions A = fai...., ae) and & agents. The reward function of agent i is (, a,) = 1 and 0 otherwise. The state-action occupancy polytope of this MOMDP is the (e- ---mn-dmmensional simplex O = (E. dx a) = 1 E [R Take any point in d, E O. There exists at least agent i that has Jz(d,) ds, < J. Take the halfspacc H, {zz, R₂) })- Observe that H, O is equivalent to smaller -ddimenniala simplex {E, du (s, a) 1 #
which has volume of vol ((1 4)) ( E-1 vol(O). v)) Therefore, vol(())
vol(OnH.)
The centroid of the occupancy polytope, as per Theorem 2, attains a worst-case measure of quantile- fairness. However, the centroid policy can be highly suboptimal as it disregards the preferences of the agents involved. For instance, there could exist a 99%-quantile fair policy. To this end, we take an egalitarian approach and aim to find q-quantile fair policy with the maximum g.
Max quantile fair algorithm. Algorithm searches for the optimal value q", for which a qu-unttiee fair policy exists, and gets close to q" by a binary search. To perform the search, we need subroutine that checks, for a given value of g. if q-quantile fair policy exists. Suppose we have the g-quantile expected return F." (q) for all i, that is. the expected return amount ey such that (v.) = q. Then, the problem of existence of q-quantile fair policy is equivalent to the feasibility of the linear program far E O (x. R₂) > F- (q). E [n]}. which can be solved in polynomial time. Importantly, after finding good approximation of q. there can be infinitely many policies that are q-quantile fair and there are various ways to select the final policy after finding the value q. As mentioned earlier, desirable efficiency property is Pareto optimality; to satisfy it, one can return the policy that maximizes the sum of agents' expected returns among the ones that are q-quantile fair. Finally, to calculate (q), we can again use binary search to get 5 close to the value U; for which F.(e:) = using Olog 1/8) calls vol-comp. The discussion above is summarized below.
Proposition 3. Assuming an optimal oracle for F Algorithm finds a q-quantile fair policy that is close to the optimal value in polynomial time with (llog(1/E) per agent calls to the oracle. A 8 6-approximation to F." (q) can be computed using (log(1/8)) calls to vol-comp.
6 Policy Aggregation with Voting Rules
In this section, we adapt existing voting rules from the discrete setting to policy aggregation and discuss their computational complexity.
7

---

ALGORITHM 3: Approvalss MILP
ALGORITHM 4: c- e-Borda count MILP
compute F. (aa for all i E [n] solve the mixed integer linear program
compute Fi- "kke) for all i E [n] and & E [+] solve the mixed integer linear program
max Diet a;
max
Σ -E ai,k (Fi(ke) - P
s.t. a, F. (a) (d,, de E a a {0,1)
We [r] e [n]
s.t.
0i, ke & (dm; Ra) Vi [ni
d, O, 0.k E (0,1),
vi 1 [1/c]
return a Pareto optimal policy subject to max a-approval {i a; = 1]
return a Pareto optimal policy subject to max Borda score
Plurality. The plurality winner is the policy that achieves the maximum number of plurality votes or "approvals," where agent approves policy if it achieves their maximum expected return ((())= = max,' J((x') = 1. Hence the plurality winner is policy in arg max, Eie(n) [[)( = 1]. This formulation does not require the volumetric interpretation. However, in contrast to the discrete setting where one can easily count the approvals for all candidates, we show that solving this problem in the context of policy aggregation is not only NP-hard, but hard to approximate up to factor of a 1 1/n1/2-e. We establish the hardness of approximation by reduction from the maximum independent ser problem [20]; we defer the proof to Appendix B.
Theorem 4. For any fixed E (0, 1), there is polynomial-time n:72 c approximatiio algorithm for the maximum plurality score unless NP.
Nevertheless, we can compute plurality in practice, as we discuss below.
o-approval. We extend the k-approval rule using the volumetric interpretation of the occupancy polytope, similarly to the g-quantile faimess definition. For some a E [0, 1]. agents approve a policy if its return is among their top fraction of O, i.e., (=)) > a. The a-approval winner is a policy that has the highest number of a-approvals, so it is in arg max, Eigjn) (J((() > a]. Note that plurality is equivalent to 1-approval. It is worth mentioning that there can be infinitely many policies that have the maximum approval score and, avoid suboptimal decision, one can return a Pareto optimal solution among the set of a-approval winner policies.
Theorem 2 shows that for a 1/e, there always exists policy that all agents approve, and by Proposition such policies can be found in polynomial time, assuming access to an oracle for volumetric computations. Therefore, the problem of finding a-approval winner is "easy" for a E 1/c). In sharp contrast, for a = aal--nmmn namely, plurality- - Theorem 4 gives a hardness of approximation. The next theorem shows the hardness of computing a-approval for a (7/8, 1] via reduction from the MAX-2SAT problem. We defer the proof to Appendix B.
Theorem 5. For a (7/8, 1), computing a policy with the highest a-approval score Na-hard. This even holds for binary reward vectors and when every F; has closed form.
Given the above hardness result, compute the a-approval rule, we turn mixed-integer linear programming (MILP). Algorithm 3 simply creates n binary variables for each agent i indicating whether a-approves the policy, i.e., (J((())) > a which is equivalent to J((T)) > (a)) To encode the expected return requirement for agent to approve policy precompute F, (a). This can be done by binary search similar to Algorithm 2. Importantly, Algorithm 3 has one binary variable per agent and only n constraints which is key to its practicability.
linear constraint, we
Borda count. The Borda count rule also has natural definition in the continuous setting. In the discrete setting, the Borda score of agent for alternative e the number of alternatives c' such that b c'. In the continuous setting, (.))((T)) indicates the volume of the occupancy polytope to which agent prefers ा. The Borda count rule then selects a policy among arg max; Eie(m) (J)(
The computational complexity of the Borda count rule remains an interesting open question, though we make progress on two fronts.? First, we identify a sufficient condition under which we can find an approximate max Borda count policy using convex optimization in polynomial time. Second, similar to Algorithm 3, we present MILP to approximate the Borda count rule in Algorithm 4.
'e suspect the problem to be NP Phardrd since the objective resembles summation of "sigmoidal" functions over convex domain, which is known to be hard [37].
8

---

The first is based on the observation in Section 4 that F; is concave in range [mode( 20). We assume that the max Borda count policy π appears in the concave portion of all agents, ie., J(( > model f;) for all i E [n]. Then, the problem becomes a maximization of the concave objective max Σ, (il R.)) over the convex domain {d= E O (d=z, R.) z mode(ft), vi E [n])-
Second, Algorithm 4 is a MILP that finds an approximate max Borda count policy, As a pre- processing step, we estimate F; for each agent separately. We measure F; for the fixed expected return values of {e, 2e...., 1 - e, 1). This accounts for 1/c oracle calls to vol-comp per agent. Then, for the MILP, we introduce 1/c binary variables for each agent indicating their c-rounded return levels, i.e., as = iff (d,, R₂) > ke for & E [1/c]. The MILP then searches for an occupancy measure dx E O with maximum total Borda score among the e-rounded expected return vectors (see Appendix C for more details).
Finally, we make a novel connection between q-quantile faimess and Borda count in Theorem 6. We defer the proof to Appendix B. A corollary of Theorems 2 and 6 is that the policy returned by e-max quantile fair algorithm (Algorithm 2) achieves a (1/e- - -) multipiccative approximation of the maximum Borda score.
Theorem 6. A q-quantile fair policy is a q-approximation of the maximum Borda score.
7 Experiments
Environment. We adapt the dynamic attention allocation environment introduced by D' D'Amurr et al. [11]. We aim to monitor several sites and prevent potential incidents, but limited resources prevent us from monitoring all sites at all times; this is inspired by applications such as food inspection and pest control 6. There are m = 5 warehouses and each can be in 3 different stages: normal (norm), risky (risk) and incident (inc). There are |S|= = 3 states containing all possible stages of all warehouses. In each step, we can monitor at most one site, so there are + actions, where action m + 1 is no operation and action & m is monitoring warehouse i. There are n agents; each agent i has list & of warehouses that they consider valuable and a reward function R3, In each step t, (s,, ae) = - I[a & m] -jEt, PLWy [[$1, = inc A a, * j]. where W/ E {100, 150, ... 2500 denotes the penalty of an incident occurring in warchouse j. Ps is the scale of penalties for agent i which is sampled from {0.25, 0.5. ... nn, and 1 is the cost of monitoring. In each step. if we monitor warchouse j. its stage becomes normal. If not, it changes from norm to risk and from risk to inc with probabilities Pj and Pjiinc, and stays the same otherwise. Probabilities are sampled i.i.d. uniformly from [0.5, 0.8). The state transitions P is the product of the warehouses' stage transitions.
Rules. We compare the outcomes of policy aggregation with different rules: max-quantile, Borda, a-approval (a = 0.9, 0.8), egulitarian (maximize minimum return) and utilitarian (maximize sum of returns). We sample 5 10 random policies based on which we fit a generalized logistic function to estimate the cdf of the expected return distribution F; (Definition 4) for every agent. The policies for a-approval voting rules are optimized with respect to maximum utilitarian welfare. The egalitarian rule finds a policy that maximizes the expected return of the worst-off agent, then optimizes for the second worst-off agent, and so on. The implementation details of Borda count are in Appendix D.
Results. In Figure 1, we report the normalized expected return of agents max," J+(m") Ji(n')-min,> , J. (sorted from lowest to highest) which are averaged over 10 different environment and agents instances. We observe that the utilitarian and egalitarian rules are sensitive to the different agents' reward scales and tend to perform unfairly. The utilitarian rule achieves the highest utilitarian welfare by almost ignoring one agent. The egalitarian rule achieves higher return for the worst-off agents compared to the utilitarian rule, but still yields an inequitable outcome. The quax-quatile rule tends return the fairest outcomes with similar normalized returns for the agents. The Borda rule, while not fair rule by design, tends to find fair outcomes which are slightly worse than the max-quantile rule. The a-approval rule with max utilitarian completion tends to the utilitarian rule as -> 0 and to plurality as a + 1. Importantly, although not shown in the plots, the plurality rule ignores almost all agents and performs optimally for a randomly selected agent.
J J((z)
In addition to the fine- ane-grained utility distributions, in Table 1, we report two aggregate mea- sures based on agents' utilities: (i) the Gini index, a statistical measure of dispersion defined
'The code for the experiments is available at https///gtttl.oommmpaa/oocygggge

---

100
100
% Max Return
% Max Retur
75
50
max-q borda
90%-a 80%-a
egal
util
max-q borda 90%-a 80%-a
egal util
(a) agents consider random subset warehouses valuable
(b) symmetric agents, one per warehouse
Figure 1: Comparison of policies optimized by different rules in two different scenarios based the normalized expected return for agents. The bars, grouped by rule, correspond to agents sorted based on their normalized expected return. The error bars show the standard error of the mean.
5 symmetric agents, one per warehouse
10 agents, random subsets of warehouses
Rules
Gini index
Nash welfare
Gini index
Nash welfare
egalitarian
0.2864 + 0.0295
0.2208 + 0.0717
0.2126 + 0.0209
0.4655 + 0. 0.0581
utilitarian
0.4392 + 0.0094
0.0502 + 0.0174
0.2020 0.0182
0.5736 0.0471
80%-approvals
0.1233 + 0.0047
0.5186 + 0.0051
0.1352 + 0.0037
0.6741 = 0.0200
approopssss
0.0793 + 0.0056
0.5286 + 0.0053
0.1257 0.0034
0.6746 0.0211
Borda
0.0225 1 0.0024
0.5356 + 0.0062
0.1029 + 0.0083
0.6801 + 0.0261
max-quantile
0.0188 1 0.0022
0.5355 1 0.0062
0.0625 0.0067
0.6474 0.0232
Table 1: Comparison of policies optimized by different rules in two scenarios based Gini index and Nash welfare based on their normalized expected return averaged. We report the mean and the standard error.
EieN EyEN [((())- where lower Gini index indicates more equitable distribution, and 2n LIEN J.(x)
(ii) the Nash welfare, defined as the geometric mean of agents' utilities (TTEN J=(T)) 1/2 where a higher Nash welfare is preferable. We observe a similar trend as above, where utilitarian and egalitarian rules perform worse across both metrics. For the other four rules, the Nash welfare scores are comparable in both scenarios, with Borda showing slightly better performance. The Gini index, however, highlights clearer distinction among the rules, with max-quantile performing better.
8 Discussion
We conclude by discussing some of the limitations of our approach. A first potential limitation is computation. When we started our investigation of the policy aggregation problem, we were skeptical that ordinal solutions from social choice could be practically applied. We believe that our results successfully lay this initial concern to rest. However, additional algorithmic advances are needed to scale our approach beyond thousands of agents, states, and actions. Additionally, an interesting future direction is apply these rules within continuous state action spaces, as well as in online reinforcement learning setting where the environment remains unknown.
A second limitation is the possibility of strategic behavior. The Gibbard-San Sataadd-SSttettwwatee Theorem [16, 33] precludes the existence of "reasonable" voting rules that are strategyproof, in the sense that agents cannot gain from misreporting their ordinal preferences; we conjecture that similar result holds for policy aggregation in our framework. However, if reward functions are obtained through inverse reinforcement learning, successful manipulation would be difficult: an agent would have to act a way that the learned reward function induces ordinal (volumetric) preferences leading to a higher-return aggregate stochastic policy. This separation between the actions taken by agent and the preferences they induce would likely alleviate the theoretical susceptibility of our methods to strategic behavior.
10

---

Acknowledgments
We gratefully acknowledge funding from the Natural Sciences and Engineering Research Council of Canada (NSERC) and the Canada CIFAR AI Chairs Program (Vector Institute). This work was also partially supported by the Cooperative AI Foundation; by the National Science Foundation under grants IIS-2147187 IIS-2229881 and CCF-2007080; and by the Office of Naval Research under grants N00014-20-1- 1-2488 and 100014-24-1-2704
References
[1] P. Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the 21st International Conference on Machine Learning (ICML), pages 1-8, 2004.
[2] A. Alamdari, T. Q. Klassen, R. Toro Icarte, and A. Mcllraith. Be considerate: Avoiding negative side effects in reinforcement learning. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 18-26, 2022.
[3] P. A. Alamdari, T. Q. Klassen, E. Creager, and S. A. Mcilraith. Remembering to be fair: Non-Markovian fairness in sequential decision making. Proceedings of the 41 International Conference Machine Learning (ICML), pages 906-920, 2024.
[4] Y. Babichenko, M. Feldman, Holzman, and V. Narayan. Fair division via quantile shares. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1235-1246, 2024.
[5] R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(344):324-35,, 1952.
[6] I. Caragiannis, A. D. Procaccia, and N. Shah. When do noisy votes reveal the truth? ACM Transactions on Economics and Computation, 4(3): article 15, 2016.
[7] B. R. Chaudhury, A. Murhekar, Z. Yuan, B. Li, R. Mehta, and A. D. Procaccia. Fair federated learning via the proportional veto core. In Proceedings of the 41 International Conference on Machine Learning (ICML), 2024.
[8] N. Clegg. Bringing people together to inform decision decision-making on generative AI. Blog post, 2023. URL https: :ttttp::///bbboe http://abbbtttteee fb.
wtw.aat.....o./////////e/e/e///e wwwmnews//023///000000 06/ generative-eeeeeeee www.rveeeaioooonitt-aooooao www.oootottooooooooooooooo
[9] V. Conitzer and T. Sandholm. Common voting rules as maximum likelihood estimators. In Proceedings of the 21st Annual Conference on Uncertainty in Artificial Intelligence (UAI),
pages 145-152, 2005.
[10] V. Conitzer, Freedman, J. Heitzig, W. H. Holliday, B. M. Jacobs, N. Lambert, M. Mosse, E. Pacuit, S. Russell, H. Schoelkopf, E. Tewolde, and W. S. Zwicker. Position: Social choice should guide AI alignment dealing with diverse human feedback. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 9346 9360, 2024.
[11] A. D' Amour, H. Srinivasan, J. Atwood, P. Baljekar. Sculley, and Halpemn Fairness not static: Deeper understanding of long term fairness via simulation studies. In Proceedings of the 3rd Conference Fairness, Accountability, and Transparency (FAccT), pages 225-534, 2020.
[12] M. Dyer, A. Frieze, and R. Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM, 38(1):1-17, 1991.
[13] Z. Fan, N. Peng, M. Tian, and B. Fain. Welfare and fairness in multi-objective reinforcement learning. In Proceedings of the 22nd International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 1991-1999, 2023.
[14] Fishburn. Probabilistic social choice based on simple voting comparisons. The Review of Economic Studies, 51(4):683 1984.

---

[15] M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified np-complete graph problems. Theoretical Computer Science, 1(3):237-267, 1976. ISSN 0304-3975.
[16] A. Gibbard. Manipulation voting schemes. Econometrica, 41:587-602, 1973.
[17] B. Grünbaum. Partitions of mass-distributions and of convex bodies by hyperplanes. Pacific Journal of Mathematics, 10(4): 1960.
[18] Gurobi Optimization, LLC.C Gurobi Optimizer Reference Manual, 2023. URL htt.tt//p://r gurobi. com.
[19] P. Hammond. Interpersonal comparisons of utility: Why and how they and should be made. In J. Elster and E. Roemer, editors, Interpersonal Comparisons of Well-Being, chapter 7, pages 200-254, Cambridge University Press, 1991.
[20] Hästad. Clique hard to approximate within E. Acta Mathematica, 182:105 142, 1999.
[21] C. F. Hayes, R. Rádulescu, E. Bargiacchi, Källström, M. Macfarlane, M. Reymond, T. Ver- stracten, L. M Zintgraf, R. Dazeley, F. Heintz, et al. A practical guide to multi-objective reinforcement learning and planning. Autonomous Agents and Mulli-Agent Systems, 36(1):26, 2022.
[22] E. lanovski and A. Kondratev. Computing the proportional veto core. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021.
[23] P. Ju, A. Ghosh, and N. Shroff. Achieving fairness in multi-agent MDP using reinforcement learning. In Proceedings of the 12th International Conference on Learning Representations (ICLR), 2023.
[24] A. Y. Kondratev and E. lanovski. Veto consistent preference aggregation. In Proceedings of the 23rd International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages
2024.
[25] D. Mandal and Gan. Socially fair reinforcement learning. CoRR, abs/2208. 12584, 2022.
[26] H. Moulin. The proportional veto principle. The Review of Economic Studies, 48(3):407-416. 1981.
[27] A. Y. Ng and S. Russell. Algorithms for inverse reinforcement learning. In Proceedings of the 17th International Conference on Machine Learning (ICML), pages 663-670, 2000.
[28) R. Noothigattu, T. Yan, and A. D. Procaccia. Inverse reinforcement learning from like-minded teachers. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 9197-9204, 2021.
[29] W. Ogryczak, P. Perny, and P. Weng. A compromise programming approach to multiobjective markov decision processes. International Journal of Information Technology & Decision Making, 12(05):0021-1053 2013.
[30] L. Ouyang. J. Wu, X. Jiang. D. Almeida, C. Wainwright, Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, Christiano, J. Leike, and Lowe. Training language models follow instructions with human feedback. In Proceedings of the 36th Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
[31] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
[32] D. M. Roijers, P. Vamplew, Whiteson, and R. Dazeley. A survey of multi-objective sequential decision-making Journal of Artificial Intelligence Research, 48:67-113, 2013.
[33] M. Satterthwaite. Strategy and Arrow' conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10: 187-217, 1975.
12

---

[34] U. Siddique, P. Weng, and M. Zimmer. Learning fair policies in multi- objective (deep) reinforce- ment learning with average and discounted rewards. In Proceedings of the 37th International Conference Machine Learning (ICML), pages 8905-8915, 2020.
[35] T. Sorensen, J. Moore, J. Fisher, M. L. Gordon, N. Mireshghallah, C. Michael Rytting, A. Ye, L. Jiang, X. Lu, N. Dziri, T. Althoff, and Y. Choi. Position: A roadmap to pluralistic aligmment In Proceedings of the 41st International Conference Machine Learning (ICML), pages 46280-46302 2024.
[36] G. Swamy, C. Dann, R. Kidambi, S. Wu, and A. Agarwal. A minimaximalist approach reinforcement learning from human feedback. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 47345-47377, 2024.
[37] M. Udell and S. Boyd. Maximizing a sum of sigmoids. Optimization and Engineering, pages 1-25, 2013.
[38] R. Yang. Sun, and K. Narasimhan. generalized algorithm for multi-objective reinforcement learning and policy adaptation. In Proceedings of the 33rd Annual Conference Neural Information Processing Systems (NeurIPS), 2019.
[39] H. P. Young. Condorcet's 's theory of voting. The American Political Science Review, 82(4): 1231-1244, 1988.
[40] T. Zahavy, B. O'Dooguu,,, G. Desjardins, and S. Singh. Reward is enough for convex MDPs. In Proceedings of the 35th Annual Conference on Neural Information Processing Systems (NeurIPS), pages 25746-25750 2021.
[41] W. Zaremba, Dhar, L. Ahmad, Eloundou, S. Santurkar, Agarwal, and Le- ung. Democratic inputs to AI. Blog post, 2023. URL https://openai.com comb//oog/ democratic-inpus-tooba
[42] H. Zhong, Z. Deng, J. Su, Z. Wu, and Zhang. Provable multi-party reinforcement learning with diverse human feedback. arXiv preprint arXiv:2403.05006, 2024.
13

---

A State-action Occupancy Polytope for Discounted Reward
Definition 7 (State-action Occupaney Polytope for discounted-reward [31, 40]). For MOMDP M in the discounted-reward case, the space of valid state state-action occupancies is the polytope
o = dz
d 0, Σ
dz(ss = =(1 - -1))daii ( (8) + > d(s' sd)((
s'
B Proofs of Section 6
We define a fully connected MOMDP as a MOMDP M where for every pair of states s' S and any action a E A. P(s, a, [S] In all the hardness proofs, we create a fully connected MOMDP. For such MOMDPs, it is not difficult to observe that the state-action occupancy polytope, for both [ST Vs 8} for both the
the average and discounted reward, is equivalent to {dz E. (s,
discounted and average reward case. Furthermore,
d=(s,a)
T(als)
E=e,dd(ssad) =|S| ds
B.1 Proof of Theorem 4
Proof of Theorem 4. We show hardness of approximation by approximation-pprseeee reduction from the maximum independent set (MIS) problem.
Definition 8 (maximum independent set (MIS)). For a graph G = EV, with vertex set V and edge set E C 2()), the maximum independent set (MIS) of G is the maximum subset of vertices V S V such that there
edges between any pair of vertices v1, 02 E V
Theorem 7 (Hástad [20]). For any fixed e E (0, 1), there is no polynomial-time time approximaainniai algorithm for the MIS problem unless P = NP, and no ni- -p-aappprxiimaiion algorithm unless
ZPP NP.
Construction of MOMDP. Let G = ([n], E) a graph for which we want to find the maximum independent set. Create fully connected MOMDP M with |F] states {sa]. per edge F. There are only two actions A = {a1,a2)- In state 8, of edge e = (e1,62), performing action a₁ and 02 correspond to and 62 respectively. We create agents where agent corresponds to vertex i. The reward function of agent for state s, and action Og for k E (1, (1 is defined as
[1,
if ex i,
Ri(ses aR)
0,
o.w.
In other words, the reward functions encode the of edges incident to vertex
Correctness of reduction. A policy is optimal for agent i iff for all the edges incident to i the action corresponding is selected with probability If policy and i', then = (i,'') i') & E, since at state se either π < (s) = 1 or (a2]s) 1. Therefore, the set of agents that consider policy optimal corresponds to an independent set in Furthermore, take any independent set V' C [n]]. Let π be the policy that for each edge selects the action corresponding to the vertex in V and, if such vertices exist, select one arbitrarily. This policy is well defined since V' is an independent set and there are no edges with both vertices from V'. Policy π is optimal for agents of V since at each state their favourite action is selected. Thus, we have an equivalence between the maximum independent set of G and the plurality winner policy of M. Therefore, the hardness of approximation follows from Theorem
considered optimal by two agents
B.2 Proof of Theorem 5
Proof of Theorem 5. We reduce the MAX-2SAT problem to finding an a-approval policy for a e (7/8, 1).
For two Boolean variables 21 and 22, we denote the disjunction (i.e., logical or) of two variables by Ij V 22 and the negation of 21 by -Z1
14

---

x(((c12))
1 F((e)
11
0.5
0.5
v
π ((((ea)))
0.5
2
(a) The scaled occupancy polytope
(b) The expected return edf
Figure 2: The effective state-action occupancy polytope of agents and their expected return distribu- tion.
Definition 9 (maximum 2-satisfiability (MAX-2SAT)), Given a set of m Boolean variables
(3i.....mm] and set of 2-literal disjunction clauses (Ci,..., Cn the goal of the maximum 2-satifiability problem (MAX-2SAT) is to find the maximum number of clauses that can be satisfied together by an assignment é {2y [ay])e[n] + {True, False}.
Garey et al. [15] showed that the MAX-2SAT problem is NP-hard.
Construction of MOMDP. For instance of the MAX-2SAT problem, let [CI.-.., Cn be set of m 2-literal disjunction clauses over n variables {II,... J. We create a fully connected MOMDP M with m states state 8j representing variable Zj. There are only two actions, @'rue and @False which at state 8, correspond to setting variable xj to True and False respectively. This way, a policy π (a 8j) can be interpreted as the probability of setting the variable z, to True, subject to T (4Truels)) (3) = - (apalsee)s))
Agents and reward function. We introduce some notation before introducing the agents and their reward function. Take clause C; = 4,1 V 6,2 where Gi E {æj, -Ty Je(m] for E [2]. By combining the former relation with the mapping of xr and - to state-action pairs (8j, @True) and ($j, Palse respectively, we define A (,2, + S x A. For every Ci A(Gr,) is the state-action pair that evaluates C₁ to True when selected with probability one. Now, we are ready to introduce the agents. For each clause C₁ create 3 agents per clause follows:
Agent ag., with a reward function that 1 for ( and A(ea,2) and zero otherwise. An optimal policy of this agent selects the state-action pairs with probability one, which can be interpreted as C, + True and 222 + True that implies C2 = True.
Agent 8g,,2 with reward function that is 1 for M(ea) and A( (-01,2) note the negation. This is another assignment of variables, G,1 <- True and 6,22 < False, that implies C, +- True.
Similarly, the reward function of agi, is 1 for A( M(C1,) and A(c2,2 (which again implies C, + True).
For ease of exposition, and by slight abuse of notation, in the rest of the proof we use π to refer to the occupancy measure. From Equation (1) we have [S] dg (s, a) = π (alss) and the a-approval rule invariant to affine transformation. Therefore, we let J+(x) = (m, R).
Expected return distribution. The expected return of agent ag,, for a policy л is =AA(c,,)) + x (A(c,2)). ). For conciseness, let 01 = π (X(c,,)),, = (A(c..2)) Then, the cd
for o E [0, 1].
F Fog, (V)
Tu + u2
v] du duz
(2-v)² 2
for u E [1,2].
See Figure 2 for a visualization. The edf of other agents have the same form. For each of the 3n agents above, their maximum expected return is 2.
15

---

Rounding policy. Observe that F((3/2) = 7/8. For agent agi, to a-approve policy for (7/8, 1), they require utility (strictly) more than 3/2 F (7/8). The fact that v1, V2 E [0, 1] in addition to en + 02 > 3/2, implies that 01 > 1/2 and 02 > 1/2. Therefore, if a policy a is a-approved by agent 1g,, have (()(c,,)) 1/2 and x x((c,,2) 1/2. Further, observe that for at most one of the three agents {agı, hkejs the condition of J Jag.a (T) > 3/2 may hold as every pair of the agent disagree on one literal.
We round such a policy क assignment by letting ((z;) True if (aTruel)))) > and o(xy) < False otherwise. If an agent in { (ke(3) a-approves π. then C2 is satisfied by the assignment db. Therefore, feasible number of a-approvals among all policies and OPT is the maximum number of clauses that can be satisfied among all assignments.
have that OPT. & OPTMAX MAX-28AT where OPT is the maximum
& OPT, by deriving a policy π that gets OPT a- approvals based on the optimal assignment for OPT MAX-25AT by simply letting (a'ruue (8y) 1 iff ((x;) = Truc. If Φ satisfies a clause C₁ then for the agent ag E { {ag,, he that matches the literal assignments o for C, we have Jag (T) = 2, which is an optimal, i.c., 1-approval, policy for 1 which gets return less than their required utility ag. For the other two agents for Ct Jag(n (TT) of 3/2 for an a-approval. Therefore, we have that MAX-MX-22 2SAT = OPT and the hardness of computation follows from our reduction.
Next, we show MAX-
B.3 Proof of Theorem 6
Proof of Theorem 6. The Borda count of policy defined as Borda( = Eign Ft(J:(T)). Since F.(e) E [0, 11, max Eigjn) (T)).(T)) & n. From Definition 6, for a q-quantile fair policy Ty. we have ((()((T)) q, for all i [n]. Therefore, Σie(n) (T)))TTT) qn and we have
Borda(Tg)) max, Borda(T) (T)
qn 7
2 q.
C A Note on Algorithm 4
Here, we expand on Algorithm 4. As mentioned before. in the pre-processing step, for every agent i, we measure Fk(k)) for k [1/c] via 1/c calls to vol-comp. Let ((r) (J1 (T)) ...,,....d Ju (x)) be the (expected) return vector. Importantly, our MILP approximates the Borda score of return vector by its c-rounded-down return vector r. ([ra/c] ee E [n]). Therefore, the MILP finds a policy that has Borda count which is at least as high the maximum Borda count among e-rounded return vectors. This is not necessarily equivalent to a e) approximation of the max Borda count.
D Experimental Details
Experiments all done AMD EPYC 7502 32-Core Processor with 258GiB system memory. We use Gurobi [18] to solve LPs and MILPs.
Running time. All our voting rules has running time of less than ten minutes on the constructed MOMDPs of 35 243 states, actions, and agents. The most resource extensive task of our experiments was sampling 5- 10 random policies and computing the expected return for every agent which is a standard task. For each instance, we did this in parallel with 20 processes in a total running time of less than 2 hours per instance.
Implementation details of Borda count rule. After fitting generalized logistic function for F; based on the expected return of sampled policies, we find the value mode(f;), and check the existence of policy by solving linear program that achieves expected return of mode(fa) for all agents. Next, to utilize Gurobi LP solvers, we approximate the concave function F, by a set of linear constraints that form a piecewise linear concave approximation of F,. Therefore, our final program for an approximate Borda count rule is simply an I.P.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We summarized the theoretical contributions and experimental results in abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Some of the limitations of our approach are discussed in the discussion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

Justification:
We provide the full set of assumptions and proofs in the paper. However, details of some of the proofs (due the limited space) are deferred appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The experimental details are provided in the experiments section and appendix.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
18

---

Answer: [Yes]
Justification:
The full code with the running instructions are attached.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips. wwtppblicgguiiiiicccccceeooooppe httpr/guuiieeeeeeeeuiiiieeeeeeee /at////ooommssseeeeeee ssionsolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We describe all the essential details for reproducing the results.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes. They included in the plots, and the results reported based on the average of multiple runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
19

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: They are included in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:://neeu....eeeee cc cccppblic//ttieeeeeeeeeeeeee ctt.ehhiiiiiiiieeeseee
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethics, and the research conducted in the paper conforms with it in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss the potential for positive societal impact through better Al align- ment. While it is conceivable that our techniques would lead to worse Al alignment, this scenario seems implausible.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not use any types of data models that have the potential for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the optimization tools utilized in our code.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not experiment with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not experiment with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "F81v7XEdNB", "reviewer": "Reviewer_vrsi", "summary": "This paper studies aggregating multiple policies–which can be seen as a formalization of the task of aligning an AI system to the values of multiple individuals. When the number of states is small (such as, when multiple individuals have to select one out of a few candidates), this problem has been widely studied in voting and social choice theory, and there are many efficient aggregation rules (such as the Borda count). This paper, however, considers the other extreme: where the state-action space is huge, and it is not obvious how to design efficient methods to aggregate policies. \n\nThe main insight of this paper is that preferences over policies have a volumetric interpretation in the state-action policy space that, in some cases, leads to efficient aggregation algorithms. \n\nConcretely, the authors examine two types of aggregation rules: (1) two aggregation rules that are known to have desirable fairness properties (namely, proportional veto code and, the recently introduced, quantile fairness) and (2) voting or score-based rules such as Borda count and $\\alpha$-approval voting rule. \n\nBuilding on their insight the authors prove several results, including \n1. an algorithm which finds the policy wrt an $\\epsilon$-approximation of the proportional veto core using $O(log(1/\\epsilon))$ queries to a volume computation oracle, \n2. the existence of $q$-quantile fair policies for all $q\\geq 1/e$ (which is tight and stronger than the best possible bound in the discrete case),\n3. NP-hardness and inapproximability results for $\\alpha$-approval score.", "questions": "I do not have any specific questions for the authors.", "limitations": "I do not see significant limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and easy to read. I believe that the problem proposed in the paper is well-motivated from alignin AI systems, and is of significant interest to research on voting rules and social choice theory. The theoretical results are solid and the proofs and/or approach are well outlined. Finally, I did not check the proofs in detail, but they appear sound. One caveat is that I am not familiar with the closely related prior work (e.g., [6]) and, so, cannot comment on the novelty of the proofs and results from prior work.", "weaknesses": "I am not sure if the empirical results section is adding any value to this paper: it evaluates different aggregation rules, but I think this is not the focus of this work–I think the focus is to design efficient algorithms and/or prove existential results. If other reviews and the area chairs agree, my suggestion is to drop the empirical results section and use the additional space to add more exposition on the proofs. To be clear, this is no a significant concern for me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I am not sure if the empirical results section is adding any value to this paper: it evaluates different aggregation rules, but I think this is not the focus of this work–I think the focus is to design efficient algorithms and/or prove existential results. If other reviews and the area chairs agree, my suggestion is to drop the empirical results section and use the additional space to add more exposition on the proofs. To be clear, this is no a significant concern for me.\n\nWe agree that the main contribution and focus of our work is theoretical, that is, efficient algorithm design and existential results as mentioned. We are open to moving the empirical section to the appendix and elaborating on the theory, including the proofs, in the main body.\n\nWe do see the empirical results as contributing in two ways: (1) The aggregation rules are practical. They can be easily implemented and run fast (on not-so-small instances). (2) In addition to theoretical arguments, empirical evaluation illustrates the differences in policies generated by the proposed rules, e.g.,  some of the proposed rules result in policies that are empirically \"fairer\" to different stakeholders in complex settings.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5c8K7pIBFv", "reviewer": "Reviewer_7MP7", "summary": "The paper solves the problem which arises in preference aggregation of individual policies to a collective policy – (1) summation based aggregation are sensitive to affine transformations and (2) voting rule based aggregation faces problem of policies being exponential in S. Towards solving this, the paper proposes voting over continuous space of alternatives (which eliminates affine sensitivity) and a volumetric definition of preference ordering. The paper next proposes efficient algorithms to (1) find approximate volumetric veto core and (2) approximate q-Quantile Fairness. They also show complexity of existing voting rules, notably plurality voting and borda count. They show that problem is computationally hard for plurality and open for broad count. I am inclined towards accepting the paper.", "questions": "see weakness.\n\nWhy can't yours be a special case of Noothigattu et al. [27]?", "limitations": "Authors adequately address the problem statement and discussed limitations/candidate improvements of their work which is left to future work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper solves a well-motivated problem of policy aggregation. Their proposal of achieving different notions of approximate fairness through efficient algorithms both novel and appears to be sound. Their theoretical analysis of the complexity of using plurality and borda count based voting is also significant and allows scope for future work in the direction. Their algorithms have been validated through experiments.", "weaknesses": "In the experimental section, using a common metric to quantify the “level of fairness” guaranteed by different algorithms would be beneficial for a more learned comparison.  \n\nIn Def. 4 should the expression be vol(O’)/vol(O) >= 1 – veto(S) + epsilon instead of vol(O’) >= 1 – veto(S) + epsilon as currently stated?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> In Def. 4 should the expression be vol(O’)/vol(O) >= 1 – veto(S) + epsilon instead of vol(O’) >= 1 – veto(S) + epsilon as currently stated?\n\nYes, you are right. Thank you for catching this typo.\n\n> Why can't yours be a special case of Noothigattu et al. [27]?\n\nNoothigattu et al. assume that there's a ground-truth reward function and the agents' reward functions are random perturbations thereof. Consequently, they essentially propose to treat all the data as coming from a single agent and directly apply an inverse reinforcement learning algorithm to the pooled data. Our setup, by contrast, calls for pluralistic rules that take diverse preferences into account. \n\nPerhaps a good analogy is the shift that has been happening in the last year from reinforcement learning from human feedback (RLHF) methods that rely on the Bradley-Terry model and essentially assume there is one type of person to \"pluralistic alignment\" methods where social choice plays a major role and diverse preferences are respected. See these recent position papers for more details:\n\nTaylor Sorensen, Jared Moore, Jillian Fisher, Mitchell Gordon, Niloofar Mireshghallah, Christopher Michael Rytting, Andre Ye, Liwei Jiang, Ximing Lu, Nouha Dziri, Tim Althoff, Yejin Choi. A Roadmap to Pluralistic Alignment. arXiv:2402.05070, 2024.\n\nVincent Conitzer, Rachel Freedman, Jobst Heitzig, Wesley H. Holliday, Bob M. Jacobs, Nathan Lambert, Milan Mossé, Eric Pacuit, Stuart Russell, Hailey Schoelkopf, Emanuel Tewolde, William S. Zwicker. Social Choice Should Guide AI Alignment in Dealing with Diverse Human Feedback. arXiv:2402.05070, 2024.\n\n> In the experimental section, using a common metric to quantify the “level of fairness” guaranteed by different algorithms would be beneficial for a more learned comparison.\n\nThe current plots show the utility of different quantiles (10%, 20%, ..., 100% for the experiment with 10 agents and 20%, 40%, ..., 100% for the one with 5 agents), which provides a holistic view of the utility distribution. The bars for the worst-off agent correspond to the egalitarian welfare. In the revised manuscript, we will include additional plots with information on different fairness metrics such as the Gini coefficient and Nash welfare. If the reviewing team also has other suggestions, we would gladly consider them.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "43feIc7uDw", "reviewer": "Reviewer_61yS", "summary": "This paper joins a long list of recent work that studies how to aggregate the preferences of several agents (e.g., humans) in a reinforcement learning framework inspired by social choice theory. The problem is modeled as a multi-objective MDP with $n$ different reward functions. The authors propose to use the state-action occupancy measure instead of each agent's most preferred policy or reward function directly. Popular concepts from social choice theory, such as the Borda count rule and approval voting, are then studied from this perspective.", "questions": "- I'm a bit surprised about the title of the paper since you're not aggregating policies, but reward functions. In fact, the policies play a minor role in the paper, since you look at the preference relation induced by the reward function (which you then express in term of occupancy measures). Could you explain why what you're doing is policy aggregation and not just preference aggregation? \n\nTypo: \"Policy Aggergation\" in title of Section 5", "limitations": "Limitations are adequately addressed in my opinion.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and easy to read. \n- It appears that considering the state-action occupancy measure has some advantages over working directly with each agent's optimal policy or reward function when attempting to introduce social choice rules, which---even though a standard approach in RL---is interesting.", "weaknesses": "- In my opinion, the contributions of this work are limited. E.g., only the full information case is studied\n- The primary justification of this work (which is repeatedly mentioned in the paper) is that prior work on policy aggregation and fair RL is not invariant to affine transformations of the reward function. Essentially, agents can have differently scaled reward functions, which makes, e.g., maximizing for social welfare a bad objective. However, I don't understand why we cannot simply normalize the reward function of each agent, so that the reward functions are directly \"comparable\". I find the concern about affine transformations quite weak.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The primary justification of this work (which is repeatedly mentioned in the paper) is that prior work on policy aggregation and fair RL is not invariant to affine transformations of the reward function. Essentially, agents can have differently scaled reward functions, which makes, e.g., maximizing for social welfare a bad objective. However, I don't understand why we cannot simply normalize the reward function of each agent, so that the reward functions are directly \"comparable\". I find the concern about affine transformations quite weak.\n\nWe disagree with this comment and believe we can provide an effective rebuttal. As we mention in lines 34-37, there is a rich literature in economics about the shortcomings of interpersonal comparison of utility. Note that there is nothing about our setting that makes normalization of utilities especially compelling, so your proposed solution is equally relevant in every setting that involves interpersonal comparison of utility. If normalization \"worked,\" therefore, interpersonal comparison of utility would be a nonissue.\n\nThere are several arguments against normalizing utilities, but instead of a philosophical discussion, perhaps an example would be most useful. Suppose there are three alternatives, agent 1 has utilities (0, 1/2, 1) and agent 2 has utilities (2, 3, 4). Should the normalized utilities of agent 2 be (1/2, 3/4, 1), or should we first subtract 2 and then divide by the maximum, yielding (0, 1/2, 1)? Or should we only subtract 1? Or perhaps we should normalize so that the sum of utilities is equal, giving (0, 1/3, 2/3) for agent 1 and (2/9, 1/3, 4/9) for agent 2? Economists argue that there is no principled way to answer these questions.\n\n> I'm a bit surprised about the title of the paper since you're not aggregating policies, but reward functions. In fact, the policies play a minor role in the paper, since you look at the preference relation induced by the reward function (which you then express in term of occupancy measures). Could you explain why what you're doing is policy aggregation and not just preference aggregation?\n\nThe way we imagine the eventual pipeline is that we would observe trajectories from the optimal policy of each agent, learn reward functions via inverse reinforcement learning, and apply our techniques to select a policy. In this sense, we're aggregating the individual optimal policies into a collective policy. We also like the use of the word \"policy\" as it suggests that we're dealing with MDPs, in contrast to \"preference aggregation,\" which is much more general. That said, we'd certainly be open to changing the title if this is seen as a pivotal issue.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Reviewers are all positive about the paper. They consider the paper to be well-motivated from aligning AI systems and they find the paper to be well-written. It will be good to address reviewers' comments on the empirical section, and it might be good to add the discussion about normalizing utilities in the rebuttal to the paper if there's space.
Decision: Accept (poster)