AGCO Seminar

Abstract: 

We study the SIRS process---a continuous-time Markov chain modelling the

spread of infections on graphs. In this model, vertices are either

susceptible, infected, or recovered. Each infected vertex becomes

recovered at rate 1 and infects each of its susceptible neighbors

independently at rate~$\lambda$, and each recovered vertex becomes

susceptible at a rate~$\rho$, which we assume to be independent of the

graph size. A central quantity of the SIRS process is the time until no

vertex is infected, known as the survival time. Surprisingly though, to

the best of our knowledge, all known rigorous theoretical results that

exist so far immediately carry over from the related SIS model and do

not completely explain the behaviour of the SIRS process.

We address this imbalance by conducting theoretical analyses of the SIRS

process via the expansion properties of the underlying graph.

Our first result shows that the expected survival time of the SIRS

process on stars is at most polynomial in the graph size for any value

of~$\lambda$. This behaviour is fundamentally different from the SIS

process, where the expected survival time is exponential already for

small infection rates. This raises the question of which graph

properties result in an exponential survival time. Our main result is an

exponential lower bound of the expected survival time of the SIRS

process on expander graphs. Specifically, we show that on expander

graphs $G$ with $n$ vertices, degree close to $d$, and sufficiently

small spectral expansion, the SIRS process has expected survival time at

least exponential in $n$ when $\lambda \geq c/d$ for a constant $c > 1$.

Previous results on the SIS process show that this bound is almost

tight. Additionally, our result holds even if $G$ is a subgraph.

Notably, our result implies an almost-tight threshold for Erdos–Rényi

graphs and a regime of exponential survival time for complex network

models. The proof of our main result draws inspiration from Lyapunov

functions used in mean-field theory to devise a two-dimensional

potential function and from applying a negative-drift theorem to show

that the expected survival time is exponential.

This is joint work with Tobias Friedrich, Nicolas Klodt, Martin Krejca

and Marcus Pappik.

Abstract: 

Assignment problems are among the most well-studied in online algorithms. In these problems, a sequence of items arriving online must be assigned among a set of agents so as to optimize a given objective. This encompasses scheduling problems for minimizing makespan, p-norms, and other objectives, as well as fair division problems such as the Santa Claus problem and Nash welfare maximization. One common feature is that many of these problems are characterized by strong worst-case lower bounds in the online setting. To circumvent these impossibility results, recent research has focused on using additional (learned) information about the problem instance and this has led to dramatic improvements in the competitive ratio over the worst case. In this talk, I will first survey some of this literature (Lattanzi et al., SODA 20; Li and Xian, ICML 21; Banerjee et al., SODA 22; Barman et al., AAAI 22) that addresses specific problems in this domain. I will then proceed to describe recent work with Ilan Cohen that brings these problems under one umbrella: we give a single algorithmic framework  for learning-augmented online assignment for a large class of maximization and minimization objectives. 

Abstract: 

This talk considers a game where an inspection authority must verify that a set of operators adhere to a certain rule. The inspector has time to inspect only a few operators, and this must be done sequentially. The operators disclose the sequence of inspections as they occur.

We will discuss variants of this sequential game. The talk focuses on the mathematical structure of the set of equilibria of this inspection game, where the inspector is a Stackelberg leader and is capable of performing exactly two inspections. A static and dynamic version of the game are analyzed. In the static game, the inspection paths are the solutions to a transportation problem. This equivalence is then used to determine an explicit solution. We discuss how the static and dynamic games relate to each other. In particular, we show they lead to the same utility value for the inspector.

Most of the contents of this talk is based on joint work with Cristóbal Guzmán, Javiera Riffo, and Mathieu Van Vyve and was published at EJOR.

Abstract: 

 Alternatives to recurrent neural networks, in particular, architectures based on self-attention, are gaining momentum for processing input sequences. In spite of their relevance, the computational properties of such networks have not yet been fully explored. We study the computational power of the Transformer, one of the most paradigmatic architectures exemplifying self-attention. We show that the Transformer with hard-attention is Turing complete exclusively based on their capacity to compute and access internal dense representations of the data. Our study also reveals some minimal sets of elements needed to obtain this completeness result.

Abstract: 

In a prophet inequality problem, n independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent value as a reward. We evaluate a stopping rule by the worst-case ratio between its expected reward and the expectation of the maximum variable. Because of its connections with resource allocation and posted-price mechanisms, this problem has been intensively studied, and several variants have been introduced. While most of the literature assumes that distributions are known to the gambler, recent work has considered the question of what is achievable when the gambler has access only to a few samples per distribution. We provide a unified proof that for all three major variants of the single-selection problem (i.i.d, random-order, and free-order), a constant number of samples (independent of n) for each distribution is good enough to approximate the optimal ratios. Prior to our work, this was known to be the case only in the i.i.d. variant. 

Previous works relied on explicitly constructing sample-based algorithms that match the best possible ratio. Remarkably, the optimal ratios for the random-order and the free-order variants with full information are still unknown. Consequently, our result requires a significantly different approach than for the classic problem and the i.i.d. variant, where the optimal ratios and the algorithms that achieve them are known. A key ingredient in our proof is an existential result based on a minimax argument, which states that there must exist an algorithm that attains the optimal ratio and does not rely on the knowledge of the upper tail of the distributions.

Based on joint work with Bruno Ziliotto that will appear in STOC'24.

Abstract: 

Imagine a group of people that need each day to make some collective decision (for the entire group), choosing one of two options A and B. Some people prefer A, some prefer B, and others are OK with any of the two options. (The next day the preferences may change arbitrarily, and a new group choice is made.) The group management needs to choose A or B, in both cases making some people unhappy. This cannot be avoided completely (if someone wants A and someone else wants B, one of them will be unhappy), so the goal is more modest: each person should not be unhappy too many times.

Even this modest goal may be hard to achieve: if one person always wants A, and another person always wants B, then one of them will be unhappy at least T/2 times during a T-day period. To ensure that this kind of obstacle does not appear, let us make an additional assumption. We say that two people are in a conflict at some day d if one of them wants A, and the other one wants B. (The people that are OK with both options do not conflict with anyone.) The additional assumption: for every pair of people there is O(1) days  where they are in a conflict.

We show that there exists a strategy which makes every person unhappy at most sqrt{T} * polylog(N) times, where N is the size of the group. This bound is optimal, but our proof is very strange and somehow follows from inequalities about Kolmogorov complexity. In particular, it does not give an efficient explicit strategy. Kolmogorov complexity is often used as a tool to prove combinatorial results but, in most cases, one can reformulate the argument in terms of counting, or probabilities, or Shannon entropies, or at least find an alternative purely combinatorial argument. We do not know how to do this in this case. So far, using a combinatorial argument, we only obtained a worse bound T^{2/3} * polylog(N) by analyzing the multiplicative weight algorithm.

Joint with Alexander Shen and Tomasz Steifer

Abstract: 

In the Tariff Zone Assignment problem, an operator is tasked with partitioning a transport network (i.e., a graph) into tariff zones in order to maximize revenue under a linear pricing model. In this model, customers pay a price proportional to the number of zones traveled through, up to some maximum accepted price. If this price gets exceeded, customers drop out of the model and thus generate no revenue at all.

In this talk, first we will look at the complexity of this problem and show APX-hardness on star graphs and strong NP-hardness on paths. These complexity results motivate the introduction of a variant of the problem, which we will show to be polynomial time solvable when restricted to paths. Finally, we will discuss an integer programming approach to the original formulation of the problem.

This is joint, ongoing work with Lennart Kauther, Sven Müller and Britta Peis.

Abstract: 

In this talk, I’ll introduce the thresholded linear bandit problem, a novel sequential decision making problem at the interface of structured stochastic multi-armed bandits and learning halfspaces. In this problem, the set of arms is [0, 1]^d, the arms follow an unknown linear utility model, and the Bernoulli revenue of an arm has a success probability based on an unknown thresholding of the utility. Arms are also associated with a known linear cost. The goal of a learning algorithm is to sequentially play arms so as to maximize cumulative reward. This problem is motivated by several practical applications. For instance, imagine tuning the continuous features of an offer to a consumer; higher values incur higher cost to the vendor but result in a more attractive offer. At some threshold, the offer is attractive enough for a random consumer to accept at the higher probability level. Another motivation is selling perishable goods of tunable quality to consumers, some of whom have an outside option. For the one-dimensional case, I’ll present Leftist, which enjoys $\log^2 T$ problem-dependent regret in favorable cases and has $\log(T) \sqrt{T}$ worst-case regret; I'll also give a lower bound suggesting this is unimprovable. I’ll then sketch MD-Leftist, our algorithm for the multi-dimensional case. This algorithm obtains similar regret bounds but with $d^2 \log d$ and $d^{1.5} \log d$ dependence on dimension for the two types of bounds respectively. This work was presented at AISTATS 2023 and is joint with Junpei Komiyama, Vamsi Potluru, Andrea Nguyen, and Mica Grant-Hagen.

