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.     

一种新的基于代理缓存的流媒体分送策略

提出了一种新的带缓存的补丁调度策略,有效地将代理缓存与服务器调度技术结合起来,采用基于缓存窗口自适应伸缩的缓存分配方案,实现了流媒体对象在代理服务器中缓存的数据段数与其流行度成正比的原则。理论分析及实验结果表明,该策略有效地降低了服务器及骨干网络带宽资源的消耗,对于客户请求到达速率的变化具有非常好的适应性。     

IntelliBid: An Event-Trigger-Rule-Based Auction System over the Internet

This paper presents the design and implementation of an Event-Trigger-Rule-Based auction system called IntelliBid. A network of Knowledge Web Servers, each consisting of a Web server, an Event-Trigger-Rule (ETR) Server, an Event Engine, a Knowledge Profile Manager, and Bid Servers and their proxies constitutes IntelliBid. Together, they provide auction-related services to the creator of an auction site and the bidders and suppliers of products. IntelliBid offers a number of desirable features. First and foremost is the flexibility offered to bidders for defining their own rules to control their bids in an automatic bidding process, which frees the bidders from having to be on-line to place bids. By using different rules, the bidders can apply different bidding strategies. Second, it furnishes valuable statistical information about past auctions to both suppliers (or sellers) and bidders. The information can assist a bidder in bidding and a seller in setting a reasonable base price and/or the minimum incremental price. Third, since rules that control the automatic bidding are installed and processed by the ETR servers installed at bidders' individual sites, bidders' privacy and security are safeguarded. The statistical information that is released by IntelliBid only depicts the trend of the bidding prices of a product. The information about bidders is kept completely secret, thus safeguarding the privacy of the bidders. Fourth, IntelliBid's event, event filtering and event notification mechanisms keep both bidders and suppliers timely informed of auction events so that they or their software system can take the proper actions in the auction process. Fifth, any registered user of IntelliBid, bidder or supplier, can monitor the bids placed to any product being auctioned in IntelliBid. Sixth, IntelliBid allows bidders to do both on-line (or manual) bidding and automatic bidding. It also allows a bidder to participate in several auctions at the same time, in both manual and automated modes. The bidding of a product can depend on the result of the bidding of another product. Last, but not least, IntelliBid allows a person or organization to play both the role of bidder and the role of supplier simultaneously. The Profile Manager keeps the information as a bidder and information as a supplier separately. Moreover, IntelliBid's architecture uses a parallel event management system to do event registration and notification. This paper also reports the result of a performance study on the implication of using such a parallel system to achieve scalability.     

一种基于两级缓存的协同缓存机制

信息中心网络（information-centric networking,简称ICN）将网络通信模式从当前的以地址为中心转变为以信息为中心.泛在化缓存是ICN重要特性之一,它通过赋予网络任意节点缓存的能力来缓和服务器的压力,降低用户访问延迟.然而,由于缺少内容热度的分布感知,现有ICN缓存策略仍存在缓存利用率较低、缓存位置缺乏合理规划等问题.为了解决这些问题,提出一种基于两级缓存的协同缓存机制（a cache coordination scheme based on two-level cache,简称CSTC）.将每个节点的缓存空间分为热度感知和协作分配两部分,为不同热度的内容提供不同的缓存策略.同时,结合提出的热度筛选机制和路由策略,降低了缓存冗余,实现了缓存位置优化.最后,基于真实网络拓扑的仿真实验表明,CSTC在次热门内容缓存数量上提升了2倍,缓存命中率提升了将近50%,且平均往返跳数在多数情况下优于现有On-path缓存方式.     

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.     

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     

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.     

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.     

一种淘汰式无拍卖行的电子拍卖

在所有的封闭式电子拍卖中存在的一个共同的缺陷结点(tie)问题，即几个投标者同时投了最高价，由于存在着结点严重地影响了拍卖的效率。基于shamir的(t，n)门限体制提出了一种淘汰式无拍卖行的匿名电子拍卖，采用无拍卖行且每个投标者的标价在投标者之间分享实现标价的匿名性的同时，提出了一种淘汰式拍卖解决结点问题，从而使拍卖的效率得到了提高。     

A theoretical and empirical investigation of multi‐item on‐line auctions

In this paper we explore and analyze the structure of Internet auctions from an analytical and an empirical perspective. Such web‐based auctions are rapidly emerging as a mercantile process of choice in the electronic marketplace. We observe current Internet auctions for one‐time products, such as rapidly aging hardware, and analyze them within the framework of the existing auction theory. While traditional auction theory focuses on single‐item auctions, we observe that a majority of on‐line auctions are multi‐item auctions. A significant contribution of this work is the theoretical derivation of the structure of the winning bids in multi‐item progressive on‐line auctions. Additionally, for comparative purposes, we explore the structural characteristics of alternative multi‐item auction mechanisms proposed in the auction theory. We derive hypotheses based on our analytical results and compare two different types of auction mechanisms. We test the traditional auction theory assumption regarding the homogeneity of bidders and present the first ever empirically derived classification and performance‐comparison of on‐line bidders. We test our hypotheses using real‐world empirical data obtained by tracking a premier web‐based auction site. Statistical analysis of the data indicates that firms may gain by choosing alternative auction mechanisms. We also provide directions for further exploration of this emerging but important dimension of electronic commerce. This revised version was published online in July 2006 with corrections to the Cover Date.     

