Ben Sowell
7-13-06

Overview
--------

This program is designed to simulate the auctions that search engines perform
to sell advertisements. Typically, interested advertisers bid on certain query
terms. Every time a user searches for one of these terms, the search engine
runs an automated auction to determine which ads are displayed. As part of the 
bidding process, bidders specify individual bids as well as a daily budget. 
The goal (at least on the part of the search engine) is to maximize the 
auction revenue while respecting the bids and budgets of the individual 
bidders. 

Part of the challenge is that the auction must be performed immediately when 
a query is submitted. This is known as an online problem, in contrast to the 
offline problem where all queries are known ahead of time. In general, it is 
not possible to find an optimal solution to the online problem, but several 
algorithms have been proposed to approximate it (see Algorithms section below). 

This program simulates several algorithms for the online problem and includes
a number of extensions to more accurately simulate real world auctions. The 
remainder of this document describes in detail the program's functionality. 

A Note on Command Line Options: 
Much of the functionality in this program is accessed using the standard unix
getopt function. This allows for options to be entered in any order, and 
provides robust parsing. That said, many of the options must be entered in 
combination and some are mutually exclusive. Please consult this document for 
details on when specific options can be used. 


Algorithms
----------
The program implements the following algorithms:

mehta: 
Allocate the next query to the bidder i that maximizes the product of his/her
bid and psi(T(i)) where T(i) is the fraction of i's budget spent so far, and
			
			psi(x) = 1 - e ^ -(1 - x)

Source: 
A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani. Adwords and generalized 
online matching. In Proceedings of the 46th IEEE Symposium on Foundations of 
Computer Science, 2005.

max bid: 
Allocate the next query to the bidder with the largest bid. Ties are broken 
using the maximum remaining budget.  

max budget left: 
Allocate the next query to the bidder with the largest budget remaining.

min budget left:
Allocate the next query to the bidder with the smallest budget remaining.


Compiling
---------

The program can be easily compiled using the included "compile" script. 
Otherwise, the command
	gcc -o auction auction.c algorithms.c bidders.c queries.c prob.c
can be used. 


Specifying Bidders
------------------

Throughout execution, the program maintains a list of bidders who each bid on 
zero or more queries. Each bidder maintains a budget as well as the percentage 
of the budget spent for each algorithm. 

Budgets can either be specified in a file or generated randomly between 
specified bounds. If a file is to be used, the file name is entered on the 
command line using the -b flag. The file file must be in the following format:

numBidders				#line 1: The number of bidders
budget1					#line 2 - n: The budget of each bidder followed 
budget2					#			 by a newline. 
...

If the budgets are to be generated randomly, the -B flag is used to specify 
the number of bidders, -m is used for the minimum budget, and -M is used for 
the maximum budget. Each budget is chosen randomly (uniformly) from between
these bounds. 


Specifying Queries
------------------

Each query is identified by the individual bids made on it and stored as a list
of bidders and their respective bids. Like bidders, queries can be generated
randomly or read from a file. 

The mechanism for generating them randomly is very similar to that for bidders. 
The -Q flag is used to indicate the number of queries, -p the minimum bid size, 
and -P the maximum bid size. ('p' stands for 'price'). The program will choose
a random subset of bidders to bid on each query, and assign each a bid uniformly
distributed between the minimum and maximum size. 

The program accepts two file formats for specifying queries. For both, the 
file name is specified with the -q flag. The first, or 'standard' format, is 
used to specify deterministically the bids for each query. This format is 
detailed below:

A NOTE: Both the 'standard' and 'abbreviated' formats take an optional 
probability at the beginning of each query line. The indicates the probability
with which that query is chosen. The probabilities from every line should sum
to one. Probabilities will only affect the program if a constant graph is used 
(see the section "Constant and Variable Graphs" below). 

The first line contains the number of queries. Each successive line contains 
an optional probability followed by the number of bids for that query, 
followed by a sequence of bidder-bid pairs, where bidder's are identified 
by integers in [0, numBidders) according to their location in the list of 
bidders. 

numQueries									
[prob] numBids bidder1 bid1 bidder2 bid2 ...
[prob] numBids bidder1 bid1 bidder2 bid2 ...
...


The second or 'abbreviated' file format allows the user to specify the number 
of bidders and minimum and maximum bids on a per query basis. This is useful,
for instance, when testing special situations (i.e. a few queries have many 
bids). The user can opt to use the abbreviated format by using the -d flag. 
The file format is as follows:

The first line containsn the number of queries. Each successive line contains
an optional probability followed the number of bids for that query, followed
by the minimum and maximum bids. 

numQueries
[prob] numBids minBid maxBid
[prob] numBids minBid maxBid
...


Constant and Variable Graphs
----------------------------

