Computing solutions for matching games

DOI10.1007/S00182-011-0273-YMaRDI QIDQ662281zbMATH OpenOpenAlexFDO

Authors Péter Biró, Walter Kern, Daniël Paulusma

Publication date 22 February 2012

Published in International Journal of Game Theory (Search for Journal in Brave)

Full work available at URL http://dro.dur.ac.uk/9017/1/9017.pdf

cooperative game theory core matching game nucleolus

Games on graphs (graph-theoretic aspects) (05C57) Cooperative games (91A12) Games involving graphs (91A43) Matching models (91B68)

Review text

This paper studies matching games. A matching game is a cooperative game \((N, v)\) defined on a graph \(G = (N, E)\) with \(n=|N|\) vertices, \(m=|E|\) edges, and an edge weighting \(w : E \rightarrow {\mathbb R}_+\). The player set is \(N\) and the value of a coalition \(S\subseteq N\) is defined as the maximum weight of a matching in the subgraph induced by \(S\). As is usual in cooperative game theory, it is assumed that the grand coalition \(N\) is formed. Then, the central problem is how to allocate the total value \(v(N)\) to the individual players in \(N\). An allocation is a vector \(x\in {\mathbb R}^N\) with \(\sum_{i\in N}{x_i} = v(N)\). The authors focus on two sets of allocations for matching games: (a) the core, i.e., the set of allocations with \(\sum_{i\in S}{x_i} \geq v(S)\) for all coalitions \(S\), and (b) the nucleolus, which is a singleton contained in the core if the latter is non-empty [\textit{D. Schmeidler}, SIAM J. Appl. Math. 17, 1163--1170 (1969; Zbl 0191.49502)]. Regarding the core, the authors provide a necessary and sufficient condition for the non-emptiness of the core of a matching game, connecting the maximum weight of matchings with the maximum weight of half-matchings (Proposition 1). Since a maximum weight matching and a maximum weight half-matching can be found in \(O(nm + n^2 \log n)\) time, it follows that there exists an \(O(nm + n^2 \log n)\) time algorithm that tests if the core of a matching game is non-empty and that computes a core allocation in the case that the core is non-empty (Theorem 5). Regarding the nucleolus, the authors show that the nucleolus of a matching game with a non-empty core can be computed in \(O(n^4)\) time (Theorem 6). This result generalizes the corresponding result of \textit{T. Solymosi} and \textit{T. E. S. Raghavan} [Int. J. Game Theory 23, No. 2, 119--143 (1994; Zbl 0811.90128)] for assignment games, which are matching games based on bipartite graphs. Finally, the authors prove that it is NP-hard to determine an imputation (i.e., an allocation \(x\) such that \(x_i \geq v(\{i\})\) for all singletons \(\{i\}\)) with a minimum number of blocking pairs, even for matching games with unit edge weights (Theorem 7). The problem of determining an imputation with minimum total blocking value is shown to be polynomial-time solvable for general matching games (Proposition 2).

Recommendations

Cites work

Cited in

(26)

This page was built for publication: Computing solutions for matching games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q662281)