Allocating Indivisible Items in Categorized Domains
Authors: Erika Mackin, Lirong Xia
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We initiate a research agenda of mechanism design for categorized domain allocation problems (CDAPs)... We first characterize serial dictatorships by a minimal set of three axiomatic properties: strategy-proofness, non-bossiness, and category-wise neutrality. Then, we propose a natural extension of serial dictatorships called categorial sequential allocation mechanisms (CSAMs)... We fully characterize the worst-case rank efficiency of CSAMs for optimistic and pessimistic agents. Proof sketch: For any optimistic agents, the upper bound is calculated by counting how many bundles must be ranked below the final allocation once no agent can interrupt her from choosing the top bundle (among available ones). For pessimistic agents, in each step j we know that at least kj,Oj(l) 1 other bundles must be ranked below the final allocation. The proof for the matching lower bounds is by construction and is quite involved. |
| Researcher Affiliation | Academia | Erika Mackin Computer Science Department Rensselaer Polytechnic Institute Troy, NY, USA mackie2@rpi.edu Lirong Xia Computer Science Department Rensselaer Polytechnic Institute Troy, NY, USA xial@cs.rpi.edu |
| Pseudocode | Yes | Protocol 1: Categorial sequential allocation mechanism (CSAM) f O. Input: An order O over {1, . . . , n} {1, . . . , p}. 1 Broadcast O to all agents. 2 for t = 1 to np do 3 Let (j, i) be the t-th element in O. 4 Agent j chooses an available item dj,i 2 Di. 5 Broadcast dj,i to all agents. |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper describes theoretical mechanisms and does not use or reference any publicly available datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments that would involve dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not conduct computational experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup including hyperparameters or system-level training settings. |