Regret Bounds for Competitive Resource Allocation with Endogenous Costs

This paper studies how to allocate resources among multiple interacting modules when costs depend on the full allocation (not just individual choices). The researchers compare three strategies: ignoring costs (very inefficient), estimating costs (moderately efficient), and using competitive allocation with feedback (most efficient), showing that the competitive approach achieves dramatically better performance by exploiting information revealed through interactions. They also show that the structure of how modules interact—whether fully connected or sparse like a ring—creates a trade-off between computation cost and decision quality.