DA 03-2522

July 29, 2003

**AUCTION OF REGIONAL NARROWBAND PCS LICENSES**

**SCHEDULED FOR SEPTEMBER 24, 2003**

**ROUND RESULTS PROCESS AND RESULTS REPLICATION**

**Report No. AUC-03-51-C (Auction No. 51)**

# general information

By this public notice, the Wireless Telecommunications Bureau ("Bureau")
announces the round results process and results replication procedures
for the upcoming auction of six regional narrowband Personal
Communications Services ("narrowband PCS") licenses in the 900 MHz band
scheduled for September 24, 2003 ("Auction No. 51"). In the *Auction No.
51Procedures Public Notice*, the Bureau noted that it would release a
public notice providing details regarding round results formats and
locations, to enable participants and interested observers to replicate
the FCC's official round results. [^1]

# ROUND RESULTS PROCESS

The *round results* process is a sequence of administrative events that
occurs after the close of a round. During this time, bid data collected
during the round is processed, downloadable files are compiled, and
various indicators of auction status are created. This information can
be accessed by the public through the Results and the Bid Reports pages
of the Auction 51 Bidding & Results System, which will be available
through the Auction No. 51 website at
http://wireless.fcc.gov/auctions/51/.

The following subsections describe the events that transpire during the
round results process. The flow diagram below depicts this process and
its major components.

![](media/image2.jpeg){width="6.497222222222222in"
height="1.4493055555555556in"}

## PHASE 1 

The auction-closing rule dictates that after two consecutive rounds
without new bids the auction will close. The auction software performs a
test to see if this condition is met. If the test of the auction-closing
rule fails, the auction remains open and the round results process
continues. If the auction closes, the round results process does not
continue and the provisionally winning bids from the prior round will be
declared the winning bids of the auction.

## SOLVER PHASE

### Determine Provisionally Winning Bids 

Optimization software is used to determine the provisionally winning
bids. The determination of provisionally winning bids is a multi-step
process that involves solving for the maximum revenue and then choosing
among any tied bid sets.

### Determine Current Price Estimates 

Additional optimization procedures are used to obtain a current price
estimate of each license in the auction. The current price estimates
are, in turn, used to support the calculation of the minimum acceptable
bid for licenses and packages in the following round.

## PHASE 2

### Calculate Minimum Acceptable Bids

For each bidder, a minimum acceptable bid amount is calculated for each
eligible license and constructed package based on the following rule:

> The minimum acceptable bid is the *greatest* of:

i.  The applicable *minimum opening bid*.

ii. The bidder's own *previous high bid* on the license/package *plus
    x%*, where the Bureau will specify the value of x in each round.

iii. The *current price estimate* of the license or package *plus z%*,
     where the Bureau will specify the value of z in each round. The
     current price estimate for a package will be the sum of the current
     price estimates of the licenses that comprise the package.

> After the first round of the auction, part (iii) of the minimum
> acceptable bid rule for a "global package" -- a package consisting of
> all six of the licenses available in the auction -- will always be the
> revenue generated by the provisionally winning bid set in the previous
> round *plus w%*, where the Bureau will specify the value of *w* in
> each round.

The resulting amount will be rounded using our standard rounding
procedure.[^2]

### Calculate Bid Increments 

For each minimum acceptable bid, multi-increment bid amounts are
calculated. An increment is calculated as v% of the minimum acceptable
bid amount, where the Bureau will specify the value of v in each round.
The *k*^th^ increment bid amount is calculated as the minimum acceptable
bid amount plus *k* times the increment, rounded where the value of *k*
ranges from 1 to 8.

### Calculate Bidder Eligibility 

For each eligible bidder, *current eligibility* for the next round is
calculated. Current eligibility is defined as the *lesser* of (i) the
bidder's *eligibility activity*[^3] in the round and (ii) the reciprocal
of the *activity requirement* (1/activity requirement) multiplied by the
bidder's eligibility activity in the round. If the bidder's eligibility
activity does not meet its eligibility activity requirement and the
bidder has a waiver available, the waiver will be automatically applied
and the bidder's current eligibility for the next round remains
unchanged. If a bidder has no remaining waivers and fails to meet its
eligibility activity requirement, the bidder's current eligibility for
the next round is calculated as described above -- i.e., its eligibility
is permanently reduced.

