The design and implementation of a secure auction service

We present the design and implementation of a distributed service for performing sealed bid auctions. This service provides an interface by which clients, or “bidders”, can issue secret bids to the service for an advertised auction. Once the bidding period has ended, the auction service opens the bids, determines the winning bid, and provides the winning bidder with a ticket for claiming the item bid upon. Using novel cryptographic techniques, the service is constructed to provide strong protection for both the auction house and correct bidders, despite the malicious behavior of any number of bidders and fewer than one third of the servers comprising the auction service. Specifically, it is guaranteed that: bids of correct bidders are not revealed until after the bidding period has ended; the auction house collects payment for the winning bid; losing bidders forfeit no money; and only the winning bidder can collect the item bid upon. We also discuss techniques to enable anonymous bidding     

Design of online auctions: Proxy versus non-proxy settings

Recent years have witnessed the rapid development of online auctions. Currently, some online auctions, such as eBay, introduce a proxy bidding policy, under which bidders submit their maximum bids and delegate to a proxy agent to automatically outbid other competitors for the top bidder, whereas other online auctions do not. This paper compares these two widely used auction mechanisms (proxy setting and non-proxy setting) and characterizes the equilibrium bidding behavior and the seller's expected revenue. We find the proxy auction outperforms the non-proxy auction in terms of the seller's expected revenue. This dominance result is not prone to the specific bid announcement policy, the bidder's knowledge regarding the number of bidders, the impact of traffic congestion along the bidding process, the number of items sold through the auction, and the existence of a reserve price.We further find that the proxy setting usually fails to sustain the truthful bidding as a dominant strategy equilibrium even if no minimum bid increments are adopted, and the possibility of a low-valuation-bidder dilemma where the low-valuation bidders could be better off if all bidders collude to bid at the last minute. We also discuss the dramatically different equilibrium bidding behaviors under the two auction mechanisms.     

What Format for Multi-Unit Multiple-Bid Auctions?

This paper uses computational experiments where bidders learn over nonlinear bidding strategies to compare outcomes for alternative pricing format for multi-unit multiple-bid auctions. Multi-unit multiple-bid auctions, in which bidders are allowed to submit multiple price-quantity bids, are promising mechanisms for the allocation of a range of resources. The main advantage of such auctions is to avoid the lumpy bid problem which arises when bidders can only compete on the basis of one bid. However, there is great uncertainty about the best auction formats when multi-unit auctions are used. The theory can only supply the expected structural properties of equilibrium strategies and the multiplicity of potential equilibria makes comparisons across auction formats difficult. Empirical studies and experiments have improved our knowledge of multi-unit auctions but they remain scarce and most experiments are restricted to two bidders and two units. Moreover, they demonstrate that bidders have limited rationality and learn through experience. This paper constructs an agent-based computational model of bidders to compare the performance of alternative procurement auction formats under circumstances where bidders submit continuous bid supply functions and learn over time to adjust their bids in order to improve their net incomes. The setting is for independent private values. We show that bidding behaviour displays more interesting patterns than is depicted in the theoretical literature and that bidding patterns depend on the interplay between heterogeneity in the bidder population and the degree of rationing in the auction. Results indicate that the three auction formats have similar performance for most levels of competition but that their performances differ when competition is weak. This ranking is dependent on whether the population of bidders is homogenous or heterogeneous.     

A non-parametric estimator for setting reservation prices in procurement auctions

Electronic auction markets collect large amounts of auction field data. This enables a structural estimation of the bid distributions and the possibility to derive optimal reservation prices. In this paper we propose a new approach to setting reservation prices. In contrast to traditional auction theory we use the buyer’s risk statement for getting a winning bid as a key criterion to set an optimal reservation price. The reservation price for a given probability can then be derived from the distribution function of the observed drop-out bids. In order to get an accurate model of this function, we propose a nonparametric technique based on kernel distribution function estimators and the use of order statistics. We improve our estimator by additional information, which can be observed about bidders and qualitative differences of goods in past auctions rounds (e.g. different delivery times). This makes the technique applicable to RFQs and multi-attribute auctions, with qualitatively differentiated offers.     

