An options-based solution to the sequential auction problem

The sequential auction problem is commonplace in open, electronic marketplaces such as eBay. This is the problem where a buyer has no dominant strategy in bidding across multiple auctions when the buyer would have a simple, truth-revealing strategy if there was but a single auction event. Our model allows for multiple, distinct goods and market dynamics with buyers and sellers that arrive over time. Sellers each bring a single unit of a good to the market while buyers can have values on bundles of goods. We model each individual auction as a second-price (Vickrey) auction and propose an options-based, proxied solution to provide price and winner-determination coordination across auctions. While still allowing for temporally uncoordinated market participation, this options-based approach solves the sequential auction problem and provides truthful bidding as a weakly dominant strategy for buyers. An empirical study suggests that this coordination can enable a significant efficiency and revenue improvement over the current eBay market design, and highlights the effect on performance of complex buyer valuations (buyers with substitutes and complements valuations) and varying the market liquidity.     

一种新的量子群进化算法研究

提出了一种基于量子进化的量子群进化算法，使用量子角表示量子比特的状态，并引入改进的粒子群优化策略，对量子群中各量子的量子角进行自适应动态调整．在对0-1背包问题的求解中，表现出很好的性能．     

混合量子算法及其在flow shop问题中的应用

量子进化算法（QEA）是目前较为独特的优化算法,它的理论基础是量子计算。算法充分借鉴了量子比特的干涉性、并行性,使得QEA求解组合优化问题具备了可行性。由于在求解排序问题中,算法本身存在收敛慢,没有利用其它未成熟个体等缺陷,将微粒群算法（PSO）及进化计算思想融入QEA中,构成了混合量子算法（HQA）。采用flow shop经典问题对算法进行了测试,结果证明混合算法克服了QEA的缺陷,对于求解排序问题具有一定的普适性。     

Mechanism design for e-procurement auctions: On the efficacy of post-auction negotiation and quality effort incentives

Practical mechanisms for procurement involve bidding, negotiation, transfer payments and subsidies, and the possibility of verification of unobservable product and service quality. We model two proposed multi-stage procurement mechanisms. One focuses on the auction price that is established, and the other emphasizes price negotiation. Both also emphasize quality and offer incentives for the unobservable level of a supplier’s effort, while addressing the buyer’s satisfaction. Our results show that, with the appropriate incentive, which we will refer to as a qualityeffort bonus, the supplier will exert more effort to supply higher quality goods or services after winning the procurement auction. We also find that a mechanism incorporating price and quality negotiation improves the supply chain’s surplus and generates the possibility of Pareto optimal improvement in comparison to a mechanism that emphasizes the auction price only. From the buyer’s perspective though, either mechanism can dominate the other, depending on the circumstances of procurement. Thus, post-auction negotiation may not always be optimal for the buyer, although it always produces first-best goods or service quality outcomes. The buyer’s choice between mechanisms will be influenced by different values of the quality effort bonus. For managers in practice, our analysis shows that it is possible to simplify the optimization procedure by using a new approach for selecting the appropriate mechanism and determining what value of the incentive for the supplier makes sense.     

求解TSP的新量子蚁群算法

鉴于蚁群算法（ACA）在求解TSP时表现出的优越性,以及量子进化算法（QEA）在求解组合优化问题时表现出的高效性,将ACA与QEA的算法思想进行融合,提出一种新的求解TSP的量子蚁群算法。该算法对各路径上的信息素进行量子比特编码,设计了一种新的信息素表示方式,即量子信息素;采用量子旋转门及最优路径对信息素进行更新,加快算法收敛速度;为了避免搜索陷入局部最优,设计了一种量子交叉策略,以改善种群信息结构。仿真实验结果表明了该算法具有较快的收敛速度和全局寻优能力,性能明显优于ACS。     

基于改进量子进化算法的特征选择