### Post Files for Public Download

A number of files will be posted and made available for public download
on the Results page of the Auction 51 Bidding & Results System and on
the Results section of the Auction No. 51 website. These files contain
information about all bids made in that round, the set of bids
considered when determining the current provisionally winning bids,
current price estimates, new minimum acceptable bids for all bidders,
current provisionally winning bids, and bidder eligibility status
(bidding eligibility and activity rule waivers). Section III describes
the downloadable files.

# ROUND RESULTS DOWNLOADS

Round results files will be available for downloading upon completion of
the round results process after each round. The files will supply
bidders with more complete auction data than is available in the summary
tables and charts on the Results page. They are available in two
formats: Microsoft^®^ Access database (.mdb) and text (.txt). In
general, the database formatted files provide current round information
necessary to verify the provisionally winning bids, while the text files
contain more complete information, including data from previous rounds
of the auction. They are described in detail below.

## Database Files

A Microsoft^^ Access database containing the data needed to verify the
provisional winners for the round will be made available for download
upon completion of the round results process. Additional tables provided
within the database contain information to facilitate the correlation of
bidder, package, and license identification numbers to detailed
information about these entities. Data is also provided to verify the
selection number generated for each bid considered in the round.

The tables below detail the structure of the Microsoft^^ Access
database and the corresponding data description for each field.

The CONSIDERED_BIDS table contains a single record for every bid that is
considered in the current round.[^4]

  --------------------- ------------ ----------------------------------------
  Table Name:                        
  **CONSIDERED_BIDS**                

  **Field Name**        **Data       **Data Element Description**
                        Type**       

  bidder_id             int          Bidder Identification Number

  bid_id                int          Bid Identification Number

  package_id            int          Package Identification Number

  bid_amount            double       Bid Amount

  scaled_bid_amount     double       Bid Amount with the decimal point
                                     shifted six digits to the left (see
                                     Attachments A and B)

  bid_round_number      int          Bid Placement Round

  selection_number      float        Selection Number
  --------------------- ------------ ----------------------------------------

The CONSIDERED_BIDS_DETAIL table contains package construction
information for the packages found in the CONSIDERED_BIDS table. This
table contains a record for every license in a package. Therefore, a
package constructed of five licenses is described by five records, each
containing an identical package identification number (package_id) but a
different license identification number (license_id).

  ---------------------------- ------------ ----------------------------------------
  Table Name:                               
  **CONSIDERED_BIDS_DETAIL**                

  **Field Name**               **Data       **Data Element Description**
                               Type**       

  package_id                   int          Package Identification Number

  license_id                   int          License Identification Number
  ---------------------------- ------------ ----------------------------------------

The BID_SEED table contains a record for every bid that is considered in
the current round. Each record provides the six initial seed numbers
used with the Random Number Generator (see Attachment C) for the bid
described by the associated bid identification number (bid_id).

  ------------------ ------------ ----------------------------------------
  Table Name:                     
  **BID_SEED**                    

  **Field Name**     **Data       **Data Element Description**
                     Type**       

  bid_id             int          Bid Identification Number

  seed1              int          First Seed Number for Random Number
                                  Generator

  seed2              int          Second Seed Number for Random Number
                                  Generator

  seed3              int          Third Seed Number for Random Number
                                  Generator

  seed4              int          Fourth Seed Number for Random Number
                                  Generator

  seed5              int          Fifth Seed Number for Random Number
                                  Generator

  seed6              int          Sixth Seed Number for Random Number
                                  Generator
  ------------------ ------------ ----------------------------------------

The BIDDER_ID_MAP table contains a record for every registered bidder
for the auction. Each record associates the bidder identification number
with a company name.

  ------------------- ------------ ----------------------------------------
  Table Name:                      
  **BIDDER_ID_MAP**                

  **Field Name**      **Data       **Data Element Description**
                      Type**       

  bidder_id           int          Bidder Identification Number

  company_name        char(50)     Company
  ------------------- ------------ ----------------------------------------

