Alice trusts Bob only when Bob trusts Alice
This sounds like a fair exchange protocol where what is exchanged is a digital signature. 
Per this paper, these are impossible without trusted third parties. 

With a trusted third party, they are possible. Indeed people have proposed schemes that do what you describe again relying on a third party in the case of failure.