Abstract: 

In the top-1-of-k prophet inequality setting, a gambler is given a sequence of n random variables X_1, ..., X_n, taken from known distributions, observes their values in an adversarial order, and selects up to k of them, immediately after they are observed, so that the top value selected is as high as possible, comparing against a prophet who always selects the maximum realization. For k = 1, one recovers the classical prophet inequality, and thus this model serves as a generalization.

In this talk, we look at a new approach to solve the top-1-of-k model. We generalize the standard prophet inequality for k = 1, allowing the gambler some additional information about the future that is otherwise privy only to the prophet. Specifically, at any point in the process, the gambler is allowed to query an oracle O. The oracle responds with a single bit answer: YES, if the current realization is the largest of the remaining realizations, and NO otherwise. We show that the oracle model with k oracle calls is equivalent to the top-1-of-(k+1) model when the objective is maximizing the probability of selecting the maximum. This equivalence fails to hold when the objective is maximizing the competitive ratio, but we still show that any algorithm for the oracle model implies an equivalent competitive ratio for the top-1-of-(k+1) model.

We resolve the oracle model for any k, giving almost tight lower and upper bound on the best possible competitive ratio compared to an almighty adversary. As a consequence, we provide new results as well as improvements on known results for the top-1-of-(k+1) model.

Abstract: 

In this talk, I will give an introduction to linear programming hierarchies, with a particular focus on the hierarchy by Sherali & Adams. I will discuss some limitations of the tool, but also ways to get useful and stronger relaxations.

Abstract: 

Machine learning (ML), particularly deep learning, is being used everywhere. However, not always is used well, ethically and scientifically. In this talk we first do a deep dive in the limitations of supervised ML and data, its key component. We cover small data, datification, bias, predictive optimization issues, evaluating success instead of harm, and pseudoscience, among other problems.  The second part is about our own limitations using ML, including different types of human incompetence: cognitive biases, unethical applications, no administrative competence, copyright violations, misinformation, and the impact on mental health. In the final part we discuss regulation on the use of AI and responsible AI principles, that can mitigate the problems outlined above.

Short Bio: 

Ricardo Baeza-Yates is Director of Research at the Institute for Experiential AI of Northeastern University, as well as part-time professor at the Dept. of Computer Science of University of Chile. Before, he was VP of Research at Yahoo Labs, based in Barcelona, Spain, and later in Sunnyvale, California, from 2006 to 2016. He is co-author of the best-seller Modern Information Retrieval textbook published by Addison-Wesley in 1999 and 2011 (2nd ed), that won the ASIST 2012 Book of the Year award. From 2002 to 2004 he was elected to the Board of Governors of the IEEE Computer Society and between 2012 and 2016 was elected for the ACM Council. In 2009 he was named ACM Fellow and in 2011 IEEE Fellow, among other awards and distinctions. He obtained a Ph.D. in CS from the University of Waterloo, Canada, and his areas of expertise are responsible AI, web search and data mining plus data science and algorithms in general.

Abstract: 

A binary classification game is being played between a learner and an adversary. At each round, the adversary selects a natural number x and the learner has to predict its label h(x). Is there a bound on the number of mistakes made by the learner, assuming that h comes from some class H? Littlestone gave a learning algorithm which achieves an optimal mistake bound d, provided H has a certain combinatorial property. However, Littlestone's algorithm is believed to be computationally demanding. Can we have a feasible strategy for the learner and if so, how many mistakes would it make? I will introduce such a strategy, which is fast (for finite classes) and achieves an exponential (in d) mistake bound. The algorithm was devised together with Sasha Kozachinskiy.

Abstract: 

We study the problem of selecting screening policies for a given disease in a large population which is divided into risk groups, and where we have a measure of benefit and cost for each possible policy. We want to find a selection of them, one for each risk group so that the total benefit is maximized and a budget constraint per time period is satisfied.

To that end we start from an individual base model that accounts for the probabilistic appearance and evolution of the disease along stages. Our main result is an ergodic-like theorem which allows us to calculate the expected costs and benefits for each policy. This result is applicable to a rich class of individual models (discrete and continuous-time semi-Markov processes) currently used in the literature.

The presentation is grounded in the application to cancer screening, but can be extended to other non-contagious diseases. We wil show examples of some individual models and how our methodology allows for the efficient evaluation and optimization of large families of policies. If time permits we will also discuss the relation between our methodology and some other approaches (Markov decision processes, flowgraph models), and some future work.

Abstract: 

Auction games are a central application of game theory in economics. However, while explicit formulas for Bayes-Nash equilibria are known for particular auction settings, we generally have to rely on numerical methods to predict the outcomes of auctions. We present a simple class of learning algorithms to approximate Bayes-Nash equilibria in these games. Surprisingly, while recent theoretical results suggest that such algorithms perform poorly in general matrix games, we provide experimental evidence that they perform very well in many different auction scenarios.

Despite the positive experimental results, proving the convergence of these algorithms remains an open problem - even in very basic settings. We provide some insights and known preliminary results towards answering this question.

Abstract: 

Care Management Programs (CMPs) coordinate the care for patients with complex care needs and older frail adults, who usually represent the top of healthcare spending. Although CMPs have appeared as credible avenues for reducing healthcare utilization, empirical evidence showed mixed results. Using patient-level data we evaluate the causal impact of the CMP of a major academic medical center, and we find no impact on five healthcare utilization measures. In the light of these negative results, one wonders how can CMPs be improved. To address this question, we use Markov Decision Processes (MDPs) and Dynamic Programming to model the task of optimally allocating treatment amongst patients while fulfilling some capacity constraints. The complexity of such a problem may be very high because healthcare populations may be large enough that gathering information of the current status of each patient and tracking the evolution of their covariates is untenable. To address this challenge we develop the so-called measurized theory, which allows to model MDPs that optimize the distribution of treated and untreated patients instead of dealing with identifed patients. This abstraction transforms a complicated problem into an intuitive formulation and sets the stage for delivering clinically implementable solutions in the future.

Abstract: 

In 1971, Balas introduced the intersection cut framework as a method for generating separating hyperplanes (or "cuts") in integer optimization. These cuts are derived from convex S-free sets, and inclusion-wise maximal S-free sets yield the strongest intersection cuts. When S is a lattice, maximal S-free sets are well-studied from theoretical and computational standpoints. In this talk, we focus on the case when S is defined by a non-convex quadratic inequality and show how to construct basic maximal quadratic-free sets. Additionally, we explore how to generalize the basic procedure to construct a plethora of new maximal quadratic-free sets for homogeneous quadratics. Joint work with Antonia Chmiela, Joseph Paat, and Felipe Serrano.

Abstract: 

Discrete optimization problems are often solved using constraint programming or mided-integer programming techniques, using enumeration or branch-and-bound techniques. It is well known that if the problem formulation is very symmetric,  there may exist many symmetrically equivalent solutions to the problem. Without handling the symmetries, traditional solving methods have have to check many symmetric parts of the solution space, which comes at a high computational cost.

Handling symmetries in optimization problems is thus essential for devising efficient solution methods. In this presentation, we present a general framework that captures many of the already existing symmetry handling methods. While these methods are mostly discussed independently from each other, our framework allows to apply different symmetry handling methods simultaneously and thus outperform their individual effects. Moreover, most existing symmetry handling methods only apply to binary variables. Our framework allows to easily generalize these methods to general variable types. Numerical experiments confirm that our novel framework is superior to the state-of-the-art methods implemented in the solver SCIP.

Abstract: 

In load balancing scheduling problems n jobs are to be assigned to m machines. Each job has its own processing time, and we define the load of a machine as the sum of the processing time of all jobs assigned to it.

In this work, the machines have a concave non-decreasing function (accessed through a value oracle) applied to their loads and our goal is to maximize the sum of these valuations.

This setting models a productivity maximization of machines where we aim to allocate indivisible resources, such as fuel tanks.

We prove the existence of a PTAS for the offline version, which is the best possible as the underlying decision problem is strongly NP-hard.

We also explore the online version, where jobs arrive one by one revealing their processing time and must be allocated immediately. We first show that the List Scheduling greedy algorithm is 3/4-competitive in adversarial order. Additionally, we provide an upper bound of ≈ 0.809 (ϕ/2 where ϕ is the golden ratio) for the competitive ratio of any algorithm in this context. For the special case of only two machines, we present an algorithm that matches the given upper bound.

