We report our experiences implementing standards-based grading at scale in an Algorithms course, which serves as the terminal required CS Theory course in our department's undergraduate curriculum. The course had 200-400 students, taught by two instructors, eight graduate teaching assistants, and supported by two additional graders and several undergraduate course assistants. We highlight the role of standards-based grading (SBG) in supporting our students during the COVID-19 pandemic. We conclude by detailing the successes and adjustments we would make to the course structure.

Churn prediction is an important topic in the free online game industry. Reducing the churn rate of a game significantly helps with the success of the game. Churn prediction helps a game operator identify possible churning players and keep them engaged in the game via appropriate operational strategies, marketing strategies, and/or incentives. Playtime-related features are some of the widely used universal features for most churn prediction models. In this article, we consider developing new universal features for churn predictions for long-term players based on playtime. In particular, we measure playtime regularity using the notion ofentropyandcross-entropyfrom information theory. After computing playtime regularity of players from the datasets of six free online games of different types, we leverage information from the playtime regularity in the form of universal features for churn prediction. Experiments show that the proposed features are better at predicting churners compared to the baseline features, implying that the proposed features could utilize the information extracted from playtime more effectively than the related baseline playtime features.

We study incentivized exploration for the multi-armed bandit (MAB) problem where the players receive compensation for exploring arms other than the greedy choice and may provide biased feedback on reward. We seek to understand the impact of this drifted reward feedback by analyzing the performance of three instantiations of the incentivized MAB algorithm: UCB, ε-Greedy, and Thompson Sampling. Our results show that they all achieve O(log T) regret and compensation under the drifted reward, and are therefore effective in incentivizing exploration. Numerical examples are provided to complement the theoretical analysis.

Personality inference could create useful information, especially for the game industry. In this paper, we investigate whether and how the player personality is revealed in the player social interactions in a massively multiplayer online strategy game. We conduct an online survey with 50,319 participants to collect the player personality traits. We then develop proper features to capture the player in-game social interactions, and analyze correlations between personality and social interactions using these features. Our results show that the in-game social interactions are correlated with personality, and reveal how personality can affect social interactions in massively multiplayer online strategy games. Then we further discuss the implication of our results.

Multi-robot cooperation requires agents to make decisions that are consistent with the shared goal without disregarding action-specific preferences that might arise from asymmetry in capabilities and individual objectives. To accomplish this goal, we propose a method named SLiCC: Stackelberg Learning in Cooperative Control. SLiCC models the problem as a partially observable stochastic game composed of Stackelberg bimatrix games, and uses deep reinforcement learning to obtain the payoff matrices associated with these games. Appropriate cooperative actions are then selected with the derived Stackelberg equilibria. Using a bi-robot cooperative object transportation problem, we validate the performance of SLiCC against centralized multi-agent Q-learning and demonstrate that SLiCC achieves better combined utility.

In the free online game industry, in-game purchase prediction is an important research topic. On the one hand, knowing the players who are likely or unlikely to pay for the game can help the development of corresponding marketing strategies and incentives. On the other hand, the result of purchase prediction indicates the status of the game operation status and helps the game company allocate a reasonable amount of resources for the game. In this paper, we focus on predicting the purchase probability of paying players and finding important features. We consider two types of features related to players’ playing and purchase behaviors. Then, based on these features we proposed, we use two different models to predict the survival probability for players and analyze the feature importance.

In the free online game industry, churn prediction is an important research topic. Reducing churn rate of a game significantly helps with the success of the game. Churn prediction helps a game operator identify possible churning players and keep them engaged in the game via appropriate operational strategies, marketing strategies, and/or incentives. Most churn prediction models are based on game-specific features, which limits their applicability to other games that do not share those features. In this paper, we consider developing universal features for churn predictions for long-term players. In particular, we mine player time spending regularity from data sets of two free online games. We leverage information from players’ in-game time spending regularity in the form of universal features for churn prediction. Experiments show that our developed features are better at predicting churners, compared to the baseline features. The performance of our developed features is satisfactory even without game-specific features.

The free online game market is one of the fastest growing and most profitable markets in the electronic game industry. In order to improve players’ gaming experience and increase revenue, game data analytics is usually applied to support game development, in-game event design, and game operation. In particular, the game companies strive to understand and characterize the players’ buying power and design marketing strategies or incentives accordingly to increase their revenues. In this paper, we propose a novel algorithm to perform player clustering into the groups of high spenders (whales), moderate spenders (dolphins), and low spenders (minnows) based on the players’ purchase records via data mining technique. Evaluations including an A/B test with a typical popular free online game show that our proposed algorithm can effectively cluster the players in terms of their purchasing behavior and the game companies can benefit from our algorithm.

