ACAC '21

Abstract:
We survey some recent results on 2-edge and 2-vertex connectivity in directed graphs. Despite being complete analogs of the corresponding notions on undirected graphs, in digraphs 2-connectivity has a much richer and more complicated structure. For undirected graphs it has been known for over 40 years how to compute all bridges, articulation points, 2-edge- and 2-vertex-connected components in linear time, by simply using depth first search. In the case of digraphs, however, the very same problems have been much more challenging and have been tackled only very recently.

Short bio:

Abstract: In a decentralized system with m machines, we study the selfish scheduling problem where each user strategically chooses which machine to use. Each machine incurs a cost, which is a function of the total load assigned to it, and some cost-sharing mechanism distributes this cost among the machine's users. The users choose a machine aiming to minimize their own share of the cost, so the cost-sharing mechanism induces a game among them. We approach this problem from the perspective of a designer who can select which cost-sharing mechanism to use, aiming to minimize the price of anarchy (PoA) of the induced games.
Recent work introduced the class of "resource-aware" cost-sharing mechanisms, whose decisions can depend on the set of machines in the system, but are oblivious to the total number of users. These mechanisms can guarantee low PoA bounds for instances where the cost functions of the machines are all convex or concave, but can suffer from very high PoA for cost functions that deviate from these families. In this paper we show that if we enhance the class of resource-aware mechanisms with some prior information regarding the users, then they can achieve low PoA for a much more general family of cost functions. We first show that, as long as the mechanism knows just two of the participating users, then it can assign special roles to them and ensure a constant PoA. We then extend this idea to settings where the mechanism has access to the probability with which each user is present in the system. For all these instances, we provide a mechanism that achieves an expected PoA that is logarithmic in the expected number of users.

Abstract: We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers and, therefore, a mechanism in our setting is an algorithm that takes as input the reported---rather than the true---values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria. We focus on two relaxations of envy-freeness, namely envy-freeness up to one good} (EF1), and envy-freeness up to any good (EFX), and we positively answer the above question. In particular, we study two algorithms that are known to produce such allocations in the non-strategic setting: Round-Robin (EF1 allocations for any number of agents) and a cut and choose algorithm of Plaut and Roughgarden (EFX allocations for two agents). For Round-Robin we show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, while for the algorithm of Plaut and Roughgarden we show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting! Further, we show that a weaker version of the latter result holds for any mechanism for two agents that always has pure Nash equilibria which all induce EFX allocations.

Abstract: We consider $k$-Facility Location games, where $n$ strategic agents report their locations on the real line, and a mechanism maps them to $k \ge 2$ facilities. Each agent seeks to minimize her distance to the nearest facility. We are interested in (deterministic or randomized) strategyproof mechanisms without payments that achieve a reasonable approximation ratio to the optimal social cost of the agents. To circumvent the inapproximability of $k$-Facility Location by deterministic strategyproof mechanisms, we restrict our attention to perturbation stable instances. An instance of $k$-Facility Location on the line is $\gamma$-perturbation stable (or simply, $\gamma$-stable), for some $\gamma \ge 1$, if the optimal agent clustering is not affected by moving any subset of consecutive agent locations closer to each other by a factor at most $\gamma$. We show that the optimal solution is strategyproof in $(2+\sqrt{3})$-stable instances whose optimal solution does not include any singleton clusters, and that allocating the facility to the agent next to the rightmost one in each optimal cluster (or to the unique agent, for singleton clusters) is strategyproof and $(n-2)/2$-approximate for $5$-stable instances (even if their optimal solution includes singleton clusters). On the negative side, we show that for any $k \ge 3$ and any $\delta > 0$, there is no deterministic anonymous mechanism that achieves a bounded approximation ratio and is strategyproof in $(\sqrt{2}-\delta)$-stable instances. We also prove that allocating the facility to a random agent of each optimal cluster is strategyproof and $2$-approximate in $5$-stable instances. To the best of our knowledge, this is the first time that the existence of deterministic (resp. randomized) strategyproof mechanisms with a bounded (resp. constant) approximation ratio is shown for a large and natural class of $k$-Facility Location instances.

