Winner determination problem with loss-averse buyers in reverse auctions

doi:10.15302/J-FEM-2017019

Front. Eng

2017, Vol. 4

Issue (2) : 212-220 https://doi.org/10.15302/J-FEM-2017019

RESEARCH ARTICLE

Winner determination problem with loss-averse buyers in reverse auctions

Xiaohu QIAN¹, Min HUANG²(

), Yangyang YU², Xingwei WANG³

¹. College of Information Science and Engineering, State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang 110819, China; Research Institute of Business Analytics & Supply Chain Management, College of Management, Shenzhen University, Shenzhen 518060, China
². College of Information Science and Engineering, State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang 110819, China
³. College of Software, Northeastern University, Shenyang 110819, China

Download: PDF(212 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

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.

Keywords reverse auction loss aversion winner determination improved ant colony algorithm

Corresponding Author(s): Min HUANG

Just Accepted Date: 08 June 2017 Online First Date: 05 July 2017 Issue Date: 17 July 2017

Cite this article:

Xiaohu QIAN,Min HUANG,Yangyang YU, et al. Winner determination problem with loss-averse buyers in reverse auctions[J]. Front. Eng, 2017, 4(2): 212-220.

URL:

https://academic.hep.com.cn/fem/EN/10.15302/J-FEM-2017019
https://academic.hep.com.cn/fem/EN/Y2017/V4/I2/212

Fig.1 Description of the winner determination problem

Model parameters
$i$ :	Index of suppliers, $i = 1, 2, …, n$
$c i$ :	Unit price of supplier $i$
$k$ :	Fixed cost of choosing a supplier
$q$ :	Penalty cost if the delivery delays
$L$ :	Total demand of the buyer
$Q i$ :	Maximum capacity of supplier $i$
$d i$ :	Expected delivery of supplier $i$
$p i$ :	Delay probability of supplier $i$
$P 1$ :	Average delay probability of all selected suppliers
$C m$ :	Expected procurement cost of the buyer
$T m$ :	Expected delivery of the buyer
Behavior Parameters
$α$ :	Gain preference
$β$ :	Loss preference
$λ$ :	Degree of loss aversion
$γ$ :	Parameter of weighting functions for gain
$δ$ :	Parameter of weighting functions for loss
Decision variables
$x i$ :	Binary variable, $x i = 1$ if supplier $i$ is selected, otherwise, $x i = 0$
$y i$ :	Integer variable, supply quantity of supplier $i$

Tab.1

$j$ :	Index of ants, $j = 1, 2, …, m$	$ρ$ :	Pheromone evaporation rate, $ρ ∈ [0, 1]$
$A$ :	Sets of suppliers allowed to be selected	$τ max ?$ :	Maximum pheromone trail
$p i j$ :	Probability of supplier $i$ selected by ant $j$	$τ min ?$ :	Minimum pheromone trail
$p i j$ :	Probability of supplier $i$ selected by ant $j$	$Q$ :	Total amount of pheromone presented on potential suppliers
$τ i$ :	Pheromone trail of supplier $i$	$Q$ :	Total amount of pheromone presented on potential suppliers
$η i$ :	Heuristic information of supplier $i$	$t$	Index of loops
$a$ :	Importance parameter of pheromone trail	$h j t$ :	Number of selected suppliers for loop $t$ by ant $j$
$b$ :	Importance parameter of heuristic information	$h j t$ :	Number of selected suppliers for loop $t$ by ant $j$
$b$ :	Importance parameter of heuristic information	$f$	Initial amount of pheromone
$k$ :	Number of current iterations	$N P$ :	Size of population
$g i$ :	Number of currently selected suppliers	$N G$ :	Number of total loops

Tab.2

N^a)	Alg ^b)	$N P$	$N G$	$a$	$b$	$ρ$	$f$	$Q$	$τ min ?$	$τ max ?$	WS	BS	Mean	SD	Time
10	EM	- ^c)	-	-	-	-	-	-	-	-	80.94	80.94	80.94	-	7092.64
	ACA-LRS	70	1000	1.0	0.5	0.6	2.5	13	0.4	3.2	77.61	80.94	78.83	1.19	1.95
	IACA-LRS	50	300	0.9	0.5	0.5	2.5	15	0.5	3.8	80.94	80.94	80.94	0	0.42
