Evolutionary Techniques for Reverse Auctions

Winner determination is one of the main challenges in combinatorial auctions. However, not much work has been done to solve this problem in the case of reverse auctions using evolutionary techniques. This has motivated us to propose an improvement of a genetic algorithm based method, we have previously proposed, to address two important issues in the context of combinatorial reverse auctions: determining the winner(s) in a reasonable processing time, and reducing the procurement cost. In order to evaluate the performance of our proposed method in practice, we conduct several experiments on combinatorial reverse auctions instances. The results we report in this paper clearly demonstrate the efficiency of our new method in terms of processing time and procurement cost.

预算约束下多任务联邦学习激励机制

联邦学习是一种实现数据隐私保护的分布式机器学习范式,性能取决于数据源的质量和数据规模。客户端是理性个体,参与联邦学习将耗费计算、通信和隐私等成本,需要通过激励提高客户端的参与意愿。因此联邦学习能成功应用的关键之一是尽可能多地激励高质量数据客户端参与训练。多任务联邦学习环境下客户端拥有面向不同任务且质量不同的数据,并具有执行能力的约束。为提高多个学习任务的整体性能,在预算受限的条件下设计一种面向任务的客户选择和报酬机制。通过分析影响模型精度的重要因素,提出一种基于客户端数据样本分布特征的质量评估标准,并结合客户端成本信息,设计一种逆向拍卖的激励机制(EMD-MQMFL),实现客户端的任务指派和支付策略。从理论上分析和证明了该机制具有诚实性、个人理性以及预算可行性,并通过大量实验验证了该方法在联邦学习性能上的有效性。在MNIST、Fashion-MNIST、Cifar-10数据集上的实验结果表明,EMD-MQMFL在数据不平衡的情况下,平均模型精度比已有的机制至少提高5.6个百分点。

基于选择的移动群智感知反向拍卖激励机制

由于移动群智感知中工人和平台的自私性,社会福利和数据质量往往难以达到平衡,损害了基于移动群智感知的服务可用性和准确性。为了解决这一问题,本文提出一种基于选择的反向拍卖激励机制,分别研究反向拍卖中以工人为中心的任务选择和以平台为中心的工人选择,在最大限度提高社会福利的同时优化数据质量。首先,根据工人和任务的位置等属性评估工人与任务之间的匹配度,提出基于动态规划的任务选择算法,在工人资源约束下为每个工人选择具有最佳回报的任务进行投标;其次,使用多臂赌博机建模反向拍卖赢家选择过程,并设计了一种基于置信度上界的赢家选择算法,以确定最佳中标工人集;最后,实验验证本文所提出的激励机制能够同时有效提升社会福利和数据质量。

车辆群智感知中激励驱动的车辆选择与调度方法

车辆群智感知旨在利用智能车辆配备的车载传感器和计算资源,收集一系列区域的感知数据.目前,根据车辆轨迹是否可更改,通常可将感知车辆分为机会型车辆和参与型车辆.其中,机会型车辆轨迹路线固定,不可随意更改.而参与型车辆轨迹路线可根据现实需求进行更改.因此,如何选择合适的机会型车辆完成感知任务,以及如何规划参与型车辆的轨迹是一项挑战性研究问题.这里,以2种类型感知车辆的不同移动特性为出发点,通过群智感知平台(CSP)管理2种类型的车辆,并分别针对机会型车辆和参与型车辆解决不同的问题.首先,针对机会型车辆,需选择特定的车辆集合,以完成感知任务并最小化CSP开销.为解决此问题,提出一项基于反向拍卖的激励机制以选择开销最小的车辆集合完成感知任务,主要包括获胜车辆选择和报酬支付2个阶段,同时验证了所提方法可保证机会型车辆的个体合理性和真实性;其次,针对参与型车辆,需通过CSP调度以规划每个参与型车辆的轨迹,执行感知任务并最小化CSP的开销.为解决此问题,提出一项基于深度强化学习的方法以调度车辆行驶轨迹,为车辆分配不同的感知任务.此外,在最小化CSP开销的同时,还考虑感知任务执行的公平性问题,引入感知公平指数以确保不同子区域感知任务完成的均衡性.最后,基于真实世界数据集的广泛评估表明,所提方法效果良好,并优于其他基准方案.

A Reverse Auction Mechanism for Time-Varying Multidimensional Resource Allocation in Vehicular Fog Computing with Cloud and Edge Collaboration

