In this paper, we study the dynamics of the susceptible-infected-recovered (SIR) model on a network with community structure, namely the stochastic block model (SBM). As usual, the SIR model is a stochastic model for an epidemic where infected vertices infect susceptible neighbors at some rate η, and recover at rate γ, and the SBM is a random graph model where vertices are partitioned into a finite number of communities. The connection probability between two vertices depends on their community affiliation, here scaled so that the average degrees have a finite limit as the network grows.
We prove laws of large numbers (LLN) for the epidemic’s trajectory to a system of ordinary differential equations over any time horizon (finite or infinite), including in particular a LLN for the final size of the infection.
Our proofs rely on two main ingredients: (i) a new coupling of the SIR epidemic and the randomness of the SBM, revealing a vector-valued random variable that drives the epidemic (related to what is usually called the “force of the infection” via a linear transformation), and (ii) a novel technique for analyzing the limiting behavior of the infinite time horizon for the infection, using the fact that once the infection passes the herd immunity threshold it dies out quickly and has a negligible impact on the overall size of the infection.
conference
EAAMO
Disincentivizing Filter Bubbles in Social Networks
On social networks, algorithmic personalization drives users into filter bubbles where they rarely see content that deviates from their interests. We present a model for content curation and personalization that avoids filter bubbles, along with algorithmic guarantees and nearly matching lower bounds. In our model, the platform interacts with n users over T timesteps, choosing content for each user from k categories. The platform receives stochastic rewards as in a multi-arm bandit. To avoid filter bubbles, we draw on the intuition that if some users are shown some category of content, then all users should see at least a small amount of that content. We first analyze a naive formalization of this intuition and show it has unintended consequences: it leads to “tyranny of the majority” with the burden of diversification borne disproportionately by those with minority interests. This leads us to our model which distributes this burden more equitably. We require that the probability any user is shown a particular type of content is at least γtimes the average probability all users are shown that type of content. Full personalization corresponds to γ= 0 and complete homogenization corresponds to γ= 1; hence, γencodes a hard cap on the level of personalization. We also analyze additional formulations where the platform can exceed its cap but pays a penalty proportional to its constraint violation. We provide algorithmic guarantees for optimizing recommendations subject to these constraints. These include nearly matching upper and lower bounds for the entire range of γ∈[0,1] showing that the cumulative reward of a multi-agent variant of the Upper-Confidence-Bound algorithm is nearly optimal. Using real-world preference data, we empirically verify that under our model, users share the burden of diversification and experience only minor utility loss when recommended more diversified content.
@inproceedings{bciv23a,title={Disincentivizing Filter Bubbles in Social Networks},author={Borgs, Christian and Chayes, Jennifer and Ikeokwu, Christian and Vitercik, Ellen},booktitle={ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization},year={2023},}
Rotating savings and credit associations (roscas) are informal financial organizations common in settings where communities have reduced access to formal financial institutions. In a rosca, a fixed group of participants regularly contribute sums of money to a pot. This pot is then allocated periodically using lottery, aftermarket, or auction mechanisms. Roscas are empirically well-studied in economics. They are, however, challenging to study theoretically due to their dynamic nature. Typical economic analyses of roscas stop at coarse ordinal welfare comparisons to other credit allocation mechanisms, leaving much of roscas’ ubiquity unexplained. In this work, we take an algorithmic perspective on the study of roscas. Building on techniques from the price of anarchy literature, we present worst-case welfare approximation guarantees. We further experimentally compare the welfare of outcomes as key features of the environment vary. These cardinal welfare analyses further rationalize the prevalence of roscas. We conclude by discussing several other promising avenues
@inproceedings{aeit22,title={An Algorithmic Introduction to Savings Circles},author={Abebe, Rediet and Eck, Adam and Ikeokwu, Christian and Taggart, Samuel},booktitle={Proceedings of the AAAI Conference on Artificial Intelligence},volume={36},number={5},pages={4744--4751},year={2022},}
thesis
The Mathematics of Mutual Aid: Robust Welfare Guarantees for Decentralized Financial Organizations
Christian Ikeokwu
Oberlin College Computer Science Honors Program, 2021
The Mathematics of Mutual Aid: Robust Welfare Guarantees for Decentralized Financial OrganizationsOberlin College Computer Science Honors Program, 2021