A matching game is a cooperative game (N; v) defined on a graph G = (N;E) with an edge weighting w : E ! R+. The player set is N and the value of a coalition S N is defined as the maximum weight of a matching in the subgraph induced by S. First we present an O(nm+n2 log n) algorithm that tests if the core of a matching game defined on a weighted graph with n vertices and m edges is nonempty and that computes a core member if the core is nonempty. This algorithm improves previous work based on the ellipsoid method and can also be used to compute stable solutions for instances of the stable roommates problem with payments. Second we show that the nucleolus of an n-player matching game with a nonempty core can be computed in O(n4) time. This generalizes the corresponding result of Solymosi and Raghavan for assignment games. Third we prove that is NP-hard to determine an imputation with minimum number of blocking pairs, even for matching games with unit edge weights, whereas the problem of determining an imputation with minimum total blocking value is shown to be polynomial-time solvable for general matching games.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Computing Solutions for Matching Games


    Beteiligte:
    Biró, Péter (Autor:in) / Kern, Walter (Autor:in) / Paulusma, Daniël (Autor:in)

    Erscheinungsdatum :

    2011-01-01


    Anmerkungen:

    RePEc:has:discpr:1142


    Medientyp :

    Paper


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    330 / 629




    Adverse Selection via Matching in Cooperative Fog Computing

    Yang, Zexuan / Wang, Li / Ding, Yinan et al. | IEEE | 2018


    Interval methods for computing strong Nash equilibria of continuous games

    Kubica, Bartłomiej / Woźniak, Adam | BASE | 2016

    Freier Zugriff

    Dependable computing challenges and solutions

    Arlat, J. | British Library Online Contents | 1996


    Multi-agent discrete-time graphical games and reinforcement learning solutions

    Abouheaf, M. / Lewis, F.L. / Vamvoudakis, K.G. et al. | BASE | 2014

    Freier Zugriff