The Price of Stability for Network Design with Fair Cost Allocation
From MaRDI portal
Publication:3395046
DOI10.1137/070680096zbMath1173.91321OpenAlexW2095094403WikidataQ92406531 ScholiaQ92406531MaRDI QIDQ3395046
Tim Roughgarden, Tom Wexler, Anirban Dasgupta, Elliot Anshelevich, Éva Tardos, Jon M. Kleinberg
Publication date: 20 August 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070680096
Related Items
Cost-Sharing in Generalised Selfish Routing ⋮ Tight Inefficiency Bounds for Perception-Parameterized Affine Congestion Games ⋮ Pareto Efficiency and Approximate Pareto Efficiency in Routing and Load Balancing Games ⋮ Improved Lower Bounds on the Price of Stability of Undirected Network Design Games ⋮ The complexity of welfare maximization in congestion games ⋮ On the Uniqueness of Equilibrium in Atomic Splittable Routing Games ⋮ Tight Bounds for Cost-Sharing in Weighted Congestion Games ⋮ Further Results on Capacitated Network Design Games ⋮ Cost-Sharing Scheduling Games on Restricted Unrelated Machines ⋮ Efficient coordination mechanisms for unrelated machine scheduling ⋮ Unnamed Item ⋮ Strong equilibria in games with the lexicographical improvement property ⋮ The Price of Matching with Metric Preferences ⋮ Selfish Vector Packing ⋮ On the convergence of multicast games in directed networks ⋮ Computing Approximate Nash Equilibria in Network Congestion Games with Polynomially Decreasing Cost Functions ⋮ The Curse of Sequentiality in Routing Games ⋮ Inverse Game Theory: Learning Utilities in Succinct Games ⋮ A Selective Tour Through Congestion Games ⋮ Multicast Network Design Game on a Ring ⋮ Improved lower bounds on the price of stability of undirected network design games ⋮ Social interactions and the prophylaxis of SI epidemics on networks ⋮ Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions ⋮ Scheduling selfish jobs on multidimensional parallel machines ⋮ Wary of the worst: maximizing award guarantees when new claimants may arrive ⋮ Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids ⋮ Network Creation Games: Think Global – Act Local ⋮ Sharing Non-anonymous Costs of Multiple Resources Optimally ⋮ Incentive ratio: a game theoretical analysis of market equilibria ⋮ Implementation of optimal schedules in outsourcing with identical suppliers ⋮ The anarchy of scheduling without money ⋮ Optimal Cost-Sharing in General Resource Selection Games ⋮ Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games ⋮ The Inefficiency of Nash and Subgame Perfect Equilibria for Network Routing ⋮ Pareto optimal equilibria for selfish bin packing with uniform cost sharing ⋮ Strategic Scheduling Games: Equilibria and Efficiency ⋮ On the Price of Stability of Undirected Multicast Games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On equilibria for ADM minimization games ⋮ Unnamed Item ⋮ Efficiency analysis of load balancing games with and without activation costs ⋮ Selfish Transportation Games ⋮ Resource Allocation Games with Multiple Resource Classes ⋮ The price of stability for undirected broadcast network design with fair cost allocation is constant ⋮ How many attackers can selfish defenders catch? ⋮ What price stability? Social welfare in matching markets ⋮ Quality of equilibria for selfish bin packing with cost sharing variants ⋮ On the price of stability of some simple graph-based hedonic games ⋮ Selfish Bin Packing ⋮ Stability vs. optimality in selfish ring routing ⋮ A bin packing game with cardinality constraints under the best cost rule ⋮ Hierarchical Network Formation Games ⋮ Computation and efficiency of potential function minimizers of combinatorial congestion games ⋮ A Method with Convergence Rates for Optimization Problems with Variational Inequality Constraints ⋮ Trouble comes in threes: core stability in minimum cost connection networks ⋮ Restoring Pure Equilibria to Weighted Congestion Games ⋮ Approximate Strong Equilibrium in Job Scheduling Games ⋮ Local smoothness and the price of anarchy in splittable congestion games ⋮ $\mathcal{NP}$ -Hardness of Pure Nash Equilibrium in Scheduling and Connection Games ⋮ Cooperation in Multiorganization Matching ⋮ Equilibria in Online Games ⋮ The price of anarchy of affine congestion games with similar strategies ⋮ Multi-commodity Source Location Problems and Price of Greed ⋮ Dynamic resource allocation games ⋮ Congestion Games with Variable Demands ⋮ Price of anarchy and price of stability in multi-agent project scheduling ⋮ Competitive Cost Sharing with Economies of Scale ⋮ The Price of Anarchy of a Network Creation Game with Exponential Payoff ⋮ The Local and Global Price of Anarchy of Graphical Games ⋮ Unnamed Item ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ Dynamic Atomic Congestion Games with Seasonal Flows ⋮ Location Games on Networks: Existence and Efficiency of Equilibria ⋮ Informational Braess’ Paradox: The Effect of Information on Traffic Congestion ⋮ Exact enforcement value of soft correlated equilibrium for generalized chicken and prisoner's dilemma games ⋮ Quality of strong equilibria for selfish bin packing with uniform cost sharing ⋮ A Characterization of Undirected Graphs Admitting Optimal Cost Shares ⋮ Dynamic Resource Allocation Games ⋮ The Price of Stability of Simple Symmetric Fractional Hedonic Games ⋮ Designing Cost-Sharing Methods for Bayesian Games ⋮ Network investment games with Wardrop followers ⋮ Dynamics of Profit-Sharing Games ⋮ Inequality and Network Formation Games ⋮ Unnamed Item ⋮ Stable cost sharing in production allocation games ⋮ Efficient Black-Box Reductions for Separable Cost Sharing ⋮ On Stackelberg strategies in affine congestion games ⋮ Pricing in Information Orchestrators and Maximizing Stable Networks ⋮ The Price of Stability of Weighted Congestion Games ⋮ Balancing Load via Small Coalitions in Selfish Ring Routing Games ⋮ Geometric spanner games ⋮ Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games ⋮ Welfare Guarantees in Schelling Segregation ⋮ The Price of Stability of Weighted Congestion Games ⋮ Some anomalies of farsighted strategic behavior ⋮ Enforcing efficient equilibria in network design games via subsidies ⋮ Self-organizing Flows in Social Networks ⋮ Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines ⋮ Bottleneck links, variable demand, and the tragedy of the commons ⋮ Egalitarian-utilitarian bounds in Nash's bargaining problem ⋮ The price of anarchy and stability in general noisy best-response dynamics ⋮ Distance hedonic games ⋮ Strong equilibrium in cost sharing connection games ⋮ An abstraction-refinement methodology for reasoning about network games ⋮ Optimal cost sharing for capacitated facility location games ⋮ Atomic routing games on maximum congestion ⋮ A parallel machine schedule updating game with compensations and clients averse to uncertain loss ⋮ How to split the costs and charge the travellers sharing a ride? Aligning system's optimum with users' equilibrium ⋮ Cost-sharing scheduling games on restricted unrelated machines ⋮ Stability in the self-organized evolution of networks ⋮ Efficiency analysis with respect to the unit cost objectives in scheduling games ⋮ Beyond Pigouvian taxes: a worst case analysis ⋮ Sharing loading costs for multi compartment vehicles ⋮ Network-formation games with regular objectives ⋮ Incentive compatible and globally efficient position based routing for selfish reverse multicast in wireless sensor networks ⋮ Mixing time and stationary expected social welfare of logit dynamics ⋮ The quality of equilibria for set packing and throughput scheduling games ⋮ Implementing efficient graphs in connection networks ⋮ An efficient Nash-implementation mechanism for network resource allocation ⋮ Social context congestion games ⋮ Maximizing the minimum load: the cost of selfishness ⋮ Nash equilibria with minimum potential in undirected broadcast games ⋮ \(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games ⋮ Minimum cost connection networks: truth-telling and implementation ⋮ Timing matters: online dynamics in broadcast games ⋮ Equilibria in routing games with edge priorities ⋮ Strategic cooperation in cost sharing games ⋮ Inefficiency of equilibria for scheduling game with machine activation costs ⋮ The price of envy-freeness in machine scheduling ⋮ Coordination mechanisms for scheduling games with proportional deterioration ⋮ The power of one evil secret agent ⋮ The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler ⋮ Local and global price of anarchy of graphical games ⋮ Capacitated network design games ⋮ Congestion games with capacitated resources ⋮ Strategic multiway cut and multicut games ⋮ Bayesian generalized network design ⋮ On the performance of approximate equilibria in congestion games ⋮ Topological implications of selfish neighbor selection in unstructured peer-to-peer networks ⋮ Pairwise cooperations in selfish ring routing for minimax linear latency ⋮ Repeated congestion games with bounded rationality ⋮ A network pricing game for selfish traffic ⋮ Congestion games with failures ⋮ A note on the efficiency of position mechanisms with budget constraints ⋮ Tight bounds for selfish and greedy load balancing ⋮ Designing fast converging cost sharing methods for multicast transmissions ⋮ Performance of one-round walks in linear congestion games ⋮ Characterizing the existence of potential functions in weighted congestion games ⋮ Price of stability in survivable network design ⋮ The ring design game with fair cost allocation ⋮ Improving the \(H_k\)-bound on the price of stability in undirected Shapley network design games ⋮ Good neighbors are hard to find: Computational complexity of network formation ⋮ Designing cost-sharing methods for Bayesian games ⋮ Minimizing Rosenthal potential in multicast games ⋮ Selfish vector packing ⋮ Strong equilibrium in network congestion games: increasing versus decreasing costs ⋮ Cost sharing mechanisms for fair pricing of resource usage ⋮ Profit sharing with thresholds and non-monotone player utilities ⋮ On the efficiency of the proportional allocation mechanism for divisible resources ⋮ Tighter bounds on the inefficiency ratio of stable equilibria in load balancing games ⋮ Improved bounds on equilibria solutions in the network design game ⋮ The efficiency of fair division ⋮ The impact of social ignorance on weighted congestion games ⋮ Non-cooperative facility location and covering games ⋮ Selfish bin packing ⋮ Simple combinatorial auctions with budget constraints ⋮ Incentive-based search for equilibria in Boolean games ⋮ Competitive cost sharing with economies of scale ⋮ Surrogate optimization for \(p\)-norms ⋮ Connectivity and equilibrium in random games ⋮ Mean-field game approach to admission control of an \(M/M/\infty \) queue with shared service cost ⋮ The price of atomic selfish ring routing ⋮ The cost of selfishness for maximizing the minimum load on uniformly related machines ⋮ Bayesian ignorance ⋮ Inefficiency of equilibria for the machine covering game on uniform machines ⋮ Non-cooperative cost sharing games via subsidies ⋮ Congestion games with linearly independent paths: convergence time and price of anarchy ⋮ Exact and approximate equilibria for optimal group network formation ⋮ Strategic network formation through peering and service agreements ⋮ An \(O(\frac{\log n}{\log \log n})\) upper bound on the price of stability for undirected Shapley network design games ⋮ A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games ⋮ Equilibrium strategies for multiple interdictors on a common network ⋮ Network design with weighted players ⋮ The path player game ⋮ Strong price of anarchy ⋮ Price of Pareto optimality in hedonic games ⋮ Pure Nash equilibria in player-specific and weighted congestion games ⋮ Non-cooperative queueing games on a network of single server queues ⋮ Non-cooperative tree creation ⋮ Schelling games on graphs ⋮ Bounding the inefficiency of compromise in opinion formation ⋮ The Pareto frontier of inefficiency in mechanism design ⋮ On the Price of Anarchy of cost-sharing in real-time scheduling systems ⋮ Mechanism design for set cover games with selfish element agents ⋮ FIFO and randomized competitive packet routing games ⋮ On Pareto optimality in social distance games ⋮ A unifying approximate potential for weighted congestion games ⋮ Non-blind strategies in timed network congestion games ⋮ Timed network games ⋮ The effect of false positives: Why fuzzy message detection leads to fuzzy privacy guarantees? ⋮ Tight bounds for the price of anarchy and stability in sequential transportation games ⋮ Coordination mechanisms for scheduling games with machine modification ⋮ Mixed coordination mechanisms for scheduling games on hierarchical machines ⋮ Price of anarchy for parallel link networks with generalized mean objective ⋮ Social distancing network creation ⋮ Cost-sharing games with rank-based utilities ⋮ Decentralized update selection with semi-strategic experts ⋮ The price of anarchy in series-parallel network congestion games ⋮ Geometric Network Creation Games ⋮ Scheduling games with rank-based utilities ⋮ Using Temporal Dummy Players in Cost-Sharing Games ⋮ Not all strangers are the same: the impact of tolerance in Schelling games ⋮ Scheduling games with machine-dependent priority lists ⋮ Congestion games with priority-based scheduling ⋮ Generalized graph \(k\)-coloring games ⋮ On the Existence of Pure Nash Equilibria in Weighted Congestion Games ⋮ Modified Schelling games ⋮ Non-cooperative Cost Sharing Games Via Subsidies ⋮ Cost-sharing games in real-time scheduling systems ⋮ Cost-sharing games in real-time scheduling systems ⋮ “Beat-Your-Rival” Routing Games ⋮ Network sharing by two mobile operators: beyond competition, cooperation ⋮ The Buck-Passing Game ⋮ Equilibria in Multiclass and Multidimensional Atomic Congestion Games ⋮ Pure Nash equilibria in restricted budget games
