Arbitrage-free Pricing in User-based Markets

Users have various attributes, and in user-based markets there are buyers who wish to buy a target set of users with specific sets of attributes. The problem we address is that, given a set of demand from the buyers, how to allocate users to buyers, and how to price the transactions. This problem arises in online advertising, and is particularly relevant in advertising in social platforms like Facebook, LinkedIn and others where users are represented with many attributes, and advertisers are buyers with specific targets. This problem also arises more generally in selling data about online users, in a variety of data markets. We introduce \em arbitrage-free pricing, that is, pricing that prevents buyers from acquiring a lower unit price for their true target by strategically choosing substitute targets and combining them suitably. We show that \em uniform pricing -- pricing where all the targets have identical price -- can be computed in polynomial time, and while this is arbitrage-free, it is also a logarithmic approximation to the maximum revenue arbitrage-free pricing solution. We also design a different arbitrage-free non-uniform pricing -- pricing where different targets have different prices -- solution which has the same guarantee as the arbitrage-free uniform pricing but is empirically more effective as we show through experiments. We also study more general versions of this problem and present hardness and approximation results.