Limited Supply Available! Finding the Competition Complexity for a Mixture of Supply Limiting Mechanisms in Bayesian Mechanism Design

Abstract

Competition complexity quantifies the number of additional bidders a suboptimal auction needs in order to achieve an expected revenue that exceeds the expected revenue of the optimal auction. The core intuition is that increased competition drives up payments, which in turn increases revenue. Competition complexity is well explored for VCG auctions; however, Supply Limiting Mechanisms (SLM), a relatively recent auction design, have not been analyzed from this perspective. We introduce closed-form expressions for the expected optimal revenue OPT(c, k, n) and the expected supply-limiting mechanism revenue SLM(s, k, n). We show that a single SLM with a fixed supply limit cannot dominate OPT for all market conditions, which motivates reformulating the problem as a mixture of SLMs with different supply limits. This reformulation raises two key questions: how many additional bidders are needed, and how should the mixture weights (λ_s) be chosen? We establish lower and upper bounds on n(c), the minimum number of total bidders required, via two baseline methods: a linear program and a uniform weighting scheme. The main contribution of this thesis is the greedy algorithm: a recursive procedure that constructs weights λ_1, ... , λ_{n-1} by satisfying the revenue constraints MIX(k) = OPT(c, k) exactly for k = 1, ... , n-1, exploiting the lower-triangular structure of the constraint system. We prove that the greedy mixture satisfies MIX(k) >= OPT(c, k) for all k >= n as well, provided the weights satisfy E[s] >= c, a necessary and sufficient condition that we establish rigorously. We further prove that the greedy weights are monotonically non-decreasing, λ_1 <= λ_2 <= ... <= λ_{n-1}, at n = 2c + 1 via an inductive argument that reduces to a lambda-free algebraic inequality in c, t, and n. One part of the proof remains open: a closed-form algebraic verification of this lambda-free inequality for all c, though it has been confirmed numerically for c = 1, ... , 18.