44 citations · 80 across the 32 of their papers we have counts for
8 papers · 1 filter
Simple Games versus Weighted Voting Games: Bounding the Critical Threshold Value
Frits Hof, Walter Kern, Sascha Kurz +2
A simple game is given by a set of players and a partition of~ into a set~ of losing coalitions~ with value that is closed under takin…
Computing the Nucleolus of Weighted Voting Games in Pseudo-polynomial Time
Kanstantsin Pashkovich
We provide an algorithm for computing the nucleolus for an instance of a weighted voting game in pseudo-polynomial time. This resolves an open question posed by Elkind. et.al. 2007…
On the approximability of the stable matching problem with ties of size two
Robert Chiang, Kanstantsin Pashkovich
The stable matching problem is one of the central problems of algorithmic game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum…
Three-dimensional Stable Matching with Cyclic Preferences
Kanstantsin Pashkovich, Laurent Poirrier
We consider the three-dimensional stable matching problem with cyclic preferences, a problem originally proposed by Knuth. Despite extensive study of the problem by experts from di…
Bounds on the number of 2-level polytopes, cones and configurations
Samuel Fiorini, Marco Macchia, Kanstantsin Pashkovich
We prove an upper bound of the form on the number of affine (resp. linear) equivalence classes of, by increasing order of generality, 2-level d-pol…
On Critical Threshold Value for Simple Games
Kanstantsin Pashkovich
In this note, we show that for every simple game with n players the critical threshold value is at most n/4. This verifies the conjecture of Freixas and Kurz.
On the approximability of the stable marriage problem with one-sided ties
Felix Bauckholt, Kanstantsin Pashkovich, Laura Sanità
The classical stable marriage problem asks for a matching between a set of men and a set of women with no blocking pairs, which are pairs formed by a man and a woman who would both…
Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time
Jochen Koenemann, Kanstantsin Pashkovich, Justin Toth
We provide an efficient algorithm for computing the nucleolus for an instance of a weighted cooperative matching game. This resolves a long-standing open question posed in [Faigle,…