Performance Evaluation of Multi-Object Auctions

The paper evaluates the performance of two multi-object auction models: sequential and simultaneous, using different performance measures. The objects put up for auction have different synergies for different bidders. We define different types of bidders who can exist in these multi-object auction models. The classification of bidders is based on the bidding strategies they use. We then study the effects of different parameters in auction and bidding strategies, on the performance of these auction models by simulating them using a JAVA based framework.This material is based upon work supported by a National Science Foundation grant (DMI 9800449) to the Dharmaraj Veeramani last author. The authors also thank the referees of the paper and the area editors for their valuable comments on the work.     

基于多Agent的多属性拍卖系统研究

通过对现有网上拍卖系统的深入分析,指出多属性网上拍卖系统的研究是最为薄弱的环节。依据网上交易的需求和分布式人工智能迅速发展,提出了一种基于多Agent的多属性网上拍卖系统,着重对多属性拍卖协议和策略,以及系统构架进行了探讨,给出了集成式的多属性网上拍卖系统的算法,并对今后的研究方向进行了展望。     

Optimal reserve prices in weighted GSP auctions

Most search engines use the weighted Generalized Second Price (wGSP) auction to sell keyword-based text ads, generating billions of dollars of advertising revenue every year. Designing and implementing near-optimal reserve prices for these wGSP auctions are naturally important problems for both academia and industry.In this paper, we show how to calculate and implement the near-optimal reserve price of the wGSP mechanism in realistic settings. Unlike reserve prices in standard single-item auctions, optimal reserve prices in wGSP auctions are discriminatory, different even for advertisers bidding on the same keyword. The optimal reserve price results can be extended to support CPA/CPC/CPM¹ hybrid auctions.Our simulations indicate that setting a proper reserve price will transfer some bidder utility (payoff) to auctioneer utility, resulting in higher revenue for the search engine. We describe a practical methodology to implement optimal reserve prices in production systems.     

网上逆向拍卖系统vAuc的设计与实现

vAuc系统是为日本一会社开发的基于Internet环境下的逆向拍卖系统。介绍了逆向拍卖的基本思想,详细叙述了vAuc系统的设计过程,并给出了vAuc系统的几个关键的实现技术。     

基于代理竞拍网站的同步竞拍技术研究与实现

网络竞拍作为电子商务的一种交易形式,已经发展得十分成熟。人们不再局限于参与本国的网络竞拍,而是越来越多地通过网络参与各国知名竞拍网站的竞拍。由于种种原因,导致跨国度竞拍难以实现,于是出现了代理竞拍网站,而同步竞拍技术是实现代理竞拍网站的核心。提出一种解决问题的网络模型,使用HttpClient抓取竞拍网站页面的数据,保证信息的实时性、减少系统数据库的开销;通过修改优化Web应用测试工具Selenium,服务器端低开销地自动完成在目标竞拍网站出价的操作,从而实现同步竞拍。该模型具有更好的兼容性、通用性和稳定性。     

一个利用群签名的电子拍卖协议

利用群签名与可验证的秘密共享方案设计了一个新的密封投标的电子拍卖协议。在该协议中,多个拍卖者共同主持拍卖过程,所有的拍卖者通过可验证的秘密共享方案共享一个密钥,这使得投标者在投标时只需要一次加密,其计算量与拍卖者的数量无关;另外,中标者的身份是由群管理者根据中标者对投标消息的签名来确定的,所以一次注册后,投标者可同时参加多个拍卖活动,而不会泄露自己的身份。     

Efficient anonymous auction protocols with freewheeling bids

The need for electronic auction services has been increasing in recent years. Taking security into account, anonymity of online bidders becomes more important than it used to be. However, bidders cannot bid of his/her free will in existing anonymous auction protocols. For real-time applications, time delays are the significant factor taken into account. As a result, the proposed paper presents a simple and efficient method to ensure that the bidders can bid arbitrarily and anonymously.     

Walrasian Equilibrium: Hardness,Approximations and Tractable Instances

