Simple sequencing problems with interdependent costs

In this paper we analyze simple sequencing problems under incomplete information and interdependent costs. We prove the necessity of concave cost function for implementability of such problems. Implementability means that one can achieve aggregate cost minimization in expost equilibrium. We also show that simple sequencing problems are implementable if and only if the mechanism is a 'generalized VCG mechanism.' We then consider first best implementability, that is implementability with budget balancing transfer. We prove that for implementable n agent simple sequencing problems, with polynomial cost function of order (n - 2) or less, one can achieve first best implementability. Finally, for the class of implementable simple sequencing problems with "sufficiently well behaved" cost function, this is the only first best class. (C) 2003 Elsevier Inc. All rights reserved.