Improving the Performance of Online Auctions Through Server-side Activity-based Caching

Online auction sites have very specific workloads and user behavior characteristics. Previous studies on workload characterization conducted by the authors showed that (1) bidding activity on auctions increases considerably after 90% of an auction’s life time has elapsed, (2) a very large percentage of auctions have a relatively low number of bids and bidders and a very small percentage of auctions have a high number of bids and bidders, (3) prices rise very fast after an auction has lasted more than 90% of its life time. Thus, if bidders are not able to successfully bid at the very last moments of an auction because of site overload, the final price may not be as high as it could be and sellers, and consequently the auction site, may lose revenue. In this paper, we propose server-side caching strategies in which cache placement and replacement policies are based on auction-related parameters such as number of bids placed or percent remaining time till closing time. A main-memory auction cache at the application server can be used to reduce accesses to the back-end database server. Trace-based simulations were used to evaluate these caching strategies in terms of cache hit ratio and cache efficiency. The performance characteristics of the best policies were then evaluated through experiments conducted on a benchmark online auction system.     

一种保护标价安全的电子拍卖方案

电子拍卖的一个热点问题是保护标价的秘密性，因为存在第三方不可信任或相互勾结．提出了一个实用的保护标价安全的电子拍卖方案，除了中标价以外，它在任何勾结攻击情况下都能保证投标者标价的秘密性，可以公开验证中标价的正确性，效率远远高于最近Brandt提出的方案．其实现只需要O（log2υ）轮通信，其中υ是标价的范围．投标者注册使用数字签名后能保证协议的不可伪造性、抗重放攻击性和不可否认性．协议中使用零知识证明的安全性保证了系统的鲁棒性．     

Visualizing combinatorial auctions

We propose a novel scheme to visualize combinatorial auctions; auctions that involve the simultaneous sale of multiple items. Buyers bid on complementary sets of items, or bundles, where the utility of securing all the items in the bundle is more than the sum of the utility of the individual items. Our visualizations use concentric rings divided into arcs to visualize the bundles in an auction. The arcs’ positions and overlaps allow viewers to identify and follow bidding strategies. Properties of color, texture, and motion are used to represent different attributes of the auction, including active bundles, prices bid for each bundle, winning bids, and bidders’ interests. Keyframe animations are used to show changes in an auction over time. We demonstrate our visualization technique on a standard testbed dataset generated by researchers to evaluate combinatorial auction bid strategies, and on recent Federal Communications Commission (FCC) auctions designed to allocate wireless spectrum licenses to cell phone service providers.     

Bidding strategies for realistic multi-unit sealed-bid auctions

When autonomous agents decide on their bidding strategies in real world auctions, they have a number of concerns that go beyond the models that are normally analyzed in traditional auction theory. Oftentimes, the agents have budget constraints and the auctions have a reserve price, both of which restrict the bids the agents can place. In addition, their attitude need not be risk-neutral and they may have uncertainty about the value of the goods they are buying. Some of these issues have been examined individually for single-unit sealed-bid auctions. However, in this paper, we extend this analysis to the multi-unit case, and also analyze the multi-unit sealed-bid auctions in which a combination of these issues are present, for unit-demand bidders. This analysis constitutes the main contribution of this paper. We then demonstrate the usefulness in practice of this analysis; we show in simulations that taking into account all these issues allows the bidders to maximize their utility. Furthermore, using this analysis allows a seller to improve her revenue, i.e. by selecting the optimal reserve price and auction format.     

Doing their bidding: An empirical examination of factors that affect a buyer’s utility in Internet auctions

