Auction design with costly preference elicitation

We consider auction design in a setting with costly preference elicitation. Well designed auctions can help to avoid unnecessary elicitation while determining efficient allocations. Careful design can also lead to more efficient outcomes when elicitation is too costly to permit perfect allocative efficiency. An incremental revelation principle is developed and used to motivate the role of proxied and indirect auction designs. Proxy agents, situated between bidders and an auction, can be used to maintain partial information about bidder preferences, to compute equilibrium bidding strategies based on the available information, and to elicit additional preference information as required. We derive information-theoretic elicitation policies for proxy agents under a simple model of costly elicitation across different auction designs. An experimental analysis demonstrates that indirect mechanisms, such as ascending-price auctions, can achieve better allocative efficiency with less preference elicitation than sealed-bid (direct) auctions because they promote better decisions about preference elicitation.A preliminary version of this paper appeared in the Proc. of the IJCAI’99 Workshop on Agent Mediated Electronic Commerce.     

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.     

Cheating in online auction – Towards explaining the popularity of English auction

Action frauds constitute largest part of all Internet frauds. Cheating is a kind of fraud that does not have direct evidences of its occurrence. We conduct theoretical studies as well as simulation experiments to find out the effect of cheating in three important types of auctions: English auction, first-price sealed-bid, and second-price sealed-bid auction. Our cheating environment consists of shill bidding, bid shading and false bidding in English, first-price and second-price auction, respectively. In the experiments ordinary bidders, bidders with the equilibrium bidding strategy, and cheaters compete with each other. Both theoretical and experimental results confirm that the equilibrium bidding strategies indeed increases the bidders’ expected utility. Therefore, it can be concluded that adoption of rational bidding strategies can combat cheating. It is found that most of the auction sites intuitively prefer English auction to other auction mechanisms. There is not much theoretical or experimental evidence to support such an intuition. We use honest bidder’s expected gain and honest seller’s revenue loss as a basis to compare these three important auctions types. The analysis of the results reveals English auction to be the most preferred mechanism from both honest buyer’s and honest seller’s point of view. This result can be used as an experimental evidence to explain the popularity of English auction over the Internet.     

Real time prediction of closing price and duration of B2B reverse auctions

Nowadays, online auctions have become the most successful business model in the electronic marketplace. To the best of the authors’ knowledge, no other work has been devoted to the prediction of closing price and duration of Business-to-Business (B2B) English reverse online auctions in which goods or service providers compete with each other to win contracts by lowering offering prices with each bid, which is conducted on a virtual platform hosted on the Internet. This research designs and proposes a new methodology to predict closing prices and duration within the first few bids of the corresponding auctions based on real time bidding information rather than static auction information. In this article, we employ real time information and prediction rules to forecast the behavior of live auctions. This is in contrast to the static prediction approach that takes into consideration only information available at the beginning of an auction such as products, item features, or the seller’s reputation. This simulation is based on discretized auction data derived from a B2B online auction marketplace over a two-year period. Three measurements including accuracy, coverage, and benefit are used to evaluate the methodology. Results show that after observing the first 4 bids, this methodology can predict closing prices and duration with 84.6 and 71.9% accuracy, respectively.     

Assessing the benefits of group-buying-based combinatorial reverse auctions

Combinatorial reverse auctions represent a popular business model in procurement. For multiple buyers, different procurement models based on combinatorial reverse auctions may be applied. For example, each buyer may hold one combinatorial reverse auction independently. Alternatively, the buyers may delegate the auction to a group-buyer and let the group-buyer hold only one combinatorial reverse auction on behalf of all the buyers. A combination of a combinatorial reverse auctions with the group-buying model makes it possible to reduce the overall cost to acquire the required items significantly due to complementarities between items. However, combinatorial reverse auctions suffer from high computational complexity. To assess the advantage of combining group-buying with combinatorial reverse auctions, three issues must be addressed, including performance, computational efficiency and the scheme to reward the buyers. This motivates us to compare the performance and efficiency of the aforementioned two different combinatorial reverse auction models and to study the possible schemes to reward the buyers. To achieve these objectives, we first illustrate the advantage of group-buying-based combinatorial reverse auctions over multiple independent combinatorial reverse auctions. We then formulate the problems for these two combinatorial reverse auction models and propose solution algorithms for them. We compare performance and computational efficiency for these two combinatorial reverse auction models. Our analysis indicates that a group-buying-based combinatorial reverse auction not only outperforms multiple independent combinatorial reverse auctions but also is more efficient than multiple independent combinatorial reverse auctions. We also propose a non-uniform scheme to reward the buyers in group-buying based combinatorial reverse auctions.     

A secure reverse Vickrey auction scheme with bid privacy