The LICENSE_ID_MAP table contains a single record for every license in
the auction. Each record contains relevant license detail descriptions
for the associated license identification number.

  -------------------- ------------ ----------------------------------------
  Table Name:                       
  **LICENSE_ID_MAP**                

  **Field Name**       **Data       **Data Element Description**
                       Type**       

  license_id           int          License Identification Number

  description          char(30)     License Description

  service_code         char(2)      License Service Code

  market               char(6)      License Market

  frequency_block      char(2)      License Frequency Block

  sub_market           int          License Sub Market
  -------------------- ------------ ----------------------------------------

The Microsoft^^ Access database is named "auction51Rnd#.mdb", where \#
indicates the round of the auction. To facilitate the download of a
potentially large database, the file will be compressed within a
similarly named Zip file, "auction51Rnd#.zip."

## Text Files

A collection of tab-delimited text files will be made available for
public download separately as well as a single zipped file. These files
supplement the data made available in the downloadable .mdb file with
more extensive and detailed auction data. Each text file will be named
*auction#\_rnd#xx.txt,* where *auction#* is the number of the auction
(i.e., 51), *rnd#*, is the round number, and *xx* is an abbreviated file
descriptor. Specific file names are included in the table definitions
below.

### All Bids File

This file includes all bids considered in the determination of the
round's provisionally winning bids, which are, every bid by every bidder
throughout the auction and a set of FCC bids on each license for a
thousand dollars less than the applicable minimum opening bid. This file
contains one row for each license of each package. Therefore, the file
contains multiple rows and some duplicated data for packages with
multiple licenses. Bids placed but removed within a round will not be
included in this file. The table below contains information on the
column header, data type, and data description for each column within
the file.

  ------------------- ------------- -------------------------------------
  **File Name:                      
  51\_*rnd#*ab.txt                  
  (All Bids)/**                     

  **Column Header**   **Data Type** **Data Description**

  round               int           Round in which this bid was placed

  fcc_account_num     char(10)      Bidder-held FCC account number

  company             char(50)      Company Name of the bidder

  package_id          numeric(10)   Unique package identifier

  license_desc        char(30)      Description of the license

  service_code        char(2)       Identifies type of service (spectrum)
                                    offered

  market              char(6)       Identifies the geographic region of
                                    the license

  freq_block_num      char(2)       Identifies the block of frequency of
                                    the license

  sub_market          int           Identifies a portion of a market
                                    being offered

  bid_amt             money         Bid Amount of bid

  bid_type            char(1)       Identifies the type of bid: B= new
                                    bid; L= renewed non-winning bid; W=
                                    renewed winning bid; A= last and best
                                    bid;
  ------------------- ------------- -------------------------------------

### Current Round Bids File

This file includes only those bids placed in the current round. The
Current Round Bids file contains one row for each license of each
package.

  ------------------- ------------- -------------------------------------
  **File Name:                      
  51\_*rnd#*cb.txt                  
  (Current Round                    
  Bids)/**                          

  **Column Header**   **Data Type** **Data Description**

  round               int           Round in which this bid was placed

  fcc_account         char(10)      Bidder-held FCC account number

  company             char(50)      Company Name of the bidder

  package_id          numeric(10)   Unique package identifier

  license_desc        char(30)      Description of the license

  service_code        char(2)       Identifies type of service (spectrum)
                                    offered

  market              char(6)       Identifies the geographic region of
                                    the license

  freq_block_num      char(2)       Identifies the block of frequency of
                                    the license

  sub_market          int           Identifies a portion of a market
                                    being offered

  gross_bid_amt       money         Gross amount of the bid placed

  net_bid_amount      money         Net amount of the bid placed

  last_best           char(1)       Identifies a last and best bid

  prov_winner         char(1)       Identifies a provisional winner

  renewed_bid         char(1)       Identifies a renewed bid

  selection_num       float         Selection Number
  ------------------- ------------- -------------------------------------

### Minimum Acceptable Bids File

This file includes a row for all licenses applied for and every package
that was bid on by each respective bidder. **Packages that have been
constructed but not bid on in any round are not included in this
report.** The table below contains information on the column header,
data type, and data description for each column in the file.

  ------------------------ ------------- ------------------------------------
  **File Name:                           
  51\_*rnd#*mb.txt**                     

  **Column Header**        **Data Type** **Data Description**

  round_num                int           Identifies the round for which the
                                         minimum acceptable bid value applies

  fcc_account_num          char(10)      Bidder-held FCC account number

  company                  char(50)      Company Name of the bidder

  package_id               numeric(10)   Unique package identifier

  min_acceptable_bid_amt   money         Minimum acceptable bid amount

  gap_method               int           Rule method used to determine
                                         minimum acceptable bid
  ------------------------ ------------- ------------------------------------

### Auction Summary File

This file includes round summary statistics. Each row of the file
contains the statistics for each round in the auction. The table below
contains information on the column header, data type, and data
description for each column in the file.

  --------------------- ------------ ------------------------------------
  **File Name:                       
  51\_*rnd#*as.txt**                 

  **Column Header**     **Data       **Data Description**
                        Type**       

  round                 int          Round number of auction summary

  num_elig_bidders      int          Number of bidders still eligible in
                                     auction

  fcc_owned_licenses    int          Number of FCC owned licenses

  new_bids              int          Number of new bids in the round

  gross_rev             money        Gross Revenue for the round

  net_rev               money        Net Revenue for the round

  net_rev_pct           Float(8)     Percentage of Net Revenue increase
                                     in the round
  --------------------- ------------ ------------------------------------

### Auction Parameters File

This file includes the parameters for the auction. Each row of the file
contains the parameters for each round in the auction. The table below
contains information on the column header, data type, and data
description for each column in the file.

  --------------------- ------------ ------------------------------------
  **File Name:                       
  51\_*rnd#*ap.txt**                 

  **Column Header**     **Data       **Data Description**
                        Type**       

  round_num             int          Round number of auction summary

  required_activity     float(8)     Fraction of current eligibility a
                                     bidder must be active on without
                                     risk of eligibility reduction or
                                     eligibility activity waiver usage.

  min_bid\_ pctg_x      float(8)     Fraction of previous high bid to be
                                     applied in rule (ii) of minimum
                                     acceptable bid calculations

  min_bid\_ pctg_w      float(8)     Fraction of Gross Revenue to be
                                     applied in rule (iii) of minimum
                                     acceptable bid calculations for
                                     global bids

  min_bid\_ pctg_z      float(8)     Fraction of current price estimate
                                     to be applied in rule (iii) of
                                     minimum acceptable bid calculations

  min_bid_incr_pctg_v   float(8)     Fraction of minimum acceptable bid
                                     to be used as bid increment

  weight_factor         float(8)     Exponential smoothing weight factor
                                     used when determining current price
                                     estimates
  --------------------- ------------ ------------------------------------

### Bidder Summary File

This file includes summary information for bidders and contains one row
per qualified bidder. The table below contains information on the column
header, data type, and data description for each column in the file.

  ------------------------- ----------- ------------------------------------
  **File Name:                          
  51\_*rnd#*bs.txt**                    

  **Column Header**         **Data      **Data Description**
                            Type**      

  current_round             int         Current round number of the auction

  fcc_account_number        char(10)    Bidder-held FCC account number

  company                   char(50)    Company name of the bidder

  current_dollar_exposure   money       Dollar exposure of bids placed in
                                        the round

  overall_dollar_exposure   money       Dollar exposure considering all bids
                                        placed

  initial_max_elig          money       Bidder's initial eligibility

  current_max_elig          money       Bidder's current eligibility

  eligibility_activity      int         Bidder's eligibility activity for
                                        the round

  required_activity         int         Bidder's required activity level for
                                        the round

  prov_winning_activity     int         Bidder's activity from provisionally
                                        winning bids in the prior round

  remaining_waivers         int         Current number of waivers that the
                                        bidder has available

  waiver_ind                char(1)     Indicator of waiver being used in
                                        the round

  last_best                 char(1)     Indicator of last and best bids in
                                        the round

  bidding_credit_pctg       float       Bidding credit percentage that the
                                        bidder may apply to its gross bid
                                        amount
  ------------------------- ----------- ------------------------------------

### Provisionally Winning Bids File

This file contains information about the provisionally winning bids for
the round. It contains one row for each license of each package
contained in the set of provisionally winning bids. The file is in the
same format as the All Bids File. See Section III.B.1 for file
specifications.

  ------------------- ------------- -------------------------------------
  **File Name:                      
  51\_*rnd#*pw.txt                  
  (Provisionally                    
  Winning Bids)**                   

  **Column Header**   **Data Type** **Data Description**

  round_num           int           Round in which this bid was placed

  fcc_account_num     char(10)      Bidder-held FCC account number

  company             char(50)      Company Name of the bidder

  package_id          numeric(10)   Unique package identifier

  license_desc        char(30)      Description of the license

  service_code        char(2)       Identifies type of service (spectrum)
                                    offered

  market              char(6)       Identifies the geographic region of
                                    the license

  freq_block_num      char(2)       Identifies the block of frequency of
                                    the license

  sub_market          int           Identifies a portion of a market
                                    being offered

  bid_amt             money         Bid Amount of bid

  bid_type            char(1)       Identifies the type of bid: B= new
                                    bid; L= renewed non-winning bid; W=
                                    renewed winning bid; A= last and best
                                    bid;
  ------------------- ------------- -------------------------------------

### Current Price Estimate File 

This file contains one row for each license in the auction and displays
the current price estimate for each license. Bidders can use this file
to determine minimum acceptable bid amounts for packages created between
rounds. The table below contains information on the column header, data
type, and data description for each column in the file.

  ---------------------- ---------- -------------------------------------
  **File Name:                      
  51\_*rnd#*pr.txt**                

  **Column Header**      **Data     **Data Description**
                         Type**     

  current_round          int        Current round number of the auction

  lic_id                 int        Unique license identifier

  license_desc           char(30)   Description of the license

  service_code           char(2)    Identifies the service (spectrum)
                                    being offered

  market                 char(6)    Identifies the geographic region of
                                    the license

  freq_block_num         char(2)    Identifies the frequency block of the
                                    license

  sub_market             int        Identifies the portion of the market
                                    offered

  estimated_price        money      Estimate of the license price
  ---------------------- ---------- -------------------------------------

###  {#section .unnumbered}

# Reproducing the Provisionally Winning Bids 

At the close of each round, the round results process executes software
that determines the provisionally winning bids. This software employs
the CPLEX^^ optimization suite developed by ILOG^^, Inc. to determine
the maximum revenue and to choose among tied bid sets. Bidders will be
provided with the necessary instructions, problem models, and bid data
to facilitate the reproduction and verification of these results.
Instructions, problem models, and sample bid data will be posted on the
Auction No. 51 website by August 31, 2003. Below is a summary of the
optimization problems that must be solved and a description of a
modeling language tool, OPL Studio™, that can be used to verify the
provisionally winning bids for each round. The necessary bid data will
be provided each round in a Microsoft^^ Access database format, as
described in Section III.A.

## Summary of How Provisionally Winning Bids Are Determined

*Provisionally winning bids* are the set of consistent bids that
maximize total revenue in a particular round. Consistent bids are those
that (i) do not contain overlapping licenses and (ii) are made or
renewed by an individual bidder in the same round. Attachment A contains
a mathematical formulation of the optimization problem used to determine
the maximum revenue.

Since there can be more than one set of consistent bids that produces
the maximum revenue, a procedure for randomly selecting among these tied
sets is used when determining the provisionally winning bids. This tie
breaking procedure involves two steps, the assignment of a *selection
number* to each considered bid[^5] and the determination of the set that
produces the *maximum sum of* *selection numbers* among all tied bid
sets.

A bid's *selection number* is the sum of *n* pseudo-random numbers where
*n* is the number of licenses comprising the package being bid. Section
IV.B describes the process of assigning selection numbers and explains
how a bidder can reproduce selection numbers.

Once the selection numbers have been generated for each considered bid,
the optimization software is used to determine the set that produces the
maximum sum of selection numbers among any tied bid sets. This set
becomes the set of provisionally winning bids. Attachment B contains a
mathematical formulation of the optimization problem used to determine
this set. Thus, the provisionally winning bids are the set of consistent
bids that maximize revenue and maximize the sum of selection numbers.

## Assigning and Reproducing Selection Numbers

As part of the round results process, each considered bid is assigned a
new selection number.[^6] A bid's selection number is the sum of *n*
pseudo-random numbers where *n* is the number of licenses comprising the
package. Each pseudo-random number is generated by invoking a
well-documented and well-tested routine developed by Pierre L'Ecuyer.
This routine uses two multiple recursive random number generators of
order three with period length 2^219^. The description of the algorithms
can be found in L'Ecuyer, P. (1999) "Good Parameters and Implementations
for Combined Multiple Recursive Random Number Generators" *Operations
Research* 47 (1) pp. 159-164. Attachment C provides the C code used for
the generation of these random numbers. This code requires six integer
seed numbers as input and produces a double precision number between
zero and one.

The CPLEX^^ optimization software is capable of finding solutions to a
limited number of digits of accuracy; therefore, we perform the
following calculations to obtain a selection number for each bid. For a
bid on a package consisting of *n* licenses, we sum *n* double-precision
pseudo-random numbers. We then round this number to the nearest
millionth, i.e., six digits of accuracy to the right of the decimal
point.

A bid's selection number as well as the beginning seed numbers used to
produce it will be released upon completion of round results process for
each round within the Microsoft^^ Access data file as described in
Section III.A. This data along with the random number generator routine
can be used to reproduce the selection number associated with each
considered bid.

## Using OPL Studio™ to Reproduce Results

Formulations of the maximum revenue problem and the maximum sum of
selection numbers problem, written in an algebraic modeling language,
will be made available to bidders. Algebraic modeling languages provide
a mechanism for taking the algebraic description of the problem and
feeding this information along with the data to any of the standard
optimization software packages. Such modeling languages have the
advantage of keeping the problem in a concise representation common to
modelers while the software automatically generates the individual
constraints of the problem. Thus, these languages keep the model in a
simpler, more easily readable form while the modeling software manages
communication with an appropriate solver. Once optimal solutions have
been found, they are expressed in terms of the modeler\'s notation so
that they can be viewed and analyzed.

These models, stored as Revenue.mod and SelectionSum.mod, will be
available for download from the Auction No. 51 website. They are written
in the Optimization Programming Language (OPL) and used in the
application OPL Studio™.[^7] Most other algebraic modeling languages
have similar syntax so that a translation from OPL to any other
commercial modeling language is relatively straightforward.[^8] Since
the generic model is separate from any data instances of a given
auction, the same two model formulations can be used at the end of any
round of the auction to verify the results reported by the Bureau.

Along with the ".mod" files is an OPL Script file, stored as
RoundSolver.osc, which contains a meta-script for executing the two OPL
models and outputting information about the results. The OPL Script file
first executes the revenue model. Once the maximum revenue has been
determined, the OPL Script dynamically fixes the revenue constraint in
the selection sum model. This constraint ensures that bids in the
solution set produce the maximum revenue. The selection sum model is
then executed and information about the bids that compose the winning
set is written to the terminal output.

Once round results have been posted, bidders will be able to download
the Microsoft^®^ Access database containing the necessary information
about the considered bids for that round. With this data the OPL Script
can be executed in order to replicate the results obtained by the
Bureau. Instructions for setting-up the OPL Studio™ environment and
reproducing the provisionally winning bids each round are available with
the OPL files found on the Auction No. 51 website.

There is a rare chance that more than one set of bids can satisfy the
conditions of provisionally winning bids (i.e., there is more than one
set of bids that produces the maximum revenue and the maximum selection
sum). If such a case exists, the round results process will generate all
such sets and assign each a random number. The set with the largest
associated random number will be the set of provisionally winning bids.
If this unlikely event occurs, the set of bids that are found when the
OPL Script has been executed may not be the provisionally winning bids
for the round but will be a set of bids that produces both the maximum
revenue and the maximum selection sum.

# Point of contact

For questions regarding round results, download files, and reproducing
the provisionally winning bids contact Karen Wrege at (202) 418-0660.

# ATTACHMENT A

**Formulation of the Maximum Revenue Problem**

### ![](media/image3.wmf){width="5.031944444444444in" height="2.577777777777778in"} {#section-1 .unnumbered}

> where *B* is the set of considered bids (we use *i* as the index
> related to bids*)*,
>
> *b~i~* is the bid amount of bid *i*,
>
> *L* is the set of licenses (we use *l* as the index related to
> licenses),
>
> ![](media/image4.wmf){width="2.375in" height="0.5in"},
>
> *BR* is the set of bidders in the current round,
>
> (we use *j* as the index related to bidders),
>
> *AR~j~* is the set of active rounds of bidder *j* (we use *k* as the
> index related to rounds),
>
> *R~jk~* is the set of bids in active round *k* of bidder *j*, and
> \|*R~jk~*\| is the cardinality of the set
>
> ![](media/image5.wmf){width="2.5416666666666665in" height="0.5in"},
>
> ![](media/image6.wmf){width="3.9166666666666665in" height="0.5in"}

Note that an FCC bid on each license is included in the set of
considered bids. Therefore, the first set of constraints can be
formulated as equality.

Constraints (1) assure that each license is awarded exactly once. The
variables *y~jk~* are indicator variables that, when equal to one, allow
bids of bidder *j* from round *k* to be part of an optimal solution.
Constraints (3) allow at most one such *y~jk\ ~*for each bidder to equal
one and therefore at most one round of a bidder's bids can be part of an
optimal solution. When *y~jk~* is equal to zero, constraints (2) assure
that all bids in the round for bidder *j* in round *k (*x~*i*~
*i∈R~jk~*) equal zero. Similarly, when *y~jk~* equals one, constraints
(2) allow all bids in that round to be considered for inclusion in the
optimal set. [^9]

The objective function finds a set of bids that maximize the sum of the
bid amounts while simultaneously satisfying the constraints. Thus, the
result α is the maximum revenue obtainable for this round.

Note that in order to avoid numerical difficulties in the selection sum
problem, bid amounts are "scaled" by shifting the decimal place six
units to the left.[^10] Thus, the value of α will be scaled similarly.
Bidders will be provided with both the scaled and unscaled bid amounts
in the Microsoft^®^ Access database. For details on why scaling is
important in the selection sum problem, see Attachment B.

# ATTACHMENT B

**Formulation of the Maximum Selection Sum Problem**

![](media/image7.wmf){width="4.154166666666667in"
height="2.7597222222222224in"}

> where:
>
> *B* is the set of considered bids (we use *i* as the index related to
> bids*)*,
>
> *s~i~* is the selection number of bid *i*,
>
> *L* is the set of licenses (we use *l* as the index related to
> licenses),
>
> ![](media/image8.wmf){width="2.375in" height="0.5in"},
>
> *BR* is the set of bidders in the current round,
>
> (we use *j* as the index related to bidders),
>
> *AR~j~* is the set of active rounds of bidder *j* (we use *k* as the
> index related to rounds),
>
> *R~jk~* is the set of bids in active round *k* of bidder *j*, and
> \|*R~jk~*\| is the cardinality of the set
>
> *b~i~* is the bid amount of bid *i*,
>
> *α* is the maximum revenue (see Attachment A),
>
> ![](media/image5.wmf){width="2.5416666666666665in" height="0.5in"}
>
> ![](media/image6.wmf){width="3.9166666666666665in" height="0.5in"}

Constraints (1)-(3) are identical to the constraints in the maximum
revenue problem. Constraints (4) assure that the optimal set will yield
the maximum revenue. The objective function maximizes the sum of the
selection numbers.

As presented above, the selection sum problem has both very large and
very small numbers in the constraint matrix, which can result in
numerical difficulties. In order to avoid this, constraint (4) uses
scaled bid amounts and the associated scaled maximum revenue value, α,
as discussed in Attachment A. Bid amounts are scaled by shifting the
decimal place six units to the left. No accuracy is lost in altering the
data in this manner since the shift results in no loss of significant
digits. Bidders will be provided with both the scaled and unscaled bid
amounts in the Microsoft^®^ Access database.

# ATTACHMENT C

**C Code for the Random Number Generator**

#define norm 1.0842021724855052e-19

#define m1 9223372036854769163

#define m2 9223372036854754679

#define a12 1754669720

#define q12 5256471877

#define r12 251304723

#define a13n 3182104042

#define q13 2898513661

#define r13 394451401

#define a21 31387477935

#define q21 293855150

#define r21 143639429

#define a23n 6199136374

#define q23 1487847900

#define r23 985240079

long long s10, s11, s12, s20, s21, s22;

double MRG63k3a ()

{

long long h, p12, p13, p21, p23;

/\* Component 1 \*/

