One big problem with the N-way lottery protocol in this paper is that it requires an extremely steep security deposit. Each player wagers only 1 coin, but has to additionally deposit N(N-1) coins. In total, only N coins are wagered, but O(N3) coins are escrowed for fairness. They argue (and I agree with it) that this is the best that can be done... for a one round protocol!
I claim that we can improve on this, having exactly the same payoff structure and security, and deposits only of size N. The caveat is that it requires log2 N rounds. The protocol is a tournament bracket. Each player commits to log2 N random numbers. In first round, player 0 plays a 50/50 coinflip game with player 1, player 2 plays with player 3, etc. If a player reveals their random secret, they can immediately exit the game and get their deposit back. If they win, they go on to the next round. If one player in a match does not reveal their secret, then their deposit is forfeited.
[edit]I actually have no idea how to pull this off. Seems impossible to me at the moment.