Enchère combinatoire - Combinatorial auction
.jpg)
Une enchère combinatoire est un type de marché intelligent dans lequel les participants peuvent placer des offres sur des combinaisons d'articles hétérogènes discrets, ou « packages », plutôt que sur des articles individuels ou des quantités continues. Ces lots peuvent également être appelés lots et l'ensemble de l'enchère est une enchère multi-lots . Les enchères combinatoires sont applicables lorsque les enchérisseurs ont des évaluations non additives sur des lots d'articles, c'est-à-dire qu'ils évaluent des combinaisons d'articles plus ou moins que la somme de leurs évaluations des éléments individuels de la combinaison.
Les enchères combinatoires simples sont utilisées depuis de nombreuses années dans les enchères immobilières , où une procédure courante consiste à accepter des offres pour des lots d'articles. Ils ont été utilisés récemment pour le transport de camions complets, les itinéraires de bus, les achats industriels et l' attribution de spectre radio pour les communications sans fil. Ces dernières années, les équipes d'approvisionnement ont appliqué des enchères combinatoires inversées dans l'achat de biens et de services. Cette application est souvent appelée optimisation de l'approvisionnement. Étant donné que l' approvisionnement en construction implique souvent des négociations sur plusieurs composants, des enchères inversées combinatoires sont suggérées pour réduire les coûts dans cette industrie.
Bien qu'elles permettent aux enchérisseurs d'être plus expressifs, les enchères combinatoires présentent à la fois des défis informatiques et théoriques par rapport aux enchères traditionnelles. Un exemple de problème de calcul est de savoir comment déterminer efficacement l'allocation une fois que les offres ont été soumises au commissaire-priseur. C'est ce qu'on appelle le problème de détermination du gagnant.
Le problème de détermination du gagnant peut être formulé comme suit : étant donné un ensemble d'enchères dans une enchère combinatoire, trouver une allocation d'articles aux enchérisseurs, y compris la possibilité que le commissaire-priseur conserve certains articles, qui maximise ses revenus. Ce problème est difficile pour les grandes instances. Plus précisément, il est NP-difficile , ce qui signifie qu'il est conjecturé qu'il n'existe pas d' algorithme en temps polynomial qui trouve l'allocation optimale. Le problème d'enchères combinatoires peut être modélisé comme un problème d' emballage d'ensembles . Par conséquent, de nombreux algorithmes ont été proposés pour trouver des solutions approchées aux problèmes d'enchères combinatoires. Par exemple, Hsieh (2010) a proposé une approche de relaxation lagrangienne pour les problèmes d'enchères inversées combinatoires.
Bon nombre de ces aspects des enchères combinatoires, y compris certains exemples concrets, sont également abordés dans le livre complet édité par Cramton, Shoham et Steinberg (2006).
Histoire
Les enchères combinatoires ont été proposées pour la première fois par Rassenti, Smith et Bulfin (1982) pour l'attribution de créneaux d'atterrissage aux aéroports . Leur document introduit de nombreuses idées clés sur les ventes aux enchères combinatoires, y compris la formulation de programmation mathématique du problème du commissaire- priseur, le lien entre le problème de la détermination du gagnant et d'emballage de jeu problème, la question de la complexité de calcul, l'utilisation des techniques de l' économie expérimentale pour tester combinatoire enchères, et prise en compte des questions de compatibilité des incitations et de révélation de la demande dans les enchères combinatoires.
Ventes d'horloges combinatoires
Un cas particulier d'enchère combinatoire est l'enchère combinatoire au cadran (CCA), qui combine une enchère au cadran, au cours de laquelle les enchérisseurs peuvent fournir leurs confirmations en réponse à la hausse des prix, avec une enchère par offre scellée ultérieure, dans laquelle les enchérisseurs soumettent des offres sous pli scellé. . Le commissaire-priseur utilise les offres finales pour calculer la meilleure allocation de valeur et les paiements Vickrey .
Voir également
Les références
Lectures complémentaires
- Peter Cramton, Yoav Shoham et Richard Steinberg (2006). Enchères combinatoires . MIT Appuyez sur . ISBN 0-262-03342-9 . Un livre contributif avec une large couverture du sujet.
- de Vries, S.; Vohra, R. (2003). « Enchères combinatoires : Une enquête » (PDF) . Journal INFORMS sur l'informatique . 15 (3) : 284-309. CiteSeerX 10.1.1.23.8046 . doi : 10.1287/ijoc.15.3.284.16077 . ISSN 1526-5528 . Un peu daté, mais une enquête classique.
- Vazirani, Vijay V. ; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Théorie algorithmique des jeux (PDF) . Cambridge, Royaume-Uni : Cambridge University Press. ISBN 0-521-87282-0.. Un livre contribué avec un bon chapitre d'introduction sur les enchères combinatoires du point de vue de la théorie informatique ; voir chapitre 11.
- Rassenti, Stephen J. ; Smith, Vernon L.; Bulfin, Robert L. (1982). "Un mécanisme d'enchères combinatoires pour l'attribution de créneaux horaires à l'aéroport" (PDF) . Journal d'économie de Bell . 13 (2) : 402-417. doi : 10.2307/3003463 . JSTOR 3003463 . Les premiers travaux qui ont popularisé l'idée d'une vente aux enchères combinatoire.
- Rothkopf, M.; Pekec, A.; Harstad, R. (1998). « Enchères combinatoires gérables informatiquement ». Sciences de gestion . 44 (8) : 1131-1147. CiteSeerX 10.1.1.723.9753 . doi : 10.1287/mnsc.44.8.1131 . Un premier article influent sur les considérations informatiques.
- Hammami, Farouk ; Rekik, Monia; Coelho, Leandro C. (2019). "Approches de solutions exactes et heuristiques pour le problème de construction d'offres dans les enchères d'approvisionnement en transport avec une flotte hétérogène". Recherche sur les transports Partie E : Examen de la logistique et des transports . 127 : 150-177. doi : 10.1016/j.tre.2019.05.009 . Une application d'enchères combinatoires pour l'approvisionnement en services de transport.
- Hsieh, Fu-Shiung (2010). « Enchère inversée combinatoire basée sur la révélation des multiplicateurs lagrangiens » (PDF) . Systèmes d'aide à la décision . 48 (2) : 323-330. doi : 10.1016/j.dss.2009.08.009 .
- Shoham, Yoav; Leyton-Brown, Kevin (2009). Systèmes multi-agents : fondements algorithmiques, théoriques des jeux et logiques . New York : Cambridge University Press . ISBN 978-0-521-89943-7.Un aperçu sous forme de manuel ; voir la section 11.3. Téléchargeable gratuitement en ligne .