Computing Solutions for Matching Games

Péter Biró, Walter Kern () and Daniel Paulusma ()
Additional contact information
Walter Kern: Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O.Box 217, NL-7500 AE Enschede
Daniel Paulusma: Department of Computer Science, University of Durham Science Laboratories, South Road, Durham DH1 3EY, England

No 1142, CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies

Abstract: 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 de ned 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.

Keywords: matching game; nucleolus; cooperative game theory (search for similar items in EconPapers)
JEL-codes: C61 C63 C71 C78 (search for similar items in EconPapers)
Pages: 21 pages
Date: 2011-12
New Economics Papers: this item is included in nep-cmp, nep-gth and nep-hpe
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://econ.core.hu/file/download/mtdp/MTDP1142.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to econ.core.hu:80 (A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond.)

Related works:
Journal Article: Computing solutions for matching games (2012)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:has:discpr:1142

Access Statistics for this paper

More papers in CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies Contact information at EDIRC.
Bibliographic data for series maintained by Nora Horvath ( this e-mail address is bad, please contact ).