Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

arXiv:2402.05300v2 (Ed.)This paper considers a multiplayer resourcesharing game with a fair reward allocation model. Multiple players choose from a collection of resources. Each resource brings a random reward equally divided among the players who choose it. We consider two settings. The first setting is a oneslot game where the mean rewards of the resources are known to all the players, and the objective of player 1 is to maximize their worstcase expected utility. Certain special cases of this setting have explicit solutions. These cases provide interesting yet nonintuitive insights into the problem. The second setting is an online setting, where the game is played over a finite time horizon, where the mean rewards are unknown to the first player. Instead, the first player receives, as feedback, the rewards of the resources they chose after the action. We develop a novel Upper Confidence Bound (UCB) algorithm that minimizes the worstcase regret of the first player using the feedback received.more » « lessFree, publiclyaccessible full text available March 4, 2025

arXiv:2401.07170v1 (Ed.)This paper considers online optimization for a system that performs a sequence of backtoback tasks. Each task can be processed in one of multiple processing modes that affect the duration of the task, the reward earned, and an additional vector of penalties (such as energy or cost). Let A[k] be a random matrix of parameters that specifies the duration, reward, and penalty vector under each processing option for task k. The goal is to observe A[k] at the start of each new task k and then choose a processing mode for the task so that, over time, time average reward is maximized subject to time average penalty constraints. This is a renewal optimization problem and is challenging because the probability distribution for the A[k] sequence is unknown. Prior work shows that any algorithm that comes within ϵ of optimality must have (1/ϵ^2) convergence time. The only known algorithm that can meet this bound operates without time average penalty constraints and uses a diminishing stepsize that cannot adapt when probabilities change. This paper develops a new algorithm that is adaptive and comes within O(ϵ) of optimality for any interval of (1/ϵ^2) tasks over which probabilities are held fixed, regardless of probabilities before the start of the interval.more » « lessFree, publiclyaccessible full text available January 13, 2025

arXiv:2311.11180v1 (Ed.)This paper presents a subgradientbased algorithm for constrained nonsmooth convex optimization that does not require projections onto the feasible set. While the wellestablished FrankWolfe algorithm and its variants already avoid projections, they are primarily designed for smooth objective functions. In con trast, our proposed algorithm can handle nonsmooth problems with general convex functional inequality constraints. It achieves an ϵsuboptimal solution in O(ϵ^−2) iterations, with each iteration requiring only a single (potentially inexact) Linear Minimization Oracle (LMO) call and a (possibly inexact) subgra dient computation. This performance is consistent with existing lower bounds. Similar performance is observed when deterministic subgradients are replaced with stochastic subgradients. In the special case where there are no functional inequality constraints, our algorithm competes favorably with a recent nonsmooth projectionfree method designed for constraintfree problems. Our approach uti lizes a simple separation scheme in conjunction with a new Lagrange multiplier update rule.more » « lessFree, publiclyaccessible full text available November 18, 2024

Yllka Velaj and Ulrich Berger (Ed.)
This paper considers a twoplayer game where each player chooses a resource from a finite collection of options. Each resource brings a random reward. Both players have statistical information regarding the rewards of each resource. Additionally, there exists an information asymmetry where each player has knowledge of the reward realizations of different subsets of the resources. If both players choose the same resource, the reward is divided equally between them, whereas if they choose different resources, each player gains the full reward of the resource. We first implement the iterative best response algorithm to find an ϵapproximate Nash equilibrium for this game. This method of finding a Nash equilibrium may not be desirable when players do not trust each other and place no assumptions on the incentives of the opponent. To handle this case, we solve the problem of maximizing the worstcase expected utility of the first player. The solution leads to counterintuitive insights in certain special cases. To solve the general version of the problem, we develop an efficient algorithmic solution that combines online convex optimization and the driftplus penalty technique.
Free, publiclyaccessible full text available October 1, 2024 
This paper revisits a classical problem of slotted multiple access with success, idle, and collision events on each slot. First, results of a 2user multiple access game are reported. The game was conducted at the University of Southern California over multiple semesters and involved competitions between studentdesigned algorithms. An algorithm called 4State was a consistent winner. This algorithm is analyzed and shown to have an optimal expected score when competing against an independent version of itself. The structure of 4State motivates exploration of the open question of how to minimize the expected time to capture the channel for a nuser situation. It is assumed that the system delivers perfect feedback on the number of users who transmitted at the end of each slot. An efficient algorithm is developed and conjectured to have an optimal expected capture time for all positive integers n. Optimality is proven in the special cases n ∈ {1, 2, 3, 4, 6} using a novel analytical technique that introduces virtual users with enhanced capabilities.more » « less

