Fairness and Efficiency in Online Class Matching

We thank the reviewer for their kind words with respect to our results and their presentation. We also appreciate the noted typos which have since been corrected.

For the noted weakness on comparisons to other price of fairness (PoF) results: the first set of results on the PoF refers back to Bertsimas et al. and Caragiannis et al. Bertsimas et al. analyze the upper bound on the utility (egalitarian social welfare) loss incurred by fairness notion such as proportional fairness and max-min fairness for divisible goods. In particular, a main takeaway of their results is that for a small number of players, PoF stays relatively small, e.g., for two players PoF for proportional fairness is at most 8.6% and 11.1% for max-min fairness. Caragiannis et al. further obtain more extensive results from a similar vein, in particular for notions of proportionality, envy-freeness, and equitability, for allocation of divisible and indivisible goods and chores. As pointed out by Bei et al., their significant limitation for indivisible setting is that their guarantee does not hold for every problem instance as the results are not satisfied as a worst-case analysis. Bei et al. tackle such limitations by investigating PoF from worst-case scenario, under various notions including Nash social welfare, envy-free up to one good, balancedness, and egalitarian social welfare. We note that all of these results do not directly apply to our setting since our notion of class envy-freeness is not equivalent to any of the properties above.

To your final question, the x_{a,o} are independent of rounding outcomes in the prior steps, hence the inequality holds for each agent being selected at least once with the given probability bound.

References:

Bertsimas et al.: The Price of Fairness, D. Bertsimas, V. Farias, N. Trichakis, OR’11

Caragiannis et al.: The Efficiency of Fair Division, I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, M. Kyropoulou, TCS’12

Bei et al.: The Price of Fairness for Indivisible Goods, X. Bei, X. Lu, P. Manurangsi, W. Suksompong, TCS’21

We thank the reviewer for their comprehensive feedback and kind words regarding the problem setting and approximate results (both upper and lower bound).

For the first noted weakness on the algorithmic contribution, we refer the reviewer to our general comments made to Reviewer gpQ6 on the approximate guarantee and nontriviality of our algorithm.

For the inquiry regarding the preferences for (1/2)-CEF and (1/2)-CPROP in expectation over (1/2)-CEF1 and (1/2)-MMS ex post, as well as the comparison between the Random algorithm and the Match-And-Shift algorithm, we emphasize that the prior work was unable to provide any approximate guarantees for the CEF objective. Moreover, (1/2)-CEF is a stronger guarantee than their (1/2)-CEF1 by definition, as it ensures a greater degree of equity between groups while maintaining the same approximate fairness factor. It is also known in the fair division literature that EF1 allocations are guaranteed to exist and are computable in polynomial time whereas EF is not guaranteed to exist. For proportionality, (1/2)-CPROP is fundamentally stronger than (1/2)-MMS. CPROP considers the maximum minimal satisfaction achievable over all possible (including divisible) matchings, whereas MMS is limited to indivisible matchings. This distinction means that CPROP offers a more robust and flexible framework for ensuring fairness.

The simplicity of the Random algorithm and its non-trivial yet strong O(1) expected guarantees makes it highly practical and promising. The inherent flexibility of randomized algorithms allows for a degree of leeway in the allocation process, accommodating minor errors or misestimations without significant degradation of the overall fairness or efficiency of the system. This flexibility as compared to deterministic algorithms is crucial in real-world applications where exact outcomes may be unpredictable or where slight deviations from the ideal are acceptable for the sake of greater overall efficiency or user satisfaction.

Furthermore, the Random algorithm is nearly optimal at the class level (see our impossibility construction), simple to implement while ensuring the above noted improved and more practical expected guarantees. This makes the Random algorithm superior in environments where conditions are dynamic or partially unknown at the time of decision-making. We believe these methods offer significant advantages for complex allocation tasks, particularly when equity and adaptability are paramount.

Lastly, we thank the reviewer for noting the potentially outdated bibtex entries. We have gone through and rectified the references which needed updates. We hope the reviewer will consider increasing their score if the above sufficiently addresses the concerns.