特征选择作为一种数据预处理技术被广泛研究,由于其具有NP难度而一直无法找到有效的求解方法。鉴于目前在特征选择中应用较多的遗传算法存在进化机制上的局限,将量子进化算法应用于特征选择,提出了一种基于改进量子进化算法的特征选择算法。以增加种群多样性和提高寻优性能为目标改进了量子进化算法,以Fisher比和特征维度为特征子集的评价准则构造了适应度函数,按照量子进化算法求解优化问题的步骤设计了特征选择算法。使用UCI数据库中的数据集对三种算法作对比验证,通过识别重要特征、提高学习算法性能、特征选择效率三组实验,结果表明,该算法能够识别出重要特征,并随着数据集特征维度升高,特征选择的性能逐渐优于对比算法,到了高维数据集,特征选择效率明显优于对比算法。     

一种基于量子进化算法的概率进化算法

针对量子进化算法(QEA)求解二进制编码问题比较有效,而求解多进制编码问题则比较困难,提出一种概率进化算法(PEA)。该算法汲取了量子复合位、叠加态等思想,采用由观测概率构成的概率复合位进行编码,观测和更新操作直接针对观测概率进行。PEA保持了QEA的性能,运算速度远优于QEA,并可以采用任意进制编码。函数优化和背包问题实验验证了PEA的有效性。     

Exploring local search in winner determination problem

In Combinatorial Auctions, multiple goods (items) are available for auction simultaneously, and bidders bid for combinations of goods called bundles. In the single unit combinatorial auction problem, there is only single unit of each item present and the items are considered to be indivisible. This forms the supply side constraint resulting in a need by the seller to decide on which bundles to allocate for maximizing the revenue. Determining these winning bundles is an NP-complete problem and is known by the name of Winner Determination Problem (WDP) in literature. Combinatorial auction mechanism has a wide range of practical applications such as allocation of railroads, auction of adjacent pieces of real estate, auction of airport landing slots, distributed job shop scheduling etc. The optimal heuristic search algorithms like CASS and CABOB proposed for solving the WDP take a lot of CPU time for solving large problem instances. Though these algorithms give optimal solutions, they would be useful only in scenarios where time is not at all a constraint, and the bidding is a one time affair. This poses a limitation in conducting combinatorial auctions with multiple rounds of bidding and hence hinders the widespread use of combinatorial auctions on the patterns of traditional English auction and internet auctions. Thus faster solution of WDP holds the key to widespread use and popularity of combinatorial auctions. This paper attempts to address the above issue, and proposes a simple local search technique LSWDP (Local Search for Winner Determination Problem) that runs very fast and provides solutions quite close to optimal for a number of applications. It also outputs optimal solutions in many instances taking only a fraction of the CPU time taken by CASS. In addition LSWDP was found to outperform the anytime algorithm CASS given a time cutoff. This paper also presents an enhancement called LSCN (Local Search using Complimentary Neighborhood) that provides still better solutions in terms of close to optimal behavior and achieves a much better strike rate in hitting optimal solutions. LSCN runs slower than LSWDP but still takes only a fraction of the CPU time taken by CASS thus encouraging the use of local search for combinatorial auctions. Finally, an extension to multi-partition search has been proposed and analyzed.

Autonomous Adaptive Agents for Single Seller Sealed Bid Auctions

In developing open, heterogeneous and distributed multi-agent systems researchers often face a problem of facilitating negotiation and bargaining amongst agents. It is increasingly common to use auction mechanisms for negotiation in multi-agent systems. The choice of auction mechanism and the bidding strategy of an agent are of central importance to the success of the agent model. Our aim is to determine the best agent learning algorithm for bidding in a variety of single seller auction structures in both static environments where a known optimal strategy exists and in complex environments where the optimal strategy may be constantly changing. In this paper we present a model of single seller auctions and describe three adaptive agent algorithms to learn strategies through repeated competition. We experiment in a range of auction environments of increasing complexity to determine how well each agent performs, in relation to an optimal strategy in cases where one can be deduced, or in relation to each other in other cases. We find that, with a uniform value distribution, a purely reactive agent based on Cliff’s ZIP algorithm for continuous double auctions (CDA) performs well, although is outperformed in some cases by a memory based agent based on the Gjerstad Dickhaut agent for CDA.     

