Abstract:

In this paper, we study a conjecture of optimal pricing for two matroids, which arises from the problem of maximizing social welfare in combinatorial markets through pricing schemes. Given two matroids with a common ground set of items, there exists a disjoint partition of the ground set such that each subset is a base of one corresponding matroid (called ideal base-partition). The conjecture believes that there exists a price function on the items such that, if we pick any one of the cheapest bases of one matroid from the ground set, then the remaining items still constitute a base of the other matroid. By using perfect matchings on bipartite graphs, we prove that if the ground set admits at most two ideal base-partitions, then the conjecture is true and we can give the price vector efficiently.

Key words: matroid, pricing scheme, matroid bases, perfect matching