A new approach is presented for solving infrastructure maintenance optimization problems involving multiple, conflicting, and incommensurable criteria. Pareto analysis is adapted from the theory of social welfare economics to identify the solutions that mutually achieve the best compromise among competing criteria. The proposed approach is applied to the domain of bridge maintenance management to assist decision makers in optimizing bridge preservation decisions. Two criteria are considered in this study: the minimization of life-cycle costs and the maximization of bridge network condition. Feasibility and capability of the proposed approach are demonstrated by using an application example of concrete bridge decks. The uncertainty in deck deterioration is considered by using stochastic Markov chain models developed from the condition data of concrete bridge decks in Nebraska. Further research is needed to expand the application of the proposed approach to other infrastructure facilities, and to consider other decision criteria, such as network reliability, functionality, and user cost.