Author name cluster

Vignesh Viswanathan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers

2 author rows

AAMAS Conference 2025 Conference Paper

On the Hardness of Fair Allocation under Ternary Valuations

Zack Fitzsimmons
Vignesh Viswanathan
Yair Zick

We study the problem of fair allocation of indivisible items when agents have ternary additive valuations — each agent values each item at some fixed integer values 𝑎, 𝑏, or 𝑐 that are common to all agents. The notions of fairness we consider are max Nash welfare (MNW), when 𝑎, 𝑏, and 𝑐 are non-negative, and max egalitarian welfare (MEW). We show that for any distinct non-negative𝑎, 𝑏, and 𝑐, maximizing Nash welfare is APX-hard — i. e. , the problem does not admit a PTAS unless P = NP. We also show that for any distinct 𝑎, 𝑏, and 𝑐, maximizing egalitarian welfare is APX-hard except for a few cases when 𝑏 = 0 that admit efficient algorithms. These results make significant progress towards completely characterizing the complexity of computing exact MNW allocations and MEW allocations. En route, we resolve open questions left by prior work regarding the complexity of computing MNW allocations under bivalued valuations, and MEW allocations under ternary mixed manna.

PDF

ICLR Conference 2025 Conference Paper

Towards Optimal Multi-draft Speculative Decoding

Zhengmian Hu
Tong Zheng
Vignesh Viswanathan
Ziyi Chen 0002
Ryan A. Rossi
Yihan Wu
Dinesh Manocha
Heng Huang 0001

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.

Details

AAAI Conference 2024 Conference Paper

Axiomatic Aggregations of Abductive Explanations

Gagan Biradar
Yacine Izza
Elita Lobo
Vignesh Viswanathan
Yair Zick

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.

PDF Details DOI

JAAMAS Journal 2024 Journal Article

Graphical house allocation with identical valuations

Hadi Hosseini
Andrew McGregor
Vignesh Viswanathan

Abstract 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, called Graphical House Allocation, 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 the envy value over all edges in a social graph. We focus on graphical house allocation with identical valuations. When agents have identical and evenly-spaced valuations, our problem reduces to the well-studied Minimum Linear Arrangement. 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, cliques, and complete bipartite graphs; we also obtain fixed-parameter tractable (and, in some cases, polynomial-time) algorithms for paths, cycles, stars, cliques, complete bipartite graphs, and their disjoint unions. Additionally, a conceptual contribution of our work is the formulation of a structural property for disconnected graphs that we call splittability, which results in efficient parameterized algorithms for finding optimal allocations.

Details DOI

TMLR Journal 2024 Journal Article

Simple Steps to Success: A Method for Step-Based Counterfactual Explanations

Jenny Hamer
Nicholas Perello
Jason Valladares
Vignesh Viswanathan
Yair Zick

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.

PDF Details

AAMAS Conference 2024 Conference Paper

Tight Approximations for Graphical House Allocation

Hadi Hosseini
Andrew McGregor
Rik Sengupta
Rohit Vaish
Vignesh Viswanathan

The Graphical House Allocation problem asks: how can 𝑛 houses (each with a fixed non-negative value) be assigned to the 𝑛 vertices of an undirected graph 𝐺, so as to minimize the “aggregate local envy”, i. e. , the sum of absolute differences along the edges of 𝐺? This problem generalizes the classical Minimum Linear Arrangement problem, as well as the well-known House Allocation Problem from Economics, the latter of which has notable practical applications in organ exchanges. Recent work has studied the computational aspects of Graphical House Allocation and observed that the problem is NP-hard and inapproximable even on particularly simple classes of graphs, such as vertex disjoint unions of paths. However, the dependence of any approximations on the structural properties of the underlying graph had not been studied. In this work, we give a complete characterization of the approximability of Graphical House Allocation. We present algorithms to approximate the optimal envy on general graphs, trees, planar graphs, bounded-degree graphs, bounded-degree planar graphs, and bounded-degree trees. For each of these graph classes, we then prove matching lower bounds, showing that in each case, no significant improvement can be attained unless P = NP. We also present general approximation ratios as a function of structural parameters of the underlying graph, such as treewidth; these match the aforementioned tight upper bounds in general, and are significantly better approximations for many natural subclasses of graphs. Finally, we present constant factor approximation schemes for the special classes of complete binary trees and random graphs. Some of the technical highlights of our work are the use of expansion properties of Ramanujan graphs in the context of a classical resource allocation problem, and approximating optimal cuts in binary trees by analyzing the behavior of consecutive runs in bitstrings.

PDF

AAMAS Conference 2023 Conference Paper

Graphical House Allocation

Hadi Hosseini
Justin Payan
Rik Sengupta
Rohit Vaish
Vignesh Viswanathan

