Noticias en español
Sampling 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 MoreTwo-Edge Connectivity via Pac-Man Gluing.
Abstract: We study the 2-edge-connected spanning subgraph (2-ECSS) problem: Given a graph G, compute a connected subgraph H of G with the minimum number of edges such that H is spanning, i.e., V(H) = V(G), and H is 2-edge-connected, i.e., H remains connected upon the deletion of any single edge, if such an H exists. The 2-ECSS problem is known to be NP-hard. In this work, we provide a polynomial-time (5/4 + epsilon)-approximation for the problem for an arbitrarily small epsilon>0, improving the previous best approximation ratio of 13/10 + epsilon. Our improvement is based on two main...
Read MoreThe Burial of Coupling Constraints in Linear Bilevel Optimization.
Abstract: It has been common sense in (linear) bilevel optimization that problems with coupling constraints are more difficult to tackle than those without such constraints. While the modeling capabilities in terms of the feasible sets are indeed richer because coupling constraints allow to model disconnected feasible sets, complexity theory did not see any difference between problems with our without coupling constraints. In this talk, we show that there is no difference at all when one considers optimal solutions instead of just feasible points. For the case of optimistic bilevel...
Read MoreColour-bias perfect matchings in hypergraphs.
Abstract: We study conditions under which an r-edge-coloured k-uniform hypergraph has a perfect matching that contains substantially more than n/(kr) monochromatic edges. Our main result solves this problem for perfect matchings under minimum degree conditions, which answers recent questions of Gishboliner, Glock and Sgueglia. This is joint work with Hiêp Hàn, Richard Lang, João Pedro Marciano, Matías Pavez-Signé, Andrew Treglown, and Camila Zárate-Guerén.
Read More