Distributed Auction Algorithms for the Assignment Problem with Partial Information
Loading...
Authors
Park, Chulwoo
An, Woosun
Pattipati, Krishna R.
Kleinman, David L.
Subjects
assignment problem
blackboard coordination structure
distributed auction algorithm
Maritime Operations Centers (MOC),
blackboard coordination structure
distributed auction algorithm
Maritime Operations Centers (MOC),
Advisors
Date of Issue
2010-06-22
Date
Publisher
Monterey, CA; Naval Postgraduate School
Language
Abstract
Task-asset assignment is a fundamental problem paradigm in a wide variety of applications. Typical problem setting involves a single decision maker (DM) who has complete knowledge of the weight (reward, benefit, accuracy) matrix and who can control any of the assets to execute the tasks. Motivated by planning problems arising in distributed organizations, this paper introduces a novel variation of the assignment problem, wherein there are multiple DMs and each DM knows only a part of the weight matrix and/or controls a subset of the assets. We extend the auction algorithm to such realistic settings with various partial information structures using a blackboard coordination structure. We show that by communicating the bid, the best and the second best profits among DMs and with a coordinator, the DMs can reconstruct the centralized assignment solution. The auction setup provides a nice analytical framework for formalizing how team members build internal models of other DMs and achieve team cohesiveness over time.
Type
Article
Presentation
Presentation
Description
Series/Report No
Department
Information Science
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
15th International Command and Control Research and Technology Symposium (ICCRTS), June 22-24, 2010, Santa Monica, CA "Where have we been? Where are we going?"
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.