Vignesh Viswanathan

Vignesh Viswanathan, Yair Zick

We study fair allocation of indivisible goods when agents have matroid rank valuations. Our main contribution is a simple algorithm based on the colloquial Yankee Swap procedure that computes provably fair and efficient Lorenz dominating allocations. While there exist polynomial time algorithms to compute such allocations, our proposed method improves on them in two ways. (a) Our approach is easy to understand and does not use complex matroid optimization algorithms as subroutines. (b) Our approach is scalable; it is provably faster than all known algorithms to compute Lorenz dominating allocations. These two properties are key to the adoption of algorithms in any real fair allocation setting; our contribution brings us one step closer to this goal.

Gagan Biradar, Yacine Izza, Elita Lobo et al.

The recent criticisms of the robustness of post hoc model approximation explanation methods (like LIME and SHAP) have led to the rise of model-precise abductive explanations. For each data point, abductive explanations provide a minimal subset of features that are sufficient to generate the outcome. While theoretically sound and rigorous, abductive explanations suffer from a major issue -- there can be several valid abductive explanations for the same data point. In such cases, providing a single abductive explanation can be insufficient; on the other hand, providing all valid abductive explanations can be incomprehensible due to their size. In this work, we solve this issue by aggregating the many possible abductive explanations into feature importance scores. We propose three aggregation methods: two based on power indices from cooperative game theory and a third based on a well-known measure of causal strength. We characterize these three methods axiomatically, showing that each of them uniquely satisfies a set of desirable properties. We also evaluate them on multiple datasets and show that these explanations are robust to the attacks that fool SHAP and LIME.

Vignesh Viswanathan

We consider the problem of dividing a set of indivisible goods among agents with additive valuations. This problem has been studied under various objectives in both the computer science and the operations research literature. Our main contribution is a novel dictator test using this problem, which can separate a dictator from any function sufficiently far from a dictator. We use this test to prove the following hardness results (assuming the unique games conjecture is true): (1) We show that it is NP-hard to approximate the max Nash welfare by a factor better than $\sqrt[3]{\frac{81}{65}} - \varepsilon \approx 1.0761$. This improves on the previous best known inapproximability factor of $\sqrt{\frac87} - \varepsilon \approx 1.069$. (2) We show that it is NP-hard to approximate the maximum budgeted allocation by a factor better than $\frac{243}{227} - \varepsilon \approx 1.07$. This improves on the previous best known inapproximability factor of $\frac{16}{15} - \varepsilon \approx 1.067$. (3) We show that it is NP-hard to approximate the max generalized assignment problem (GAP) by a factor better than $\frac{145}{129} - \varepsilon \approx 1.124$. This improves on the previous best known inapproximability factor of $\frac{11}{10} - \varepsilon \approx 1.10$.

Hadi Hosseini, Justin Payan, Rik Sengupta et al.

The classical house allocation problem involves assigning $n$ houses (or items) to $n$ agents according to their preferences. A key criterion in such problems is satisfying some fairness constraints such as envy-freeness. We consider a generalization of this problem wherein the agents are placed along the vertices of a graph (corresponding to a social network), and each agent can only experience envy towards its neighbors. Our goal is to minimize the aggregate envy among the agents as a natural fairness objective, i.e., the sum of all pairwise envy values over all edges in a social graph. When agents have identical and evenly-spaced valuations, our problem reduces to the well-studied problem of linear arrangements. For identical valuations with possibly uneven spacing, we show a number of deep and surprising ways in which our setting is a departure from this classical problem. More broadly, we contribute several structural and computational results for various classes of graphs, including NP-hardness results for disjoint unions of paths, cycles, stars, or cliques, and fixed-parameter tractable (and, in some cases, polynomial-time) algorithms for paths, cycles, stars, cliques, and their disjoint unions. Additionally, a conceptual contribution of our work is the formulation of a structural property for disconnected graphs that we call separability which results in efficient parameterized algorithms for finding optimal allocations.

Vignesh Viswanathan, Yair Zick

