The {\it nucleon} is introduced as a new allocation concept for
non-negative cooperative n-person transferable utility games.
The nucleon may be viewed as the multiplicative analogue of
Schmeidler's nucleolus.
It is shown that the nucleon of (not necessarily bipartite) matching
games ... more >>>

We show that the perfect matching problem is in the
complexity class SPL (in the nonuniform setting).
This provides a better upper bound on the complexity of the
matching problem, as well as providing motivation for studying
the complexity class SPL.

Using similar ... more >>>

We study bounded degree graph problems, mainly the problem of
k-Dimensional Matching \emph{(k-DM)}, namely, the problem of
finding a maximal matching in a k-partite k-uniform balanced
hyper-graph. We prove that k-DM cannot be efficiently approximated
to within a factor of $ O(\frac{k}{ \ln k}) $ unless $P = NP$.
This ... more >>>

We study small degree graph problems such as Maximum Independent Set
and Minimum Node Cover and improve approximation lower bounds for
them and for a number of related problems, like Max-B-Set Packing,
Min-B-Set Cover, Max-Matching in B-uniform 2-regular hypergraphs.
For example, we prove NP-hardness factor of 95/94
more >>>

We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>>