Q:

Template overload resolution with multiple viable types

Here are 2 template functions for calculating max
template<typename T>
auto max(T a, T b) {
  cout <<  "Calling 1\n";
  return b < a ? a : b;
}

template<typename T1, typename T2>
auto max (T1 a, T2 b) {
  cout <<  "Calling 2\n";
  return b < a ? a : b;
}

If I call the max function as follows
max(1, 2);

The first function (Calling 1) is selected. Why is that the case? Both 1 and 2 can match equally well in this case. 

A:

This is because the first max is more specialized as the second max.
What happens during template overload resolution is that the compiler instantiates both templates and then asks "Which one is more specialized?"
In a nutshell it asks, given overload A and overload B, "Can I instantiate B with the deduced type(s) from A, but not vice versa?" If so, then A is more specialized than B (we can go from A to B, but not back). It does the same thing the other way. If both can be instantiated from each other, it is ambiguous and a compiler error.
In reality, we don't use the actual type for T (int in this case), but some made-up type ("synthesized type").
In your case, the first template requires both types to be the same:
template<typename T>
auto max(T a, T b)

So we have max<int> (or max<synthesized1>)
Can we instantiate the second one given synthesized1 for T? Sure thing, T1 = synthesized1 and T2 = synthesized1.
Can we go the other way though?
The second template has two parameters, so it allows that a and b are different types, so it is more general. It gets instantiated with two synthesized types:
template<typename T1, typename T2>
auto max (T1 a, T2 b)

so, max<synthesized2, synthesized3>.
Can we instantiate the first max<T> with types synthesized2 and synthesized3? Nope, it requires that a and b have the same type. Therefore the first template is more specialized, and the compiler chooses it.
Refer to [temp.deduct.partial] for standardese

