Allocating Indivisible Items in Categorized Domains
Rensselaer Poytechnic Institute
February 25, 2014 (Tue)
room tbd
Lunch will be served at noon.


Imagine you are organizing a seminar event and must allocate 10 discussion topics and 10 dates to 10 students. Students may have different and combinatorial preferences over (topic, date) bundles, and their preferences over one component may depend on the other component. What would you do?

The design and analysis of allocation mechanisms for indivisible items without monetary transfer have constituted an active area at the interface of computation and economics. To overcome existing communicational and computational barriers, we propose a novel and general class of allocation problems called categorized domain allocation problems (CDAPs), where the indivisible items are partitioned into multiple categories and each agent must get at least one item from each category.

We first take a traditional axiomatic approach in economics to characterize serial dictatorships by a minimal set of three properties: strategy-proofness, non-bossiness, and category-wise neutrality. Then, we design and analyze a natural extension of serial dictatorships called categorical sequential allocation mechanisms, which allocate the items in multiple rounds so that in each round, the active agent chooses an item from the designated category. We characterize the worst-case ordinal efficiency of categorical sequential allocation mechanisms for optimistic and pessimistic agents, and use computer simulations to study the expected efficiency of these mechanisms.

Bio: Lirong Xia is an assistant professor at Rensselaer Polytechnic Institute. He earned a Bachelor's degree from Tsinghua University in Beijing, China and Master's and PhD degrees from Duke University. Before joining Rensselaer, he did a Postdoc at the Center for Research on Computation and Society (CRCS) at Harvard University. His research focuses on the intersection of computer science and microeconomics, in particular computational social choice, game theory, mechanism design, and prediction markets.

Please email Kristina Striegnitz ( if you have any questions concerning the seminar series or if you would like to receive the seminar announcements by email.