Andy,

Excellent feedback, thank you for that!

You're on point in suggesting to make it explicit to prioritize non-self matches over self matches --- which can be done in the algorithm or by requiring that v_ij > 0 when i != j. The latter was my original intention.

Even with that, there is always the possibility of a self-match, which in my code I call a 'fault'. It turns out that, with the above change to ensure prioritization, there can be at most one fault. Otherwise, there would be two players who could have matched earlier (due to the above) but didn't, a contradiction.

A fault happens depending on the randomization and the conditioning of the instance, as you pointed out. Nothing to avoid, it's just a fact of life that one person may not be able to mix all of his coins in that instance.

Still, you reminded me of a topic I wanted to include in the paper on well- or ill-conditioned instances. Eg, if one player has input that is larger than the sum of all the others, then chances are that he will mix with a large number of the other players, and will certainly be the one with a self match for the remainder of his coins.

I want to avoid this or allow the players to avoid mixing in this circumstance, so another open question I will add is: can input conditions be defined that define an ill-conditioned instance? If so, then the approach will be that either each player checks for this condition during the process to decide whether to mix with a certain player or during peer discovery the condition is used to filter which players are grouped together.

On DoS:
That's exactly the line of thinking that's helpful, because I think the algorithm is such that DoS is an attacker's best option.

My thoughts are that particular attack can be mitigated by (1) adding a step where players confirm the inputs they received against each others, and (2) allowing the players to drop a peer if the result of that confirmation show that the peer sent different inputs to sufficiently high number of players. This seems similar to the blame idea from Tim's CoinShuffle paper.

What's clear is that honest players need a way to identify and boot bad players. That is a work in progress, and I been considering whether to use such a step for input confirmation for a while now. Need to be careful about opening more attack vectors by the inclusion of confirmation steps.