It is a hot issue to allocate resources using auction mechanisms in vehicular fog computing(VFC)with cloud and edge collaboration.However,most current research faces the limitation of only considering single type resource allocation,which cannot satisfy the resource requirements of users.In addition,the resource requirements of users are satisfied with a fixed amount of resources during the usage time,which may result in high cost of users and even cause a waste of resources.In fact,the actual resource requirements of users may change with time.Besides,existing allocation algorithms in the VFC of cloud and edge collaboration cannot be directly applied to time-varying multidimensional resource allocation.Therefore,in order to minimize the cost of users,we propose a reverse auction mechanism for the time-varying multidimensional resource allocation problem(TMRAP)in VFC with cloud and edge collaboration based on VFC parking assistance and transform the resource allocation problem into an integer programming(IP)model.And we also design a heuristic resource allocation algorithm to approximate the solution of the model.We apply a dominant-resource-based strategy for resource allocation to improve resource utilization and obtain the lowest cost of users for resource pricing.Furthermore,we prove that the algorithm satisfies individual rationality and truthfulness,and can minimize the cost of users and improve resource utilization through comparison with other similar methods.Above all,we combine VFC smart parking assistance with reverse auction mechanisms to encourage resource providers to offer resources,so that more vehicle users can obtain services at lower prices and relieve traffic pressure.

Meeting peak electricity demand through combinatorial reverse auctioning of renewable energy

The option of organizing E-auctions to purchase electricity required for anticipated peak load period is a new one for utility companies.To meet the extra demand load,we develop electricity combinatorial reverse auction(CRA)for the purpose of procuring power from diverse energy sources.In this new,smart electricity market,suppliers of different scales can participate,and homeowners may even take an active role.In our CRA,an item,which is subject to several trading constraints,denotes a time slot that has two conflicting attributes,electricity quantity and price.To secure electricity,we design our auction with two bidding rounds:round one is exclusively for variable energy,and round two allows storage and nonintermittent renewable energy to bid on the remaining items.Our electricity auction leads to a complex winner determination(WD)task that we represent as a resource procurement optimization problem.We solve this problem using multi-objective genetic algorithms in order to find the trade-off solution that best lowers the price and increases the quantity.This solution consists of multiple winning suppliers,their prices,quantities and schedules.We validate our WD approach based on large-scale simulated datasets.We first assess the time-efficiency of our WD method,and we then compare it to well-known heuristic and exact WD techniques.In order to gain an exact idea about the accuracy of WD,we implement two famous exact algorithms for our constrained combinatorial procurement problem.

基于逆向拍卖的D2D边缘缓存网络编码内容定价与交易机制

在D2D边缘缓存网络中引入网络编码技术具有缓存利用率高、数据块调度过程简单及系统鲁棒性高等优点。但是,由于对编码块分享所带来的设备能量消耗等顾虑,用户倾向于只从网络获取内容而进行内容分享,这种自私行为直接影响了系统的总体性能。针对该问题,提出了一种基于逆向拍卖的D2D编码网络内容分享激励机制——RACON。RACON以实现网络内容分享总效用最大化为目标,将内容请求者视作拍卖过程的买家,而将买家周围的潜在内容提供者视为拍卖过程的卖家;买、卖方的内容叫价过程可综合考虑其自身电量资源、用户之间传输距离以及传输内容的供需关系等影响因素;拍卖结果允许多个卖家中标,并采用虚拟代币结算,从而激励用户间相互分享缓存内容。理论分析证明RACON机制符合双边激励相容性、个人理性约束、物质及弱预算平衡特征,可有效约束买、卖方拍卖行为。仿真实验进一步表明,RACON机制能够有效地激励网络内用户间编码内容分享过程,最大化边缘缓存网络效用。

基于反向拍卖的电动汽车能源交易激励机制

电动汽车通过泛在电力物联网(Ubiquitous Power Internet of Things, UPIoT)作为移动负载向电力系统提供电力储备,在增强电网稳定性等方面被认为具有巨大潜力,随着电动汽车数量的极速增涨,基于电动汽车的能源交易引起了能源供应商的广泛关注。基于此,提出一种基于反向拍卖的电动汽车能源交易激励方案。在定价过程中引入多用户协商博弈框架,进而制定电动汽车的最优定价支付策略;并以最大化能源聚合商的收益为目标,提出了预算受限的车辆选择算法。经与已有方案进行仿真对比,所提方案在降低能源聚合商成本、提高能源聚合商收益和激励车辆放电方面都具有较好的性能。

A Reverse Auction Framework for Hybrid Access in Femtocell Network

