Asymptotically Tight Bounds for Inefficiency in Risk-Averse Selfish Routing
Authors: Thanasis Lianeas, Evdokia Nikolova, Nicolas E. Stier-Moses
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we provide the first lower bounds on the PRA. First, we show a family of structural lower bounds, which grow linearly with the size of the graph and players risk-aversion. They are tight for graph sizes that are powers of two. We also provide asymptotically tight functional bounds that depend on the allowed latency functions but not on the topology. The functional bounds match the price-of-anarchy bounds for congestion games multiplied by an extra factor that accounts for risk aversion. Finally, we provide a closed-form formula of the PRA for a family of graphs that generalize series-parallel graphs and the Braess graph. This formula also applies to the mean-standard deviation user objective a much more complex model of risk-aversion due to the cost of a path being non-additive over edge costs. |
| Researcher Affiliation | Collaboration | University of Texas at Austin {tlianeas|nikolova}@austin.utexas.edu Nicolas E. Stier-Moses Facebook Core Data Science nstier@fb.com |
| Pseudocode | No | The paper presents mathematical proofs and theoretical constructions but does not include any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any links to open-source code or state that code for the methodology is available. |
| Open Datasets | No | This paper is theoretical and does not involve experimental training on datasets. |
| Dataset Splits | No | This paper is theoretical and does not involve validation datasets for experiments. |
| Hardware Specification | No | This paper is theoretical and does not describe any specific hardware used for computations or experiments. |
| Software Dependencies | No | This paper is theoretical and does not mention specific software dependencies or versions required for experiments. |
| Experiment Setup | No | This paper is theoretical and does not describe any experimental setup details such as hyperparameters or training settings. |