Apparatus, methods, and computer program products are disclosed that use a lease to manage interpersonal communications over a computer-mediated network such as a telephone network or the Internet, whether using textual, audio, or video communication means. The use of the lease allows enables negotiated evolution and revocation of a communication privilege in a socially-acceptable manner.