Abstract: Blame attribution is one of the key aspects of accountable decision making, as it provides means to quantify the responsibility of an agent for a decision making outcome. In this paper, we study blame attribution in the context of cooperative multi-agent sequential decision making. As a particular setting of interest, we focus on cooperative decision making formalized by Multi-Agent Markov Decision Processes (MMDP), and we analyze different blame attribution methods derived from or inspired by existing concepts in cooperative game theory. We formalize desirable properties of blame attribution in the setting of interest, and we analyze the relationship between these properties and the studied blame attribution methods. Interestingly, we show that some of the well known blame attribution methods, such as Shapley value, are not performance-incentivizing, while others, such as Banzhaf index, may over-blame agents. To mitigate these value misalignment and fairness issues, we introduce a novel blame attribution method, unique in the set of properties it satisfies, which trade-offs explanatory power (by under-blaming agents) for the aforementioned properties. We further show how to account for uncertainty about agents' decision making policies, and we experimentally: a) validate the qualitative properties of the studied blame attribution methods, and b) analyze their robustness to uncertainty.

Abstract: Potential games are arguably one of the most important and widely studied classes of normal form games. They define the archetypal setting of multi-agent coordination as all agent utilities are perfectly aligned with each other via a common potential function. Can this intuitive framework be transplanted in the setting of Markov Games? What are the similarities and differences between multi-agent coordination with and without state dependence? We present a novel definition of Markov Potential Games (MPG) that generalizes prior attempts at capturing complex stateful multi-agent coordination. Counter-intuitively, insights from normal-form potential games do not carry over as MPGs can consist of settings where state-games can be zero-sum games. In the opposite direction, Markov games where every state-game is a potential game are not necessarily MPGs. Nevertheless, MPGs showcase standard desirable properties such as the existence of deterministic Nash policies. In our main technical result, we prove polynomial convergence of independent policy gradient (and its stochastic variant) to Nash policies by adapting recent gradient dominance property arguments developed for single agent MDPs to multi-agent learning settings.

Abstract: We focus on min-max optimization in team zero-sum games. These are games that do not satisfy the minimax theorem and have a duality gap. We show that convergence to a Nash Equilibrium is impossible using Gradient Descent Ascent (GDA), its optimistic variant, extra gradient etc. The key observation is that the Nash Equilibrium might be a saddle point of the underlying optimization landscape. Using techniques from control theory, we complement our negative results by designing a modified GDA that converges locally to Nash equilibria.

Abstract: A recent line of research focuses on the study of stochastic multi-armed bandits (MAB), in the case where temporal correlations of specific structure are imposed between the player's actions and the reward distributions of the arms (see, e.g., [Kleinberg and Immorlica, 2018]). These correlations lead to (sub-)optimal solutions that exhibit interesting dynamical patterns -- a phenomenon that yields new challenges both from an algorithmic as well as a learning perspective. In this work, we extend the above direction to a combinatorial semi-bandit setting and study a variant of stochastic MAB, where arms are subject to matroid constraints and each arm becomes unavailable (blocked) for a fixed number of rounds after each play. A natural common generalization of the state-of-the-art for blocking bandits, and that for matroid bandits, only guarantees a $1/2$-approximation for general matroids. In this paper we develop the novel technique of correlated (interleaved) scheduling, which allows us to obtain a polynomial-time $(1 - 1/e)$-approximation algorithm (asymptotically and in expectation) for any matroid. Along the way, we discover an interesting connection to a variant of Submodular Welfare Maximization, for which we provide (asymptotically) matching upper and lower approximability bounds. In the case where the mean arm rewards are unknown, our technique naturally decouples the scheduling from the learning problem, and thus allows to control the $(1-1/e)$-approximate regret of a UCB-based adaptation of our online algorithm.

Abstract: We consider the problem of computing a (pure) Bayes-Nash equilibrium in the first-price auction with continuous value distributions and discrete bidding space. We prove that when bidders have independent subjective prior beliefs about the value distributions of the other bidders, computing an epsilon-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete.

