Double Auctions, and Generalizations of the No Trade Theorem

Abstract: Consider a seller who has a good which she (privately) values for v_s, and a buyer who (privately) values the good for v_b. If v_b > v_s, we would like them to trade the good for some price p, where p < v_b and p > v_s. The no trade mechanism states that no truthful individual rational mechanism can elicit v_s, v_b, decide on p and perform the trade. In 1992, McAfee showed how to circumvent this impossibility when there are multiple sellers and buyers, where each seller owns one unit of the good, and each buyer wants a single unit.
In our work, we study the case where sellers own multiple units of the good, and buyers want multiple units. We show a new mechanism for this case, and show that its performance tends to 1 for a large market. We then discuss what happens when there are multiple types of items, and present a truthful mechanism (albeit with worse approximation ratio) for the case where each seller holds a single type of items, but buyers can want items of multiple types. Finally, we show (mostly) impossibility results for the case where buyers and sellers hold items of different types.