{'fraction_non_alphanumeric': 0.05302297662320339, 'fraction_numerical': 0.00656951345583086, 'mean_word_length': 4.250919278585187, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Mechanism design for resource allocation with applications to centralized multi-commodity routing

We formulate and study the algorithmic mechanism design problem for a general class of resource allocation settings, where the center redistributes the private resources brought by individuals. Money transfer is forbidden. Distinct from the standard literature, which assumes the amount of resources brought by an individual to be public information, we consider this amount as an agent's private, possibly multi-dimensional type. Our goal is to design truthful mechanisms that achieve two objectives: max-min and Pareto efficiency. For each objective, we provide a reduction that converts any optimal algorithm into a strategy-proof mechanism that achieves the same objective. Our reductions do not inspect the input algorithms but only query these algorithms as oracles. Applying the reductions, we produce strategy-proof mechanisms in a non-trivial application: network route allocation. Our models and result in the application are valuable on their own rights.


INTRODUCTION
One of the most important problems at the intersection of economics and computation is algorithmic mechanism design, which dates back to the seminal work of Nisan and Ronen [20]. The basic problem asks: Given an algorithmic optimization problem, is it possible to efficiently produce a truthful mechanism that (approximately) achieves the optimal value of the original problem?
Over the past decade, there has been a number of breakthroughs regarding this problem in settings where money transfer is allowed, including the rich literature on truthful welfare-maximizing mechanism design [22,9,8], and Bayesian incentive compatible (BIC) mechanism design [14]. Recently, the same problem has been investigated under the context of revenue optimal mechanism design [6,7].
Distinct from the above literature, we study algorithmic mechanism design without money [21,Chapter 10]. In particular, we study a general class of resource allocation problems, where each agent brings a certain amount of resources and the mechanism distributes these resources to achieve certain objectives. It is important to note that our setting differs from the standard resource allocation literature (such as one-sided matching, hedonic games, etc) in that each agent's type is the amount of resources she brings, rather than her preference over allocations. Our goal is to design strategy-proof mechanisms that achieve two objectives: maxmin and Pareto efficiency.
Our framework is rich enough to encompass, or at least heavily intersect with, a variety of applications, such as cloud resource allocation [13,24], facility location [26], fair division [25] and network route allocation [this paper].

Main results
We make the following contributions.

Black-box reductions
For any resource allocation problem, we provide two reductions, one for maxmin and the other for Pareto efficiency, that automatically convert any optimal algorithm into a strategy-proof mechanism that achieves the same objective. Our reductions do not make use of any algorithm but only assume black-box access to the algorithm.
• For the maxmin objective, we construct a polynomial time algorithm that, for any input, generates the optimal group-strategy-proof mechanism by calling the optimal algorithm only once. • For Pareto efficiency, we show that, if there is an algorithm that serially optimizes the utility profile, the algorithm per se is strategy-proof.

Application
Simple reductions as they may seem, their generalities are demonstrated by a complex, practical application: network route allocation. Network route allocation. In this application, each node downloads a file from a server node located somewhere in the network. It can download via a direct route to the sever (it can do so without joining the mechanism, imposing an IR constraints to the design problem) or, by joining the mechanism, download via certain indirect routes that pass through other nodes. Each node has a certain private capacity (resource) that specifies the maximum limit of flow that can pass through it. Upon receiving the reports of private capacities, the mechanism returns a multi-commodity flow on the network. Our model encompasses both client-server networks and peer-to-peer networks [23,Chapter 4]. Applying our reductions, one can obtain IR and strategy-proof mechanisms that achieve either maxmin or efficiency.

Related work
In the literature of mechanism design without money, a popular line of work concerns how to locate a facility [17,26]. They study a mechanism design problem where agents are located on the real line and the mechanism select the location of a facility, where each agent's cost is its distance to the facility. The objectives are maxmin as well as efficiency.
They give tight bounds on ratio of the optimal strategyproof mechanism over the optimal algorithm without incentive constraints. This line of work has been extended to a number of variations, such as there are two facilities [15], or the utility function is not linear [11], or the objective is the least square [10].
Resource allocation is also of central importance to the multiagent system community. It has been widely discussed in the application of smart grid [28,27] and has been of the main application scenario of security games (see [30]).
Our resource allocation notion is related to the classic bilateral trade setting [19], resource exchange setting [3], as well as the recently coined reallocation settings [4]. A key distinction is, as mentioned, our setting treats the amount of contributed resources as private type while this amount is public information in their settings and they all treat valuation functions as types. Furthermore, their objectives are focused on characterization of efficient truthful mechanisms while our objective is to reduce mechanism design to algorithm design.
The second blackbox reduction in this paper, i.e., the one for the Pareto efficiency objective, makes use of algorithms that serially maximizes the utility profiles. This idea naturally relates our reduction to the (randomly) serial dictatorship literature [29,5,16,2], which are known to be strategyproof and Pareto efficient. Note again that their strategyproofness is defined with respect to truthful announcement of preferences, rather than contributed resources. Another distinction is that the serial dictatorship literature is concerned with allocation of indivisible items while our focus is on divisible resources. This distinction is not essential though, if randomization are permitted.

THE RESOURCE ALLOCATION PROB-LEM
We now formulate the resource allocation problem. An environment specifies the parameters for the mechanism designer to operate. • S = S1 × S2 × · · · × Sn, where each Si is the private type set of agent i, • P is a set of public information and resources shared by all agents, • O is the set of outcomes.
By revelation principle [18], one can without loss restrict attentions to the set of direct revelation mechanisms, which can be regarded as functions that maps agents' reported type profile and public info. into an outcome. Each agent i in the environment comes with a private amount of resources si ∈ Si and is asked by the mechanism to report this quantity. Upon receiving all inputs, the mechanism returns an outcome, i.e., an allocation of resources.
For example, consider a variant of the dominant resource problem defined in [13], Si = R+ m where the j-th element in the vector is the amount of j-th resource that agent i owns. Agent i needs ci,1 units of the first type of resource and ci,2 units of the second and · · · ci,m units of the m-th in order to conduct 1 unit of job task. Thus, P is the set of all possible such {(ci,1, ci,2, · · · , ci,m)} n j=1 and O is the set of all possible distributions of resources.
A resource allocation environment imposes certain feasibility constraints on any mechanism defined on it. For example, no mechanism shall allocate 3 CPU units to an agent if there are only 2 units of CPU within the society.
Consider again the dominant resource problem, o ∈ F EA( s1, · · · , sn, p) if and only if the resource allocation prescribed by o is feasible 1 under the input.
We consider environments and feasibility constraints that satisfy the following resource monotone property.
Intuitively, resource monotonicity states that the larger amount of resource one contributes, the larger is the set of feasible allocations. For a mechanism defined on an environment satisfying the resource monotonicity, we call it a resource allocation mechanism.
Every player has a utility function ui : O × P → R. In this paper, we consider a type of ui that must only be related to public information and outcome. This means that the agent's utility does not depend on her private resources. In addition, we assume that there exists an empty outcome o * that for any other outcome o, ui(o * , p) ≤ ui(o, p).
The above definition of utility is not uncommon in the resource allocation domain. Consider again the dominant resource problem, the number of total units of computation player i can conduct only depends on the allocation outcome o and her c-vector (ci,1, ci,2, · · · , ci,m) and the empty outcome is the allocation where no one gets any resource.
The goal of resource allocation mechanism design is to optimize a certain real-valued function w : O → R for equilibrium outcomes. Here w can be different functions according to different application scenarios. For example, in some cases w denotes social welfare, i.e., w(o) = Definition 5. A mechanism is dominant-strategy truthful, (aka. strategy-proof ) if for any s1, · · · , sn, p and any s i ≤i si 2 , then ui (M(s1 · · · si, · · · sn, p), p) ≥ ui M(s1 · · · s i · · · sn, p), p Definition 6. A mechanism is group strategy-proof if for any s1, · · · , sn, p and any s 1 , · · · , s n where each s i ≤i si, then ui (M(s1, · · · , sn, p), p) ≥ ui M(s 1 , · · · , s n , p), p It is easy to see that the definition above subsumes (is stronger than) another definition of group strategyproofness that no subset of agents could jointly deviate so that the resulting outcome is better off for anyone in this subset.
Our goal in this paper is to provide a tool to design strategyproof mechanisms that optimize certain objectives. In particular, given an algorithm that optimizes a certain objective, we use this algorithm as a black-box and return a strategy-proof mechanism that optimizes the same objective.

MAX-MIN
In this section, we consider the problem of designing a strategy-proof mechanism that maximizes the minimal utility among all agents, i.e., w(o) = mini∈N ui(o, p). We show that, given an algorithm that computes the arg maxo w(o), we can construct a strategy-proof mechanism with output o such that w(o ) = w(o) for each input.
Definition 7. An environment is continuous if for any (s1, · · · , sn, p), let ow = arg maxo w(o) and for any u i ≤ ui(ow, p), there must exist some outcome o ∈ F EA(s1, s2, · · · , si, · · · , sn, p) such that ui(o , p) = u i and for any j = i, uj(o , p) = uj(ow, p). Theorem 1. If there exists an algorithm A that optimizes w(o) = mini ui(o, p) for some continuous, resource monotone environment, one can efficiently construct a strategyproof mechanism M that optimizes w(o).
This theorem states that for the resource allocation problems under consideration, designing strategy-proof mechanism with max-min objective is no harder than the corresponding algorithm design problem.
We prove the following stronger theorem instead.
Theorem 2. If there exists an algorithm A that optimizes w(o) = mini ui(o, p) for some continuous , resource monotone environment, one can efficiently construct a groupstrategy-proof mechanism M that optimizes w(o).

outputs on;
oi is often small enough, for example in our application, so that M has time complexity O(T IM E(A)). Now we verify that M really outputs a feasible solution which optimizes w(·). The outcome on is feasible because in each step oi is feasible by the continuity of the environment. Also, it is straightforward that w(on) = w(o0).
Finally, we prove that M is group-strategy-proof. Consider any input s1, s2, · · · , sn, p and everyone reports s i where s i ≤i si: . . . = ui M(s 1 , s 2 , · · · , s i , · · · , s n , p), p So M is a group-strategy-proof mechanism that optimizes w(o).
Applying the same technique, one can produce a strategyproof mechanism to optimize w(o) = mini fi(ui(o, p)) with n strictly increasing functions f1, f2, · · · , fn. With this extension, we can optimize some interesting objectives subject to the individual rationality constraints. We now formally define individual rationality.

MAX-MIN SUBJECT TO INDIVIDUAL RA-TIONALITY
In this section, we consider the setting where if a player does not join the mechanism, he will get a utility ri(p) that only depends on the public information p. In the previous setting, every player's ri(p) = −∞; in other words, she always wants to join the mechanism in the previous setting.

Definition 8.
A mechanism is individual rational if on any inputs s1, s2, · · · , sn, p, the mechanism outputs o such that for any i ∈ N , ui(o, p) ≥ ri(p).

Replacing
So the problem now is to design a strategy-proof and individual rational mechanism that achieves certain objective. This can be achieved by the same method as Theorem 1.
Theorem 3. If there exists an algorithm A that computes w(o) = mini fi(ui(o, p)) for a continuous environment with strictly increasing functions f1, f2, · · · , fn, one can construct a strategy-proof mechanism M that computes w(o).
The reduction is identical to that in theorem 1 thus the proof is omitted.
By this theorem, we can design individual rational and strategy-proof mechanism that optimizes the following: Corollary 1. Let fi(x) = x−ri(p), one obtains an individual rational and strategy-proof mechanism that optimizes the minimal utility gain fi.
Corollary 2. If ri(p) > 0 for any i ∈ N , let fi(x) = x/ri(p), one obtains an individually rational and strategyproof mechanism that optimizes minimal increasing rate.

Optimizing mini ui(o, p) subject to IR
A further question is, can we optimize mini ui(o, p) instead of w(o) = mini fi(ui(o, p)), subject to IR? We answer this affirmatively by modifying the previous method to produce an IR and SP mechanism that optimizes mini ui(o, p).
Theorem 4. If there exists an algorithm A that computes w(o) = mini ui(o, p) for any continuous, resource monotone environment, such that ui(o, p) ≥ ri(p), then we can construct a strategy-proof and individual rational mechanism M that computes w(o).

PARETO EFFICIENCY
In this section, we discuss the objective of implementing a serially optimal outcome. We still use the same setting except that we now restrict agent's i type space Si to R. Definition 9. An outcome o is called serially optimal under s1, · · · , sn, p if the utility profile (u1(o, p), · · · , un(o, p)) is the lexicographically largest one among all possible utility profiles; formally, for any o ∈ F EA(s1, · · · , sn, p), either the utility profile of o equals to that of o or there exists some j ∈ N such that for all k < j, u k (o, p) = u k (o , p) and uj(o, p) > uj(o , p).
Clearly, serial optimality implies Pareto efficiency, so we focus on the former. Our problem now becomes, given any list of input, compute a strategy-proof and serially optimal outcome. Before we start, we need the following property.
Theorem 5. If there exists an algorithm A that serially optimizes w(o) = (u1(o, p), u2(o, p), · · · , un(o, p)) for monotone utility functions, resource monotone environment and ui(o, p) ≥ ri(p), and for each player i, her utility, which is a function of si, ui (A(s1 . . . si . . . sn, p), p) is continuous, the algorithm itself is an IR and SP mechanism that computes a serially optimal outcome.

If (uj(o , p))
n j=1 has the property that ui(o , p) > ui(o, p), then there must exist k < i such that uj(o , p) = uj(o, p) for all j < k and u k (o , p) < u k (o, p) (because a solution in (2) is a solution in (1) and (uj(o, p)) n j=1 is the serially optimal). However we can construct a larger solution for (2): by the monotone utility function condition, we know that there exists an outcome o such that uj(o , p) = uj(o, p) for all j = i and uj(o , p) > ui(o, p) − δ for some δ and ε which is a contradiction that the algorithm find a serially optimal solution.
So gi(ε) is a monotonically decreasing function when gi(ε) > 0. And if gi(ε * ) = 0, then gi( ) for > * will always be 0 . We can conclude that gi(·) is a monotonically decreasing function. Since xi(·) = gi(·) + ri(p), xi(·) is also a monotonically decreasing function which means player i will never get more profit by reporting a lower s i ≤ si.
The theorem states that for monotone utility functions and resource environment, mechanism design is as easy as algorithm design.

Serial optimization by contribution
In order to do serial optimization, one needs to pre-specify a (static) ordering on N , resulting in unfairness for agents who have low rank. In this section, we show that, without sacrificing strategyproofness, this ordering can be extended to depend on the input. In particular, this ordering can be consistent with the ranking of agents' contributions: the more one contributes, the higher priority she gets.
Formally, define "order envy-freeness" as follows: Definition 11. Consider the class of serially optimized mechanisms, a mechanism is order envy-free (OEF) with respect to {li} n i=1 (li is a weight for agent i) if for any two agents i, j ∈ N , such that lisi > ljsj, i is ranked before j in the serial ordering.
Order envy-freeness states that an agent gets a higher priority for optimization than the ones with lower contributions. In particular, if set li = 1 ∀i, the order of optimization is same as the ranking on reports.
Theorem 6. If there exists an algorithm A that serially optimizes w(o, q) = (uq 1 (o, p), uq 2 (o, p), · · · , uq n (o, p)) ( where q is an index on agents such that lq i sq i ≥ lq j sq j for any i < j) for monotone utility functions, resource monotone environment and ui(o, p) ≥ ri(p), then the algorithm itself is an IR, SP and OEF (w.r.t {lj} n j=1 ) mechanism that compute a serially optimal outcome.
To achieve order envy-freeness, we define a slightly different reduction as follows. Given reported {si}, we generate an ordering qi such that for any i, lq i sq i > lq i+1 sq i+1 and optimizes each xi according to the order {qi}. In other words, we define the order according to their contributions: the more you share, the earlier you get served. Technically speaking, this modified mechanism does not belong to the class of mechanisms we have proposed since the ordering of optimization now explicitly depends on the report. However, it is easy to check that this modification does not affect IR, PE, SP and guarantee OEF as a plus. The mechanism is listed below. The proof follows a similar argument to the static case, which we do not repeat.

APPLICATION: NETWORK ROUTE AL-LOCATION
Starting from this section, we show the generality of our methodology by applying it to two realistic scenarios. The two applications are highly nontrivial and valuable on their own rights.
We first consider an interesting route allocation problem in multiple-commodity networks. For the network structures under consideration, there are several vertices known as users. Each user demands a file of certain size stored on a server. The users form a directed graph. Each user has a capacity, which denotes the maximum (traffic) flow that can go through that vertex. We assume this vertex capacity is private information of the user. Between each user and each server, there is an arc constrained by certain capacity, denoting the maximal flow that can go through the arc. Given such a network, a user can download her target file via any route to the destination server 3 . Given the reported vertex capacities, a route allocation mechanism allocates a route (or multiple routes, both of which we consider) and feasible flow within the route for each user.
It is not hard to see that our formulation encompasses route allocation problems in both client-server based and peer-to-peer based (simply treat a server in our model as a peer that never downloads) networks. In practice, the same route allocation problem has been witnessed by Xun-You Inc. 4 , an online gaming platform that aims to resolve the congestions on networks consisting of subnetworks by multiple Internet Service Providers. The same problems have also been witnessed by route optimization among multiple express companies, each of which specializes in some geographic region.
A user's utility is the negation of its time delay, given by − file size allocated flow .
This notion of utility is widely used in the evaluation of performance in a network system or an operating system. More importantly, it does not depend on the private information of users, i.e., the private capacity of each vertex, allowing our framework to be applicable. We will use the above reduction theorems to design a strategy-proof mechanism that achieves the minmax objective (see [20]), i.e., to minimize the maximum delay among all users. We also consider the objective of Pareto efficiency.

Setting
Formally, in our setting, there are n users P = {p1, p2, · · · , pn} and m servers Q = {q1, q2, · · · , qm} (pi is called user i and qj is called server j). For a user pi, her desired file is stored on server di, i.e, q d i . The size of the file is ci units. If the amount of her available bandwidth 5 is x (x units of flow per second), she can finish her task in ci/x.
The connections between users form a directed graph G = (V, E), where V is the set of vertex in the graph, E is the set of edges. For a vertex in V , it denotes a user in P . A pair of users can connect with each other. For an edge u, v ∈ E, we assume there is not limitation in the edge u, v , in other words, arbitrarily large flow can pass through this edge. This is with out loss of generality -all results carry over to the setting where each edge has a capacity.
Also, each user pi can connect to a subset of servers. For a pair of user pi and server qj, there is an edge between them with bandwidth bi,j. That is, this edge can transmit at most bi,j units of flow per second. When bi,j = 0, there is no connection between pi and qj.
Each user has a bandwidth limitation locally. The total amount of flow she can download and share with others per second is at most vi. In reality, vi is the limitation that can depend on user i's hardware or software. A user pi can download her own file either by the edge directly between pi and q d i or indirectly from some pj's where pj downloads it from the edge pj and q d i .
Consider the illustrating example in Figure 2. The left nodes are users and the right nodes are servers. The solid lines denote connections between users and dashed lines denote connections between users and servers. In this example, user p3 could download its file through the edge p3, q2 , through the path p3, p1 , p1, q2 or the path p3, p1 , p1, p2 , p2, q2 . We assume that G, {bi,j} i=1...n j=1···m , {(di, ci)}i=1···n are public information that is shared by all users and the mechanism designer, while {vi} n i=1 is private information known only to each user i. Given a reported profile of (v1, v2, · · · , vn), a mechanism returns a flow assignment xi for each i (a multiple-route assignment).
Thus, we can define the environment {N , S, P, O, u} of this problem: • N denotes the set of n agents, • S = S1 × S2 × · · · Sn each Si = R represents the local bandwidth limitation vi, • P represents servers Q, the whole graph structures G = (V, E), {(di, ci)}i=1···n and all information about capacities on edges, • O is the set of all the possible assignments, • ui(o, p) = − c i x i where xi is i's total amount of flow in the assignment o.
Also we need to define individual rationality ri(·): for any agent i ∈ N , the flow she receives by a mechanism is greater than or equal to her direct route bandwidth b i,d i if she does not join the mechanism. Formally, ri(p) = b i,d i .

Max-Min objective subject to individual rationality
Lemma 1. The above environment is resource monotone and continuous.
For any u i ≤ ui, we can simply decrease xi to x i = −ci/u i ≤ −ci/ui = xi by cancelling xi − x i units of flow in the assignment. So it is continuous.
By theorem 4, we only need to give an algorithm to optimize mini ui(o). Because the multiple-commodity flow problem can be written in linear program, so we can get the algorithm by binary search and linear programming: . For all pi ∈ P , add constraint xi = x i 4. Solve the new LP to compute the assignment.

Pareto efficiency subject to individual rationality
By theorem 5, we know that if there exists an algorithm to find a serially optimal outcome o for monotone utility function, resource monotone environment and IR, it is a strategy-proof mechanism. Algorithm 6.3 gives the outcome we want. Almost all constraints are the same as what we listed in the previous section except that the seventh constraint ensures that the final solution (u1(o, p), · · · , un(o, p)) is the serially optimal one among all the outcomes.

5.
j xj,i + e ,j f j,e ≤ vi (e going into i) ; 6. k x k,i ≤ bi,j (where k have the following property: d k = j), for all i, j; 7. for all j ≤ i − 1, set xi = x * i where x * i 's are the xi's optimized so far; 8. all variables are non-negative; We have already checked the resource monotone condition and still need to check whether the utility function is monotone. To prove the lemma 2, we need to prove the following lemma. The lemma states that, it is without loss of generality to restrict to allocations where each user exhausts all its bandwidth.
Proof. First we prove that all bandwidth in i, di will always be used in some solution. Because of the inequalities xi ≥ b i,d i , the final bandwidth xi is at least b i,d i . If the bandwidth in the edge pi, q d i is not fully exhausted (let b be the remaining bandwidth in that edge), we can remove b i,d i − b bandwidth from other paths and add it into the edge i, di . This operation does not violate any constraint. So we can repeat this operation and finally all i, di is fully exhausted.
After having such a solution, we can modify some flow assignment so that all bandwidth in i, di will always be used by i in some solutions. Now every edge pi, q d i is fully used, we can use exchange techniques to let pi, q d i is only used by i. If part of pi, q d i is used by other user j, there must be a path from pi to p k and then from p k to q d i with bandwidth ε. We can give this path to user j (attached to the path from pj to pi) and give ε units bandwidth in pi, q d i to pi. Repeating this operations, we finally let all bandwidth in pi, q d i be used only by user i.
We now prove that the utility functions are monotone: Proof. For any i ∈ N and any inputs s1, · · · , sn, p, i will get ui(o, p) = − c i x i from the best outcome o. For any • x i = xi − ε, and for other x j = xj; • f j,e = fj,e for all possible j, e; Now we check whether the solution violates any constraint. For the first two inequalities, they still hold. For the third and sixth one, they aren't related to any new variables so it still holds. Because 0 < δ ≤ − c i x i + c i b i,d i , we find that Then, we will show that x1(·), · · · , xn(·) is continuous functions of variable ε. We can use the following lemma [1]: for the function x1(ε), there exists a closed interval [α, β], such that the LP is infeasible for all ε ∈ [α, β]; and in the interval [α, β], x1(ε) ⊆ R and it is a continuous convex piecewise linear function. So for x1(·), it is a continuous function. Now using induction, if we have proven that x1(·), · · · , x k (·) is continuous functions, then x k+1 (ε) = x k+1 (ε, x1(ε), · · · , x k (ε)). Using the theorem about multiparametric linear programming [12], we know that x k+1 is a continuous function over {ε, x1, · · · , x k }. Also because xi(·) is a continuous function of ε, it is easy to verify x k+1 (·) is a continuous function of ε according to the definition.
All the constraints hold. So these utility functions are monotone.
Lemma 2 implies algorithm 6.3 is strategy-proof. In addition, we can obtain order envy-freeness by sorting agents according to weights {lj} and types {sj} and optimizing them one by one. This is quite straightforward by theorem 6; To conclude the section, we have the following theorem: Theorem 7. There exists an IR and SP mechanism which minimizes maximal cost/delay and an IR, OEF and SP mechanisms which gives a Pareto efficient solution for the route allocation problem.

CONCLUSION AND FUTHER WORK
In this paper, we studied truthful mechanism design for a general class of resource allocation settings, where the center redistributes the private resources brought by individuals. We designed truthful mechanisms that achieve two objectives: maxmin and Pareto efficiency. For each objective, we provided a reduction that converts any optimal algorithm into a strategy-proof mechanism that achieves the same objective. Applying the reductions, one can systematically produce strategy-proof mechanisms in a non-trivial application: network route allocation.
There are a number of exciting research directions to extend this work. First of all, the mechanism for the maxmin objective is wasteful in the sense that all the players are brought down to a utility level that equals the maxmin. Is there another strategy proof mechanism that achieves maxmin but yields better social welfare? Second, one can consider the same set of objectives under more general settings where randomization is allowed. Last but not least, we are also interested in finding more applications to our general algorithmic mechanism design framework.