Auctions

 

The auction is an important economic mechanism which is widely used to sell a variety of commodities, such as treasury bills, mineral rights including oil fields, real estate, art works, etc. With the growing popularity of the Internet, many traditional auctions are transforming into electronic auctions, and many new electronic auctions are being created. As a result, a number of web-based auction markets [1] have emerged. These range from relatively public markets such as auctions run by e-Bay, Amazon, and Yahoo! to Business-to-Business auctions (freemarkets.com, commerceonce.com) to double auctions such as on-line stock markets. Compared to traditional auctions, electronic auctions have the advantages; they are global in scope, may be less expensive than traditional auctions. Participants in electronic auctions require neither physical presence nor (for off-line auctions) a connected electronic presence.

Our Auction Model. We consider general auctions. We view an auction as a triplet of trading rules, participant strategies, and result disclosure rules. The trading rules are announced before the auction. The sellers and bidders submit their strategies during the submission time as specified in the trading rules. Then, during the auction evaluation time, the seller and bidder strategies are evaluated according to the trading rules and the result is determined. The result disclosure rules furthermore define how the result is announced, i.e. public or only to the winner and the seller.

This model embraces a wide variety of auctions. See [] for more information on auction types and variations. We briefly present the most common auctions:

• Ascending-bid auction (aka English auction): The bidders alternatively raise their bids or retire until only one bidder is left.
• Descending-bid auction (aka Dutch auction): The price continuously decreases until a bidder claims the good at that price.
• First-price sealed-bid auction: Each bidder submits her bid secretly, the highest bidder wins and pays the value of the bid.
• Second-price sealed-bid auction (aka Vickrey auction): Each bidder submits her bid secretly, the highest bidder wins and pays the value of the second-highest bid.

Our auction model also embraces more elaborate auctions, as shown in the following examples. Usually, auctions have one seller and many buyers, but in reverse auctions such as Priceline, only one buyer initiates the auction and many sellers place their offers. In the case of multiple buyers and sellers, the auction is called a double auction. If the resource sold in the auction is an on-going resource such as electricity, and the bids are cleared in short time intervals, the auction is known as a continuous auction. For example the stock market is an instance of a continuous double auction. If the bids contain multiple attributes such as volume and price, the auction is called a multi-attribute auction. For example, a future specifies a contract to buy/sell a stock at a particular price at a certain time in the future, hence it is a multi-attribute auction. The bids can include conditions of other commodities, i.e. ``I buy A at a price X only if I can buy B at a price Y.''. Such an auction is called combinatorial auction.

Fraud. Buyers and sellers have direct interests in the outcome of the auction. However, often society itself has a broader interest in ensuring that certain kinds of fraudulent or criminal behavior does not occur. Our model can also extend to include these interests, by including attempts at fraud monitoring and suppression as additional trading rules.

Problem Statement. Electronic auctions are promising, but they also create new security challenges. The Internet bears many security threats; auctioneers, sellers, and bidders may all have more opportunities to cheat in an electronic auction. Many different types of auctions exist and they have various security requirements. The security properties we consider include:

• Authentication, privacy and anonymity of participants
• secrecy of bids and strategies
• controllable revelation of information about the auction including the final result
• the atomicity of the goods and charge (i.e., a winner only needs to pay if he gets the goods or vice versa) [19, 3].
• authentication by participants and stakeholders that any given auction actually followed the above rules.

Prior to our work, no solution satisfied this wide variety of security requirements.

A main disadvantage of most of the existing auction schemes is that they require the sellers and bidders to trust the auctioneer. But in fact a common attack is that the auctioneer uses the seller and bidder information as an advantage to increase profits.

A critical part of auctions and markets is the ability of participants to hide private information, such as their strategies, resources, and even identities. However, this privacy enables many types of fraud, such as:

• Options front-running, where a broker places a small order for himself before placing a large order for a client (which changes the price)
• Money laundering in futures markets, where a broker places symmetric orders, and later attributes the winning one to Alice and the losing one to Bob (thus enabling Bob to pay an untraceable bribe to Alice)
• Fraudulent bids that win auctions [20].
• Collusion among participants in an auction
• Auctioneer driving up the price via fake bidders (perhaps to increase his commission), or otherwise exploiting the anonymity of bidders.

As marketplaces become increasingly distributed and automated, these problems become even worse. The problem is further complicated by mutual distrust among auctioneers, who would not want to share any of their secret information. When a critical infrastructure (e.g., the power-grid) is involved, the consequences of this rogue activity may change from simple fraud to a significant national emergency.