We study the problem of allocating indivisible chores among agents with binary supermodular cost functions. In other words, each chore has a marginal cost of $0$ or $1$ and chores exhibit increasing marginal costs (or decreasing marginal utilities). In this note, we combine the techniques of Viswanathan and Zick (2022) and Barman et al. (2023) to present a general framework for fair allocation with this class of valuation functions. Our framework allows us to generalize the results of Barman et al. (2023) and efficiently compute allocations which satisfy weighted notions of fairness like weighted leximin or min weighted $p$-mean malfare for any $p \ge 1$.

Jenny Hamer, Nicholas Perello, Jake Valladares et al.

Algorithmic recourse is a process that leverages counterfactual explanations, going beyond understanding why a system produced a given classification, to providing a user with actions they can take to change their predicted outcome. Existing approaches to compute such interventions -- known as recourse -- identify a set of points that satisfy some desiderata -- e.g. an intervention in the underlying causal graph, minimizing a cost function, etc. Satisfying these criteria, however, requires extensive knowledge of the underlying model structure, an often unrealistic amount of information in several domains. We propose a data-driven and model-agnostic framework to compute counterfactual explanations. We introduce StEP, a computationally efficient method that offers incremental steps along the data manifold that directs users towards their desired outcome. We show that StEP uniquely satisfies a desirable set of axioms. Furthermore, via a thorough empirical and theoretical investigation, we show that StEP offers provable robustness and privacy guarantees while outperforming popular methods along important metrics.

Cyrus Cousins, Vignesh Viswanathan, Yair Zick

We study the problem of fairly allocating a set of indivisible goods among agents with {\em bivalued submodular valuations} -- each good provides a marginal gain of either $a$ or $b$ ($a < b$) and goods have decreasing marginal gains. This is a natural generalization of two well-studied valuation classes -- bivalued additive valuations and binary submodular valuations. We present a simple sequential algorithmic framework, based on the recently introduced Yankee Swap mechanism, that can be adapted to compute a variety of solution concepts, including max Nash welfare (MNW), leximin and $p$-mean welfare maximizing allocations when $a$ divides $b$. This result is complemented by an existing result on the computational intractability of MNW and leximin allocations when $a$ does not divide $b$. We show that MNW and leximin allocations guarantee each agent at least $\frac25$ and $\frac{a}{b+2a}$ of their maximin share, respectively, when $a$ divides $b$. We also show that neither the leximin nor the MNW allocation is guaranteed to be envy free up to one good (EF1). This is surprising since for the simpler classes of bivalued additive valuations and binary submodular valuations, MNW allocations are known to be envy free up to any good (EFX).

Siddharth Barman, Vignesh Viswanathan

We study a generalization of the classical Hajnal-Szemerédi theorem to vertex-weighted graphs. Given a graph with nonnegative vertex weights, a coloring is called $α$-approximately equitable up to one vertex ($α$-EQ1) if, for each color class, the total weight remaining after removing its maximum-weight vertex is at most $α\geq 1$ times the weight of any other color class. For vertex-weighted graphs with maximum degree $Δ$, we show that there exist instances for which no $k$-coloring is $α$-EQ1 for any $k < \frac{3Δ}{2}$ and $α< \sqrt{2}$. In light of this impossibility, we relax these parameters and establish the following results for any vertex-weighted graph $G$ with maximum degree $Δ$: (1) for any $\varepsilon \in (0,1)$ and all $k \geq (\frac{c}{\varepsilon^2}\ln{\frac{1}{\varepsilon}}) Δ$, there exists a $(1 + \varepsilon)$-EQ1 $k$-coloring of $G$, where $c$ is a fixed constant; and (2) for all $k \ge Δ+ 1$, there exists a $2$-EQ1 $k$-coloring of $G$. Furthermore, such equitable colorings can be computed in polynomial time. En route to our results on equitability under vertex weights, we establish sufficient conditions for the existence of $k$-colorings that are equitable with respect to any given partition of the vertex set. Our coloring results correspond to fairness guarantees in a constrained fair division setting and lead to concentration inequalities for partly dependent random variables.

Vignesh Viswanathan

