Noticias en español
Almost sure convergence in evolutionary models with vanishing mutations.
Abstract: We analyze the long-term behavior of evolutionary models where mutations gradually vanish over time. Our focus is on the almost sure convergence of the empirical occupation measure—that is, the time-averaged distribution of states—as the mutation parameter decays in a controlled manner. Under suitable conditions, we prove that this measure converges almost surely to a specific invariant distribution of a limiting Markov chain, while also establishing explicit convergence rates. Our analysis is carried out within a class of time-inhomogeneous Markov chains on a finite state space,...
Read MoreDeterministic Impartial Selection with Weights.
Abstract: In the impartial selection problem, a subset of agents up to a fixed size k among a group of n is to be chosen based on votes cast by the agents themselves. A selection mechanism is impartial if no agent can influence its own chance of being selected by changing its vote. It is \alpha-optimal if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of \alpha of the votes received by the subset of size k with the highest number of votes. We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted...
Read MoreOn the complexity of the CSP.
Abstract: The Constraint Satisfaction Problem (CSP) is defined as follows: we are given a set of variables, a set of values, and a set of constraints, where each constraint restricts the combination of values that certain tuple of variables can take. The question is whether there exists an assignment of values to the variables that satisfies all the constraints. The CSP is a well-known NP-complete problem, and hence much research has been done to identify restrictions of this problem that can be solved in polynomial time. In this talk, we focus on the so-called structural restrictions, that...
Read MorePrice of Anarchy in Algorithmic Matching of Romantic Partners.
Abstract: Algorithmic matching is a pervasive mechanism in our social lives and is becoming a major medium through which people find romantic partners and potential spouses. However, romantic matching markets pose a principal-agent problem with the potential for moral hazard. The agent’s (or system’s) interest is to maximize the use of the matching website, while the principal’s (or user’s) interest is to find the best possible match. This creates a conflict of interest: the optimal matching of users may not be aligned with the platform’s goal of maximizing engagement, as it could lead to...
Read MoreMean-Field Opinion Dynamics in Random Graphs.
Abstract: We consider a set of agents in a network having different opinions over a binary subject. The network is encoded as a (undirected or directed) graph, and each opinion is represented as a value between 0 and 1. At each discrete stage, each agent updates her opinion as a convex combination between the average opinion of her neighbors and her intrinsic opinion, which coincides with its initial opinion. It is well known that such dynamic converges to a stable opinion, which can be computed by inverting a matrix associated with the adjacency matrix of the network. When the network...
Read MoreRobust Admission via Two-Stage Stable Matching under Ranking Uncertainty.
Abstract: The Bachillerato Inicia UC program offers a pathway for students from Chilean technical high schools to articulate into undergraduate programs at Pontificia Universidad Católica de Chile. Upon applying, candidates rank up to three preferred programs. However, articulation is determined only after one year, based on their academic ranking within the cohort – a value unknown at the time of admission. This setting gives rise to a two-stage admission problem with downstream matching constraints and exogenous uncertainty. The challenge is to select a feasible subset of students...
Read More