In the Shapley-Scarf economy each agent is endowed with one unit of an indivisible good (house) and wants to exchange it for another, possibly the most preferred one among the houses in the market. In this economy, core is always nonempty and a core allocation can be found by the famous Top Trading Cycles algorithm. Recently, a modification of this economy, containing Q >= 2 types of goods (say, houses and cars for Q=2) has been introduced. We show that if the number of agents is 2, a complete description of the core can be found efficiently. However, when the number of agents is not restricted, the problem to decide the nonemptyness of the core becomes NP-hard already in the case of two types of goods. We also show that even the problem to decide whether an allocation exists in which each agent strictly improves compared to his endowment, is NP-complete.
In the minimization of the number of subtours made by the insertion head of an SMD placement machine a variant of the network flow problem arose. In a network with <span class="tex">n</span> vertices and <span class="tex">m</span> arcs a set <span class="tex">F</span> of arcs (parametrized arcs) is given. The task is to find a flow of a given size such that the maximum of flow values along the arcs from <span class="tex">F</span> is minimized. This problem can be solved by a sequence of maximum flow computations in modified networks where the capacities of the parametrized arcs are successively set to an increasing sequence of target parameter values. We show that it suffices to consider at most <span class="tex">O(|F|)</span> different target values and so this approach leads to a strongly polynomial algorithm consisting of at most <span class="tex">O(|F|)</span> maximum flow computations.
To overcome the shortage of cadaveric kidneys available for transplantation, several countries organize systematic kidney exchange programs. The kidney exchange problem can be modelled as a cooperative game between incompatible patient-donor pairs whose solutions are permutations of players representing cyclic donations. We show that the problems to decide whether a given permutation is not (weakly) Pareto optimal are NP-complete.