Bidder-anonymous English auction scheme with privacy and public verifiability

This work studies the English auction protocol, which comprises three interactive parties—the Registration Manager, the Auction Manager and the Bidder. The registration manager confirms and authenticates the identities of bidders; the auction manager issues the bidding rights and maintains order in holding the auction. The proposed scheme provides the following security features—anonymity, traceability, no framing, unforgeability, non-repudiation, fairness, public verifiability, non-linkability among various auction rounds, linkability within a single auction round, bidding efficiency, single registration, and easy revocation. The scheme developed herein can effectively reduce the load on the registration and auction managers by requiring the end server to derive the key. It also eliminates the need for bidders to download the auction key and the auction certificate. Hence, the time complexity of processing data is clearly reduced and the best interests of the bidders can be achieved. Accordingly, the scheme is consistent with the actual practice of online transactions.     

基于带惩罚的点概率距离策略优化算法在展示广告实时竞标中的研究

实时竞价(RTB)是在线展示广告中被广泛采用的广告投放模式,针对由于RTB拍卖环境的高度动态性导致最佳出价策略难以获得的问题,提出了一种基于强化学习(RL)的出价策略优化方法,即采用带惩罚的点概率距离策略优化(POP3D)算法来学习最佳出价策略。在基于POP3D的出价框架中,广告投标过程被建模为情节式的马尔可夫决策过程,每个情节被划分为固定数量的时间步,每个广告展示的出价由它的预估点击率大小和竞标因子共同决定。每个时间步,竞标代理都会根据上一时间步的拍卖情况对竞标因子进行调整,以使得出价策略能够适应高度动态的拍卖环境,竞标代理的目标是学习最佳的竞标因子调整策略。在iPinYou数据集上的实验结果表明,与DRLB算法相比,所提出价算法在预算比例为1/16和1/32时,在点击次数方面均提升了0.2%;当预算比例为1/8、1/16和1/32时,在赢标率方面分别提升了1.8%、1.0%和1.7%;另外,在稳定性方面,所提方法也具有优势。表明了该方法的优越性。     

Quantum-inspired evolutionary algorithms with a new termination criterion, H/sub /spl epsi// gate, and two-phase scheme

From recent research on combinatorial optimization of the knapsack problem, quantum-inspired evolutionary algorithm (QEA) was proved to be better than conventional genetic algorithms. To improve the performance of the QEA, this paper proposes research issues on QEA such as a termination criterion, a Q-gate, and a two-phase scheme, for a class of numerical and combinatorial optimization problems. A new termination criterion is proposed which gives a clearer meaning on the convergence of Q-bit individuals. A novel variation operator H/sub /spl epsi// gate, which is a modified version of the rotation gate, is proposed along with a two-phase QEA scheme based on the analysis of the effect of changing the initial conditions of Q-bits of the Q-bit individual in the first phase. To demonstrate the effectiveness and applicability of the updated QEA, several experiments are carried out on a class of numerical and combinatorial optimization problems. The results show that the updated QEA makes QEA more powerful than the previous QEA in terms of convergence speed, fitness, and robustness.     

应急物资采购及代储服务交易的逆向组合拍卖机制设计

建立市场化的政企联合储备模式已经成为应急物资储备体系建设的重要方式.基于此,着眼于应急物资采购及代储服务的交易问题,设计一个逆向组合拍卖机制.在此拍卖机制中,政府是拍卖的买方兼委托人,企业是拍卖的卖方兼竞拍者,应急物资采购及代储服务是拍卖商品.首先,通过一个报童模型建立政府决策行为与拍卖活动之间的关系,并提出企业的投标策略;其次,建立最小化供需偏差和最大化供给数量的竞胜标决定模型;最后,提出一个符合实际背景的数值算例对拍卖机制进行模拟和验证.研究表明,所提出的逆向组合拍卖机制不仅具有经济效率,还能够促进政府一次性达成与多家企业在多个周期的合作.由此可见,运用拍卖机制解决应急物资政企联合储备的交易问题具备理论的优越性和现实的适用性.     

