  Load balancing is a well-studied problem, with balls-in-bins being the
primary framework. The greedy algorithm $\mathsf{Greedy}[d]$ of Azar et al.
places each ball by probing $d > 1$ random bins and placing the ball in the
least loaded of them. With high probability, the maximum load under
$\mathsf{Greedy}[d]$ is exponentially lower than the result when balls are
placed uniformly randomly. V\"ocking showed that a slightly asymmetric variant,
$\mathsf{Left}[d]$, provides a further significant improvement. However, this
improvement comes at an additional computational cost of imposing structure on
the bins.
  Here, we present a fully decentralized and easy-to-implement algorithm called
$\mathsf{FirstDiff}[d]$ that combines the simplicity of $\mathsf{Greedy}[d]$
and the improved balance of $\mathsf{Left}[d]$. The key idea in
$\mathsf{FirstDiff}[d]$ is to probe until a different bin size from the first
observation is located, then place the ball. Although the number of probes
could be quite large for some of the balls, we show that
$\mathsf{FirstDiff}[d]$ requires only at most $d$ probes on average per ball
(in both the standard and the heavily-loaded settings). Thus the number of
probes is no greater than either that of $\mathsf{Greedy}[d]$ or
$\mathsf{Left}[d]$. More importantly, we show that $\mathsf{FirstDiff}[d]$
closely matches the improved maximum load ensured by $\mathsf{Left}[d]$ in both
the standard and heavily-loaded settings. We further provide a tight lower
bound on the maximum load up to $O(\log \log \log n)$ terms. We additionally
give experimental data that $\mathsf{FirstDiff}[d]$ is indeed as good as
$\mathsf{Left}[d]$, if not better, in practice.
