Group for Research in Decision Analysis

G-2014-80

A heuristic optimization of Bayesian incentive-compatible cake-cutting

, , and

Cake-cutting is a metaphor for problems where a principal agent has to fairly allocate resources. Such problems cover various areas of operations research and management science, like, for instance, shift scheduling with employees' preferences. Recent work focuses on optimizing social efficiency while guaranteeing fairness, but ignore incentive-compatibility constraints, or vice versa. In this paper, we present a new approach to heuristic mechanism design with Bayesian incentive-compatibility. As opposed to other papers, we do not allow monetary transfer. Our approach relies on the revelation principle and the computation of Bayesian-Nash equilibria using the so-called return function. This computation consists in tracking a best-reply dynamics of return function, which are mappings of action to probability distribution on outcomes, instead of the more classical but harder-to-compute best-reply dynamics of strategies. In essence, our mechanism-design approach explores a parameterized class of revelation mechanisms, which we know by construction to be Bayesian incentive-compatible. We highlight the efficiency of this approach through numerical results on instances of respectively 2, 5 and 20 agents.

, 14 pages