# Price Competition, Fluctuations, and Welfare Guarantees

ACM Conference on Economics and Computation (ACM-EC 2015) |

We first study best response dynamics in markets with sellers that provide a homogeneous good, and show that except for a modest number of initial rounds, the welfare is guaranteed to be high. We consider two variations: in the first the sellers have full information about the buyer’s valuation. Here we show that if there are $n$ items available across all sellers and $n_{\max}$ is the maximum number of items controlled by any given seller, then the ratio of the optimal welfare to the achieved welfare will be at most $\log\left(\frac{n}{n-n_{\max} + 1}\right)+1$. As the market power of the largest seller diminishes, the welfare becomes closer to optimal. In the second variation we consider an extended model in which sellers have uncertainty about the buyer’s valuation. Here we similarly show that the welfare improves as the market power of the larger seller decreases, yet with a worse ratio of $\frac{n}{n-n_{\max} + 1}$. Our welfare bounds in both cases are essentially tight. The exponential gap in welfare between the two variations quantifies the value of accurately learning the buyer’s valuation in such settings.
Finally, we show that extending our results to heterogeneous goods in general is not possible. Even for the simple class of $k$-additive valuations, there exists a setting where the welfare approximates the optimal welfare within any non-zero factor only for $O(1/s)$ fraction of the time, where $s$ is the number of sellers.