Abstract: We study the computational complexity of computing solutions for the straight-cut and square-cut pizza sharing problems. We show that finding an approximate solution is PPA-hard for the straight-cut problem, and PPA-complete for the square-cut problem, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. Our PPA-hardness results apply even when all mass distributions are unions of non-overlapping squares, and our FIXP-hardness result applies even when all mass distributions are unions of weighted squares and right-angled triangles. We also show that decision variants of the square-cut problem are hard: we show that the approximate problem is NP-complete, and the exact problem is ETR-complete.

Abstract: The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in d dimensions.

Abstract:
In 1979, Hylland and Zeckhauser gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties -- it is incentive compatible in the large and produces an allocation that is Pareto optimal -- and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalent and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following results.

• - A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., when the agent's utilities come from a bi-valued set.
• - In general, there are instances that have only irrational equilibria.
• - Computing an exact equilibrium solution is in FIXP.
• - Computing an approximate equilibrium is PPAD-complete, and this holds even for 4-valued utilities.
• - Computing an equilibrium that maximizes approximately the social welfare (the weight of the matching) within a certain contant factor is NP-hard.

The talk is based on joint works with Vijay Vazirani, and Thomas Chen, Xi Chen and Binghui Peng.

Bio:

Abstract:
Disease-associated nucleotides lie primarily in non-coding regions, increasing the urgency of understanding how gene-regulatory circuitry impacts human disease. To address this challenge, we generate tran-scriptional and epigenomic maps of 823 human tissues, 1500 individuals, and 7.5 million single cells. We link variants to target genes, upstream regulators, cell types of action, and perturbed pathways, and predict causal genes and regions to provide unbiased views of disease mechanisms, sometimes re-shaping our understanding. We find that Alzheimer’s variants act primarily through immune processes, rather than neuronal processes, and the strongest genetic association with obesity acts via energy storage/dissipation rather than appetite/exercise decisions. We combine single-cell profiles, tissue-level variation, and genetic variation across healthy and diseased individuals to deconvolve bulk profiles into single-cell profiles, to recognize changes in cell type proportion associated with disease and aging, to partition genetic effects in-to the individual cell typeswhere they act, and to recognize cell-type-specific and disease-associated somatic mutations in exonic regions indicative of mosaicism. We expand these methods to electronic health records to recognize meta-phenotypes associated with combinations of clinical notes, prescriptions, lab tests, and billing codes, to impute missing phenotypes in sparse medical records, and to recognize the mo-lecular pathways underlying complex meta-phenotypes in genotyped individualsby integration of molecular phenotypes imputed in disease-relevant cell types. Lastly, we develop programmable and modular technologies for manipulating these pathways by high-throughput reporter assays, genome editing,and gene targeting in human cells and mice, demonstrating tissue-autonomous therapeutic avenues in Alzheimer’s, obesity, and cancer. These results provide a roadmap for translating genetic findings into mechanistic insights and ultimately new therapeutic avenues for complex disease and cancer.
Bio:

Abstract: Approximate pattern matching is a natural and well-studied problem on strings: Given a text T, a pattern P, and a threshold k, find (the starting positions of) all substrings of T that are at distance at most k from P. We consider the two most fundamental string metrics: the Hamming distance and the edit distance. Under the Hamming distance, we search for substrings of T that have at most k mismatches with P, while under the edit distance, we search for substrings of T that can be transformed to P with at most k edits. Exact occurrences of P in T have a very simple structure: If we assume for simplicity that $|T| \le 3|P|/2$ and trim T so that P occurs both as a prefix and as a suffix of T, then both P and T are periodic with a common period. However, an analogous characterization for the structure of occurrences with up to k mismatches was proved only recently by Bringmann et al. [SODA'19]: Either there are $O(k^2)$ k-mismatch occurrences of P in T, or both P and T are at Hamming distance $O(k)$ from strings with a common period $O(m/k)$. We tighten this characterization by showing that there are $O(k)$ k-mismatch occurrences in the case when the pattern is not (approximately) periodic, and we lift it to the edit distance setting, where we tightly bound the number of k-edit occurrences by $O(k^2)$ in the non-periodic case. Our proofs are constructive and let us obtain a unified framework for approximate pattern matching for both considered distances. We showcase the generality of our framework with results for the fully-compressed setting (where T and P are given as a straight-line programs) and for the dynamic setting (where we extend a data structure of Gawrychowski et al. [SODA'18]).
A longer abstract can be found here: https://arxiv.org/pdf/2004.08350.pdf.
This paper was presented in FOCS 2020.

