Matching markets with historical data are abundant in many applications,
e.g., matching candidates to jobs in hiring, workers to tasks
in crowdsourcing markets, and jobs to servers in cloud services. In
all these applications, a match consumes one or more shared and
limited resources and the goal is to best utilize these to maximize
a global objective. Additionally, one often has historical data and
hence some statistics (usually first-order moments) of the arriving
agents (e.g., candidates, workers, and jobs) can be learnt. To model
these scenarios, we propose a unifying framework, called Multi-
Budgeted Online Assignment with Known Adversarial Distributions.
In this model,we have a set of offline servers with different deadlines
and a set of online job types. At each time, a job of type j arrives.
Assigning this job to a server i yields a profit w(i, j) while consuming
a(i,j) -- a vector lying in [0, 1]^K -- quantities of distinct resources. The goal is to design an (online) assignment policy that maximizes the total expected
profit without violating the (hard) budget constraint. We propose
and theoretically analyze two linear programming (LP) based algorithms
which are almost optimal among all LP-based approaches.
We also propose several heuristics adapted from our algorithms and
compare them to other LP-agnostic algorithms using both synthetic
as well as real-time cloud scheduling and public safety datasets.
Experimental results show that our proposed algorithms are effective
and significantly out-perform the baselines. Moreover, we
show empirically the trade-off between fairness and efficiency of
our algorithms which does well even on fairness metrics without
explicitly optimizing for it.
more »
« less
Equity Promotion in Online Resource Allocation
We consider online resource allocation under a typical non-profit setting, where limited or even scarce resources are administered by a not-for-profit organization like a government. We focus on the internal-equity by assuming that arriving requesters are homogeneous in terms of their external factors like demands but heterogeneous for their internal attributes like demographics. Specifically, we associate each arriving requester with one or several groups based on their demographics (i.e., race, gender, and age), and we aim to design an equitable distributing strategy such that every group of requesters can receive a fair share of resources proportional to a preset target ratio. We present two LP-based sampling algorithms and investigate them both theoretically (in terms of competitive-ratio analysis) and experimentally based on real COVID-19 vaccination data maintained by the Minnesota Department of Health. Both theoretical and numerical results show that our LP-based sampling strategies can effectively promote equity, especially when the arrival population is disproportionately represented, as observed in the early stage of the COVID-19 vaccine rollout.
more »
« less
- Award ID(s):
- 1948157
- NSF-PAR ID:
- 10420139
- Date Published:
- Journal Name:
- Proceedings of the AAAI Conference on Artificial Intelligence
- Volume:
- 36
- Issue:
- 9
- ISSN:
- 2159-5399
- Page Range / eLocation ID:
- 9962 to 9970
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Online matching markets (OMMs) are commonly used in todayâs world to pair agents from two parties (whom we will call offline and online agents) for mutual benefit. However, studies have shown that the algorithms making decisions in these OMMs often leave disparities in matching rates, especially for offline agents. In this article, we propose online matching algorithms that optimize for either individual or group-level fairness among offline agents in OMMs. We present two linear-programming (LP) based sampling algorithms, which achieve competitive ratios at least 0.725 for individual fairness maximization and 0.719 for group fairness maximization. We derive further bounds based on fairness parameters, demonstrating conditions under which the competitive ratio can increase to 100%. There are two key ideas helping us break the barrier of 1-1/đž~ 63.2% for competitive ratio in online matching. One is boosting , which is to adaptively re-distribute all sampling probabilities among only the available neighbors for every arriving online agent. The other is attenuation , which aims to balance the matching probabilities among offline agents with different mass allocated by the benchmark LP. We conduct extensive numerical experiments and results show that our boosted version of sampling algorithms are not only conceptually easy to implement but also highly effective in practical instances of OMMs where fairness is a concern.more » « less
-
null (Ed.)Rationale To understand novel diseases, patients may draw comparisons to other diseases. Objective We examined whether mentally associating specific diseases with COVID-19 was related to self-reported protective behaviors early in the pandemic. Methods In March 2020, a national sample of 6534 U.S. adults listed diseases that came to mind when thinking of COVID-19. They self-reported protective behaviors, demographics, and COVID-19 risk perceptions. Results Participants associated COVID-19 with common infectious diseases like seasonal influenza (59%), common cold (11%), and pneumonia (10%), or emergent infectious diseases like pandemic influenza (28%), SARS/MERS (27%), and Ebola (14%). Seasonal influenza was most commonly mentioned, in all demographic groups. Participants mentioning seasonal influenza or common cold reported fewer protective behaviors. Those mentioning pneumonia or emergent infectious diseases reported more protective behaviors. Mentioning pneumonia, SARS/MERS, and Ebola was associated with the most protective behaviors, after accounting for other generated diseases, demographics, and risk perceptions (e.g., for avoiding crowds, OR = 1.52, 95% CI = 1.26, 1.83; OR = 1.28, 95% CI = 1.13, 1.46; OR = 1.30, 95% CI = 1.11, 1.52, respectively). Conclusions Early in the pandemic, most participants mentally associated COVID-19 with seasonal flu, which may have undermined willingness to protect themselves. To motivate behavior change, COVID-19 risk communications may need to mention diseases that resonate with people while retaining accuracy.more » « less
-
more » « less
Abstract Purpose There are growing signs that the COVIDâ19 virus has started to spread to rural areas and can impact the rural health care system that is already stretched and lacks resources. To aid in the legislative decision process and proper channelizing of resources, we estimated and compared the countyâlevel change in prevalence rates of COVIDâ19 by ruralâurban status over 3 weeks. Additionally, we identified hotspots based on estimated prevalence rates.
Methods We used crowdsourced data on COVIDâ19 and linked them to countyâlevel demographics, smoking rates, and chronic diseases. We fitted a Bayesian hierarchical spatiotemporal model using the Markov Chain Monte Carlo algorithm in Râstudio. We mapped the estimated prevalence rates using ArcGIS 10.8, and identified hotspots using GettisâOrd local statistics.
Findings In the rural counties, the mean prevalence of COVIDâ19 increased from 3.6 per 100,000 population to 43.6 per 100,000 within 3 weeks from April 3 to April 22, 2020. In the urban counties, the median prevalence of COVIDâ19 increased from 10.1 per 100,000 population to 107.6 per 100,000 within the same period. The COVIDâ19 adjusted prevalence rates in rural counties were substantially elevated in counties with higher black populations, smoking rates, and obesity rates. Counties with high rates of people aged 25â49 years had increased COVIDâ19 prevalence rates.
Conclusions Our findings show a rapid spread of COVIDâ19 across urban and rural areas in 21 days. Studies based on quality data are needed to explain further the role of social determinants of health on COVIDâ19 prevalence.
-
Abstract Objective: The aim of this study was to investigate the performance of key hospital units associated with emergency care of both routine emergency and pandemic (COVID-19) patients under capacity enhancing strategies. Methods: This investigation was conducted using whole-hospital, resource-constrained, patient-based, stochastic, discrete-event, simulation models of a generic 200-bed urban U.S. tertiary hospital serving routine emergency and COVID-19 patients. Systematically designed numerical experiments were conducted to provide generalizable insights into how hospital functionality may be affected by the care of COVID-19 pandemic patients along specially designated care paths, under changing pandemic situations, from getting ready to turning all of its resources to pandemic care. Results: Several insights are presented. For example, each day of reduction in average ICU length of stay increases intensive care unit patient throughput by up to 24% for high COVID-19 daily patient arrival levels. The potential of 5 specific interventions and 2 critical shifts in care strategies to significantly increase hospital capacity is also described. Conclusions: These estimates enable hospitals to repurpose space, modify operations, implement crisis standards of care, collaborate with other health care facilities, or request external support, thereby increasing the likelihood that arriving patients will find an open staffed bed when 1 is needed.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1609/aaai.v36i9.21234