h = s10 / q13; p13 = a13n \* (s10 - h \* q13) - h \* r13;

h = s11 / q12; p12 = a12 \* (s11 - h \* q12) - h \* r12;

if (p13 \< 0) p13 += m1;

if (p12 \< 0) p12 += m1 - p13; else p12 -= p13;

if (p12 \< 0) p12 += m1;

s10 = s11; s11 = s12; s12 = p12;

/\* Component 2 \*/

h = s20 / q23; p23 = a23n \* (s20 - h \* q23) - h \* r23;

h = s22 / q21; p21 = a21 \* (s22 - h \* q21) - h \* r21;

if (p23 \< 0) p23 += m2;

if (p21 \< 0) p21 += m2 - p23; else p21 -= p23;

if (p21 \< 0) p21 += m2;

s20 = s21; s21 = s22; s22 = p21;

/\* Combination \*/

if (p12 \> p21) return ((p12 - p21) \* norm);

else return ((p12 - p21 + m1) \* norm);

}

[^1]: *See* Auction of Regional Narrowband PCS Licenses Scheduled for
    September 24, 2003; Notice and Filing Requirements, Minimum Opening
    Bids, Upfront Payments, Package Bidding and Other Auction
    Procedures, *Public Notice*, DA 03-1994 (rel. June 18, 2003),
    ("*Auction No. 51 Procedures Public Notice*").

