Accession Number:

ADA525341

Title:

Distributed Auction Algorithms for the Assignment Problem with Partial Information

Descriptive Note:

Conference paper

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF INFORMATION SCIENCES

Report Date:

2010-06-01

Pagination or Media Count:

15.0

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 andor 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.

Subject Categories:

  • Information Science

Distribution Statement:

APPROVED FOR PUBLIC RELEASE