The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

In addition to the centralized matching algorithms developed in [19], we present two decentralized matching schemes for the Navy detailing process, decentralized linear programming matching and decentralized random matching, which accommodate the requirements for matching married couples, achieve high fill rate, and fill both priority and undesirable billets. In the decentralized linear programming (DLP) matching scheme Sailors submit applications to a detailer who determines the tentative matching in each stage of a multiple-stage process until the process converges. An exact winner determination model and a heuristic are provided. A near-optimal matching is shown to be achievable. The second scheme, a decentralized random matching (DRM), allows random preference and bilateral negotiation between the Sailor and the Command. We show that it produces a stable matching, just as a centralized deferred acceptance algorithm would. A performance comparison of both centralized and decentralized matching algorithms is presented to provide guidelines on when an algorithm should be preferred and how effective each algorithm is for the Navy detailing process.

Keywords

decentralized linear programming matching, decentralized random matching, Navy detailing process, stable matching, couples

Notes

Sponsor: Navy Personnel Research, Studies and Technology (NPRST)

Grant ID: N6610-98-D-9501

Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems

Associated Lab(s) / Group(s): Advanced Agent - Robotics Technology Lab

Number of pages: 23

Text Reference

Wei Yang, Katia Sycara, and Joseph Andrew Giampapa, "Decentralized Matching Schemes for the Navy Detailing Process," tech. report CMU-RI-TR-03-51, Robotics Institute, Carnegie Mellon University, December, 2003

BibTeX Reference

@techreport{Yang_2003_4564,
   author = "Wei Yang and Katia Sycara and Joseph Andrew Giampapa",
   title = "Decentralized Matching Schemes for the Navy Detailing Process",
   booktitle = "",
   institution = "Robotics Institute",
   month = "December",
   year = "2003",
   number= "CMU-RI-TR-03-51",
   address= "Pittsburgh, PA",
}

The Robotics Institute

Menu