P2P网络中的代理拍卖协议

提出一个点对点（P2P）网络中的二价代理拍卖协议。投标者在投放出价链之后即可自由进出协议,由P2P节点代理完成拍卖;在整个拍卖过程中,低的出价链会在未被完全解密的状态下先被淘汰,最后只留下最高出价链。与已有的其他协议相比,它兼具密闭拍卖和分布式拍卖的优点,不仅能做到异步出价,而且能保护所有出价者的出价隐私。     

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.     

User-assisted in-network caching in information-centric networking

In information-centric networking, in-network caching has the potential to improve network efficiency and content distribution performance by satisfying user requests with cached content rather than downloading the requested content from remote sources. In this respect, users who request, download, and keep the content may be able to contribute to in-network caching by sharing their downloaded content with other users in the same network domain (i.e., user-assisted in-network caching). In this paper, we examine various aspects of user-assisted in-network caching in the hopes of efficiently utilizing user resources to achieve in-network caching. Through simulations, we first show that user-assisted in-network caching has attractive features, such as self-scalable caching, a near-optimal cache hit ratio (that can be achieved when the content is fully cached by the in-network caching) based on stable caching, and performance improvements over in-network caching. We then examine the caching strategy of user-assisted in-network caching. We examine three caching strategies based on a centralized server that maintains all content availability information and informs each user of what to cache. We also examine three caching strategies based on each user’s content availability information. We first show that the caching strategy affects the distribution of upload overhead across users and the number of cache hits in each segment. One interesting observation is that, even with a small storage space (i.e., 0.1% of the content size per user), the centralized and distributed approaches improve the cache hit ratio by 50% and 45%, respectively. With an overall view of caching information, the centralized approach can achieve a higher cache hit ratio than the distributed approach. Based on this observation, we discuss a distributed approach with a larger view of caching information than the distributed approach and, through simulations, confirm that a larger view leads to a higher cache hit ratio. Another interesting observation is that the random distributed strategy yields comparable performance to more complex strategies.     

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.     

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

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

Exploiting Regularities in Web Traffic Patterns for Cache Replacement

Abstract. Caching web pages at proxies and in web servers' memories can greatly enhance performance. Proxy caching is known to reduce network load and both proxy and server caching can significantly decrease latency. Web caching problems have different properties than traditional operating systems caching, and cache replacement can benefit by recognizing and exploiting these differences. We address two aspects of the predictability of traffic patterns: the overall load experienced by large proxy and web servers, and the distinct access patterns of individual pages. We formalize the notion of ``cache load' under various replacement policies, including LRU and LFU, and demonstrate that the trace of a large proxy server exhibits regular load. Predictable load allows for improved design, analysis, and experimental evaluation of replacement policies. We provide a simple and (near) optimal replacement policy when each page request has an associated distribution function on the next request time of the page. Without the predictable load assumption, no such online policy is possible and it is known that even obtaining an offline optimum is hard. For experiments, predictable load enables comparing and evaluating cache replacement policies using partial traces , containing requests made to only a subset of the pages. Our results are based on considering a simpler caching model which we call the interval caching model . We relate traditional and interval caching policies under predictable load, and derive (near)-optimal replacement policies from their optimal interval caching counterparts.     

基于区域划分的混合式NDN缓存策略

针对NDN(命名数据网络)中确定性缓存和概率性缓存各自特点,提出一种确定性缓存和概率性缓存相结合的混合式NDN缓存策略(HDP)。基于区域划分的思想,在网络边缘采用基于热度的确定性缓存策略,在网络核心采用基于缓存收益和内容热度的概率性缓存策略,从而将两种缓存策略的优势相结合,进一步提高NDN缓存性能。实验表明该策略与现有NDN缓存方法相比,能有效提高缓存服务率和命中率,并有助于降低内容访问延迟,改善用户体验。     

Two-level workload characterization of online auctions

Online auctions are rapidly becoming one of the significant forms of electronic commerce for buying and selling goods and services. A good understanding of the workload of auction sites should provide insights about their activities and help in improving the quality of the service provided to their users. This paper presents a site level and a user level workload characterization of a real online auction site using data collected by automated agents. The main contributions of this paper are as follows: (i) a detailed workload characterization of a real auction site; (ii) an analysis of the presence of heavy tailed distributions in this workload; (iii) an analysis of the bidding activity during closing minutes of auctions; and (iv) an analysis of the arrival rate process of bidders and bids within clusters based on different attributes. These results can be used to devise dynamic pricing and promotion models to improve revenue throughput of online auction sites.     

Bidding strategies for real-life small loan auctions

We define and identify bidding strategies in real-life small loan auctions (Prosper.com). In such auctions, lenders bid for borrowers' loan listings and the winners get to fund the loan at an interest rate determined by the auction. The exceptionally large empirical database provided by Prosper.com offers a unique opportunity to test and further develop the theory of online auctions. This study shows that bidding behavior is not homogeneous among bidders, as the traditional auction theory suggests. Instead, bidders use many different bidding strategies. Moreover, learning and bidders' consistency over time in different auctions is studied.     

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

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