2012/07/10 by Sergio Cabello, Cabello, Sergio
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #cs.DS #cs.GT
paper · pdf · doi:10.48550/arxiv.1207.2317
arxiv created 2012/07/10 · openalex publication_date 2012/07/10 · arxiv updated 2012/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G(V,E) be a directed graph with n vertices and m edges. The edges E of G are divided into two types: EF and EP. Each edge of EF has a fixed price. The edges of EP are the priceable edges and their price is not fixed a priori. Let r be a vertex of G. For an assignment of prices to the edges of EP, the revenue is given by the following procedure: select a shortest path tree T from r with respect to the prices (a tree of cheapest paths); the revenue is the sum, over all priceable edges e, of the product of the price of e and the number of vertices below e in T. Assuming that k=|EP|≥ 2 is a constant, we provide a data structure whose construction takes O(m+nlogk-1 n) time and with the property that, when we assign prices to the edges of EP, the revenue can be computed in (logk-1 n). Using our data structure, we save almost a linear factor when computing the optimal strategy in the Stackelberg shortest paths tree game of [D. Bilò and L. Gualà and G. Proietti and P. Widmayer. Computational aspects of a 2-Player Stackelberg shortest paths tree game. Proc. WINE 2008].