Love this!

My general problem with Pokémon (at least the older versions, haven't played the latest) is that when playing against others it frequently just boils down to the same set of legendary and overpowered mons.

You sort of addressed this running the milp without certain mons as options, which makes sense.

But you already have the machinery for a better constraint: max total base stat. You could think of it as "weight classes" in box.

So, for a given weight class, your team can only add up to Y in total base stat. You can squeeze one of the OP mons, but then the rest are slackers. Or you could balance them.

It makes it a lot more interesting and invites for diversity. And you could run it for many different values of Y.

It's a good idea but base stats aren't everything: https://youtu.be/gEkMi_y3Wzo

That's why the competitive scene maintains a listing of tiers across generations derived from analyzing the actual usages across thoughful battles. https://www.smogon.com/sm/articles/sm_tiers

In competitive Pokémon there are usually different tiers of which Pokémon are accepted. In most legendaries are limited or fully banned.

For the mainline games it usually does not matter. You can beat it with any single Pokémon pretty much.

You'd need something which better encapsulates the power level of a pokemon; move pools, abilities, typing and synergies all play a role. There are bad pokemon with a huge base stat total, and a hypothetical pokemon with a tiny base stat total of 50 but with ground/poison typing and the wonder guard ability would be an absolute nightmare.

The Smogon tiers (NU, RU, UU, UUBL, OU, Uber) is a thorough attempt at placing all pokemon in tiers based on overall power level and to make interesting balanced matches at different tiers.

That's a great idea!

Follow up thought: it would be cool if you imagine a match to consist of three sets each for a different class.

So each player comes with three teams of small, mid and large base stat classes. You can't repeat monster across teams. Whoever wins 2/3 wins the match.

...

And if this was my college house, we would have a price system for the mons so you wouldn't be able to repeat mons even between players. But that's a different thing altogether.

That property is true in most games though, unless it is heavily optimized for 'balance'. Consider Chess, or Poker, or Soccer, if both players play correctly a huge range of strategies are just easily exploitable and thus unplayed.

That said, complexity emerges and explodes in the tiny differences, even if there's like 8 pokemon that are in 95% of teams, and 10 situational pokemon that appear 5% of the times, that's like C(6,8) teams which is like 56 possible teams of Uber pokemon, and a buttload of possible teams with situational pokemon like choice scarf ditto, eviolite Chansey, nuzzle u-turn super fang pachirisu, etc...

Even if the teams were the same, just the possible differences in movesets create a lot of different sets, suppose 6 possible moves for each mon, you have C(4,6) sets for each mon, each with their own probability weight as well.