Winner-take-all (WTA) refers to the neural operation that selects a (typically small) group of neurons from a large neuron pool. It is conjectured to underlie many of the brain's fundamental computational abilities. However, not much is known about the robustness of a spike-based WTA network to the inherent randomness of the input spike trains. In this work, we consider a spike-based -WTA model wherein randomly generated input spike trains compete with each other based on their underlying firing rates and winners are supposed to be selected. We slot the time evenly with each time slot of length 1 ms and model the input spike trains as independent Bernoulli processes. We analytically characterize the minimum waiting time needed so that a target minimax decision accuracy (success probability) can be reached. We first derive an information-theoretic lower bound on the decision time. We show that to guarantee a (minimax) decision error (where ), the waiting time of any WTA circuit is at least [Formula: see text]where is a finite set of rates and is a difficulty parameter of a WTA task with respect to set for independent input spike trains. Additionally, is independent of , , and . We then design a simple WTA circuit whose waiting time is [Formula: see text]provided that the local memory of each output neuron is sufficiently long. It turns out that for any fixed , this decision time is order-optimal (i.e., it matches the above lower bound up to a multiplicative constant factor) in terms of its scaling in , , and .