We appreciate the reviewer for being very responsive. We agree that ex-ante guarantee and ex-post guarantee are usually not directly comparable, however, it is explicitly mentioned as one of the main open problems in Hosseini et al. 2023:

1. Any deterministic algorithm for "divisible" items with CEF better than 1-1/e and NW
2. Any deterministic algorithm for "divisible" items with any reasonable CEF, NW, and USW better than 1/2.
3. Any randomized algorithm for "indivisible" items with any reasonable CEF, NW and USW.

In particular, their randomized algorithm (nor deterministic algo) does not have any CEF guarantee, but only has 0.593-PROP, 1/2-USW and NW. In addition, to provide such a missing hole in the randomized result (of no CEF guarantee), they further analyze another wasteful algorithm with CEF guarantee, but it is necessarily bound to be wasteful, which we believe is the reason that they pose open problem 3 explicitly. Hence, we believe our result in this context explicitly resolves open problem 3 with further guarantee on CPROP.

We hope this meets the reviewer's expectations and would appreciate your understanding as well as a possible increase in the score in par with other reviewers.

For an expansion on motivating examples of this problem setting: the study of online matching under fairness constraints is motivated by the challenges posed by the advent of Internet economics and new marketplaces, which demand solutions that are both transparent and fair, as highlighted in Moulin’s “Fair Division in the Internet Age”. These applications, where items must be matched to agents immediately and irrevocably as they arrive, include allocating advertisement slots [Mehta et al., 2007], assigning packets in switch routing [Azar and Richter, 2005], distributing food donations [Lee et al., 2019], and matching riders to drivers in ridesharing platforms [Banerjee and Johari, 2019]. Much of this work ignores the notion of fair matching. For example, a food bank that is distributing food must allocate food as it arrives due to perishability, and it’s important to ensure that these resources are sent to locations in such a manner that serves all communities equitably.

With respect to the lack of experimental validation, we emphasize that this work is intended to be largely theoretical. Capturing this problem precisely with an experimental procedure raises several design questions and would be an interesting direction of future research. Specifically, since our analysis is worst-case it would be interesting to see how our algorithm performs in practice.

We hope the reviewer will consider increasing their score if the above sufficiently addresses the concerns!

We thank the reviewer for their careful reading of our work, highlighting the novelty of our analysis and impossibility constructions, as well as constructive feedback. We also appreciate the identification of a typo which has since been rectified. We here address the noted weaknesses and related question raised.

For the open problem raised by [16] on non-wasteful randomized algorithms: it is important to highlight that the 1/2-CEF guarantee provided by our algorithm represents a significant advancement in the field, effectively resolving the open question from prior work. This result is the first of its kind to ensure a nontrivial guarantee of fairness in expectation under the stringent non-wasteful constraint. The noted nontriviality of analyzing the natural “random” algorithm to achieve this level of fairness without wasteful allocations underscores the novelty and utility of our approach. We also emphasize that the original Hosseini paper was only able to achieve an approximate 1-1/e guarantee with a randomized algorithm when allowing for wastefulness. By restricting ourselves to non-wasteful and fair allocations, our task becomes considerably more challenging. For a more extensive comparison of our result against that of [16], we refer the reviewer to our remarks to reviewer h2C8 which delineates how the fairness guarantees differ (and are improved).

Moreover, as discussed in our upper bound construction for a randomized algorithm, we highlight that an optimal algorithm must implement a randomization procedure at the class level. An algorithm that does not incorporate this can be exploited by an adversary. Thus, although our algorithm seems natural, it is strongly motivated by this consideration. The nontrivial analysis, which relies on doubling techniques to properly bound the expected guarantees, will likely be useful in all future works that analyze algorithms abiding by these constraints.

We acknowledge that surpassing the 1/2-CEF barrier remains a formidable challenge, one that we pose as an open problem to the research community. We hope that our work will inspire future research on this problem. Furthermore, we hope the reviewer will consider increasing their score if the above sufficiently addresses the concerns!