The obvious way to attack a MAC is to try every key; therefore, if we use an n-bit key we need $2^n$ steps to break it.
But we can also try every tag in order to find the correct one, and in some concrete scenarios (e.g. CBC-MAC with AES-256) the tag is smaller than the key.
Does this mean that a MAC with n-bit keys and t-bit tags will offer $\min(n,t)$ bits of security, or is there something wrong with this reasoning?