טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentTalisman Rina
SubjectTowards Generic Low Payment Mechanisms for Decenteralized
Task Allocation - A Learning Based Approach
DepartmentDepartment of Industrial Engineering and Management
Supervisor Mr. Amir Ronen
Full Thesis textFull thesis text - English Version


Abstract

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.