No-Regret Learning for Fair Multi-Agent Social Welfare Optimization

We thank the reviewer for the detailed and valuable comments to our paper. We address the reviewer's questions as follows.

Q1: However, why not consider a simple average, which is more intuitive? I recommend that the authors provide some realistic applications for NSW.

A: It is well-known that a simple average does not promote fairness. To see this, consider the following example mentioned by Hossain et al. [2021]: suppose there are 10 agents and 2 arms, where the first 4 agents receive reward 1 from arm A and reward 0 from arm B, and the other 6 agents receive reward 0 from arm A and reward 1 from arm B. If we use average as the measure, then the best policy is to always pull arm B, while if we use NSW as the measure, the distribution (0.4, 0.6) over the two arms is the best policy, which is clearly more reasonable from a fairness viewpoint.

For “some realistic applications for NSW”, we refer the reviewer to our first response to Reviewer t2CF.

Q2: For (2), why do you use $𝑁𝑆𝑊(u^\top p_t)$ rather than $\sum_{i\in[N]}p_{t,i}𝑁𝑆𝑊(𝑢_{𝑡,𝑖})$? The definition of regret seems strange.

A: This is because the former (geometric average of expected utilities) is arguably more meaningful as a fairness measure than the latter (expected geometric average of utilities). To see this, simply consider a setting with 2 agents and 2 arms, where the first agent always gets reward 1 from arm A and reward 0 from arm B, while the second agent is the opposite (reward 0 from arm A and reward 1 from arm B). Then, in terms of geometric average of expected utilities, the uniform distribution is the best policy (which makes sense from a fairness viewpoint); on the other hand, in terms of the expected geometric average of utilities, all distributions achieve the same value of 0, implying that all polices are as fair, which is clearly not what we want.

Q3: The statement in Line 165 is not correct. We don't need to observe 𝑢𝑡𝑇𝑝𝑡 when using BCO though we may need the dimension of 𝑢 to be 1, i.e. 𝑁=1. When you prove the lower bounds, I think the negative result, i.e., Thm 3.2, holds because NSW is concave but https://arxiv.org/pdf/2402.06535 needs convexity. However, in Appendix B. 1., you have convexity, so you can only construct a hard-to-learn example with at least two agents. I'm not sure whether my intuition is correct. If it is, some statement in the paper doesn't hold. If not, please explain more about the construction of your lower bounds to make it easy to understand.

A: We believe that there are some significant misunderstandings from the reviewer. First of all, when $N=1$, our problem simply reduces to the classic multi-armed bandit problem, whose minimax regret rate is well-studied, so our focus is on the case when $N\geq 2$. After all, what is the point of considering fairness when there is only one agent?

Second, you mentioned that our NSW is concave while standard BCO needs convexity, but note that our problem is about utility maximization while BCO is about loss minimization, so concavity in the former is just equivalent to convexity in the latter by simply taking negation of the objective.

Finally, your comment about Appendix B.1 also does not make sense to us. In Appendix B.1, we consider the product version of NSW used by previous works, which is neither convex nor concave.

Q4: You mention that NSW is not Lipschitz, but why not make a truncation? If an agent has a very small utility, like 𝜎 in the paper, the regret will be small. Otherwise, we can use Lipschitzness. Is there any difference between your methods? If not, show the reason why NSW doesn't make the problem harder. Also, if you have time, it's meaningful to use experiments to compare these two ideas.

A: We are not sure if we fully understand the reviewer’s idea, and will clarify based on our understanding below. If this does not address your question, please do follow up on this.

First, note that our truncation in the analysis is on the quantity $\langle p_t, u_{:,n}\rangle$ (Line 202), which is related to the unknown utility $u$ and is thus cannot be explicitly implemented in the algorithm itself.

Second, if what the reviewer meant is to truncate $\langle p_t, \hat{u}_{t,:,n}\rangle$ instead, that is, replace NSW in Algorithm 1 by

$NSW_{\sigma}(\mu)=\prod_{i=1}^N \max(\sigma, \mu)^{1/N},$

then, regardless whether the analysis works, it does not seem that the algorithm can be efficiently implemented since it is unclear how to compute $p_t$ given that $NSW_{\sigma}$ is not concave (and neither is $\log NSW_{\sigma}$).

Q5: What will happen if the learning can only observe NSW rather than everyone's utility? Will it change the dependence of $𝐾$ and $𝑁$ ?

