We present a new inter-domain traffic engineering protocol based on the concepts of Nash bargaining and dual decomposition. Under this scheme, ISPs use an iterative procedure to jointly optimize a social cost function, referred to as the Nash product. We show that the global optimization problem can be separated into sub-problems by introducing appropriate shadow prices on the inter-domain flows. These sub-problems can then be solved independently and in a decentralized manner by the individual ISPs. Our approach does not require the ISPs to share any sensitive internal information (such as network topology or link weights). More importantly, our approach is provably Pareto-efficient and fair. Therefore, we believe that our approach is highly amenable to adoption by ISPs when compared to past naive approaches. We conduct simulation studies of our approach over several real ISP topologies. Our evaluation shows that the approach converges quickly, offers equitable performance improvements to ISPs, is significantly better than unilateral approaches (e.g. hot potato routing) and offers the same performance as a centralized solution with full knowledge.