Auctions come in a wide range of types, distinguished by the way bidders submit their bids and how the allocations and prices are determined [16]. In a double-sided (or just double ) auction, both buyers and sellers submit bids. A single agent may even submit both, offering to buy or sell depending on the price. Double auctions come in different forms. Most of them have the following features: (1) There are more than 2 buyers and more than 2 sellers; (2) One unit of good is traded each time; (3) Bids are observable to all agents once they are submitted; (4) Each agent's preference is unknown to other agents.
Based on the timing of the bidding protocol, double auctions can be classified as synchronous (or synchronized ) double auctions and asynchronous double auctions. In a synchronous double auction, all agents submit their bids in lockstep. Bids are ``batched'' during the trading period, and then cleared at the end of the period. In real life, the clearinghouse is an prime example of such auctions. The Santa Fe Tournament [19] also adopts the form of such auctions. Asynchronous double auctions are also called continuous double auctions where agents offer buy or sell and accept other agents' offers at any moment. Continuous double auctions have been widely used in stock exchange markets [8] and internet auctions.
The book edited by Friedman and Rust [9] collects several studies of double auctions, including both simulations and game-theoretic analyses. Game-theoretic studies [20,8] on double auctions generally adopt the framework of static (one-shot) games with incomplete information, for which the equilibrium solution is Bayesian Nash equilibrium. Since double auctions are essentially dynamic games since agent interaction takes more than one round, the static game framework fails to address the basic dynamics of the system. Other theoretical studies [6] try to explain the experimental data generated from human subjects. They assume that each buyer or seller has a reservation price and has a way to re-calculate its reservation price after trading. While the study of human behavior is interesting, we are more interested designing artificial agents who can bid as smart as possible to get maximum payoffs from the double auctions.
Gode and Sunder [11] designed zero-intelligence agents who submit random bids within the range that their utilities never decrease. Such agents can be viewed as ome type of 0-level agents defined in this paper. To improve upon zero-intelligence agents, Cliff [4] designed zero-intelligence-plus agents who submit bids within the utility increasing range, but the bids are chosen so that their utilities will increase with a proportion. The proportion is adjusted over time. The adjusting process can be seen an an online learning process. The learning depends on several parameters such as the learning rate. Cliff implemented a genetic algorithm (GA) to let the agent learn about these parameters. The training with the GA requires the agent to know the final convergence price of the whole auction. It is not clear how such GA training can be applied to online settings.
Other types of intelligent agents have also been designed for double auctions. In Santa Fe Tournament [19], 30 different intelligent programs competed in a synchronized double auction, then a simple non-adaptive agent won. We have more discussion of that agent at the end of Section 6.