[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Fairness over time in dynamic resource allocation with an application in healthcare

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

Decision making problems are typically concerned with maximizing efficiency. In contrast, we address problems where there are multiple stakeholders and a centralized decision maker who is obliged to decide in a fair manner. Different decisions give different utility to each stakeholder. In cases where these decisions are made repeatedly, we provide efficient mathematical programming formulations to identify both the maximum fairness possible and the decisions that improve fairness over time, for reasonable metrics of fairness. We apply this framework to the problem of ambulance allocation, where decisions in consecutive rounds are constrained. With this additional complexity, we prove structural results on identifying fair feasible allocation policies and provide a hybrid algorithm with column generation and constraint programming-based solution techniques for this class of problems. Computational experiments show that our method can solve these problems orders of magnitude faster than a naive approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. The reader may have observed that an approach based on column generation would lend itself well for such a model. This is discussed in Sect. 5.

  2. Or any other equivalent solution.

  3. This is due to the fact that research projects often work with datasets associated with specific regions, each of which must follow local guidelines and regulations.

  4. In practice, the CP component of Algorithm 1 remains very fast, so this loss in efficiency is negligible.

  5. National Institute for Public Health and the Environment of the Netherlands.

  6. These instances can be found at https://github.com/PhilippeOlivier/ambulances.

  7. Constructing these sophisticated clusters is not a trivial task, which is why we settled on a random distribution of population densities for the synthetic instances. By randomizing the placement of the population for the Utrecht instance, its gap becomes similar to that of the synthetic instances.

  8. The entry “#solved” takes an integer value between 0 and 5 for synthetic instances and 0/1 for the Utrecht instance.

References

  1. Aleksandrov, M., Walsh, T.: Online fair division: a survey. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, pp. 13557–13562 (2020)

  2. AAlkan, A., Demange, G., Gale, D.: Fair allocation of indivisible goods and criteria of justice. Econom. J. Econom. Soc. 1023–1039 (1991)

  3. Balas, E., Jeroslow, R.: Canonical cuts on the unit hypercube. SIAM J. Appl. Math. 23(1), 61–69 (1972)

    Article  MathSciNet  Google Scholar 

  4. Bampis, E., Escoffier, B., Mladenovic, S.: Fair resource allocation over time. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’18, Richland, SC, pp. 766–773. International Foundation for Autonomous Agents and Multiagent Systems (2018)

  5. Brotcorne, L., Laporte, G., Semet, F.: Ambulance location and relocation models. Eur. J. Oper. Res. 147(3), 451–463 (2003). https://doi.org/10.1016/S0377-2217(02)00364-8. (ISSN 0377-2217)

    Article  MathSciNet  Google Scholar 

  6. Burt, O.R., Harris, C.C.: Letter to the editor-apportionment of the U.S. house of representatives: a minimum range, integer solution, allocation problem. Oper. Res. 11(4), 648–652 (1963). https://doi.org/10.1287/opre.11.4.648

    Article  Google Scholar 

  7. Demassey, S., Pesant, G., Rousseau, L.M.: A cost-regular based hybrid column generation approach. Constraints 11(4), 315–333 (2006). https://doi.org/10.1007/s10601-006-9003-7. (ISSN 1572-9354)

    Article  MathSciNet  Google Scholar 

  8. D’Ambrosio, C., Frangioni, A., Liberti, L., Lodi, A.: On interval-subgradient and no-good cuts. Oper. Res. Lett. 38(5), 341–345 (2010)

    Article  MathSciNet  Google Scholar 

  9. Eisenhandler, O., Tzur, M.: The humanitarian pickup and distribution problem. Oper. Res. 67(1), 10–32 (2019). https://doi.org/10.1287/opre.2018.1751

    Article  MathSciNet  Google Scholar 

  10. Gamrath, G. Anderson, D. Bestuzheva, K., Chen, W.K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Le Bodic, P., Maher, S.J., Matter, F., Miltenberger, M., Mühmer, E., Müller, B., Pfetsch, M.E., Schlösser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., Witzig, J.: The SCIP Optimization Suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin. URL http://nbn-resolving.de/urn:nbn:de:0297-zib-78023 (2020)

  11. Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Le Bodic, P., Maher, S.J., Matter, F., Miltenberger, M., Mühmer, E., Müller, Be., Pfetsch, M.E., Schlösser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., Witzig, J.: The SCIP Optimization Suite 7.0. Technical report, Optimization. URL http://www.optimization-online.org/DB_HTML/2020/03/7705.html (2020)

  12. Gendreau, M., Laporte, G., Semet, F.: A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel Comput. 27(12), 1641–1653 (2001). https://doi.org/10.1016/S0167-8191(01)00103-X. (ISSN 0167-8191)

    Article  Google Scholar 

  13. Heier Stamm, J.L., Serban, N., Swann, J., Wortley, P.: Quantifying and explaining accessibility with application to the 2009 h1n1 vaccination campaign. Health Care Manag. Sci. 20(1), 76–93 (2017). https://doi.org/10.1007/s10729-015-9338-y. (ISSN 1572-9389)

    Article  PubMed  Google Scholar 

  14. Jacobsen, S.: On marginal allocation in single constraint min-max problems. Manag. Sci. 17(11), 780–783 (1971). https://doi.org/10.1287/mnsc.17.11.780

    Article  MathSciNet  Google Scholar 

  15. Katoh, N., Ibaraki, T., Mine, H.: An algorithm for the equipollent resource allocation problem. Math. Oper. Res. 10(1), 44–53 (1985)

    Article  MathSciNet  Google Scholar 

  16. Koopman, B.O.: The optimum distribution of effort. J. Oper. Res. Soc. Am. 1(2), 52–63 (1953). https://doi.org/10.1287/opre.1.2.52

    Article  MathSciNet  Google Scholar 

  17. Luss H.: Equitable Resource Allocation: Models, Algorithms and Applications. Information and Communication Technology Series. Wiley (2012). URL https://books.google.ca/books?id=Z2_3oWjnASkC (ISBN 9781118449219)

  18. Margot, F.: Symmetry in integer linear programming. In:50 Years of Integer Programming 1958–2008, pp. 647–686. Springer (2010)

  19. Matérn, B.: Spatial variation—stochastic models and their applications to some problems in forest survey sampling investigations. Rep. For. Res. Inst. Sweden 49(5), 1–144 (1960)

    MathSciNet  Google Scholar 

  20. Ogryczak, W., Luss, H., Pióro, M., Nace, D., Tomaszewski, A.: Fair optimization and networks: a survey. J. Appl. Math. (2014). https://doi.org/10.1155/2014/612018. (ISSN 1110-757X)

    Article  MathSciNet  Google Scholar 

  21. Ogryczak, W.: Fair optimization—methodological foundations of fairness in network resource allocation. In: 2014 IEEE 38th International Computer Software and Applications Conference Workshops, pp. 43–48 (2014)

  22. Porteus, E.L., Yormark, J.S.: More on min-max allocation. Manag. Sci. 18(9), 502–507 (1972). https://doi.org/10.1287/mnsc.18.9.502

    Article  MathSciNet  Google Scholar 

  23. Procaccia, A.D.: Cake cutting algorithms. In: Handbook of computational social choice, chapter 13. Citeseer (2015)

  24. Toshihide, I., Naoki, K.: Resource Allocation Problems: Algorithmic Approaches. Foundations of Computing, p. 1. The MIT Press (1988). (ISBN 0262090279, 9780262090278)

  25. Zeitlin, Z.: Minimization of maximum absolute deviation in integers. Discrete Appl. Math. 3(3), 203–220 (1981). https://doi.org/10.1016/0166-218X(81)90017-2. (ISSN 0166-218X)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the National Institute for Public Health and the Environment of the Netherlands (RIVM) for access to the data of their ambulance service. We are grateful to the anonymous referees for useful comments and remarks.

Author information

Authors and Affiliations

  1. CERC, Polytechnique Montréal, Montreal, Canada

    Andrea Lodi & Philippe Olivier

  2. Jacobs Technion-Cornell Institute, Cornell Tech and Technion - IIT, New York, USA

    Andrea Lodi

  3. Polytechnique Montréal, Montreal, Canada

    Gilles Pesant

  4. IIM Ahmedabad, Ahmedabad, India

    Sriram Sankaranarayanan

Authors
  1. Andrea Lodi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Philippe Olivier
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Gilles Pesant
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sriram Sankaranarayanan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrea Lodi.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Appendix

A Dual of the CMP

$$\begin{aligned} \max \quad&T\mu&\end{aligned}$$
(13a)
$$\begin{aligned} \text {s.t.} \quad&\sum _{i=1}^n \alpha _i = 1&\quad (g)&\end{aligned}$$
(13b)
$$\begin{aligned}&\sum _{i=1}^n \beta _i = 1&\quad (h)&\end{aligned}$$
(13c)
$$\begin{aligned}&\lambda _i - \alpha _i + \beta _i = 0&\quad (y_i)&\quad \forall \,i = 1, \dots , n \end{aligned}$$
(13d)
$$\begin{aligned}&\mu \le \frac{1}{T}\sum _{i=1}^n {\tau }_{ij}\lambda _i&\quad (q_j)&\quad \forall \,j = 1, \dots , k \end{aligned}$$
(13e)
$$\begin{aligned}&\alpha _i,\,\beta _i \ge 0&&\quad \forall \,i = 1, \dots , n. \end{aligned}$$
(13f)

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lodi, A., Olivier, P., Pesant, G. et al. Fairness over time in dynamic resource allocation with an application in healthcare. Math. Program. 203, 285–318 (2024). https://doi.org/10.1007/s10107-022-01904-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-022-01904-6

Mathematics Subject Classification

Search

Navigation