Check out the new USENIX Web site.

next up previous
Next: Phase 1: Determining the Up: A scalable secret-bid second-price Previous: Incorrect bids

Bid resolution

The auctioneers use the submitted bids to compute the selling price tex2html_wrap_inline1100 , which will be equal to the second highest bid submitted. This computation is performed over d rounds, one digit per round, going from most significant to least significant. We will use k to refer to the number of the current round. The value of the digits of tex2html_wrap_inline1106 is not kept secret (from the auctioneers), but is known to all auctioneers as it is computed.

Some shared polynomials tex2html_wrap_inline1108 will be computed from the tex2html_wrap_inline1110 over the course of price determination. Intuitively, these values are used to track the bid tex2html_wrap_inline1112 of bidder tex2html_wrap_inline1114 as compared to the first k-1 digits of the selling price.

While the comparisons above use the value of tex2html_wrap_inline1130 , the results are determined entirely by the first k-1 digits, which are known prior to round k. The tex2html_wrap_inline1136 are indicators for the winning bidder. The value tex2html_wrap_inline1138 is non-zero when the first k-1 digits of the bid tex2html_wrap_inline1142 indicate that the bid is greater than tex2html_wrap_inline1144 . Since the selling price is the second highest bid, tex2html_wrap_inline1146 means that bidder j has the highest bid. The tex2html_wrap_inline1150 are indicators for the losing bidders. The value tex2html_wrap_inline1152 will equal 0 when the first k-1 digits of the bid tex2html_wrap_inline1158 indicate that the bid is less than tex2html_wrap_inline1160 . So, tex2html_wrap_inline1162 means that tex2html_wrap_inline1164 is at most the third highest bid and that the particular bid tex2html_wrap_inline1166 will have no effect on the outcome of the bidding.

The tex2html_wrap_inline1168 , which are computed in round k by tex2html_wrap_inline1172 , indicate whether a bid is at least as high as some specific test value. The value tex2html_wrap_inline1174 is non-zero when the first k digits of bid tex2html_wrap_inline1178 (interpreted as a base c number) is greater than or equal to the first k-1 digits of tex2html_wrap_inline1184 appended by l (interpreted as a base c number). These tex2html_wrap_inline1190 are used in round k to determine the tex2html_wrap_inline1194 digit of the selling price by testing all possible values.

Since the tex2html_wrap_inline1196 and tex2html_wrap_inline1198 are computed from values tex2html_wrap_inline1200 , tex2html_wrap_inline1202 , and tex2html_wrap_inline1204 in round k-1, we must establish values for the tex2html_wrap_inline1208 and tex2html_wrap_inline1210 . For all j, let tex2html_wrap_inline1214 be the constant polynomial 0 and let tex2html_wrap_inline1218 be the constant polynomial 1. In an implementation, computation using these initial values will be trivial (i.e. addition to 0 or multiplication by 1).

The auctioneers will perform summations of the tex2html_wrap_inline1226 over certain values of j (i.e. subsets of tex2html_wrap_inline1230 ). Define tex2html_wrap_inline1232 to be a collection of subsets of tex2html_wrap_inline1234 (the index set for the bidders). Let tex2html_wrap_inline1236 if and only if the tex2html_wrap_inline1238 bit (in a tex2html_wrap_inline1240 bit binary representation) of j-1 is zero. We will interpret these tex2html_wrap_inline1244 as partitions which separate tex2html_wrap_inline1246 into two parts based on inclusion in the set tex2html_wrap_inline1248 . The rationale behind the selection of these partitions (the tex2html_wrap_inline1250 for tex2html_wrap_inline1252 ) is that for any pair of distinct bidders j and tex2html_wrap_inline1256 , there is at least one partition which separates j from tex2html_wrap_inline1260 .





next up previous
Next: Phase 1: Determining the Up: A scalable secret-bid second-price Previous: Incorrect bids



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