The auctioneers use the submitted bids to compute the selling price
, 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
is not kept secret (from the auctioneers), but is known to all
auctioneers as it is computed.
Some shared polynomials will be computed from
the
over the course of price determination. Intuitively,
these values are used to track the bid
of bidder
as
compared to the first k-1 digits of the selling price.
The , which are computed in round k by
, indicate whether a bid is at least
as high as some specific test value. The value
is
non-zero when the first k digits of bid
(interpreted as a base
c number) is greater than or equal to the first k-1 digits of
appended by l (interpreted as a base c number). These
are used in round k to
determine the
digit of the selling price by testing all
possible values.
Since the and
are computed from values
,
, and
in round k-1, we must establish
values for the
and
. For all j, let
be the
constant polynomial 0 and let
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 over certain
values of j (i.e. subsets of
). Define
to be a collection of subsets of
(the index set for the bidders). Let
if
and only if the
bit (in a
bit binary
representation) of j-1 is zero. We will interpret these
as
partitions which separate
into two parts based on
inclusion in the set
. The rationale behind the selection of
these partitions (the
for
) is
that for any pair of distinct bidders j and
, there is at least
one partition which separates j from
.