The problem of controlling a Markov chain on a countable state space with ergodic or ’long run average’ cost is studied in the presence of additional constraints, requiring finitely many (say, m) other ergodic costs to satisfy prescribed bounds. Under extremely general conditions, it is proved that an optimal stationary randomized strategy can be found that requires at most m randomizations. This generalizes a result of Ross.