A Budget-balanced, Incentive-compatible Scheme for Social Choice

Many practical scenarios involve solving a social choice problem: a group of self-interested agents have to agree on an outcome that best fits their combined preferences. We assume that each outcome presents a certain utility to an agent and that the best outcome is the one that maximizes the sum of these utilities. We call a mechanism for solving social choice problems incentive-compatible if for each agent, the behavior that maximizes its own utility is also the one that maximizes the group’s utility. One way to achieve incentive-compatibility is the Vickrey-Clarke-Groves (VCG) tax ([5]) mechanism. However, it produces a surplus of taxes that cannot be redistributed to the agents and can severely reduce agents’ utilities. Game theory has shown that it is not possible to have a general scheme that is incentive-compatible, budget-balanced and guarantees a Pareto-efficient solution. We present a scheme that sacrifices Pareto-efficiency to achieve budget balance while being both incentive-compatible and individually rational. On randomly generated social choice problems, the scheme results in significantly better overall agent utility than the VCG tax mechanism.