This is joint work with José Soto.

Abstract: 

Motivated by hiring pipelines, we study three selection and ordering problems in which applicants for a finite set of positions must be interviewed or made offers to. There is a finite time budget for interviewing or making offers, and a stochastic realization after each decision, leading to computationally-challenging problems. In the first problem, we study sequential interviewing and show that a computationally-tractable, non-adaptive policy that must make offers immediately after interviewing is near-optimal, assuming offerees always accept their offers. In the second problem, we assume that applicants have already been interviewed but only accept offers with some probability; we develop a computationally-tractable policy that makes offers for the different positions in parallel, which can be used even if positions are heterogeneous and is approximately optimal relative to a policy that can make the same amount of offers not in parallel. In the third problem, we introduce a model where the hiring firm is tightly time constrained and must send all offers simultaneously in a single time step, with the possibility of hiring over capacity at a cost; we provide nearly-tight bounds for the performance of practically motivated value-ordered policies. All in all, our paper takes a unified approach to three different hiring problems, based on linear programming.  Our results in the first two problems generalize and improve the existing guarantees in the literature that were between 1/8 and 1/2 to new guarantees that are at least 1-1/e ≈ 63.2%.

Abstract: 

This seminar introduces Partially Observable Markov Decision Processes (POMDPs), emphasizing their relationship with decision problems and decidability. We then explore a novel theoretical class of POMDPs based on a weak ergodicity property. The seminar concludes by identifying necessary conditions for POMDPs to exhibit this characteristic, bridging the gap between this theoretical result and its potential practical implementation.

Abstract: 

We study the design of energy-efficient algorithms for well known distributed models of computation: the LOCAL and CONGEST models. Specifically, as a measure of complexity, we consider the maximum, taken over all the edges, or over all the nodes, of the number of rounds at which an edge, or a node, is activein the algorithm. We first show that every Turing-computable problem has a CONGEST algorithm with constant node-activation complexity, and therefore constant edge-activation complexity as well. That is, every node (resp., edge) is active in sending (resp., transmitting) messages for only O(1) rounds during the whole execution of the algorithm. In other words, every Turing-computable problem can be solved by an algorithm consuming the least possible energy. In the LOCAL model, the same holds obviously, but with the additional feature that the algorithm runs in O(poly(n)) rounds in n-node networks. However, we show that insisting on algorithms running in O(poly(n)) rounds in the CONGEST model comes with a severe cost in terms of energy. Namely, there are problems requiring Ω(poly(n)) edge-activations (and thus Ω(poly(n)) node-activations as well) in the CONGEST model whenever solved by algorithms bounded to run in O(poly(n)) rounds. Finally, we demonstrate the existence of a sharp separation between the edge-activation complexity and the node-activation complexity in the CONGEST model, for algorithms bounded to run in O(poly(n)) rounds. Specifically, under this constraint, there is a problem with O(1) edge-activation complexity but Ω(n1/4) node-activation complexity.

(Joint work with Pierre Fraignuiaud, Pedro Montealegre and Ian Todinca)

Abstract: 

Apportionment is the problem of distributing h indivisible seats across states in proportion to the states' populations. In the context of the US House of Representatives, this problem has a rich history and is a prime example of interactions between mathematical analysis and political practice. Grimmett suggested to apportion seats in a randomized way such that each state receives exactly their proportional share qᵢ of seats in expectation (ex ante proportionality) and receives either ⌊qᵢ⌋ or ⌈qᵢ⌉ many seats ex post (quota). However, there is a vast space of randomized apportionment methods satisfying these two axioms, and so we additionally consider prominent axioms from the apportionment literature. Our main result is a randomized method satisfying quota, ex ante proportionality and house monotonicity — a property that prevents paradoxes when the number of seats changes and which we require to hold ex post. This result is based on a generalization of dependent rounding on bipartite graphs, which we call cumulative rounding and which might be of independent interest, as we demonstrate via applications beyond apportionment.

Abstract: 

In online combinatorial auctions m indivisible items are to be allocated to n agents who arrive online. Agents have random valuations for the different subsets of items and the goal is to allocate the items on the fly so as to maximize the total value of the assignment. A prophet inequality in this setting refers to the existence of an online algorithm guaranteed to obtain, in expectation, a certain fraction of the expected value obtained by an optimal solution in hindsight. The study of prophet inequalities for online combinatorial auctions has been an intensive area of research in recent years, and constant factor prophet inequalities are known when the agents' valuation functions are submodular or fractionally subadditive. Despite many efforts, for the more general case of subadditive valuations, the best-known prophet inequality has an approximation guarantee of O(log log m).

We prove the existence of a constant factor prophet inequality for the subadditive case, resolving a central open problem in the area.

Our prophet inequality is achieved by a novel, but elementary, sampling idea which we call the Mirror Lemma. This lemma is essentially concerned with understanding algorithms for which the set of items that are allocated and those that are not, distribute equally. The other main ingredient is a nonstandard application of Kakutani's fixed point theorem.

Abstract: 

We examine variations of the classical secretary problem in a new setting, where the decision-maker (DM) can request one (or more) bits of ordinal information from agents before they arrive. Specifically, each agent has private information (their weight) that is publicly revealed upon arrival. As usual, the DM must irrevocably decide whether to select the agent or not after this step. Additionally, at any given time, the DM can privately ask yes-or-no questions to agents who have not yet arrived, and the agents can only answer ordinal questions based on comparing their private information with the information publicly available up to that point. We refer to this additional information as ordinal advice. For example, the DM may ask if the agent’s hidden value is higher than that of all agents who have arrived so far, but he cannot ask if that value is the largest of the entire list as the agent does not have information about the other agents that haven’t arrived.

The goal is to select the agent with the highest weight from the list. We consider different ways in which the agents can arrive, such as randomly, in an adversarial order, or with a random sample of agents that are revealed beforehand. In the latter case, the DM is the one who chooses the number of applicants included in the sample, and the rest of the input is presented in an order chosen by an adversary either before or after the realization of the sample set. We explore the impact of varying the amount of ordinal advice allowed by considering the cases where the DM can ask for zero, one, or multiple rounds of ordinal advice. We present algorithms that achieve optimal competitive ratios for almost all the settings considered. Notably, we observe that ordinal advice improves the performance in every scenario, with the exception of the adversarial-order setting.

This talk is based on joint work with José Soto.

Abstract: 

We consider the problem of scheduling jobs on a single machine, non-preemptively. The goal is to minimize the total completion time of the jobs. It is well known that this problem is solved by scheduling the jobs in order of shortest processing times (SPT) when the jobs’ processing times are known or shortest expected processing times (SEPT), when we have full knowledge on the true expected values.

In this talk, we consider the stochastic scheduling problem in which we have additional uncertainty about the parameters of the distribution of the jobs’ processing times. We assume that jobs appear in $m$ classes and the processing times of jobs in one class are independently and identically distributed. By processing a job from one class one can learn about the true parameters of the distribution. The initial beliefs on these parameters are modelled as a prior distribution and after processing a job the posterior distribution models the updated beliefs on the parameter.

When the processing times are exponentially distributed with an unknown parameter that is gamma distributed, optimal policies based on Gittins-indices exist (see, e.g., Hamada and Glazebrook, 1993). However, computing these indices may be computationally challenging.

In this talk, we consider two simple policies, based on SEPT. The first policy processes the jobs based on the initial beliefs of the expected processing time. This implies that all jobs of one class are processed consecutively. The second policy, always processes a job from a class with shortest expected processing time according to the updated beliefs.

We can show that both policies have a (worst-case) approximation ratio of $m$, the number of classes, and that this ratio is tight.

This talk is based on (updated beliefs of) joint work with Sebastian Marban and Cyriel Rutten.

Abstract: 

Learning theory has burgeoned since 1971 (VC-dimension by Vapnik and Chervonenkis) when the framework was established and the fundamental theorem proved. We extend the framework to model a strategic setting that allows for adversarial behavior during the test phase. As an example consider a situation where students may manipulate their application materials knowing universities' admissions criteria. We define a new parameter, SVC (Strategic VC dimension) and use it to characterize the statistical and computational learnability of the strategic linear classification problem. The practice of learning exploded in 2012 (AlexNet by Krizhevsky, Sutskever and Hinton) leading to a profusion of deep neural network (DNN) architectures and training algorithms. We consider the problem of  creating tags from a noisy scanning technology (e.g. optochemical inks, magnetic microwires etc.). 

Formalizing it as a coding-theoretic problem. we develop a novel neural network architecture (DANNI) and training algorithm to solve it, with provable performance guarantees.

The theory part is joint work with Anil Vullikanti, Haifeng Xu and Fan Yao, and the practice part is joint with Akshar Varma.

