Learning Social Welfare Functions

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).

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. Minor: - Perhaps include a short primer on VC dimension, pseudo-dimension, Rademacher complexity, and PAC learning for unfamiliar audiences in the appendix - 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 - Line 142: "welfare" not "malfare"

Questions

NA

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

Yes

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.

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]). The 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. This 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. As 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.

Questions

N/A

Rating

4

Confidence

1

Soundness

3

Presentation

2

Contribution

2

Limitations

Some discussion has been included but it is somewhat limited and surface level.

Summary

This work studies learning the social welfare function from a power mean function class. - 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. - 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. - Finally, they conduct experiments to justify their results.

Strengths

This work studies a new problem of learning social welfare function. The writing is very clear. They 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. 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. 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?

Questions

see weaknesses.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

NA

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

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.

Questions

1. How should I understand the "pseudo-dimensions" of $M_{w, d}$ and $M_d$ in line 161? 2. 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?

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

See above.