Research On Some Optimization Problems On Mechanism Design

Mechanism design is the sub-field of microeconomics and game theory that considers how to implement good system-wide solutions. A large part of research in computer science is concerned with protocols and algorithms for interconnected collections of computers. The designer of such an algorithm or protocol algorithm or protocol always makes an implicit assumption that the participating computers will act as instructed - except, perhaps, for the faulty or malicious ones. Computers on the Internet belong to different persons or organizations and will likely do what is most beneficial to their owners. We cannot simply expect each computer on the Internet to faithfully follow the designed protocols or algorithms. It is more reasonable to expect that each computer will try to manipulate it for its owners' benefit. Such an algorithm or protocol must therefore be designed in advance for this kind of behavior! In this paper we suggested a framework for studying optimization problems that involve selfish participants. As such participants, agents are capable of manipulating the algorithm; the algorithm designer should ensure in advance that the agents' interests are best served by telling truthfully. Following notions from the field of mechanism design, we suggest a framework for studying such algorithms. In this model the algorithmic solution is adorned with payments to the participants. The payments should be carefully chosen as to motivate all participants to act as the algorithm designer wishes. First, we introduce the basic notions and basic property of mechanism design. Then, we apply the standard tools of mechanism design to the shortest paths problem and the minimum spanning tree problem. Finally, task scheduling problem is concerned in this paper. We present several theorems regarding this problem including an approximation mechanism, lower bounds and a randomized mechanism.