Simple sequencing problems with interdependent costs

• 成果类型: Article
• 署名作者: Hain, R; Mitra, M
• 署名单位: Indian Statistical Institute
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2003.09.005
• 发表日期: 2004
• 页码: 271-291
• 关键词: simple sequencing problems; Ex-post equilibrium; first best implementability

摘要

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.