We can view the simulation as maintaining a bipartite graph where the vertex 
sets are the bidders and queries, and each edge is a bid. The standard behavior
of the program is to use a so-called variable graph. In this case, each query 
in the query list is processed exactly once, and afterwards the bids are 
"forgotten" and are never used again. Two or more queries may have the same 
sequence of bidders or bids, and the queries are not the same as far as the 
program is concerned. 

On the other hand, if we use a constant graph the relationship between bidders 
and queries is fixed, and the queries are processed in a random order 
according to a given probability distribution. This allows us to simulate a
situation in which the overall distribution of queries might be known, but the 
specific order is not. 

The probability distribution can be specified in several ways. As discussed 
above, it can be included in the query file. In this case, the user is 
responsible for ensuring that all of the probabilities sum to 1. The 
probability distribution can also be generated randomly using the -D [dist] 
option where dist is one of "uniform", "normal", or "pareto." Each query will 
be assigned a probability according to the specified distribution. Note that 
this option will override any probabilities included in the query file.

Constant graph mode can be enabled with the option -c [num] where num is the 
number of queries to process.


Slots & Pricing
---------------

Search engines rarely display only one advertisement per page, and to 
accommodate this we also allow the user to vary the number of slots
(winners). This can be specified with the -n option. There is one slot by 
default. 

By default, each winner pays an amount equal to their bid. Most search engines
have begun to charge each bidder an amount equal to the next-highest highest 
in order to encourage them to bid according to their value. This is known as a 
"second price" scheme, and it can be enabled using the -s flag. 


Output
------
	
It is also possible to save randomly generated data to a file for later use.
If you include the -o [outFile] option, then the bidders and queries will be
written to outFile so that they can be read back later. 

	
Examples
--------
The following example demonstrate how the program might be used in practice. 
Consult the sections above or the list of options below for more information. 

Reading bidder and query data from one or two files:

./auction -b bidders.txt -q queries.txt
./auction -f combined.txt


Combining file input with random generation:

./auction -b bidders.txt -Q 1000 -p .10 -P 1.00
./auction -B 1000 -m 1000 -M 10000 -q queries.txt


Using a abbreviated query file and random bidders:

./auction -B 1000 -m 1000 -M 10000 -dq queries.txt 


Generating bidders and queries randomly:

./auction -B 1000 -m 1000 -M 10000 -Q 1000 -p .10 -P 1.00


Outputting data to a file:

./auction -B 1000 -m 1000 -M 10000 -Q 1000 -p .10 -P 1.00 -o outfile.txt


Reading data from a file, generating a normal probability distribution, and 
using an constant graph:

./auction -f combined.txt -c 1000 -D normal


The above with two slots and second price bidding

./auction -f combined.txt -c 1000 -D normal -s -n 2


Complete List of Options
------------------------
	-b [bidder file]    The file from which to read bidder data. Cannot be
	                    used with -f, -B, -m, or -M. 
                    

	-B [num]            The number of bidders to randomly generate. Must be 
	                    combined with -m and -M. Cannot be used with -b or -f. 
        
	-m [min budget]     The minimum possible budget for the randomly generated 
	                    bidders. Must be combined with -B and -M. Cannot be 
	                    used with -b or -f. 

	-M [max budget]     The maximum possible budget for the randomly generated 
	                    bidders. Must be combined with -B and -M. Cannot be 
	                    used with -b or -f.

	-f [file]           The file from which to read bidder and query data. 
	                    Shorthand for -b and -q. Cannot be used with -b, -B, 
	                    -m, -M, -q, -Q, -p, or -P. 

	-q [query file]     The file from which to read query data. Cannot be used
	                    with -f, -Q, -p, or -P. If this option is combined 
	                    with -d, the abbreviated format is assumed, otherwise
	                    the standard format is used. 


	-d                  Flag which specifies that the abbreviated file format
	                    should be used. Must be combined with the -q option. 
	                    Cannot be combined with -f, -Q, -p, or -P.


	-Q [num]            The number of queries to randomly generate. Must be 
	                    combined with -p and -P. Cannot be used with -q or -f. 


	-p [min bid]        The smallest possible bid to be generated. Must be 
	                    combined with -Q and -P. Cannot be used with -q or -f.


	-P [max bid]        The smallest possible bid to be generated. Must be 
	                    combined with -Q and -P. Cannot be used with -q or -f.


	-f [file]           The file from which to read bidder and query data. 
	                    Shorthand for -b and -q. Cannot be used with -b, -B, 
	                    -m, -M, -q, -Q, -p, or -P.
	
	
	-D [dist]			Assigns each query a probability generated randomly 
						from the specified distribution. The argument dist
						must be one of "uniform," "normal." or "pareto."
	
						
	-c [num]			Enables constant graph mode (See above). For this to 
						work properly, each query must be assigned a 
						probability, either in a file or with the -D option. 
	
	
	-n [num]			The number of slots to use. The default is 1
	
						
	-s					Enables second price bidding. 
	
	
	-o [outfile]		File to output bidder and query data to. 
	