We investigate a formal framework where agents use referrals from other agents to locate high-quality service providers. Agents have common knowledge about providers which are able to provide these services. The performance of providers is measured by the satisfaction obtained by agents from using their services. Provider performance varies with their current load. We assume that agents are truthful in reporting interaction experiences with providers and refer the highest quality provider known for a given task. The referral mechanism is based of the exchange value theory. Agents exchange both the name of the provider to use and the satisfaction obtained by using a referred provider. We present an algorithm for selecting a service provider for a given task which includes mechanisms for deciding when and who to ask for a referral. This mechanism requires learning, over interactions, both the performance levels of different service providers, as well as the quality of referrals provided by other agents. We use a satisficing rather than an optimizing framework, where agents are content to receive service quality above a threshold. We experimentally demonstrate the effectiveness of our algorithm in producing stable system configurations where reasonable satisfaction expectations of all agents are met.