Karn Liberated Ultimate vs Yorion

Question

So lets say I use the +4 on Karn Liberated, exiling two cards from my opponent's hand, and my opponent also is using Yorion, Sky Nomad as their companion, with a deck size of 80. Now when I restart the game with Karn's ultimate, would they be allowed to reveal Yorion as their companion even though their deck has only 78 cards? Additionally shouldn't restarting the game with Karn win the game if the opponents deck is only at 59 cards when the new game starts?

Answer 1

Restarting the game does not worry about a deck's legality, but it will recheck the companion condition

Restarting the game runs through the entirety of the start game procedures

721.1. One card (Karn Liberated) restarts the game. A game that is restarted immediately ends. No players in that game win, lose, or draw that game. All players in that game when it ended then start a new game following the procedures set forth in rule 103, “Starting the Game,” with the following exception:
721.1a The starting player in the new game is the player who controlled the spell or ability that restarted the game.

The game start procedures are as follows (abbreviated):

1. Determine start player (skipped as per 721.1a)
2. Set aside sideboards and substituted cards (double faced cards in decks without sleeves)
3. Reveal companions (optional)
4. Reveal commanders (if playing Commander or Brawl)
5. Set aside Conspiracies (if playing Conspiracy Draft)
6. Shuffle the decks, which become libraries.
7. Life totals are set
8. Each player draws their starting hand, and mulligans
9. Take opening hand actions (eg Leylines)
10. Turn over the top card of the Planar deck (if playing Planechase)
11. Starting player takes their first turn.

Notably, checking the legality the deck never happens. I actually can't find anywhere in the rules where deck legality is checked, but rule 721.3 explicitly covers the case where the player's starting hand is less than the number of cards in their deck, thereby implying that a deck with fewer cards than the deck minimum (but greater than 7) can be used without causing a game loss.

However, the part where companions are revealed does check deck construction.

103.2b If a player wishes to reveal a card with a companion ability that they own from outside the game, they may do so after setting aside their sideboard. A player may reveal no more than one card this way, and they may do so only if their deck fulfills the condition of that card’s companion ability. (See rule 702.139, “Companion.”)

And Karn's ability doesn't merely move cards around - it really is changing which cards are part of the deck being used to restart the game with.

721.5. Effects may exempt certain cards from the procedure that restarts the game. These cards are not in their owner’s deck as the new game begins.

That said, if Yorian (or any other companion) was pulled into your hand, it will be part of your deck and ineligible to be a companion

721.2. All Magic cards involved in the game that was restarted when it ended, including phased-out permanents and nontraditional Magic cards, are involved in the new game, even if those cards were not originally involved in the restarted game. Ownership of cards in the new game doesn’t change, regardless of their location when the new game begins. Example: A player casts Living Wish, bringing a creature card into the game from outside the game. Then that game is restarted. The creature card will be part of that player’s library when the new game begins.

(Incidentally, this rule doesn't affect Commanders, because Commanders are taken from inside your deck, not from outside the game like companions are. So a Commander can always be revealed and put in the command zone even if it was put into play, or in a library, or still in the command zone.)

Answer 2

No, a reduced deck size in a restarted game does not cause an immediate loss or invalidation of a companion requirement,

Karn Liberated's ability to restart the game does not involve deck construction. Deck construction (and possible violations thereof) happen before starting the main game. Changes to the deck size through bringing in additional cards or having cards exiled before Karn Liberated's ability restarts the game do not count as a violation of deck construction. Therefore a changed deck size does not cause an immediate loss as Karn Liberated's ability resolves.

There is no explicit clarification on this point in the rules. However, the rules do acknowledge that a deck size may change before restarting the game:

719.1. One card (Karn Liberated) restarts the game. A game that is restarted immediately ends. No players in that game win, lose, or draw that game. All players in that game when it ended then start a new game following the procedures set forth in rule 103, “Starting the Game,” with the following exception:

719.2. All Magic cards involved in the game that was restarted when it ended, including phased-out permanents and nontraditional Magic cards, are involved in the new game, even if those cards were not originally involved in the restarted game. Ownership of cards in the new game doesn’t change, regardless of their location when the new game begins. Example: A player casts Living Wish, bringing a creature card into the game from outside the game. Then that game is restarted. The creature card will be part of that player’s library when the new game begins.

719.3. Because each player draws seven cards when the new game begins, any player with fewer than seven cards in their library will lose the game when state-based actions are checked during the upkeep step of the first turn, regardless of any mulligans that player takes. (See rule 704, “State-Based Actions.”)

There is no format where fewer than 7 cards would be a legal starting deck size, so if the rules handle that case, it is implicit that a lower deck size would not be an inherent game loss.

Answer 3

The cards are still owned by your opponent and part of your opponent's deck, even if they start the game in exile and then move to the battlefield. This has been a fairly frequently asked question ever since Karn was previewed (2009 thread, 2012 thread, I'm sure you can find more...) but has never had an explicit ruling from Wizards that works this however; on the other hand, everyone agrees it's obvious that Karn's ultimate isn't intended to act as "win the game if you've exiled one card from your opponent".