An efficient Nash-implementation mechanism for network resource allocation

We propose a mechanism for auctioning bundles of multiple divisible goods in a network where buyers want the same amount of bandwidth on each link in their route. Buyers can specify multiple routes (corresponding to a source-destination pair). The total flow can then be split among these multiple routes. We first propose a one-sided VCG-type mechanism. Players do not report a full valuation function but only a two-dimensional bid signal: the maximum quantity that they want and the per-unit price they are willing to pay. The proposed mechanism is a weak Nash implementation, i.e., it has a non-unique Nash equilibrium that implements the social-welfare maximizing allocation. We show the existence of an efficient Nash equilibrium in the corresponding auction game, though there may exist other Nash equilibria that are not efficient. We then generalize this to arbitrary bundles of various goods. Each buyer submits a bid separately for each good but their utility function is a general function of allocations of bundles of various divisible goods. We then present a double-sided auction mechanism for multiple divisible goods. We show that there exists a Nash equilibrium of this auction game which yields the efficient allocation with strong budget balance.     

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

基于环签名理论提出一个电子拍卖方案,适用于公司内部或者具有排外性的团体内部的拍卖,拍卖期间,成员可以在任何地点、任何时间提交自己的投标消息,等到拍卖结束后,再提交自己相应的投标值,匿名的同时又能证明投标消息的合法性,既证明了自己属于组内成员,又不会泄漏投标者的确切身份,保护了投标者的隐私。     

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.     

Auctions and Differential Pricing: Optimal Seller and Bidder Strategies in Second-chance Offers

The second chance offer is a common seller practice on eBay. It consists of price discrimination against the losing bidder, who is offered an identical item at the value of his or her highest bid. Prior work has shown that, if the goods are private-value goods and price discrimination is certain, rational bidders can anticipate it and accordingly modify their bidding strategies; this results in revenue loss for the seller. This paper hence examines the impact of randomized price discrimination. It examines a similar, more general problem: a seller has k items of the private-value good. They are sold to N bidders in a two-stage game. The first stage is a sealed-bid first-price auction with N bidders. The second stage is a take-it-or-leave-it offer to each of k − 1 losing bidders; randomized between a fixed-price offer and a second-chance offer. Showing that analytic techniques do not provide complete solutions because bidding strategies are not always monotonic increasing, this paper uses genetic algorithm simulations to determine the Bayesian (near-Nash) equilibrium strategies for bidders and sellers, for N = 8 and different values of k. It finds that price discrimination is beneficial to the seller when k is small, as item scarcity increases competition among bidders. The paper’s use of randomized seller strategies and genetic algorithm simulations is unique in the study of the second-chance offer.     

Procurement decision making mechanism of divisible goods based on multi-attribute auction

Multi-attribute auction enables negotiation on several attributes in addition to the price such as quality, quantity, time of delivery and service levels. Most of the existing multi-attribute auction mechanisms are designed by considering a unique good or indivisible multiple goods. This paper focuses on designing a multi-attribute auction mechanism for addressing the decision making problem of multi-attribute and multi-source procurement of a kind of homogeneous continuous divisible goods (such as coal, oil, electricity and gas). The suppliers’ optimal bidding strategies are discussed, and a bidding method named the minimum bid increment method is proposed to simulate the overall process of suppliers’ multiple rounds of bidding. Theoretical analysis shows that our auction mechanism is an efficient mechanism, and satisfies the incentive compatibility conditions and the individual rationality conditions. Moreover, a multi-attribute auction example about the steam coal procurement is given to show how to implement our multi-attribute auction mechanism.     

Bidder's strategy under group-buying auction on the Internet

The group-buying auction is a new kind of dynamic pricing mechanism on the Internet. It is a variant of the sellers' price double auction, which makes the bidders as a group through Internet to get the volume discounts, i.e., the more bidders bid, the lower the price of the object being auctioned becomes. In this paper, we analyze the group-buying auction under some assumptions, such as that the independent private values (IPVs) model applies and bidders are risk neutral and symmetric, etc., and build an incomplete information dynamic game model to illustrate the bidders' bidding process. It proves that for the bidders there exists a weakly dominant strategy S, i.e., no matter when a bidder arrives at the auction and what the bidding history is, the highest permitted bid price that is no greater than his value to the object is always his optimal bid price but may not be the unique one.     

