Bayesian Fair Division: Truthfulness in Picking Sequence with Correlated Valuations
2026-08-07 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study a method where people take turns choosing items, which isn't usually honest because people can game the system if they know exactly what others value. They investigate if honesty improves when people only have partial, noisy knowledge of others' preferences, focusing on two participants. They find that when two people's preferences are somewhat similar, being truthful is a stable strategy. However, with more than two participants, different ways to cheat appear, showing limits to honesty in these turn-based methods.
Sequential allocationFair divisionIndivisible goodsTruthfulnessBayesian modelBayesian Nash equilibriumValuation correlationMechanism designManipulationGame theory
Authors
Xiaolin Bu, Biaoshuai Tao
Abstract
Sequential allocation mechanisms contain a class of widely studied mechanisms (e.g., round-robin) in the fair division of indivisible goods, where agents take turns picking items in a predefined picking order. It is known that the sequential allocation mechanisms are not truthful: when an agent's most preferred item is not valued by others, the agent may manipulate the mechanism by choosing to defer picking that item and instead competing for another slightly less preferred item that is valued by others. Two underlying reasons are that each agent has perfect knowledge of the others' valuations, and each item's value to each agent can differ significantly. Will the mechanism be more truthful when each agent only has partial information about the others' valuations, which are known to be roughly consistent? This naturally motivates the study of the Bayesian fair division model. In this paper, we answer this question affirmatively for two agents. Under the Bayesian model, we precisely characterize the extent of this ``rough consistency'' that incentivizes agents' truth-telling. In particular, we show that for the case of two agents, when the valuations are positively correlated, truth-telling forms a Bayesian Nash equilibrium under the sequential allocation mechanisms. However, we show that truthfulness fails to extend to the setting with more than two agents. For more than two agents, we reveal a new type of manipulation that is different from the above-mentioned manipulation that defers a highly valued but less competitive item. Our result reveals a fundamental limitation on the truthfulness of sequential mechanisms.