Price Competition in Online Combinatorial Markets
Venue
Proceedings of the 23st World Wide Web Conference 2014
Publication Year
2014
Authors
Moshe Babaioff, Renato Paes Leme, Noam Nisan
BibTeX
Abstract
We consider a single buyer with a combinatorial preference that would like to
purchase related products and services from different vendors, where each vendor
supplies exactly one product. We study the general case where subsets of products
can be substitutes as well as complementary and analyze the game that is induced on
the vendors, where a vendor's strategy is the price that he asks for his product.
This model generalizes both Bertrand competition (where vendors are perfect
substitutes) and Nash bargaining (where they are perfect complements), and captures
a wide variety of scenarios that can appear in complex crowd sourcing or in
automatic pricing of related products. We study the equilibria of such games and
show that a pure efficient equilibrium always exists. In the case of submodular
buyer preferences we fully characterize the set of pure Nash equilibria,
essentially showing uniqueness. For the even more restricted "substitutes" buyer
preferences we also prove uniqueness over {\em mixed} equilibria. Finally we begin
the exploration of natural generalizations of our setting such as when services
have costs, when there are multiple buyers or uncertainty about the the buyer's
valuation, and when a single vendor supplies multiple products.
