Groupe d’études et de recherche en analyse des décisions

G-2014-80

A heuristic optimization of Bayesian incentive-compatible cake-cutting

, et

Le partage de gâteau est une métaphore très utilisée pour décrire les problèmes où un agent principal doit allouer des ressources de manière juste. De tels problèmes couvrent une grande variété de domaines de recherche opérationnelle, comme, par exemple, la construction d'horaires personnalisés avec les préférences des employés. Plusieurs travaux récents cherchent à maximiser le bien-être social tout en garantissant l'équité (Cohler et al. (2001), Caragiannis et al. (2011), Bei et al. (2012)), mais ignorent les contraintes de compatibilité avec les incitatifs. À l'inverse, Mossel et Tamuz (2010) et Chen et al. (2013) s'intéressent à l'équité et les incitatifs sans considérer le bien-être social. Dans ce papier, nous présentons une approche pour optimiser un compromis d'équité et de bien-être social, tout en satisfaisant les contraintes d'incitatifs bayésiens. Cette approche repose sur le principe de révélation de Gibbard (1973) et Myerson (1979), et sur le calcul des équilibres de Bayes-Nash proposé par Hoang et al. (2014). Ce calcul consiste à simuler une dynamique de meilleures réponses de fonctions de retour, qui associent à toute action une distribution probabiliste de résultats, plutôt que de simuler une dynamique de meilleures réponses des stratégies, comme cela est fait de façon plus classique. On peut alors explorer une classe de mécanismes révélés paramétrés, qui, par construction, sont compatibles avec les incitatifs bayésiens. Nous montrons l'efficacité de l'approche avec des instances de 2, 5 et 20 joueurs.

, 14 pages