Submodularity in economics

Authors

  • Mikhail M. Kovalev Belarusian State University, 4 Niezaliezhnasci Avenue, Minsk 220030, Belarus
  • Anna A. Koroleva Belarusian State University, 4 Niezaliezhnasci Avenue, Minsk 220030, Belarus

Keywords:

submodular functions, optimisation, Monge matrix, polymatroids, submodular utilities, submodular games

Abstract

It is shown that submodularity simplifies the optimisation of economic processes. The main properties of submodular and strongly submodular functions and their connection with trends in economic processes (negative synergy and interchangeability) are established. Classes of problems in economics modeled by submodular functions are described. The contribution of submodularity to economic decision-making is demonstrated.

Author Biographies

  • Mikhail M. Kovalev, Belarusian State University, 4 Niezaliezhnasci Avenue, Minsk 220030, Belarus

    doctor of science (physics and mathema­ tics), full professor; professor at the department of analytical economics and econometrics, faculty of economics

  • Anna A. Koroleva, Belarusian State University, 4 Niezaliezhnasci Avenue, Minsk 220030, Belarus

    doctor of science (economics), docent; dean of the faculty of economics

References

  1. Rodrik D. Ekonomika reshaet: sila i slabost’ «mrachnoi nauki» [Economics rules: the rights and wrongs of the «dismal science»]. Golovlyanitsyna E, translator. Moscow: Gaidar Institute Press; 2016. 256 p. Russian.
  2. Koroleva AA. Matematicheskii instrumentarii analiza razvitiya transportnoi logistiki v Belarusi [Mathematical tools for analysing the development of transport logistics in Belarus]. Minsk: Belarusian State University; 2022. 279 p. Russian.
  3. Koroleva AA. From Monge to modern optimisation of transport flows. Journal of the Belarusian State University. Economics. 2021;1:26–36. Russian.
  4. Koroleva AA. Submodular functions in economics and logistics. Journal of the Belarusian State University. Economics. 2021; 2:18–25. Russian.
  5. Kovalev MM. Matroidy v diskretnoi optimizatsii [Matroids in discrete optimisation]. Minsk: URSS; 2020. 222 p. Russian.
  6. Demidenko VM. [Conic characterisation of Monge matrices]. Kibernetika i sistemnyi analiz. 2004;4:87–98. Russian.
  7. Grishukhin V. Ekstremal’nye luchi konusa submodulyarnoi funktsii [Extremal rays of the cone of a submodular function]. Moscow: Tsentral’nyi ekonomiko-matematicheskii institut Akademii nauk USSR; 1982. 66 p. Russian.
  8. Girlich E, Kovalev M, Moshchensky A. Convexity and Monge arrays. Magdeburg University [Preprint]; 1993. [22 p.].
  9. Girlich E, Kovalev M, Zaporozhets A. Subcones of submodular functions. Otto von Guericke Universität Magdeburg [Preprint];1994. [28 р.].
  10. Adler IJ, Hoffman A, Schamir R. Monge and feasibility sequences in general flow problems. Discrete Applied Mathematics. 1993;44:21–38. DOI: 10.1016/0166-218X(93)90220-I.
  11. Bein WW, Brucker P, Park J, Parthak P. Monge properties in higher dimensions. Discrete Applied Mathematics. 1995;58:97–109.
  12. Burkard RE, Klinz B, Rudolf R. Perspectives of Monge properties in optimisation. Discrete Applied Mathematics. 1996;70(2): 95–161. DOI: 10.1016/0166-218X(95)00103-X.
  13. Deineko V, Woeginger G. Some problems around travelling salesmen, dartboards, and eurocoins. Bulletin of the European Association for Theoretical Computer Science. 2006;90:43–52.
  14. Dietrich BL. Monge sequences, antimatroids, and the transportation problem with forbidden arcs. Linear Algebra and Its Applications. 1990;139:133–145. DOI: 10.1016/0024-3795(90)90393-Q.
  15. Shamir R. A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs. Discrete Mathematics. 1993;114:435–444. DOI: 10.1016/0012-365X(93)90382-4.
  16. Cherenin VP. Reshenie nekotorykh kombinatornykh zadach optimal’nogo planirovaniya metodom posledovatel’nykh raschetov [Solving some combinatorial problems of optimal planning by the method of successive calculations]. Novosibirsk: [s. n.]; 1962. 21 p. (Materialy k Konferentsii po opytu i perspektivam primeneniya matematicheskikh metodov i elektronnykh vychislitel’nykh mashin v planirovanii). Russian.
  17. Khachaturov VR. Algoritmy maksimizatsii supermodulyarnykh funktsii i ikh primenenie v zadachakh optimal’nogo raspredeleniya investitsii v regionakh [Algorithms for maximising supermodular functions and their application in problems of optimal investment distribution in regions] [dissertation]. Moscow: Tsentral’nyi ekonomiko-matematicheskii institut RAN; 2002. 95 p. Russian.
  18. Khachaturov VR, Veselovskii VE, Zlotov AV, Kaldybaev SU, Kaliev EZh, Kovalenko AG, et al. Kombinatornye metody i algoritmy resheniya zadach diskretnoi optimizatsii bol’shoi razmernosti [Combinatorial methods and algorithms for solving high-dimensional discrete optimisation problems]. Moscow: Nauka; 2000. 354 p. Russian.
  19. Khachaturov VR. Matematicheskie metody regional’nogo programmirovaniya [Mathematical methods of regional programming]. Moscow: Nauka; 1989. 304 p. (Ekonomiko-matematicheskaya biblioteka). Russian.
  20. Khachaturov VR. Nekotorye voprosy i prilozheniya metoda posledovatel’nykh raschetov k resheniyu zadach razmeshcheniya proizvodstva [Some questions and applications of the method of sequential calculations to solving problems of production placement] [dissertation]. Moscow: Tsentral’nyi ekonomiko-matematicheskii institut Akademii nauk SSSR; 1968. 164 p. Russian.
  21. Montlevich VM. On the submodularity of the profit function in a problem of transport planning. Bulletin of Samara State University. Natural Science Series. 2014;10:48–54. Russian.
  22. Brodetskii GL, Gusev DA. Ekonomiko-matematicheskie metody i modeli v logistike: protsedury optimizatsii [Economic and mathematical methods and models in logistics: optimisation procedures]. Moscow: Akademiya; 2012. 195 p. Russian.
  23. Trubin V. [Two classes of location determination problems in tree networks]. Kibernetika. 1983;4:84–87. Russian.
  24. Danilov VI. Lektsii po teorii igr [Lectures on the theory of games]. Moscow: New Economic School; 2002. 140 p. Russian.
  25. Edmonds J. Submodular functions, matroids and certain polyhedra. In: Guy R, Hanani H, Sauer N, Schӧnheim J, editors. Combinatorial structures and their applications. Proceedings of the Calgary international conference; 1969 June 2–14; Calgary, Canada. New York: Gordon and Breach; 1970. p. 69–87.
  26. Gospodarik CG, Kovalev MM. Collective economic security of the EAEU: statement of the problem, indicators, consolidated index. Belarusian Economic Journal. 2022;2:23–33. Russian. EDN: GLZCZD.
  27. Gospodarik CG, Kovalev MM. EAES – 2050: global’nye trendy i evraziiskaya ekonomicheskaya politika [EAEU – 2050: global trends and Eurasian economic policy]. Minsk: Publishing Centre of the Belarusian State University; 2015. 152 p. Russian.
  28. Pisaruk NN. [Representation of the lattice of optimal solutions in the submodular function minimisation problem]. Computational Mathematics and Mathematical Physics. 1989;29(9):1426–1431. Russian. DOI: 10.1016/0041-5553(89)90188-2.
  29. Fujishige S. Submodular systems and related topics. In: Korte B, Ritter K, editors. Mathematical programming at Oberwolfach II. Berlin: Springer-Verlag; 1984. p. 113–131 (Mathematical programming studies; volume 22).
  30. Lovasz L. Submodular functions and convexity. In: Bachem A, Grötschel M, Korte B, editors. Mathematical programming. The state of the art. Bonn, 1982. Berlin: Springer-Verlag; 1983. p. 235–257.
  31. Schrijver A. A combinatorial algorithm minimizing submodular function in strongly polynomial time. Journal of Combinatorial Theory. Series B. 2000;80:346–355.
  32. Topkis DM. Supermodularity and complementarity. Princeton: Princeton University Press; 1998. 272 p. (Frontiers of economic research).
  33. Danilov VI. Tselochislennaya vypuklost’ [Integer convexity]. Moscow: Tsentral’nyi ekonomiko-matematicheskii institut RAN;2020. 19 p. Russian.
  34. Topkis DM. Minimizing a submodular functions on a lattice. Operations Research. 1978;26(2):305–321. DOI: 10.1287/opre. 26.2.305.

Downloads

Additional Files

Published

2024-12-19

Issue

No. 2 (2024): Journal of the Belarusian State University. Economics

Section

C. Mathematical and Quantitative Methods

License

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)

How to Cite

[1]
Kovalev, M.M. and Koroleva, A.A. 2024. Submodularity in economics. Journal of the Belarusian State University. Economics. 2 (Dec. 2024), 4–12.