Duan‐Shin Lee

Duan-Shin Lee

In this paper we propose a Bayesian game to allocate resources. In this game, there are $c$ units of resources to be allocated to $n$ players. Agent $i$ has a demand of $V_i$ units of resources and takes action $X_i$ according to a strategy function $s_i$, \ie $X_i=s_i(V_i)$. Payoffs are setup such that player $i$ is contented with no more than $V_i$ units of resources. We assume that resources are granted to the players on a smallest-request-first and all-or-nothing basis. For this game with two players, we analyze the equilibrium strategy functions mathematically within the family of alternating identity-and-flat (AIF) functions. We show that Nash equilibrium profiles consist of two identity functions, two AIF functions with a common switch point, or two AIF functions with one and three switch points, respectively. For an $n$-player game with a large $n$ and a large $c_n$ of order $O(n)$, we present a mean-field first order approximation and a second-order Gaussian approximation for its equilibrium strategy function. The first-order analysis obtains an equilibrium AIF function with one switch point. In Gaussian analysis of large games, we propose a construction algorithm. This construction algorithm begins in searching within the family of AIF functions. If a gradient conflict condition occurs, the game enters a chattering regime, in which players play a continuous, strictly increasing strategy function that is not an identity nor a flat function. Conceptually one can view the chattering regime as if players alternate between a slope-one strategy and a flat strategy infinitely fast in order to sustain a high payoff. We prove that the construction algorithm always obtains a Nash equilibrium and terminates in a finite number of steps. We present several numerical examples for the two player game as well as the Gaussian model.

Duan-Shin Lee, Yu-Hsiu Hung

In this paper we study team-symmetric games with $m\ge 2$ teams. Players within a team have symmetric identity and have a common payoff function. We show that team-symmetric games always have a team-symmetric Nash equilibrium. We develop and solve a linear complementarity problem of team-symmetric Nash equilibria. We propose an actor-critic based multi-agent reinforcement learning algorithm for team-symmetric games. Through simulations, we show that this multi-agent reinforcement learning algorithm performs much better than many existing algorithms.

Cheng-Shang Chang, Chia-Tai Chang, Duan-Shin Lee et al.

In this paper, we first propose a new iterative algorithm, called the K-sets+ algorithm for clustering data points in a semi-metric space, where the distance measure does not necessarily satisfy the triangular inequality. We show that the K-sets+ algorithm converges in a finite number of iterations and it retains the same performance guarantee as the K-sets algorithm for clustering data points in a metric space. We then extend the applicability of the K-sets+ algorithm from data points in a semi-metric space to data points that only have a symmetric similarity measure. Such an extension leads to great reduction of computational complexity. In particular, for an n * n similarity matrix with m nonzero elements in the matrix, the computational complexity of the K-sets+ algorithm is O((Kn + m)I), where I is the number of iterations. The memory complexity to achieve that computational complexity is O(Kn + m). As such, both the computational complexity and the memory complexity are linear in n when the n * n similarity matrix is sparse, i.e., m = O(n). We also conduct various experiments to show the effectiveness of the K-sets+ algorithm by using a synthetic dataset from the stochastic block model and a real network from the WonderNetwork website.