Learning Desirable Matchings From Partial Preferences

A fundamental problem in multi-agent systems is resource allocation. Specifically, the problem of assigning a number of indivisible objects to agents with different preferences has been widely studied not only in multi-agent systems, but also in economics [21] and theoretical computer science [12]. The focus of our work is the special case of allocating n objects to n agents (so each agent is matched to a single object), which models many real-world applications. For example, imagine allocating office spaces to faculty members in a new building. Instead of asking each faculty member to report a full preference ranking over the available offices, the department head may ask faculty members to reveal their top choices, and then if need be, he may ask individual faculty members to reveal their next best choices, and so on. The goal of the department head is to learn a matching that satisfies some form of "economic efficiency" while asking as few queries as possible.