Hardness results for multicast cost sharing.

DOI10.1016/S0304-3975(03)00085-9zbMath1045.68163OpenAlexW1966991436MaRDI QIDQ1401398

Joan Feigenbaum, Rahul Sami, Arvind Krishnamurthy, Scott J. Shenker

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00085-9

zbMATH Keywords

MulticastCommunication complexityAlgorithmic mechanism design

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Randomized algorithms (68W20)

Related Items

Approximation and collusion in multicast cost sharing, Beyond Moulin mechanisms, The communication cost of selfishness, When ignorance helps: graphical multicast cost sharing games, On the convergence of multicast games in directed networks, Sharing the cost of multicast transmissions in wireless networks, Cost sharing and strategyproof mechanisms for set cover games, A BGP-based mechanism for lowest-cost routing, Designing fast converging cost sharing methods for multicast transmissions, The Price of Nash Equilibria in Multicast Transmissions Games, Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems, New efficiency results for makespan cost sharing, Revenue monotonicity in deterministic, dominant-strategy combinatorial auctions, The communication requirements of efficient allocations and supporting prices, Is Shapley Cost Sharing Optimal?, Cost sharing over combinatorial domains : Complement-free cost functions and beyond, Fair cost-sharing methods for scheduling jobs on parallel machines, Mechanism design for set cover games with selfish element agents

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed games
• Approximation and collusion in multicast cost sharing
• Incremental cost sharing: Characterization by coalition strategy-proofness
• A crash course in implementation theory
• A Concept of Egalitarianism Under Participation Constraints
• Competitive generalized auctions
• Communication Complexity
• Applications of approximation algorithms to cooperative games
• Algorithmic mechanism design
• Sharing the cost of multicast transmissions
• Strategyproof sharing of submodular costs: budget balance versus efficiency