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.