We consider the problem of partitioning an undirected graph (representing a social network) over $n$ nodes and max degree $Δ$ into $k$ equally sized parts. Each node in the graph, representing an agent, derives utility proportional to the number of their neighbors in their assigned part. Our goal is to find a balanced partitioning that is fair. The two notions of fairness we consider are the core and envy-freeness. A partition is envy-free if no node gains utility from moving to a different part, and a partition is in the core if no set of $n/k$ nodes can deviate to form a new part with all nodes gaining in utility. We show that there exists a balanced partition which is both $O(\max\{\sqrtΔ, k^2\} \ln n)$-approximately envy-free and in the $(k + o(k))$-approximate core. Taken separately, these two guarantees are comparable to (and in some cases, better than) the best known envy-freeness and core guarantees for this problem. Moreover, we show that these desirable partitions can be computed efficiently if we slightly relax the balancedness constraint. In addition, when $k = 2$, we show that a $(1.618 + o(1))$-core exists, and a $(2 + \varepsilon)$-core can be computed in polynomial time. The last two results make progress on two open questions from Li et al. [AAAI, 2023].

Zhengmian Hu, Tong Zheng, Vignesh Viswanathan et al.

Large Language Models (LLMs) have become an indispensable part of natural language processing tasks. However, autoregressive sampling has become an efficiency bottleneck. Multi-Draft Speculative Decoding (MDSD) is a recent approach where, when generating each token, a small draft model generates multiple drafts, and the target LLM verifies them in parallel, ensuring that the final output conforms to the target model distribution. The two main design choices in MDSD are the draft sampling method and the verification algorithm. For a fixed draft sampling method, the optimal acceptance rate is a solution to an optimal transport problem, but the complexity of this problem makes it difficult to solve for the optimal acceptance rate and measure the gap between existing verification algorithms and the theoretical upper bound. This paper discusses the dual of the optimal transport problem, providing a way to efficiently compute the optimal acceptance rate. For the first time, we measure the theoretical upper bound of MDSD efficiency for vocabulary sizes in the thousands and quantify the gap between existing verification algorithms and this bound. We also compare different draft sampling methods based on their optimal acceptance rates. Our results show that the draft sampling method strongly influences the optimal acceptance rate, with sampling without replacement outperforming sampling with replacement. Additionally, existing verification algorithms do not reach the theoretical upper bound for both without replacement and with replacement sampling. Our findings suggest that carefully designed draft sampling methods can potentially improve the optimal acceptance rate and enable the development of verification algorithms that closely match the theoretical upper bound.

Gagan Biradar, Vignesh Viswanathan, Yair Zick

Explaining the decisions of black-box models is a central theme in the study of trustworthy ML. Numerous measures have been proposed in the literature; however, none of them take an axiomatic approach to causal explainability. In this work, we propose three explanation measures which aggregate the set of all but-for causes -- a necessary and sufficient explanation -- into feature importance weights. Our first measure is a natural adaptation of Chockler and Halpern's notion of causal responsibility, whereas the other two correspond to existing game-theoretic influence measures. We present an axiomatic treatment for our proposed indices, showing that they can be uniquely characterized by a set of desirable properties. We also extend our approach to derive a new method to compute the Shapley-Shubik and Banzhaf indices for black-box model explanations. Finally, we analyze and compare the necessity and sufficiency of all our proposed explanation measures in practice using the Adult-Income dataset. Thus, our work is the first to formally bridge the gap between model explanations, game-theoretic influence, and causal analysis.

Vignesh Viswanathan, Omer Lev, Neel Patel et al.

Equilibrium computation in markets usually considers settings where player valuation functions are known. We consider the setting where player valuations are unknown; using a PAC learning-theoretic framework, we analyze some classes of common valuation functions, and provide algorithms which output direct PAC equilibrium allocations, not estimates based on attempting to learn valuation functions. Since there exist trivial PAC market outcomes with an unbounded worst-case efficiency loss, we lower-bound the efficiency of our algorithms. While the efficiency loss under general distributions is rather high, we show that in some cases (e.g., unit-demand valuations), it is possible to find a PAC market equilibrium with significantly better utility.