Handling the special case where several biddders tie for the highest bid is surprisingly complex. First, simply detecting that there has been a tie is an information leak. This means that perfect privacy requires a method of computing the winner of a tied or untied bid in a uniform manner. Since computation and communication costs would leak information if they were different for tied or non-tied cases, this means that the overhead costs for all auctions must be the same as the overhead for the worst-case tie-breaking situation.
The simplest approach is to reveal 
as
described above to determine if there is a clear winner. If all these
values are 0, then there is a tie. Now reveal 
and randomly select some j for which
as the winner. This method is direct and efficient,
but reveals all tying bids (to the auctioneers).
Finding an efficient tie-breaking method to follow the bid resolution protocol as described is still an open problem. The authors are studying a modification to the overall protocol which allows efficient tie-breaking. The alternative has more complexity (in terms of its description) but uses a small value of p (with other modifications to prevent errors), so that communication costs are reduced.