Tolerable Manipulability in Dynamic Assignment without Money

This paper is going to appear in the proceedings 24th AAAI conference on Artificial Intelligence (AAAI '10), 2010. This is joint work with James Zou and David Parkes from Harvard University. This work was carried out when I spent my summer internship in Harvard.

We studied the problem of object assignments in dynamic settings. That is, the agents in the system are arriving dynamically and need one object. The agents have strict preferences over these objects. And no monetary transfers are involved.

Consider the collaborative project like cleaning up task on wiki. The interested users, voluntarily participate for these tasks. However, they may have preferences on these tasks. The problem is not all the agents are available at the same time. The agents will arrive dynamically and will be available till some time and may leave the system. So, if at all we have to assign a task to an agent, we have to perform this before he or she leaves. And it should try to assign agents their preferable tasks which is private information to the agents.

In static settings, Svensson's has shown that, if we need no-bossy and neutrality with respect to objects, serial dictatorship is the only strategyproof mechanism for the objects assignment. No-bossy means, nobody can dictate the outcome for the other agents without affecting himself. Using his theorem, we show that, in on-line settings, greedy algorithm, which we call as APSD, is the only strategyproof mechanism that also satisfies neutrality and no-bossy properties.

APSD:(Arrival Priority Serial Dictatorship)
As soon as an agent arrives, he is assigned his most preferred item from pool of available items.

APSD is very simple, natural mechanism and satisfies nice game theoretic properties. viz, strategyproof, no-bossy, neutrality and ex-post efficiency. However, it may happen that because of one agent arriving sooner, and getting his best choice, all the subsequent agents can get worse of. Somehow, if know that some agent is not that worse of by doing some less
preferred task as compared to others (or receiving less preferred object), then we may assign him this less preferable task/object and make others happy. Based on this, we propose a mechanism which we call as scoring rule (SR). SR is susceptible for manipulations. We characterize all possible manipulations and show that if everybody manipulates optimally, it reduces to APSD. If only fraction of agents are strategic and the others are reporting truthfully, the ex-ante performance of SR is better than APSD.

This performance is considering rank based utilities has been used by Budish and Cantillon. We assume we assume risk neutral agents with a constant difference in utility across items that are adjacent in their preference list. That is, the difference between utility of receiving object ranked 1 and ranked 2 is same as the difference between receiving object 2 and 3. Based on this assumption, we use expected rank for all the agents that they assign to their assigned object as performance metric for a mechanism.

We also compare the ex-ante performance of the SR with CONSENSUS, an on-line stochastic optimization based algorithm. SR outperforms CONSENSUS.

For technical details, please refer to our paper.
(If want a copy of it for non-commercial purpose, please let me know.)

---
Sujit Gujar
Research Student,
Indian Institute of Science, Bangalore.