The classical house allocation problem involves assigning 𝑛 houses (or items) to𝑛 agents according to their preferences. A key criteria in such problems is satisfying some fairness constraints such as envyfreeness. 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 the envy value 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; we also obtain 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.

PDF

AAMAS Conference 2023 Conference Paper

Relaxations of Envy-Freeness Over Graphs

Justin Payan
Rik Sengupta
Vignesh Viswanathan

In allocating a set of indivisible items among agents, the condition of envy-freeness cannot always be achieved. Envy-freeness up to any good (EFX) and envy-freeness with 𝑘 hidden items (HEF-𝑘) are two compelling relaxations of envy-freeness, which remain elusive in many settings. We study a natural relaxation of these two fairness constraints, where we place the agents on the vertices of a graph, and only require that our allocations satisfy the EFX (resp. HEF) constraint on the edges of the graph. We refer to these allocations as graph-EFX (resp. graph-HEF) or simply 𝐺-EFX (resp. 𝐺-HEF) allocations. We show that, for any graph 𝐺, there always exists a 𝐺-HEF-𝑘 allocation of goods, where 𝑘 is the size of a minimum vertex cover of 𝐺, and this is tight. We show that 𝐺-EFX allocations of goods exist for three different classes of graphs — two of them generalizing the star 𝐾1, 𝑛−1 and the third generalizing the threeedge path 𝑃4. Many of these results extend to allocations of chores as well. Overall, we show several natural settings in which the graph structure helps obtain strong fairness guarantees. Finally, we devise an algorithm tested using Spliddit data, to show that 𝐺-EFX allocations appear to exist for paths 𝑃𝑛, pointing the way towards generalizing our results to even broader families of graphs.

PDF

AAMAS Conference 2023 Conference Paper

Yankee Swap: A Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations

Vignesh Viswanathan
Yair Zick

We study fair allocation of indivisible goods when agent valuations are matroid rank functions (MRFs). 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 fair and efficient allocations for MRF valuations, we improve 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.

PDF

AAMAS Conference 2022 Conference Paper

Moving Target Defense under Uncertainty for Web Applications

Vignesh Viswanathan
Megha Bose
Praveen Paruchuri

Moving target defense (MTD) has emerged as a key technique that can be used in various security applications to reduce the threat of attackers by taking away their ability to perform reconnaissance and exploit vulnerabilities. However, most of the existing research in the field assumes unrealistic access to information about the attacker’s motivations and/or actions when developing MTD strategies. Many of the existing approaches also assume complete knowledge regarding the vulnerabilities of a particular application and how each of these vulnerabilities can be exploited by an attacker. In this work, we propose an algorithm that generates effective MTD strategies for web applications that does not rely on prior knowledge about the attackers. Our approach assumes that the only information the defender receives about its own reward function, is via interaction with the attacker in a repeated game setting. We evaluate our algorithm using data which is mined from the National Vulnerability Database to show that it matches the performance of the state of the art techniques, despite using much less information.

PDF

AAMAS Conference 2021 Conference Paper

Computing using Samples: Theoretical Guarantees with the Direct Learning Approach

Vignesh Viswanathan

Machine learning algorithms in the field of economics and game theory usually involve computing an intermediate valuation function from data samples and using this approximate function to compute desired solution concepts. This approach has several problems ranging from a high sample complexity to a lack of provable guarantees about the final solution. In order to avoid these problems, we explore a new method to learn solution concepts from data: instead of learning an intermediate valuation function, we learn the solution concept directly from the samples. This approach provides an alternative way to approximately learn solution concepts using fewer samples. In addition to this, from our study of using this approach to learn market equilibria, we find that, in a lot of settings, it is easier to prove efficiency and fairness guarantees about the learned solutions.

PDF

AAMAS Conference 2021 Conference Paper

The Price is (Probably) Right: Learning Market Equilibria from Samples

Omer Lev
Neel Patel
Vignesh Viswanathan
Yair Zick

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 learningtheoretic 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.

PDF

IJCAI Conference 2020 Conference Paper

Fighting Wildfires under Uncertainty - A Sequential Resource Allocation Approach

Hau Chan
Long Tran-Thanh
Vignesh Viswanathan

Standard disaster response involves using drones (or helicopters) for reconnaissance and using people on the ground to mitigate the damage. In this paper, we look at the problem of wildfires and propose an efficient resource allocation strategy to cope with both dynamically changing environment and uncertainty. In particular, we propose Firefly, a new resource allocation algorithm, that can provably achieve optimal or near optimal solutions with high probability by first efficiently allocating observation drones to collect information to reduce uncertainty, and then allocate the firefighting units to extinguish fire. For the former, Firefly uses a combination of maximum set coverage formulation and a novel utility estimation technique, and it uses a knapsack formulation to calculate the allocation for the latter. We also demonstrate empirically by using a real-world dataset that Firefly achieves up to 80-90% performance of the offline optimal solution, even with a small amount of drones, in most of the cases.

PDF Details DOI