Noticias en español
Mean-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 MoreAnalyzing the (k-)swap neighborhood for makespan scheduling.
Abstract: Analyzing the behavior of local search methods has received considerable attention over the last two decades. One interesting question is how the simplest form of local search, i.e., iterative improvement, behaves w.r.t. a certain neighborhood both in quality of the solution as well as number of iterations needed to obtain a local optimal solution. In this talk, we consider the basic scheduling problem in which n jobs need to be scheduled on m identical machines so as to minimize the makespan, i.e., the completion time of the last job. Finn and Horowitz (1979) showed that the...
Read MoreSampling tree-weighted balanced graph partitions in polynomial time.
Abstract: When judging the fairness of a political redistricting map, it is useful to be able to generate a large ensemble of “random” alternative maps. Formally, this is a graph partitioning problem. The objective is to output random partitions of the vertex set into k equal-sized pieces inducing connected subgraphs. Numerous algorithms have been developed to sample either exactly or approximately from the so-called “spanning tree distribution,” where each partition is weighted by the product of the numbers of spanning trees in each part. However, none of these...
Read MoreGenerative Social Choice
The mathematical study of voting, social choice theory, has traditionally only been applicable to choices among a few predetermined alternatives, but not to open-ended decisions such as collectively selecting a textual statement. We introduce generative social choice, a design methodology for open-ended democratic processes that combines the rigor of social choice theory with the capability of large language models to generate text and extrapolate preferences. Our framework divides the design of AI-augmented democratic processes into two components: first, proving that the process satisfies...
Read MoreTruthful Budget Aggregation: Beyond Moving-Phantom Mechanisms.
Abstract: We study a budget-aggregation setting in which a number of voters report their ideal distribution of a budget over a set of alternatives, and a mechanism aggregates these reports into an allocation. Ideally, such mechanisms are truthful, i.e., voters should not be incentivized to misreport their preferences. For the case of two alternatives, the set of mechanisms that are truthful and additionally meet a range of basic desiderata (anonymity, neutrality, and continuity) exactly coincides with the so-called moving-phantom mechanisms, but whether this space is richer for more...
Read More