Segmenting uncertain demand in group-buying auctions

Demand uncertainty is a key factor in a seller’s decision-making process for products sold through online auctions. We explore demand uncertainty in group-buying auctions in terms of the extent of low-valuation demand and high-valuation demand. We focus on the analysis of a monopolistic group-buying retailer that sells products to consumers who express different product valuations. We also examine the performance of a group-buying seller who faces competitive posted-price sellers in a market for the sale of the same products, under similar assumptions about uncertain demand. Based on a Nash equilibrium analysis of bidder strategies for both of these seller-side competition structures, we are able to characterize the group-buying auction bidders’ dominant strategies. We obtained a number of interesting findings. Group-buying is likely to be more effective in settings where there is larger low-valuation demand than high-valuation demand. The structure of demand matters. This finding has relevance to the marketplace for new cameras, next-generation microprocessors and computers, and other high-valuation goods, which are unlikely to be as effectively sold in group-buying markets. We obtained additional results for the case of continuous demand, and find that there is a basis for the seller to improve revenues via effective group-buying auction price curve design.     

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.     

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.     

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.     

Interplay between Buy-It-Now price and last minute bidding on online bidding strategies

Sellers and buyers on online auction sites like eBay have the option of setting and executing auction parameters such as auction length, Buy-It-Now price, starting price, reserve price, etc. Understanding why bidders choose to execute the Buy-It-Now price as opposed to submitting a bid at the last minute of an auction helps managers better choose auction parameters and generate more revenue. In this paper, we first study online bidder behavior pertaining to the execution of the Buy-It-Now option as opposed to the last minute bidding strategy on eBay. Consequently, we study the seller’s decision to set a Buy-It-Now option and the amount of it. Our main finding is that a dominant strategy for the seller is to offer a Buy-It-Now option at the beginning of the auction. An early bidder arriving at the auction site is indifferent in choosing threshold Buy-It-Now prices or moving onto the auction and under particular circumstances strategically waiting for the last minutes of the auction to submit a bid. We also provide conditions on the existence of a set of equilibria which predicts the outcome of the game of executing the Buy-It-Now option versus last-minute bidding on eBay.     

基于区块链的密封式投标拍卖方案

随着互联网技术的飞速发展,传统拍卖正逐渐转变为电子拍卖,其中隐私保护越来越受到关注。针对当前电子投标拍卖系统中出现的问题,如竞买人隐私存在被泄露的风险、第三方拍卖中心的费用昂贵、第三方拍卖中心可能与竞买人勾结等,提出一种基于区块链智能合约技术的密封式投标拍卖方案。该方案充分利用区块链的去中心化、防篡改和可信赖性等特征构建了一个无第三方的拍卖环境,并通过区块链上的安全保证金策略约束竞买人的行为,从而提高密封式电子拍卖的安全性。同时该方案利用Pedersen承诺保护竞买人的竞拍价格不被泄露,并通过Bulletproofs零知识证明协议验证中标价格的正确性。安全性分析和实验结果表明,提出的拍卖方案满足安全性要求,各个阶段的时间消耗均在可接受范围内,满足日常拍卖要求。     

Distributed ascending proxy auction — A cryptographic approach

In recent years, auctions have become a very popular price discovery mechanism in the Internet. The common auction formats are typically centralized in nature. The peer-to-peer paradigm demands gearing up auctions for decentralized infrastructures. In this context, this paper proposes a distributed mechanism for ascending second-price auctions that relies on standard cryptographic algorithms. In essence, the auction protocol has the capability of preserving the privacy of the winning bidder’s true valuation. The auction protocol makes use of a high number of auctioneers divided into several groups. A bidder creates an encrypted chain of monotonously increasing bidding steps, where each bidding step can be decrypted by a different auctioneer group. This considerably reduces the attack and manipulation possibilities of malicious auctioneers. In addition, this secure approach does not require bidders to be online unless they are submitting their bid chain to the auctioneers.     

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.     