We study the complexity issues for Walrasian equilibrium in a special case of combinatorial auction, called single-minded auction, in which every participant is interested in only one subset of commodities. Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004) showed that it is NP-hard to decide the existence of a Walrasian equilibrium for a single-minded auction and proposed a notion of approximate Walrasian equilibrium called relaxed Walrasian equilibrium. We show that every single-minded auction has a relaxed Walrasian equilibrium that satisfies at least two-thirds of the participants, proving a conjecture posed in Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004). Motivated by practical considerations, we introduce another concept of approximate Walrasian equilibrium called weak Walrasian equilibrium. We show NP-completeness and hardness of approximation results for weak Walrasian equilibria. In search of positive results, we restrict our attention to the tollbooth problem (Guruswami et al. in Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 1164–1173, 2005), where every participant is interested in a single path in some underlying graph. We give a polynomial time algorithm to determine the existence of a Walrasian equilibrium and compute one (if it exists), when the graph is a tree. However, the problem is still NP-hard for general graphs.     

Bidding strategies in online single-unit auctions: Their impact and satisfaction

Online bidders use different strategies in their biddings. However, we are unsure of the bidders strategies and their effectiveness in achieving auction goals. Our study was an attempt to identify bidding strategies empirically in online single-unit auctions and evaluate their outcome in terms of cost saving, perceived bidder enjoyment, and bidder satisfaction. A research model was developed and used to examine the relationships. Both objective and subjective data of online single-unit auctions were collected from Taobao.com to validate our postulated hypotheses. We found three main bidding strategies: early, snipe, and agent-supported ratchet bidding based on their behavior patterns. These resulted in different levels of winning outcome and cost saving, but had no significant effect on perceived enjoyment. The hypotheses of the relationship between auction outcomes and bidder satisfaction of their bidding strategies were confirmed.     

A secure multi-item e-auction mechanism with bid privacy

The recent focus within the auction field has been multi-item auctions where bidders are not restricted to buying only one item of the merchandise. It has been of practical importance in Internet auction sites and has been widely executed by them. In this paper, we concentrate on the use of the multi-item auction for task assignment scenarios and propose a novel PUPA auction protocol to solve the problem of bid privacy in multi-item auctions. A verifiable technique of shared key chain is proposed to find the winners without revealing the losing bid and bidder’s privacy. It can be shown that our new scheme is robust against cheating bidders.     

一种安全的多属性拍卖模型

网络拍卖不仅成为电子商务不可分割的部分,而且是自治Agent和多Agent系统(MAS)技术的重要应用领域.同时,拍卖作为一种有效的资源分配形式,在联盟生成等MAS问题中有着重要的应用,因而受到学者们越来越多的关注.拍卖的安全性、隐私性特征是拍卖研究的重要方面.给出了一个一般的多属性拍卖模型和一个安全的多属性拍卖协议--SVAMA协议,并证明了SVAMA的一些重要性质,如Strategy-proof等.并与已有的多属性拍卖和使用的安全方法进行了比较,部分改进了David,Brandt等人的工作.     

Resource trading in cloud environments for utility maximisation using game theoretic modelling approach

We develop a novel auction-based scheme for trading free processors in cloud computing environment. Our scheme allows clients to fairly compete for the offered processors. Second-price auction is used where each client bids for the processors. The client that makes the higher bid wins the auction and starts using the processors for executing its jobs. The winner pays the second highest bid. Maximising profit is the key objective for the cloud provider (CP). The optimisation problem of renting processors on the cloud market is a complex and challenging task. The proposed mechanism takes into account the market demand and the economic concerns for the CP and clients. Within this context, we show the existence of a Nash equilibrium which leads to a unique allocation under certain processors distribution. Numerical analysis stresses the ability of our approach to maximise the client's utility under varying cloud environment conditions.     

一种暗标叫价的多属性拍卖方法