Future generation wireless technologies are expected to serve an increasingly dense and dynamic population of users that generate short bundles of information to be transferred over the shared spectrum. This calls for new distributed and lowoverhead MultipleAccessControl (MAC) strategies to serve such dynamic demands with spectral efficiency characteristics. In this work, we address this need by identifying and developing two fundamentally different MAC paradigms: (i) congestionbased paradigm that estimates the congestion level in the system and adapts to it; and (ii) agebased paradigm that prioritizes demands based on their ages. Despite their apparent differences, we develop policies under each paradigm in a generic multichannel access scenario that are provably throughputoptimal when they employ any asymptoticallyefficient channel encoding/decoding mechanism. We also characterize the stability regions of the two designs, and investigate the conditions under which one design outperforms the other. We perform extensive simulations to validate the theoretical claims and investigate the nonasymptotic performances of our designs.more » « less

This paper proves a representation theorem regarding sequences of random elements that take values in a Borel space and are measurable with respect to the sigma algebra generated by an arbitrary union of sigma algebras. This, together with a related representation theorem of Kallenberg, is used to characterize the set of multidimensional decision vectors in a discrete time stochastic control problem with measurability and causality constraints, including opportunistic scheduling problems for timevarying communication networks. A network capacity theorem for these systems is refined, without requiring an implicit and arbitrarily complex extension of the state space, by introducing two measurability assumptions and using a theory of constructible sets. An example that makes use of well known pathologies in descriptive set theory is given to show a nonmeasurable scheduling scheme can outperform all measurable scheduling schemes.more » « less

With the adoption of 5G wireless technology and the InternetofThings (IoT) networking, there is a growing interest in serving a dense population of lowcomplexity devices over shared wireless uplink channels. Different from the traditional scenario of persistent users, in these new networks each user is expected to generate only small bundles of information intermittently. The highly dynamic nature of such demand and the typically lowcomplexity nature of the user devices calls for a new MAC paradigm that is geared for lowoverhead and distributed operation of dynamic users.In this work, we address this need by developing a generic MAC mechanism for estimating the number and coordinating the activation of dynamic users for efficient utilization of the timefrequency resources with minimal public feedback from the common receiver. We fully characterize the throughput and delay performance of our design under a basic thresholdbased multichannel capacity condition, which allows for the use of different channel utilization schemes. Moreover, we consider the SuccessiveInterferenceCancellation (SIC) MultiChannel MAC scheme as a specific choice in order to demonstrate the performance of our design for a spectrallyefficient (albeit idealized) scheme. Under the SIC encoding/decoding scheme, we prove that our lowoverhead distributed MAC can support maximum throughput, which establishes the efficiency of our design. Under SIC, we also demonstrate how the basic thresholdbased success model can be relaxed to be adapted to the performance of a nonideal success model.more » « less

null (Ed.)This paper presents a network layer model for a wireless multiple access system with both persistent and nonpersistent users. There is a single access point with multiple identical channels. Each user who wants to send a file first scans a subset of the channels to find one that is idle. If at least one idle channel is found, the user transmits a file over that channel. If no idle channel is found, a persistent user will repeat the access attempt at a later time, while a nonpersistent user will leave. This is a useful mathematical model for situations where a group of persistent users stay near an access point for an extended period of time while nonpersistent users come and go. Users have heterogeneous activity behavior, file upload rates, and service durations. The system is a complex multidimensional Markov chain. The steady state probabilities are found by exploiting a latent reversibility property and leveraging a discrete Fourier transform. This enables simple expressions for throughput and blocking probability.more » « less