Streaming systems that can maintain Quality of Experience (QoE) for users have attracted much attention because they can be applied in various fields, such as emergency response training and medical surgery. Dynamic Adaptive Streaming over HTTP (DASH) is a typical protocol for streaming system. In order to improve QoE in DASH, a multi-server system has been presented by pseudo-increasing bandwidth through multiple servers. This multi-server system is designed to share streaming content efficiently in addition to having redundant server resources for each streaming content, which is excellent for fault tolerance. Assigning DASH server to users in these multi-servers environment is important to maintain QoE, thus a method of server assignment of users (user allocation method) for multi-servers is presented by using cooperative game theory. However, this conventional user allocation method does not take into account the size of the server bandwidth, thus users are concentrated on a particular server at the start of playback. Although the average required bit rate of video usually fluctuates, bit rate fluctuations are not taken into account. These phenomena may decrease QoE. In this paper, we propose a novel user allocation method using coalition structure generation in cooperative game theory to improve the QoE of all users in an immediate and stable manner in DASH environment. Our proposed method can avoid user concentration, since the bandwidth used by the overall system is taken into account. Moreover, our proposed method can be performed every time the average required bit rate changes. We demonstrate the effectiveness of our method through simulations using Network Simulator 3 (NS3).

With the high development of computation requirements in Internet of Things, resource-limited edge servers usually require to cooperate to perform the tasks. Most related studies usually assume a static cooperation approach which might not suit the dynamic environment of edge computing. In this paper, we consider a dynamic cooperation approach by guiding edge servers to form coalitions dynamically. It raises two issues: 1) how to guide them to optimally form coalitions and 2) how to cope with the dynamic feature where server statuses dynamically change as the tasks are performed. The coalitional Markov decision process (CMDP) model proposed in our previous work can handle these issues well. However, its basic solution, coalitional Q-learning, cannot handle the large scale problem when the task number is large in edge computing. Our response is to propose a novel algorithm called deep coalitional Q-learning (DCQL) to solve it. To sum up, we first formulate the dynamic cooperation problem of edge servers as a CMDP: each edge server is regarded as an agent and the dynamic process is modeled as a MDP where the agents observe the current state to formulate several coalitions. Each coalition takes an action to impact the environment which correspondingly transfers to the next state to repeat the above process. Then, we propose DCQL which includes a deep neural network and so can well cope with large scale problem. DCQL can guide the edge servers to form coalitions dynamically with the target of optimizing some goal. Furthermore, we run experiments to verify our proposed algorithm's effectiveness in different settings.

Coalition Structure Generation (CSG) is a main research issue in the domain of coalition games. A majority of existing works assume that the value of a coalition is independent of others in the coalition structure. Recently, there has been interest in a more realistic settings, where the value of a coalition is affected by the formation of other coalitions. This effect is known as externality. The focus of this paper is to make use of Maximum Satisfiability (MaxSAT) to solve the CSG problem where externalities may exist. In order to reduce the exponentially growing number of possible solutions in the CSG problem, we follow the previous works by representing the CSG problem as sets of rules in MC-nets (without externalities) and embedded MC-nets (with externalities). Specifically, enlightened by the previous MC-net-based algorithms exploiting the constraints among rule relations to solve the CSG problem, we encode such constraints into weighted partial MaxSAT (WPM) formulas. Experimental results demonstrate that an off-the-shelf MaxSAT solver achieves significant improvements compared to the previous algorithm for the same set of problem instances.

Coalition Structure Generation (CSG) means partitioning agents into exhaustive and disjoint coalitions so that the sum of values of all the coalitions is maximized. Solving this problem could be facilitated by employing some compact representation schemes, such as marginal contribution network (MC-net). In MC-net, the CSG problem is represented by a set of rules where each rule is associated with a real-valued weights, and the goal is to maximize the sum of weights of rules under some constraints. This naturally leads to a combinatorial optimization problem that could be solved with weighted partial MaxSAT (WPM). In general, WPM deals with only positive weights while the weights involved in a CSG problem could be either positive or negative. With this in mind, in this paper, we propose an extension of WPM to handle negative weights and take advantage of the extended WPM to solve the MC-net-based CSG problem. Specifically, we encode the relations between each pair of agents and reform the MC-net as a set of Boolean formulas. Thus, the CSG problem is encoded as an optimization problem for WPM solvers. Furthermore, we apply this agent relation-based WPM with minor revision to solve the extended CSG problem where the value of a coalition is affected by the formation of other coalitions, a coalition known as externality. Experiments demonstrate that, compared to the previous encoding, our proposed method speeds up the process of solving the CSG problem significantly, as it generates fewer number of Boolean variables and clauses that need to be examined by WPM solver.