Search

Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given distribution. Upon observing each value, the gambler either accepts it as a reward or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is maximising the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. This model has been studied with infinite, finite and unknown number of values. When the gambler faces a random number of values, the model is said to have random horizon. We consider the model in which the gambler is given a priori knowledge of the horizon's distribution. Alijani et al. (2020) designed a single-threshold algorithms achieving a ratio of $1/2$ when the random horizon has an increasing hazard rate and is independent of the values. We prove that with a single-threshold, a ratio of $1/2$ is actually achievable for several larger classes of horizon distributions, with the largest being known as the $\mathcal{G}$ class in reliability theory. Moreover, we extend this result to its dual, the $\overline{\mathcal{G}}$ class (which includes the decreasing hazard rate class), and to low-variance horizons. Finally, we construct the first example of a family of horizons, for which multiple thresholds are necessary to achieve a nonzero ratio. We establish that the Secretary Problem optimal stopping rule provides one such algorithm, paving the way towards the study of the model beyond single-threshold algorithms., Comment: 54 pages, 2 figures

We examine sorting algorithms for $n$ elements whose basic operation is comparing $t$ elements simultaneously (a $t$-comparator). We focus on algorithms that use only a single round or two rounds -- comparisons performed in the second round depend on the outcomes of the first round comparators. We design deterministic and randomized algorithms. In the deterministic case, we show an interesting relation to design theory (namely, to 2-Steiner systems), which yields a single-round optimal algorithm for $n=t^{2^k}$ with any $k\ge 1$ and a variety of possible values of $t$. For some values of $t$, however, no algorithm can reach the optimal (information-theoretic) bound on the number of comparators. For this case (and any other $n$ and $t$), we show an algorithm that uses at most three times as many comparators as the theoretical bound. We also design a randomized Las-Vegas two-rounds sorting algorithm for any $n$ and $t$. Our algorithm uses an asymptotically optimal number of $O(\max(\frac{n^{3/2}}{t^2},\frac{n}{t}))$ comparators, with high probability, i.e., with probability at least $1-1/n$. The analysis of this algorithm involves the gradual unveiling of randomness, using a novel technique which we coin the binary tree of deferred randomness.

We study the ionised gas kinematics of 293 Active Galactic Nuclei (AGN) hosts as compared to that of 485 control galaxies from the MaNGA-SDSS survey using measurements of the [OIII]$\lambda$5007\AA emission-line profiles, presenting flux, velocity and W$_{80}$ maps. In 45% of the AGN, a broad component was needed to fit the line profiles wings within the inner few kpc, that we have identified with an outflow. But in most AGN, the profiles are broader than that of their controls over a much more extended region, identified as the "kinematically disturbed regions" (KDRs). We find a positive correlation between the mean $\langle$W$_{80}\rangle$ and L[OIII], supporting that the KDR is due to heating and turbulence of the ISM by outflows and radiation from the AGN. The extent R$_{KDR}$ reaches up to 24kpc, with a mean ratio to that of the ENLR of 57%. We estimate ionised gas mass flow rates ($\dot{M}_{\rm out}$) and kinetic powers ($\dot{E}_{\rm out}$) both from the AGN broad components and from the W$_{80}$ values, that can be obtained for the whole AGN sample. We find values for $\dot{M}_{\rm out}$ and $\dot{E}_{\rm out}$ that correlate with the AGN luminosity $L_{bol}$, populating the low luminosity end of these known correlations. The mean coupling efficiency between $\dot{E}_{\rm out}$ and AGN luminosity is $\approx$ 0.02% from the W$_{80}$ values and lower from the broad component. But the large extent of the KDR shows that even low-luminosity AGN can impact the host galaxy along several kpc in a "maintenance mode" feedback.

We introduce the concept of community consensus in the presence of malicious agents using a well-known median-based consensus algorithm. We consider networks that have multiple well-connected regions that we term communities, characterized by specific robustness and minimum degree properties. Prior work derives conditions on properties that are necessary and sufficient for achieving global consensus in a network. This, however, requires the minimum degree of the network graph to be proportional to the number of malicious agents in the network, which is not very practical in large networks. In this work, we present a natural generalization of this previous result. We characterize cases where, although global consensus is not reached, some subsets of agents $V_i$ will still converge to the same values $M_i$ among themselves. To reach this new type of consensus, we define more relaxed requirements in terms of the number of malicious agents in each community, and the number $k$ of edges connecting an agent in a community to agents external to the community.