What factors make individual bidders pay more or less for the same item in online auctions? We use data on over 55,000 bids over a three-year period collected by a customized Internet software agent. These data are used to perform a within-bidders quasi-experiment, testing bidders who bid on the exact same item at different times during a 30-day period in online auctions. With theories from information systems and consumer behavior as our theoretical lens, we then examine factors that make individuals pay more for the exact same item in online auctions. We find that the same individual will tend to pay more for items sold on a weekend, for items with a picture, and for items sold by experienced sellers. We also find that the same individual is willing to pay more for the same item if others express an interest in that item, exhibiting a type of herd effect. Our results are generalizable to other auctions, and shed light on electronic commerce sales in general, where firms try to sell products for the highest possible price.     

Competitive analysis of incentive compatible on-line auctions

This paper studies auctions in a setting where the different bidders arrive at different times and the auction mechanism is required to make decisions about each bid as it is received. Such settings occur in computerized auctions of computational resources as well as in other settings. We call such auctions, on-line auctions.

We first characterize exactly on-line auctions that are incentive compatible, i.e. where rational bidders are always motivated to bid their true valuation. We then embark on a competitive worst-case analysis of incentive compatible on-line auctions. We obtain several results, the cleanest of which is an incentive compatible on-line auction for a large number of identical items. This auction has an optimal competitive ratio, both in terms of seller's revenue and in terms of the total social efficiency obtained.     

一种匿名的高效M＋1电子拍卖

为了实现投标者的身份匿名,给出了一个基于RSA函数的M 1电子拍卖方案,任何投标者不能否认所投的标书,未中标价不会被泄露.该方案执行开标算法至多需要P轮交互,至多2p log2t次模乘法运算,其中P是标价的个数,t是RSA公钥.计算量与投标者的数量无关,方案安全、高效,远高于现有拍卖方案的效率.     

Maximizing sellers’ welfare in online auction by simulating bidders’ proxy bidding agents

This paper presents an agent-based simulation model to estimate the effects of auction parameters on the auction outcomes, and to find an optimal or, at least, a near-optimal infrastructure. In particular, this study intends to study how bidders’ personalities and bidding strategies with other auction parameters affect the closing prices in two auction mechanisms: English and Yankee auction. Experimental results show that the aggregated outcome of multiple English auctions is more favorable to auctioneers and sellers than that of a corresponding single Yankee auction. It is also shown that raising minimum bid increment or bid starting price positively affects the closing prices in both auction types. However, two auction systems respond differently to the changes in parameter values in terms of magnitude and robustness. Further, it is noted that the closing price of an auction is negatively related to the proportion of risk-takers who adopt sniping strategy to submit their bids. As the proportion of risk-takers increases, the closing price significantly decreases in hard-ending auctions (eBay-like system), but only marginally in soft-ending auctions (Amazon-like system). In particular, soft-ending auctions with less snipers and a longer time window of automatic extension return the most favorable closing price to sellers.     

一个新的分布式安全电子拍卖协议

基于Shamir的（t＋1,n）门限方案和公钥加及数字签名提出一个适于分布式松耦合发布／预约系统使用的安全电子拍卖协议。协议除满足了安全分布式拍卖的基本需求外,还保证了代理拍卖服务器的不可否认性及投标者的匿名性。与先前工作相比,新协议具有较多的安全特性,而且更适合于分布式大规模拍卖。松耦合发布预约结构广泛使用于可扩展 自适应的分布式系统中,它的灵活性使之为许多应用所采用。但是,在不安全的通信环境中,这种结构缺乏容错性和安全支持,新协议可以在分布式松耦合发布／预约系统中实现安全性和容错性,同时具有适当的运行效率。最后,我们对协议设计的正确性和效率进行了详尽分析。     

Using Economic Theory to Guide Numerical Analysis: Solving for Equilibria in Models of Asymmetric First-Price Auctions

