Short abstract

This tutorial provides an overview of recent approaches put forward in the computational social choice and mechanism design literature to take into consideration the social network component of a variety of decision problems.

The tutorial is divided into two parts. The first part is on social choice and social networks: after giving a brief introduction of the classical setting of social choice theory and basic techniques in social network analysis, we will present recent work analysing the effects of social network phenomena to classical collective decision methods and move further to work designing mechanisms that take into consideration the network structure underlying a social choice problem. Finally, we will end with a detailed overview of recent work in opinion diffusion, when opinions represents preferences or binary views, and researchers investigate the termination of the process, its resistance to manipulative actions, and conditions to reach consensus.

The second part of the tutorial will be focused on mechanism design for information sharing on a social network such that truthful information will be fully propagated in the network. 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 neighbours). In order to get more participants, we incentivize participates who are already in the market to invite their neighbours to join the market, which is not achievable with traditional mechanism design. This novel design approach can be applied to auctions, crowdsourcing and general task allocation problems to receive better outcomes.

Slides

part1; part2

Outline (preliminary)

1. Social Choice and Social Networks (Umberto)
   • Effects of social networks on collective choice (noisy votes, iterative voting, voting equilibria)
   • Social choice on networks (liquid democracy, ratings and recommendation, poll manipulation)
   • Opinion diffusion (binary views, preferences, and beliefs)
   
   
2. Mechanism Design on Social Networks (Dengji)
   • Promotions via Social Networks
   • Mechanism Design Overview
   • Mechanism Design on Social Networks (the model, the new definition of incentives, the failure of traditional mechanisms, the new challenges)
   • Truthful Diffusion Mechanisms (mechanisms for auctions and crowdsourcing, when diffusion is costly, when privacy/computation is an issue)
   • The Generalization to Combinatorial Settings (the challenges, more than revenue maximization, false-name manipulation...)

Target Audience

The tutorial is addressed to:

• Researchers in computational social choice and algorithmic game theory who are interested in applying techniques from social network analysis to their favourite collective choice problem.
• Researchers in agent-based simulations and information propagation in social networks looking for open problems and novel settings to test their techniques.
• Young researchers and PhD students in multiagent systems interested in getting a survey of a novel area of research in their field.

There is no strict requirement for attending the tutorial, except for a good mastery of mathematical proofs, formal modelling, and computational complexity. Previous knowledge of social choice theory, game theory, and mechanism design will of course be an advantage, but the basic definitions will be given during the tutorial.

Presenters Bio

Umberto Grandi is an Assistant Professor at IRIT and University of Toulouse 1 Capitole since 2014, working since then on the interplay between collective decisions and social networks, as witnessed by the recent award of a national ANR young researcher project on social choice and social networks. He received his PhD from the University of Amsterdam in 2012. Since 2017 he is director and co-founder of an international master (Master MIAGE on innovative information systems). Umberto is strongly committed to teaching and outreach activities, with two laboratories on voting and artificial intelligence organised at the European Researchers Night in 2014 and 2018, and an outreach video on social algorithms produced in 2016.

Dengji Zhao is an 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. Umberto Grandi, Social Choice on Social Networks. In U. Endriss (editor), Trends in Computational Social Choice, pp. 169-184, AI Access, 2017.
2. 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)
3. 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)
4. 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)
5. updating...