In recent years auctions have become more and more important in the field of multi-agent systems as useful mechanisms for resource allocations, task assignments and electronic commerce. In this paper, we concentrate on the use of the reverse Vickrey auction for task assignment scenarios and propose a novel RVP auction protocol as a method to solve problems to bid privacy in reverse Vickrey auctions. A verifiable technique of encryption key chain is used to find the second lowest bid without revealing the losing bid and unnecessary information. Through analysis, it is verified that our new scheme is robust against cheating bidders.     

A Multi-attribute bidding strategy for a single-attribute auction marketplace

Auctions and negotiations are important mechanisms of economic exchange. Negotiations are less structured as they involve exchange of offers by both parties. They may involve several issues and new issues can be added in the course of negotiations. Auctions, on the other hand are highly structured, and thus they are much amenable to automation. However, most existing auctions involve bidding on a single issue (price). This is an obvious limitation as participants may have different preferences over multiple attributes of a given type of product or service. This paper proposes an approach by which a software agent solution could effectively implement a multi-attribute bidding strategy for single-attribute auction marketplaces. This allows to significantly expand the set of potential auctions to bid on, while assuring the minimum utility level for the bidder at a given point in time. The bidding model is based upon concession-making curve introduced in prior work on electronic negotiations. Using data collected from eBay the paper shows that bidding across several attributes would result in higher utility outcome, and faster results than bidding within a single attribute set.     

DECLARATIVE SPECIFICATION OF FAULT TOLERANT AUCTION PROTOCOLS: THE ENGLISH AUCTION CASE STUDY

Auction mechanisms are nowadays widely used in electronic commerce Web sites for buying and selling items among different users. The increasing importance of auction protocols in the negotiation phase is not limited to online marketplaces. In fact, the wide applicability of auctions as resource‐allocation and negotiation mechanisms have also led to a great deal of interest in auctions within the agent community. A challenging issue for agents operating in open Multiagent Systems (such as the emerging semantic Web infrastructure) concerns the specification of declarative communication rules which could be published and shared allowing agents to dynamically engage well‐known and trusted negotiation protocols. To cope with real‐world applications, these rules should also specify fault tolerant patterns of interaction, enabling negotiating agents to interact with each other tolerating failures, for instance terminating an auction process even if some bidding agents dynamically crash. In this paper, we propose an approach to specify fault tolerant auction protocols in open and dynamic environments by means of communication rules dealing with crash failures of agents. We illustrate these concepts considering a case study about the specification of an English Auction protocol which tolerate crashes of bidding agents and we discuss its properties.     

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.     

Operational efficiency of decentralized Internet auction mechanisms

The recent consumer-to-consumer (C2C) Internet auction boom at eBay, Yahoo, Amazon, and other sites has added new theoretical challenges to the science of auctions. This paper uses experiments with economically-motivated human subjects to measure the operational efficiency of decentralized Internet auction mechanisms as they compare to centralized double auction mechanisms. Subjects are recruited randomly from the undergraduate population of a large urban university to be buyers or sellers in a simulated trading environment. They are randomly assigned costs and values for 10 units of a virtual product. During the experiment subjects trade these units through computer terminals in auctions similar to those held on eBay and generate profits, which subjects receive at the end of the experiment. The paper uses data from this experiment and previous laboratory experiments to compare operational efficiency and convergence pattern of prices to equilibrium levels in continuous double auctions versus online Internet auctions based on two variables: auction size and time. Experimental results suggest that, because of their decentralized nature, Internet auctions require a few more participants and more time to achieve operational efficiency levels than centralized markets which use continuous double auction mechanisms.     

Designing Electronic Auctions: An Internet-Based Hybrid Procedure Combining Aspects of Negotiations and Auctions

We discuss design issues pertaining to multiple issue auctions in the WWW environment. Based on a critical evaluation of existing auctions, we propose NegotiAuction^tm, an algorithmic Internet-based auction procedure, which combines certain elements of negotiations and auctions. It can be used either in reverse or forward auctions. When defining a multiple issue (multiple attribute) auction, the auction owner has more control over the bidding process than is possible in traditional auctions, signaling bid requirements to the bidders individually. This will result in a preferred set of auction winners. It is believed to reduce the total transaction time and eliminate the necessity of holding subsequent negotiations with the set of winners.     

An agent-based English auction protocol using Elliptic Curve Cryptosystem for mobile commerce

Rapid development of the Internet and the extensive use of mobile phones have increased demand for mobile devices in Internet auctions. This trend is acting as an incentive to develop an auction model for mobile-based environment. Recently, Kuo-Hsuan Huang proposed a mobile auction agent model (MoAAM), which allows the bidders to participate in online auctions through a mobile agent. He used modular exponentiation operations in his method. As a result, the processing time for key generation, bidding, and verification were long. Thus, we propose to add the concept of Elliptic Curve Cryptosystem (ECC) onto MoAAM, because ECC has low computation amount and small key size, both of which will aid to increase the speed in generating keys, bidding, and verification. In terms of reduction of computation load on mobile devices and auction-manager server, the proposed method will make online auction system more efficient as well as more convenient to use. This paper mainly uses the English auction protocol as the key auction protocol. The protocol consists of four entities: Registration Manager (RM), Agent House (AH), Auction House (AUH), and Bidders (B). The Registration Manager registers and verifies Bidder identity. The Agent House manages the agents and assigns public transaction keys to Bidders. The Auction House provides a place for auction and maintains all necessary operations for a smooth online auction. Bidders are buyers who are interested in purchasing items at the auction. Our proposed method conforms to the requirements of an online auction protocol in terms of anonymity, traceability, no framing, unforgetability, non-repudiation, fairness, public verifiability, unlinkability among various auction rounds, linkability within a single auction round, efficiency of bidding, one-time registration, and easy revocation.     