In models of first-price auctions, when bidders are ex ante heterogeneous, deriving explicit equilibrium bid functions is typically impossible, so numerical methods are often employed to find approximate solutions. Recent theoretical research concerning asymmetric auctions has determined some properties these bid functions must satisfy when certain conditions are met. Plotting the relative expected pay-offs of bidders is a quick, informative way to decide whether the approximate solutions are consistent with theory. We approximate the (inverse-)bid functions by polynomials and employ theoretical results in two ways: to help solve for the polynomial coefficients and to evaluate qualitatively the appropriateness of a given approximation. We simulate auctions from the approximated solutions and find that, for the examples considered, low-degree polynomial approximations perform poorly and can lead to incorrect policy recommendations concerning auction design, suggesting researchers need to take care to obtain quality solutions.     

Winner's curse and parallel sales channels—Online auctions linked within e-tail websites

A sample of 416 online auctions was examined to determine the extent of overpayment (winner's curse) where online auctions and e-tail websites were linked together to form a parallel sales channel. The results indicated that 8.7% of the highest winning online auction bidders exceeded e-tail posted reference prices of identical retail merchandise found at the same website. Significantly, such bids exceeded the reference prices by a mean percentage dollar amount of 14.1% thus suggesting the existence of a winner's curse. The results also indicated that (1) there was a significant negative association between reference price and mean percentage dollar amount overbid; (2) there was a significant negative association between auction lot size and mean percentage dollar amount overbid; and (3) there was no significant association between overtime auctions and mean percentage dollar amount overbid. While manipulation of reference price and auction lot size might minimize winner's curse, erratic or irrational behavior (by online auction and/or e-tail websites) may lead to disinformation.     

Practical secrecy-preserving,verifiably correct and trustworthy auctions

We present a practical protocol based on homomorphic cryptography for conducting provably fair sealed-bid auctions. The system preserves the secrecy of the bids, even after the announcement of auction results, while also providing for public verifiability of the correctness and trustworthiness of the outcome. No party, including the auctioneer, receives any information about bids before the auction closes, and no bidder is able to change or repudiate any bid. The system is illustrated through application to first-price, uniform-price and second-price auctions, including multi-item auctions. Empirical results based on an analysis of a prototype demonstrate the practicality of our protocol for real-world applications.     

Optimal quota allocation for a revenue-maximizing auction holder facing a random number of bidders

This paper is motivated by the following practical multi‐unit auction. Before purchasing a vehicle in Singapore, a prospective buyer must bid for a certificate that entitles him to purchase the vehicle. Each month a certain number, say Q, of “certificates of entitlement” are made available and the highest Q bidders receive the right to purchase. Each successful bidder pays a “quota premium” equal to the bid submitted by the Qth highest bidder. We construct a stochastic optimization model using results from the theory of order statistics, where the objective is to determine the optimal number of units to be released in order to maximize the auction holders expected revenue. As the amounts bid and the number of bidders are both random, there may be wide – and, undesirable – fluctuations in the quota premia from one month to the next. We perform the optimization subject to a probabilistic constraint that limits the month‐to‐month fluctuations in quota premia. We show, assuming specific distributions for the bid amounts and the number of bidders, that in order to satisfy the probabilistic constraint one may have to reduce the available quota. For different bid random variables, the feasible set arising from the probabilistic constraint may assume different shapes. We also present a sufficient condition for comparing the size of the two feasible sets corresponding to different bid random variables. The results are illustrated by sensitivity analyses that examine the effect of varying parameter values on the optimal solution.     

“Bid more,pay less” – overbidding and the Bidder’s curse in teleshopping auctions

This paper provides a theoretical and empirical analysis of the multi-unit Dutch teleshopping auctions of 1–2–3.tv. There are two channels for sales transactions: Customers either bid in the teleshopping auctions or purchase in the online shop for a simultaneously available fixed price. Our theoretical analysis indicates that profit-maximizing customers do not overbid the fixed price, since they risk experiencing the Bidder’s Curse: Buying at a uniform auction price that is higher than the fixed price. Our data set includes nearly 700,000 recorded bids. We find that customers overbid in 26% of all bids, but the Bidder’s Curse only occurs in 5% of all auctions. Offline-bidders (telephone calls) overbid both by larger amounts and more often than do online-bidders (website or app), and, on average, the most frequent customers do not experience learning effects.