Bargaining with the Devil: When to Negotiate, When to Fight