TR09-145 Authors: Shankar Kalyanaraman, Chris Umans

Publication: 25th December 2009 10:16

Downloads: 2808

Keywords:

We study the complexity of {\em rationalizing} network formation. In

this problem we fix an underlying model describing how selfish

parties (the vertices) produce a graph by making individual

decisions to form or not form incident edges. The model is equipped

with a notion of stability (or equilibrium), and we observe a set of

``snapshots'' of graphs that are assumed to be stable. From this we

would like to infer some unobserved data about the system: edge

prices, or how much each vertex values short paths to each other

vertex.

We study two rationalization problems arising from the network

formation model of Jackson and Wolinsky \cite{JW96}. When the goal

is to infer edge prices, we observe that the rationalization problem

is easy. The problem remains easy even when rationalizing prices do

not exist and we instead wish to find prices that maximize the

stability of the system.

In contrast, when the edge prices are given and the goal is instead

to infer valuations of each vertex by each other vertex, we prove

that the rationalization problem becomes NP-hard. Our proof exposes

a close connection between rationalization problems and the

Inequality-SAT (I-SAT) problem.

Finally and most significantly, we prove that an approximation

version of this NP-complete rationalization problem is NP-hard to

approximate to within better than a 1/2 ratio. This shows that the

trivial algorithm of setting everyone's valuations to infinity

(which rationalizes all the edges present in the input graphs) or to

zero (which rationalizes all the non-edges present in the input

graphs) is the best possible assuming P $\ne$ NP. To do this we

prove a tight $(1/2 + \delta)$-approximation hardness for a variant

of I-SAT in which all coefficients are non-negative. This in turn

follows from a tight hardness result for $\text{{\sc

Max-Lin}}_{{\mathbb R}_+}$ (linear equations over the reals, with

non-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 without

the non-negativity constraint.

Our technical contributions regarding the hardness of I-SAT and

$\text{{\sc Max-Lin}}_{{\mathbb R}_+}$ may be of independent

interest, given the generality of these problems.