Abstract: 

Pandora's Box models optimization problems where the input consists of stochastic random variables, but the uncertainty can be removed (i.e. reveal the exact value of a variable) by paying an extra price. Our goal is to maximize (or minimize) the price of the variable chosen minus (resp. plus) the cost we paid to learn the exact instantiations of the variables. All previous work on this class of problems assumes that different random variables in the input are distributed independently. Until recently nothing was known for the case of correlated input.

In this talk I will introduce Pandora's Box problem and describe the first constant approximation algorithm for Pandora's Box with correlated distributions. I will also briefly mention a newer, simpler algorithm that directly generalizes the independent case algorithm while also improving on the approximation factor.

This is based on joint work with Shuchi Chawla, Yifeng Teng, Christos Tzamos and Ruimin Zhang.

Abstract: 

We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition government. This setting (known as weighted fair division) constitutes a generalization of the well-studied apportionment problem, and we present two approaches for lifting apportionment methods to weighted fair division.

In the first part of the talk, we focus on additive valuations and show that picking sequences derived from divisor methods provide natural envy-freeness, proportionality, and monotonicity properties. However, picking sequences quickly lose their fairness guarantees when moving beyond additive valuations. In the second part of the talk, we introduce welfare measures based on harmonic numbers and show that variants of maximum weighted harmonic welfare offer strong fairness guarantees under matroid-rank valuations. Surprisingly, these guarantees are even stronger than those that are satisfied by the well-known Nash welfare rule.

This talk is based on joint work with Mithun Chakraborty, Luisa Montanari, Nicholas Teh, and Warut Suksompong. 

Abstract: 

Inspired by first-passage percolation models, we consider zero-sum games on Z^d and study their limit behavior when the game duration tends to infinity. After reviewing several fundamental results in this literature, we present a generalization and discuss connections with long-term behavior of Hamilton-Jacobi equations.

Abstract: Consider a set system on a finite ground set E, where each set P in the system is equipped with a required hitting probability r(P) and each element e of E has a probability marginal p(e). We study the question whether the marginals can be decomposed into a distribution over all subsets of E such that the resulting random set intersects each set P from the system with probability at least r(P). A simple necessary condition is that for every set P in the system, the sum of the marginals of elements in P is at least r(P).

Extending a result by Dahan, Amin, and Jaillet (Mathematics of Operations Research 47:457-484, 2022) motivated by a security game in a directed acyclic graph, we show that the aforementioned necessary condition is also sufficient in the following two settings: (i) the set system fulfills a max-flow/min-cut property and the requirements are affine; (ii) the set system is an abstract network and the requirements fulfill a weak conservation law. We provide algorithms for the computation of the corresponding decompositions and, in some cases, simple explicit descriptions of these decompositions. As a subroutine, we also devise a combinatorial algorithm for computing shortest paths in abstract networks, partially answering an open question by McCormick (SODA 1996). A consequence of our results is that equilibria for the security game studied by Dahan et al. (2022) and similar games involving randomized surveillance strategies can be computed efficiently, even when the underlying digraph contains cycles.

Abstract: An emerging frontier in Algorithmic Game Theory is Algorithmic Contract Theory, which studies the classic hidden-action principal-agent problem of contract theory through the computational lens.

In this talk, I will present three basic ways in which the problem can be combinatorial and survey both hardness and poly-time (approximation) results.

The analysis will uncover some surprising connections (but also fundamental differences) to combinatorial auctions.

Abstract: Marketplace platforms use experiments (also known as “A/B tests”) as a method for making data-driven decisions about which changes to make on the platform. When platforms consider introducing a new feature, they often first run an experiment to test the feature on a subset of users and then use this data to decide whether to launch the feature platform-wide. However, it is well documented that estimates of the treatment effect arising from these experiments may be biased due to the presence of interference driven by the substitution effects on the demand and supply sides of the market.   

In this work, we develop an analytical framework to study experimental design in two-sided marketplaces. We develop a stochastic market model and associated mean field limit to capture dynamics in such experiments. Notably, we use our model to show how the bias of commonly used experimental designs and associated estimators depend on market balance. We also propose novel experimental designs that reduce bias for a wide range of market balance regimes. We also discuss a simpler model to study the bias-variance trade-off among different experimental choices. Finally, we present results on calibrated models and live implementations on two real-world platforms. Overall, our  work shows the potential of structural modeling to yield insight on experimental design for practitioners. 

Based on joint work with Ramesh Johari, Hannah Li, Inessa Liskovich, and Geng Zhao.

Abstract: When organizations select from a set of applicants, they often use a priority ranking in tandem with policies designed to ensure diversity or boost the chances of applicants from certain groups. These policies add significant complexity to the selection process, and examples from around the world show that they often do not have the intended effect, or are accompanied by unintended consequences. 

Motivated by a desire to make these rules more transparent, we provide three axioms intended to capture explainability: monotonicity, lower invariance, and non-bossiness. We show that these axioms characterize a family of "outcome-based" selection rules. This family of selection rules is rich enough to incorporate many (but not all) existing reserve and quota policies. We illustrate our findings using examples from the allocation of affordable housing in New York City.

Abstract:  In this talk, I will present an extension of the prophet inequality problem to a competitive setting. At every period, a new sample from a known distribution arrives, which is publicly observed. Then, two players simultaneously decide whether to pick an available value or to pass and wait until the next period (ties are broken uniformly at random).  As soon as a player gets one sample, he leaves the market, and his payoff is the value of the sample. In a first variant, namely no recall case, the agents can only bid in each period for the current value. In a second variant, the full recall case, the agents can also bid at each period for any of the previous samples that have not been already selected. For each variant, we study the two-player game induced by the optimal stopping problem, focusing on subgame-perfect Nash equilibria. In particular,  I will describe the set of subgame-perfect Nash equilibria payoffs, I will compare the two model variants in terms of the payoffs of the players and I will provide tight bounds for the Price of Anarchy and Price of Stability of the former setting when the number of arrivals is two.

Joint work with Fabien Gensbittel and Jérôme Renault (TSE).

Abstract: The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ) formulation. First, we argue that the choice of some parameters of this formulation is arbitrary and, therefore, there is a family of formulations of which MTZ is a particular case. We analyze this family, noting that in general the formulations involved are not comparable to each other and there is no one that dominates the rest. Then, we study the intersection of this family, which we show to be equivalent to the well-known Circuit Inequalities formulation. Finally, we extend this approach to the Desrochers-Laporte and Single-Commodity Flow formulations, obtaining similar results. Based on joint work with Diego Morán (UAI).

Abstract: Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. We give a deterministic mechanism with an additive performance guarantee of $O(n^{(1+\gamma)/2})$ in a setting with $n$ individuals where each individual casts $O(n^{\gamma})$ nominations, where $\gamma \in [0,1]$. For $\gamma=0$, i.e., when each individual casts at most a constant number of nominations, this bound is $O(\sqrt{n})$. This matches the best-known guarantee for randomized mechanisms and a single nomination. For $\gamma=1$ the bound is $O(n)$. This is trivial, as even a mechanism that never selects provides an additive guarantee of $n-1$. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.

This is joint work with Felix Fischer, David Hannon, and Max Klimm.

Abstract: Combinatorial generation is the task of computing all solutions to a combinatorial problem instead of only one of them. For example, we may be interested in all spanning trees of a given graph or all optimal weight perfect matchings of a given weighted graph. In recent years, there has been much interest in unifying techniques or general approaches that simultaneously apply to various combinatorial generation problems. 

We propose a new simple general approach for combinatorial generation. Given some binary strings X⊆{0,1}ⁿ, our approach consists of greedily computing a Hamilton path in a polytope with X as vertices, namely conv(X). Our main result shows that this approach works for all X⊆{0,1}ⁿ and is efficient whenever optimization over X can be efficiently solved, showing an unexplored relation between combinatorial optimization and generation. More specifically, if we can solve certain linear optimization problems for X in time O(T), we can compute a Hamilton path in conv(X) in roughly O(T⋅log(n)) time per vertex.

As a consequence, we obtain new efficient algorithms for combinatorial generation problems that can be binary encoded, like spanning tree generation, 0/1 vertex enumeration, and perfect matching generation. Furthermore, consecutive objects visited by our generation algorithms differ only in a local operation, like an edge exchange in the case of spanning trees or an alternating cycle exchange in the case of perfect matchings. 

This is joint work with Torsten Mütze. 

Abstract: Assume that you want to sort n integers, and you have many copies of a device that can sort k integers. At one step, you can partition n integers into sets of size at most k by putting them into your devices. How many such steps do you need to sort your initial array? 

