Let's say that there is a message which is considered valid if signed by both Alice and Bob.

Alice could sign the message and then give it to Bob, so that he can sign it and give it back to her.

But, for various reasons, Alice doesn't want Bob to have a fully-signed message that she doesn't also have. If she just signs it and sends it, he could sign it and not send it back.

Is there some way that both of them can sign the message (maybe interactively?) so that it doesn't become valid for Bob if it isn't also valid for Alice?

(This could be done by a trusted third party who would simply escrow the message until it had received both signatures, and then release both signatures to Alice and Bob. Of course, I want a solution without a third party.)