Transcoding proxy caching is an important technology for improving the services over Internet, especially in the environment of mobile computing systems. In this paper, we address cooperative determination on cache replacement candidates for transcoding proxies. An original model which determines cache replacement candidates on all candidate nodes in a coordinated fashion with the objective of minimizing the total cost loss is proposed. We formulate this problem as an optimization problem and present a low-cost optimal solution for deciding cache replacement candidates.