Noticias en español
Efficiency and fairness in random resource allocation and social choice.
Abstract: We study efficiency in general collective choice problems when agents have ordinal preferences, and randomization is allowed. We establish the equivalence between welfare maximization and ex-ante efficiency for general domains, and relate ex-ante efficiency with ex-post efficiency, characterizing when the two notions coincide. We also propose a new general notion of fairness that is applicable in any social choice environment, not only in resource allocation. Our results have implications for well-studied mechanisms including random serial dictatorship and a number of specific...
Read MoreSemi-random process.
Abstract: The semi-random graph process is a single-player game that begins with an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. During the talk, we will focus on the following problems: a) perfect matchings, b) Hamilton cycles, c) constructing a subgraph isomorphic to an...
Read MorePercolation on dense random graphs with given degrees.
Abstract: We study the order of the largest connected component of a random graph having two sources of randomness: first, the graph is chosen randomly from all graphs with a given degree sequence, and then bond percolation is applied. Far from being able to classify all such degree sequences, we exhibit several new threshold phenomena for the order of the largest component in terms of both sources of randomness. We also provide an example of a degree sequence, for which the order of the largest component undergoes an unbounded number of jumps in terms of the percolation parameter, giving...
Read MoreA PTAS for Unsplittable Flow on a Path.
Abstract: In the Unsplittable Flow on a Path problem (UFP) we are given a path with edge capacities, and a set of tasks where each task is characterized by a subpath, a demand, and a weight. The goal is to select a subset of tasks of maximum total weight such that the total demand of the selected tasks using each edge e is at most the capacity of e. The problem admits a QPTAS [Bansal, Chakrabarti, Epstein, Schieber, STOC’06; Batra, Garg, Kumar, Mömke, Wiese, SODA’15]. After a long sequence of improvements [Bansal, Friggstad, Khandekar, Salavatipour, SODA’09; Bonsma, Schulz,...
Read MoreHow to split the costs and charge the travellers sharing a ride? aligning system’s optimum with users’ equilibrium.
Abstract: Emerging on-demand sharing alternatives, in which one resource is utilised simultaneously by a circumstantial group of users, entail several challenges regarding how to coordinate such users. A very relevant case refers to how to form groups in a mobility system that offers shared rides, and how to split the costs within the travellers of a group. These are non-trivial tasks, as two objectives conflict: 1) minimising the total costs of the system, and 2) finding an equilibrium where each user is content with her assignment. Aligning both objectives is challenging, as users are not...
Read MoreNash Flows over Time: Uniqueness, Continuity and Long-term behavior.
Abstract: In the talk, we consider a dynamic model of traffic that has received a lot of attention in the past few years, Nash Flows over time. Users control infinitesimal flow particles aiming to travel from a source to destination as quickly as possible. Flow patterns vary over time, and congestion effects are modeled via queues, which form whenever the inflow into a link exceeds its capacity. We will see that assuming constant inflow into the network at the source, equilibria always settle down into a “steady state” in which the behavior extends forever in a linear fashion....
Read More