1 of 33

Economic Views of�Large-Scale Online Behaviors

　Yun Kuen Cheung * Lexing Xie　　　�

Australian National University

2 of 33

Past AFOSR Projects

  • Next project pending :-)

​

  • Lexing Xie, Yu-Ru Lin. FA2386-20-1-4064, Linking Online Engagement to Pandemic Responses, 2020-2022
  • Lexing Xie. FA2386-19-1-4078, Linking Online Attention to Measurable actions, 2019-2021
  • Lexing Xie, Manuel Cebrian, Pascal Van Hentenryck. FA2386-15-1-4018, The Anatomy of Social Media Popularity, 2015-2018
  • Lexing Xie. FA2386-12-1-4041, The Role of Content and Context in Social Media Epidemics, 2012-2013

3 of 33

Past AFOSR Project:

  1. Measurements
  2. Stochastic Processes of Machine Learning

Yang, Xie, Wu. The Shapes of the Fourth Estate During the Pandemic: Profiling COVID-19 News Consumption in Eight Countries. CSCW 2023

4 of 33

Economics:

Effective Allocation

of Scarce Resources

5 of 33

Current Project: Explain Measurements in Online Economies

  • Economic perspective offers a more complete explanation:�
    • Agents – humans and platforms – with different preferences.�
    • Agents’ own preferences affect their transactions.�
    • Platform makes influence via ads, recommender systems, etc.

6 of 33

Current Project: Explain Measurements in Online Economies

  • Economic perspective offers a more complete explanation:�
    • Billions of daily transactions.�
    • Algorithms/AI are necessary.�
    • Rapid changes → volatile economic structure.�
    • Economics studies how transactions collectively affect fairness, diversity, efficiency and stability.

7 of 33

Rest of This Talk

  • Case Study 1: Trial-Offer Market of Cultural Goods [Optimisation]�
    • equilibrium optimizes a natural objective mixing efficiency and diversity�
    • agent interactions are mirror descent, thus reaching equilibrium�
  • Case Study 2: Learning in Game [Dynamical Systems]�
    • even one of the simplest learning-in-game systems can be chaotic �
  • For each case: Summary and Future Research

8 of 33

Trial-Offer Market of Cultural Goods

9 of 33

Trial-offer Market with Personalisation

[Salganik et al. 2006, Krumme et al. 2012, Maldonado et al. 2018]

RecSys makes suggestions�according to market shares of the songs.

Pick songs according to their own preferences, and suggestions�from recommender system (RecSys).

10 of 33

Trial-offer Market with Personalisation

[Salganik et al. 2006, Krumme et al. 2012, Maldonado et al. 2018]

Trial-Offer Market Equilibrium:

A market share which stays stochastically stable.

11 of 33

Trial-offer Market with Personalisation

[Salganik et al. 2006, Krumme et al. 2012, Maldonado et al. 2018]

Trial-Offer Market Equilibrium:

A market share which stays stochastically stable.

​

Two immediate questions: [Zhu, C., Xie; WWW 2023]�

  • Does market equilibrium exist?
    • Yes!
    • It is unique under some natural assumptions.

12 of 33

Trial-offer Market with Personalisation

[Salganik et al. 2006, Krumme et al. 2012, Maldonado et al. 2018]

Trial-Offer Market Equilibrium:

A market share which stays stochastically stable.

​

Two immediate questions: [Zhu, C., Xie; WWW 2023]�

  • Does market equilibrium exist?
    • Yes!
    • It is unique under some natural assumptions.�
  • Does the user-RecSys interaction find the equilibrium?
    • Yes!
    • The interaction is same as stochastic mirror ascent algorithm on a naturally motivated objective.

13 of 33

Stochastic Mirror Ascent Algorithm

Market equilibrium = maximum of objective

Stability is a natural consequence.

14 of 33

Market equilibrium is optimiser [Zhu, C., Xie; WWW 2023]

Log Utility Regularised by Entropy Maximisation

​

Φj is market share of the j-th song

​

​

​

​

maximise

​

​

​

subject to

Shannon entropy:

a diversity measure

an efficiency measure

15 of 33

Zero-sum game

​

Army: type of vehicle and pathway

Zombie: pathway (combination of pathways if there are many zombies)

For each choice of army and zombie, lose = probability of the outcome

16 of 33

Economies and Optimisation

  • Insight: Economies carry out implicit optimisation
    • Adam Smith [1776]
      • “invisible hand” metaphor
      • agents trade according to their self-interests in free market
      • the trades produce widespread benefits unintentionally
    • Kenneth Arrow and many others [1951 and before]:
      • First Welfare Theorem of Economics – �market equilibrium achieves Pareto optimality

17 of 33

