IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v110y2001i2d10.1023_a1017587615488.html
   My bibliography  Save this article

An Intersection Theorem on an Unbounded Set and Its Application to the Fair Allocation Problem

Author

Listed:
  • Z. Yang

Abstract

We prove the following theorem. Let m and n be any positive integers with m≤n, and let $$T^n = \{ x \in \mathbb{R}^n |\Sigma _{i = 1}^n x_i = 1\}$$ be a subset of the n-dimensional Euclidean space ℝ n . For each i=1, . . . , m, there is a class $$\{ M_i^j {\text{| }}j = 1,...,n\}$$ of subsets M i j of Tn . Assume that $$\cup _{j = 1}^n M_i^j = T^n ,$$ for each i=1, . . . , m, that M i j is nonempty and closed for all i, j, and that there exists a real number B(i, j) such that $$x \in T^n$$ and its jth component xj≤B(i, j) imply $$x\not \in M_i^j$$ . Then, there exists a partition $$(\Pi (1),...,\Pi (m))$$ of {1, . . . , n} such that $$\Pi (i) \ne \emptyset$$ for all i and $$\cap _{i = 1}^m \cap _{j \in \Pi (i)} M_i^j \ne \emptyset .$$ We prove this theorem based upon a generalization of a well-known theorem of Birkhoff and von Neumann. Moreover, we apply this theorem to the fair allocation problem of indivisible objects with money and obtain an existence theorem.

