Summary
This paper studies an online allocation problem with long-term fairness constraints where, unlike prior works, the protected attributes of online users (e.g., gender, ethnicity) are not observed, but they can be purchased from $K$ different sources for some additional cost. The goal is to maximize the overall utility of the users minus the cost of additional information that was bought minus a fairness penalty that is characterized by a convex function $R(\cdot)$. The authors study this problem under an i.i.d. assumption on the users and propose Algorithm 1 with sublinear regret for the problem.
Strengths
- Addressing fairness constraints in online allocation is a very well-motivated problem and the authors' assumption that protected attributes are not observed is a more realistic model of the applications. Therefore, the contributions of this work are of potential interest to a wide audience.
- Simultaneous source selection and dual gradient descent in Algorithm 1 is an important contribution that shows the naive approach of performing these two tasks separately is not good enough for this problem.
- The proposed algorithm is compatible with various notions of group fairness.
Weaknesses
- The problem setup is a bit confusing. I'm not sure how the public context $z_t$, protected attributes $a_t$, and the purchased piece of information $c_{tk_t}$ are related to each other. On line 152, the authors make the assumption that $c_{tk_t}$ contains $z_t$ and I'm not quite sure if I understand what that means.
- The authors have distinguished their paper from prior works based on the fact that protected attributes are not observed and could only be purchased. However, a comparison of the paper with prior works in terms of techniques and proof ideas is missing. It appears that both primal and dual updates in Algorithm 1 are quite standard and the main challenge is to combine these two steps. This point needs to be highlighted and clarified.
- Given the vagueness of the problem framework, explaining the setting in the context of a few motivating applications is very helpful. In particular, the process of purchasing data from data sources needs clarification.
Questions
- Can you provide a few motivating applications that could be cast into your framework and explain what data sources are and how they relate to each other?
- Can you explain the connection between $a_t$, $z_t$, and $c_{tk_t}$ in the context of a motivating application? How do these quantities relate to each other? What is the dimension of each quantity? How is $\mathbb{E}[a_t|c_{tk_t}]$ estimated?
- Assuming that $\sum_{t}x_t>0$, the function $(\sum_t x_t)R(\frac{\sum_t a_tx_t}{\sum_t x_t})$ is simply the perspective of the convex function $R(\cdot)$ and therefore, it should be convex in $x=(x_1,\dots,x_T)$. However, on lines 329-330, it is claimed that the opposite is true. Can you explain why convexity doesn't hold?
- Is it possible to use Algorithm 1 to obtain results for the adversarial setting? What would be the main challenges?
- On line 131, why is $c_{tk}$ enough to estimate $u_t$ and $a_t$? How about the public context information $z_t$, is it not helpful for estimation?
--------------------------------
I've read the authors' rebuttal, thanks for addressing my questions and concerns.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
Discussion of potential negative societal impact is not necessary.