Online Algorithms for the Santa Claus Problem

Published in NeurIPS 2022, 2022

The Santa Claus problem is a fundamental problem in fair division: the goal is to partition a set of heterogeneous items among heterogeneous agents so as to maximize the minimum value of items received by any agent. In this paper, we study the online version of this problem where the items are not known in advance and have to be assigned to agents as they arrive over time. If the arrival order of items is arbitrary, then no good assignment exists in the worst case. However, we show that even for arbitrary items, if their arrival order is random, then for any $\varepsilon > 0$, we can obtain a competitive ratio of $1-\varepsilon$ when the optimal assignment gives value at least $\Omega(\log n / \varepsilon^2)$ to every agent. We also show that this result is almost tight: namely, if the optimal solution has value at most $C \ln n / \varepsilon$ for some constant $C$, then there is no $(1-\varepsilon)$-competitive algorithm even with random arrival order.

Recommended citation: Hajiaghayi. et al (2022), Online Algorithms for the Santa Claus Problem (NeurIPS 2022)

A Machine-Learning Approach for Predicting Impaired Consciousness in Absence Epilepsy

Published in Annals of Clinical and Translational Neurology, 2022

Behavior during 3–4 Hz spike-wave discharges (SWDs) in absence epilepsy can vary from obvious behavioral arrest to no detectible deficits. Knowing if behavior is impaired is crucial for clinical care but may be difficult to determine without specialized behavioral testing, often inaccessible in practice. We aimed to develop a pure electroencephalography (EEG)-based machine-learning method to predict SWD-related behavioral impairment. Our classification goals were 100% predictive value, with no behaviorally impaired SWDs misclassified as spared; and maximal sensitivity. First, using labeled data with known behavior (130 SWDs in 34 patients), we extracted EEG time, frequency domain, and common spatial pattern features and applied support vector machines and linear discriminant analysis to classify SWDs as spared or impaired. We evaluated 32 classification models, optimized with 10-fold cross-validation. We then generalized these models to unlabeled data (220 SWDs in 41 patients), where behavior during individual SWDs was not known, but observers reported the presence of clinical seizures. For labeled data, the best classifier achieved 100% spared predictive value and 93% sensitivity. The best classifier on the unlabeled data achieved 100% spared predictive value, but with a lower sensitivity of 35%, corresponding to a conservative classification of 8 patients out of 23 as free of clinical seizures. Our findings demonstrate the feasibility of machine learning to predict impaired behavior during SWDs based on EEG features. With additional validation and optimization in a larger data sample, applications may include EEG-based prediction of driving safety, treatment adjustment, and insight into mechanisms of impaired consciousness in absence seizures.

Recommended citation: Springer, M. et al (2022), A machine-learning approach for predicting impaired consciousness in absence epilepsy. Ann Clin Transl Neurol.

Analysis of a Learning Based Algorithm for Budget Pacing

Published in arXiv, 2022

In this paper, we analyze a natural learning algorithm for uniform pacing of advertising budgets, equipped to adapt to varying ad sale platform conditions. On the demand side, advertisers face a fundamental technical challenge in automating bidding in a way that spreads their allotted budget across a given campaign subject to hidden, and potentially dynamic, “spent amount” functions…

Recommended citation: MohammadTaghi Hajiaghayi and Max Springer. (2022). "Analysis of a Learning Based Algorithm for Budget Pacing" arXiv, preprint.

The pulse: transient fMRI signal increases in subcortical arousal systems during transitions in attention.

Published in NeuroImage, 2021

Studies of attention emphasize cortical circuits for salience monitoring and top-down control. However, subcortical arousal systems have a major influence on dynamic cortical state. We hypothesize that task-related increases in attention begin with a “pulse” in subcortical arousal and cortical attention networks, which may be reflected indirectly through transient fMRI signals…

Recommended citation: Rong Li, Jun Hwan Ryu, Peter Vincent, Max Springer, Dan Kluger, Erik A. Levinsohn, Yu Chen, Huafu Chen and Hal Blumenfeld. (2021). "The pulse: transient fMRI signal increases in subcortical arousal systems during transitions in attention." Neuroimage, in press.