Noticias en español
Selfish Learners in Queueing Systems with Small Buffers.
Abstract: Algorithmic Game Theory has provided a good understanding of the impact of strategic behavior on outcomes in many one-shot games, including traffic routing and online auctions. This has been extended to repeated games under the assumption players use some form of (no-regret) learning. However, in many real-life scenarios, rounds are not repetitive and may involve carryover effects from one round to the next. This is the case of budgeted auctions and queuing systems. In this talk, we analyze a queueing system modeling packet routing in data centers. Routers compete for getting...
Read MoreImproveApproximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
Abstract: The Forest Augmentation Problem (FAP) asks for a minimum set of additional edges (links) that make a given forest 2-edge-connected while spanning all vertices. A key special case is the Path Augmentation Problem (PAP), where the input forest consists of vertex-disjoint paths. Grandoni, Jabal Ameli, and Traub [STOC’22] recently broke the long-standing 2-approximation barrier for FAP, achieving a 1.9973-approximation. A crucial component of this result was their 1.9913-approximation for PAP; the first better-than-2 approximation for PAP. In this work, we improve these results...
Read MoreAlmost 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 More