1. Walrasian Dynamics in Multi-unit Markets
- Author
-
Simina Brânzei and Aris Filos-Ratsikas
- Subjects
FOS: Computer and information sciences ,TheoryofComputation_MISCELLANEOUS ,Computer Science::Computer Science and Game Theory ,General equilibrium theory ,Computer science ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Set (abstract data type) ,symbols.namesake ,Computer Science - Computer Science and Game Theory ,0202 electrical engineering, electronic engineering, information engineering ,Revenue ,Conjecture ,TheoryofComputation_GENERAL ,General Medicine ,Computer Science::Computers and Society ,Computer Science::Multiagent Systems ,ml-ai ,010201 computation theory & mathematics ,Nash equilibrium ,Best response ,symbols ,020201 artificial intelligence & image processing ,Mathematical economics ,Computer Science and Game Theory (cs.GT) - Abstract
In a multi-unit market, a seller brings multiple units of a good and tries to sell them to a set of buyers that have monetary endowments. While a Walrasian equilibrium does not always exist in this model, natural relaxations of the concept that retain its desirable fairness properties do exist. We study the dynamics of (Walrasian) envy-free pricing mechanisms in this environment, showing that for any such pricing mechanism, the best response dynamic starting from truth-telling converges to a pure Nash equilibrium with small loss in revenue and welfare. Moreover, we generalize these bounds to capture all the (reasonable) Nash equilibria for a large class of (monotone) pricing mechanisms. We also identify a natural mechanism, which selects the minimum Walrasian envy-free price, in which for n=2 buyers the best response dynamic converges from any starting profile. We conjecture convergence of the mechanism for any number of buyers and provide simulation results to support our conjecture.