20	EM	-	-	-	-	-	-	-	-	-	-	-	-	-	-
	ACA-LRS	85	1700	1.5	1.3	0.6	4.2	15	0.5	4.5	142.79	146.25	144.62	3.24	9.65
	IACA	70	1500	1.5	1.2	0.7	4.0	17	0.6	5	145.78	149.40	147.19	1.73	6.42
30	EM	-	-	-	-	-	-	-	-	-	-	-	-	-	-
	ACA-LRS	95	2000	1.1	1.2	0.6	4.0	17	0.4	4.5	120.74	131.05	125.66	5.29	26.70
	IACA-LRS	80	1500	1.3	1.2	0.5	4.3	17	0.4	5	129.58	131.05	130.24	3.28	20.16

Tab.3 Results obtained with different algorithms under different scales

$T m$	$C m$	$C 0$	$S$	BS	WS	Mean	Time
6	44500	44553.0	3000	-309.94	-309.94	-309.94	0.42
7	44500	44514.0	2500	-259.06	-259.06	-259.06	0.42
8	44500	44514.0	1900	-204.06	-204.06	-204.06	0.42
9	44500	44208.0	1600	-69.81	-69.81	-69.81	0.42
10	44500	44282.5	1000	80.94	80.94	80.94	0.42
11	44500	44208.0	600	181.44	181.44	181.44	0.42
12	44500	44208.0	300	256.81	256.81	256.81	0.42
13	44500	44208.0	100	280.33	280.33	280.33	0.42
14	44500	44208.0	0	291.5	291.5	291.5	0.42
15	44500	44208.0	0	291.5	291.5	291.5	0.42

Tab.4 Effects of expected delivery on the optimal solutions

$C m$	$T m$	$C 0$	$S$	BS	WS	Mean	Time
44000	10	44208.5	1000	-551.69	-551.69	-551.69	0.42
44100	10	44208.5	1000	-359.65	-359.65	-359.65	0.42
44200	10	44208.5	1000	-186.74	-186.74	-186.74	0.42
44300	10	44208.5	1000	-129.61	-129.61	-129.61	0.42
44400	10	44208.5	1000	-33.02	-33.02	-33.02	0.42
44500	10	44208.5	1000	80.95	80.95	80.95	0.42
44600	10	44208.5	1000	194.90	194.90	194.90	0.42
44700	10	44208.5	1000	308.86	308.86	308.86	0.42
44800	10	44208.5	1000	422.81	422.81	422.81	0.42
44900	10	44208.5	600	536.77	536.77	536.77	0.42

Tab.5 Effects of expected procurement cost on the optimal solutions

Tab.6 Results obtained with different models under different scales

Fig.2 Comparison analysis of different models under IACA-LRS

