A player may declare a companion only if that player's starting deck conforms to that companion's deckbuilding rule. You cannot directly check your opponent's deck for being legal for that companion; only a judge may perform a deck check. You assume the opponent follows all rules until you see they don't; in that case, you call a judge. That being said, there is no way for players to gain an unfair advantage from misconstructing a deck under the companion rules or otherwise, since all such attempts would become public the moment they would reveal the illegal card(s).
By declaring a card as a companion, a player claims that their current starting deck conforms to the additional deckbuilding rule imposed by that companion. If that player's current starting deck would not in fact be legal for that companion, the player is not allowed to declare that companion in the first place, let alone to cast it from outside the game. Of course, as stated above, you have no way of checking that at the start of a game, but the "contract" is that you believe the opponent until you see contrary evidence.
Declaring a companion happens before each game starts and is public knowledge, because the declared companion card is visible to all players while it's still in the sideboard:
702.138a Companion is a keyword ability that functions outside the game. It’s written as “Companion—[Condition].” Before the game begins, you may reveal one card you own from outside the game with a companion ability whose condition is fulfilled by your starting deck. (See rule 103.1b.) If you do, once during that game, you may play that card from outside the game.
Note that, unlike e.g. the Commander in Commander games, declaring a companion is neither mandatory nor fixed. If you choose to not declare a companion for a game, then there are no additional deckbuilding rules for that game. Sideboarding between games changes your starting deck and therefore might affect the legality of a certain companion. You can even declare a different companion for each game, as long as you sideboarded accordingly:
Starting Deck
After a player has set aside their sideboard, their remaining deck becomes their starting deck. See rule 103.1.
If, at any point during the game, a card that does violate the current companion's rule is revealed, you call a jduge who will then perform a deck check. I'm no judge, but intuitively, I would apply a harsh penalty (game loss) for illegally declaring a companion, even by mistake - declaring a companion can completely change the way their opponent would play the game. Even if the companion, or none of the illegal cards, are played, their implied potential can cause drastic strategic changes, such as withholding counters or removal.
If the illegal companion was declared intentionally, it would be cheating and cause for disqualification. Determining which applies is up to the judge.