We consider a model of an information network where nodes can fail and transmission of information is costly. The formation of paths in such networks is modeled as the Nash equilibrium of an N player routing game. The task of obtaining this equilibrium is shown to be NP-Hard. We derive analytical results to identify conditions under which the equilibrium path is congruent to well known paths such as the most reliable or cheapest neighbor path. The issue of characterizing off-equilibrium paths in the game is addressed and different path utility metrics proposed. Our first metric measures the degree of individual node suboptimality by evaluating paths in terms of the weakness of the worst-off player. It is shown that there exist information networks not containing paths of weakness less than Vr/3. Consequently, guaranteeing approximate equilibrium paths of bounded weakness is computationally difficult. We next propose a team game with players having a common payoff function whose equilibrium outcome can be computed in polynomial time. Finally, a fair team game with bounded payoff difference is proposed whose equilibrium is also easily computable.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Strategic path reliability in information networks


    Beteiligte:

    Erscheinungsdatum :

    2002-01-01


    Anmerkungen:

    RePEc:diw:diwwpp:dp298


    Medientyp :

    Paper


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    330 / 629




    Strategic path reliability in information networks

    Kannan, Rajgopal / Sarangi, Sudipta / Iyengar, Sundaraja Sitharama | BASE | 2002

    Freier Zugriff

    Strategic path reliability in information networks

    Kannan, Rajgopal / Sarangi, Sudipta / Iyengar, Sundaraja Sitharama | BASE | 2002

    Freier Zugriff

    Intent Inference and Strategic Path Prediction

    Krozel, Jimmy / Andrisani, Dominick | AIAA | 2005


    Estimating Path Travel-Time Reliability

    Rakha, H.A. / EL-Shawarby, I. / Arafeh, M. et al. | IEEE | 2006