When k = 2, this problem is just a problem of constructing a sorting network. It can be solved in O(log n) steps, though the construction is complicated and impractical. We consider a reversed setting. Namely, we fix a number of steps and seek for the minimal k such that our problem is solvable within this number of steps with this k. We determine the minimal k for 2,3, and 4 steps. 

Joint work with Natalia Dobrokhotova-Maikova and Vladimir Podolski. 

Abstract: Let $G$ be a graph of order $n\ge 2$, and let $k$ be an integer with $k\in \{1,2,\dots,n-1\}$. The $k$-token graph $F_k(G)$ of $G$ is the graph whose vertices are all the $k$-subsets of vertices of $G$, and two of such $k$-subsets are adjacent whenever their symmetric difference is an edge of $G$. We denote by $C_4$ the $4$-cycle and by $D_4$ the diamond graph (a $4$-cycle with a chord). We say that $G$ is a $(C_4,D_4)$-free graph if $G$ does not contain $C_4$ nor $D_4$ as a subgraph.

In 2012 Fabila-Monroy et al. conjectured the following: If $G$ and $H$ are two graphs such that $F_k(G)$ and $F_k(H)$ are isomorphic for some $k$, then $G$ and $H$ are isomorphic. In this talk we will show this conjecture for the family of $(C_4,D_4)$-free graphs. Moreover, we will see how this reconstruction problem is related to the automorphism group of token graphs.  This is a joint work with Ruy Fabila Monroy.

Abstract: We study the assignment of indivisible objects to individuals when transfers are not allowed. Previous literature has mainly focused on efficiency (from ex-ante and ex-post perspectives), and individually fair assignments. Consequently, egalitarian concerns have been overlooked. We are inspired by the assignment of apartments in housing cooperatives where families regard the egalitarianism of the assignments as a first-order requirement. In particular, they want to avoid assignments where some families get their most preferred apartment, while others get options ranked very low in their preferences. Based on Rawls' idea of fairness, we introduce the notion of Rawlsian assignments. We prove that there always exists a unique Rawlsian assignment, which is sd-efficient, and satisfies equal treatment of equals. We illustrate our analysis with preference data from housing cooperatives. Our results show that the Rawlsian assignment substantially improves, from an egalitarian perspective, both the probabilistic serial mechanism, and the mechanism currently in use. 

Joint with Tom Demeulemeester

Abstract: In pursuit of Sustainable Development Goal 3 “Ensure healthy lives and promote well-being for all at all ages,” considerable global effort is directed toward elimination of infectious diseases in general and Neglected Tropical Diseases in particular. For various such diseases, the deployment of mobile screening teams forms an important instrument to reduce prevalence toward elimination targets. There is considerable variety in planning methods for the deployment of these mobile teams in practice, but little understanding of their effectiveness. Moreover, there appears to be little understanding of the relationship between the number of mobile teams and progress toward the goals. This research considers capacity planning and deployment of mobile screening teams for one such neglected tropical disease: Human African trypanosomiasis (HAT, or sleeping sickness). We prove that the deployment problem is strongly NP-Hard and propose three approaches to find (near) optimal screening plans. For the purpose of practical implementation in remote rural areas, we also develop four simple policies. The performance of these methods and their robustness is benchmarked for a HAT region in the Democratic Republic of Congo (DRC). Two of the four simple practical policies yield near optimal solutions, one of which also appears robust against parameter impreciseness. We also present a simple approximation of prevalence as a function of screening capacity, which appears rather accurate for the case study. While the results may serve to more effectively allocate funding and deploy mobile screening capacity, they also indicate that mobile screening may not suffice to achieve HAT elimination.

Abstract: Amoeba graphs were born as examples of balanceable graphs, which are graphs that appear in any 2-edge coloring of the edges of a large enough $K_n$ with a sufficient amount of red and blue edges. As they were studied further, interesting aspects were found.

An edge replacement $e\to e$ in a labeled graph G means to take an edge e in E(G) and replace it with e' \in E(\overline{G})\cup \{e\}$. If $G-e+e'$ is isomorphic to $G$ then we say $e\to e'$ is a \emph{feasible edge replacement}. Every edge replacement yields a set of permutations of the labels in $G$. The set of all permutations associated with all feasible edge replacements in $G$ generates the group $\Gamma_G$. A labeled graph $G$ of order $n$ is a \emph{local amoeba} if $\Gamma_G \cong S_n$. One might think local amoebas are hard to find. However, in this talk we will go over a recursive construction of infinite families of local amoebas.

Es trabajo conjunto con Ludmila Matyskova

