Up: Student Seminars for 2014
Top: Math Department Student Seminars

Allocating Indivisible Items in Categorized Domains


Lirong Xia
Rensselaer Polytechnic Institute

February 25, 2014
5:00 pm
Bailey Hall 207

Refreshments will be served in Bailey Hall 204 4:45pm


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. http://www.cs.rpi.edu/~xial/

For additional information, send e-mail to math@union.edu or call (518) 388-6246.
Up: Student Seminars for 2014
Top: Math Department Student Seminars

Union College Math Department Home Page
Comments to: math@union.edu
Created automatically on: Tue Oct 23 06:30:02 EDT 2018