Possible and Necessary Allocations via Sequential Mechanisms

Aziz, Haris; Walsh, Toby; Xia, Lirong

Possible and Necessary Allocations via Sequential Mechanisms

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. 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.

Haris Aziz, Toby Walsh, and Lirong Xia. 2015. Possible and Necessary Allocations via Sequential Mechanisms. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 468–473. https://ijcai.org/proceedings/2015/72

@inproceedings{ijcai2015p72,
  title     = {Possible and Necessary Allocations via Sequential Mechanisms},
  author    = {Aziz, Haris and Walsh, Toby and Xia, Lirong},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {468--473},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/72},
}

TY  - CPAPER
TI  - Possible and Necessary Allocations via Sequential Mechanisms
AU  - Aziz, Haris
AU  - Walsh, Toby
AU  - Xia, Lirong
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 468
EP  - 473
UR  - https://ijcai.org/proceedings/2015/72
ER  -