Submodular Welfare under Routing Coupling: A Hierarchical Decomposition with Perturbation Guarantees

This paper studies joint submodular welfare maximization and routing over graphs, where agents select items under diminishing returns and transport them through a network with congestion-dependent costs. Although welfare maximization admits matroid-based approximations and routing reduces to shortes