We consider the problem of distributed packet selection and scheduling for multiple video streams sharing a communication channel. An optimization framework is proposed to enable the multiple senders to coordinate their packet transmission schedules, such that the overall quality over the video clients is maximized. The framework relies on rate-distortion information that is used to characterize a video packet and that consists of two quantities: the size of the packet in bits, and its importance for the reconstruction quality of the corresponding stream. Using the framework, each of the senders allocates to its own video packets a share of the bandwidth available on the communication channel, that is proportional to the relative importance of these packets. Thereby, a decentralized streaming strategy is provided that allows for trading-off rate and distortion, not only within a single video stream, but also across different streams. Simulation results demonstrate that, for the difficult case of scheduling non-scalably encoded video streams, our framework substantially outperforms a conventional streaming system that does not consider the relative importance of the video packets. The gains in performance reach up to 8 dB in both streaming scenarios under examination, namely adaptation to random packet loss and simultaneous adaptation to packet loss and available bandwidth.