Cette page appartient aux archives web de l'EPFL et n'est plus tenue à jour.
This page belongs to EPFL's web archive and is no longer updated.

Mechanism Design

A. Procaccia and M. Tennenholtz, 2009, Approximate mechanism design without money, EC 2009

Posted by Katherine Skirving Larson on Tuesday 8 May 2012 at 14:01
In this paper, authors claim that there is no optimal truthful mechanism without money. In absence of such a solution, they suggest a solution in which optimality is sacrificed in order to get strategyproofness.

The paper presents a case study in which agents want to select the location of a facility. The cost of each agent is its distance to the facility. In this case study, the median location is strategyproof if the goal is to minimize the sum of costs of all agents. However, if the goal is to minimize maximum cost then the mechanism is not strategyproof. This only happens because we consider the problem with out paying money.

The authors then consider the same problem for locating two facilities. In this case the cost of each agent is its distance with nearest facility. For this problem they give a randomized approximation mechanism and they provide the proof of strategyproofness.

Another problem which is studied in the paper is locating a facility when agents can associate multiple locations. Here again authors give a approximate mechanism which was not clear for me.

Not using money, a certain mechanism might not be longer strategyproofed. But the argument in the paper that any other mechanism can't be strategyproofed is not clear.

The abstract is written in a way that it could be concluded the authors give alternative solutions for designing mechanisms without money for general problems. But, in fact, the paper studies one problem in three different form, which is still valuable.
Posted by Laleh Makarem on Tuesday 8 May 2012 at 19:36
This paper proposes some approximate mechanisms (for a specific problem) in which no money is transferred to agents. The studied problem is the facility location problem for which tractable optimal solution exists. However the mechanism that yield the optimal solution is not strategyproof. The authors first consider the basic setting of locating a facility given the location (on a real line) profile of the agents for two objectives: minimizing social cost, and minimizing maximum cost. Then they introduce the first extension in which two facilities need to be located. The second extension is the case of each agent having multiple locations and one facility is to be located. For each of these cases deterministic and randomized strategyproof and group strategyproof mechanisms are proposed and for most of them upper and lower bounds are specified. Of more interest are the randomized mechanism that have better bounds compared to the deterministic ones. The paper has very concise and useful summary of the results for each case and also a discussion subsection in which open question and possible extensions are discussed. One interesting question would be to investigate the possibility of relations between the mechanisms with money and the mechanisms without money.
Posted by Mehdi Riahi on Wednesday 9 May 2012 at 0:43
The main contribution on this paper was, in my opinion, the innovative idea that approximation is not a necessary evil, but something you can use to produce strategy prof mechanisms without payments. I liked this idea and I liked their simple but very elegant results (theorem 2.3. for example which was at the very beginning was so simple and kept me turning the pages). I like that they show many results and seem to take into account a good number of variations from the original setting of one facility-one agent location. However, I would have also liked to see a motivation of why approximation rates of 2, 3/2, 5/3 etc (which to me seem big) are acceptable in a real world environment.

Some criticism...
They mention there is a new class of problems they think was neglected in previous work and should be reconsidered: problems for which "there is an optimal, computationally eficient, truthful, payment-based mechanism but no optimal truthful mechanism without money".. And yet "our agenda only applies to optimization problems where there exist reasonable strategyproof mechanisms without payments". That was very confusing. What do they mean by "reasonable"? Why are they saying these problems should be considered and then seem to mention that they won't focus on them? Do they mean they will only look at problems from that class for which an approximation strategy proof mechanism without payments exists?

In the beginning they say Mechanism 2 "incorporates several new ideas in order to achieve strategyproofness" creating a feeling of anticipation. But it was not clear to me when I got to it what exactly are the new ideas.

Overall, I think they made a good start in tackling approximation strategy proof mechanisms without money, which is why I don't mind the very simple settings of looking only at single peaked preferences.
Posted by Alexandra Mihaela Olteanu on Wednesday 9 May 2012 at 13:50
{The paper, at a glance: }
The paper considered in this blog is the full version of the paper that they presented in EC'09.
It talked about obtaining strategy-proof mechanisms in an environment where payment/money is not available. In order to get strategy-proofness, sometimes, optimality has to be sacrificed.

{What is interesting to me: }
In all of the cases defined, they provide a deterministic strategy-proof mechanism, together with its approximation ratio whenever it is not optimal. After that, in an attempt to do better, they provide a randomized strategy-proof mechanism, and they did it (they got better approximation ratio).

{Critics: }
There are some (minor) error, e.g.
- Last paragraph of section 2 (before section 2.1) y \in R^n which should be y \in R.
- In the proof of Theorem 2.3 "rt(x) can be pushed to the right..." it should be "rt(x) can be pushed to the left..."
- In the end of section 3.1, I tried to find the worst case, analyze it, and I've got is (n-2) approximation ratio. Then the question is: if the worst case is (n-2) approx. ratio why did they declare it as (n-1) approx. ratio? (it turned out that since the bound is still O(n), they didn't bother to provide the tight one).

{Salute: }
I like the paper in the sense that they try to enter a new problem. Well, it is not entirely new since the problem case is well studied, strategy-proof, and non-optimality in mechanism design are not new phenomenon. But the motivation they delivered in putting strategy-proof on top of optimality when payment is not possible will be useful (or at least a new alternative) for some cases where trust is essential (and payment is not an option).
Posted by Tri Kurniawan Wijaya on Thursday 10 May 2012 at 15:28