分析了已有的多属性拍卖方法中存在的问题,给出了一种广义的多属性拍卖模型．进而提出了一种暗标叫价多属性拍卖方法——MAV,并证明了MAV的一些重要性质,如卖方激励相容性等,还给出了卖方的占优策略和买方的Bayes最优策略．论证了MAV中的买卖方总效用在Bayes均衡点上达到最大．最后与已有的多属性拍卖方法进行了比较,结果表明MAV改进了Esther等人的工作．     

群智感知中基于反拍卖模型的众包激励方法

激励是实现群智感知（CS）众包服务的主要方法,针对现有方法在服务过程中没有充分考虑节点参与数量和恶意竞争对群智感知带来的影响,提出一种基于反拍卖模型的激励（RVA-IM）方法。首先,研究众包的激励机制,结合反拍卖与Vickrey拍卖思想,构建面向任务覆盖的反拍卖模型;其次,对模型中涉及的任务覆盖、反拍卖选择和奖励实施等关键技术问题进行深入分析与研究;最后,从计算有效、个人理性、预算平衡、真实性和诚实性五个方面分析RVA-IM激励方法的有效性。实验结果表明,与IMC-SS和MSensing激励方法相比,RVA-IM在有效性和可行性方面均有较好的表现,能够解决现有方法中的恶意竞争问题,并能够平均提升众包服务完成率约21%。     

基于环签名的电子拍卖方案

在拍卖过程中如何保护投标者隐私和身份以及防止中标者反悔是设计安全电子拍卖系统的关键技术.该方案满足投标者的无条件匿名性、健壮性、中标者的不可抵赖性和公开验证性等一般安全性要求外,对可信第三方的依赖小,安全性高.基于环签名技术,提出了一种电子拍卖方案.     

无收据的密封式电子拍卖协议

提出一个高效的无收据密封式电子拍卖协议，无收据的意义是在协议进行过程中没有可以作为“收据”的公开数据，从而能够更好地保证竞拍者的安全。与现有的无收据密封式电子拍卖协议相比，该文的协议在竞拍价格变化较大的情况下，效率有很大的提高。     

基于蜂群算法的多属性反向拍卖中供应商投标策略模型

为了确定多因素多组合投标环境下当前供应商的最佳投标策略,给出一种多属性反向拍卖中供应商投标策略模型。该模型分析了竞争供应商的投标策略和获胜者确定规则,着重将人工蜂群算法的优化流程与当前供应商的决策过程相结合,根据竞争供应商的投标策略计算其成本函数,利用人工蜂群算法进行探索,得到当前投标组合下一轮最优投标策略。仿真实验表明,该模型在动态变化的投标过程中能快速高效求得当前供应商每一个投标组合的最优投标策略。     

网上拍卖的风险防范机制及其发展研究

网络经济的发展促使电子商务得到快速应用,而网上拍卖是电子商务中最成功的一种形式。网上拍卖有着传统拍卖所没有的一些优点。随着计算机技术和网络技术的发展,网上拍卖日益广泛与深入,同时也使得网上拍卖系统的风险问题日益突出。本文考虑的就是通过建立一些风险防范机制来降低网上拍卖的风险。     

基于间隔型双边拍卖的网格资源预留算法

针对已有基于竞价拍卖的网格资源预留方法存在的问题，提出了一种基于间隔型双边拍卖的网格资源预留算法。根据网格资源预留的需求和拍卖机制的特点，给出了网格系统模型；基于间隔型双边拍卖的思想，设计了适合网格系统的资源拍卖机制，给出了详细的网格资源预留算法；算法的最优性分析表明：在资源拍卖过程，提供真实信息对用户方和资源方均是唯一占优策略，且算法能够保证中标资源供需平衡。 最后，模拟实验结果证明了算法的有效性和正确性。     

多Agent协商领域中的拍卖

协商是多Agent研究领域的热点方向,对策论是目前多Agent协商领域研究的主要方法之一,而拍卖属于对策论研究范畴。总结了多Agent协商领域中一些重要的拍卖形式,并给出了拍卖过程的模型和一般的算法流程。