Opinion Optimization for Two Different Social Objectives: Combinatorial Algorithms and Linear Program Rounding

In this paper, we aim to optimize the two different social objectives of opinion optimization at equilibrium by controlling some individuals. This is usually called “Stackelberg games”, in which a centralized authority is allowed to assign the strategies to a subset of individuals. The Stackelberg strategies of the centralized authority are the algorithms to select a subset of individuals and decide the actions for them in order to palliate the cost caused by the selfish behavior of the uncontrolled individuals. We give some combinatoral algorithms and linear program rounding algorithms as Stackelberg strategies for approximately optimizing the objective of utilitarian social cost (on special cases) and the objective of total expressed opinion (on general directed graphs), respectively.