What happens if a tribute effect has no valid target?
The Tribute ability and abilities that trigger if the tribute wasn't paid are separate. It is perfectly legitimate for an opponent to not pay a tribute when there is no target for the ability that will trigger afterward. As with any such cases, that ability will then be countered automatically.

Why this is the case is not quite as straightforward, since the rules are a little roundabout about it, but tribute, being a static ability (like unleash) is just something that goes on as the creature enters the battlefield (what makes it feel very different is the delay introduced by the opponent choosing instead of you). The tribute-bound ability will trigger after that, when the creature is on the battlefield, and depending on the opponent's choice. At that point, if it has no target, it will fizzle normally (the same as when you control no other creature and cast Breaching Hippocamp).