Efficiency and Stability in a Model of Wireless Communication Networks

Efficiency and Stability in a Model of Wireless Communication Networks

We introduce a model of (wireless communication) networks: a group of agents want to communicate with each other. Each agent can choose his communication range. Any two agents can directly communicate if each agent belongs to another agent’s communication range. Also, they can indirectly communicate if two agents are connected through a sequence of communication ranges between agents. Agents can benefit through the communication, but building a communication range is costly. Although efficiency and stability are not compatible in a general context, we identify an interesting subclass of problems where an efficient and stable network exists: the uniform interval model, the uniform circle model, and the communication favorable domain. Also, we investigate the consequence of allowing agents to relocate their positions. As it turns out, for a certain network, relocation-proofness is equivalent to stability.