Suggested Citation

  • Z. Yang, 2001. "An Intersection Theorem on an Unbounded Set and Its Application to the Fair Allocation Problem," Journal of Optimization Theory and Applications, Springer, vol. 110(2), pages 429-443, August.
  • Handle: RePEc:spr:joptap:v:110:y:2001:i:2:d:10.1023_a:1017587615488
    DOI: 10.1023/A:1017587615488
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1017587615488
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1023/A:1017587615488?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Talman, A.J.J., 1991. "Intersection theorems on the unit simplex and the simplotope," Other publications TiSEM 3d9e52e1-2498-49ac-928b-2, Tilburg University, School of Economics and Management.
    2. Svensson, Lars-Gunnar, 1983. "Large Indivisibles: An Analysis with Respect to Price Equilibrium and Fairness," Econometrica, Econometric Society, vol. 51(4), pages 939-954, July.
    3. van der Laan, Gerard & Talman, Dolf & Yang, Zaifu, 1997. "Existence of an equilibrium in a competitive economy with indivisibilities and money," Journal of Mathematical Economics, Elsevier, vol. 28(1), pages 101-109, August.
    4. P. J. J. Herings & A. J. J. Talman, 1998. "Intersection Theorems with a Continuum of Intersection Points," Journal of Optimization Theory and Applications, Springer, vol. 96(2), pages 311-335, February.
    5. Yang, Z.F., 1996. "Simplicial fixed point algorithms and applications," Other publications TiSEM 60fbb5f7-785c-4c91-8b84-5, Tilburg University, School of Economics and Management.
    6. Svensson, Lars-Gunnar, 1987. "Erratum [Large Indivisibles: An Analysis with Respect to Price Equilibrium and Fairness]," Econometrica, Econometric Society, vol. 55(2), pages 489-489, March.
    7. Zhou Lin, 1994. "A New Bargaining Set of an N-Person Game and Endogenous Coalition Formation," Games and Economic Behavior, Elsevier, vol. 6(3), pages 512-526, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. P. J. J. Herings & G. A. Koshevoy & A. J. J. Talman & Z. Yang, 2004. "General Existence Theorem of Zero Points," Journal of Optimization Theory and Applications, Springer, vol. 120(2), pages 375-394, February.
    2. Talman, A.J.J. & Yang, Z.F., 2004. "The Computation of a Coincidence of Two Mappings," Other publications TiSEM 9fbcc219-da4d-4564-b4e3-6, Tilburg University, School of Economics and Management.
    3. Ning Sun & Zaifu Yang, 2009. "Strategy Proof And Privacy Preserving Fair Allocation Mechanism," The Japanese Economic Review, Japanese Economic Association, vol. 60(2), pages 143-151, June.
    4. Sun, Ning & Yang, Zaifu, 2003. "A general strategy proof fair allocation mechanism," Economics Letters, Elsevier, vol. 81(1), pages 73-79, October.
    5. Talman, A.J.J. & Yang, Z.F., 2009. "A constructive proof of Ky Fan's coincidence theorem," Other publications TiSEM 9f92e51a-4229-4bbe-9a75-5, Tilburg University, School of Economics and Management.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Z. F. Yang, 2000. "Multipermutation-Based Intersection Theorem and Its Applications," Journal of Optimization Theory and Applications, Springer, vol. 104(2), pages 477-487, February.
    2. Echenique, Federico & Goel, Sumit & Lee, SangMok, 2024. "Stable allocations in discrete exchange economies," Journal of Economic Theory, Elsevier, vol. 222(C).
    3. Azrieli, Yaron & Shmaya, Eran, 2014. "Rental harmony with roommates," Journal of Economic Theory, Elsevier, vol. 153(C), pages 128-137.
    4. Sprumont, Yves, 2013. "Constrained-optimal strategy-proof assignment: Beyond the Groves mechanisms," Journal of Economic Theory, Elsevier, vol. 148(3), pages 1102-1121.
    5. Shinji Ohseto, 2006. "Characterizations of strategy-proof and fair mechanisms for allocating indivisible goods," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 29(1), pages 111-121, September.
    6. , & ,, 2015. "Strategy-proofness and efficiency with non-quasi-linear preferences: a characterization of minimum price Walrasian rule," Theoretical Economics, Econometric Society, vol. 10(2), May.
    7. William Thomson, 2011. "Consistency and its converse: an introduction," Review of Economic Design, Springer;Society for Economic Design, vol. 15(4), pages 257-291, December.
    8. Youngsub Chun & Manipushpak Mitra & Suresh Mutuswami, 2014. "Egalitarian equivalence and strategyproofness in the queueing problem," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 56(2), pages 425-442, June.
    9. Meertens, Marc & Potters, Jos & Reijnierse, Hans, 2002. "Envy-free and Pareto efficient allocations in economies with indivisible goods and money," Mathematical Social Sciences, Elsevier, vol. 44(3), pages 223-233, December.
    10. Tommy ANDERSSON & Lars EHLERS & Lars-Gunnar SVENSSON, 2014. "Transferring Ownership of Public Housing to Existing Tenants : A Mechanism Design Approach," Cahiers de recherche 09-2014, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    11. Youngsub Chun & Boram Park, 2017. "A graph theoretic approach to the slot allocation problem," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(1), pages 133-152, January.
    12. Talman, Dolf & Yang, Zaifu, 2011. "A model of partnership formation," Journal of Mathematical Economics, Elsevier, vol. 47(2), pages 206-212, March.
    13. Rodrigo A. Velez, 2022. "A polynomial algorithm for maxmin and minmax envy-free rent division on a soft budget," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 59(1), pages 93-118, July.
    14. Marc Fleurbaey, 2006. "To Envy or to be Envied? Refinements of No-Envy fot the Compensation Problem," IDEP Working Papers 0603, Institut d'economie publique (IDEP), Marseille, France, revised Jul 2006.
    15. Andersson, Tommy & Andersson, Christer & Talman, Adolphus Johannes Jan, 2010. "Sets in Excess Demand in Ascending Auctions with Unit-Demand Bidders," Working Papers 2010:15, Lund University, Department of Economics, revised 28 Jun 2012.
    16. T. Andersson & C. Andersson & A. Talman, 2013. "Sets in excess demand in simple ascending auctions with unit-demand bidders," Annals of Operations Research, Springer, vol. 211(1), pages 27-36, December.
    17. Tommy Andersson & Lars Ehlers & Lars-Gunnar Svensson & Ryan Tierney, 2022. "Gale’s Fixed Tax for Exchanging Houses," Mathematics of Operations Research, INFORMS, vol. 47(4), pages 3110-3128, November.
    18. BOSSERT, Walter & WEYMARK, J.A., 2006. "Social Choice: Recent Developments," Cahiers de recherche 01-2006, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    19. Hahn, Kyungdong & Gilles, Robert P., 1998. "Efficient egalitarian-equivalence and the core of an economy with public projects," Economics Letters, Elsevier, vol. 60(2), pages 173-178, August.
    20. Velez, Rodrigo A. & Thomson, William, 2012. "Let them cheat!," Games and Economic Behavior, Elsevier, vol. 75(2), pages 948-963.

    More about this item

    Keywords

    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:110:y:2001:i:2:d:10.1023_a:1017587615488. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.