Strategy/False-name Proof Protocols for Combinatorial Multi-Attribute Procurement Auction

In this paper, we investigate a model of a combinatorial, procurement multi-attribute auction, in which each sales item is defined by several attributes called quality, the buyer is the auctioneer (e.g., a government), and the sellers are the bidders. Furthermore, there exist multiple items and both buyer and sellers can have arbitrary (e.g., substitutable/complementary) preferences on a bundle of items. Our goal is to develop a protocol that is strategy-proof for sellers. We first present a VickreyClarkeGroves (VCG)-type protocol. As in a standard combinatorial auction, a VCG-type protocol is not false-name-proof, i.e., it is vulnerable against manipulations using multiple identifiers. Next, we show that any strategy-proof protocol in this model can be represented as a framework called Price-Oriented Rationing-Free (PORF) protocol, in which for each bidder, for each bundle of items, and for each quality, the payment for the bidder is determined independently of his own declaration, and the bidder can obtain a bundle that maximizes his utility independently of the allocations of other bidders. We develop a false-name-proof protocol in this model.     

Revenue monotonicity in deterministic, dominant-strategy combinatorial auctions

In combinatorial auctions using VCG, a seller can sometimes increase revenue by dropping bidders. In this paper we investigate the extent to which this counterintuitive phenomenon can also occur under other deterministic, dominant-strategy combinatorial auction mechanisms. Our main result is that such failures of “revenue monotonicity” can occur under any such mechanism that is weakly maximal—meaning roughly that it chooses allocations that cannot be augmented to cause a losing bidder to win without hurting winning bidders—and that allows bidders to express arbitrary known single-minded preferences. We also give a set of other impossibility results as corollaries, concerning revenue when the set of goods changes, false-name-proofness, and the core.¹     

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     

一种安全高效的M+1电子拍卖

为了保护电子拍卖过程中投标者的隐私,以及防止投标者中标后反悔,本文利用签名技术和位承诺协议,提出了一个安全高效的M+1匿名拍卖协议。该协议不仅保证了标价的保密性和可验证性,投标者对所投标价的不可否认性和匿名性,而且保证了在整个拍卖过程中,无人可以操纵其他人的投标。即使某一投标者与拍卖代理相互勾结,也不会影响协议的安全性和有效性。     

Simultaneous Independent Online Auctions with Discrete Bid Increments

Decentralized multi-item auctions offer great opportunities for integrating fragmented online auction markets into larger markets with more efficient outcomes. This paper extends the theory of multi-item ascending auctions of substitutes by considering any finite positive bid increment and allowing the bidders to bid asyn-chronously instead of bidding in a round-robin fashion. We consider a setup where the bidders utilities over multiple items are additive and bound the maximum inefficiency in the allocation when the bidders follow a simple greedy strategy. We also obtain the limits within which the prices of individual items can vary from one outcome to another. For the special case of single unit bidder demand, we also bound the maximum surplus which a bidder can extract by unilaterally switching to some other strategy. The paper suggests an upper bound for the minimum required bid increment which would be necessary for competitive price discovery and truthful bidding in a practical online implementation.The work was done while the author was with IBM Research.     

Security analysis with improved design of post-confirmation mechanism for quantum sealed-bid auction with single photons

Quantum sealed-bid auction (QSA) has been widely studied in quantum cryptography. For a successful auction, post-confirmation is regarded as an important mechanism to make every bidder verify the identity of the winner after the auctioneer has announced the result. However, since the auctioneer may be dishonest and collude with malicious bidders in practice, some potential loopholes could exist. In this paper, we point out two types of collusion attacks for a particular post-confirmation technique with EPR pairs. And it is not difficult to see that there exists no unconditionally secure post-confirmation mechanism in the existing QSA model, if the dishonest participants have the ability to control multiparticle entanglement. In the view of this, we note that some secure implementation could exist if the participants are supposed to be semi-quantum, i.e., they can only control single photons. Finally, two potential methods to design post-confirmation mechanism are presented in this restricted scenario.