These questions were inspired by the problem of designing a
cheat-proof program to play Magic: The Gathering over the Internet
that does not require a trusted third party. You don't have to answer
both questions if you don't want to.

Question 1:

Alice and Bob want to play a game over the Internet that is like a
simplified version of poker. These are the rules:

Alice and Bob ante one point.
Alice and Bob are each "dealt" a "card" with a random value from one
to ten. They can see their own card but cannot see their opponent's
card.
Alice and Bob may then wager additional points according to standard
poker procedure. (You may assume that Alice bets first.)
If neither player folds, Alice and Bob reveal their card to their
opponent. The player with the higher card value wins all the points
that were wagered. (Ignore ties.)

Neither Alice nor Bob considers the other trustworthy, and no third
party that is trusted by both Alice and Bob is available. How can this
game be played fairly?

Question 2:

Alice and Bob want to play "guess the number." The rules are:

Alice secretly chooses 0 or 1.
Bob publicly chooses either 0 or 1.
Alice reveals whether she originally chose 0 or 1.
If Bob's choice is the same as Alice's choice, Bob wins. If they are
different, Alice wins.

Once the game begins, Alice and Bob can only interact through a
communications system that can only send a message in one direction at
a time. Before the game begins but after they agree on a method of
playing the game, both players have as much time as they want to
prepare. (If they want 10^100 years, they have it, but they don't have
infinite time.) On the other hand, once the game actually begins,
Alice and Bob can't perform computationally infeasable calculations.
Neither player trusts the other, and no third party is available. How
can this game be played fairly?

Well, that's not quite what I had in mind. You're assuming the program
is a neutral third party; I should have made it clear that Alice and
Bob each have to run their own copy of all software they use, and are
capable of writing software that lies. What I really wanted to know
is, if the only way Alice and Bob can interact with each other is by
sending messages to each other, is there a way to ensure that if one
player tries to cheat, the other can always find out?

The basic problem seems to be this:
Suppose Alice and Bob want to play "guess the number: 0 or 1." They
want to devise a communications protocol so that neither of these
scenarios are possible:

Scenario 1
Alice: Here's my choice. It's [encrypted text: 0].
Bob decrypts the text and finds that it's 0.
Bob: I guess that you picked 0.
Alice: Here's the decryption key.
Bob: I was correct. I win.

Scenario 2
Alice: Here's my choice. It's [gibberish].
Bob: Here's my choice. It's 0.
Alice calculates a decryption key that will turn [gibberish] into 1.
Alice: Here's my decryption key.
Bob: I was wrong. You win.

Here's why the game can't be played. For this game, any decryption
method can be regarded as a function of two inputs, the decryption key
and the encrypted message. The range of this function can be
considered to be the set {0, 1, neither}. Once the message is chosen,
either there exists keys A and B such that F(A, message) = 0 and F(B,
message) = 1, or there isn't. If there are such keys, Alice could lie
to Bob about what she picked. If there are no such keys, Bob can find
out Alice's choice before he makes his own. The only loophole I can
see is to find encryption/decryption methods that make it extremely
difficult to find such keys (which is how cryptography is supposed to
work, I think).