IJCAI'19 Tutorial: Mechanism Design Powered by Social Interactions

Dengji Zhao

ShanghaiTech Universiy, China

This tutorial introduces a novel mechanism design theory for information propagation on a social network such that truthful information will be fully propagated and collected via the network. The goal is to design resource or task allocation mechanisms such that existing participants are incentivized to invite more participants via their (private) social interactions, which is fundamentally different from and achieves better outcomes than traditional prepaid-promotions via search engines or social media.

Abstract

Designing mechanisms utilizing social interactions has not been well-established yet and has many interesting open problems in both theory and practice, which also underpins the development of the global digital economy. This tutorial will discuss how to design such incentives to utilize social interactions and analyze the key challenges and existing novel solutions.

The literature of mechanism design has traditionally assumed that the set of participants are fixed and are known to the mechanism (i.e. the market owner) in advance. However, in practice, the market owner can only directly reach a small number of participants (her neighbors). In order to get more participants, the market owner often needs costly promotions via, e.g., Google, Facebook or Twitter, but the impact of these promotions is often unpredictable. Specifically, the extra revenue that the owner gets from the promotions may not even cover the costs of the promotions.

To solve this dilemma, we build promotions inside the market mechanism without using any third-party advertising platform. The promotion guarantees that the market owner will never lose and does not need to pay if the promotion is not beneficial to her. This is achieved by incentivizing people who are aware of the market to propagate the information to their neighbors further, and their neighbors would do the same (social interactions). They will be rewarded only if their diffusion effort is beneficial to the market owner, so the promotion is cost-free to some extent.

Outline

  1. Mechanism Design Overview
    1. Vickrey-Clarke-Groves mechanism
    2. Sponsored search auctions
  2. Existing Models Powered by Social Interactions
    1. DARPA Network Challenge
    2. Collective buying
  3. Mechanism Design Powered by Social Interactions
    1. The model
    2. The new definition of incentives
    3. The failure of traditional mechanisms (VCG)
    4. The new challenges
  4. Diffusion Mechanisms for Resource Allocation
    1. Mechanism for promoting single item
    2. Mechanism for promoting multiple items
    3. When diffusion is costly
  5. Diffusion Mechanisms for Collaborative Task Allocation
    1. The difference from resource allocation
    2. How to share the rewards (existing solutions failed)
  6. The Generalization and Applications
    1. More than revenue maximization
    2. False-name manipulation also plays a role
    3. The dynamics and privacy of the networks
    4. Extension to Social Choice (mechanisms without payment)

Target Audience

The potential target audience are PhD students and researchers who are interested in Algorithmic Game Theory, Mechanism Design/Auctions, Social Choice, Information Propagation on Social Networks. There is no strict requirement for attending the tutorial. Previous knowledge of game theory and mechanism design will be an advantage, but the basic definitions will be covered during the tutorial.

The research direction is new and has not been well explored yet, and our novel solutions have attracted the community. We believe the challenge itself is very interesting to many AI researchers, especially those who work on algorithmic game theory and social network related topics. It plays an essential role for the next generation of sale/task promotions, and it challenges existing advertising models (like sponsored search auctions) and makes the promotions decentralised.

Slides (coming soon)

Presenter Bio

Dengji Zhao is a Tenure-track Assistant Professor at ShanghaiTech University, China since 2017. He received double Ph.D. (2012) degrees in Computer Science from University of Western Sydney and University of Toulouse, and received double M.Sc. (2009) degrees in Computational Logic from Technische Universität Dresden and Universidad Politécnica de Madrid. Before joining ShanghaiTech, he was a postdoc (2013-2014) working with Prof. Makoto Yokoo and a research fellow (2014-2016) working with Prof. Nick Jennings. Most of Zhao's research is on artificial intelligence (especially multi-agent systems) and algorithmic game theory (especially mechanism design and its applications in the sharing economy).

References/Readings

  1. Dengji Zhao, Bin Li, Junping Xu, Dong Hao, Nick Jennings: Selling Multiple Items via Social Networks. (Reviews, Presentation, Poster) In the Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-18)
  2. Bin Li, Dong Hao, Dengji Zhao, Tao Zhou: Customer Sharing in Economic Networks with Costs. (Reviews, Presentation, Poster) In the Proceedings of the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence (IJCAI-ECAI-18)
  3. Bin Li, Dong Hao, Dengji Zhao, Tao Zhou: Mechanism Design in Social Networks. (Reviews, Presentation) In the Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)
  4. Umberto Grandi: Social Choice on Social Networks. In U. Endriss (editor), Trends in Computational Social Choice, pp. 169-184, AI Access, 2017.
  5. updating...