In many kinds of games with economic significance, it is very important to study the submodularity of functions. In this paper, we mainly study the problem of maximizing a concave function over an intersection of two matroids. We obtain that the submodularity may not be preserved, but it involves one maximal submodular problem (or minimal supermodular problem) with some conditions. Moreover, we also present examples showing that these conditions can be satisfied.
Min Li, Dong-Lei Du, Da-Chuan Xu, Zhen-Ning Zhang
. A Note on Submodularity Preserved Involving the Rank Functions[J]. Journal of the Operations Research Society of China, 2019
, 7(3)
: 399
-407
.
DOI: 10.1007/s40305-019-00255-y
[1] Murota, K.:Discrete convex analysis. SIAM Monographs on Discrete Mathematics and Applications, Phil (2003)
[2] Vondrák J.:Submodularity in combinatorial optimization, PhD Thesis, Charles University (2007)
[3] He, S.M., Zhang, J.W., Zhang, S.Z.:Polymatroid optimization, submodularity, and joint replenishment games. Oper. Res. 60, 128-137(2012)
[4] Shapely, L.S.:Complements and substitutes in the optimal assignment problem. Naval Res. Logist. Q. 9, 45-48(1962)
[5] Cao, Z., Qin, C., Yang, X.:Shapleys conjecture on the cores of abstract market games. Games Econ. Behav. 108, 466-477(2018)
[6] Mass, J., Neme, A., Zhang, S.Z.:On cooperative solutions of a generalized assignment game:limit theorems to the set of competitive equilibria. J. Econ. Theory 154, 187-215(2014)
[7] Papadimitriou, C.H., Steiglltz, K.:Combinatorial optimization:Algorithms and complexity. Dover publications, Mineola, New York (1998)
[8] Vohra, R.V.:Advanced Math. Econ. Taylor & Francis e-Library, Londan, New York (2009)
