Is this set-up too complicated?

Your math is right, AFAIK. In a deck made of pairs, you'll have 1/n chances of dealing a pair to at least one player, n being the number of pairs in the deck (which in your game is also the number of players).

I can't figure a simple method to blindly deal two non-paired cards to each player. But I think I have an improvement over your deal-again method.

If one or more players have a pair, each player discards just one card, and keeps the other. Discarded cards are shuffled and dealt again. This process is repeated until no player has any pairs.

Now, if my maths are correct, by doing this you're going to have less chances of dealing a pair than reshuffling all the cards. In the worst scenario, each player will keep a different card, hence the chances of a pair will remain the same as with your method. But some other times two players will each keep half a pair, thus reducing the probability of a pair being dealt.

Seo

Yep, I'm affraid you're stuck with my worst case scenario. :-(

Maybe you can modify your relationship cards to include two names: if the first name is your character, you ignore it and use the second name. If the first name is not your character, you ignore the second name.

This will eliminate all the need for reshuffling, but will result in two characters being connected to a third. I don't know if this is posible in your game.

Or even more simple: add a rule "if the relationship card has your character name, ignore it and apply to the player on your right". That will only work if players characters are not kept secret.

Seo

It seems a simpler and faster (but still a little awkward) way of doing this would be: Everybody gets their character. Then the relationships are scattered in the table middle face down. Then go around the table like so:

1 - Take a card and look at it.
2 - If it's yourself, take a different card, then put yours back in and rescatter the cards.
3 - Next player!

As I understand it, you'll only have as many cards as there are players, so shuffling would be a pain anyway with so few cards. Scattering is really the easier method. Rescattering is quick and easy, and while you may have to do it as much as once per person (well, once for everybody but the last person!), you are guaranteed to never have to do more than 1 per person.

EDIT: Oops, I see the flaw in my plan. It's okay for the first person, but each later person who draws themselves later on gets information about who has them. And kind of vice-versa too, when you see someone have to return a card, you know they drew themselves which is all kinds of information.

Can you pre-deal one of each card, then offset and deal one of each card again to create the pairs, then randomly distribute the pairs?

I.e.:

deal J, Q, K, A face down.
then on top of that deal K, A, J, Q face down.
Randomly distibute the piles to players 1, 2, 3, and 4.

Or if you like, set the pairs together, 'shuffle' the pairs so they're still pairs but in a random or unknown order, then deal them out and offset the top row by moving them over once, then distribute the new 'sets of 2 cards which are no longer pairs'.

- Seth

I.e.:

deal J, Q, K, A face down.
then on top of that deal K, A, J, Q face down.
Randomly distibute the piles to players 1, 2, 3, and 4.

Or if you like, set the pairs together, 'shuffle' the pairs so they're still pairs but in a random or unknown order, then deal them out and offset the top row by moving them over once, then distribute the new 'sets of 2 cards which are no longer pairs'.

- Seth

But that would mean, unless I'm much mistaken, that everybody will be able to deduce what the other pairs are. If the character for each player is made public, you'll automatically have knowledge about their relationships too. If the players characters remain hidden, you'll still know what character is related to whom, though not what player has each pair. I'm not sure about how this will apply to your game in particular.

Seo