skip to main content
research-article

The Random Assignment Problem with Submodular Constraints on Goods

Published:22 January 2018Publication History
Skip Abstract Section

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.

References

  1. 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 ScholarGoogle ScholarCross RefCross Ref
  2. H. Aziz. 2015. Random assignment with multiunit demands. arXiv:1401.7700v3 {cs.GT} 19 Jun 2015.Google ScholarGoogle Scholar
  3. A. Bogomolnaia. 2015. Random assignment: Redefining the serial rule. J. Econ. Theor. 158, A (July 2015), 308--318.Google ScholarGoogle ScholarCross RefCross Ref
  4. 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 ScholarGoogle ScholarCross RefCross Ref
  5. A. Bogomolnaia and H. Moulin. 2001. A new solution to the random assignment problem. J. Econ. Theor. 100, 2 (Oct. 2001), 295--328.Google ScholarGoogle ScholarCross RefCross Ref
  6. 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 ScholarGoogle ScholarCross RefCross Ref
  7. 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 ScholarGoogle Scholar
  8. S. Fujishige. 1978. Algorithms for solving the independent-flow problems. J. Oper. Res. Soc. Japan 21, 2 (June 1978), 189--204.Google ScholarGoogle Scholar
  9. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  10. S. Fujishige. 2005. Submodular Functions and Optimization (2nd ed.). Elsevier, Amsterdam.Google ScholarGoogle Scholar
  11. 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 ScholarGoogle ScholarCross RefCross Ref
  12. 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 ScholarGoogle Scholar
  13. 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 ScholarGoogle Scholar
  14. S. Fujishige, Y. Sano, and P. Zhan. 2017. Submodular optimization views on the random assignment problem. Preprint, RIMS-1881, Kyoto University, September 2017.Google ScholarGoogle Scholar
  15. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  16. 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 ScholarGoogle Scholar
  17. 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 ScholarGoogle ScholarCross RefCross Ref
  18. 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 ScholarGoogle ScholarCross RefCross Ref
  19. E. J. Heo and V. Manjunath. 2015. Implementation in stochastic dominance Nash equilibria. Soc. Choice Welf. 48, 1 (Jan. 2017), 5--30.Google ScholarGoogle Scholar
  20. 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 ScholarGoogle ScholarCross RefCross Ref
  21. F. Kojima. 2009. Random assignment of multiple indivisible objects. Math. Soc. Sci. 57, 1 (Jan. 2009), 134--142.Google ScholarGoogle ScholarCross RefCross Ref
  22. F. Kojima and M. Manea. 2010. Incentives in the probabilistic serial mechanism. J. Econ. Theor. 145, 1 (Jan. 2010), 106--123.Google ScholarGoogle ScholarCross RefCross Ref
  23. N. Megiddo. 1974. Optimal flows in networks with multiple sources and sinks. Math. Program. 7, 1 (Dec. 1974), 97--107.Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. K. Nagano. 2007. A strongly polynomial algorithm for line search in submodular polyhedra. Discrete Optim. 4, 3--4 (Dec. 2007), 349--359. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. J. Oxley. 1992. Matroid Theory. Oxford University Press, Oxford.Google ScholarGoogle Scholar
  26. A. Roth and M. Sotomayor. 1990. Two Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press, Cambridge.Google ScholarGoogle Scholar
  27. A. Schrijver. 2003. Combinatorial Optimization—-Polyhedra and Efficiency. Springer, Berlin.Google ScholarGoogle Scholar
  28. 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 ScholarGoogle Scholar
  29. L. S. Shapley. 1971. Cores of convex games. Int. J. Game Theor. 1, 1 (Dec. 1971), 11--26.Google ScholarGoogle ScholarCross RefCross Ref
  30. D. J. A. Welsh. 1976. Matroid Theory. Academic Press, London.Google ScholarGoogle Scholar
  31. L. Zhou. 1990. On a conjecture by Gale about one-sided matching problems. J. Econ. Theor. 52, 1 (Oct. 1990), 123--135.Google ScholarGoogle ScholarCross RefCross Ref

Index Terms

  1. The Random Assignment Problem with Submodular Constraints on Goods

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in

      Full Access

      • Published in

        cover image ACM Transactions on Economics and Computation
        ACM Transactions on Economics and Computation  Volume 6, Issue 1
        February 2018
        103 pages
        ISSN:2167-8375
        EISSN:2167-8383
        DOI:10.1145/3182630
        Issue’s Table of Contents

        Copyright © 2018 ACM

        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 22 January 2018
        • Accepted: 1 October 2017
        • Revised: 1 August 2017
        • Received: 1 February 2017
        Published in teac Volume 6, Issue 1

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • research-article
        • Research
        • Refereed

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader