Oxides with the cubic fluorite structure, e.g., ceria (CeO2), are known to be good solid electrolytes when they are doped with cations of lower valence than the host cations. The high ionic conductivity of doped ceria makes it an attractive electrolyte for solid oxide fuel cells, whose prospects as an environmentally friendly power source are very promising. In these electrolytes, the current is carried by oxygen ions that are transported by oxygen vacancies, present to compensate for the lower charge of the dopant cations. Ionic conductivity in ceria is closely related to oxygen-vacancy formation and migration properties. A clear physical picture of the connection between the choice of a dopant and the improvement of ionic conductivity in ceria is still lacking. Here we present quantum-mechanical first-principles study of the influence of different trivalent impurities on these properties. Our results reveal a remarkable correspondence between vacancy properties at the atomic level and the macroscopic ionic conductivity. The key parameters comprise migration barriers for bulk diffusion and vacancy-dopant interactions, represented by association (binding) energies of vacancy-dopant clusters. The interactions can be divided into repulsive elastic and attractive electronic parts. In the optimal electrolyte, these parts should balance. This finding offers a simple and clear way to narrow the search for superior dopants and combinations of dopants. The ideal dopant should have an effective atomic number between 61 (Pm) and 62 (Sm), and we elaborate that combinations of Nd/Sm and Pr/Gd show enhanced ionic conductivity, as compared with that for each element separately.