We study the complexity of {\em rationalizing} network formation. Inthis problem we fix an underlying model describing how selfishparties (the vertices) produce a graph by making individualdecisions to form or not form incident edges. The model is equippedwith a notion of stability (or equilibrium), and we observe a set of``snapshots'' of graphs that are assumed to be stable. From this wewould like to infer some unobserved data about the system: edgeprices, or how much each vertex values short paths to each othervertex.

We study two rationalization problems arising from the networkformation model of Jackson and Wolinsky \cite{JW96}. When the goalis to infer edge prices, we observe that the rationalization problemis easy. The problem remains easy even when rationalizing prices donot exist and we instead wish to find prices that maximize thestability of the system.

In contrast, when the edge prices are given and the goal is insteadto infer valuations of each vertex by each other vertex, we provethat the rationalization problem becomes NP-hard. Our proof exposesa close connection between rationalization problems and theInequality-SAT (I-SAT) problem.

Finally and most significantly, we prove that an approximationversion of this NP-complete rationalization problem is NP-hard toapproximate to within better than a 1/2 ratio. This shows that thetrivial algorithm of setting everyone's valuations to infinity(which rationalizes all the edges present in the input graphs) or tozero (which rationalizes all the non-edges present in the inputgraphs) is the best possible assuming P = NP. To do this weprove a tight (12+) -approximation hardness for a variantof I-SAT in which all coefficients are non-negative. This in turnfollows from a tight hardness result for {\sc Max-Lin}R+ (linear equations over the reals, withnon-negative coefficients), which we prove by a (non-trivial)modification of the recent result of Guruswami and Raghavendra\cite{GR07} which achieved tight hardness for this problem withoutthe non-negativity constraint.

Our technical contributions regarding the hardness of I-SAT and{\sc Max-Lin}R+ may be of independentinterest, given the generality of these problems.