Possible and Necessary Allocations via Sequential Mechanisms

Abstract

A simple mechanism for allocating indivisible resources is sequential allocation in which agents take turns to pick items. We focus on possible and necessary allocation problems, checking whether allocations of a given form occur in some or all mechanisms for several commonly used classes of sequential allocation mechanisms. In particular, we consider whether a given agent receives a given item, a set of items, or a subset of items for five natural classes of sequential allocation mechanisms: balanced, recursively balanced, balanced alternating, strictly alternating and all policies. We identify characterizations of allocations produced balanced, recursively balanced, balanced alternating policies and strictly alternating policies respectively, which extend the well-known characterization by Brams and King [2005] for policies without restrictions. In addition, we examine the computational complexity of possible and necessary allocation problems for these classes.

References in corpus (6)

• Determining Possible and Necessary Winners Given Partial Orders
• Towards a Dichotomy for the Possible Winner Problem in Elections Based on Scoring Rules
• The Computational Complexity of Random Serial Dictatorship
• A Social Welfare Optimal Sequential Allocation Procedure
• How to make the most of a shared meal: plan the last bite first
• Taking the Final Step to a Full Dichotomy of the Possible Winner Problem in Pure Scoring Rules

Cited by in corpus (7)

• Picking Sequences and Monotonicity in Weighted Fair Division
• The Constrained Round Robin Algorithm for Fair and Efficient Allocation
• Welfare of Sequential Allocation Mechanisms for Indivisible Goods
• Parameterized Complexity of Manipulating Sequential Allocation
• Algorithms for Manipulating Sequential Allocation
• Expected Outcomes and Manipulations in Online Fair Division
• Deceased Organ Matching in Australia