Forward looking Nash equilibrium for keyword auction

We introduce the concept of forward looking Nash equilibrium for the position auction (also called the generalized second price auction), a widely studied protocol for Internet advertisement bidding processes. We show that it has a unique solution for the position auction. Most importantly, the cost each bidder pays and the revenue of the auctioneer under the equilibrium are all equal to those under VCG mechanism. As the position auction is not an incentive compatible protocol, the fact that the forward looking Nash equilibrium results in the same payoff for everyone as in the VCG protocol justifies the practical protocol.     

基于模糊博弈的英式拍卖动态模型

为了给竞价人或其代理的竞价提供决策支持,提出了模糊博弈的英式拍卖动态模型.以模糊参数出价意愿取代估价作为分析的基础,采用Bellman和Zadeh的模糊决策理论替代博弈论中的Nash平衡理论,分析英式拍卖中的竞价行为,建立英式拍卖静态博弈均衡模型,进而提出动态博弈模型和分析动态拍卖策略.通过仿真实验证明算法的有效性.     

A hybrid mechanism for heterogeneous e-procurement involving a combinatorial auction and bargaining

We discuss the design of a hybrid mechanism for e-procurement, which implements a multi-attribute combinatorial auction, followed by a bargaining process to achieve desirable procurement transaction outcomes. For the auction phase of the mechanism, we discuss incentive-compatible bidding strategies for suppliers, and how the buyer should determine the winning suppliers. In the follow-on bargaining phase, the buyer can implement a pricing strategy that views the winning suppliers as though they are in different groups. We develop a model and derive decision conditions for the buyer to formulate procurement strategy in this context. Our most important finding is that, compared with the classical Vickrey–Clarke–Groves mechanism, the proposed mechanism improves the transactional social surplus, by including the possibility of post-auction bargaining. We also consider the likelihood that such a hybrid mechanism will be able to provide sustainable business value so long as there is reasonable symmetry in bargaining power between the buyer and the supplier. We offer some thoughts on how to extend this research with approaches from behavioral economics and experimental methods.     

基于MapReduce模型的并行量子进化算法

利用MapReduce模型可自动编写串行程序及编程接口简单的优点,实现量子进化算法在MapReduce模型下的并行化,提出基于MapReduce模型的并行量子进化算法MRQEA,并将其部署到Hadoop云计算平台上运行。对0-1背包问题的测试结果证明,MRQEA算法在处理大型数据集时具有良好的加速比和并行效率。     

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.     

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.     

Strategic bidding using fuzzy adaptive gravitational search algorithm in a pool based electricity market

A novel stochastic optimization approach to solve optimal bidding strategy problem in a pool based electricity market using fuzzy adaptive gravitational search algorithm (FAGSA) is presented. Generating companies (suppliers) participate in the bidding process in order to maximize their profits in an electricity market. Each supplier will bid strategically for choosing the bidding coefficients to counter the competitors bidding strategy. The gravitational search algorithm (GSA) is tedious to solve the optimal bidding strategy problem because, the optimum selection of gravitational constant (G). To overcome this problem, FAGSA is applied for the first time to tune the gravitational constant using fuzzy “IF/THEN” rules. The fuzzy rule-based systems are natural candidates to design gravitational constant, because they provide a way to develop decision mechanism based on specific nature of search regions, transitions between their boundaries and completely dependent on the problem. The proposed method is tested on IEEE 30-bus system and 75-bus Indian practical system and compared with GSA, particle swarm optimization (PSO) and genetic algorithm (GA). The results show that, fuzzification of the gravitational constant, improve search behavior, solution quality and reduced computational time compared against standard constant parameter algorithms.