IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2302.07627.html
   My bibliography  Save this paper

LP-Duality Theory and the Cores of Games

Author

Listed:
  • Vijay V. Vazirani

Abstract

LP-duality theory has played a central role in the study of the core, right from its early days to the present time. However, despite the extensive nature of this work, basic gaps still remain. We address these gaps using the following building blocks from LP-duality theory: 1. Total unimodularity (TUM). 2. Complementary slackness conditions and strict complementarity. Our exploration of TUM leads to defining new games, characterizing their cores and giving novel ways of using core imputations to enforce constraints that arise naturally in applications of these games. The latter include: 1. Efficient algorithms for finding min-max fair, max-min fair and equitable core imputations. 2. Encouraging diversity and avoiding over-representation in a generalization of the assignment game. Complementarity enables us to prove new properties of core imputations of the assignment game and its generalizations.

Suggested Citation

  • Vijay V. Vazirani, 2023. "LP-Duality Theory and the Cores of Games," Papers 2302.07627, arXiv.org, revised Mar 2023.
    • Handle: RePEc:arx:papers:2302.07627
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2302.07627
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Johan Karlander & Kimmo Eriksson, 2001. "Stable outcomes of the roommate game with transferable utility," International Journal of Game Theory, Springer;Game Theory Society, vol. 29(4), pages 555-569.
    2. Tamás Király & Júlia Pap, 2008. "Total Dual Integrality of Rothblum's Description of the Stable-Marriage Polyhedron," Mathematics of Operations Research, INFORMS, vol. 33(2), pages 283-290, May.
    3. Xiaotie Deng & Qizhi Fang & Xiaoxun Sun, 2009. "Finding nucleolus of flow game," Journal of Combinatorial Optimization, Springer, vol. 18(1), pages 64-86, July.
    4. Christopher P. Chambers & Federico Echenique, 2015. "The Core Matchings of Markets with Transfers," American Economic Journal: Microeconomics, American Economic Association, vol. 7(1), pages 144-164, February.
    5. Núñez, Marina & Rafels, Carles, 2008. "On the dimension of the core of the assignment game," Games and Economic Behavior, Elsevier, vol. 64(1), pages 290-302, September.
    6. Ehud Kalai & Eitan Zemel, 1982. "Totally Balanced Games and Games of Flow," Mathematics of Operations Research, INFORMS, vol. 7(3), pages 476-478, August.
    7. M. L. Balinski, 1965. "Integer Programming: Methods, Uses, Computations," Management Science, INFORMS, vol. 12(3), pages 253-313, November.
    8. Potters, Jos & Reijnierse, Hans & Biswas, Amit, 2006. "The nucleolus of balanced simple flow networks," Games and Economic Behavior, Elsevier, vol. 54(1), pages 205-225, January.
    9. Péter Biró & Walter Kern & Daniël Paulusma, 2012. "Computing solutions for matching games," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(1), pages 75-90, February.
    10. Chung-Piaw Teo & Jay Sethuraman, 1998. "The Geometry of Fractional Stable Matchings and Its Applications," Mathematics of Operations Research, INFORMS, vol. 23(4), pages 874-891, November.
    11. Vijay V. Vazirani, 2023. "The Investment Management Game: Extending the Scope of the Notion of Core," Papers 2302.00608, arXiv.org, revised Sep 2023.
    12. Walter Kern & Daniël Paulusma, 2009. "On the Core and f -Nucleolus of Flow Games," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 981-991, November.
    13. Vazirani, Vijay V., 2022. "The general graph matching game: Approximate core," Games and Economic Behavior, Elsevier, vol. 132(C), pages 478-486.
    14. Hiroshi Nagamochi & Dao-Zhi Zeng & Naohiśa Kabutoya & Toshihide Ibaraki, 1997. "Complexity of the Minimum Base Game on Matroids," Mathematics of Operations Research, INFORMS, vol. 22(1), pages 146-164, February.
    15. Shanfeng Zhu & Xiaotie Deng & Maocheng Cai & Qizhi Fang, 2002. "On computational complexity of membership test in flow games and linear production games," International Journal of Game Theory, Springer;Game Theory Society, vol. 31(1), pages 39-45.
    16. M. Maschler & B. Peleg & L. S. Shapley, 1979. "Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 303-338, November.
    Full references (including those not matched with items on IDEAS)

    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. Vijay V. Vazirani, 2022. "New Characterizations of Core Imputations of Matching and $b$-Matching Games," Papers 2202.00619, arXiv.org, revised Dec 2022.
    2. Vijay V. Vazirani, 2022. "Cores of Games via Total Dual Integrality, with Applications to Perfect Graphs and Polymatroids," Papers 2209.04903, arXiv.org, revised Nov 2022.
    3. Qizhi Fang & Bo Li & Xiaohan Shan & Xiaoming Sun, 2018. "Path cooperative games," Journal of Combinatorial Optimization, Springer, vol. 36(1), pages 211-229, July.
    4. Walter Kern & Daniël Paulusma, 2009. "On the Core and f -Nucleolus of Flow Games," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 981-991, November.
    5. Márton Benedek & Jörg Fliege & Tri-Dung Nguyen, 2020. "Finding and verifying the nucleolus of cooperative games," CERS-IE WORKING PAPERS 2021, Institute of Economics, Centre for Economic and Regional Studies.
    6. Nguyen, Tri-Dung & Thomas, Lyn, 2016. "Finding the nucleoli of large cooperative games," European Journal of Operational Research, Elsevier, vol. 248(3), pages 1078-1092.
    7. Vazirani, Vijay V., 2022. "The general graph matching game: Approximate core," Games and Economic Behavior, Elsevier, vol. 132(C), pages 478-486.
    8. Tianhang Lu & Han Xian & Qizhi Fang, 2023. "Approximate Core Allocations for Edge Cover Games," Papers 2308.11222, arXiv.org.
    9. Péter Biró & Walter Kern & Daniël Paulusma, 2012. "Computing solutions for matching games," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(1), pages 75-90, February.
    10. Vijay V. Vazirani, 2023. "The Investment Management Game: Extending the Scope of the Notion of Core," Papers 2302.00608, arXiv.org, revised Sep 2023.
    11. Vijay V. Vazirani, 2021. "The General Graph Matching Game: Approximate Core," Papers 2101.07390, arXiv.org, revised Jul 2021.
    12. Vijay V. Vazirani, 2024. "Equitable Core Imputations via a New Adaptation of The Primal-Dual Framework," Papers 2402.11437, arXiv.org, revised Dec 2024.
    13. Federico Echenique & SangMok Lee & Matthew Shum & M. Bumin Yenmez, 2021. "Stability and Median Rationalizability for Aggregate Matchings," Games, MDPI, vol. 12(2), pages 1-15, April.
    14. Xiaotie Deng & Toshihide Ibaraki & Hiroshi Nagamochi, 1999. "Algorithmic Aspects of the Core of Combinatorial Optimization Games," Mathematics of Operations Research, INFORMS, vol. 24(3), pages 751-766, August.
    15. Michel Le Breton & Juan Moreno-Ternero & Alexei Savvateev & Shlomo Weber, 2013. "Stability and fairness in models with a multiple membership," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(3), pages 673-694, August.
    16. Potters, Jos & Reijnierse, Hans & Biswas, Amit, 2006. "The nucleolus of balanced simple flow networks," Games and Economic Behavior, Elsevier, vol. 54(1), pages 205-225, January.
    17. Daniel Granot & Jeroen Kuipers & Sunil Chopra, 2002. "Cost Allocation for a Tree Network with Heterogeneous Customers," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 647-661, November.
    18. Núñez, Marina & Rafels, Carles, 2009. "A glove-market partitioned matrix related to the assignment game," Games and Economic Behavior, Elsevier, vol. 67(2), pages 598-610, November.
    19. Andreas S. Schulz & Nelson A. Uhan, 2010. "Sharing Supermodular Costs," Operations Research, INFORMS, vol. 58(4-part-2), pages 1051-1056, August.
    20. Biró, Péter & Kern, Walter & Paulusma, Daniël & Wojuteczky, Péter, 2018. "The stable fixtures problem with payments," Games and Economic Behavior, Elsevier, vol. 108(C), pages 245-268.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:arx:papers:2302.07627. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.