Learning Social Welfare Functions
Authors: Kanad Shrikar Pardeshi
Itai Shapira
Ariel D. Procaccia
Aarti Singh
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Social Choice Learning
Power Mean Functions
PAC Learning
Preference Learning
Statistical Learning Theory
Social Welfare Functions
Primary area: algorithmic_game_theory
TL;DR: We show how to learn a policy maker's implicit social welfare function from their past decisions by fitting power mean functions, with provable sample complexity guarantees even under noisy observations.

Abstract: Is it possible to understand or imitate a policy maker's rationale by looking at past decisions they made? We formalize this question as the problem of learning social welfare functions belonging to the well-studied family of power mean functions. We focus on two learning tasks; in the first, the input is vectors of utilities of an action (decision or policy) for individuals in a group and their associated social welfare as judged by a policy maker, whereas in the second, the input is pairwise comparisons between the welfares associated with a given pair of utility vectors. We show that power mean functions are learnable with polynomial sample complexity in both cases, even if the social welfare information is noisy. Finally, we design practical algorithms for these tasks and evaluate their performance.

Learning Social Welfare Functions
Kanad Shrikar Pardeshi Carnegie Mellon University
Itai Shapira
Harvard University
kpardesh@andrew. cmu. edu
itaishapiraßg haw.ara.
Ariel D. Procaccia Harvard University
Aarti Singh
Carnegie Mellon University aarti Marti@andrew. cmu. cmu
arielprodseas. harvard.
edu
Abstract
Is it possible to understand or imitate a policy maker's rationale by looking at past decisions they made? We formalize this question the problem of learning social welfare functions belonging to the well-studied family of power mean functions. We focus on two learning tasks; in the first, the input vectors of utilities of an action (decision or policy) for individuals in a group and their associated social welfare as judged by policy maker, whereas in the second, the input is pairwise comparisons between the welfares associated with a given pair of utility vectors. We show that power mean functions are learnable with polynomial sample complexity in both cases, even if the social welfare information is noisy. Finally, we design practical algorithms for these tasks and evaluate their performance.
Introduction
Consider standard decision making setting that includes set of possible actions (decisions or policies), and set of individuals who assign utilities to the actions. social welfare function aggregates the utilities into single number, providing measure for the evaluation of actions with respect to the entire group. Utilitarian social welfare, for example, the sum of utilities, whereas egalitarian social welfare is the minimum utility. Given two actions that induce the utility vectors (3, 0) and (1, 1) for two individuals, the former is preferred when measured by utilitarian social welfare, whereas the latter is preferred according egalitarian social welfare.
When competent decision makers adopt policies that affect groups or even entire societies, they may have social welfare function in mind, but is typically implicit. Our goal is to learn social welfare function that is consistent with the decision maker's rationale. This learned social welfare function has at least two compelling applications: first, understanding the decision maker's 's priorities and ideas of fairness, and second, potentially imitating a successful decision maker's 's policy choices future dilemmas in other domains.
As a motivating example, consider the thousands of decisions made by public health officials in the United States during the Covid-19 pandemic: opening and closing schools, restaurants, and gyms, requirements for masking and social distancing, lockdown recommendations, and so on. Fach decision induces utilities for individuals in the population; closing schools, for instance, provides higher utility to medically vulnerable individuals compared to opening them, but arguably has much lower utility for students and parents. Assuming that healthcare officials were acting in the public interest and (approximately) optimizing a social welfare function, which one did they have mind? Our goal is to answer such questions by learning from example decisions.
Another example we consider in this paper that allocating food resources in a community by based nonprofit to hundreds of recipient organizations. Working with a dataset of utility of 18
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: summary of our results regarding the sample complexity of various tasks. Here, & Mmxx (Mmax - Mmin) and A = log (mmaa/ Umin], with all d individual utilities assumed to be in the range [Mminn Mmax-] p E [o, 1/2) is the probability of mislabeling for the i.i.d noise model, and Tmax is the maximum temperature of the logistic noise model.
Social Welfare Information
Loss
Known Weights
Unknown Weights
Cardinal values
l2
O(52)
O dog d) O log d) d of 1-2
Pairwise comparisons
0-1
O d)
Pairwise comparison with i.d noise
0-1
log ot 0
2-2p1
Pairwise comparisons with logistic noise estimation
Logistic
Tmax
O TTaaxk d dllog
different stakeholders such as donors, volunteers, dispatchers and recipient organizations [11], we consider the task of learning the social welfare implicit the decisions that may be made by the nonprofit.
In order to formalize this problem, there are two issues need to address. First, facilitate sample-efficient learnability, we need to make some structural assumptions on the class of social welfare functions. We focus the class of weighted power mean functions, which includes the most prominent social welfare functions: the aforementioned utilitarian and egalitarian welfare, as well as Nash welfare (the product of utilities). This class is a natural choice, as the only class of functions feasible under set of reasonable social choice axioms such as monotonicity, symmetry, and scale invariance [20, 7].
Second, we need to specify the input to our learning problem. There are two natural options, and explore both: utility vectors coupled with their values under target social welfare function, or pairwise comparisons between utility vectors. We demonstrate sample complexity bounds for both types of inputs, where the social welfare value or comparisons can be noiseless or corrupted by noise. We note that estimating the utility vector associated with any particular decision or policy is ostensibly challenging, but in fact this has been done prior work and we have access to relevant data, as we discuss in Section 6.
Learning weighted power mean functions is a non-standard regression or classification problem due the complex, highly nonlinear dependence the power parameter p, which is the parameter of interest. While one can invoke standard hyperparameter selection approaches such cross-validation to select p from grid of values, the infinite domain of p does not allow demonstration of a polynomial sample complexity without deriving an appropriate cover. We derive statistical complexity measures such neuudo-imension, covering number, VC dimension and Rademacher complexity for this function class, under both cardinal and ordinal observations of the social welfare function. Our sample complexity bounds summarized in Table 1. These results may be of interest for other problems where weighted power mean functions are used, such as fairness in federated learning [12].
Our contributions.
We highlight some key contributions of this paper. We first establish the statistical learnability of widely used social welfare functions belonging to the weighted power mean functions family. We derive polynomial sample complexity of (11) for learning using cardinal social welfare values under l2 loss, and (log d) (where d denotes the number of individuals) for learning using comparisons under 0 10-1 1 loss in the unweighted/known weight setting. The upper bounds leverage the monotonicity of the target functions with p in the cardinal case, and the restricted number of roots in the ordinal setting. We also prove matching lower bounds for the ordinal case.
We also establish polynomial sample complexity of Od d) for both cardinal and ordinal tasks in the setting when the individual weights are unknown. This result is intuitive, as learning an additional d weight parameters incurs proportional increase in the sample requirement.
We then analyze the sample complexity for the more practical ordinal task under different noise models (i.i.d. and logistic noise) and characterize the effect of noise on learning. In the i.i.d. noise setting, sample complexity increases with noise level p, converging to the noiseless complexity as p O. Unlike the i.i.d. case where p is known, in the logistic noise model, we also consider estimating the noise level 7 and evaluate the likelihood with respect to the noisy distribution. As increases, estimating the noise becomes more challenging, leading to higher sample complexity.

---

Finally, despite the problem's is non-convexity, we demonstrate a practical algorithm for learning weighted power mean functions across tasks using simulated data and real-world food resource allocation dataset from Lee et al. [11]. Our empirical results validate theoretical bounds and highlight algorithm performance across parameter settings.
Related work. Conceptually, our work related to that of Procaccia et al. [18], who study the learnability of decision rules that aggregate individual utilities. In their work, however, individual utilities are represented as rankings over a set of alternatives (rather than cardinal utilities as in our case), and the rule to be learned is a voting rule that maps input rankings to a winning alternative. They provide sample complexity results for two families of voting rules: positional scoring rules and voting trees.
Basu and Echenique [1] derive VC dimension bounds for additive, Choquet, and max- min expected utility for decision-making under uncertainty, bounding the number of pairwise comparisons needed to falsify candidate decision rule and estabilishing learnability for these classes. Their work addresses decision rules operating on probability distributions rather than utility vectors, resulting in technical distinctions from ours; for instance, the max-min rule is not learnable in their setting (infinite VC dimension), whereas it is learnable in ours.
Kalai [10] studies the learnability of choice functions and establishes PAC guaranteees. Choice functions are defined with respect to a fixed and finite set of alternatives X, with each sample being a subset from X and the choice over this subset. In contrast, our approach involves learning function over an infinite action space where utilities are known.
Pellegrini et al. [17] conducts experiments on learning aggregation functions which are assumed to be a composition of Lp means, observing that they perform favorably in various tasks such as scalar aggregation, set expansion and graph tasks. Our work provides more theoretical analysis, proving the sample-efficient learnability of weighted power mean aggregation functions.
Melnikov and Hüllermeier [14] considers learning from actions with feature vectors and their global scores, with local scores for each individual unavailable for learning. They learn both local and global score functions, and consider the ordered weighted averaging operator for aggregating local scores. While we assume that each individual's local score is given, the aggregation function belongs to a richer function family motivated by social choice theory.
2 Problem Setup
We assume that the decision-making process concerns d individuals. The decision-making setting we consider has each action associated with a positive utility vector u E [Mminn Mmaax] describes the utilities derived from the d individuals.
C Rd. which
We encode the impact of each individual i [d] the decision -akiing process through a weight value w, 2 such that > w;- = 1. These weight values together form weight vector w E A The weight vector might be known or unknown quantity. A common instance in which the weight vector is known is when all agents are assumed to have an equal say, in which case w = La/d. For all settings we consider, we provide PAC guarantees for both known weights and unknown weights.
We assume that the decision-makee However, this social welfare value can be latent and need not be available to us as data. For the first task concerned with cardinal decision values, the social welfare values are available and can be used for learning. For the second task, both actions in the pair have latent social welfare which is not available to us; however, the preferred action in the pair known to us. We consider learning bounds with the empirical risk minimization (ERM) algorithm for all the losses in this work, with ş being learned when the weights are known, and (w, p) being learned when the weights are unknown.
process provides a cardinal social welfare value each action.
Power Mean. The (weighted) power mean is defined on p E R U [=boo), and for E R$, w E
A-11, 1, is
1/p
El wau?
p +
M w,
u
wi
=
3

---

