---
title: "Possible and Necessary Allocations via Sequential Mechanisms"
authors:
  - "Haris Aziz"
  - "Toby Walsh"
  - "Lirong Xia"
doi: ""
url: "https://ijcai.org/proceedings/2015/72"
pdf: "https://ijcai.org/proceedings/2015/0072.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "468-473"
track: "Main Track"
keywords:
---

# Possible and Necessary Allocations via Sequential Mechanisms

Haris Aziz, Toby Walsh, Lirong Xia

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 468-473.

## 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 natural classes of sequential allocation mechanisms: balanced, recursively balanced, balanced alternation, and strict alternation. We present characterizations of the allocations that result respectively from the classes, 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.