Obvious strategyproofness (OSP) is an appealing concept as it allows to maintain incentive compatibility even in the presence of agents that are not fully rational, e.g., those who struggle with contingent reasoning [10]. However, it has been shown to impose some limitations, e.g., no OSP mechanism can return a stable matching [3]. We here deepen the study of the limitations of OSP mechanisms by looking at their approximation guarantees for basic optimization problems paradigmatic of the area, i.e., machine scheduling and facility location. We prove a number of bounds on the approximation guarantee of OSP mechanisms, which show that OSP can come at a signi cant cost. However, rather surprisingly, we prove that OSP mechanisms can return optimal solutions when they use monitoring | a mechanism design paradigm that introduces a mild level of scrutiny on agents' declarations [9].
Algorithmic Mechanism Design (AMD) is by now an established research area in computer science that aims at conceiving algorithms resistant to sel sh manipulations. As the number of parties (a.k.a., agents) involved in the computation increases, there is, in fact, the need to realign their individual interests with the designer's. Truthfulness is the chief concept to achieve that: in a truthful mechanism, no sel sh and rational agent has an interest to misguide the mechanism. A question of recent interest is, however, how easy it is for the sel sh agents to understand that it is useless to strategize against the truthful mechanism.
Recent research has come up with di erent approaches to deal with this
question. Some authors [
For the former problem, we want to compute a schedule of jobs on
selfish related machines so to minimize the makespan. For this single-dimensional
problem, it is known that a truthful PTAS is possible [
For the facility location problem, we want to determine the location of a
facility on the real line given the preferred locations of n agents. The objective
is to minimize the social cost, de ned as the sum of the individual agents'
distances between their preferred location and the facility's. Moulin [
However, a surprising connection of OSP mechanisms with a novel mechanism
design paradigm { called monitoring { allows us to prove strong positive results.
Building upon the notion of mechanisms with veri cation [
We prove that, for machine scheduling, there is an optimal OSP mechanism
with monitoring. The construction of this mechanism can use any algorithm for
the problem as a black box, thus implying that there is PTAS that is OSP. Our
construction is based upon the rst-price (truthful) mechanism (with
monitoring) recently designed in [
Mechanisms and strategy-proofness. In this work we consider a classical mechanism design setting, in which we have a set of outcomes O and n sel sh agents. Each agent i has a type ti 2 Di, where Di is de ned as the domain of i. The type ti is private knowledge of agent i. Moreover, each sel sh agent i has a cost function ci : Di O ! R. For ti 2 Di and X 2 O, ci(ti; X) is the cost paid by agent i to implement X when her type is ti.
A mechanism consists of a protocol whose goal is to determine an outcome X 2 O. To this aim, the mechanism is allowed to interact with agents. During this interaction, agent i is observed to take actions; these actions may depend on her presumed type bi 2 Di that can be di erent from the real type ti. We say that agent i takes actions according to bi to stress this. For a mechanism M, we let M(b) denote the outcome returned by the mechanism when agents take actions according to their presumed types b. Usually, this outcome is given by a pair (f; p), where f = f (b) (termed social choice function) maps the actions taken by the agents according to b to a feasible solution for the problem at the hand, and p = (p1(b); : : : ; pn(b)) 2 Rn maps the actions taken by the agents according to b to payments from the mechanism to each agent i.
A mechanism M is strategy-proof if for every i, every b i and every bi 2 Di, it holds that ci(ti; M(ti; b i)) ci(ti; M(bi; b i)), where ti is the true type of i. That is, in a strategy-proof mechanism the actions taken according to the true type are dominant for each agent. Moreover, a mechanism M satis es voluntary participation if for every i and every b i, it holds that ci(ti; M(ti; b i)) 0. Obvious strategyproofness. An extensive-form mechanism M is de ned by a directed tree T = (V; E) such that: (i) every leaf ` of the tree is labeled by a possible outcome X(`) 2 O of the mechanism; (ii) every internal vertex u 2 V is labeled by a subset S(u) [n] of agents; (iii) every edge e = (u; v) 2 E is labeled by a subset T (e) D of type pro les such that: { the subsets of pro les that label the edges outgoing from the same vertex u are disjoint, i.e., for every triple of vertices u; v; v0 such that (u; v) 2 E and (u; v0) 2 E, we have that T (u; v) \ T (u; v0) = ;; { the union of the subsets of pro les that label the edges outgoing from a nonroot vertex u is equal to the subset of pro les that label the edge going in u, i.e., Sv : (u;v)2E T (u; v) = T ( (u); u), where (u) is the parent of u in T ; { the union of the subsets of pro les that label the edges outgoing from the root vertex r is equal to the set of all pro les, i.e., Sv : (r;v)2E T (r; v) = D; { for every u; v such that (u; v) 2 E and every two pro les b; b0 2 T ( (u); u) such that (bi)i2S(u) = (b0i)i2S(u), if b belongs to T (u; v), then also b0 must belong to T (u; v).
Observe that, according to the de nition above, for every pro le b there is only one leaf ` = `(b) such that b belongs to T ( (`); `). For this reason we say that M(b) = X(`). Moreover, for every type pro le b and every node u 2 V , we say that b is compatible with u if b 2 T ( (u); u). Finally, two pro les b, b0 are said to diverge at vertex u if there are two vertices v; v0 such that (u; v) 2 E, (u; v0) 2 E and b 2 T (u; v), whereas b0 2 T (u; v0).
An extensive-form mechanism M is obviously strategy-proof (OSP) if for every agent i, for every vertex u such that i 2 S(u), for every b i; b0 i, and for every bi 2 Di such that (ti; b i) and (bi; b0 i) are compatible with u, but diverge at u, it holds that ci(ti; M(ti; b i)) ci(ti; M(bi; b0 i)).
Monitoring. Let M(b) denote the outcome returned by mechanism M = (f; p) when agents take actions according to b. Commonly, the cost paid by agent i to implement M(b) is de ned as a quasi-linear combination of agent's true cost ti(f (b)) and payment pi(b), i.e., ci(ti; M(b)) = ti(f (b)) pi(b). This approach disregards the agent's declaration for evaluating her cost.
In mechanisms with monitoring the usual quasi-linear de nition is maintained
but costs paid by the agents are more strictly tied to their declarations [
We are given a set of m di erent jobs to execute and the n agents control related machines. That is, agent i has a job-independent processing time ti per unit of job (equivalently, an execution speed 1=ti that is independent from the actual jobs). Therefore, the social choice function f must choose a possible schedule f (b) = (f1(b); : : : ; fn(b)) of jobs to the machines, where fi(b) denotes the job load assigned to machine i when agents take actions according to b. The cost that agent i faces for the schedule f (b) is ti(f (b)) = ti fi(b). Note that our mechanisms for machine scheduling will always pay the agents.
For this setting, monitoring means that those agents who have exaggerated their unitary processing time, i.e., they take actions according to bi > ti, can be made to process up to time bi instead of the true processing time ti. E.g., we could not allow any operation in the time interval [ti; bi] or charge bi ti.
We focus on social choice functions f optimizing the makespan, i.e., f (b) 2 arg minx mc(x; b), where mc(x; b) = maxin=1 bi(x). We have the following results. Theorem 1. For every " > 0, there is no (2 ")-approximate mechanism for the machine scheduling problem that is OSP without monitoring and satis es voluntary participation.
Theorem 2. For every -approximate algorithm f for the machine scheduling problem on related machines there is an -approximate mechanism for the same problem that is OSP with monitoring and satis es voluntary participation. 4
In the facility location problem, the type ti of each agent consists of her position on the real line. The social choice function f must choose a position f (b) 2 R for the facility. The cost that agent i pays for a chosen position f (b) is ti(f (b)) = d(ti; f (b)) = jti f (b)j. So, ti(f (b)) denotes the distance between ti and the location of the facility computed by f when agents take actions according to b.
We can implement monitoring also in this setting whenever evidences of the distance can be provided (and cannot be counterfeited). In fact, in this context, monitoring means that ti(f (b)) = maxfd(ti; f (b)); d(bi; f (b))g. Therefore, once the evidence is provided, the mechanism can check whether ti(f (b)) < bi(f (b)) and charge the agent the di erence for cheating.
We focus on optimizing the social cost, i.e., f (b) 2 arg minx2R cost(x; b), where cost(x; b) = Pn
i=1 bi(x). We have the following results.
Theorem 3. For every " > 0, there is no (n 1 ")-approximate mechanism for the facility location problem that is OSP without monitoring. Theorem 4. There is a (n 1)-approximate mechanism for the facility location problem that is OSP, even without monitoring.