Optimal Nash Equilibria for Bandwidth Allocation
share
In bandwidth allocation, competing agents wish to transmit data along paths of links in a network, and each agent's utility is equal to the minimum bandwidth she receives among all links in her desired path. Recent market mechanisms for this problem have either focused on only Nash welfare branzei_nash_2017, or ignored strategic behavior goel_beyond_2018. We propose a nonlinear variant of the classic trading post mechanism, and show that for almost the entire family of CES welfare functions (which includes maxmin welfare, Nash welfare, and utilitarian welfare), every Nash equilibrium of our mechanism is optimal. Next, we prove that fully strategyproof mechanisms for this problem are impossible in general, with the exception of maxmin welfare. Finally, we show how some of our results can be directly imported to the setting of public decision-making via a reduction due to garg_markets_2018.
READ FULL TEXT