Paper Info
Title
Towards Generic Low Payment Mechanisms for Decentralized Task Allocation: A Learning Based Approach
Abstract
We study the problem of procuring a cheap path in a disjoint path graph in which the edges belong to self interested agents. A wide range of task allocation problems can be reduced to this problem [2]. Motivated by recent negative results regarding incentive compatible mechanisms for the problem, our focus is on non incentive compatible mechanisms. Such mechanisms have both good and bad equilibria and therefore it is not clear how to analyze them. In this paper we take first steps towards the construction of generic low payment mechanisms for task allocation. We focus on simple mechanisms conveying minimal amount of information to the agents. By simulation, we investigate the behavior of the agents during repeated executions of the mechanism. We study three adaptive strategies for the agents, each represents a different learning approach. Our goal is to pinpoint phenomena which are consistent across all three types of strategies. We demonstrate that it may be possible to achieve long range payments overwhelmingly smaller than the payments of incentive compatible mechanisms. Several recommendations which facilitate obtaining low payments along with advises for avoiding pitfalls are given in the paper.
Year
DOI
Venue
2005
10.1109/ICECT.2005.96
CEC
Keywords
Field
DocType
decentralized task allocation,towards generic low payment,task allocation,long range payment,disjoint path graph,generic low payment mechanism,non incentive,task allocation problem,low payment,cheap path,incentive compatible mechanism,compatible mechanism,graph theory,industrial engineering,routing,resource allocation,engineering management,electronic commerce,production,supply chain management,supply chains,learning artificial intelligence,incentive compatibility
Graph theory,Graph,Mathematical optimization,Incentive compatibility,Adaptive strategies,Computer science,Supply chain management,Resource allocation,Supply chain,Payment
Conference
ISBN
Citations 
PageRank 
0-7695-2277-7
4
0.55
References 
Authors
9
2
Name
Order
Citations
PageRank
Amir Ronen11152169.60
Rina Talisman240.55