Arbitrage-free pricing in user-based markets

Chaolun Xia, S. Muthukrishnan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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, Linkedln 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 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 suita bly. We show that 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 des ign 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.

    Original languageEnglish (US)
    Title of host publication17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
    PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
    Number of pages9
    ISBN (Print)9781510868083
    StatePublished - 2018
    Event17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018 - Stockholm, Sweden
    Duration: Jul 10 2018Jul 15 2018

    Publication series

    NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
    ISSN (Print)1548-8403
    ISSN (Electronic)1558-2914


    Conference17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018


    • Advertising
    • Algorithm
    • Arbitrage
    • Arbitrage-free
    • Data
    • Market
    • Pricing
    • Revenue maximization
    • User attribute

    ASJC Scopus subject areas

    • Artificial Intelligence
    • Software
    • Control and Systems Engineering


    Dive into the research topics of 'Arbitrage-free pricing in user-based markets'. Together they form a unique fingerprint.

    Cite this