Abstract
We study markets with mixed manna, where m divisible goods and chores shall be divided among n agents to obtain a competitive equilibrium. Equilibrium allocations are known to satisfy many fairness and efficiency conditions. While a lot of recent work in fair division is restricted to linear utilities, we focus on a substantial generalization to separable piecewise-linear and concave (SPLC) utilities. We first derive polynomial-time algorithms for markets with a constant number of items or a constant number of agents. Our main result is a polynomial-time algorithm for instances with a constant number of chores (as well as any number of goods and agents) under the condition that chores dominate the utility of the agents. Interestingly, this stands in contrast to the case when the goods dominate the agents utility in equilibrium, where the problem is known to be PPAD-hard even without chores.
J. Garg and P. McGlaughlin—Supported by NSF grant CCF-1942321 (CAREER). M. Hoefer and M. Schmalhofer—Supported by DFG grant Ho 3831/5-1, 6-1 and 7-1.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
More precisely, the allocation satisfies an adaptation of proportionality up to one good (PROP1) to mixed manna.
- 2.
While we conjecture that conceptually all our ideas can be applied also when \(u_{ijk} = 0\) is allowed, the analysis of such segments generates a lot of technicalities, which we leave for future work.
- 3.
Any feasible allocation that gives all agents non-negative utility can be seen as CE. We can compute such an allocation when solving the LP (1) to determine the instance type.
- 4.
Alternatively, if the goal is to compute CEEIs for a fair division instance, we can determine the instance type in polynomial time by solving the LP (1) and then assign appropriate budgets \(e_i = 1\) or \(e_i = -1\) for all \(i \in N\).
- 5.
For consistency with previous sections, we assume that \(u_{ij} \ne 0\) throughout. Our arguments can be adapted easily by assuming that when \(u_{ij} = 0\), j is a good for i.
References
Aziz, H., Caragiannis, I., Igarashi, A., Walsh, T.: Fair allocation of indivisible goods and chores. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI) (2019)
Aziz, H., Moulin, H., Sandomirskiy, F.: A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation. Oper. Res. Lett. 48(5), 573–578 (2020)
Aziz, H., Rey, S.: Almost group envy-free allocation of indivisible goods and chores. IJCAI (2020)
Azrieli, Y., Shmaya, E.: Rental harmony with roommates. J. Econ. Theory 153, 128–137 (2014)
Barman, S., Krishnamurthy, S.K.: On the proximity of markets with integral equilibria. In: Proceedings of the 33rd Conference on Artificial Intelligence (AAAI) (2019)
Bhaskar, U., Sricharan, A., Vaish, R.: On approximate envy-freeness for indivisible chores and mixed resources (2020). arxiv:2012.06788
Bogomolnaia, A., Moulin, H., Sandomirskiy, F., Yanovskaia, E.: Competitive division of a mixed manna. Econometrica 85(6), 1847–1871 (2017)
Bogomolnaia, A., Moulin, H., Sandomirskiy, F., Yanovskaia, E.: Dividing bads under additive utilities. Soc. Choice Welf. 52(3), 395–417 (2018). https://doi.org/10.1007/s00355-018-1157-x
Brams, S.J., Taylor, A.D.: Fair Division - From Cake-Cutting to Dispute Resolution. Cambridge University Press, Cambridge (1996)
Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A. (eds.): Handbook of Computational Social Choice. Cambridge University Press, Cambridge (2016)
Branzei, S., Sandomirskiy, F.: Algorithms for competitive division of chores (2019). arXiv:1907.01766
Chaudhury, B.R., Garg, J., McGlaughlin, P., Mehta, R.: Dividing bads is harder than dividing goods: on the complexity of fair and efficient division of chores (2020). arxiv:2008.00285
Chaudhury, B.R., Garg, J., McGlaughlin, P., Mehta, R.: Competitive allocation of a mixed manna. In: Proceedings of the 31st Symposium on Discrete Algorithms (SODA) (2021)
Chen, X., Teng, S.: Spending is not easier than trading: on the computational equivalence of fisher and Arrow-Debreu equilibria. In: Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), pp. 647–656 (2009)
Devanur, N., Kannan, R.: Market equilibria in polynomial time for fixed number of goods or agents. In: Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS), pp. 45–53 (2008)
Devanur, N., Papadimitriou, C., Saberi, A., Vazirani, V.: Market equilibrium via a primal-dual algorithm for a convex program. J. ACM 55(5), 1–18 (2008)
Garg, J., McGlaughlin, P.: Computing competitive equilibria with mixed manna. In: Proceedings of the 19th Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 420–428 (2020)
Garg, J., Mehta, R., Sohoni, M., Vazirani, V.V.: A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities. SIAM J. Comput. 44(6), 1820–1847 (2015)
Garg, J., Végh, L.A.: A strongly polynomial algorithm for linear exchange markets. In: Proceedings of the 51st Symposium on Theory of Computing (STOC) (2019)
Huang, X., Lu, P.: An algorithmic framework for approximating maximin share allocation of chores (2019). arXiv:1907.04505
McGlaughlin, P., Garg, J.: Improving Nash social welfare approximations. J. Artif. Intell. Res. 68, 225–245 (2020)
Moulin, H.: Fair Division and Collective Welfare. MIT Press, Cambridge (2003)
Nisan, N., Tardos, É., Roughgarden, T., Vazirani, V. (eds.): Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
Orlin, J.: Improved algorithms for computing Fisher’s market clearing prices. In: Proceedings of the 42nd Symposium on Theory of Computing (STOC), pp. 291–300 (2010)
Robertson, J., Webb, W.: Cake-Cutting Algorithms: Be Fair If You Can. AK Peters, MA (1998)
Su, F.E.: Rental harmony: sperner’s lemma in fair division. Am. Math. Mon. 106(10), 930–942 (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Garg, J., Hoefer, M., McGlaughlin, P., Schmalhofer, M. (2021). When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores. In: Caragiannis, I., Hansen, K.A. (eds) Algorithmic Game Theory. SAGT 2021. Lecture Notes in Computer Science(), vol 12885. Springer, Cham. https://doi.org/10.1007/978-3-030-85947-3_22
Download citation
DOI: https://doi.org/10.1007/978-3-030-85947-3_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-85946-6
Online ISBN: 978-3-030-85947-3
eBook Packages: Computer ScienceComputer Science (R0)