11th Max Planck Advanced Course on the Foundations of Computer Science

Hello all,
I attend the 11th Max Planck Advanced Course
on the Foundations of Computer Science at Saarbrucken, Germany.

The summary of the course has been posted by Swaprava Nath on AGTB by Noam Nisan.

http://agtb.wordpress.com/2010/08/18/swaprava-nath-reports-on-saarbrucken-agt-course/

It is followed by my comments.
So interested readers may read the blog.

---

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

M-PREF 2010

Hello all,

This years Multidisciplinary Workshop on Advances in Preference Handling (M-PREF 2010), is going to be held in conjunction with ECAI 2010.

For more details: http://preferencehandling.free.fr/welcome.html

If you are interested in submitting any paper here, hurry up. Deadline is 7th May.

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

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.

Cost Sharing Mechanisms

Hello all,
Vast amount of literature is available on cost sharing mechanisms. Here is summary of a paper by Herve Moulin and Scott Shenker, titled, "Strategyproof sharing of submodular costs: budget balance versus efficiency". This paper appeared in Economic Theory, Volume 18, Number 3 / November, 2001.

A scenario where a service is to be allocated to n agents is studied. Each agent either may receive the service or may not receive. The cost of service depends upon set of agents served and is assumed to be a submodular function through out the paper. Each agent has a maximum willingness to pay (u_i) for receiving the service. u_i s are private to the agents. Authors explore the strategyproof mechanisms for this problem to allocate the service to subset of the agents.

Due to Green-Laffont impossibility theorem, no strategy proof mechanism is efficient as well as budget balanced.

The authors first propose a class of mechanisms that is group strategy proof, budget balanced and satisfies voluntary participation (VP), No Positive Transfers (NPT) and Consumer Sovereignty (CS). These mechanisms depend upon a cross monotonic cost sharing method for the given cost function to satisfy the above properties.

One can use the cross monotonic cost sharing method of his choice, which could be anything from egalitarian to shapley or their convex combinations. Authors also show that Shapley Value based cost sharing is the one with minimal loss in efficiency.

When efficiency is more important than budget balance, then authors propose marginal cost sharing based mechanism which belongs to the class of Groves' mechanisms (Efficient + strategy proof).

Authors show if a mechanism has to satisfy reasonable properties along with efficiency and strategy proof, marginal cost sharing mechanism is the unique mechanism.

Authors compare maximal worst case welfare loss in Shapley cost sharing mechanism vs worst case maximal budget deficit in marginal cost sharing mechanism and show that the former is smaller as compared to later.

Thus authors feel budget balanced mechanisms are better as they also satisfy group strategyproof as well as it is a rich class as compared to unique efficient mechanism.


Acknowledgements:
This paper was presented in ECL, by Radhika. She also helped in editing this summary. The inital draft of the annotation of the talk was prepared by Rohith Vallam.


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