[^2]: Results above \$10,000 are rounded to the nearest \$1,000; results
    below \$10,000 but above \$1,000 are rounded to the nearest \$100;
    and results below \$1,000 are rounded to the nearest \$10.

[^3]: We define a bidder's *eligibility activity* in a round to be the
    greater of (i) its bidding activity in the round and (ii) the
    bidding units associated with the bidder's provisionally winning
    bids from the prior round. *See Auction No. 51 Procedures Public
    Notice* at 22.

[^4]: When determining provisionally winning bids, all bids made in
    every round throughout the course of the auction (except for bids
    that are placed and subsequently removed during the same round) will
    be considered. In addition, each license is treated as having a bid
    placed by the FCC at some small amount less than the minimum opening
    bid. *See Auction No. 51 Procedures Public Notice* at 28 and 29.

[^5]: When determining provisionally winning bids, all bids made in
    every round throughout the course of the auction (except for bids
    that are placed and subsequently removed during the same round) will
    be considered. In addition, each license is treated as having a bid
    placed by the FCC at \$1000 less than the minimum opening bid. *See
    Auction No. 51 Procedures Public Notice* at 28 and 29.

[^6]: The order by which considered bids are assigned selection numbers
    is determined by ascending bid_id.

[^7]: OPL Studio™, developed by ILOG, Inc. (www.ilog.com), is an
    integrated development environment for combinatorial optimization
    applications. OPL Studio™ can be purchased at a reduced price for
    use during the auction by contacting Mark Steidel (775) 881-2813
    <msteidel@ilog.com>.

[^8]: A description of a number of algebraic modeling languages can be
    found on the web at

    <http://www-fp.mcs.anl.gov/otc/Guide/SoftwareGuide/Categories/optsysmodlang.html>.

[^9]: We acknowledge also that there is an alternative formulation for
    constraints (2) of the form *x~j~* ≤ *y~ij~* for all *i,j* that
    would expand the number of constraints but make the linear program
    solution value tighter. We have left the formulation as is since
    optimization packages often add these tightening constraints as
    needed.

[^10]: No accuracy is lost in altering the data in this manner since the
    shift results in no loss of significant digits.