Motivated by the ideas of asynchronous relaxation algorithms this paper investigates optimal decision-making problems that exhibit decentralized characteristics. Such problems consist of a collection of interacting sub-systems, each one described by local properties and dynamics, joined together by the need to accomplish a common task which achieves overall optimal performance. Special properties of such systems that make them ideally suited for the framework of asynchronous computing are (a) the lack of a single overall objective describing the collective performance, and (b) the asynchronism in implementing topologically optimal decisions based on information which is local in space and time. A methodology for decentralized decision making is developed based on the solution of a series of sub-problems in which each minimizes a local objective while maximizing a common Lagrangian function, by generating independent approximations of an ascent direction in the space of the dual variables. The concepts are illustrated by means of motivating examples.