Abstract
Problems of allocating indivisible goods to agents in an efficient and fair manner without money have long been investigated in literature. The random assignment problem is one of them, where we are given a fixed feasible (available) set of indivisible goods and a profile of ordinal preferences over the goods, one for each agent. Then, using lotteries, we determine an assignment of goods to agents in a randomized way. A seminal paper of Bogomolnaia and Moulin (2001) shows a probabilistic serial (PS) mechanism to give an ordinally efficient and envy-free solution to the assignment problem.
In this article, we consider an extension of the random assignment problem to submodular constraints on goods. We show that the approach of the PS mechanism by Bogomolnaia and Moulin is powerful enough to solve the random assignment problem with submodular (matroidal and polymatroidal) constraints. Under the agents’ ordinal preferences over goods we show the following:
(1) The obtained PS solution for the problem with unit demands and matroidal constraints is ordinally efficient, envy-free, and weakly strategy-proof with respect to the associated stochastic dominance relation.
(2)For the multiunit demand and polymatroidal constraint problem, the PS solution is ordinally efficient and envy-free but is not strategy-proof in general. However, we show that under a mild condition (that is likely to be satisfied in practice) the PS solution is a weak Nash equilibrium.
- A. Abdulkadíroǧlu and T. Sönmez. 1998. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66, 3 (May 1998), 689--701.Google ScholarCross Ref
- H. Aziz. 2015. Random assignment with multiunit demands. arXiv:1401.7700v3 {cs.GT} 19 Jun 2015.Google Scholar
- A. Bogomolnaia. 2015. Random assignment: Redefining the serial rule. J. Econ. Theor. 158, A (July 2015), 308--318.Google ScholarCross Ref
- A. Bogomolnaia and E. J. Heo. 2012. Probabilistic assignment of objects: Characterizing the serial rule. J. Econ. Theor. 147, 5 (Sept. 2012), 2072--2082.Google ScholarCross Ref
- A. Bogomolnaia and H. Moulin. 2001. A new solution to the random assignment problem. J. Econ. Theor. 100, 2 (Oct. 2001), 295--328.Google ScholarCross Ref
- E. Budish, Y.-K. Che, F. Kojima, and P. Milgrom. 2013. Designing random allocation mechanisms: Theory and applications. Am. Econ. Rev. 103, 2 (April 2013), 585--623.Google ScholarCross Ref
- J. Edmonds. 1970. Submodular functions, matroids, and certain polyhedra. In Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schönheim (Eds.). 69--87. Gordon and Breach New York, 1970.Google Scholar
- S. Fujishige. 1978. Algorithms for solving the independent-flow problems. J. Oper. Res. Soc. Japan 21, 2 (June 1978), 189--204.Google Scholar
- S. Fujishige. 1980. Lexicographically optimal base of a polymatroid with respect to a weight vector. Math. Oper. Res. 2, 2 (May 1980), 186--196. Google ScholarDigital Library
- S. Fujishige. 2005. Submodular Functions and Optimization (2nd ed.). Elsevier, Amsterdam.Google Scholar
- S. Fujishige. 2009. Theory of principal partitions revisited. In Research Trends in Combinatorial Optimization, W. Cook, L. Lovász, and J. Vygen (Eds.). 127--162. Springer: Berlin, 2009.Google ScholarCross Ref
- S. Fujishige, Y. Sano, and P. Zhan. 2016. A solution to the random assignment problem with a matroidal family of goods. Preprint, RIMS-1852, Kyoto University, May 2016.Google Scholar
- S. Fujishige, Y. Sano, and P. Zhan. 2016. An extended probabilistic serial mechanism to the random assignment problem with multi-unit demands and polymatroidal supplies. Preprint, RIMS-1866, Kyoto University, November 2016.Google Scholar
- S. Fujishige, Y. Sano, and P. Zhan. 2017. Submodular optimization views on the random assignment problem. Preprint, RIMS-1881, Kyoto University, September 2017.Google Scholar
- G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. 1989. A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18, 1 (Feb. 1989), 30--55. Google ScholarDigital Library
- M. X. Goemans, S. Gupta, and P. Jaillet. 2017. Discrete Newton’s algorithm for parametric submodular function minimization. In Proceedings of IPCO 2017, F. Eisenbrand and J. Koenemann (Eds.). IPCO 2017, LNCS 10328, 212--227.Google Scholar
- T. Hashimoto, D. Hirata, O. Kesten, M. Kurino, and M. U. Ünver. 2014. Two axiomatic approaches to the probabilistic serial mechanism. Theor. Econ. 9, 1 (Jan. 2014), 253--277.Google ScholarCross Ref
- E. J. Heo. 2014. Probabilistic assignment problem with multi-unit demands: A generalization of the serial rule and its characterization. J. Math. Econ. 54 (Oct. 2014), 40--47.Google ScholarCross Ref
- E. J. Heo and V. Manjunath. 2015. Implementation in stochastic dominance Nash equilibria. Soc. Choice Welf. 48, 1 (Jan. 2017), 5--30.Google Scholar
- A.-K. Katta and J. Sethuraman. 2006. A solution to the random assignment problem on the full preference domain. J. Econ. Theor. 131, 1 (Nov. 2006), 231--250.Google ScholarCross Ref
- F. Kojima. 2009. Random assignment of multiple indivisible objects. Math. Soc. Sci. 57, 1 (Jan. 2009), 134--142.Google ScholarCross Ref
- F. Kojima and M. Manea. 2010. Incentives in the probabilistic serial mechanism. J. Econ. Theor. 145, 1 (Jan. 2010), 106--123.Google ScholarCross Ref
- N. Megiddo. 1974. Optimal flows in networks with multiple sources and sinks. Math. Program. 7, 1 (Dec. 1974), 97--107.Google ScholarDigital Library
- K. Nagano. 2007. A strongly polynomial algorithm for line search in submodular polyhedra. Discrete Optim. 4, 3--4 (Dec. 2007), 349--359. Google ScholarDigital Library
- J. Oxley. 1992. Matroid Theory. Oxford University Press, Oxford.Google Scholar
- A. Roth and M. Sotomayor. 1990. Two Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press, Cambridge.Google Scholar
- A. Schrijver. 2003. Combinatorial Optimization—-Polyhedra and Efficiency. Springer, Berlin.Google Scholar
- L. J. Schulman and V. V. Vazirani. 2015. Allocation of divisible goods under lexicographic preferences. In Proceedings of 35th IARCS Annual Conf. Foundation of Software Technology and Theoretical Computer Sciences (FSTTCS’15), P. Harsha and G. Ramalingam (Eds.). Dagstuhl Publishing, 543--559.Google Scholar
- L. S. Shapley. 1971. Cores of convex games. Int. J. Game Theor. 1, 1 (Dec. 1971), 11--26.Google ScholarCross Ref
- D. J. A. Welsh. 1976. Matroid Theory. Academic Press, London.Google Scholar
- L. Zhou. 1990. On a conjecture by Gale about one-sided matching problems. J. Econ. Theor. 52, 1 (Oct. 1990), 123--135.Google ScholarCross Ref
Index Terms
The Random Assignment Problem with Submodular Constraints on Goods
Recommendations
Submodular optimization views on the random assignment problem
AbstractWe present a non-pricing allocation scheme of divisible goods to agents with utility functions and submodular constraints on goods. The main contribution of the present paper is that through our non-pricing allocation scheme we reveal the close ...
Polyhedral Clinching Auctions for Indivisible Goods
Web and Internet EconomicsAbstractIn this study, we propose the polyhedral clinching auction for indivisible goods, which has so far been studied for divisible goods. As in the divisible setting by Goel et al. (2015), our mechanism enjoys incentive compatibility, individual ...
Robust Auctions for Revenue via Enhanced Competition
In “Robust Auctions for Revenue via Enhanced Competition,” T. Roughgarden, I. Talgam-Cohen, and Q. Yan revisit the classic Bulow–Klemperer result. This result compares the revenues of two well-known auction formats: the welfare-maximizing Vickrey auction ...
Comments