Arbitrage-free pricing in user-based markets

Chaolun Xia, S. Muthukrishnan

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

Abstract

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)
Pages327-335
Number of pages9
ISBN (Print)9781510868083
StatePublished - Jan 1 2018
Externally publishedYes
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
Volume1
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018
CountrySweden
CityStockholm
Period7/10/187/15/18

Keywords

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

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

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

  • Cite this

    Xia, C., & Muthukrishnan, S. (2018). Arbitrage-free pricing in user-based markets. In 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018 (pp. 327-335). (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS; Vol. 1). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).