We have used density functional theory to study the structural stability of surface alloys. Our systems consist of a single pseudomorphic layer of $M_xN_{1-x}$ on the Ru(0001) surface, where $M$ = Fe or Co, and $N$ = Pt, Au, Ag, Cd, or Pb. Several of the combinations studied by us display a preference for atomically mixed configurations over phase-segregated forms. We have also performed further {it ab initio} calculations to obtain the parameters describing the elastic interactions between atoms in the alloy layer, including the effective atomic sizes at the surface. We find that while elastic interactions favor alloying for all the systems considered by us, in some cases chemical interactions disfavor atomic mixing. We show that a simple criterion (analogous to the Hume-Rothery first law for bulk alloys) need not necessarily work for strain-stabilized surface alloys, because of the presence of additional elastic contributions to the alloy heat of formation, that will tend to oppose phase segregation.