1	Banerji A, Gupta N (2014). Detection, identification, and estimation of loss aversion: Evidence from an auction experiment. American Economic Journal: Microeconomics, 6(1): 91–133
2	Cachon G P, Zhang F (2006). Procuring fast delivery: Sole sourcing with information asymmetry. Management Science, 52(6): 881–896
3	De Boer L, Labro E, Morlacchi P (2001). A review of methods supporting supplier selection. European Journal of Purchasing & Supply Management, 7(2): 75–89
4	De Vries S, Vohra R V (2003). Combinatorial auctions: A survey. INFORMS Journal on Computing, 15(3): 284–309
5	Escudero L F, Landete M, Marín A (2009). A branch-and-cut algorithm for the winner determination problem. Decision Support Systems, 46(3): 649–659
6	Hishamuddin H, Sarker R A, Essam D (2013). A recovery model for a two-echelon serial supply chain with consideration of transportation disruption. Computers & Industrial Engineering, 64(2): 552–561
7	Ho W, Xu X, Dey P K (2010). Multi-criteria decision making approaches for supplier evaluation and selection: A literature review. European Journal of Operational Research, 202(1): 16–24
8	Huang M, Qian X, Fang S C, Wang X (2016). Winner determination for risk aversion buyers in multi-attribute reverse auction. Omega, 59: 184–200
9	Jackson C (1976). Technology for spectrum markets. Ph.D. thesis, Department of Electrical Engineering, Massachusetts Institute of Technology, Cambridge, MA
10	Kahneman D, Tversky A (1979). Prospect theory: An analysis of decision under risk. Econometrica, 47(2): 263–291
11	Ma Z, Kwon R H, Lee C G (2010). A stochastic programming winner determination model for truckload procurement under shipment uncertainty. Transportation Research Part E: Logistics and Transportation Review, 46(1): 49–60
12	Qian X, Fang S C, Huang M, An Q, Wang X (2017). Reverse auctions with regret-anticipated bidders. Annals of Operations Research
13	Qian X, Fang S C, Huang M, Nie T, Wang X (2016). Bidding decisions with nonequilibrium strategic thinking in reverse auctions. Working Paper, 1–28
14	Rassenti S J, Smith V L, Bulfin R L (1982). A combinatorial auction mechanism for airport time slot allocation. Bell Journal of Economics, 13(2): 402–417
15	Rekik M, Mellouli S (2012). Reputation-based winner determination problem for combinatorial transportation procurement auctions. Journal of the Operational Research Society, 63(10): 1400–1409
16	Remli N, Rekik M (2013). A robust winner determination problem for combinatorial transportation auctions under uncertain shipment volumes. Transportation Research Part C: Emerging Technologies, 35: 204–217
17	Sandholm T (2002). Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135(1): 1–54
18	Singh R K, Benyoucef L (2011). A fuzzy TOPSIS based approach for e-sourcing. Engineering Applications of Artificial Intelligence, 24(3): 437–448
19	Srinivasan S, Stallert J, Whinston A B (1998). Portfolio trading and electronic networks. Working Paper, 1–26
20	Tang C S, Zhang K, Zhou S X (2015). Incentive contracts for managing a project with uncertain completion time. Production and Operations Management, 24(12): 1945–1954
21	Tunca T I, Wu D J, Zhong F (2014). An empirical analysis of price, quality, and incumbency in procurement auctions. Manufacturing & Service Operations Management: M & SOM, 16(3): 346–364
22	Tversky A, Kahneman D (1992). Advances in prospect theory: Cumulative representation of uncertainty. Journal of Risk and Uncertainty, 5(4): 297–323
23	Wang X, Wang X, Che H, Li K, Huang M, Gao C (2015). An intelligent economic approach for dynamic resource allocation in cloud services. IEEE Transactions on Cloud Computing, 3(3): 275–289
24	Wang X, Sun J, Li H, Wu C, Huang M (2013). A reverse auction based allocation mechanism in the cloud computing environment. Applied Mathematics & Information Sciences, 7(1): 75–84
25	Zhang B, Yao T, Friesz T L, Sun Y (2015). A tractable two-stage robust winner determination model for truckload service procurement via combinatorial auctions. Transportation Research Part B: Methodological, 78: 16–31
26	Zhou S X, Tao Z, Zhang N, Cai G G (2016). Procurement with reverse auction and flexible noncompetitive contracts. Decision Sciences, 47(3): 554–581

[1]	Xianjia WANG, Shiwei WU. Mechanism design of reverse auction on concession period and generalized quality for PPP projects[J]. Front. Eng, 2017, 4(2): 156-170.

Viewed

Full text

Abstract

Cited

Shared

Discussed