Auction-Based On-Demand P2P Min-Cost Media Streaming with Network Coding Realizing on-demand media streaming in a peer-to-peer (P2P) fashion is more challenging than in the case of live media streaming, since only peers with close-by media play progresses may help each other in obtaining the media content. The situation is further complicated if we wish to pursue low aggregated link cost in the transmission. In this paper, we present a new algorithmic perspective toward on-demand P2P streaming protocol design. While previous approaches employ streaming trees or passive neighbor reconciliation for media content distribution, we instead coordinate the streamingsession as an auction where each peer participates locally by bidding for and selling media flows encoded with network coding. We show that this auction approach is promising in achieving low-cost on-demand streaming in a scalable fashion. It is amenable to asynchronous, distributed, and lightweight implementations, and is flexible to provide support for random-seek and pause functionalities. Through extensive simulation studies, we verify the effectiveness and performance of the proposed auction approach, focusing on the optimality in overall streaming cost, the convergence speed, and the communication overhead.