Abstract: TBA

Abstract: We present new, faster pseudopolynomial time algorithms for the $k$-Subset Sum problem, defined as follows: given a set $Z$ of $n$ positive integers and $k$ targets $t_1, \ldots, t_k$, determine whether there exist $k$ disjoint subsets $Z_1,\dots,Z_k \subseteq Z$, such that $\Sigma(Z_i) = t_i$, for $i = 1, \ldots, k$. Assuming $t = \max \{ t_1, \ldots, t_k \}$ is the maximum among the given targets, a standard dynamic programming approach based on Bellman's algorithm can solve the problem in $O(n t^k)$ time. We build upon recent advances on extsc{Subset Sum} due to Koiliaris and Xu [Koil19] and Bringmann [Brin17] in order to provide faster algorithms for $k$-Subset Sum. We devise two algorithms: a deterministic one of time complexity $ \tilde{O}(n^{k / (k+1)} t^k)$ and a randomised one of $ \tilde{O}(n + t^k)$ complexity. We further demonstrate how these algorithms can be used in order to cope with variations of $k$-Subset Sum, namely Subset Sum Ratio, $k$-Subset Sum Ratio and Multiple Subset Sum.

Abstract: We will review recent work on Quantum Machine Learning and discuss the prospects and challenges of applying this new exciting computing paradigm to machine learning applications.

Bio:

Abstract: In this talk, we introduce the largest connected subgraph game, played on a graph G. In each round, Alice first colours an uncoloured vertex of G red, and then, Bob colours an uncoloured vertex of G blue, with all vertices initially uncoloured. Once all the vertices are coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph of G whose order is greater than the order of any blue (red, resp.) connected subgraph of G. We first prove that Bob can never win this game, and define a large class of graphs (called reflection graphs) in which the game is a draw. We then show that determining the outcome of the game is PSPACE-complete, even in bipartite graphs of small diameter, and that the problem of recognising reflection graphs is GI-hard. We also prove that the game is a draw in paths if and only if the path is of even order or has at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd length. Lastly, we give a linear time algorithm that determines the outcome of the game in cographs.
This is a joint work with Julien Bensmail, Fionn Mc Inerney, and Nicolas Nisse.

Abstract: We consider $(n,f)$-evacuation on a circle, an evacuation problem of a hidden exit on the perimeter of a unit radius circle for $n>1$ robots, $f$ of which are faulty. All the robots start at the center of the circle and move with maximum speed~1. Robots must first find the exit and then move there to evacuate in minimum time. The problem is considered complete when all the honest robots know the correct position of the exit and the last honest robot has evacuated through the exit. During the search, robots can communicate wirelessly. We focus on symmetric-persistent algorithms, that is, algorithms in which all robots move directly to the circumference, start searching the circle moving in the same direction (cw or ccw), and do not stop moving around the circle before receiving information about the exit. We study the case of $(n,1)$ and $(n,2)$ evacuation. We first prove a lower bound of $1+\frac{4\pi}{n}+2\sin(\frac{\pi}{2}-\frac{\pi}{n})$ for one faulty robot even a crash-faulty one. We also observe an almost matching upper bound obtained by means of an earlier search algorithm. We finally study the case with two Byzantine robots and we provide an algorithm that achieves evacuation in time at most $3+\frac{6\pi}{n}$ , for $n \geq 9$, or at most $3+\frac{6\pi}{n}+\delta(n)$.

Abstract: Along with high penetration of Electric Vehicles (EVs), charging stations are required to service a large amount of charging requests while accounting for constraints on the station's peak electricity consumption. To this end, a charging station needs to make online charging scheduling decisions often under limited future information. An important challenge relates to the prioritization of EVs that have unknown valuations for different levels of charging services. In this paper, we take into consideration the inability of EV users to express these valuations explicitly. We consider a paradigm where a menu of possible charging schedules and corresponding prices is generated online. By letting the EV users pick their most preferable menu option, the proposed algorithm commits on each EV's charging completion time upon its arrival, achieves a near optimal total weighted charging completion time, and prevents the users from strategically misreporting their preferences, while offering a practical and implementable solution to the problem of EVs - charging station interaction.