Self-driving vehicles are being increasingly deployed in the wild. One of the most important next hurdles for autonomous driving is how such vehicles will optimally interact with one another and with their surroundings. In this paper, we consider the lane changing problem that is fundamental to road-bound multi-vehicle systems, and approach it through a combination of deep reinforcement learning (DRL) and game theory. We introduce a proactive-passive lane changing framework and formulate the lane changing problem as a Markov game between the proactive and passive vehicles. Based on different approaches to carry out DRL to solve the Markov game, we propose an asynchronous lane changing scheme as in a single-agent RL setting and a synchronous cooperative lane changing scheme that takes into consideration the adaptive behavior of the other vehicle in a vehicle's decision. Experimental results show that the synchronous scheme can effectively create and find proper merging moment after sufficient training. The framework and solution developed here demonstrate the potential of using reinforcement learning to solve multi-agent autonomous vehicle tasks such as the lane changing as they are formulated as Markov games.

We consider a cognitive radio network with one primary (PU), one secondary user (SU), and two distinct destinations. SU not only exploits the idle time slots (i.e. PU is not transmitting) to send its own packets, but also interfere with the PU with a certain probability that is optimized to maximize the stable throughput of the SU under a delay constraint for the PU. This optimization problem is formulated using two schemes. First, the hard delay guarantee scheme where the objective is to maximize the throughput of the SU subject to the delay of the PU's packet is less than a certain value. Second, the soft delay guarantee scheme where the objective is to minimize the delay of the PU's packets minus a constant multiplied by the throughput of the SU. Numerical results reveal that none of the proposed outperforms the other in general. The first scheme ensures a fix delay performance for the PU's packets on the boundary of the stability region. While the second scheme guarantees a finite delay performance with higher stable throughput than that of the first scheme.

MIMO interference network optimization is important for increasingly crowded wireless communication networks. This paper presents a new algorithm, named Dual Link Algorithm, for weighted sum-rate maximization where the interference is efficiently managed. We consider general MIMO interference channels with Gaussian input and a total power constraint. Two of the previous state-of-the-art algorithms are the WMMSE algorithm and the polite water-filling (PWF) algorithm. The WMMSE algorithm is provably convergent, while the PWF algorithm takes the advantage of the optimal transmit signal structure and converges the fastest in most situations but is not guaranteed to converge in all situations. Therefore, it is highly desirable to design an algorithm that has the advantages of both algorithms. The proposed dual link algorithm is such an algorithm. Its fast and guaranteed convergence is important to distributed implementation and time varying channels. In addition, the technique and a scaling invariance property used in the convergence proof may find applications in other non-convex problems in communication networks.

Speed scaling has been widely adopted in computer and communication systems, in particular, to reduce energy consumption. An important question is how speed scaling interacts with other resource allocation mechanisms such as scheduling and routing. In this paper, we study the interaction of speed scaling with load balancing. We characterize the equilibrium resulting from the load balancing and speed scaling interaction, and introduce two optimal load-balancing designs, in terms of traditional performance metric and cost-aware (in particular, energy-aware) performance metric, respectively. Especially, we characterize the load-balancing–speed-scaling equilibrium with respect to the optimal load-balancing schemes in processor-sharing systems. Our results show that the degree of inefficiency at the equilibrium is mostly bounded by the heterogeneity of the system, but independent of the number of servers. These results provide insights in understanding the interaction of load balancing with speed scaling and guiding new designs.

The weighted sum-rate maximization in a general multiple-input multiple-output (MIMO) interference network has known to be a challenging non-convex problem, mainly due to the interference between different links. In this paper, by exploring the special structure of the sum-rate function being a difference of concave functions, we apply the convex-concave procedure to the weighted sum-rate maximization to handle non-convexity. With the introduction of a certain damping term, we establish the monotonie convergence of the proposed algorithm. Numerical examples show that the introduced damping term slows down the convergence of our algorithm but helps with finding a better solution in the network with high interference. Even though our algorithm has a slower convergence than some existing ones, it has the guaranteed convergence and can handle more general constraints and thus provides a general solver that can find broader applications.

Our dependence on mobile communications continues to grow; however, wireless devices may encounter inadequate coverage due to a variety of shortage and outage circumstances. In particular, in disaster situations, the access to communications is critical for rescue operations while local wireless infrastructure may have suffered damage. In this paper, we demonstrate the concept of hybrid cellular mobile ad hoc network (hybrid cellular-MANET) to extend wireless coverage by showing a fully functioning microblogging system for smartphones and tablets without requiring modifications of the existing wireless infrastructure in an emulated disaster area. Participating devices connect to each other through WiFi radio to form a hybrid cellular-MANET, relaying data off the MANET through the nodes that have sufficient cellular forwarding capability. We have proposed a self-organizing, mobility-aware, multi-path routing protocol (HMANET) to control the data forwarding in the hybrid cellular-MANET. We compare its performance with the classic Hybrid Wireless Mesh Protocol (HWMP) used in the IEEE 802.11s standard in the built microblogging system. Our experimental results show that the HMANET protocol statistically outperforms the HWMP protocol in terms of adaptiveness to role change and mobility in the hybrid cellular-MANET.

