JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]


Journal of Information Science and Engineering, Vol. 40 No. 2, pp. 217-230


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


PO-AN CHEN+, YI-LE CHEN AND WEI LO
Institute of Information Management
National Yang Ming Chiao Tung University
Hsinchu City, 300 Taiwan
E-mail: poanchen@nycu.edu.tw; {jairachen78; lo.nuwa}@gmail.com


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.


Keywords: opinion optimization, Stackelberg strategies, combinatorial algorithms, linear program rounding, randomized algorithms

  Retrieve PDF document (JISE_202402_01.pdf)