Optimization Algorithms and Equilibrium Analysis for Dynamic Resource Allocation
Abstract
We consider optimization and equilibrium models and algorithms for dynamic resource allocation. The most important accomplishment would be the paper: The Simplex and Policy-Iteration Methods are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate, where I proved that the classic policy-iteration method (Howard 1960), including the Simplex method (Dantzig 1947) with the most-negative-reduced-cost pivoting rule, is a strongly polynomial-time exact algorithm for solving the Markov decision problem (MDP) exactly with any fixed discount factor. Markov decision process (e.g., Shapley, 1953) is arguably one of the most widely used decision models and methodologies in practice, as a celebrated example to showcase the power of optimization to help making sensible decisions in a complex system and stochastic environment. And the two methods are the most used methods but their theoretical complexities were open before this result. We also explore an online resource allocation in a set of research publications, including prediction market, Internet auction, and etc.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 31, 2012
- Accession Number
- ADA564449
Entities
People
- Yinyu Ye
Organizations
- Stanford University