Summary
The authors propose group-fair multi-matching algorithms in the presence of uncertainty about the valuations of agent-item pairs. The algorithms fall under two families: Conditional Value at Risk (CVaR), and robust optimization. The types of utilities they consider are also two-fold: normal utilitarian, and egalitarian group-fairness. The latter seeks to maximize the utility of the group with the minimum utility.
The authors begin with the robust optimization approach for overall utility maximization, where they derive max-min guarantees for the worst possible valuation within a particular valuation uncertainty set. Here, they propose solving a natural nested concave-convex program. Due to computational feasibility, they would like to utilize the structure of the specific problem in order to achieve a more efficient problem framing. To do this, they demonstrate that the nested program (eq 1) can be re-written as a single concave cubic program. Furthermore, the optimal assignment can be found by solving a particular system of equations with the optimal dual variables (Proposition 3.1). They also show that under some simplified assumptions on the uncertainty set containing the true valuation matrix, the optimal solution can be found by simply solving a LP or QP (Prop. 3.2, 3.3).
The authors then move to robust optimization for egalitarian welfare. Here, the problem is more complex since the objective function loses its smoothness, and is now a nested max min min optimization problem. They make a key assumption on the independence of the uncertainty set w.r.t. the data groups, which helps them swap the minimum over groups and minimum valuation over uncertainty sets. By another dual derivation, one can solve the resulting problem with iterated quadratic programming (Prop. 3.4). Furthermore, the problem has the nice property that under simplified uncertainty sets, it still reduces to solving a single LP (Prop. 3.5). The authors also note that the problem can be decomposed in the case of monotonic welfare functions.
The next topic covered is w.r.t. the CVaR approach, which assumes that the distribution over agent-item valuations is known to the mechanism designer. We begin with the optimal utilitarian assignment. Here, the optimal solution can be computed, but may be computationally infeasible for arbitrary distribution over valuation matrices $D$. Therefore, the authors adopt and approach where they sample many valuation matrices from the distribution, and solve a particular linear program which computes an empirical estimate of the \alpha-CVaR. Prior work shows that this is a consistent estimator as the number of samples goes to infinity, but they provide a concrete sample complexity bound for subgaussian distributions (Prop. 4.3), under assumption 4.2. When the distribution is normal, only the mean and covariance matter, and a particular QP can be solved (Prop. 4.4). Similar results are discussed for the group egalitarian assignment, in section 4.2.
The authors close with a series of experiments on real AAMAS reviewer bid data, where they are able to demonstrate the effectiveness and scalability of their method to a modest sample size. Here, uncertainty is defined by a model fit to predict reviewer bids on unseen examples.
Strengths
The problem considered by the authors, namely, understanding the role of uncertainty in matching algorithms, is important and well-motivated. Furthermore, their setup is extremely practical and testable. I enjoyed reading about the optimization tricks and problem specific structure used to solve each of the instances. I found the fact that the optimal assignment was given by a particular system of linear equations with the optimal dual variables very neat.
Overall, I do not think that any other work in the literature has explored and proposed feasible algorithms for matching in the presence of uncertainty in such a variety of settings (robust optimization under both utility optimal and egalitarian matchings, similarly for CVaR). I also appreciate that the code for running all programs was included. It can be quite difficult to implement programs of this complexity in practice (which a skim of the implemented gurobi programs can verify). I encourage the authors to consider cleaning up and releasing the code as a package, there is certainly a dearth of available code for efficient matching algorithms online currently!
Weaknesses
I believe that there are numerous opportunities to improve the quality of presentation in the main paper. If addressed, I plan to raise my score. Most importantly, Propositions 3.4, 3.3, 3.1 should — in my opinion — be stated informally in the main text. I don’t believe the reader will gain much by staring at the (impressive!) equations. Having the informal version retain the key takeaway — we can reduce to solving a system of equations with the optimal dual variables — would make it much easier to parse, and also emphasize the important (and cool) part of the proposition.
In lines 25-30, you specify where uncertainty may arise from. I would also consider mentioning how you capture this uncertainty: namely, by modeling uncertainty over agent-item pair valuations. These valuations completely capture the “preferences” you discuss later in the paragraph. However, when I think of matchings and preferences, concepts like stability come to mind, which is a much harder constraint to satisfy than utility maximization.
I detail more areas for improving clarity and preciseness of writing in the questions section of my response. Most are minor besides simplifying the main statement of the propositions.
If accepted, I also recommend utilizing the additional space to discuss the experiments in further detail. In particular, is table 2 reporting normalized utilities? Why are most of the results 1.0? Is this to be expected?
Questions
Q1. 113 “always the case that the constraints define a finite set such that |A| ∈ N.” Do you include the possibility that |A| = 0?
Q2. 116 “Let u : A × $\mathcal{V}$ × G → R be an affine function mapping from allocations to utilities for each group.” I don't think $\mathcal{V}$ was defined before this statement, but am assuming that it refers to the set of all valuation matrices. However, in 131, you define $\mathcal{V}$ to be the uncertainty set containing the true valuation matrix with high probability. There is probably a cleaner way to get around this without overloading, since it seems the uncertainty set definition is more important for your discussion throughout. Perhaps simply define the utility function to map from an arbitrary collection of valuations to R, instead of the set of all valuations?
Q3. 133 Not sure whether $W({u}(a))$ formally type checks properly, shouldn’t $u$ be a function of $V$ as well as the assignment $a$ (and also groups, as defined above?)
Q4. 134 $D_v$ is a distribution over valuation matrices? This seems to be defined in the next paragraph 136-145. Is it possible to switch the order of these two paragraphs?
Q5. 184 can probably do without the $\forall G \in \mathcal{G}$ in the sentence immediately following $w_G$. Also, I believe that the presentation would be enhanced by considering numbers to be not-bold (e.g. $w_G$, $u_{G_1}$, etc.), and to keep vectors bold (which the authors have already done). This would certainly help parse the notation, since there is quite a bit.
Q6. 224: valuation matrices of each group are independent of each other. What are the practical implications of this assumption? What kind of problems are we not capturing by making this assumption? This should be stated clearly, and perhaps the assumption should be stated more formally.
Q7. Equation (9), should the LHS term have an overset of $\tilde{v} \sim D_v$ for the CVaR_\alpha term? My understanding is that CVaR is w.r.t. a particular distribution $D$, not a particular draw of the random variable. Are you sweeping this into the CVaR term somehow?
Q8. 326: “Section 5.1”, should this be table 2?
Q9. How is adversarial welfare defined? The worst welfare within the uncertainty set?
Q10. I do not believe that $W_{USW}$ or $W_{GESW}$ appear in the main paper, and hence, you may be able to remove these acronyms from section 2.1. Furthermore, throughout the paper, you seem to not use the acronyms until presenting the experimental results (which makes sense).
Q11. 339: “Although the CVaR approach is less important at low noise levels, the CVaR of welfare decreases for both welfare measures as noise increases”. As someone not super familiar with CVaR, why is it less important at lower noise levels? Do we expect the noise to mainly impact the right tail or something like that?
Q12. 178-180: rounding algorithms in the case of fractional solutions. Do you think you can expand a bit on how these randomized rounding algorithms apply to your specific experiments? How much of a difference do they make? Is there a Birkhoff-von-Neumann decomposition-type result for randomized-multi-matchings which can be used to sample?
Limitations
The limitations are discussed in the main body of the paper, the most salient of which is that that CVaR requires solving a large number of linear programs to obtain the desired guarantees, and hence can be slow in practice. I don't see this as that big of a problem, however, especially since in the proposed setting of reviewer assignment, only a single matching is constructed and utilized.