In the two-tier macro-femto heterogeneous network, hybrid access is regarded as the most ideal access con- trol approach to mitigating macro-femto cross-tier interference and enhancing overall network performance. However, the implementation of hybrid access is hindered by a lack of incentive market mechanism to motivate private femtocell owners to offer access permissions to macro users. In this paper, we propose a reverse auction framework for access permission transaction between a macrocell operator and multiple femtocell owners to promote hybrid access. Our goal is to maximize social welfare while guaranteeing the truthfulness of the auction. Since the coverage of multiple femtocells may overlap, we partition each cell to adjust the granularity of access permission availability. We first propose a Vickery-Clarke-Grove （VCG）-based mechanism, which costs the least among all auction mechanisms that produce maximum social welfare. As the VCG mechanism is too time-consuming, we propose two alternative truthful mechanisms, namely, generalized second- price and suboptimal mechanism. We further extend the auction framework to the scenario where femtocell owners have heterogeneous valuations for access permissions in different locations.

Mechanism design of reverse auction on concession period and generalized quality for PPP projects

Reverse auctions of PPP projects usually require the bid to specify several characteristics of quality and the concession period to be fulfilled. This paper sets up a summary function of generalized quality, which contributes to reducing the dimensions of information.Thus, the multidimensional reverse auction model of a PPP project can be replaced by a two-dimensional direct mechanism based on the concession period and the generalized quality. Based on the theory of the revelation principle, the feasibility conditions, equilibrium solution and generalized quality requirements of such a mechanism,considering the influence of a variable investment structure are described. Moreover, two feasible multidimensional reverse auctions for implementing such a direct mechanism: Adjusting the scoring function and establishing a special reverse auction rule are built. The analysis shows that in these types of reverse auctions, optimal allocation can be achieved, the social benefit under the incomplete information will be maximized, and the private sector with the highest integrated management level wins the bid. In such a direct mechanism, the investment and financial pressure of the public sector can be reduced.

Winner determination problem with loss-averse buyers in reverse auctions

Reverse auctions have been widely adopted for purchasing goods and services. This paper considers a novel winner determination problem in a multiple-object reverse auction in which the buyer involves loss-averse behavior due to uncertain attributes. A corresponding winner determination model based on cumulative prospect theory is proposed. Due to the NP-hard characteristic, a loaded route strategy is proposed to ensure the feasibility of the model. Then, an improved ant colony algorithm that consists of a dynamic transition strategy and a Max-Min pheromone strategy is designed. Numerical experiments are conducted to illustrate the effectiveness of the proposed model and algorithm. We find that under the loaded route strategy, the improved ant colony algorithm performs better than the basic ant colony algorithm. In addition, the proposed model can effectively characterize the buyer's loss-averse behavior.

基于反向拍卖算法的任务导向型货运无人机任务分配研究

目前,我国社会经济明显复苏,物流经济蓬勃发展,货运无人机在物流领域的作用日益凸显。供应链中的运输任务涉及食品、日用品、大宗补给品等物资,因此选择适应任务类型的货运无人机将直接影响物资的运输效率。同时,在优先完成任务的基础上,货运无人机需要对任务执行成本进行有效控制,这将成为货运无人机任务规划的重要考量。

Optimal Procurement Management by Reverse Auctions for a Price-Setting Newsvendor

In this paper, we study the optimal procurement management by reverse auctions for a price-setting newsvendor(retailer) in a single period setting. The retailer facing price-dependent stochastic demand first designs a procurement contract and then invites the suppliers to bid for this contract in the reverse auction. The winning supplier produces and delivers the demanded quantity.The retailer obtains the procurement quantity and simultaneously determines the retail price. By using the price elasticity of the lost-sales rate, we show that the retailer’s expected profit(excluding the procurement cost) is a concave function of the purchased quantity, which can be used to obtain the optimal procurement and retail pricing decisions for the retailer. Further, when the underlying random term of demand function is normally distributed under left-truncation(at 0), we get the analytical expressions of the purchased quantity and expected profit function for the retailer. Moreover, some numerical examples are given.

An Improved Reverse Auction for Addressing Water Quality in Agricultural Watersheds Using Coupled Simulation-Optimization Models

As nutrients and sediment in agricultural watersheds continue to degrade water quality, attention is increasingly given to reverse auctions to cost-effectively address these pollutants. Typically, reverse auctions include a selection process which depends on both the monetary bid and a ranking of the environmental benefit, where the latter is often approximated using simple models, such as the Universal Soil Loss Equation （USLE）. When the environmental objective is to improve water quality, the cost-effectiveness of such ranking methods cannot always be assured since simple models may poorly approximate the effects on downstream water quality. In this paper, we introduce an alternative reverse auction approach that takes advantage of richer watershed process models and optimization tools that are now much more commonly available. This ＂improved＂ reverse auction allows decision-makers to better consider the cost-effective assignment of conservation practices and to address water quality or other environmental objectives. In a spatially detailed simulation, we demonstrate how this approach can improve the design of a reverse auction for the Raccoon River Watershed in Iowa, and estimate the potential gains from using the simulation-optimization approach relative to simpler ranking methods for selecting bids. We also point out that simple bid ranking schemes may not yield sufficient nutrient reductions to achieve water quality goals but bids areeasily selected to achieve any feasible water quality improvement in the ＂improved＂ auction process.

