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 motivate...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.展开更多
文章研究多服务器、多客户端联邦学习(federated learning,FL)场景中的激励机制,并将任务分配和定价问题建模为多个逆向拍卖问题。根据切比雪夫(Chebyshev)定理对客户端每一轮的本地模型性能进行评估,并进一步利用指数衰减函数评估其本...文章研究多服务器、多客户端联邦学习(federated learning,FL)场景中的激励机制,并将任务分配和定价问题建模为多个逆向拍卖问题。根据切比雪夫(Chebyshev)定理对客户端每一轮的本地模型性能进行评估,并进一步利用指数衰减函数评估其本地模型的总体性能;设计基于本地模型性能的逆向拍卖(local model performance based reverse auction,LPRA)算法解决任务分配和定价问题以激励更多高性能的客户端参与,并从理论上证明LPRA算法满足个体理性、真实性和计算高效性;通过仿真实验验证LPRA算法的有效性。展开更多
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 reso...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.展开更多
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 behav...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.展开更多
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...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.展开更多
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 reve...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.展开更多
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 aucti...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.展开更多
电动汽车通过泛在电力物联网(Ubiquitous Power Internet of Things, UPIoT)作为移动负载向电力系统提供电力储备,在增强电网稳定性等方面被认为具有巨大潜力,随着电动汽车数量的极速增涨,基于电动汽车的能源交易引起了能源供应商的广...电动汽车通过泛在电力物联网(Ubiquitous Power Internet of Things, UPIoT)作为移动负载向电力系统提供电力储备,在增强电网稳定性等方面被认为具有巨大潜力,随着电动汽车数量的极速增涨,基于电动汽车的能源交易引起了能源供应商的广泛关注。基于此,提出一种基于反向拍卖的电动汽车能源交易激励方案。在定价过程中引入多用户协商博弈框架,进而制定电动汽车的最优定价支付策略;并以最大化能源聚合商的收益为目标,提出了预算受限的车辆选择算法。经与已有方案进行仿真对比,所提方案在降低能源聚合商成本、提高能源聚合商收益和激励车辆放电方面都具有较好的性能。展开更多
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. How...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.展开更多
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 con...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.展开更多
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 inc...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.展开更多
文摘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.
文摘文章研究多服务器、多客户端联邦学习(federated learning,FL)场景中的激励机制,并将任务分配和定价问题建模为多个逆向拍卖问题。根据切比雪夫(Chebyshev)定理对客户端每一轮的本地模型性能进行评估,并进一步利用指数衰减函数评估其本地模型的总体性能;设计基于本地模型性能的逆向拍卖(local model performance based reverse auction,LPRA)算法解决任务分配和定价问题以激励更多高性能的客户端参与,并从理论上证明LPRA算法满足个体理性、真实性和计算高效性;通过仿真实验验证LPRA算法的有效性。
基金Supported by the National Natural Science Foundation of China(71971188)the Humanities and Social Science Fund of Ministry of Education of China(22YJCZH086)+1 种基金the Natural Science Foundation of Hebei Province(G2022203003)the S&T Program of Hebei(22550301D)。
文摘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.
基金sponsored by the Distinguished Young Scholars Award of NSFC Grant #71325002the Major International Joint Research Project of NSFC Grant #71620107003+2 种基金the Foundation for Innovative Research Groups of NSFC Grant #61621004111 Project Grant #B16009the Fundamental Research Funds for State Key Laboratory of Synthetical Automation for Process Industries Grant #2013ZCX11
文摘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.
基金Supported by Hunan Provincial Department of Education Fund(20A485,19K093)National Center for Applied Mathematics in Hunan Province。
文摘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.
文摘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.
文摘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.
文摘电动汽车通过泛在电力物联网(Ubiquitous Power Internet of Things, UPIoT)作为移动负载向电力系统提供电力储备,在增强电网稳定性等方面被认为具有巨大潜力,随着电动汽车数量的极速增涨,基于电动汽车的能源交易引起了能源供应商的广泛关注。基于此,提出一种基于反向拍卖的电动汽车能源交易激励方案。在定价过程中引入多用户协商博弈框架,进而制定电动汽车的最优定价支付策略;并以最大化能源聚合商的收益为目标,提出了预算受限的车辆选择算法。经与已有方案进行仿真对比,所提方案在降低能源聚合商成本、提高能源聚合商收益和激励车辆放电方面都具有较好的性能。
基金This work was supported in part by the National Natural Science Foundation of China under Grant Nos. 61702380, 61202393, and 61701216, the CPSF (China Postdoctoral Science foundation) under Grant No. 2012M521797, the International Cooperation Foundation of Shaanxi Province of China under Grant No. 2013KW01-02, the International Postdoctoral Exchange Fellowship Program 2013 under Grant No. 57 funded by the Office of China Postdoctoral Council, and Shenzhen Science, Technology and Innovation Commission Basic Research Project under Orant Nos. JCYJ 20160531190935987 and JCYJ 20160531191011045.
文摘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.
基金supported by the National Natural Science Foundation of China (Grant Nos. 71231007 and 71373222)
文摘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.
基金This research was funded in part from support received from the US Environmental Protection Agency's Targeted Watersheds Grants Program (Project #WS97704801), the National Science Foundation's Dynamics of Coupled Natural and Human Systems of the U.S. (Project #DEB1010259-CARD-KLIN), and the US Department of Agriculture-National Institute of Food and Agriculture's Coordinated Agricultural Project (Project #20116800230190-CARD).
文摘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.