|M.Sc Student||Rina Talisman|
|Subject||Towards Generic Low Payment Mechanisms for Decenteralized|
Task Allocation - A Learning Based Approach
|Department||Department of Industrial Engineering and Management||Supervisor||Mr. Ronen Amir|
|Full Thesis text|
Situations in which a set of tasks is to be allocated among self interested agents are of major importance in economics and electronic commerce. Perhaps the most natural requirement from a task allocation mechanism (protocol) is low spending. We study a representative task allocation problem of procuring a cheap path in a disjoint path graph, in which the edges belong to self interested agents. Motivated by recent negative results regarding incentive compatible mechanisms for the problem, our focus is on non incentive compatible mechanisms.
In this work we put aside the traditional game theoretic techniques and focus on a learning based approach. Through simulations and theoretical analysis, we investigate the performance of a simple first price mechanism during repeated execution. Our findings
indicate that it is possible to achieve low payments together with a high purchase ratio. This work contains many recommendations for the construction of low payment mechanisms along with possible pitfalls which should be avoided. Since a wide range of task allocation problems can be reduced to the problem we study, we believe that our results give a lot of hope for development of generic low payment mechanisms for decentralized task allocation.