Economies and Optimisation

  • Insight: Economies carry out implicit optimisation
    • Eisenberg-Gale [1959, 1961]
      • Market equilibrium of homogeneous Fisher market optimises Nash social welfare
    • Kelly-Maulloo-Tan [1997], Kelly-Vazirani [2003]
      • Stable point of network control = market equilibrium�of Eisenberg-Gale, achieves proportional fairness
    • Nisan-Segal [2006]
      • Auction’s Walrasian equilibrium, if exists,�= optimal of a “config linear program”

18 of 33

Project Target 1: Economies and Optimisation

1. Understand economic systems via optimisation insight�

    • What are economies optimising?� (e.g. a mixture of fairness, diversity and efficiency)�
    • Market interactions are gradient/mirror descent:
      • Birnbaum, Devanur, Xiao [ACM EC 2011]
      • C., Cole, Devanur [STOC 2013]
      • C., Cole, Tao [ACM EC 2018]
      • C., Leonardos, Piliouras [IJCAI 2021]

19 of 33

Project Target 1: Economies and Optimisation

2. Measuring and Improving Recommender Systems

Entropy of the market share

Efficiency = # success purchase / # trials

Ranking strategies:

​

  • Quality ranking
  • Popularity ranking
  • Random ranking

​

20 of 33

Project Target 1: Economies and Optimisation

3. Fairness of Economies – Optimisation with social norm constraints�

    • Broad range of social norms → wide spectrum of fairness�(e.g. alpha fairness [Lan et al.; INFOCOM 2010])�
    • Trade-offs among fairness concepts�[Kleinberg et al.; ITCS 2017]�
    • Algorithmic reparation [Davis et al.; Big Data & Society 2021]

21 of 33

Project Target 1: Economies and Optimisation

3. Fairness of Economies – Optimisation with social norm constraints�

    • Social norms impose constraints for optimisation:
      • The diversity should be at least …
      • The incomes of Uber drivers with similar profile should not differ by more than …�
    • How do constraints affect the optimal objective and measures of efficiency, diversity and stability?

22 of 33

Chaos in Economic Systems

23 of 33

Instability of Economic Systems

  • While some economic systems can reach equilibrium, other systems can be unstable and unpredictable.�
  • A complete picture of internet economic systems require approaches more than optimisation.

24 of 33

Instability of Economic Systems

  • Dynamical Systems is the primary math area of studying unstable and unpredictable systems.�
  • A central concept is Lyapunov chaos, often referred as butterfly effect in pop culture:

​

A tiny change in the current state�can lead to vastly different outcome in the future.

25 of 33

MWU Learning in Two-Person Zero-Sum Games

  • Arguably one of the “simplest” learning-in-game systems:
    • Game-wise
      • Two-person zero-sum game is among the first class of games considered in game theory.
      • Nash equilibrium is easy to compute via linear programming.� [John von Neumann, Oskar Morgenstern, 1944]

26 of 33

MWU Learning in Two-Person Zero-Sum Games

  • Arguably one of the “simplest” learning-in-game systems:
    • Learning-wise
      • Multiplicative Weights Updates (MWU) is one of the first adaptive learning algorithms. [Arora, Hazan, Kale; ToC 2012]
      • For each possible action j (e.g. Rock, Paper, Scissors), compute the cumulative payoff wj in the past.
      • Then in the next time step, pick action j with probability

27 of 33

MWU Learning in Two-Person Zero-Sum Games

Theorem. [C., Piliouras COLT 2019]

In almost every two-person zero-sum game, if both persons adopt MWU algorithm to play the game, the system is Lyapunov chaotic�in the cumulative payoff space.

28 of 33

Project Target 2: Instability of Economies, and Intervention

  • Insight: Chaos – expansion of possibilities
    • Measuring possibilities mathematically: volume

29 of 33

Project Target 2: Instability of Economies, and Intervention

  • Insight: Volume analysis
    • Volume analysis is applicable to many combinations of�games and learning algorithms:
      • C., Piliouras [NeurIPS 2020]
      • C., Tao [ICLR 2021]
      • C., Piliouras, Tao [ICLR 2022]

30 of 33

Project Target 2: Instability of Economies, and Intervention

  • Interventions to avoid instability and chaos�
    • MWU is more stable in cooperative than competitive games.�Vice-versa for a slight variant of MWU.�
    • Adjust game structure via policy or design.�
    • Encourage/enforce use of proper algorithms.

31 of 33

Summary

32 of 33

  • Economic perspective offers a more complete explanation of how agents’ preferences influence internet economies.

​

  • Internet → New Economic Structures
    • Infinite supplies of digital goods
    • Attention is scarce, not digital goods [Simon 1971]
    • Ride-sharing: spatial & volatile demands and supplies

33 of 33

  • Trial-offer market with personalisation
    • Optimisation: computational approach to understand how internet economies may achieve fairness, efficiency, diversity and stability.�
  • MWU learning in two-person zero-sum games
    • Dynamical systems: useful math tools (e.g. volume) to understand instability and chaos of internet economics.