It is sometimes more convenient to use the (natural) log power mean than the power mean. Since E== W, I, in effect we have d variables, Wiy.... Wa-1 and We refer to the weighted power mean family with known weight w as
Mw,d (M w, p)lp E RR.
If the weight is unknown, the weighted power mean family is denoted by
Ma = (- w.p)lp E R, w. Az-1).
The power mean family is a natural representation for social welfare functions. Cousins [7, 6] puts forward of axioms under which the of possible welfare functions is precisely the weighted power mean family. An unweighted version of these functions results in the family of constant elasticity of substitution (CES) welfare functions [8], which are widely studied in econometrics.
To show the generality of this family of functions, we list few illustrative cases:
M(,:w,p= -o) minted u4, which corresponds egalitarian social welfare.
M(u;w,, = 0) II 1=1 "i which corresponds to a weighted version of Nash social welfare.
M(u; w. 1) Σi=1 W344, which corresponds to weighted utilitarian welfare.
M(u; w. 0o) = maXied Us which corresponds to egalitarian social welfare.
We note that for p = oo, the decision utility is independent of w. With w; 1/d for all E [d]. we get the conventional interpretations of the welfare notions mentioned above.
The power mean family has some useful properties. An obvious one is that Mu, w, p) E (u() "(a)], where u(1) and u(a) denote the first and d-th order statistics of (#1...., u,)) 2(1) is attained at p = -00, and u(d) is attained at p = cc. A more general observation is the following:
Lemma 2.1. (a) (u; w.p) is nondecreasing with respect p for all E [Umins Umax d w Ad-1-
(b) M(u w,p) is monotonic with respect to w. for each E [d - 1}, for all [umins Umax p R.
(c) Mu, wp) and log (u; w.p) log (v; w,p) are quasilinear with respect to w if is fixed.
This monotonicity of the power mean in and p was also noted by Qi et al. [19]. A proof for the above lemma provided in Appendix A.I.
Cardinal Social Welfare
We first consider the case where know the cardinal value of the social choice associated with each action. Learning in this setting thus corresponds to regression. Formally, we assume an underlying distribution D [Mmin: ummax] 1 [umin Mmax over the utilities and social welfare values. We receive ii.d samples {(u; 3/5) }/)) ~ DD, u, being the utility vector and yi E [14(1)> Ma(an) being the social welfare value associated with action i.
We consider the &g loss over M (u, w.p) and yt. The true risk in this case is
R(w, p) (uw)) (M (w:w)) v)²
To analyze the PAC learnability this setting, we first provide bounds on the pseudo-dimension'' of Mw,d and Mg- We begin by noting that
M(u w. u(a) M (r: where [d] and
U(d)
For a formal definition of secudo-dimension refer to Definition A.2. A comprehensive review can be found in Vidyasagar and Vidyasagar [22].

---

Since (r; p) E [0, 11. we can determine the pseudo-dimensee of this function class.
We now define the function classes
Sw.d = {f(u w.p) = M(; (w,p) E As-1 x R),
Sa (,( p, = M(r, [
We then have the following bounds on pseudo-dimensions: Lemma 3.1.
(a) If w is known, then Pdim(Sw.nr ,d)
(b) w is not known, then Pd) < [8d(log d + 1).
detailed proof is provided in Appendix A.3.
We highlight the fact that and w are the parameters of the log power mean function family, which calls for the novel bounds provided in this work. These bounds the pseudo-dimensions now be used to obtain PAC bounds:
Theorem 3.2. Given a set of samples {uu V:) drawn from a distribution D D",for any d >
the following holds with probability at least 1 - 5 with respect to the &g loss function:
(a) If w is known, then
(v
(22lgg 2 22og
log (4/6)
R(w, P)
inf R(w. S 16 PER
+ +6V
n
vn
2n
(b) If w unknown, then R(w,p)
inf (w.))
R(w, p) S16E
2 log 2 + 16(d log2 d + 1) log n
e
Vn
(4/5)
+ 61
2n
where { Umma (umax Umin).
For the complete proof, see Appendix A.5. Below, we provide a proof sketch.
Proof Sketch. We first use the pseudo-dimensions found above to bound the Rademacher complexity of MM and Mw.d a in Lemma A.6. Since (u,; w.p) E [Umin Mmaax] and Yi E [Mmiu Umax). the & loss function in this case has domain [Mmin Umax Umax Mm It is Lipschitz continuous on this domain with Lipschitz constant 2f. Using Lemma A.6 and Talagrand's contraction lemma, we obtain the bounds
R( Mw,a) S 2(Umax umin (w, and Ri( Ma) 2(Umax Umin (MM).
These Rademacher complexity bounds are then used to obtain the uniform convergence bounds above.
These bounds are distribution-free, with the only assumption being that all utilities and social welfare values are in the range [Mmin Mmnax] They also imply ((1) and Od d) dependence of sample complexity on d for known and unknown weights respectively. Moreover, we observe the dependence of the upper bound on Umax Umin for the &z loss. We note that when umax Umin wo. all utilities and social welfare function values are also uo. In this case, the Rademacher complexity bound is also zero, which is expected.
Computationallly, (u; w. p) is non-convex w and p. which means that the bg loss is also non- convex. However, observe that from Lemma 2.1 (c), M (u; w. is quasilinear w.r.t. with fixed p. which makes the & loss function quasi-convex for all (u, y) We use this fact to construct a practical algorithm.
shortcoming of this setting is that decision-makes are required provide a social welfare value for each action. A more natural setting might be when decision-makers only provide their preferences between actions - potentially just their revealed preferences, i.e., the choices they have made the past and and we address this case next.
A detailed explanation of the quasi-convexity of l2 loss provided in Appendix A.2.
5

---

Pairwise Preference Between Actions
For this setting, assume underlying distribution D [Mmin Mmax x [imin Umaxx] ) We obtain ii.d. samples {(u, vz); 3:)) ~ DD", where (u, v2) are the utilities for the i-th pair of actions, and yi comparison between their (latent) social choice values. We encode the comparison function as C' [uminn Umax] 1d x [Umin "max] + {=1}, with
{+1)-
C((u, v); w) = sign (log M (u; w. - log M wp))
We denote the family of above functions by Cw.dd = {C((u, w):
IR} when the weights known, and Ca {C( v); w.P) :p / R, w Ad-1) when the weights unknown. We consider learning with 0 loss over C(uu, Vi); w, p) and The true risk in this case is
(1 + C((u, v):w,p))) w.p)
R R(w, p) (()))))))
2
To provide convergence guarantees for the above setting, we bound the VC dimension of the comparison-bann function classes mentioned above
Lemma 4.1. (a) Ifw w is known, then VC(Cw.a) < 2(logg d + 1).
(b) w unknown, then VC(Ca) < 8(dlog, d + 1).
(c) (Lower bounds): VC(Ca) log2 d and VC a) 2 d -
The detailed proof of the above lemma is provided Appendix A.6.
We find the asymptotically tight lower bound for the known weights case rather surprising, as it is priori unclear that the correct bound should be superconstant and scale with d.
The finiteness of VC dimension guarantees PAC learnability, and we get uniform convergence bounds using the VC theorem.
Theorem 4.2. Given samples {(u,, vi). D and for 0-1 loss and any > 0, with probability at least - 8. (a) If w is known, then
2(log, d + log(n + +) log(8/6)
R(w, inf R(w,p) & 16V PER
n
(b) If w is unknown, then
8(d d + +1) log(n + 1) + log(8/0)
inf R(w (w.p)EAd-IXR
R(w,p) < 161
We note that unlike the bounds on & loss of Theorem 3.2, these bounds on 0-1 loss are independent of the range of utility values and only depend d. They provide sample complexity bounds which depend on d as Ollog d) and (d lollog d) for known and unknown weights respectively. Despite these PAC guarantees, empirical risk minimization can be particularly difficult this case, since the loss function as well as the function class log (u; w.p) log M (v; w.p) can be non-convex. To illustrate this non-convexity, we plot the value of the above function for two pairs of utility vectors with respect to p in Figure 6, with d = 6 and w = a/d. However, the quasilinearity of log M (u: w, p) log (v; w. p) with fixed can be used to design efficient algorithms.
4.1 Convergence Bounds Under LLD Noise
Decision making can be especially challenging if two actions are difficult to compare, and the preference data obtain can potentially be noisy. We first consider each comparison to be mislabeled in an i.i.d. manner with known probability E [0, 1/2). We make use of the framework developed by Natarajan et al. [16], and consider convergence guarantees under 0-1 loss.
Specifically, the unbiased estimator of f--1 is
(1 pp (1, plp- (1,--)
(t =
1 1
We conduct ERM with respect to fo-1 1 to obtain (w,p) E A x R (only learning if weights are known). We observe that f0-1 y) = (1 + ly)/2 1/2-Lipschitz in I, vl, y E (+1}. Using
Theorem of Natarajan et al. [16], we get the following convergence bounds:

---

Theorem 4.3. Given samples {((u,, va). w))== ~ DD, for any > 0 and for any E (0.1/2).
with probability at least 1 - with respect 0-1 loss,
(a) If w is known, then
8 inf R(w,p) - PER
(log2 d + 1) log(n + +1) + =2
log(1 /6)
R(W, P)
2p
2n
(b) If w is unknown, then
(d + 1) log(n +1
(1/0)
R(w, ())
inf
R(w,p) S 1 2p
+ 2V
(w.p)EAs-IXB
2n
A detailed proof of the above theorem is provided in Appendix A.7.
We note that although ERM is conducted with respect to f0 on the noisy distribution, the risks are defined on the underlying noiseless distribution. This gives (log d/(1 2p)²) and Old d/(1 2p)²) sample complexities for the known and unknown weights cases respectively. We note that when p O, the above bounds reduce the noiseless bounds in Theorem 4.2. Since the noise level p usually not known to us, it can be estimated using cross-vas cros-vvaldattio as suggested by Natarajan et al. [16].
However, conducting ERM on f0- might be prohibitively difficult due to the non-convex nature of the function. An i.i.d noise model might also be inappropriate in certain settings; next consider more natural noise model.
5 Pairwise Preference With Logistic Noise
Intuitively, we expect that two actions would be harder to compare if their social welfare values are closer each other. We formalize this intuition in the form of noise model inspired by the BTL noise model [4, 13]. Let w and p" be the true power mean parameters, and let r* E [0, Tmax] be temperature parameter. For an action pair (u, v), we assume that the probability of being preferred to v is
(I) We see that a larger difference between the log power means of and translates to higher probability u being preferred. If u and v lie on the same level set of log M(; "ww,")) the probability becomes 0.5, which matches the intuition of both actions being equally preferred. We also note the dependence of the probability on r": higher 7" corresponds to more confidence the preferences, with r" meaning indifference for all pairs of actions. The mislabeling probability is also invariant to scaling of u and v.
P = [| v): "/""""p"""" ,p),") 1+ exp (-T* (log M (u; w p-) log M ( w ,"))
Our learning task now becomes estimating w, and given data. We denote the function family in this case by
Tw.dd {T (log M:: (.:.pp) log M (:; w. ()) [T,p]
when the weights are known, and
Ta = {r (log M ((:w,)) log M w. p)) |r, w.p)
when the weights are unknown. A natural loss function to consider in this case is negative log likelihood, and consider PAC learnability with this loss. Using the framework developed in Section 3, we obtain the following PAC bounds:
Theorem 5.1. Given samples {(u,, vs), v:) ~ Dr and for negative log likelihood loss, for all
8 > O, with probability at least 1 6, (a) If w is known, then
2og 2 log n
C.
log (4/5)
R(w P) inf R(w, p) & 16rmaxk pER
+
+ B1
n
Vn
2n
7

---

(b) If w is unknown, then
2 log 16(dlog, d + 1) log
R(w,D) inf
R(w,p) S 16T max
(w.p)
2c
log(4/8)
167
+3
Vn
2n
where k = log (Mmax/ Umin)
We derive this result in detail in Appendix A.8.
This gives us sample complexity bounds of (1) and (dd d) with respect to d for the known and unknown weights cases respectively, thus establishing PAC learnability. An important distinction between Theorem 4.3 and the above theorem is that Theorem 4.3 bounds risk with respect to 0-1 loss, while the above theorem bounds risk with respect to logistic loss which is continuous and hence easier to control. Moreover, we estimate the noise level r in the logistic case along with and p. whereas Theorem 4.3 is concerned with estimating w and p.
As with the previous cases, non-convexity in this setting also makes global optimization with respect to w and (and hence ERM) difficult. We observe that logistic loss is quasilinear in w with fixed p², and this observation can be used to construct effective algorithm.
6 Empirical Results
We conduct several simulations on semi-synthetic data to gain additional insight into sample complex- ity and demonstrate an empirically effective algorithm. The implementation also serves to demonstrate the practicability of our approach, including the availability of individual utility functions.
Data. The dataset we rely on (which is not publicly available) comes from the work of Lee et al. [11] with a US-based nonprofit that operates an on-demand donation transportation service supported by volunteers. WeBuildAT is participatory framework that enables stakeholders, including donors, volunteers, recipient organizations, and nonprofit staff, to collaboratively design algorithmic policies for allocating donations. Donors provide food donations, volunteers transport the donations, recipient organizations receive and distribute the food, and dispatchers (nonprofit staff) manage the allocation and logistics. The "actions" are hundreds of recipient organizations that may receive incoming donation.
As part of this framework, Lee et al. [11] learned a (verifiably realistic) utility function over the actions for each of 18 stakeholders from the different groups based on 8 features: travel time between donors and recipients, recipient organization size, USDA-defined food access levels in recipient neighborhoods, median household income, poverty rates, the number of weeks since the last donation, the total number of donations received in the last three months, and the type of donation (common or uncommon).
In our simulations, we use the values of these stakeholder utility functions learned by Lee et al. [11] as the utility vectors. We fix p" and weight vector w' to generate the social welfare values (uu w.p.. We use noisy versions of these social welfare values in the cardinal case, whereas noisy pairwise comparisons between random pairs of utility vectors are used in the ordinal case.
Algorithm. As noted in previous sections, & and logistic losses are quasiconvex with respect to w for single samples when p is fixed. Although the sum of quasiconvex functions is not guaranteed to be quasiconvex, we empirically observe that gradient descent on the loss function applied to the data can still lead to convergence true parameters. As our simulations show, this minimum increasingly resembles w (the real weight) with decreasing noise. Thus, our algorithm consists of performing a grid search on p and conducting gradient descent on w for each p. We provide more details about the algorithm in Appendix B.
minimum which has empirical risk comparable to that of the
Cardinal case. We consider p" = 2.72 and a random weight w We then add Gaussian noise with standard deviation (uadd) u,(1)) y/ to each sample, where v corresponds to the noise level. The Gaussian noise is clipped to stay within (Wa1)) v.an). Finally, we learn and w using our algorithm, and we present the results in Figure 1.
A detailed explanation of this fact is provided in Appendix A.2.2
8

---

2,85
10
divergence
10¹
10"
2.80
80"
10
Value
10
samples
samples
Number samples
(a) Test loss
(b) K L(w")) ([w)
(c) Learnt p
Figure 1: Results for cardinal with number of samples. Different lines show results for different values added noise v. Solid lines correspond to values for learned parameters, whereas dotted lines correspond to values for real parameters.
16
Teat accuracy (nolseless
1.0
divergenne 10"
10
Test lest
0.8
0.8
4000
samples
samples
samples
(a) Test loss
(b) K L(w" (w)
(c) Noiscless test accuracy
100.0
Figure 2: Results for ordinal with number of samples. Different lines show results for different values noise level r. Solid lines correspond to values for learned parameters, whereas dotted lines correspond to values for real parameters.
In Figure la, observe that the test loss for learned parameters decreases with decreasing noise and increasing number of samples. We also observe that the test loss for learned parameters closely matches that for real parameters in Figure la. In Figure 1b, we observe that KL divergence between the true and learnt weights decreases uniformly with decreasing noise and increasing number of samples. This supports the fact that algorithm is indeed able to find the correct minimum. We also plot the trend of mean learned p in Figure Ic, and we observe that the learned increasingly resembles the real pa with lower noise and greater number of samples. Plots for train loss and loss on noiseless test data are provided in Appendix C.
Ordinal case. We consider p" -.662 and random weight w We compare each sample in the considered training data with 10 other randomly chosen samples, with the comparisons being noised according to the logistic noise model in Equation (1). We then learn and for each p in the chosen grid and then choose the best p. Our results are shown in Figure 2.
In Figure 2a observe that the test loss for learned parameters matches that for real parameters for small T" and a large number of training samples. The relative deviation between test losses progressively increases for smaller numbers of samples and smaller r* We note that small r* corresponds to more noise in the comparisons, which results in higher losses. However, the deviation also estimating the noise parameter, which is
between learned loss and true loss is smaller, as easier to estimate for small r", since the logistic function has larger gradient.
We observe uniform decrease in KL divergence between w and w' for larger number of samples and smaller 7*, again pointing to the effectiveness of the algorithm. We also observe that test accuracy on noiseless data increases with more samples and higher r". Interestingly, for 7" 0.1 and 7" 1, the test accuracy on noiseless data (Figure 2c) significantly higher than that on (noisy) test data, another indicator of effective ERM being conducted by the algorithm.

---

In Figure 4b in Appendix C, we observe greater variation in learned compared to the cardinal case. possible reason behind this that changes in p result in smaller changes losses for negative p than for positive p. This hypothesis is supported by simulations for the ordinal case conducted for p = 1.62, with results presented in Figure 5. Figure 5e, we observe that learned p is much more consistent with the real p as r" decreases.
We also conduct simulations on fully synthetic data to study the effect of d, and we present the results in Appendix E. We verify the theoretical Odd log d) scaling of error with unknown weights for the ordinal case in Figure
7 Discussion
Our work has (at least) several limitations, which can inspire future work. First, as seen in Section 6, we are able gain access to realistic utility vectors, in this case ones based on models that were learned from pairwise comparisons, Utilities are also routinely estimated for other economically- motivated algorithms - say, Stackelberg security games [21].
However, these estimates are of course not completely accurate. It is an interesting direction of future work to extend our results to the setting where the utility vectors need to be estimated, either by outside expert, or using input from the individuals themselves.
Although our experiments demonstrate convergence of the algorithm to the correct minimum, rigorous theoretical analysis about the nature of minima for the & and logistic loss functions still needed and could lead to algorithmic improvements. One issue is that scaling the algorithm to the national scale 10S, say, can be prohibitively expensive.
Finally, our work only applies to weighted power mean functions. While we have argued that this family is both expressive and natural, would be exciting obtain results for even broader, potentially non- non-parametric families of social welfare functions.
The ability to learn social welfare functions enable to understand decision maker's priorities and ideas of fairness, based on past decisions they have made. This has direct societal impact as these notions can be used to both understand biases and inform the design of improved fairness metrics. A second potential application is to imitate successful decision maker's s policy choices in future dilemmas or other domains. This may pose some ethical questions if the learning model is misspecified; however, the restriction of the function class to weighted power means, which is inspired by natural social choice theory axioms, mitigates this risk.
Acknowledgements
This research was partially supported by the National Science Foundation under grants IIS-2147187. 11S-2229881, and CCF-2007080; by the Office of Naval Research under grants N00014-20-15 1-288, N00014-24-1-2704 and N00014-22-1-2188 and by the USDA under grant 2021-67021-35339)
10

---

References
[1] Pathikrit Basu and Federico Echenique, On the falsifiability and learnability of decision theories. Theoretical Economics, 1279):3279-3355, 2020.
[2] Girish S Bhat and Carla D Savage. Balanced Gray codes. the Electronic Journal of Combina- torics, 3(1):R25, 1996.
[3] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[4] Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika, 39:324, 1952.
[5] Laurent Condat. Fast projection onto the simplex and the ball. Mathematical Programming, 158(1)5575-585, 2016.
[6] Cyrus Cousins. An axiomatic theory of provably-fair welfare-centric machine learning. Ad- vances in Neural Information Processing Systems, 34:16610-11621, 2021.
[7] Cyrus Cousins. Revisiting fair PAC learning and the axioms of cardinal welfare. In International Conference on Artificial Intelligence and Statistics, pages 6422-6442 6642, 2023.
[8] Ashish Goel, Reyna Hulett, and Benjamin Plaut. Markets beyond Nash welfare for Leontief utilities. 15th International Conference on Web and Internet Economics, 2019.
[9] Graham JO Jameson. Counting zeros generalised polynomials: Descartes' rule of signs and Laguerre's extensions. The Mathematical Gazette,
2006.
[10] Gil Kalai. Statistical learnability and rationality of choice. Technical report, Institute of Mathematics and Center for Rationality, The Hebrew University of Jerusalem, 2001.
[11] Min Kyung Lee, Daniel Kusbit, Anson Kahng, Ji Tae Kim, Xinran Yuan, Allissa Chan, Daniel See, Ritesh Noothigattu, Siheon Lee, Alexandros Psomas, al. WeBuildAI: Participatory framework for algorithmic governance. Proceedings the ACM on human-computt interaction. 3(CSCW):1-35, 2019.
[12] Li, M. Sanjabi, A. Beirami, and V. Smith. Fair resource allocation in federated learning. In 8th International Conference on Learning Representations, 2020.
[13] R.D. Luce. Individual Choice Behavior: A Theoretical Analysis. Dover, 2005.
[14) Vitalik Melnikov and Eyke Hüllermeier. Learning aggregate: Tackling the aggrega- tion/disaggregaatonn problem for OWA. In Proceedings of The Eleventh Asian Conference on Machine Learning, volume 101 of Proceedings of Machine Learning Research, pages
1110-1125, 2019.
[15] Mehryar Mohri. Foundations of machine learning, 2018.
[16] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. Advances Neural Information Processing Systems, 26, 2013.
[17] Giovanni Pellegrini, Alessandro Tibo, Paolo Frasconi, Andrea Passerini, and Manfred Jaeger. Learning aggregation functions. In Proceedings of the 30th International Joint Conference Artificial Intelligence, pages 2892-2898, 2021.
[18] Ariel D. Procaccia, Aviv Zohar, Yoni Peleg, and Jeffrey S. Rosenschein. The learnability of voting rules. Artificial Intelligence, 173(12):113--114) 2009.
[19] Feng Qi. Jia- Riang Mei. Da-Feng Xia, and Sen-Lin Xu. New proofs of weighted power mean incqualities and monotonicity for generalized weighted mean values. Mathematical Inequalities and Applications, 3:377-, 09 2000.
[20] Kevin W. S. Roberts. Interpersonal comparability and social choice theory. The Review of Economic Studies, 47(2):421-43 1980.

---

[21] M. Tambe, editor. Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned. Cambridge University Press, 2012.
[22] M Vidyasagar and M Vidyasagar. Vapnik-chervonenkiss, pseudo-and fat-shattering dimensions. Learning and Generalisation: With Applications to Neural Networks, pages 115-147, 2003.
12

---

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]
Section 2 establishes the problem's theoretical setting. Section deals with PAC learnability in the cardinal case, while sections 4 and address PAC learnaillity in the ordinal case. Section and Appendix B provide the algorithm and evaluation on semi-synthetic data.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Limitations are discussed in detail in Section 7
Guidelines:
The answer NA means that the paper has 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 separate "L_imitations" section in 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 on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or 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 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 in the paper. The authors should use their best 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.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: Proofs for all theorems are provided in Appendix A. 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 proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results 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 not)?
Question:
Answer: [Yes]
The dataset used is described in Section 6, and the details of the algorithm used are provided in B. We have also provided code for the semi-synthetic experiments. For reproducibility, all experiments are run with a seed, and the used seed values are specified in the code.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) 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., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: We rely dataset shared with by Lee al. [11]. It is not publicly accessible because it includes potentially sensitive information.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
Sttpe//giide//CoeSutiei wwt.SSubiisiiooooooo.oooo oeiiioinoccyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for 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: / /nipp. httpcccccppppccciccccooooo gwt///udde/////// /ooeeee//oodSmmmiiii weaianisssioooooiiiiiiio
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
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 possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The data generation process is explained Section 6. Details about the algorithm, in particular steps taken ensure convergence, are provided in B
Guidelines:
The answer NA means that the paper does not 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: We use the default error bars provided by the Seaborn library for the plots in Section 6 and Appendices C and E. These error bars describe the variation in observed metrics for different random splits between test and train data.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is 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% CL, if the hypothesis of Normality of 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 in the text how they were calculated and reference the corresponding figures or 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 execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Compute resources information is provided in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 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 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttps///eerrpps.c./bbbb/////bb csGuidelinss!
Answer: [Yes]
Justification:
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 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: Potential societal impacts of the work are discussed in Section 7
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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:
Guidelines:
The answer NA means that the paper poses no 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 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. Licenses 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 and describe the Food Rescue data used for semi-synthetic experiments
in Section 6
Guidelines:
The answer NA means that the paper does use 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 (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswiphchre toode.. 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 has changed) should be provided.
If this information 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:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset 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. Crowdsoureing 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:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS 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.
19

---

A Deferred Proofs
A.1 Proof of Lemma 2.1
Proof of Lemma /./ (a). Let > 0. Define 1; = uh for all i E [n]. Since 4, S 1 for all i E [n] and given that -i=1 wi
Maua
follows that Σi=1 wilk > = wi 1. Therefore, log(w;(,) S 0 for
each i. Given > > 0, we obtain
0 s log
Σ
wath
(p
1=1
= p log
Σ wilk
q
log
wiyk
< 1pp-l log Σ Wib
q
log
wit
Umax + p- log
With
Umax +
log
W
= log M (u; w, - log M (u; w.
This derivation similarly holds for the case 0 > > demonstrating the monotonicity of log (u; w,p) with respect p. The continuity of log M(u w.p) with respect to p p ensures the monotonicity for all E R. Since log is a strictly increasing function, this guarantees the monotonicity of M(u; w.p).
Proof of Lemma 2.1 (b). Since E wi = 1, we express wi = >i= Wy and consider d' - 1 variables.
For * 0, we have
d-1
)
log M w,p) p-p Σ with + un 1 1- Σ w/
1=1
log (uu; w.p)
up - u/
p
Ow;
Di=1
d-1
wane
+ n/d
d-1 >i=1
We
u
p
i=1
EL wan is positive since it is positive weighted sum of utilities. We aim to show that
p (uf u >
Suppose that u, ua. If then uf u > Conversely, p < 0, then of - up < O, but since p= is also negative, the product remains positive. Thus, us > ud, the log-norm increases with w,. A similar argument shows that the log-norm decreases if us < ud.
For O, we have
i log ((u
a
d-1
Σ ic log un
1-
1
Σ
wc
log
ud
Ow;
Dw;
f=1
U1
log
ud
① log M (u; w, w.p)
lim
p
Fw;
20

---

This indicates that for u, > the derivative is positive, implying an increase, and negative for u, us, implying a decrease. Thus, the function is monotonic for all w, E [d 1]. Since log is strictly increasing function, this guarantees the monotonicity of (u;; w.p).
I
Proof of Lemma 2.1 (c). We prove that log (u:wpp) - log M(v; w. is quasilinear. The proof for (u; w,p) follows by setting v = 1a-
As noted in [3], the ratio of two linear functions is quasilinear when the denominator is strictly positive. Given that (w, vP) 0 for all d 1- it follows that
f(w) (w, wW,
(w, vP)
quasilinear function. Furthermore, since f(w) > for all w E Ad-1, and for any x > ///P monotone for p R \ {(), the expression M(u; w. w.p)/M(v w,p) f(w)!/p is also quasilinear. Because g(x) log(z) is monotone, quasilinearity is preserved, which implies that log M (u; w.p) log M (v; w, p) is quasilinear as well.
A.2 Properties of Loss Functions
A.2.1 Quasiconvexity of &g Loss
Since (u; quasilinear. For W1, W2 E A4-1, we therefore have
w, p) is quasilinear by Lemma 2.1 (c), it follows that f(w) M w.p) is also
min (f(w1), [(w2) E f(Aw1 + (1- - A)w2) S max (f(w)), f(w2))
= f(\w, + (1 2 < max
Thus, f(w)? = (M(u; y)² is quasiconvex.
A.2.2 Quasilinearity of Logistic Loss
By Lemma 2.1 (c), we know that log M (u; w, p) log (v: w, w) is quasilinear. We consider two cases for the logistic loss. For 1, since (z)) log( + exp(- -x)) is monotonic function, preserves quasilinearity. For y 0, we have log (z)) log(1 + exp(-z)) + x, which is also monotonic and therefore preserves quasilinearity.
Using these properties, conclude that the logistic loss term -oloog - y) log(1 (x)) a quasilinear function.
A.3 Proof of Lemma 3.1
We differentiate between representations of Rademacher complexity:
R(F -B E,
sup
E (2Fe
n
fEF
Rabs
E,
sup
E (zii)
7
fEF
It is clear that Ri(F) S (F). We now list few results related to Pollard's pseudo-dimension.
Definition A.1 (Pseudo-shatteriing) Let H be set of real valued functions from input space X. We say C (#1...., Fm pseudo-shattered if there exists a vector r = (r1,...: Fi)) such that for all be (+1)** m
(b....., .h....,,..)), b,.,, there exists hú E H such that sign (h,( --)=))=000 by.
Definition A.2 (Pseudo-an (isedd-ddmession)) ). The pseudo- dimension Pdim (H) is the cardinality of the largest set pseudo-shattered by H.
The following lemma connects pscudo-dimensions to VC dimensions:
21

---

Lemma A.3 (Mohri [15]). For every h E H. define the binary function (x(x,r) = sign (h(æ) r).
Define Bи [B, h Hj. Then, VC(Bx) Pdim(H)
The following lemma bounds the Rademacher complexity using pseudo-dimension and covering numbers.
Lemma A.4 (Mohri [15]). For F S [0, 1]x with Pdim(FF)
F(c,FFdn)) - (2)
2d
where d, (f.() 4 Ei= (f(x;) -((x)))((z))))) 1/2
We also have the following covering number bound for Rademacher complexity:
Lemma A.5 (Mohri [15]). For F - [0,
2 2log (c, tc).
Rabo (F) inf c>0
n
We now turn to bounding the complexity for the unknown and known weights cases:
Proof of Lemma 3.1 (a). The function class is:
Mw.d (M(r; w.lp R).
Moreover, from Lemma 2.1, it follows that for fixed Rd. Mu; w.p) is non-decreasing function with respect to Consequently, there exists a pt E R &RUP { such that for any y E (Umin; Mmax)). ). we have M (u; w,p) for all p p', and (u; w.p) y for all p p". This implies that Bas (u, y) sign(M w) y) changes its sign exactly once as increases.
We note that for B (z, y). point be shattered (by choosing p p" and p p²). However, for two points u and v, the number of times a sign change occurs with increasing p for either u or v is most twice, meaning that only labels can be achieved. Thus, 2 points cannot be shattered. m
Proof of Lemma 3.1 (b). The function class is:
Ma [M(::. R).
We note that
By (u, y) = sign (M (u: w, p) - y) sign (log M (u; w.p) log y)
sign (log M (u; w.p) loog My w.iw)))
which, observe, is exactly the expression in the noiseless comparison-based setup for the unknown weights case. We show in Lemma 4.1 (b) that the VC dimension for this expression is upper bounded by 8(d 1). Thus, our result is proved.
A.4 Rademacher Complexity Bound for the Cardinal Case
Lemma A.6.
(a) If w is known, then
2 log 2 + 2 2 V
R(Mw.a) I Umax
n
Vn
(b) If w is unknown, then
log 2 + 16(2 log, 1) log
R(Mw.d) S Umax
7
n
where c. > 0 is a constant.
22

---

Proof. We prove the result for the case of unknown weights: the result for known weights follows by replacing the pseudo-dimense bound of S with that of Sw,d from Lemma 3.1. Let dp denote the pseudo-dimension in the unknown weights case.
1
R(Ma) = E.
GM(u:,,,))
sup (waplEAd 1XR i=1
Ex
sup
6illmax M(r:: w.P)
(w.p)Edd- 1=1
Umax Ee
sup (w.p)ESi-IX8
M (r:; w.p)
i=1
1
I Umax Ee
sup
Je, (r.
Ti (w.p)EAR-1X) x
1=1
Umax Raba
From Lemma A.4 and Lemma A.5, and given that log M (r; w.p) E [0, 1], we have
Wi,, dn) - (2) dp.
2 2oog + 4dp log(c/c)
Rabs (So) S inf
+e)
2 log + 2dp log n
(setting e = c/ cn)
Vn
thus giving
R(Ma) = umax (v2log
2 2 + 2d, log n
Substituting dp 8(d + 1) yields the required bound.
We observe that the above lemma provides bounds of O O(Vlog())/n) for known weights and (( log(d) log(n)/)) for unknown weights the Rademacher complexity. Notably, these bounds depend on Umax, indicating that the complexity of the function class grows as the maximum utility value increases.
A.5 Proof for Theorem 3.2
Proof. We prove the result for the case of unknown weights; the result for known weights follows a similar argument. For the loss, the function class is defined as
L2 (u W. w.P). y) (y M(u: w,
(.lu:. p))² Aa-1 x RJ.
Since both Mu; w, and yi lie within the range (M([)) u((a)] C [Uminn Umax], have y
M (u: w, w.p) [Mmin Umax Umax Umin] Over the bounded range [->, 7.], the function (t,
(t - y Lipschhti continuous with respect to t. Thus, using Talagrand's contraction lemma and Lemma A.6, get
*(C2) = Ri2 o Ma) S 2(umax Umin ) (M))
We then use the uniform convergence bounds for Rademacher complexity obtain
log(4/0)
R,(wp)) R(w,p) p)) < 8(Umax Umin )o((Ma) + 3/
sup (w.p)ed--1xe
2n
23

---

Thus,
R(w.p) - R(w,p) = Rn (w,p) Rn(w.p) + Rnn p) - R(w,p)) + (R(w, Rr, (n(
2 0 + + 2e
log(4/6)
16(umax Umin) ( (M(MMa) + VV
2n
Finally, substituting R(Ma) from Lemma A.6 provides the required bounds.
A.6 Proof of Lemma 4.1
First, we state a lemma from Jameson [9]:
Lemma A.7 (Jameson [9), Theorem 4.6). Let - R be defined as f(p) - exp(ber), where > b2 ... > bn and Σi= a; O. Define A₃ == Ei= 0g and denote by S(Aj) the number of sign changes in the sequence (A:) Then, the number of unique zeros of f is at most ((A,) + 1.
Consider the function f(p)
Ei
Ei way for u, E Rd with disjoint entries:
f(p) = Σ W.ue 1=1
Σ wpyp 1=1
Wy exp(p log u:)
Σ wi exp(p log vs).
1=1
Applying Lemma A.7, if wf; = w for all i, the sequence {A,}. consisting of sums of w or -w, can have most d sign changes. A sign change at index k implies Ag-1
and the next sign change cannot occur before index k + 2. Therefore, {p) has at most d zeros in this case. In the general case, where Wt * wy for some i * j. sign change in {A,} can occur any index except the first and the last. Thus, ('()) can have at most 2d I roots, sign changes are possible at all intermediate indices. We conclude that (u; w, w,p) p) Mn(v; ; w, p), defined over {d:o0), J. can change sign as a function p at most d times if w: 2= and up to 2d times in the general case.
Lemma A.8. Let R + R be two polynomials such that c c:= r(x) q(x) is a constant for all E R. and the sets of roots (.1,.... va) and {yh...., yak of r and g respectively are disjoint, positive and of size Then, for le 0, 1....,d the k-th power sums of the roots 21,-... ...... ,. Da are equal, i.e.:
, Fd and
Proof. Given that r r- = c. both polynomials have the same non-constant coefficients. According to Vieta's formulas, the k-th elementary symmetric polynomial of x, ex (x), is the sum of all products of l distinct v; s, and similarly e (y) for y. If - q = c, it implies that the symmetric polynomials derived from the roots of r and y are equal, ex (x) (y)
Newton's identities relate the elementary symmetric polynomials and the power sums as follows:
kee(x) = -e
ky Σ 1=1
where p. (x) the i-power sums of the roots. Given that ex) = c (y), we can equate the right-hand sides of the above identities to obtain the power sums px(x) and py(y). This yields p& (x) Py for each kt due to the recursive nature of Newton's 's identities and the fact that the elementary symmetric polynomials of and y equal for all & < d.
Hence, (x) = (y) for all = O,....
....., d - 1, which concludes the proof.
Given f(p) defined above, Lemma A.8 implies there exists disjoint u. E Ed such that Mu(u; w.p) = Mp(v; w),), for d - 1 unique values of p and for w; = 1/d. Moreover, suppose that for a set {p: heta there exist u, v E Rd and w E Ad-1 such that (,, w,p,) = Mp(v; w.).). Then, for any À 0, there exist u', v' e Rd such that Mp(u's w, Ap.) M,(''; Ap:).
24

---

Lemma A.9 (Jameson [9], Theorem 3.4). For any k < d and .... .....P E R, there exist u. E R. and w E A such that Mp p.) Mp(v; w. pi) for each i k. Furthermore, the difference Mı w, w,p:) Mv(v; w,P) pi) does not change sign within any interval (Di,Ptt)).
We now proceed to the proof of Lemma 4.1, which bounds the VC dimensions of the function classes Cw,d and Ca.
Proof of Lemma 4.1 (a). As there most 2d roots f(p). there be most 2d sign changes as p varies from -00 to oo. Consequently, the hypothesis class defined by all p (denoted as Mw.dl a) is subset of the hypothesis class that consists of at most 2d 1 sign changes on the real line. This larger hypothesis class is denoted by Ha. and we have VC(.Mw.e) S VC(Ha).
Let us consider samples {u, v; v For each sample, sign changes occur at most 2d - times, and hence the total number of changes in labeling over the entire real line bounded by (2d - 1)m (as changes, each change in labeling corresponds change in sign for at least one of the samples). This implies that the total number of possible labelings is (2d 1)m + 1.
If the set of m samples is shattered, the upper bound derived above should be at least as large as the total number of labelings possible. We thus have:
(2d 1)m + 12 2mh
We can show that m 2([log2 d + 1) points cannot be shattered. Consider
2m
(2d
1)m - 22( d +1) 2(2d - 1)( d1 +
> 22(1og, d+1) - 4dd4dd + 2 d| 4d + 11
4d 4d log, d| 2| d|
4d +
4d(d - [ogg d)) - 4d + 2 foog d| +
2 4d - 4d + 2 log2 d 1, since d - [log2 d) 2 1 Ad E
1ogg d1 +
Thus, m 2(log2 + 1) points cannot be shattered, meaning that VC(Ha) 2(logg + 1).
We now bound the VC dimension for the unknown weight case. Consider p + In this case, hypothesis C((u, v); w.p) p) can be expressed as
log Σi wru?)
log Ei=1 Wa's
d log
d Σ
sign
sign (p) sign
log
Σ ure?
way?"
1=1
d
sign (p) sign
Σ wane -
Σ
wiy!
i=1
sign (p) sign ( ((w, up v²))
sign ((w, sign (p) (u² v²))).
where u = (uf = Thus, for a fixed p. the set of viable w's spans a halfspace. We note that each component of sign (p) (uº vP) is continuous, which means that (w, sign (p) (ux vP)) is continuous function in and p.
For n > d samples {(u,, va), " we define (p) sign (p) (u² v"),ie [n]. F 0. For fixed p. we note that the set of possible labelings for w E A is subset of the set of possible labelings for w Rd, which in turn the set of labelings generated by n hyperplanes. Since this problem has VC dimension d, the number of possible labelings for a fixed p is upper bounded by (n + 1)d. Let B(p) denote the set of possible labelings for hyperplanes defined by (p) for particular p.
Lemma A.10. Let pı and p2 have the same sign, with a labeling & E (+13" such that & & B(pt) but E E B(pz). Then, there is a p E P2] such that there is set of d linearly dependent vectors hay (p), (p)...., ...,, baa (p).
25

---

Proof. Let & be the labeling which is in (p2)) but not in B(p)). Since this labeling is not in (p1).. for each w, there some hyperplane h; (p1) such that & (w, (p:)) ) Since this labeling is in ((22), there is some w such that ( (w, (P2)) 2 0 for every E [n].
Let B C IR denote the unit hypersphere around the origin. Since the labelings are invariant to the scale of w, the set of possible labelings for E R is exactly the set of possible labelings for w B
Consider the quantity
(p) max min & (w,)), wes
We observe that if m(p) < 0, for each there is some i E [n]] such that & (w, h:(p) 0, i.e., the labeling is not attained at any point. On the other hand, if m(p) 2 O, there is some w such that the labeling is attained at w. Since (w, (p)) is a continuous function in w and p for all i E [n]] min; & (w, h, is also continuous function in w and Thus, mp() is also a continuous function in p.
Using this fact and the intermediate value theorem, there should be some E [PL. Pa] such that m(p) 0. Let w B be vector at which mpp) = 0 is attained. We now show that at this p, at least d of the n vectors (h;(p)) are linearly dependent.
Suppose this were not the case, i.e., any set of d vectors in the set is linearly independent. This means that most d of the vectors lie on the hyperplane {x (w, x) 0}. Let (())) (p), .... h (p) denote these vectors, with S
Since m(p) 0, there should be least one such vector. Let H kxd be the matrix with these vectors the rows.
If these & vectors are linearly dependent, we can add any of the remaining n - vectors to get a set of d linearly dependent vectors. Let consider the case where they are not linearly dependent. Consider (x: Hx = 1,3. This is an underdetermined set of linear equations, and the set should be non-empty (because of linear independence of the k vectors). Let Xg be one of the vectors in this set.
(w.b.(p)) We have (x)),,(o))
Let t >> maX4e(n)
(w + hp()) = (w,h,(p)) + (x0,h4(())
(w,hi(p) max (w, (w,hy(p)) (xo, h.(p))
Jein| (xo, hp(p)
(w, h;(p)) (xo. h:(p))
2 (w,hi(p) (xo, h,(p))
-
Thus, w + txo is a point such that +w bx > 0 for all i E [n]. This means that m(p) > O, which contradiction. Intuitively, this means that if any d vectors in {h+(p)) are linearly independent, then m(p) > 0. Thus, there should be a set of d linearly dependent vectors h..).......))) (p)
From the above lemma, we observe that any change in the set of labelings is accompanied by a ap which gives d linearly dependent vectors.
Proof of Lemma 4. (b). Using the lemma above, to bound the number of possible labelings, we first bound the number of p's such that there are d linearly dependent vectors.
Consider set of d vectors hp))).... ... hu(p)) As the vectors are linearly dependent, the determinant of the matrix constructed using these vectors should be zero. We should thus have
sign (p) (u)1 of
sign (p) (ufa -efa)
= 0.
sign (p) (ufa - oi
sign (p) (uf - 2ad)
Upon expanding the determinant, we get an equation of the form E a.d, which has 24 d! terms. From an earlier lemma, we know that this equation should have at most 2d dd! roots. Upon adding the original configuration, get 2d d! possible configurations. The choice of the d vectors can be
26

---

made in (2) ways, and hence we have bound on the possible changes as 2dd!(() (2)) In the worst case, we assume that all the labelings are changed, and we thus get an upper bound on the changes as
(n + 1)d2ad! d
In the beginning of the proof, we had carefully set aside p O. We now observe that p is root of the above system of equations. Thus, we are implicitly considering any possible changes at p 0 as well.
We can show that n = 8([dlog2 d + 1) points cannot be shattered.
(n+ + 1) d!
n d
= (n + 1)d2d n(n - 1)... (n-d (n-d+1)
(n + n2
nd
We now show that for every d E N. the inequality id nd < 2" holds, i.e. n-d- 2d n 0 for n [[[d d] + 1). For d E
{1, 2}. this statement can be verified directly. Therefore, 1 > 0 for any 2 3.
suffices to show that (z) == 8(x log2
1) 2x 18g logz x 1)]
f(x) > 8x log, r 2x logg (16 logg x) + 9, for x log, 1,
6r log, r 2x loga (log, z) 9x +9 9
> 4x log, r - 9x + 9 = g(x).
log we note that g2( 4/ log - 5 0.77 O, with g((x) being an increasing function. Thus, f(x > g(z) > 0 for all 2 3. This means that f(x) > 0, which proves our bound. This implies
We note that g(3) = 12 3 - 18 > > O. Moreover, g'(x) = 4 log, + 4/logg - 9, and
that the VC dimension bounded above by 8(d d 1)
Proof of Lemma 4.1 (c). Take m = (d) + 1. Let di..... 02m E {=1)m be a Gray code ordering
of the set {+1]"h such that two successive values have Hamming distance of and that the number
of changes in different bit positions is at most 2 I d (for the existence of such an ordering, see [2]). For < 2mm denote by 8; E [m]] the bit position in which a; and 0+41 differ. By using Lemma A.9 times, there exists a sample (u; va 1m and p1 <... < p2m-1, where p; satisfies || llp: = || [pp.
8 j. Furthermore, define Po -oc, and note that each interval (pi, Pi+1) for 0 < < 2m corresponds to a unique combination of labels over {u,, v1
When the weights are unknown, we observe that p = 1 similar to the case of linear classification with the constraint of positive weights and no bias term. This is because
C((u, v): 1) sign (M; w, 1) - M(v; w. 1))
sign (log M (u; 1) log M(v, 1))
sign Σ
w. wn u.)
==1
Since linear classification with no bias term has VC dimension of d - 1, this is a lower bound for the VC dimension of Cw.d-
L
A.7 Proof of Theorem 4.3
Proof. We prove the result for unknown weights. with the known weights result following similar
steps. We consider the function class Ca as in Section 4, with lo-1 loss being 60-1 (t. y) = (1
ty)/2, y {=1}. We observe that 4 is 1/2 Lipschitz w.r.t. t. Thus, by applying Theorem 3 of
Natarajan et al. [16], we observe that w.r.t. fo-1 on the noiseless data distribution,
1og(1/8)
R(w, P) - R(w, I ACA)(CA + 21
(2)
2n
27

---

where L, (1+ 1p+1 - P+1 P+1- Here, p+1 and p-1 are defined as the probability of mislabeling true positive and true negative examples, which our case the same value, p. Thus, Lp = 1/((111 2p)) in our case, We obtain R(C,) using the VC bound on Rademacher complexity:
16(dlog, d 1) Iog(n +
R(C,)) S
Substituting it in Equation (2) concludes proof.
A.8 Proof of Theorem 5.1
Proof. We prove the result for the case of unknown weights; the known weights case follows similar steps. First, we establish bound on the Rademacher complexity of
Tw.a a = {i (log (-; (.,.w)W)) p) log M w. p)) T,p}.
Define
Ui(d)
log (u, w. log (2(1) + log
log (r.; w,9),
Ui(1)
and
(i(d)
log MM,, w.)) log v((1) + log
log M (r'sw,,))
M1(1)
1
((a))
E,
sup J.W. P
EJ (log M(;;:; - log ((v; w.p))
n
E,
sup
Ei log M (u;; w.p)
+
Eg
sup
Ti)T log M (v;;w,p)
T.W.P
11
T.W. P
i=1
1
1
E,
sup
T log M (u, w.p)
+ E.
sup
E log M (vii w.p)
T.W.P
n
T.W.P
==1
1
Ui(d)
E.
sup
ETT log 41(1) + log
log M (I:; w, w.,g)
T.W.P
t=1
11(11)
(((d)
E
sup
G7 log log + log
log M('r: w.g)
T.W.P 1=1
0((1)
1
Ui(d)
E
sup
log
log M (r:;; w,
T.W.P i=1
(4(1))
1
(i(d)
E,
sup
EiT log
log M (r/s w.
T.W.P im
(1(1)
K E.
GT log M (r.;w,))
+ 16
G7 log M (r/s w.
sup
sup
T.W.P
1=1
w.p
Tiaxx
E.
sup T.W.P
log M(r;;; w.
Tmax Ri
E.
sup T.W.P
log M ((13 w.
1=1
1=1
2Tmax KD (aaahoSS. (Sa).
We now apply the bound on (Sa) from Appendix A.4 to obtain the following bound on RR(T)::
2og + 16(d d 1) log
A(T)) S 2mmax
n +
Vn
28

---

Finally, we use the uniform convergence bounds derived from Rademacher complexity to establish the following PAC bound:
R R(W. P) R(w,p) = (R,,w,)) Rm Rn(wp)) + (n.(w.)) - R(w,p)) + (R(w. (..
50+ +
(lg(4/0)
= (Ta)(TT) + -61
2n
B
Algorithm
Our algorithm can be broken into two nested steps. The first step consists of choosing and the second step involves conducting gradient descent (and possibly 7) to obtain their empirically optimal values, w and p. In our experiments we choose using grid search. However, optimization over p can also be done using other methods like simulated annealing. We minimize the & loss in the cardinal case with weighted power mean and the logistic loss in the ordinal case with log weighted power mean. The algorithm's 's pseudocode is presented in Algorithm 1.
Algorithm ERM algorithm for weighted power mean- bean-based optimization
Require: {(x, y))
W 1/d
Obest f 0
0
for E [Plowers Plower + C,
.PPpper Pupper| do
V + arg minw
((M(u; w. w.p), ((M w,p), y:)
w arg mill
v < Whest then
W w
Ubett f-
end if
end for
Return W, Ubest
Note that for the ordinal case, would optimize over r along with w. For our experiments,
Plower 3.5 and Pupper = 3.5. We use a grid resolution of e = 0.1. Since the function is not convex, use several tricks to ensure quick convergence:
While Algorithm 1 from [5] for projection onto the simplex, it can potentially be time consuming. Thus, we project the gradient w itself on the unit simplex and use it for gradient descent, with the simplex projection algorithm being used only when some weights become too small/negative.
To prevent the algorithm from taking excessively large steps, use the learning rate to clip the norm of the gradient. More specifically, if gt is the gradient and À is the learning rate, we use the update
gt+1 = 9t min (A. 119el12)
9t
[g ll2
If the optimal value hasn't 't improved in a certain number of iterations, the algorithm may be oscillating above the minimum. We thus halve the learning rate to encourage better convergence.
If the learning rate becomes too small, the steps taken would be too small to change the loss significantly. Thus, we terminate the algorithm. We also terminate the algorithm if the range of the past few losses is too small.
29

---

We also conduct gradient descent parallely starting from d + 1 points. The d + points correspond points close to the vertices of the simplex (corresponding to almost one-hot vectors) and the centroid of the simplex. This was done since convergence was observed to be slow for certain weights. At each step, Ubest updated according to the point giving the minimum loss.
We ran the experiments on an NVIDIA RTX A5000 GPU. The algorithm with the above settings takes about 30 minutes to check for all 71 values of p.
C Semi-synthetic Experiments: Further Information
Here we provide additional results and details from our semi-synthetic experiments. Figure 3 shows cardinal case results with varying sample sizes and noise levels. Figure 4 provides ordinal case results across different sample sizes and values of 7. Figure 5 displays ordinal case results for p 1.62 across varying values o.
10
Test loss (noiseless)
10
-3
Train loss
4
10
10
10
10
10
10"
Number of samples
Number of samples
(a) Train
(b) Noiseless test loss
0.001
0.167
Figure 3: More results for cardinal case with number of samples. Different lines show results for different values of added noise. Solid lines correspond to values for learnt parameters, whereas dotted lines correspond to values for real parameters.
D Additional Plots
Figure 6 shows pair of utility vectors (u, v) such that with w 1a/d, Mu; w.p) log (v; p) is non-convex. Upon slightly changing the value of to v', we see that there can be significant change in the region {p= log M (u; w,p) log M (v; w.p) > 0}.
E Simulations
We conduct additional simulations cardinal and ordinal data with logistic noise.
For each d and n, we construct a dataset a specified range [umin: Umax] id = [L, 100004 Each individual i is assumed have scaled and translated beta distribution over [umin Umaax] with the parameters (as, 3.) differing for each i. Utilities for each action are drawn independently for each individual to construct utility vector. The underlying weight vector is sampled uniformly from A2-1-
To learn p (and w if needed), we assume to be in fixed range, in this case |-10, 10). We begin with random sampling stage, where Nrandom instances of p (and w) are uniformly sampled. At the end of this stage, we select the parameter set with the lowest training loss and then perform gradient descent for Ngrad steps. We observe that this two-stage method yields good results across the values of d we consider. Each setting is run three times to obtain error bounds on the empirical results.
30

---

-0.5
-1.0
Train loss
Value of
-1.5
10"
-2.0
-2.5
500
1030
2080
4000
5000
500
1000
2000
4000
8000
Number of samples
Number of samples
(a) Train loss
(b) Learnt p
10
Test loss (noiseless)
0.9
Test Test accuracy
0.8
0.7
10"1
0.6
500
1000
2000
4000
8000
2000
Number samples
Number of samples
(c) Test accuracy
(d) Noiseless test loss
1.0
10.0
40.0
100.0
Figure 4: More results for ordinal case with number of samples. Different lines show results for different values of т. Solid lines correspond to values for learnt parameters, whereas dotted lines correspond to values for real parameters.
In the unknown weights case, we observe that sampling occurs in d dimensions. As increases, we encounter the curse of dimensionality. meaning that Nrandom would need to grow exponentially with d maintain sampling density across different d. This makes maintaining the same density impractical for larger dimensions. As compromise, we increase Nrandom linearly with d.
E.1 Cardinal Values
For cardinal values, we add Gaussian noise to each y with standard deviation (uga) - u(1)/11 /10 and clamp the values (u()), M(ay)- Experiments conducted for both known and unknown weights with 22 Figure 7a (known weights) and Figure 7b (unknown weights) show the estimated test loss on noiseless test data generated using the parameters.
observe relatively little change in the test loss difference for known weights as n increases. However, for higher d, there is greater decrease in test loss with increasing when weights are also being learned. The estimated test loss also increases with d, with stronger trend for unknown weights.
E.2
Logistic Noise
For logistic noise, we generate pairs of utility vectors with p 0.9 and w obtained through random sampling, then mislabel each instance according to Equation (1) with -* 10. Since we also need to learn т, we set Tmax = 50 and sample uniformly along with p (and w). Figure 7a (known weights) and Figure 7b (unknown weights) show the accuracy noiseless test data of the learned parameters.
31

---

10"
KL divergence
10
Test loss
10
10
10
10
1000
2000
8000
500
1000
2000
4000
8000
Number of samples
Number of samples
(a) Test loss
(b) K
Test accuracy (nolseless)
1.00
0.90
Train loss
0.85
10-
0.80
0.75
0.70
10
2000
1000
2000
4000
8000
Number of samples
Number of samples
(c) Noiseless test accuracy
(d) Train loss
Test loss (noiseless)
0.8
Value p
0.11
2.0
0.5
10
Number samples
Number samples
Number of samples
(c) Learnt P
(f) Test accuracy
gg) Noiscless test loss
100.0
Figure 5: More results for ordinal with p 1.62. Different lines show results for different values of r. Solid lines correspond to values for learnt parameters, whereas dotted lines correspond values for real parameters.
32

---

Difference in log power means
(u, v)
1.5
(u, v')
1.0
0.5
0.0
-0.5
2
5
P
Figure 6: An example showing the non-convexity of log (u, w, w. - log (v, w. w)p.. We see that the function has five roots for (u, v), but is translated downwards for (u, v') and has only three roots in this case. If the correct label is for both pairs, then p should be greater than 6; however, gradient-based optimization can stop between and 4, which is local optimum and does not give correct labels to both points.
0.20
Estmattdd (noleeless) Test
Estimated (noloeless)
0.15
0.10
0.04
0.05
0.00
10
10
10"
10
10"
(a) Cardinal social welfare values, known weights
(b) Cardinal social welfare values, unknown weights
Acourad (nclseless)
1.00-
Test Accuracy (noiseless)
0.98
0.9
0.98
0.94
0.92
10"
10
n
(c) Pairwise comparisons with logistic noise, known weights
(d) Pairwise comparisons with logistic noise, unknown weights
d=
d=
Figure 7: Results for synthetic data cardinal and ordinal logistic tasks
Across different settings, the proportion of correctly labeled samples in the training dataset has mean 71.4%, with a maximum of 86.5%.
For known weights, accuracy increases with n. and mean accuracy remains high (> 93%) across d. Differences between curves for various values of d are minimal, with all approaching near near-perfect accuracy becomes large. This suggests that error bounds may be independent of d. For unknown weights, a clear trend of decreasing performance with increasing d observed, expected due to the O (V d) dependence of logistic loss enror bounds. Nevertheless, all settings achieve high
33

---

accuracy as n merrasss. Up to moderately high d, the logistic noise model successfully finds highly accurate parameters despite significant mislabeling in the training data.
Test Accuracy (nolseless)
0.8-
5
10
0.7
0
10 15
20
25
n= y n/ldlog nlog d')
Figure 8: Verification of (d log d) risk bound for ordinal case with logistic noise, unknown weights
In Figure 8, we re-plot the test accuracy a on noiseless data against v = /n/ (dd n log d), a re-scaled version of Figure 7d. Theoretically, and r are related as 1 (1/n)) The alignment of all curves in Figure 8, compared to the original curves in Figure 7d, provides evidence that our risk and sample complexity bounds indeed scale d dloog n log d for the ordinal case with logistic noise and unknown weights.
34


Reviews:
[{"review_id": "tSQobUqdXa", "reviewer": "Reviewer_5Qbq", "summary": "The paper is about learning social welfare function which belongs to a well-studied family of weighted power mean function, as a way to understand a policy maker's rationale. In particular, the paper focuses on two settings: 1) when the input is the vector of utilities/social welfare, and 2) when the input is a pairwise comparison. The paper derives theoretical bounds for different social welfare information for different kinds of loss function with both known and unknown weights, and", "questions": "1. How should I understand the \"pseudo-dimensions\" of $M_{w, d}$ and $M_d$ in line 161?\n\n2. For the pairwise comparison setting, does it require access to the pairwise comparisons between all pairs of actions? Can it be extended to a setting where there's only partial comparison available, if so, how does it change the theoretical bound?", "limitations": "See above.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper focuses on an interesting and important question on social welfare function learning, which has great potentials in social learning and policy making. Overall, it is well-organized and well-presented. The theoretical results are solid and elegant. Overall, the authors are careful and transparent about evaluating both the strengths and weaknesses of their work. The claims/arguments are explored in sufficient depth.", "weaknesses": "I find some of the results hard to interpret, for example, the bounds in Theorem 3.2. It would be great if the authors could add intuitions behind the result and better demonstrate the influence of each term.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I find some of the results hard to interpret, for example, the bounds in Theorem 3.2. It would be great if the authors could add intuitions behind the result and better demonstrate the influence of each term.\n\nWe appreciate the reviewer's comments and will add further intuition about the role of each term in our results to make the bounds more interpretable.  \n\nOur bounds provide a characterization of the sample complexity of learning social welfare functions. Theorem 3.2, for example, provides bound for learning from cardinal utility data.\n\nThe first term in both bounds of Theorem 3.2 depends on $\\xi = u_{\\max}(u_{\\max} - u_{\\min})$. This quadratic dependence on the range of utility values is expected, since the $\\ell_2$ loss also scales quadratically with the magnitude of the utilities (equivalently with $\\xi$). \n\nWhen the weights $\\mathbf{w}$ are known, there is no dependence on $d$ in the first term. However, when $\\mathbf{w}$ is unknown, the first term grows as $d\\log d$. This means that to keep the first term roughly constant, the number of samples $n$ needs to increase proportionally to $d\\log d$ as $d$ grows. This is intuitive since learning the $d$ parameters in the unknown weights case requires a proportional increase in the number of samples.\n\nThe second term in both bounds is an artifact of applying the Rademacher bound.\n\n> How should I understand the \"pseudo-dimensions\" of $M_{w,d}$ and $M_{d}$ in line 161?\n\nThe proof of Lemma 3.1 in the appendix provides the formal definitions related to pseudo-dimensions (Definition A.4 will be added for completeness). Intuitively, the pseudo-dimension plays a role similar to the VC-dimension for binary function classes, and these complexity measures directly translate into sample complexity bounds for PAC learning. We will add a short clarifying remark to this effect in Section 3.\n\n> For the pairwise comparison setting, does it require access to the pairwise comparisons between all pairs of actions? Can it be extended to a setting where there's only partial comparison available, if so, how does it change the theoretical bound?\n\nOur results hold even if we only observe comparisons for a polynomial in $d$ number of pairs for known and unknown weights respectively, as long as these pairs are drawn i.i.d. from some underlying distribution. In other words, we do not require access to pairwise comparisons between all pairs.\n\n[1] Anthony M, Bartlett PL. The Pseudo-Dimension and Fat-Shattering Dimension. In: Neural Network Learning: Theoretical Foundations. Cambridge University Press; 1999:151-164.", "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": "IhxCT2xjdX", "reviewer": "Reviewer_7Nn5", "summary": "This work studies learning the social welfare function from a power mean function class.\n\n- They first consider the cardinal social welfare setting, where the data distribution is over the utilities and social welfare values. They provide the upper bounds on the pseudo-dimensions of the function class and then apply them to bound the generalization loss.\n\n- They then consider pairwise preference setting, where the data distribution is over utilities of a pair of actions and the comparison of their social welfare values. They provide bounds on the VC dimension of the function class and then apply them to bound the generalization loss. They further study two noisy settings, iid noise and logistic noise.\n\n- Finally, they conduct experiments to justify their results.", "questions": "see weaknesses.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This work studies a new problem of learning social welfare function.\n\nThe writing is very clear.\n\nThey provide both theoretical and empirical analyses.", "weaknesses": "The availability of labels in the real world: In the cardinal setting, the label of the data point is the true social welfare value. I am curious if there really exists any such labeled data set. I have the same question in the pairwise comparison setting.\n\nThe technical contribution seems to be limited. It looks like the results are derived by applying standard learning theory results. If there are any technical challenges in deriving the results, e.g., Lemmas 3.1 and 4.1, it would be great if the authors could address them. This is also not a new approach but standard ERM. So far, the problem studied in this work looks like a special case of general learning problems and doesn't require any new techniques.\n\nThe experimental results for this problem also look consistent with the phenomena in general learning, e.g., loss decreases with decreasing noise and increasing sample size. What is the takeaway information from the experiments?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The availability of labels in the real world: In the cardinal setting, the label of the data point is the true social welfare value. I am curious if there really exists any such labeled data set. I have the same question in the pairwise comparison setting.\n\nLet us start with pairwise comparisons. In our paper, we use data from the work of Lee et al. on food allocation, from which we derive the learned utility functions of participants/stakeholders. Their data also includes food allocation decisions made by a human decision maker (specifically, a \"dispatcher\"). These allocation decisions provide ordinal information and induce pairwise comparisons: for each of thousands of decisions in the data, the chosen alternative is preferred to each alternative that was not chosen. Consquently, we have the data to learn the $p$-mean welfare function optimized by the human dispatcher in practice. We did not run this experiment as it requires quite a bit of data processing and does not seem to give generalizable insights. Nevertheless, this shows that pairwise comparison data is, in fact, available, and demonstrates why we'd expect to obtain such data more generally. \n\nThe cardinal setting is important to study to understand the complexity of the problem, before analyzing the harder pairwise setting. Obtaining cardinal labels is more challenging but not impossible. We're actively working on this through collaborations with domain experts in public health and disaster management. We're designing experimental platforms to elicit cardinal labels from real decision-makers in these domains. In other words, we're actively working to bridge the gap between theory and practice through ongoing collaborations and experimental design efforts. While it's difficult to convey the full scope of our work within the constraints of anonymous review, we're genuinely committed to making this approach practically viable.\n\n\n> The technical contribution seems to be limited. It looks like the results are derived by applying standard learning theory results. If there are any technical challenges in deriving the results, e.g., Lemmas 3.1 and 4.1, it would be great if the authors could address them. This is also not a new approach but standard ERM. So far, the problem studied in this work looks like a special case of general learning problems and doesn't require any new techniques.\n\n\nWe disagree with this comment. While the VC and Rademacher based bounds are standard, deriving these quantities for the specific class of social welfare functions is technically challenging as we outline below. Similarly, while ERM is standard, we demonstrate how to leverage properties such as quasi-convexity of the class of social welfare functions to implement the computationally challenging ERM in practice and enable learning in real world settings. We highlight the novel technical challenges and contributions in our work below.\n\nLemma 4.1 presented significant technical challenges. For the known weights case (4.1a), a key difficulty was bounding the number of roots of the difference of two weighted power mean functions. This required applying a little-known result by Jameson on counting zeros of generalized polynomials, leading to a tight VC dimension bound of $O(\\log d)$, which scales non-trivially with d. For unknown weights (4.1b), we developed a novel proof technique involving analysis of linear dependence among vectors defined by utility differences. This required intricate combinatorial arguments to establish an $O(d \\log d)$ upper bound, which isn't derivable from standard learning theory results. \n\nFor the lower bound with known weights, we provided a lower bound (4.1c) using a Gray code construction inspired by Bhat and Savage, demonstrating that our upper bound in this case is tight. \n \nBeyond our lemmas, we proved quasi-convexity of our functions with respect to weights for fixed p. This property holds for individual samples but may not extend to empirical loss over multiple samples, since the empirical losses we consider involve a mean over multiple samples. Nevertheless, this observation allowed us to design a practical, performant algorithm, demonstrating real-world applicability while highlighting our problem's complexity.\n\n> The experimental results for this problem also look consistent with the phenomena in general learning, e.g., loss decreases with decreasing noise and increasing sample size. What is the takeaway information from the experiments?\n\nOur experiments offer insights beyond typical learning phenomena, specifically for learning social welfare functions. They validate our hypothesis that gradient descent with fixed $p$ is effective, despite the absence of guaranteed quasi-convexity.\n\nUsing semi-synthetic data based on real-world utility vectors, we demonstrate our approach's practicality. Despite the non-convexity in $(\\mathbf{w}, p)$, our algorithm consistently converges to parameters close to $(\\mathbf{w}^*, p^*)$, which is not captured by our theoretical results. This convergence is crucial, as it indicates that the learned $(\\hat{\\mathbf{w}}, \\hat{p})$ accurately captures the true weights and fairness notion with sufficient samples.\n\n Key takeaways include:\n1. Empirical validation of the scaling laws established in our theoretical bounds\n2. Demonstration of effective learning with realistic sample sizes using a computationally feasible algorithm\n4. Evidence that learned parameters closely reflect true individual weights and fairness notions (e.g., KL divergence between true and learned weights decreases to <0.1 with sufficient samples)\n4. Quantification of sample complexity increase with noise under various noise models.\n\n These results not only support our theoretical contributions but also highlight the practical applicability of our approach in learning and interpreting decision-makers' implicit social welfare functions.", "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": "TataE0MYGo", "reviewer": "Reviewer_W5KA", "summary": "This paper studies the learnability of social welfare functions -- which are functions over the utility of a group of voters and an outcome. Under varying information schemes, they address the question of how well it is possible to learn the social welfare function being used by a decision maker. The first setting considers learning when cardinal values of actions are knowable, which the authors point out corresponds to regression. The second setting looks at when the information given is a pair of utilitty vectors and some indication of which vector corresponds to higher social welfare. Finally, the authors consider the pairwise model when information is noisy. The paper shows that in all settings being considered, a large class of social welfare functions are learnable with a polynomial number of samples. Experiments demonstrate the existence of a practical algorithm for these results.", "questions": "N/A", "limitations": "Some discussion has been included but it is somewhat limited and surface level.", "rating": 4, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The problem being studied in this paper is well-defined and seems like it may be interesting. Despite the questions asked not being obscure, I am aware of little work that studies similar ideas ([17] being the exception, and I've always thought it odd that more work has not directly built atop [17]).\n\nThe methodology taken in the paper seems quite reasonable. While the proofs are not included in the body the results appear correct, to my limited understanding.\n\nThis problem is certainly able to inspire potential future research and provides a reasonable contribution in its own right.", "weaknesses": "While only incidentally a weakness of this particular paper, the state of science would be better if this were three separate papers (or a journal submission). There is simply not enough time to consider the paper in depth and the parts of the paper important for peer-review (ie. the proofs and many validation experiments) are not in the part of the paper that gets the bulk of reviewing attention so my understanding of the paper is quite limited; I found the math quite dense and open to improved clarity.\n\nAs far as clarity is concerned, the paper is moderately readable but I feel that the results could be explained somewhat more clearly without requiring additional space. The introduction does an adequate job of outlining the common idea of social welfare and what problem the paper studies. I understand what the problem solves but not until the end of Section 7 is there some suggestion of why this problem might be interesting. Motivating the questions in the paper earlier would be useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "At the risk of slightly abusing the rebuttal, we note that overall you seem to have a positive view of the paper. You write that the problem \"seems like it may be interesting\" and it \"provides an interesting contribution in its own right,\" the methodology \"seems quite reasonable,\" the results \"appear to be correct,\" and the work \"is certainly able to inspire potential future research.\" The weaknesses you list don't appear to be criticisms of the paper; the first seems to reflect a shortcoming of the NeurIPS reviewing timeline, and the second is that the paper is \"moderately readable\" with a suggestion (which we would be happy to follow) to move some of the discussion to the introduction. \n\nIn light of this, we would be very grateful if you would consider updating your rating of the paper. Alternatively, we would kindly ask that you clarify the weaknesses that lead you to recommend rejection.", "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": "lvlB7uTRzY", "reviewer": "Reviewer_1QjM", "summary": "The authors study the learnability of social welfare functions given decisions data by a central decision-maker that is taking into account their constituents' welfare. They discuss PAC bounds according to a number of settings with a focus on weighted power mean functions. These settings include cardinal utility vectors under a target social welfare functions and pairwise comparisons between utility vectors. Learning is taken either without noise, with iid noise, or logistic noise. The authors validate their theoretical findings by learning welfare functions on proprietary data by Lee et. al. (2018).", "questions": "NA", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Interesting novel concept and quality results. This was a pleasure to read and will be a useful contribution to the research community.", "weaknesses": "I'd be interested if you could discuss some implications or interpretations of your work. You obtain PAC bounds for the various settings and you summarize your results in Table 1. I am not immediately sure what the quality of these results are, how they compare to prior work, and how they would be represented in real-world learning.\n\nMinor: \n- Perhaps include a short primer on VC dimension, pseudo-dimension, Rademacher complexity, and PAC learning for unfamiliar audiences in the appendix\n- Perhaps cite (Xia, AAMAS 2013) and related papers on preference/rank learning (e.g., (Zhao, Liu, and Xia, IJCAI 2022) or (Newman, Royal Society 2022) or (Conitzer and Sandholm, UAI 2005) or (Xia, Conitzer, and Lang, AAMAS 2010)) as related work\n- Line 142: \"welfare\" not \"malfare\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I'd be interested if you could discuss some implications or interpretations of your work. You obtain PAC bounds for the various settings and you summarize your results in Table 1. I am not immediately sure what the quality of these results are, how they compare to prior work, and how they would be represented in real-world learning.\n\nOur PAC bounds provide theoretical guarantees on the sample complexity of learning social welfare functions, demonstrating that accurate learning is possible with a reasonable number of samples. These bounds are the first of their kind, as prior work [1] focused on more restricted classes and did not provide finite-sample guarantees. There is plethora of other work on preference learning and ranking, including the papers the reviewer suggested, but these don't focus on learning social welfare functions to the best of our knowledge. We showcase the practical feasibility of our approach on a real-world dataset of food allocation decisions [2], highlighting its potential to uncover valuable insights about decision-making priorities. Learning social welfare functions from data can significantly impact society by enabling us to understand a decision maker's priorities and notions of fairness, ultimately helping to identify biases and inform the design of improved policies. However, we recognize the crucial ethical considerations surrounding the deployment of such learning systems, particularly the risks associated with model misspecification. Our focus on the axiomatically-justified family of weighted power means mitigates these risks, but careful validation remains essential.\nWe will incorporate a more detailed discussion of these implications and expand on the connections to related work on preference learning and decision theory in the revised paper.\n\n> Perhaps include a short primer on VC dimension, pseudo-dimension, Rademacher complexity, and PAC learning for unfamiliar audiences in the appendix. \n\nWe will add a primer on key learning-theoretic concepts to the appendix, making the paper more accessible to a broader audience. \n\n> Perhaps cite (Xia, AAMAS 2013) and related papers on preference/rank learning (e.g., (Zhao, Liu, and Xia, IJCAI 2022) or (Newman, Royal Society 2022) or (Conitzer and Sandholm, UAI 2005) or (Xia, Conitzer, and Lang, AAMAS 2010)) as related work\n\nThank you for suggesting these papers, which we're familiar with; we're happy to discuss them. Here's a quick comparison:\n\n[3] provides a high-level overview of methods for designing novel social choice mechanisms. It identifies challenges and develops a three-stage workflow to combine machine learning methods and social choice axioms. While their paper provides prescriptions for learning social choice functions, they do not study the complexity of learning these functions from data. Our paper focuses on a particular class of social *welfare* functions and demonstrates polynomial sample complexity and efficient learnability in practice.\n\n[4] studies random utility models (RUMs) with 3 modifications, with a special focus on Plackett-Luce (PL) models. It presents a sufficient condition and an EM algorithm for MLE. This work concerns preference learning and models individual utilities for agents. By contrast, our work models how these individual utilities are combined to generate social welfare, and this problem has a different axiomatic basis which gives rise to a different function family. We note that preference learning and social welfare learning can be a part of the same pipeline, with the former modeling utilities and the latter using these utilities to model social welfare.\n\n[5] addresses the problem of ranking entities through pairwise comparisons, where comparisons can contradict each other. It gives an EM algorithm using a BTL model modified to capture different types of comparisons. However, this work develops a ranking for the current set of alternatives, whereas our goal is to learn the social welfare function, which can be used for completely new comparisons in the ordinal case.\n\n[6] explores which common voting rules have a noise model which makes the rule an MLE, establishing results for various popular voting rules. [7] extends this work further by considering aggregation of multi-issue voting, using CP-nets to represent how issues depend on each other. Both papers mention two perspectives for social choice: 1) agents' diverse preferences are the basis for joint decisions, 2) there are correct joint decisions with agents having different perceptions, and thus each agent has a noisy version of this correct joint decision. While both papers adopt the second perspective, our work is aligned with the first.\n\n[1] A. D. Procaccia, A. Zohar, Y. Peleg, and J. S. Rosenschein. The learnability of voting rules. Artificial Intelligence, 2009.  \n\n[2] Min Kyung Lee, et al. WeBuildAI: Participatory framework for algorithmic governance. CSCW 2019.\n\n[3] Xia, Lirong. Designing social choice mechanisms using machine learning. AAMAS 2013.\n\n[4] Zhao, Z., Liu, A., & Xia, L. Learning mixtures of random utility models with features from incomplete preferences. IJCAI 2022.\n\n[5] Newman, M. E. Ranking with multiple types of pairwise comparisons. Proceedings of the Royal Society A, 2022.\n\n[6] Conitzer, V., & Sandholm, T. Common voting rules as maximum likelihood estimators. UAI 2005.  \n\n[7] Xia, Lirong, Vincent Conitzer, and Jérôme Lang. Aggregating preferences in multi-issue domains by using maximum likelihood estimators. AAMAS 2010.", "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: The paper spots two accepts (7) and an additional positive review. 

The single borderline reject review on the paper mentions that there are writing issues, that the paper's contributions don't fit into a single ML paper, and that it should be submitted as an expanded version at a journal instead. Given that the reviewer has not provided specific/precise evidence of writing issues in the paper to the authors nor to me, that there seems to be no real issue with the content itself, and given that having more content than usual for a ML paper should really not be a reason for rejection, I do think the paper should be accepted. 

With two positive reviewers at 7 and relatively few weaknesses, I think the paper could be considered for a spotlight. I am marking my confidence as "less certain" as I believe the paper lies somewhere between accept (poster) and accept (spotlight)
Decision: Accept (spotlight)