Path Lotteries and Bandit Edge Pricing: Coalition-Aware Markets on Integral Networks

Amin et al. (2023) show elegant equilibrium existence and polynomial-time computation under conditions linking preferences and network structure, but when conditions fail you may need path-based, differentiated prices and equilibria can be elusive. We propose adding two ingredients: (i) path lotteries that convexify integral constraints by randomizing across routes at the coalition level, and (ii) bandit-driven edge price updates that learn the minimal price vector supporting stable coalitions and near-VCG utilities under uncertainty. This synthesizes combinatorial auction insights with online learning used in task offloading markets (Wu & Liao, 2025) and repeated double auctions among boundedly rational agents (Zhao et al., 2021). The novelty is to treat non-convex, integral flow constraints as a design problem—use randomized allocations to regain existence and a learning layer to discover prices that support them. We also probe a counterintuitive question inspired by Balseiro et al.: can reserve-like edge price floors increase welfare by stabilizing coalitions and deterring congestion-inducing low-value participation? If successful, this offers a unifying template for networked capacity-sharing (transport, data networks, energy routing) where classic equilibrium arguments struggle.

References:

1. Robust Auction Design in the Auto-bidding World. S. Balseiro, Yuan Deng, Jieming Mao, V. Mirrokni, Song Zuo (2021). Neural Information Processing Systems.
2. Market Design for Task Offloading under Information Asymmetry and System Uncertainty. Yifei Wu, Guocheng Liao (2025). 2025 International Conference on Sensor-Cloud and Edge Computing System (SCECS).
3. Market Design for Capacity Sharing in Networks. Saurabh Amin, Patrick Jaillet, Haripriya Pulyassary, Manxi Wu (2023).
4. Auction Design through Multi-Agent Learning in Peer-to-Peer Energy Trading. Zibo Zhao, Chengzhi Feng, Andrew L. Lu (2021). arXiv.org.