Abstract: Many machine learning systems are vulnerable to small perturbations made to inputs either at test time or at training time. This has received much recent interest on the empirical front due to applications where reliability and security are critical. However, theoretical understanding of algorithms that are robust to adversarial perturbations is limited. In this work we focus on Principal Component Analysis (PCA), a ubiquitous algorithmic primitive in machine learning. We formulate a natural robust variant of PCA where the goal is to find a low dimensional subspace to represent the given data with minimum projection error, that is in addition robust to small perturbations. Unlike PCA which is solvable in polynomial time, our formulation is computationally intractable to optimize as it captures a variant of the well-studied sparse PCA objective as a special case. In the talk, I will mainly focus on worst-case approximation algorithms that find constant factor approximations with respect to the bst subspace, in terms of the projection error and the robustness criterion. If time allows, we will also discuss several applications of our PCA formulation.

Abstract: For many learning problems one may not have access to fine grained label information; e.g., an image can be labeled as husky, dog, or even animal depending on the expertise of the annotator. In this work, we formalize these settings and study the problem of learning from such coarse data. Instead of observing the actual labels from a set $\mathcal{Z}$, we observe coarse labels corresponding to a partition of $\mathcal{Z}$ (or a mixture of partitions). Our main algorithmic result is that essentially any problem learnable from fine grained labels can also be learned efficiently when the coarse data are sufficiently informative. We obtain our result through a generic reduction for answering Statistical Queries (SQ) over fine grained labels given only coarse labels. The number of coarse labels required depends polynomially on the information distortion due to coarsening and the number of fine labels $|\mathcal{Z}|$. We also investigate the case of (infinitely many) real valued labels focusing on a central problem in censored and truncated statistics: Gaussian mean estimation from coarse data. We provide an efficient algorithm when the sets in the partition are convex and establish that the problem is NP-hard even for very simple non-convex sets.

Abstract: There have been two separate lines of work on estimating Ising models: (1) estimating them from multiple independent samples under minimal assumptions about the model's interaction matrix; and (2) estimating them from one sample in restrictive settings. We propose a unified framework that smoothly interpolates between these two settings, enabling significantly richer estimation guarantees from one, a few, or many samples. Our main theorem provides guarantees for one-sample estimation, quantifying the estimation error in terms of the metric entropy of a family of interaction matrices. As corollaries of our main theorem, we derive bounds when the model's interaction matrix is a (sparse) linear combination of known matrices, or it belongs to a finite set, or to a high-dimensional manifold. In fact, our main result handles multiple independent samples by viewing them as one sample from a larger model, and can be used to derive estimation bounds that are qualitatively similar to those obtained in the afore-described multiple-sample literature. Our technical approach benefits from sparsifying a model's interaction network, conditioning on subsets of variables that make the dependencies in the resulting conditional distribution sufficiently weak. We use this sparsification technique to prove strong concentration and anti-concentration results for the Ising model, which we believe have applications beyond the scope of this paper.

Abstract: We study the problem of covering and learning sums $S = X_1 +\cdots+X_n$ of independent random variables $X_i$ with unbounded, or even infinite, support. De et al. (2018) at FOCS 2018, showed that the maximum value of the collective support of $X_i$’s necessarily appears in the sample complexity of learning $S$. We bypass this lower bound in the general setting where each variable $X_i$ has decreasing probability mass function and is a different member of some, possibly multi-parameter, exponential family E that satisfies some structural properties. These properties allow E to contain heavy tailed distributions and distributions that are not log-concave.
Our main results in this setting are the following.
(Covering). For every ε > 0, and E that satisfies some structural assumptions, there exists a set L(E, ε) that covers S within ε in total variation distance, such that the size of L(E, ε) depends on some parameters of Ε but it is independent on the size of the support of $X_i$. In particular, the support can be infinite.
(Learning). For every ε > 0, and every k-parameter family Ε that satisfies some structural assumptions, there exists an algorithm with $\tilde{Ο}(k)·poly(1/ε)$ samples that learns a sum of n arbitrary members of E within ε in TV distance. Our results are the first to address the problem of learning sums of independent random variables with unbounded support in a very general setting.