We consider lossy data compression in capacity-constrained networks with correlated sources. We derive, using dual decomposition, a distributed algorithm that maximizes an aggregate utility measure defined in terms of the distortion levels of the sources. No coordination among sources is required; each source adjusts its distortion level according to distortion prices fed back by the sinks. The algorithm is developed for the case of squared error distortion and high resolution coding where the rate-distortion region is known, and can be easily extended to consider achievable regions that can be expressed in a related form. Our distributed optimization framework applies to unicast and multicast with and without network coding. Numerical examples show relatively fast convergence, allowing the algorithm to be used in time-varying networks.

Recent advances in network coding have shown great potential for efficient information multicasting in communication networks, in terms of both network throughput and network management. In this paper, the problem of flow control at end-systems for network-coding-based multicast flows is addressed. Optimization-based models are formulated for network resource allocation, based on which two sets of decentralized controllers at sources and links/nodes for congestion control are developed for wired networks with given coding subgraphs and without given coding subgraphs, respectively. With random network coding, both sets of controllers can be implemented in a distributed manner, and work at the transport layer to adjust source rates and at network layer to carry out network coding. The convergence of the proposed controllers to the desired equilibrium operating points is proved, and numerical examples are provided to complement the theoretical analysis. The extension to wireless networks is also briefly discussed.

In this paper, we consider cross-layer optimization in wireless networks with wireless broadcast advantage, focusing on the problem of distributed scheduling of broadcast links. The wireless broadcast advantage is most useful in multicast scenarios. As such, we include network coding in our design to exploit the throughput gain brought in by network coding for multicasting. We derive a subgradient algorithm for joint rate control, network coding and scheduling, which however requires centralized link scheduling. Under the primary interference model, link scheduling problem is equivalent to a maximum weighted hypergraph matching problem that is NP-complete. To solve the scheduling problem distributedly, locally greedy and randomized approximation algorithms are proposed and shown to have bounded worst-case performance. With random network coding, we obtain a fully distributed cross-layer design. Numerical results show promising throughput gain using the proposed algorithms, and surprisingly, in some cases even with less complexity than cross-layer design without broadcast advantage.

Motivated partially by a control-theoretic viewpoint, we propose a game-theoretic model, calledrandom access game, for contention control. We characterize Nash equilibria of random access games, study their dynamics, and propose distributed algorithms (strategy evolutions) to achieve Nash equilibria. This provides a general analytical framework that is capable of modeling a large class of system-wide quality-of-service (QoS) models via the specification of per-node utility functions, in which system-wide fairness or service differentiation can be achieved in a distributed manner as long as each node executes a contention resolution algorithm that is designed to achieve the Nash equilibrium. We thus propose a novel medium access method derived from carrier sense multiple access/collision avoidance (CSMA/CA) according to distributed strategy update mechanism achieving the Nash equilibrium of random access game. We present a concrete medium access method that adapts to a continuous contention measure called conditional collision probability, stabilizes the network into a steady state that achieves optimal throughput with targeted fairness (or service differentiation), and can decouple contention control from handling failed transmissions. In addition to guiding medium access control design, the random access game model also provides an analytical framework to understand equilibrium and dynamic properties of different medium access protocols.

We consider energy efficient network coding design in wireless networks with multiple unicast sessions. Our approach decomposes multiple unicast sessions into a superposition of multicast and unicast sessions, with coding occurring only within each session. We give an optimization approach that is more general than the existing poison-remedy optimization formulation. For the case of wireless, we consider XOR coding and give an achievable rate region for a primary interference model. To simplify network operation, we give an oblivious backpressure algorithm which does not optimize overhearing of transmissions, and a practical protocol called COPR based on the oblivious backpressure algorithm. Simulation experiments show that COPR largely reduces network power consumption over existing algorithms.

In this paper, we generalize the random access game model, and show that it provides a general gametheoretic framework for designing contention based medium access control. We extend the random access game model to the network with multiple contention measure signals, study the design of random access games, and analyze different distributed algorithms achieving their equilibria. As examples, a series of utility functions is proposed for games achieving the maximum throughput in a network of homogeneous nodes. In a network with n traffic classes, an N-signal game model is proposed which achieves the maximum throughput under the fairness constraint among different traffic classes. In addition, the convergence of different dynamic algorithms such as best response, gradient play and Jacobi play under propagation delay and estimation error is established. Simulation results show that game model based protocols can achieve superior performance over the standard IEEE 802.11 DCF, and comparable performance as existing protocols with the best performance in literature.