A: As we discussed in Lines 161-171, in this case, the problem is just an instance of standard bandit convex minimization (or equivalently, bandit concave maximization). Therefore, applying the state-of-the-art algorithms from [Fokkema et al., 2024] achieves $O(K^{1.75}\sqrt{T})$ regret in the stochastic setting and $O(K^{3.5}\sqrt{T})$ in the adversarial setting (both without $N$ dependence).

Q6: In Line 324, what is $𝑓(𝑝_𝑡)$? I believe the input of $𝑓$ is an $\mathbb{R}^𝑁$ vector. However, $𝑝_𝑡$ belongs to $\mathbb{R}^𝐾$.'

A: It should be $f(u_t^\top p_t)$ instead. Thanks for pointing out the typo!

Q7: In Line 338, "is not only convex" should be "concave".

A: This is not a typo. Note that we are talking about -NSW here, which is indeed convex since NSW is concave.

Reference

[Fokkema et al., 2024] H. Fokkema, D. van der Hoeven, T. Lattimore, and J. Mayo. Online Newton method for bandit convex optimisation. In Conference on Learning Theory, 2024.

Thanks for the reviewer's detailed and valuable comments to our paper. We address the reviewer's questions as follows.

Q1: the use of the Nash Social Welfare is not motivated

A: We will add more discussion on the significance and relevance of the use of NSW in the next version as suggested. We point out that Hossain et al. [2021], the main work we improve upon, has provided very good motivation on studying NSW, and we copy one such discussion below for reference:

This problem of making a fair collective decision when the available alternatives affect multiple agents is well-studied in computational social choice. The literature offers a compelling fairness notion called the Nash social welfare, named after John Nash… Maximizing the Nash social welfare is often seen as a middle ground between maximizing the utilitarian social welfare (sum of utilities to the agents), which is unfair to minorities, and maximizing the egalitarian social welfare (minimum utility to any agent), which is considered too extreme. The solution maximizing the Nash social welfare is also known to satisfy other qualitative fairness desiderata across a wide variety of settings.

Q2: Could you please quickly comment on why the Nash Social Welfare is defined as the geometric average of the expected utility, instead of the expectation of the geometric averages of the utilities? Admittedly, the latter might be less interesting from a mathematical standpoint. Is this a choice you are making, or is it a commonly accepted definition?

A: We point out that the former (geometric average of expected utilities, which we study) is arguably more meaningful as a fairness measure than the latter (expected geometric average of utilities). To see this, simply consider a setting with 2 agents and 2 arms, where the first agent always gets reward 1 from arm A and reward 0 from arm B, while the second agent is the opposite (reward 0 from arm A and reward 1 from arm B). Then, in terms of geometric average of expected utilities, the uniform distribution is the best policy (which makes sense from a fairness viewpoint); on the other hand, in terms of the expected geometric average of utilities, all distributions achieve the same value of 0, implying that all polices are as fair, which is clearly not what we want.

Therefore, both previous works (Hossain et al. [2021] and Jones et al. [2023]) and ours study the former notion (which is in fact also mathematically more interesting as the reviewer pointed out).

Q3: Could you please detail a bit more how you obtain the third line from the second line of the computations at the end of page 14?

A: We use the fact that $a^N-b^N=(a-b)\cdot (\sum_{k=0}^{N-1} a^kb^{N-1-k})$ with $a=<p_t, \hat{u}_{t,:,n}>^{1/N}$ and $b=<p_t, u_{:,n}>^{1/N}$.

Finally, thanks for pointing out the typo on Page 4! We will fix that in the next revision.

Thanks for the reviewer's appreciation of our paper! We answer the reviewer's question as follows.

Q1: A detailed discussion on the potential applications of the model.

One important application of the model is fair repeated policy decision making. In fact, we believe that Hossain et al. [2021], the main work we improve upon, already provided very good justification for studying this model, and we copy one such discussion from their introduction below:

This problem can model situations where the principal is deliberating a policy decision and the arms correspond to the different alternatives she can implement. However, in many real-life scenarios, making a policy decision affects not one, but several agents. For example, imagine a company making a decision that affects all its employees, or a conference deciding the structure of its review process, which affects various research communities…This problem of making a fair collective decision when the available alternatives affect multiple agents is well-studied in computational social choice. The literature offers a compelling fairness notion called the Nash social welfare, named after John Nash… Maximizing the Nash social welfare is often seen as a middle ground between maximizing the utilitarian social welfare (sum of utilities to the agents), which is unfair to minorities, and maximizing the egalitarian social welfare (minimum utility to any agent), which is considered too extreme. The solution maximizing the Nash social welfare is also known to satisfy other qualitative fairness desiderata across a wide variety of settings.