Abstract
We consider the problem of allocating indivisible goods using the leading notion of fairness in economics: the competitive equilibrium from equal incomes. Focusing on two major classes of valuations, namely perfect substitutes and perfect complements, we establish the computational properties of algorithms operating in this framework. For the class of valuations with perfect complements, our algorithm yields a surprisingly succinct characterization of instances that admit a competitive equilibrium from equal incomes.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Given a set of students and courses to be offered at a university, how should the courses be scheduled given that the students have preferences over their schedules and the courses have capacity constraints on enrollment?
References
Arrow, K.J., Debreu, G.: Existence of an equilibrium for a competitive economy. Econometrica 22(3), 265–290 (1954)
Aziz, H.: Competitive equilibrium with equal incomes for allocation of indivisible objects (2015). http://arxiv.org/pdf/1501.06627v1.pdf
Bouveret, S., Lemaître, M.: Characterizing conflicts in fair division of indivisible goods using a scale of criteria. In: AAMAS, pp. 1321–1328 (2014)
Brainard, W., Scarf, H.E.: How to compute equilibrium prices in 1891. Cowles Foundation Discussion Paper (2000)
Budish, E.: The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J. Polit. Econ. 119(6), 1061–1103 (2011)
Deng, X., Papadimitriou, C., Safra, S.: On the complexity of price equilibria. J. Comput. Syst. Sci. 67(2), 311–324 (2003)
Eisenberg, E., Gale, D.: Consensus of subjective probabilities: the pari-mutuel method. Ann. Math. Stat. 30, 165–168 (1959)
Foley, D.K.: Resource allocation and the public sector. Yale Econ. Essays 7(1), 45–98 (1967)
Hylland, A., Zeckhauser, R.: The efficient allocation of individuals to positions. J. Polit. Econ. 87(2), 293–314 (1979)
Moulin, H.: Fair division and collective welfare. MIT press, Cambridge (2004)
Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
Othman, A., Papadimitriou, C.H., Rubinstein, A.: The complexity of fairness through equilibrium. In: Proceedings of ACM-EC, pp. 209–226 (2014)
Thomson, W., Varian, H.: Theories of justice based on symmetry. In: Hurwicz, L., Schmeidler, D. (eds.) Essays in Memory of Elisha Pazner. Social Goals and Social Organizations. Cambridge University Press, Cambridge (1985)
Varian, H.: Equity, envy, and efficiency. JET 9(1), 63–91 (1974)
Walras, L.: Elements d’economie politique pure, ou theorie de la richesse sociale (in French) (1874)
Acknowledgements
We would like to thank the anonymous reviewers for useful feedback that helped improve the paper. Simina Brânzei and Peter Bro Miltersen acknowledge support from the Danish National Research Foundation and The National Science Foundation of China (under the grant 61361136003) for the Sino-Danish Center for the Theory of Interactive Computation, and the Center for Research in Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brânzei, S., Hosseini, H., Miltersen, P.B. (2015). Characterization and Computation of Equilibria for Indivisible Goods. In: Hoefer, M. (eds) Algorithmic Game Theory. SAGT 2015. Lecture Notes in Computer Science(), vol 9347. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48433-3_19
Download citation
DOI: https://doi.org/10.1007/978-3-662-48433-3_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48432-6
Online ISBN: 978-3-662-48433-3
eBook Packages: Computer ScienceComputer Science (R0)