报告题目：Fashion game and utilities of graphs

报告人：林文松教授，东南大学

报告时间：2023年5月19日10:30-11:30

报告地点：21-410

报告摘要：

We propose and study an optimization problem of the fashion game on graphs. There are two kinds of players in a graph G: Conformists and Rebels. All players choose their actions from an identical set of the two symmetric actions {0, 1}. An action profile π of G is a mapping from the vertex set of G to the action set {0, 1}. A conformist (resp. rebel) likes people having the same (resp. different) action with her and dislikes people having the different (resp. same) action. The utility u(v, π) of a player v under the action profile π is the number of neighbors she likes minus the number of neighbors she dislikes. The utility u(G, π) of G under π is the minimum utility among all players. Let t be an integer. A graph G is said to be t-satisfiable if there is an action profile of G such that all players have utilities at least t. The utility of G, denoted by u(G), is the maximum t such that G is t-satisfiable.In this talk, we shall discuss some results on utilities of graphs, including the utilities of some special classes of graphs, computational complexity of the problem to decide if a graph is t-satisfiable and the algorithms for determining utilities of some special graphs.

This talk is based on joint works with Chenli Shen and Qi Wang.

邀请人：朱绪鼎