IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v132y2022icp478-486.html
   My bibliography  Save this article

The general graph matching game: Approximate core

Author

Listed:
  • Vazirani, Vijay V.

Abstract

The classic paper of Shapley and Shubik (1971) characterized the core of the assignment game using ideas from matching theory and LP-duality theory and their highly non-trivial interplay. Whereas the core of this game is always non-empty, that of the general graph matching game can be empty.

Suggested Citation

  • Vazirani, Vijay V., 2022. "The general graph matching game: Approximate core," Games and Economic Behavior, Elsevier, vol. 132(C), pages 478-486.
    • Handle: RePEc:eee:gamebe:v:132:y:2022:i:c:p:478-486
    DOI: 10.1016/j.geb.2022.01.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825622000239
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2022.01.017?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 search for a different version of it.

    References listed on IDEAS

    as
    1. M. L. Balinski, 1965. "Integer Programming: Methods, Uses, Computations," Management Science, INFORMS, vol. 12(3), pages 253-313, November.
    2. Rodica Brânzei & Tamás Solymosi & Stef Tijs, 2005. "Strongly essential coalitions and the nucleolus of peer group games," International Journal of Game Theory, Springer;Game Theory Society, vol. 33(3), pages 447-460, September.
    3. 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.
    4. 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.
    5. SCHMEIDLER, David, 1969. "The nucleolus of a characteristic function game," LIDAM Reprints CORE 44, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Solymosi, Tamas & Raghavan, Tirukkannamangai E S, 1994. "An Algorithm for Finding the Nucleolus of Asignment Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 23(2), pages 119-143.
    7. Aumann, Robert J. & Maschler, Michael, 1985. "Game theoretic analysis of a bankruptcy problem from the Talmud," Journal of Economic Theory, Elsevier, vol. 36(2), pages 195-213, August.
    8. Walter Kern & Daniël Paulusma, 2003. "Matching Games: The Least Core and the Nucleolus," Mathematics of Operations Research, INFORMS, vol. 28(2), pages 294-308, May.
    9. 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)

    Citations

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


    Cited by:

    1. 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.
    2. Tianhang Lu & Han Xian & Qizhi Fang, 2023. "Approximate Core Allocations for Edge Cover Games," Papers 2308.11222, arXiv.org.
    3. Vijay V. Vazirani, 2022. "New Characterizations of Core Imputations of Matching and $b$-Matching Games," Papers 2202.00619, arXiv.org, revised Dec 2022.
    4. Vijay V. Vazirani, 2023. "LP-Duality Theory and the Cores of Games," Papers 2302.07627, arXiv.org, revised Mar 2023.

    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. 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.
    3. Tamas Solymosi & Balazs Sziklai, 2015. "Universal Characterization Sets for the Nucleolus in Balanced Games," CERS-IE WORKING PAPERS 1512, Institute of Economics, Centre for Economic and Regional Studies.
    4. Xiaotie Deng & Qizhi Fang & Xiaoxun Sun, 2009. "Finding nucleolus of flow game," Journal of Combinatorial Optimization, Springer, vol. 18(1), pages 64-86, July.
    5. 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.
    6. Tamás Solymosi, 2019. "Weighted nucleoli and dually essential coalitions (extended version)," CERS-IE WORKING PAPERS 1914, Institute of Economics, Centre for Economic and Regional Studies.
    7. Tamás Solymosi, 2019. "Weighted nucleoli and dually essential coalitions," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(4), pages 1087-1109, December.
    8. Heinrich Nax & Bary Pradelski, 2015. "Evolutionary dynamics and equitable core selection in assignment games," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(4), pages 903-932, November.
    9. F.Javier Martínez-de-Albéniz & Carles Rafels & Neus Ybern, 2015. "Insights into the nucleolus of the assignment game," UB School of Economics Working Papers 2015/333, University of Barcelona School of Economics.
    10. repec:has:discpr:1321 is not listed on IDEAS
    11. Walter Kern & Daniël Paulusma, 2003. "Matching Games: The Least Core and the Nucleolus," Mathematics of Operations Research, INFORMS, vol. 28(2), pages 294-308, May.
    12. Qizhi Fang & Bo Li & Xiaohan Shan & Xiaoming Sun, 2018. "Path cooperative games," Journal of Combinatorial Optimization, Springer, vol. 36(1), pages 211-229, July.
    13. 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.
    14. Vijay V. Vazirani, 2023. "LP-Duality Theory and the Cores of Games," Papers 2302.07627, arXiv.org, revised Mar 2023.
    15. Han Xiao & Tianhang Lu & Qizhi Fang, 2021. "Approximate Core Allocations for Multiple Partners Matching Games," Papers 2107.01442, arXiv.org, revised Oct 2021.
    16. Han Xiao & Qizhi Fang, 2022. "Population monotonicity in matching games," Journal of Combinatorial Optimization, Springer, vol. 43(4), pages 699-709, May.
    17. Frits Hof & Walter Kern & Sascha Kurz & Kanstantsin Pashkovich & Daniël Paulusma, 2020. "Simple games versus weighted voting games: bounding the critical threshold value," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(4), pages 609-621, April.
    18. Samuel Ferey & Pierre Dehez, 2016. "Multiple Causation, Apportionment, and the Shapley Value," The Journal of Legal Studies, University of Chicago Press, vol. 45(1), pages 143-171.
    19. Meinhardt, Holger Ingmar, 2021. "Disentangle the Florentine Families Network by the Pre-Kernel," MPRA Paper 106482, University Library of Munich, Germany.
    20. Csóka, Péter & Jean-Jacques Herings, P., 2019. "Liability games," Games and Economic Behavior, Elsevier, vol. 116(C), pages 260-268.
    21. Rene van den Brink & Ilya Katsev & Gerard van der Laan, 2023. "Properties of Solutions for Games on Union-Closed Systems," Mathematics, MDPI, vol. 11(4), pages 1-16, February.

    More about this item

    Keywords

    Assignment game; General graph matching game; Core; Approximate core; Transferable utility (TU) market; LP-duality;
    All these keywords.

    JEL classification:

    • C02 - Mathematical and Quantitative Methods - - General - - - Mathematical Economics
    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D47 - Microeconomics - - Market Structure, Pricing, and Design - - - Market Design

    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:eee:gamebe:v:132:y:2022:i:c:p:478-486. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    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.