A virtual competition auction model for perishable products

Online auctions for perishable products have tremendous potentials. However, the current forms of online auctions do not take full advantages of information technology enabled online auctions, and are ineffective for online auctions for perishable products. This study proposes a virtual competition auction model for perishable products. In virtual competition auctions, the bidder is provided with auction historical data, and the bidder’s decision is represented by a demand curve that is composed of a series of bids. A preliminary laboratory experiment based on a prototype of virtual competition auction system is reported. The preliminary laboratory experiment result shows that the virtual competition auction model for perishable products is more effective than the ordinary open-cry auction model.     

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.     

The Power of Fair Pricing Mechanisms

We explore the revenue capabilities of truthful, monotone (“fair”) allocation and pricing functions for resource-constrained auction mechanisms within a general framework that encompasses unlimited supply auctions, knapsack auctions, and auctions with general non-decreasing convex production cost functions. We study and compare the revenue obtainable in each fair pricing scheme to the profit obtained by the ideal omniscient multi-price auction. We show that for capacitated knapsack auctions, no constant pricing scheme can achieve any approximation to the optimal profit, but proportional pricing is as powerful as general monotone pricing. In addition, for auction settings with arbitrary bounded non-decreasing convex production cost functions, we present a proportional pricing mechanism which achieves a poly-logarithmic approximation. Unlike existing approaches, all of our mechanisms have fair (monotone) prices, and all of our competitive analysis is with respect to the optimal profit extraction.     

Should we collude? Analyzing the benefits of bidder cooperation in online group-buying auctions

Cooperation among bidders in traditional auctions is typically forbidden. This is because it is viewed as being harmful to the interests of sellers, who hope to obtain fair prices for their sale items. It also may be harmful to other bidders who are not able to take advantage of any cooperation that is occurring. In online group-buying auctions, in contrast to traditional auctions, cooperation results in higher welfare, leading to market expansion that benefits buyers and sellers, as well as the auction intermediary. This has not been well understood in prior research, however. In this article, we show how the online group-buying auction mechanism on the Internet can be effectively enhanced to produce higher welfare for the participants. The key to achieving this, we find, is for the auction intermediary to provide a means for bidders to cooperate, so as to collectively express greater demand. Such cooperation, it turns out, permits the group-buying auction mechanism to dominate the fixed-price mechanism from the seller’s point of view under some circumstances. Through an analytical modeling analysis, we offer insights into how sellers can set their group-buying auction price curves more effectively, so as to take advantage of bidder cooperation to improve auction performance. We further argue that the goal of the auction intermediary should be to offer an information sharing mechanism to facilitate bidding ring formation, as a means to maximize the value of this market mechanism.     

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.     

Consumer adoption of group-buying auctions: an experimental study

Internet-based group-buying auctions enable consumers to obtain volume discounts, but they face risk and trust issues that are not present in other e-retailing formats, which affects their adoption by consumers. Bidders experience uncertainty about the final auction price, and the risk of whether the auction will be completed. We evaluate textual comments and the number of bids made in an auction as drivers of a consumer’s perceived financial and psychological risks toward the group-buying auction mechanism and trust in the auction initiator. We use an Internet-based experimental test bed for online group-buying auctions and will report on one experiment that we conducted. Our results indicate that textual comments made by the participants about sellers in past auctions and existing bids affected a consumer’s perceived trust in the auction initiator and the financial risk of the mechanism. Positive textual comments and more bids appear to enhance perceived trust in the auction initiator and reduce financial risk, and other consumers are more willing to make bids as a result. Consumers continued to express concerns about the uncertainty of the final group-buying auction price though.     

一个基于知识证明签名的安全电子拍卖协议

论文研究了英式电子拍卖协议,基于知识证明签名给出一个安全有效的电子拍卖协议。该协议实现了竞拍者身份的匿名性、获胜竞拍者的不可否认性、可公开验证性、竞拍者不可伪装性、可跟踪同一拍卖中某竞拍者的投标以及某个竞拍者在不同拍卖中不可关联性等问题。论文的工作重点是引入了可信第三方并利用知识证明签名来解决其它协议中撤消竞拍者的问题,可简单地撤消某个竞拍者并保证拍卖的高效率。另外,本文还给出了避免拍卖管理者的不公正性的改进协议。