Abstract: We consider a Bayesian persuasion model in which the receiver can gather independent information about the state at a uniformly posterior-separable cost. We show that the sender provides information that prevents the receiver from gathering independent information in equilibrium. When the receiver faces a lower cost of information, her `threat' of gathering independent information increases, thus decreasing the sender's power to persuade. A lower cost of information can also hurt the receiver because the sender may provide strictly less information in equilibrium. Finally, we propose a solution method that can be used to solve our model in specific applications.

Es trabajo conjunto con Ludmila Matyskova

Abstract: The kidney exchange problem is a combinatorial optimization problem that arises naturally when implementing centralized kidney exchange programs. Given a directed weighted graph (called the compatibility graph), we aim to find a collection of simple and vertex-disjoint cycles maximizing the total weight of their participating arcs.

Because of logistical considerations, a bound k is placed on the length of each possible cycle. We will briefly explain how the problem is polynomially solvable in the cases k = 2 and unbounded k, and why it turns NP-complete for k >= 3.

MIP formulations are used in practice because of their efficiency and flexibility to accommodate extra constraints of the exchange programs. We will introduce the cycles MIP formulation of Roth et al. and explain why its linear relaxation is polynomially solvable. Inspired by this result, we present a conjecture on the integrality gap of this formulation, which is part of our ongoing work.

Time permitting, we will also discuss the addition of exchange chains starting from a distinguished subset of vertices (representing deceased or altruistic donors) and explain how their introduction makes even the associated linear relaxation problem NP-hard.

Abstract: This work started with a real-world problem where the task was to partition a set of locations into disjoint subsets such that each subset is spread in a way that it covers the whole set with a certain radius. 

This made us formalizing the following problem which we call Solidarty Cover Problem. Given a finite set S, a metric d, and a radius r, and a number of partitions m. We define a subset C of S to be an r-cover if B(C,r)=S. The Solidarity Cover Problem is the problem of determining whether there exist m disjoint r-covers. We consider the optimization problems of maximizing the number of r-covers which is essentially the domatic number problem, and the optimization problem of minimizing the radius. 

This is joint work with Britta Peis and Eran Rosenbluth.

Abstract: We consider prophet inequalities under general downward-closed constraints. In a prophet inequality problem, a decision-maker sees a series of online elements and needs to decide immediately and irrevocably whether or not to select each element upon its arrival, subject to an underlying feasibility constraint. Traditionally, the decision-maker’s expected performance has been compared to the expected performance of the prophet, i.e., the expected offline optimum. We refer to this measure as the Ratio of Expectations (or, in short, RoE). However, a major limitation of the RoE measure is that it only gives a guarantee against what the optimum would be on average, while, in theory, algorithms still might perform poorly compared to the realized ex-post optimal value. 

Hence, we study alternative performance measures. In particular, we suggest the Expected Ratio (or, in short, EoR), which is the expectation of the ratio between the value of the algorithm and the value of the prophet. This measure yields desirable guarantees, e.g., a constant EoR implies achieving a constant fraction of the ex-post offline optimum with constant probability. Moreover, in the single-choice setting, we show that the EoR is equivalent (in the worst case) to the probability of selecting the maximum, a well-studied measure in the literature. This is no longer the case for combinatorial constraints (beyond single-choice), which is the main focus of this paper.

Our main goal is to understand the relation between RoE and EoR in combinatorial settings. Specifically, we establish a two-way black-box reduction: for every feasibility constraint, the RoE and the EoR are at most a constant factor apart. This implies a wealth of EoR results in multiple settings where RoE results are known.

This is joint work with Tomer Ezra, Stefano Leonardi, Rebecca Reiffenhäuser, and Matteo Russo.

Abstract: In the context of the COVID-19, the development of methods to trace the spread of the virus is of vital importance. One of such methods relies on PCR testing of wastewater samples to locate sudden the appearance of infection. Given a representation of the wastewater network as a directed graph, we aim for a strategy that finds a new infected node using the worst-case minimum number of tests. This problem proves to be challenging on networks with uncertainty, as is the case of real-world data. We will explore the connection with other known graph problems and show upper bounds for the number of tests in an optimal strategy on graphs of bounded treewidth and planar graphs. Then we analyze experimental results obtained using a greedy algorithm to select nodes to sample, and finally conclude by stating several relevant open questions.

Joint work with I. Beaudry, J. Baboun, M. Castro, A. Jara, B. Rubio, J. Verschae.

Abstract: The growing body of work in learning-augmented online algorithms studies how online algorithms can be improved when given access to ML predictions about the future. Motivated by ML models that give a confidence parameter for their predictions, we study online algorithms with predictions that are $\epsilon$-accurate: namely, each prediction is correct with probability (at least) $\epsilon$, but can be arbitrarily inaccurate with the remaining probability. We show that even with predictions that are accurate with a small probability and arbitrarily inaccurate otherwise, we can dramatically outperform worst-case bounds for a range of classical online problems including caching, online set cover, and online facility location. Our main results are an $O(\log(1/\varepsilon))$-competitive algorithm for caching, and a simple $O(1/\varepsilon)$-competitive algorithm for a large family of covering problems, including set cover and facility location, with $\epsilon$-accurate predictions.

Abstract: In the context of the COVID-19, the development of methods to trace the spread of the virus is of vital importance. One of such methods relies on PCR testing of wastewater samples to locate sudden the appearance of infection. Given a representation of the wastewater network as a directed graph, we aim for a strategy that finds a new infected node using the worst-case minimum number of tests. This problem proves to be challenging on networks with uncertainty, as is the case of real-world data. We will explore the connection with other known graph problems and show upper bounds for the number of tests in an optimal strategy on graphs of bounded treewidth and planar graphs. Then we analyze experimental results obtained using a greedy algorithm to select nodes to sample, and finally conclude by stating several relevant open questions.

Joint work with I. Beaudry, J. Baboun, M. Castro, A. Jara, B. Rubio, J. Verschae.

Abstract: Differentially private (DP) stochastic nonconvex optimization (SNCO) is a fundamental problem, where the goal is to approximate stationary points (i.e points with small norm of the gradient) of the population loss, given a dataset of i.i.d. samples from a distribution, while satisfying differential privacy with respect to the dataset. Most of the existing works in the literature have addressed either the convex version of this problem (DP-SCO) or the closely related problem of Private Non-Convex Empirical Risk Minimization, where one seeks to approximate stationary points of the empirical loss.

In the first part of this talk I will provide an overview of differential privacy and of (non-private) stochastic nonconvex optimization. Then, I will show how to privatize the well known SPIDER algorithm for SNCO that relies on variance reduction techniques, and how to prove privacy and accuracy guarantees for its private version. The private version of SPIDER leads to the rate of convergence to stationary points of the population loss of O(d^{1/4} / (n\epsilon)^{1/2}), which was the best previously known rate for the empirical case.

The private version of SPIDER appeared in section 4 of arXiv:2206.00846.

Abstract: Given a market where discrete indivisible items of different types are sold to a set of buyers. There is a given supply of each type and each buyer has a given (maximum) demand. Each buyer valuates the items linearly in our setting. We aim for competitive prices, i.e. prices such that an allocation exists where every buyer gets one of his preferred bundles. The prices should be as small as possible and as much as possible should be sold.

We show how to compute these buyer-optimal Walrasian prices. We present an ascending auction which iteratively raises the prices on the goods in the left-most min cut in some associated auxiliary flow network. Given this prices, we can compute an allocation where as much as possible is sold. The structural insights obtained from our flow-based approach furthermore lead to several interesting insights regarding the sensitivity analysis of our ascending auction.

Joint work with Katharina Eickhoff, Tom McCormick, Britta Peis, and Laura Vargas Koch.

Abstract: In several computer science applications one encounters the following problem: Given two edge-labeled graphs G and H, how many homomorphic images of H can be found in G? Atserias, Grohe, and Marx developed a tight bound for this number, denoted #Hom(H,G), which is now known as the AGM bound. The bound relates #Hom(H,G) with the fractional edge covers of H in a very elegant and direct way. We will present a self-contained and simple proof of this result using Shearer's inequality. 

Abstract: In the context of the COVID-19, the development of methods to trace the spread of the virus is of vital importance. One of such methods relies on PCR testing of wastewater samples to locate sudden the appearance of infection. Given a representation of the wastewater network as a directed graph, we aim for a strategy that finds a new infected node using the worst-case minimum number of tests. This problem proves to be challenging on networks with uncertainty, as is the case of real-world data. We will explore the connection with other known graph problems and show upper bounds for the number of tests in an optimal strategy on graphs of bounded treewidth and planar graphs. Then we analyze experimental results obtained using a greedy algorithm to select nodes to sample, and finally conclude by stating several relevant open questions.

Joint work with I. Beaudry, J. Baboun, M. Castro, A. Jara, B. Rubio, J. Verschae.

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 arbitrary fixed graph G. We will also consider a natural generalization of the process to s-uniform hypergraphs.

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 environments, including the dichotomous, single-peaked, and social choice domains.

Joint work with Joe Root and Fedor Sandomirskiy.

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, Wiese, FOCS'11; Anagnostopoulos, Grandoni, Leonardi, Wiese, SODA'14; Grandoni, Mömke, Wiese, Zhou, STOC'18], the best known polynomial time approximation algorithm for UFP has an approximation ratio of 1+1/(e+1) +  epsilon < 1.269 [Grandoni, Mömke, Wiese, SODA'22]. It has been an open question whether this problem admits a PTAS.  In this paper, we solve this open question and present a polynomial time (1 + epsilon)-approximation algorithm for UFP.

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 rise to a behavior that cannot be observed without percolation.

Joint work with Lyuben Lichev and Guillem Perarnau.

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 aware of the externalities induced to the rest.

In this paper, we propose protocols to share the costs within a ride so that optimal solutions can also constitute equilibria. To do this, we model the situation as a non-cooperative game, which can be seen as a game-version of the well-known set cover problem. We show that the traditional notions of equilibrium in game theory (Nash and Strong) are not useful here, and prove that determining whether a Strong Equilibrium exists is an NP-Complete problem, by reducing it to the k-Exact-Cover problem. Hence, we propose three alternative equilibrium notions (stronger than Nash and weaker than Strong), depending on how users can coordinate. For each of these equilibrium notions, we propose a (possibly overcharging) cost-sharing protocol that yields the optimal solutions equilibria.

Simulations for Amsterdam reveal that our protocols can achieve stable solutions that are close to the optimum, and that having a central coordinator can have a large impact.

Abstract: Say you are tasked to find the best 150 papers among more than 250 for conference proceedings or as part of a national exercise to maximise workload.

You can ask people to review a given paper by either asking

1) Is paper A better than paper B

or

2) What’s the score of paper A?

The problem is that each review returns an incorrect response with a small probability, say 1/3.

How can you assign reviews so that you will likely find the best 150 papers while the total of queries and rounds is small?

The talk is based on the paper

Instance-Optimality in the Noisy Value-and Comparison-Model---Accept, Accept, Strong Accept: Which Papers get in? [SODA 2020]

https://epubs.siam.org/doi/10.1137/1.9781611975994.131

https://arxiv.org/pdf/1806.08182.pdf

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. This extends a result of Cominetti, Correa and Olver, who show a steady-state result in the regime where the input flow rate is smaller than the network capacity. 

Surprisingly, the steady state result turns out to be helpful to prove two nice properties:

- Uniqueness of journey times in equilibria

- Continuity of equilibria: small perturbations to the instance or to the traffic situation at some moment cannot lead to wildly different equilibrium evolutions.

This is joint work with Neil Olver and Leon Sering

Abstract:  In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ratio of the total capacity on the edges of G crossing the cut over the total demand of the crossing edges of D. In this work, we study the non-uniform sparsest cut problem for supply graphs with bounded treewidth k. For this case, Gupta, Talwar and Witmer [STOC 2013] obtained a 2-approximation with polynomial running time for fixed k, and the question of whether there exists a c-approximation algorithm for a constant c independent of k, which runs in FPT time, remained open. We answer this question in the affirmative. We design a 2-approximation algorithm for the non-uniform sparsest cut with bounded treewidth supply graphs that runs in FPT time when parameterized by the treewidth. Our algorithm is based on rounding the optimal solution of a linear programming relaxation inspired by the Sherali-Adams hierarchy. In contrast to the classic Sherali-Adams approach, we construct a relaxation driven by a tree decomposition of the supply graph by including a carefully chosen set of lifting variables and constraints to encode information of subsets of nodes with super-constant size, and at the same time we have a sufficiently small linear program that can be solved in FPT time.

This is joint work with Vincent Cohen-Addad (Google Research Zurich) and Tobias Mömke (University of Augsburg). This work has been accepted at IPCO 2022.

Abstract:  Given a hypergraph with uncertain node weights following known probability distributions, we study the problem of querying as few nodes as possible until the identity of a node with minimum weight can be determined for each hyperedge. Querying a node has a cost and reveals the precise weight of the node, drawn from the given probability distribution. Using competitive analysis, we compare the expected query cost of an algorithm with the expected cost of an optimal query set for the given instance. For the general case, we give a polynomial-time f(α)-competitive algorithm, where f(α)∈[1.618+ϵ,2] depends on the approximation ratio α for an underlying vertex cover problem. We also show that no algorithm using a similar approach can be better than 1.5-competitive. Furthermore, we give polynomial-time 4/3-competitive algorithms for bipartite graphs with arbitrary query costs and for hypergraphs with a single hyperedge and uniform query costs, with matching lower bounds.

Joint work with Evripidis Bampis, Thomas Erlebach, Murilo S. de Lima, Nicole Megow, Jens Schlöter.

Abstract:  In malleable scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. Each job is required to be executed non-preemptively and in unison, i.e., it has to occupy the same time interval on all its allocated machines. 

In this talk, we discuss a generalization of malleable scheduling, in which a function f(S, j) determines the processing time of job j on machine subset S. Under different discrete concavity assumptions on 1/f(S,j), we show that the scheduling problem can be approximated by a considerably simpler assignment problem and derive LP-based approximation algorithms. 

We also highlight a connection to the problem of fairly allocating resources (the Santa Claus problem and its generalizations) and show how our results imply resource-augmented approximation algorithms for this setting.

This is joint work with Dimitris Fotakis and Orestis Papadigenopoulos.

Abstract:  In 1988, Erdos wrote about a problem he proposed with Nesetril:

"One could perhaps try to determine the smallest integer h_t(D) for which every graph, with size h_t(D) edges and maximum degree at most D, contains two edges so that the shortest path joining these edges has length at least t. This problem seems to be interesting only if there is a nice expression for h_t(D)."

This problem can be considered as the edge version of the famous (and hard) degree-diameter problem.

It was the inspiration for a series of research papers on variants of this problem, where one is mainly dealing with the case t=2. We will discuss part of the history that resulted in the strong edge colouring conjecture, which is still widely open.

In the second part of the talk, we will look again to the initial inspirational question of all of this and say more about the cases where t is at least 3.

Abstract:  In many markets, buyers do not bid directly in the auction, but instead, they are represented by intermediaries. This includes ad auctions, where some of the buyers might be represented by intermediaries like Ad agencies, Aggregators (e.g. Home Advisor), or Ad networks participating in an Ad Exchange. The presence of intermediaries creates the potential for collusion across buyers. Also, intermediaries have their own goals that depend on the contract between buyers and the intermediary, and will behave according to the incentives induced by their goals. We will talk about the problem of designing mechanisms for such settings. In particular, we consider the problem of selling k items to unit-demand buyers with private valuations for the items. A buyer either participates directly in the auction or is represented by an intermediary, who can represent a subset of buyers. Our goal is to design robust mechanisms that are independent of the demand structure (i.e. how the buyers are partitioned across intermediaries), and perform well under a wide variety of possible contracts between intermediaries and buyers. We first consider the case of k identical items where each buyer draws its private valuation for an item i.i.d. from a known distribution that is lambda-regular (a weaker condition than monotone hazard rate). Next, we generalize this to the setting of related items. 

Abstract: In the classical stable marriage problem, we are given two sets of agents - students and schools - with each student and school having a total order of agents from the opposite set. The goal is to form disjoint pairs of students and schools so that the resulting matching satisfies a fairness property known as stability. In their fundamental work, Gale and Shapley showed that a stable matching always exists, and gave a fast algorithm to find one. These strong structural and algorithmic results propelled the application of the stable marriage model in several contexts, most notably for assigning students to public high schools in many cities in the United States. Although very successful, the marriage model however fails to capture features that have become of crucial importance both inside and outside academia, such as diversity in school cohorts, complex preference patterns, and the need to obtain larger, possibly mildly unstable, matchings. In this talk, I will first present some extensions of the concept of stability and of the marriage model, and investigate them from an optimizer's viewpoint. I will then focus in detail on recent work with Xuan Zhang (Columbia) on algorithms for stable matching models when the preference patterns of agents are described by choice functions. Our approach will allow us to deduce general sufficient conditions for efficiently optimizing linear functions over the elements of a distributive lattice.

Abstract: We consider the simplest game, Matrix Games, and basic stability questions on the value and strategies upon perturbations on the payoff matrix. Considering polynomial perturbations, we design polynomial-time algorithms for the following tasks: (a) ensuring that, for every sufficiently small error, there is a strategy to guarantee that the value is at least the value of the error-free case; (b) ensuring that there is a fixed strategy to guarantee that, for every sufficiently small error, the value is at least the value of the error-free case; and (c) computing the analytical form of the value of the game upon perturbations. We also make the connection with Linear Programming, just as Mills did in 1956 for a related problem.

Abstract:  By using random multilinear maps, we provide new lower bounds for the Erdős box problem, the problem of estimating the extremal number of the complete d-partite d-uniform hypergraph with two vertices in each part, thereby improving on work of Gunderson, Rödl and Sidorenko. Joint work with Cosmin Pohoata and Dmitriy Zakharov.

Abstract: Let G be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching B is popular if B does not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide if G admits a popular branching or not. We give a characterization of popular branchings in terms of dual certificates and use this characterization to design an efficient combinatorial algorithm for the popular branching problem. When preferences are weak rankings, we use our characterization to formulate the popular branching polytope in the original space and also show that our algorithm can be modified to compute a branching with least unpopularity margin. When preferences are strict rankings, we show that “approximately popular” branchings always exist.

This is joint work with Telikepalli Kavitha, Tamás Király, Jannik Matuschke, and Ildikó Schlotter.

Abstract: In the 2-Dimensional Knapsack problem (2DK) we are given a square knapsack and a collection of n rectangular items with integer sizes and profits. Our goal is to find the most profitable subset of items that can be packed non-overlappingly into the knapsack. The currently best known polynomial-time approximation factor for 2DK is 17/9+eps<1.89 and there is a (3/2+eps)-approximation algorithm if we are allowed to rotate items by 90 degrees. In this talk, I will present a (4/3+eps)-approximation algorithms in polynomial time for both cases, assuming that all input data are integers polynomially bounded in n.

The previous best algorithm for 2DK partitions the knapsack into a constant number of rectangular regions plus one L-shaped region and packs items into those in a structured way. We generalize this approach by allowing up to a constant number of more general regions that can have the shape of an L, a U, a Z, a spiral, and more, and therefore obtain an improved approximation ratio. In particular, our results are achieved via an algorithm that computes the essentially optimal structured packing into these regions. 

Joint work with Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero and Andreas Wiese. 

Abstract: Differentially private (DP) stochastic convex optimization (SCO) is a fundamental problem, where the goal is to approximately minimize the population risk with respect to a convex loss function, given a dataset of i.i.d. samples from a distribution, while satisfying differential privacy with respect to the dataset. Most of the existing works in the literature of private convex optimization focus on the Euclidean (i.e., $\ell_2$) setting, where the loss is assumed to be Lipschitz (and possibly smooth) w.r.t.~the $\ell_2$ norm over a constraint set with bounded $\ell_2$ diameter. Algorithms based on noisy stochastic gradient descent (SGD) are known to attain the optimal excess risk in this setting.

In this talk I will provide a brief overview of differential privacy and its applications in stochastic convex optimization, together with new upper and lower bounds on the population risk for DP-SCO in non-Euclidean setups, in particular where the reference norm is the $\ell_p$-norm, $1\leq p\leq \infty$. Our algorithms include DP versions of variance-reduced stochastic Frank-Wolfe and mirror-descent methods, together with a novel privacy mechanism, which generalizes the Gaussian mechanism. Our work draws upon concepts from the geometry of normed spaces, such as the notions of regularity, uniform convexity, and uniform smoothness. 

Based on joint work with Raef Bassily and Anupama Nandi, and available at arXiv:2103.01278

Abstract: Consider two random processes on an n vertex graph related to Internal Diffusion-Limited Aggregation (IDLA). In each process n particles perform independent random walks from a fixed vertex until they reach an unvisited vertex, at which point they settle. In the first process only one particle moves until settling and then the next starts, in the second process all particles are released together. 

We study the dispersion time which is the time taken for the longest walk to settle. We present a new coupling which allows us to compare dispersion time across the processes. We additionally prove bounds on the dispersion time(s) in terms of more well-studied parameters of random walks such as hitting times and the mixing time. 

Abstract: Gale and Shapley (1962) introduced a matching problem between two sets of agents M and W, who need to be paired by taking into account that each agent on one side of the market has an exogenous preference order over the agents of the other side. They defined a matching as stable if no unmatched pair can both improve their payoffs by breaking their couples and forming a new one. They proved the existence of a stable matching using a deferred-acceptance algorithm. Shapley and Shubik (1971) extended the model by allowing monetary transfers. Our article offers a further extension by assuming that matched couples obtain their payoff endogenously as the outcome of a strategic-form game they have to play. A matching, together with a strategy profile, is externally stable if no unmatched pair can break their couples, form a new one and play a strategy profile in their game such that both of them improve their payoffs. It is internally stable if no agent, by individually changing its strategy inside its couple, can increase its payoff without breaking the external stability of its couple. We prove the existence of an externally and internally stable matching in a large class of problems including zero-sum games, strictly competitive games, potential games and infinitely repeated games. We also prove that our main model encompasses and refines matching with monetary transfers  as well as matching with contracts. 

Abstract: In a recent breakthrough in scheduling, Batra, Garg, and Kumar gave the first constant approximation algorithm for minimizing the sum of weighted flow times. Wiese and I (STOC'21) managed to improve this large unspecified constant to 2 + epsilon. I will give a very graphic presentation of the algorithmic techniques behind this. 

Abstract: We study Online Makespan Minimization, one of the most basic scheduling problems, in the random-order model. Here jobs of a given input arrive in a uniformly chosen random order as opposed to the classical adversarial model, which considers worst-case orders. The random-order model originates from the Secretary Problem and has received quite some research interest over the last years.

For scheduling, the random-order model provides beyond worst-case guarantees while still not being overly pessimistic. Furthermore, it leads to a stronger performance measure, which considers 'nearly worst-case' orders. Recent results on Makespan Minimization in the random-order model outperform classical lower bounds, even using this stronger measure. This proves formally that classical worst-case sequences are highly order-reliant and should therefore be rare in practical applications.

In this talk we discuss the role of random-order arrival for Makespan Minimization. We compare recent random-order bounds with various classical online and semi-online guarantees, and introduce key techniques, which allow to profit from random-order arrival. These techniques should be relevant for further research on Random-Order Makespan Minimization and related problems.

This talk is based on the paper Scheduling in the Random-Order Model, which is joint work with Susanne Albers. 

Abstract: Motivated by the allocation of virtual machines into servers in the cloud, we consider the online problem of packing items with random sizes into unit-capacity bins. Items arrive sequentially, but upon arrival an item’s actual size is unknown; only its probabilistic information is available to the decision maker. Without knowing this size, the decision maker must irrevocably pack the item into an available bin or place it in a new bin. Once packed in a bin, the decision maker observes the item’s actual size, and overflowing the bin is a possibility. An overflow incurs a large penalty cost and the corresponding bin is unusable for the rest of the process. In practical terms, this overflow models delayed services, failure of servers, and/or loss of end-user goodwill. The objective is to minimize the total expected cost given by the sum of the number of opened bins and the overflow penalty cost. In this talk, we present an online algorithm with expected cost at most a constant factor times the cost incurred by the optimal packing policy when item sizes are drawn from an i.i.d. sequence. We discuss the limits of our approach and extensions to offline settings, where distributions are known in advance but packed sequentially. Joint work with Mohit Singh and Alejandro Toriello.

Abstract: Matroids, polymatroids and submodular functions are beautiful objects that have appeared in many areas of mathematics including algebra, geometry, topology and optimization. Consequently, they have been studied from multiple points of view. This oftentimes has the consequence that the same results are proven from different points of view and by very different communities. A notable example being their study in optimization and algebraic combinatorics. The goal of this talk is to tell this story, show how a small mixture of ideas from different communities lead to powerful algebraic tools, and speculate a little a bit about the opposite direction. 

Abstract: Seriation is an exploratory combinatorial data analysis technique to reorder objects into a sequence along a one-dimensional continuum when the only available information among the objects is their pairwise similarity (or dissimilarity). Linear seriation aims at inferring an ordering (permutation) consistent with an underlying linear order of the data. In many cases however, the data objects may be arranged around a closed continuum yielding a rather circular underlying order. In a matrix representation, this can be visualized as a symmetric matrix of pairwise dissimilarities between objects where elements of each row/column increase monotonically while moving to the right/bottom until some specific element and then decrease again monotonically until the end of each row/column and fold back from the left/top of the matrix. Many approaches used in linear seriation algorithms involve computing the ball hypergraph associated to the dissimilarity. We show that a similar approach can be used in the circular case. In addition to the previous we present an optimal algorithm for strict seriation, which is a natural setting for continuous data.

Abstract: How many seats should be allocated to each political party in an election? This question has a long and rich history, and plays a fundamental role in order to ensure appropriate levels of representation in the parliaments. We consider this question in the presence of types (e.g. men and women), where apart from ensuring proportionality at the party level, we also have to find an allocation which is paritary for the types. We consider two different approaches: one of them, with a greedy/local search paradigm, corresponds to a mechanism recently approved in the chilean parliament (March 2020) to find the representatives of the constitutional assembly with the goal of designing a new political constitution for Chile (election to happen in April 2021); the other one is based on the idea of integral biproportionality, introduced by Balinski and Demange in the late 80’s. We analyze both mechanisms from an axiomatic and quantitative point of view. We also provide new results regarding integral biproportional solutions and the fair share, a.k.a matrix scaling solution, which represents the ideal (but not necessarily implementable) fractional biproportional solution.

 Joint work with Claire Mathieu (CNRS & IRIF, France)

Abstract:  We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitable subset of the given polygons that fits non-overlappingly into the knapsack. We allow rotating the polygons by arbitrary angles.

In this talk we will first present:

- a quasi-poly time O(1)-approximation

- a poly time O(1)-approximation algorithm if all input polygons are triangles.

We will then look into the setting of resource augmentation, i.e., we allow to increase the size of the knapsack by a factor of 1 + δ for some δ > 0 but compare ourselves with the optimal solution for the original knapsack. In the resource augmentation setting we present:

- a poly time O(1)-approximation

- a quasi-poly time algorithm that computes a solution of optimal weight.

To the best of our knowledge, these are the first results for two-dimensional geometric knapsack in which the input objects are more general than axis-parallel rectangles or circles and in which the input polygons can be rotated by arbitrary angles.

This is joint work with Andreas Wiese.

Abstract:Just over a decade ago, Satoshi Nakamoto published a landmark white paper outlining the backbone protocol to Bitcoin, arguably the world's first mainstream digital currency. Through the Nakamoto protocol and blockchain technology, users can reliably agree upon a common transaction history maintained by miners on the public Bitcoin ledger in a decentralised and anonymous fashion. This is possible in part because agents within the protocol are assumed to be strategic rather than adversarial---a fair assumption when creating a ledger for currency. The Nakamoto protocol is thus at its core a decentralised consensus protocol among strategic agents that is built from cryptographic primitives and judicious incentive engineering. In this talk I will give an overview of how game theory is an important tool to understand decentralised consensus protocols such as Bitcoin. Along the way, I will highlight recent work pertaining to strategic mining within "pools" of miners and inherent structural limitations of Bitcoin-like proof-of-work (PoW) consensus protocols.  

Abstract: Motivated by applications in shared vehicle systems, we study dynamic pricing of resources that relocate over a network of locations. Customers with private willingness-to-pay sequentially request to relocate a resource from one location to another, and a revenue-maximizing service provider sets a price for each request. This problem can be formulated as an infinite horizon stochastic dynamic program, but is quite difficult to solve, as optimal pricing policies may depend on the locations of all resources in the network. We first focus on networks with a hub-and-spoke structure, and we develop a dynamic pricing policy and a performance bound based on a Lagrangian relaxation. This relaxation decomposes the problem over spokes and is thus far easier to solve than the original problem. We analyze the performance of the Lagrangian-based policy and focus on a supply-constrained large network regime in which the number of spokes ($n$) and the number of resources grow at the same rate. We show that the Lagrangian policy loses no more than $O(\sqrt{\ln(n)/n})$ in performance compared to an optimal policy, thus implying asymptotic optimality as $n$ grows large. We also show that no static policy is asymptotically optimal in the large network regime. Finally, we extend the Lagrangian relaxation to provide upper bounds and policies to general networks with multiple, interconnected hubs and spoke-to-spoke connections, and to incorporate relocation times. We also examine the performance of the Lagrangian policy and the Lagrangian relaxation bound on some numerical examples, including examples based on data from RideAustin.

Joint work with David B. Brown (Duke University) and Chen Chen (University of Chicago).

Paper: https://ssrn.com/abstract=3313737