A heuristic optimization of Bayesian incentive-compatible cake-cutting. (November 2016)

• Record Type: Journal Article
• Authors: Hoang, Lê Nguyên; Soumis, François; Zaccour, Georges
• Is Part Of: Computers & operations research. Volume 75(2016)
• Page Start: 76
• Page End: 82
• Publication Date: 2016-11
• Subjects: Cake-cutting problem -- Fairness -- Incentive compatibility -- Return function; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.05.009
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Abstract : Highlights: The problem is how to divide a cake between agents having heterogeneous preferences. The mechanism designer aims at an efficient and fair division. We use the concept of return function to determine equilibrium allocation. We show that all agents behave truthfully in reporting their preferences. Numerical illustrations are given for different numbers of players.