Recent advances in network coding have shown great potential for efficient information multicasting in communication networks, in terms of both network throughput and network management. In this paper, we address the problem of rate control at end-systems for network coding based multicast flows. We develop two adaptive rate control algorithms for the networks with given coding subgraphs and without given coding subgraphs, respectively. With random network coding, both algorithms can be implemented in a distributed manner, and work at transport layer to adjust source rates and at network layer to carry out network coding. We prove that the proposed algorithms converge to the globally optimal solutions for intra-session network coding. Some related issues are discussed, and numerical examples are provided to complement our theoretical analysis.

We consider lossy data compression in capacity-constrained ned networks with correlated sources. We develop, using dual decomposition, a distributed algorithm that maximizes an aggregate utility measure defined in terms of the distortion levels of the sources. No coordination among sources is required; each source adjusts its distortion level according to distortion prices fed back by the sinks. The algorithm is developed for the case of squared error distortion and high resolution coding where the rate distortion region is known, and is easily extended to consider achievable regions that can be expressed in a related form. Our distributed optimization framework applies to unicast and multicast with and without network coding. Numerical example shows relatively fast convergence, allowing the algorithm to be used in time-varying networks.

We propose a jointly opportunistic source coding and opportunistic routing (OSCOR) protocol for correlated data gathering in wireless sensor networks. OSCOR improves data gathering efficiency by exploiting opportunistic data compression and cooperative diversity associated with wireless broadcast advantage. The design of OSCOR involves several challenging issues across different network protocol layers. At the MAC layer, sensor nodes need to coordinate wireless transmission and packet forwarding to exploit multiuser diversity in packet reception. At the network layer, in order to achieve high diversity and compression gains, routing must be based on a metric that is dependent on not only link-quality but also compression opportunities. At the application layer, sensor nodes need a distributed source coding algorithm that has low coordination overhead and does not require the source distributions to be known. OSCOR provides practical solutions to these challenges incorporating a slightly modified 802.11 MAC, a distributed source coding scheme based on network coding and Lempel-Ziv coding, and a node compression ratio dependent metric combined with a modified Dijkstra's algorithm for path selection. We evaluate the performance of OSCOR through simulations, and show that OSCOR can potentially reduce power consumption by over 30% compared with an existing greedy scheme, routing driven compression, in a 4 × 4 grid network.

Abstract — This paper considers jointly optimal design of cross-layer congestion control, routing and scheduling for ad hoc wireless networks. We first formulate the rate constraint and scheduling constraint using multicommodity flow variables, and formulate resource allocation in networks with fixed wireless channels (or single-rate wireless devices that can mask channel variations) as a utility maximization problem with these con-straints. By dual decomposition, the resource allocation problem naturally decomposes into three subproblems: congestion control, routing and scheduling that interact through congestion price. The global convergence property of this algorithm is proved. We next extend the dual algorithm to handle networks with time-varying channels and adaptive multi-rate devices. The stability of the resulting system is established, and its performance is characterized with respect to an ideal reference system which has the best feasible rate region at link layer. We then generalize the aforementioned results to a general model of queueing network served by a set of interdependent parallel servers with time-varying service capabilities, which models many design problems in communication networks. We show that for a general convex optimization problem where a subset of variables lie in a polytope and the rest in a convex set, the dual-based algorithm remains stable and optimal when the constraint set is modulated by an irreducible finite-state Markov chain. This paper thus presents a step toward a systematic way to carry out cross-layer design in the framework of “layering as optimization decomposition ” for time-varying channel models. I.

We present a model for the joint design of congestion control and media access control (MAC) for ad hoc wireless networks. Using contention graph and contention matrix, we formulate resource allocation in the network as a utility maximization problem with constraints that arise from contention for channel access. We present two algorithms that are not only distributed spatially, but more interestingly, they decompose vertically into two protocol layers where TCP and MAC jointly solve the system problem. The first is a primal algorithm where the MAC layer at the links generates congestion (contention) prices based on local aggregate source rates, and TCP sources adjust their rates based on the aggregate prices in their paths. The second is a dual subgradient algorithm where the MAC sub-algorithm is implemented through scheduling link-layer flows according to the congestion prices of the links. Global convergence properties of these algorithms are proved. This is a preliminary step towards a systematic approach to jointly design TCP congestion control algorithms and MAC algorithms, not only to improve performance, but more importantly, to make their interaction more transparent.