Taking care of the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms. Obviously strategyproof (OSP) mechanisms have recently emerged as the concept of interest to this research agenda. However, the majority of the literature in the area has either highlighted the shortcomings of OSP or focused on the \right" de nition rather than on the construction of these mechanisms. We here give the rst set of tight results on the approximation guarantee of OSP mechanisms for scheduling related machines and a characterization of set system instances for which optimal OSP mechanisms exist. By extending the well-known cycle monotonicity technique, we are able to concentrate on the algorithmic component of OSP mechanisms and provide some novel paradigms for their design. We prove that OSP encompasses careful interleaving of ascending and descending auctions.
Mechanism design has been a very active research area that aims to develop algorithms (a.k.a., social choice functions) that align the objectives of the designer (e.g., optimality of the solution) with the incentives of self-interested agents (e.g., maximize their own utility).
One of the main obstacles to its application in realistic settings is the
assumption of full rationality. Where theory predicts that people should not strategize,
lab experiments show that they do (to their own disadvantage): this is, for
example, the case for Vickrey's renown second-price auction; proved to be
strategyproof and yet bidders lie when submitting sealed bids. However, lies are less
frequent when the same mechanism is implemented via an ascending auction
[
A vague explanation of this phenomenon is that, from the point of view of a
bidder, the strategyproofness (a.k.a., truthfulness) of an ascending price auction
is easier to grasp than the strategyproofness of the second-price sealed bid
auction [
As being OSP is stronger than being strategyproof, it is natural to ask if
this has an impact on what can be done by such mechanisms. For instance, the
so-called deferred-acceptance (DA) auctions [
One of the reasons behind this open question might be the absence of a
general technique for designing OSP mechanisms and the lack of an algorithmic
understanding of OSP mechanisms. Speci cally, it is well known that
strategyproofness is equivalent to certain monotonicity conditions of the algorithm
used by the mechanism for computing the solution (be it an allocation of goods
or a path in a network with self-interested agents). Therefore, one can essentially
focus on the algorithmic part and study questions regarding the quality of the
solutions (e.g., approximation) and the time needed to compute a solution (e.g.,
complexity). The same type of questions seem much more challenging for OSP
mechanisms, as such characterizations are not known. Recent work in the area,
such as [
The goal of this work is to build the foundations to reason about OSP
algorithmically. In particular, we advance the state of the art by providing an
algorithmic characterization of OSP mechanisms. Among others, our results show
why deferred acceptance auctions [
Our Contribution. To give an algorithmic characterization of OSP mechanisms, we extend the well known cycle-monotonicity (CMON) technique. This approach allows to abstract the truthfulness of an algorithm in terms of nonnegative weight cycles on suitably de ned graphs. In its more general form, the graph for truthfulness of agent i is complete and has a vertex for each possible outcome; edge weights account for the incentives of agent i in forcing a di erent outcome by lying. We show that non-negative weight cycles continue to characterize OSP when the graph of interest is carefully de ned. Speci cally, we have a graph for each agent i as well, but there is a node for each strategy pro le and we add an edge between two vertices only when there is an OSP constraint for i involving those pro les. Essentially, our main conceptual contribution is a way to accommodate the OSP constraints, which depend on the particular extensive-form implementation of the mechanism, in the machinery of CMON, which is designed to focus on the algorithmic output of mechanism. We prove that payments exist that can be paired to the algorithm in an OSP mechanism, implemented in extensive-form, if and only if this graph does not contain negative cycles.
Interestingly, our technique shows the interplay between algorithms (which
outcome/solution to return) and how the mechanism is implemented as an
extensive-form game (what we call the implementation tree). Roughly
speaking, our characterization says which algorithms can be used for any choice of
the implementation tree. The ability to choose between di erent implementation
trees is what gives extra power to the designer: for example, the construction of
OSP mechanisms based on DA auctions [
Armed with the OSP CMON technique, we are able to give the rst tight
bounds on the approximation ratio of OSP mechanisms for the problem of
scheduling n related machines (for identical jobs) and a characterization of
optimal OSP mechanisms for set system problems (which include path auctions as
a special case). A caveat for our results is about the size of the agents' domains.
While our lower bounds/necessary conditions hold regardless of the size of the
domain, the mechanisms that we provide are shown to be OSP only for
twoand three-value (agent-speci c) domains, as we prove that these are the only
cases in which non-negative two-cycles are necessary and su cient. However,
our mechanisms are, to the best of our knowledge, the rst examples of OSP
mechanisms with money that do not follow a clock or a posted price auction
format (other mechanisms that do not follow these formats have been proposed
only for setting without money, namely matching and voting [
Machine Scheduling. Machine scheduling is one of the problems that received
most attentions within the literature about OSP. In particular, [
In this work, we show that the optimum for machine scheduling can be implemented OSP-ly when the agents' domains have size two. We prove that given a \balanced" optimum (i.e., a greedy allocation of jobs to machines) we can always nd an implementation tree for which OSP is guaranteed. The mechanism directly asks the queried agents to reveal their type; given that the domain only contains two values, this is basically a descending/ascending auction.
For domains of size three, instead, we give a lower bound of pn and an essentially tight upper bound of dpne. Interestingly, the latter is proved with two di erent OSP mechanisms { one assuming more than dpne2 number of jobs and the second under the hypothesis that there are less than that.
Main Theorem about Machine Scheduling (informal). The tight approximation guarantee of OSP mechanisms that can be guaranteed over all three-value domains is pn. The OSP mechanisms use a descending auction (to nd the n dpne slowest machines) followed by an ascending auction (to nd the fastest machine(s)). On the technical level, these results are shown by using our approach of CMON two ways. We prove that any better than pn-approximate OSP mechanism must have the following structure: for a number of rounds, the mechanism must (i) separate, in its implementation tree, the largest and the second largest value in the domain; (ii) assign nothing to agents who have maximum value in the domain. The former property restricts the family of implementation trees we can use, whilst the latter restricts the algorithmic output. Our lower bound shows that there is nothing in this intersection.
Our matching upper bounds need to nd both the implementation tree and the algorithm satisfying OSP and the approximation guarantee. While the general idea of the implementation is that of a descending auction followed by an ascending auction independently of the number of jobs, we need to tailor the design of the mechanisms (namely, their ascending phase) according to the number of jobs to achieve OSP and the desired approximation simultaneously. This proves two important points. On one hand, the design of OSP mechanisms is challenging yet interesting as one needs to carefully balance algorithms and their implementation. On the other hand, it proves why xing the implementation, as in DA auctions, might be the wrong choice. We in fact extend and adapt our analysis to prove that any ascending and descending (thus including DA) auction has an approximation of n.
Set Systems. We consider a general set system problem, wherein agents have three-value (heterogeneous) domains and fully characterize the properties needed to design OSP mechanisms.
Main Theorem about Set Systems (informal). There is an OSP optimal mechanism i the set of feasible solutions are \aligned" with agents' subdomains. The OSP optimal mechanism, if any, combines ascending and descending auctions depending on the structure of the feasible solution set.
The intuition behind the characterization is simple. From OSP CMON, we know that if an OSP mechanism selects an agent e when she has a \high" cost, then it must select e when she has a \low" cost (akin to monotonicity for strategyproofness). Therefore, to design an OSP optimal mechanism, we need to de ne an implementation tree which satis es this property. At each node of the tree, the domain of the agents is restricted to a particular subdomain, depending on the particular history; in turn, the set of possible type pro les also shrinks. Hence, there may be solutions that become suboptimal for all type pro les in this set, and others that are still alive (i.e., optimal for at least one type pro le in the set). When e is asked to separate a high cost from a low cost at node u of the tree, we then need the alive solutions to be \aligned" for the subdomain at u, which roughly means that it should never be the case that there are two bid pro les in this subdomain for which e belongs to an optimal solution when she has a high cost and is not part of an optimal solution when she has a low cost.
The somehow surprising extra aspect is that, even if the alive solutions were not aligned for one single subdomain, then there would be no way to design an implementation tree to bypass this misalignment.
The technical de nition of alignment has some nuisance to do with the particular ways in which the OSP monotonicity can be broken, but on the positive side, rather immediately suggests how to interleave ascending and descending phases to design an OSP optimal mechanism. This characterization precisely shows how OSP needs to look at the quality of solutions among set of instances (encoded by agent subdomains) rather than just the single instance and how this is needed to inform the shape of the implementation tree.
Future Directions. A technical one is about the domain size and the di erence between 2-cycles and longer ones; to what extent adding an extra type in the domain can deteriorate the approximation ratio of OSP mechanisms? A second, more conceptual question, is about dealing with multi-parameter agents. Indeed, it does not seem immediate to characterize the implementation trees for this kind of agents as there is not a concept of relative ordering of types.