Solving a dynamic combinatorial auctions problem by a hybrid metaheuristic based on a fuzzy dominance relation
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 207-221.

This paper introduces a bi-objective winner determination problem which is based on English auctions. Most models of combinatorial auctions (winner determination problem) do not allow the bidder to update his offer, due to the fact that these mechanisms are static. However in reality bidders are in rough competition while there is time for auction. In this work we give a mathematical formulation of the dynamic model of the bi-objective winner determination problem, where the objectives are: (i) maximization of the total income, (ii) maximization of the number of items sold. This problem is based on the English auction mechanism, which allows bidders to renew their bids until the end of the exercise period. Then the solution is proposed by giving an algorithm based on an hybridization of a metaheuristic with a fuzzy dominance relation. A numerical experimentation using this algorithm on simulated data gives rise to satisfactory results.

DOI : 10.1051/ro/2018051
Classification : 90C27, 90C70, 90C59
Mots-clés : Multi-objective combinatorial auctions, winner determination problem, fuzzy dominance, exercise period, dynamic model
Asli, Larbi 1 ; Aïder, Méziane 1 ; Talbi, El-Ghazali 1

1 
@article{RO_2019__53_1_207_0,
     author = {Asli, Larbi and A{\"\i}der, M\'eziane and Talbi, El-Ghazali},
     title = {Solving a dynamic combinatorial auctions problem by a hybrid metaheuristic based on a fuzzy dominance relation},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {207--221},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {1},
     year = {2019},
     doi = {10.1051/ro/2018051},
     zbl = {1414.90300},
     mrnumber = {3911628},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2018051/}
}
TY  - JOUR
AU  - Asli, Larbi
AU  - Aïder, Méziane
AU  - Talbi, El-Ghazali
TI  - Solving a dynamic combinatorial auctions problem by a hybrid metaheuristic based on a fuzzy dominance relation
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 207
EP  - 221
VL  - 53
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2018051/
DO  - 10.1051/ro/2018051
LA  - en
ID  - RO_2019__53_1_207_0
ER  - 
%0 Journal Article
%A Asli, Larbi
%A Aïder, Méziane
%A Talbi, El-Ghazali
%T Solving a dynamic combinatorial auctions problem by a hybrid metaheuristic based on a fuzzy dominance relation
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 207-221
%V 53
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2018051/
%R 10.1051/ro/2018051
%G en
%F RO_2019__53_1_207_0
Asli, Larbi; Aïder, Méziane; Talbi, El-Ghazali. Solving a dynamic combinatorial auctions problem by a hybrid metaheuristic based on a fuzzy dominance relation. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 207-221. doi : 10.1051/ro/2018051. http://www.numdam.org/articles/10.1051/ro/2018051/

[1] A. Anderson, M. Tenhunen and F. Ygge, Integer programming for combinatorial auctions winner determination. In: Proc. of 4th International Conference on Multi-Agent Systems. IEEE Computer Society Press (2000) 39–46. | DOI

[2] D. Boughaci, B. Benhamou and H. Drias, Memetic Algorithms for the Optimal Winner Determination Problems in Combinatorial Auctions. J. Soft Comput., 13 (2009) 905–917. | DOI

[3] T. Buer and H. Kopfer, A Pareto-metaheuristic for a bi-objective winner determination problem in a combinatorial reverse auction. Comput. Oper. Res., 41 (2014) 208–220. | DOI | MR | Zbl

[4] D. Chakraborty, D. Guha and B. Dutta, Multi-objective optimization problem under fuzzy rule constraints using particle swarm optimization. Soft Comput., 20 (2016) 2245–2259. | DOI

[5] M. Ehrgott, Multicriteria Optimization, 2nd edition. Springer, Berlin Heidelberg New York (2005). | MR | Zbl

[6] S. Ganguly, N.C. Sahoo and D. Das, Multi-objective particle swarm optimization based on fuzzy-Pareto-dominance for possibilistic planning of electrical distribution systems incorporating distributed generation. Fuzzy Sets Syst., 213 (2013) 47–73. | DOI | MR

[7] R. Garg and A.-K. Singh, Multi-objective workflow grid scheduling using #-fuzzy dominance sort based discrete particle swarm optimization. J. Supercomput., 68 (2014) 709–732. | DOI

[8] Y. Guo, A. Lim, B. Rodrigues and Y. Zhu, Heuristics for a bidding problem. Comput. Oper. Res., 23 (2006) 2179–2188. | DOI | Zbl

[9] A. Holland and B. O’Sullivan, Towards fast Vickrey pricing using constraint programming. Artif. Intell. Rev., 21 (2004) 335–352. | DOI | Zbl

[10] N.E.A. Khalid, N.A. Bakar, F.Sh. Ismail and N.S.M. Dout, Multi-objective optimization using fuzzy evolutionary strategies optimization. Int. J. Syst. Appl. Eng. Dev., 5(6) (2011) 728–737.

[11] M. Köppen, R. Vicente-Garcia and B. Nickolay, Fuzzy-pareto-dominance and its application in evolutionary multi-objective optimization. Lect. Notes Comput. Sci., 3410 (2005) 399–412. | DOI | Zbl

[12] R.L. Leskelä, Bidder Support In Iterative Multiple-Unit Combinatorial Auctions. Ph.D. thesis. Helsinki University of Technology, Finland (2009).

[13] J. Levin and A. Skrzypacz, Are dynamic Vickrey auctions practical? Properties of the combinatorial clock auction. Economic Policy Research Discussion Paper. Stanford Institute 14–002 (2014).

[14] K. Leyton-Brown, M. Tennenholtz and Y. Shoham, An algorithm for multi-unit combinatorial auctions. In: Proc. of the 17th National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence (2000) 56–61.

[15] N. Nisan, Bidding and allocation in combinatorial auctions. In: Proceedings of the ACM Conference on Electronic Commerce (EC-00), Minneapolis. ACM SIGecom, ACM Press (2000)1–12.

[16] J. Razmia, E. Jafarian and S. Hassanzadeh-Amin, An intuitionistic fuzzy goal programming approach for finding pareto-optimal solutions to multi-objective programming problems. Expert Syst. Appl., 65 (2016) 181–193. | DOI

[17] R. Saborido, Ana B. Ruiz, J.D. Bermdez, E. Vercher and M. Luque, Evolutionary multi-objective optimization algorithms for fuzzy portfolio selection. Appl. Soft Comput., 39 (2016) 48–63. | DOI

[18] N.C. Sahoo, S. Ganguly and D. Das, Fuzzy-Pareto-dominance driven possibilistic model based planning of electrical distribution systems using multi-objective particle swarm optimization. J. Expert Syst. Appl., 39 (2012) 881–893. | DOI

[19] M. Sakawa, K. Kato, H. Sunada and T. Shibano, Fuzzy programming for multiobjective 0–1 programming problems through revised genetic algorithms. Eur. J. Oper. Res., 97 (1997) 149–158. | DOI | Zbl

[20] T. Sandholm, S. Suri, A. Gilpin and D. Levine, CABOB; A fast optimal algorithm for winner determination in combinatorial auctions. Manag. Sci., 51 (2005) 374–390. | DOI | Zbl

[21] P. Sariddichainunta and K. Sinapiromsaran, The winner determination model and computation for linear arrangement of booth auction. Inf. Technol. J., 7 (2011) 46–51.

[22] E. Zitzler, Evolutionary algorithms for multiobjective optimization: methods and applications. Ph.D. thesis, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland (1999).

Cité par Sources :