Minimizing Symmetric Convex Functions over a Hybrid of Continuous and Discrete Convex Sets

References

• [1] Anari N, Mai T, Gharan SO, Vazirani VV (2018) Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2274–2290.Google Scholar
• [2] Babaioff M, Ezra T, Feige U (2021) Fair and truthful mechanisms for dichotomous valuations. Proc. 35th AAAI Conf. Artificial Intelligence, vol. 35 (Association for the Advancement of Artificial Intelligence, Washington, DC), 5119–5126.Google Scholar
• [3] Barman S, Krishnamurthy SK, Vaish R (2018) Greedy algorithms for maximizing Nash social welfare. Proc. 17th Internat. Conf. Autonomous Agents MultiAgent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 7–13.Google Scholar
• [4] Barman S, Krishna A, Narahari Y, Sadhukan S (2022) Achieving envy-freeness with limited subsidies under dichotomous valuations. Proc. 31st Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence, Vienna, Austria), 60–66.Google Scholar
• [5] Bei X, Li Z, Liu J, Liu S, Lu X (2021) Fair division of mixed divisible and indivisible goods. Artificial Intelligence 293(103436):1–17.Google Scholar
• [6] Benabbou N, Chakraborty M, Igarashi A, Zick Y (2021) Finding fair and efficient allocations for matroid rank valuations. ACM Trans. Econom. Comput. 9(4):21:1–21:41.Google Scholar
• [7] Bhaskar U, Sricharan A, Vaish R (2021) On approximate envy-freeness for indivisible chores and mixed resources. Approximation Randomization Combin. Optim. Algorithms Techniques (APPROX/RANDOM 2021), Leibniz International Proceedings in Informatics (LIPIcs), vol. 207 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 1:1–1:23.Google Scholar
• [8] Brustle J, Dippel J, Narayan VV, Suzuki M, Vetta A (2020) One dollar each eliminates envy. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 23–39.Google Scholar
• [9] Caragiannis I, Ioannidis SD (2022) Computing envy-freeable allocations with limited subsidies. Feldman M, Fu H, Talgam-Cohen I, eds. Web Internet Econom. WINE 2021, Lecture Notes in Computer Science, vol. 13112 (Springer, Cham, Switzerland), 522–539.Google Scholar
• [10] Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J (2019) The unreasonable fairness of maximum Nash welfare. ACM Trans. Econom. Comput. 7(3):12:1–12:32.Google Scholar
• [11] Cole R, Gkatzelis V (2015) Approximating the Nash social welfare with indivisible items. Proc. 47th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 371–380.Google Scholar
• [12] Cole R, Gkatzelis V (2018) Approximating the Nash social welfare with indivisible items. SIAM J. Comput. 47(3):1211–1236.Crossref, Google Scholar
• [13] Cole R, Devanur N, Gkatzelis V, Jain K, Mai T, Vazirani VV, Yazdanbod S (2017) Convex program duality, Fisher markets, and Nash social welfare. Proc. 18th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 459–460.Google Scholar
• [14] Darmann A, Schauer J (2015) Maximizing Nash product social welfare in allocating indivisible goods. Eur. J. Oper. Res. 247(2):548–559.Crossref, Google Scholar
• [15] Devanur NR, Papadimitriou CH, Saberi A, Vazirani VV (2008) Market equilibrium via a primal–dual algorithm for a convex program. J. ACM 55(5):22:1–22:18.Crossref, Google Scholar
• [16] Frank A, Murota K (2022a) Decreasing minimization on M-convex sets: Algorithms and applications. Math. Programming 195(1–2):1027–1068.Crossref, Google Scholar
• [17] Frank A, Murota K (2022b) Decreasing minimization on M-convex sets: Background and structures. Math. Programming 195(1–2):977–1025.Crossref, Google Scholar
• [18] Frank A, Murota K (2023) Decreasing minimization on base-polyhedra: Relation between discrete and continuous cases. Japan J. Indust. Appl. Math. 40(1):183–221.Crossref, Google Scholar
• [19] Fujishige S (1980) Lexicographically optimal base of a polymatroid with respect to a weight vector. Math. Oper. Res. 5(2):186–196.Link, Google Scholar
• [20] Fujishige S (2005) Submodular Functions and Optimization, 2nd ed. (Elsevier, Amsterdam).Google Scholar
• [21] Fujishige S (2009) Theory of principal partitions revisited. Cook W, Lovász L, Vygen J, eds. Research Trends in Combinatorial Optimization (Springer, Berlin, Heidelberg), 127–162.Crossref, Google Scholar
• [22] Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York).Google Scholar
• [23] Garg J, Hoefer M, Mehlhorn K (2018) Approximating the Nash social welfare with budget-additive valuations. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2326–2340.Google Scholar
• [24] Goko H, Igarashi A, Kawase Y, Makino K, Sumita H, Tamura A, Yokoi Y, Yokoo M (2024) A fair and truthful mechanism with limited subsidy. Games Econom. Behav. 144:49–70.Crossref, Google Scholar
• [25] Groenevelt H (1991) Two algorithms for maximizing a separable concave function over a polymatroid feasible region. Eur. J. Oper. Res. 54(2):227–236.Crossref, Google Scholar
• [26] Halpern D, Shah N (2019) Fair division with subsidy. Fotakis D, Markakis E, eds. Algorithmic Game Theory, SAGT 2019, Lecture Notes in Computer Science, vol. 11801 (Springer, Cham, Switzerland), 374–389.Google Scholar
• [27] Halpern D, Procaccia AD, Psomas A, Shah N (2020) Fair division with binary valuations: One rule to rule them all. Chen X, Gravin N, Hoefer M, Mehta R, eds. Web Internet Econom., WINE 2020, Lecture Notes in Computer Science, vol. 12495 (Springer, Cham, Switzerland), 370–383.Google Scholar
• [28] Harvey NJ, Ladner RE, Lovász L, Tamir T (2006) Semi-matchings for bipartite graphs and load balancing. J. Algorithms 59(1):53–78.Crossref, Google Scholar
• [29] Iwata S, Fleischer L, Fujishige S (2001) A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4):761–777.Crossref, Google Scholar
• [30] Kawase Y, Nishimura K, Sumita H (2024) Minimizing symmetric convex functions over hybrid of continuous and discrete convex sets. 51st Internat. Colloquium Automata Languages Programming (ICALP 2024), Leibniz International Proceedings in Informatics (LIPIcs), vol. 297 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 96:1–96:19.Google Scholar
• [31] Kawase Y, Makino K, Sumita H, Tamura A, Yokoo M (2025) Towards optimal subsidy bounds for envy-freeable allocations. Artifical Intelligence 348:104406.Crossref, Google Scholar
• [32] Lee E (2017) APX-hardness of maximizing Nash social welfare with indivisible items. Inform. Processing Lett. 122:17–20.Crossref, Google Scholar
• [33] Li Z, Liu S, Lu X, Tao B (2023) Truthful fair mechanisms for allocating mixed divisible and indivisible goods. Proc. 32nd Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence, Macao, China), 2808–2816.Google Scholar
• [34] Liu S, Lu X, Suzuki M, Walsh T (2024) Mixed fair division: A survey. Proc. 38th AAAI Conf. Artificial Intelligence, vol. 38 (Association for the Advancement of Artificial Intelligence, Washington, DC), 22641–22649.Google Scholar
• [35] Lu X, Peters J, Aziz H, Bei X, Suksompong W (2023) Approval-based voting with mixed goods. Proc. 37th AAAI Conf. Artificial Intelligence (Association for the Advancement of Artificial Intelligence, Washington, DC), 5781–5788.Google Scholar
• [36] Maruyama F (1978) A unified study on problems in information theory via polymatroids. Graduation thesis, University of Tokyo, Tokyo. [In Japanese.]Google Scholar
• [37] Moriguchi S, Hara S, Murota K (2007) On continuous/discrete hybrid M♮-convex functions. Trans. Inst. Systems Control Inform. Engrg. 20(2):84–86.Google Scholar
• [38] Murota K (1998) Discrete convex analysis. Math. Programming 83(1–3):313–371.Crossref, Google Scholar
• [39] Murota K (2003) Discrete Convex Analysis (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [40] Nagano K (2007) On convex minimization over base polytopes. Fischetti M, Williamson DP, eds. Integer Programming Combin. Optim., IPCO 2007, Lecture Notes in Computer Science, vol. 4513 (Springer, Berlin, Heidelberg), 252–266.Google Scholar
• [41] Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic Game Theory (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [42] Nishimura K, Sumita H (2025) Envy-freeness and maximum Nash welfare for mixed divisible and indivisible goods. Math. Soc. Sci. 138:102449.Crossref, Google Scholar
• [43] Orlin JB (2010) Improved algorithms for computing Fisher’s market clearing prices: Computing Fisher’s market clearing prices. Proc. 42nd ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 291–300.Google Scholar
• [44] Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80(2):346–355.Crossref, Google Scholar
• [45] Segal-Halevi E, Sziklai BR (2019) Monotonicity and competitive equilibrium in cake-cutting. Econom. Theory 68(2):363–401.Crossref, Google Scholar
• [46] Takamatsu Y, Hgara S, Murota K (2004) Continuous/discrete hybrid convex optimization and its optimality criterion (in Japanese). Trans. Inst. Systems Control Inform. Engrg. 17(9):409–411.Google Scholar
• [47] Varian HR (1974) Equity, envy and efficiency. J. Econom. Theory 9(1):63–91.Crossref, Google Scholar
• [48] Végh LA (2016) A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. SIAM J. Comput. 45(5):1729–1761.Crossref, Google Scholar