Yes, agreed. One small point: for the multi-class case (more than just two classes), which include all the datasets here, you can still get ties for odd k. e.g. k=3, you can get 1 vote each for 3 different classes, etc.

Multi-class is trickier. Maybe we can break down an N-class problem into N binary-classification problems?