Fairness emerges as a vital concern to decision makers as crucial as efficiency, if not more important. Fair operations decisions are aimed at distributive justice in various scenarios. In this dissertation, we study two examples of distributively fair decision making in operations research, a dynamic fair allocation problem and a subpopulational robustness assessment problem for machine learning models.
We first study a dynamic allocation problem in which π sequentially arriving divisible resources are to be allocated to a number of agents with concave utilities. The joint utility functions of each resource to the agents are drawn stochastically from a known joint distribution, independently and identically across time, and the central planner makes immediate and irrevocable allocation decisions. Most works on dynamic resource allocation aim to maximize the utilitarian welfare, i.e., the efficiency of the allocation, which may result in unfair concentration of resources on certain high-utility agents while leaving others' demands under-fulfilled. In this work, aiming at balancing efficiency and fairness, we instead consider a broad collection of welfare metrics, the HΓΆlder means, which includes the Nash social welfare and the egalitarian welfare.
To this end, we first study a fluid-based policy derived from a deterministic surrogate to the underlying problem and show that for all smooth HoΜlder mean welfare metrics it attains an π (1) regret over the time horizon length π against the hindsight optimum, i.e., the optimal welfare if all utilities were known in advance of deciding on allocations. However, when evaluated under the non-smooth egalitarian welfare, the fluid-based policy attains a regret of order π© (βπ). We then propose a new policy built thereupon, called Backward Infrequent Re-solving (π‘π¨π±), which consists of re-solving the deterministic surrogate problem at most π (log π) times. We show under a mild regularity condition that it attains a regret against the hindsight optimal egalitarian welfare of order π (1) when all agents have linear utilities and π (log π) otherwise. We further propose the Backward Infrequent Re-solving with Thresholding (π‘π¨π±π³) policy, which enhances the (π‘π¨π±π³) policy by thresholding adjustments and performs similarly without any assumption whatsoever. More specifically, we prove the (π‘π¨π±π³) policy attains an π (1) regret independently of the horizon length π when all agents have linear utilities and π (logΒ²βΊ^π) otherwise. We conclude by presenting numerical experiments to corroborate our theoretical claims and to illustrate the significant performance improvement against several benchmark policies.
The performance of ML models degrades when the training population is different from that seen under operation. Towards assessing distributional robustness, we study the worst-case performance of a model over πππ subpopulations of a given size, defined with respect to core attributes π. This notion of robustness can consider arbitrary (continuous) attributes π, and automatically accounts for complex intersectionality in disadvantaged groups. We develop a scalable yet principled two-stage estimation procedure that can evaluate the robustness of state-of-the-art models. We prove that our procedure enjoys several finite-sample convergence guarantees, including π
ππππππππ-ππππ convergence. Instead of overly conservative notions based on Rademacher complexities, our evaluation error depends on the dimension of π only through the out-of-sample error in estimating the performance conditional on π. On real datasets, we demonstrate that our method certifies the robustness of a model and prevents deployment of unreliable models.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/cmhz-z587 |
| Date | January 2024 |
| Creators | Xia, Shangzhou |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0022 seconds