Application of Online Reverse Auctions in Revenue Management of Airline Company

Based On the online reverse auction formalism in Priceline.com, In this paper,the use of online reverse auctions in airline companies revenue management is highlighted.This research examines the process of online reverse auctions in detail, point out the potential benefits of online reverse auctions. At last we examines how the online reverse auction mechanism design for optimal allocation.

基于拍卖模型的移动群智感知网络激励机制

移动群智感知网络中用户的自私性和不确定性会造成用户参与感知活动的积极性不高及任务完成率较低等问题。针对此问题,提出了一种基于拍卖模型的激励机制。首先,以最大化用户效用为目标,在所提出的逆向拍卖机制(IMRA)中,以任务为中心进行赢标者选择且基于临界价格对赢标者进行报酬支付。然后,利用双向交互的激励机制(UBIM)使临时退出的用户可将未完成的任务转售给新用户,并提出基于二部图的用户匹配算法。实验结果表明,与 TRAC、IMC-SS 机制相比,所提的 IMRA 具有更高的用户平均效用和任务覆盖率,使用UBIM 后也提高了任务完成率。

逆向拍卖保留价建模及数值分析

以著名逆向拍卖网站Priceline为背景,研究在顾客到达为时依强度的泊松过程的条件下,卖方如何动态调整其保留价使其期望收益最大.利用逆向拍卖和收益管理的相似性及逆向拍卖的交易价格是顾客报价的特性,对卖方期望收益建立了最优控制模型,得到如下最优策略的性质:1)最大期望收益函数的单调性及凹性;2)边际期望收益函数的单调性;3)最优价格的凹性.数值分析结果验证了理论分析的正确性,且表明相对于收益管理,顾客报价越接近估价,Priceline的优势越明显.

基于多属性逆向拍卖的博弈分析

对只有一个采购商和多个供应商之间进行的单轮多属性逆向拍卖建立了非合作博弈模型,分析得出投标具有最高质量和最短交货期属性的供应商能够获得最大利润,同时能够给采购商带来最大剩余。因此采购商并不会根据最低投标价格,而是根据投标质量和交货期的最优组合来选择新的供应商。然后,把投标价格看作投标质量和交货期的函数,推导出了供应商的最优投标价格策略,并进一步推出纯子博弈纳什均衡策略。最后,通过算例验证了模型的有效性,并指出采购商在利用多属性逆向拍卖进行采购之前,应该对供应商资格进行审核来决定最后能够参与到拍卖中的供应商数目。

多属性招标拍卖中买卖双方的最优策略研究

电子采购或招标拍卖中单个买方作为招标人且多个卖方作为竞标人,考虑这种环境下的多属性密封投标机制中买卖双方的最优拍卖策略问题.首先,针对买卖双方的效用函数的形式提出了一个更具一般性的多属性拍卖模型.模型中假定买方的价值函数针对不同的非价格属性具有不同的函数形式,卖方的成本函数具有非线性形式.其次,在此模型的基础上分别给出第一评分密封投标机制下买方和卖方的最优拍卖策略.最优策略为卖方提供了参拍物品的价格属性和非价格属性的最优配置方法,为买方提供了根据其关于非价格属性的真实偏好确定评分规则属性权重的依据.然后,从买卖双方不同的角度对拍卖结果进行了比较和分析,重点分析了影响买方在评分规则中隐藏真实偏好行为的相关因素.最后,在假设模型的基础上对竞标人数的增加会激励买方在拍卖中公布真实偏好的结论给出了证明.

逆向多属性拍卖投标策略及收益性分析

逆向多属性拍卖正日渐成为主要的电子采购机制,其中投标策略以及拍卖收益性是拍卖参与人重点关心的问题,首先针对两种典型的逆向多属性拍卖机制——逆向多属性英式拍卖和逆向多属性第一得分密封拍卖,分别给出了投标人的投标策略和买卖双方的期望收益,该结论可以为拍卖参与人提供决策支持.然后证明了拍卖人在这两种典型的逆向多属性拍卖机制和另外两种多属性拍卖机制——多属性第二得分密封拍卖和多属性荷式拍卖中,拍卖期望收益是相等的这一定理,该结论是对期望收益相等定理在多属性拍卖机制中的进一步扩展.