Fair and Efficient Online Allocations.

Trade-Offs in Dynamic Allocation Problems Food rescue organizations often receive donations to allocate to food pantries or families. Donations are unpredictable, and goods are often perishable; as a result, allocations have to be made within a short time frame after arrival without knowledge of future arrivals. It is important that donations go to organizations that are able to use them; at the same time, organizations that serve different communities should be treated equitably. In "Fair and Efficient Online Allocations," Benadè, Kazachkov, Procaccia, Psomas, and Zeng study fairness-efficiency trade-offs in such online allocation problems. Against adversarial arrivals, no algorithm can provide nontrivial guarantees for both these objectives simultaneously. When item values are drawn from (potentially correlated) distributions, there is no trade-off, and a simultaneously fair and efficient algorithm is presented. We study trade-offs between fairness and efficiency when allocating indivisible items online. We attempt to minimize envy, the extent to which any agent prefers another's allocation to their own, while being Pareto efficient. We provide matching lower and upper bounds against a sequence of progressively weaker adversaries. Against worst-case adversaries, we find a sharp trade-off; no allocation algorithm can simultaneously provide both nontrivial fairness and nontrivial efficiency guarantees. In a slightly weaker adversary regime where item values are drawn from (potentially correlated) distributions, it is possible to achieve the best of both worlds. We give an algorithm that is Pareto efficient ex post and either envy free up to one good or envy free with high probability. Neither guarantee can be improved, even in isolation. En route, we give a constructive proof for a structural result of independent interest. Specifically, there always exists a Pareto-efficient fractional allocation that is strongly envy free with respect to pairs of agents with substantially different utilities while allocating identical bundles to agents with identical utilities (up to multiplicative factors). Funding: A. Psomas is supported in part by the National Science Foundation [Award CCF-2144208] and Google [the AI for Social Good Award and the Research Scholar Award]. This work was partially supported by the National Science Foundation [Grants IIS-2147187, IIS-2229881, and CCF-2007080] and the Office of Naval Research [Grant N00014-20-1-2488]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.0332. [ABSTRACT FROM AUTHOR]