Check out the new USENIX Web site.

next up previous
Next: A sample auction Up: Determining the winning bidder Previous: Determining the winning bidder

Breaking ties

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 tex2html_wrap_inline1390 as described above to determine if there is a clear winner. If all these values are 0, then there is a tie. Now reveal tex2html_wrap_inline1394 and randomly select some j for which tex2html_wrap_inline1398 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.



Doug Tygar
Wed Jul 22 10:16:16 EDT 1998