We present spaxel-by-spaxel stellar population fits for the $\sim$10 thousand MaNGA datacubes. We provide multiple extension fits files, nominated as MEGACUBES, with maps of several properties as well as emission-line profiles that are provided for each spaxel. All the MEGACUBES are available through a web interface (\url{https://manga.linea.org.br/} or \url{http://www.if.ufrgs.br/~riffel/software/megacubes/}). We also defined a final Active Galactic Nuclei (AGN) sample, as well as a control sample matching the AGN host galaxy properties. We have analysed the stellar populations and spatially resolved emission-line diagnostic diagrams of these AGNs and compared them with the control galaxies sample. We find that the relative fractions of young ($t \leq $56 Myr) and intermediate-age (100 Myr $\leq t \leq$ 2 Gyr) show predominantly a positive gradient for both AGNs and controls. The relative fraction of intermediate-age stellar population is higher in AGN hosts when compared to the control sample, and this difference becomes larger for higher [O III] luminosity AGNs. We attribute this to the fact that extra gas is available in these more luminous sources and that it most likely originates from mass-loss from the intermediate-age stars. The spatially resolved diagnostic diagrams reveal that the AGN emission is concentrated in the inner 0.5 $R_e$ (effective radius) region of the galaxies, showing that the AGN classification is aperture dependent and that emission-line ratios have to be taken together with the H$\alpha$ equivalent width for proper activity classification. We present a composite ``BPT+WHAN" diagram that produces a more comprehensive mapping of the gas excitation., Comment: Accepted for publication in MNRAS; small typos corrected

We continue our study from Lynch and Mallmann-Trenn (Neural Networks, 2021), of how concepts that have hierarchical structure might be represented in brain-like neural networks, how these representations might be used to recognize the concepts, and how these representations might be learned. In Lynch and Mallmann-Trenn (Neural Networks, 2021), we considered simple tree-structured concepts and feed-forward layered networks. Here we extend the model in two ways: we allow limited overlap between children of different concepts, and we allow networks to include feedback edges. For these more general cases, we describe and analyze algorithms for recognition and algorithms for learning.

Prophet inequalities are a central object of study in optimal stopping theory. A gambler is sent values in an online fashion, sampled from an instance of independent distributions, in an adversarial, random or selected order, depending on the model. When observing each value, the gambler either accepts it as a reward or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is maximising the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. The model, in which the gambler selects the arrival order first, and then observes the values, is known as Order Selection. In this model a ratio of $0.7251$ is attainable for any instance. Recently, this has been improved up to $0.7258$ by Bubna and Chiplunkar (2023). If the gambler chooses the arrival order (uniformly) at random, we obtain the Random Order model. The worst case ratio over all possible instances has been extensively studied for at least $40$ years. Through simulations, Bubna and Chiplunkar (2023) also showed that this ratio is at most $0.7254$ for the Random Order model, thus establishing for the first time that carefully choosing the order, instead of simply taking it at random, benefits the gambler. We give an alternative, non-simulation-assisted proof of this fact, by showing mathematically that in the Random Order model, no algorithm can achieve a ratio larger than $0.7235$. This sets a new state-of-the-art hardness for this model, and establishes more formally that there is a real benefit in choosing the order., Comment: 36 pages, 2 figures

Coordination in a large number of networked robots is a challenging task, especially when robots are constantly moving around the environment and there are malicious attacks within the network. Various approaches in the literature exist for detecting malicious robots, such as message sampling or suspicious behavior analysis. However, these approaches require every robot to sample every other robot in the network, leading to a slow detection process that degrades team performance. This paper introduces a method that significantly decreases the detection time for legitimate robots to identify malicious robots in a scenario where legitimate robots are randomly moving around the environment. Our method leverages the concept of ``Dynamic Crowd Vetting" by utilizing observations from random encounters and trusted neighboring robots' opinions to quickly improve the accuracy of detecting malicious robots. The key intuition is that as long as each legitimate robot accurately estimates the legitimacy of at least some fixed subset of the team, the second-hand information they receive from trusted neighbors is enough to correct any misclassifications and provide accurate trust estimations of the rest of the team. We show that the size of this fixed subset can be characterized as a function of fundamental graph and random walk properties. Furthermore, we formally show that as the number of robots in the team increases the detection time remains constant. We develop a closed form expression for the critical number of time-steps required for our algorithm to successfully identify the true legitimacy of each robot to within a specified failure probability. Our theoretical results are validated through simulations demonstrating significant reductions in detection time when compared to previous works that do not leverage trusted neighbor information., Comment: 9 pages, 5 figures, extended version of paper submitted to the IEEE Conference on Decision and Control (CDC 2023)

We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node $u$ has an initial value $\xi_u(0)$. In the first process, the NodeModel, at each time step $t\ge 0$, a random node $u$ and a random sample of $k$ of its neighbours $v_1,v_2,\cdots,v_k$ are selected. Then, $u$ updates its current value $\xi_u(t)$ to $\xi_u(t+1) = \alpha \xi_u(t) + \frac{(1-\alpha)}{k} \sum_{i=1}^k \xi_{v_i}(t)$, where $\alpha \in (0,1)$ and $k\ge 1$ are parameters of the process. In the second process, the EdgeModel, at each step a random pair of adjacent nodes $(u,v)$ is selected, and then node $u$ updates its value equivalently to the NodeModel with $k=1$ and $v$ as the selected neighbour. For both processes, the values of all nodes converge to $F$, a random variable depending on the random choices made in each step. For the NodeModel and regular graphs, and for the EdgeModel and arbitrary graphs, the expectation of $F$ is the average of the initial values $\frac{1}{n}\sum_{u\in V} \xi_u(0)$. For the NodeModel and non-regular graphs, the expectation of $F$ is the degree-weighted average of the initial values. Our results are two-fold. We consider the concentration of $F$ and show tight bounds on the variance of $F$ for regular graphs. We show that, when the initial values do not depend on the number of nodes, then the variance is negligible, hence the nodes are able to estimate the initial average of the node values. Interestingly, this variance does not depend on the graph structure. For the proof we introduce a duality between our processes and a process of two correlated random walks. We also analyse the convergence time for both models and for arbitrary graphs, showing bounds on the time $T_\varepsilon$ required to make all node values `$\varepsilon$-close' to each other. Our bounds are asymptotically tight under assumptions on the distribution of the initial values., Comment: 21 pages, 6 figures

Among the various aspects of algorithmic fairness studied in recent years, the tension between satisfying both \textit{sufficiency} and \textit{separation} -- e.g. the ratios of positive or negative predictive values, and false positive or false negative rates across groups -- has received much attention. Following a debate sparked by COMPAS, a criminal justice predictive system, the academic community has responded by laying out important theoretical understanding, showing that one cannot achieve both with an imperfect predictor when there is no equal distribution of labels across the groups. In this paper, we shed more light on what might be still possible beyond the impossibility -- the existence of a trade-off means we should aim to find a good balance within it. After refining the existing theoretical result, we propose an objective that aims to balance \textit{sufficiency} and \textit{separation} measures, while maintaining similar accuracy levels. We show the use of such an objective in two empirical case studies, one involving a multi-objective framework, and the other fine-tuning of a model pre-trained for accuracy. We show promising results, where better trade-offs are achieved compared to existing alternatives.

We derive the metallicity (traced by the O/H abundance) of the Narrow Line Region ( NLR) of 108 Seyfert galaxies as well as radial metallicity gradients along their galaxy disks and of these of a matched control sample of no active galaxies. In view of that, observational data from the SDSS-IV MaNGA survey and strong emission-line calibrations taken from the literature were considered. The metallicity obtained for the NLRs %each Active Galactic Nucleus (AGN) was compared to the value derived from the extrapolation of the radial oxygen abundance gradient, obtained from \ion{H}{ii} region estimates along the galaxy disk, to the central part of the host galaxies. We find that, for most of the objects ($\sim 80\,\%$), the NLR metallicity is lower than the extrapolated value, with the average difference ($$) between these estimates ranging from 0.16 to 0.30 dex. We suggest that $$ is due to the accretion of metal-poor gas to the AGN that feeds the nuclear supermassive black hole (SMBH), which is drawn from a reservoir molecular and/or neutral hydrogen around the SMBH. Additionally, we look for correlations between $D$ and the electron density ($N_{\rm e}$), [\ion{O}{iii}]$\lambda$5007 and H$\alpha$ luminosities, extinction coefficient ($A_{V})$ of the NLRs, as well as the stellar mass ($M_{*}$) of the host galaxies. Evidences of an inverse correlation between the $D$ and the parameters $N_{\rm e}$, $M_{*}$ and $A_{\rm v}$ were found.

Ionised gas kinematics provide crucial evidence of the impact that active galactic nuclei (AGN) have in regulating star formation in their host galaxies. Although the presence of outflows in AGN host galaxies has been firmly established, the calculation of outflow properties such as mass outflow rates and kinetic energy remains challenging. We present the [OIII]5007 ionised gas outflow properties of 22 z$<$0.1 X-ray AGN, derived from the BAT AGN Spectroscopic Survey using MUSE/VLT. With an average spatial resolution of 1" (0.1-1.2 kpc), the observations resolve the ionised gas clouds down to sub-kiloparsec scales. Resolved maps show that the [OIII] velocity dispersion is, on average, higher in regions ionised by the AGN, compared to star formation. We calculate the instantaneous outflow rates in individual MUSE spaxels by constructing resolved mass outflow rate maps, incorporating variable outflow density and velocity. We compare the instantaneous values with time-averaged outflow rates by placing mock fibres and slits on the MUSE field-of-view, a method often used in the literature. The instantaneous outflow rates (0.2-275 $M_{\odot}$ yr$^{-1}$) tend to be 2 orders of magnitude higher than the time-averaged outflow rates (0.001-40 $M_{\odot}$ yr$^{-1}$). The outflow rates correlate with the AGN bolometric luminosity ($L_{\rm bol}\sim$ 10$^{42.71}$-10$^{45.62}$ erg/s) but we find no correlations with black hole mass (10$^{6.1}$-10$^{8.9}$ M$_{\odot}$), Eddington ratio (0.002-1.1) and radio luminosity (10$^{21}$-10$^{26}$ W/Hz). We find the median coupling between the kinetic energy and $L_{\rm bol}$ to be 1%, consistent with the theoretical predictions for an AGN-driven outflow., Comment: Main paper: 20 pages, 15 figures, 3 tables. Accepted for publication in MNRAS

Over the years, population protocols with the goal of reaching consensus have been studied in great depth. However, many systems in the real-world do not result in all agents eventually reaching consensus, but rather in the opposite: they converge to a state of rich diversity. Consider for example task allocation in ants. If eventually all ants perform the same task, then the colony will perish (lack of food, no brood care, etc.). Then, it is vital for the survival of the colony to have a diverse set of tasks and enough ants working on each task. What complicates matters is that ants need to switch tasks periodically to adjust the needs of the colony; e.g., when too many foragers fell victim to other ant colonies. Moreover, all tasks are equally important and maybe they need to keep certain proportions in the distribution of the task. How can ants keep a healthy and balanced allocation of tasks? To answer this question, we propose a simple population protocol for $n$ agents on a complete graph and an arbitrary initial distribution of $k$ colours (tasks). We assume that each colour $i$ has an associated weight (importance) $w_i \geq 1$. By denoting $w$ as the sum of the weights of different colours, we show that the protocol converges in $O(w^2 n \log n)$ rounds to a configuration where the number of agents supporting each colour $i$ is concentrated on the fair share $w_in/w$ and will stay concentrated for a large number of rounds, w.h.p. Our protocol has many interesting properties: agents do not need to know other colours and weights in the system, and our protocol requires very little memory per agent. Furthermore, the protocol guarantees fairness meaning that over a long period each agent has each colour roughly a number of times proportional to the weight of the colour. Finally, our protocol also fulfils sustainability meaning that no colour ever vanishes.

We characterized the kinematics, morphology, and stellar population (SP) properties of a sample of massive compact quiescent galaxies (MCGs, $10 \lesssim \log M_\star$/$M_\odot \lesssim 11$ and $r_{\rm e} \sim 1-3 $kpc) in the MaNGA Survey, with the goal of constraining their formation, assembly history and assessing their relation with non-compact quiescent galaxies. We compared their properties with those of a control sample of median-sized quiescent galaxies ($r_{\rm e} \sim 4-8 $kpc) with similar effective velocity dispersions. MCGs have elevated rotational support, as evidenced by a strong anti-correlation between the Gauss-Hermite moment $h_3$ and $V/\sigma$. In contrast, 30$\%$ of control sample galaxies (CSGs) are slow rotators, and fast-rotating CSGs generally show a weak $h_3-V/\sigma$ anti-correlation. MCGs and CSGs have similar ages, but MCGs are more metal-rich and $\alpha$-enhanced. Both MCGs and CSGs have shallow negative metallicity gradients and flat [$\alpha$/Fe] gradients. On average, MCGs and CSGs have flat age gradients, but CSGs have a significantly larger dispersion of gradient values. The kinematics and SP properties of MCGs suggest that they experienced highly-dissipative gas-rich events, such as mergers, followed by an intense, short, and centrally concentrated burst of star formation, between 4 to 10 Gyr ago ($z\sim0.4-2$), and had a quiet accretion history since then. This sequence of events might be analogous to, although less extreme than, the compaction events which formed compact quiescent galaxies at $z \sim 2$. The small sizes of MCGs, and the high efficiency and short duration of their last star formation episode suggest that they are descendants of compact post-starburst galaxies., Comment: 19 pages, 18 figures (not including appendices). Accepted for publication in the Monthly Notices of the Royal Astronomical Society