Choosing k from m: feasible elimination procedures reconsidered

We show that feasible elimination procedures Peleg, 1978 can be used to select k from m alternatives. An important advantage of this method is the core property no coalition can guarantee an outcome that is preferred by all its members. We also provide an axiomatic characterization for the case k1, using the conditions of anonymity, Maskin monotonicity, and independent blocking. Finally, we show for any k that outcomes of feasible elimination procedures can be computed in polynomial time, by showing that the problem is computationally equivalent to finding a maximal matching in a bipartite graph.