12 citations · 21 across the 9 of their papers we have counts for
11 papers
Breaking the Envy Cycle: Best-of-Both-Worlds Guarantees for Subadditive Valuations
Michal Feldman, Simon Mauras, Vishnu V. Narayan +1
We study best-of-both-worlds guarantees for the fair division of indivisible items among agents with subadditive valuations. Our main result establishes the existence of a random a…
Fair Chore Division under Binary Supermodular Costs
Siddharth Barman, Vishnu V. Narayan, Paritosh Verma
We study the problem of dividing indivisible chores among agents whose costs (for the chores) are supermodular set functions with binary marginals. Such functions capture complemen…
Risk-Free Bidding in Complement-Free Combinatorial Auctions
Vishnu V. Narayan, Gautam Rayaprolu, Adrian Vetta
We study risk-free bidding strategies in combinatorial auctions with incomplete information. Specifically, what is the maximum profit that a complement-free (subadditive) bidder ca…
Two Birds With One Stone: Fairness and Welfare via Transfers
Vishnu V. Narayan, Mashbat Suzuki, Adrian Vetta
We study the question of dividing a collection of indivisible goods amongst a set of agents. The main objective of research in the area is to achieve one of two goals: fairness or…
The Speed and Threshold of the Biased Hamilton Cycle Game
Noah Brustle, Sarah Clusiau, Vishnu V. Narayan +3
We show that there is a constant C such that for any , Maker wins the Maker-Breaker Hamilton cycle game in $n+\frac{Cn}{\sqrt{\ln{n}}}…
The Speed and Threshold of the Biased Perfect Matching Game
Noah Brustle, Sarah Clusiau, Vishnu V. Narayan +3
We show that Maker wins the Maker-Breaker perfect matching game in turns when the bias is at least , for any …
Online Coloring and a New Type of Adversary for Online Graph Problems
Yaqiao Li, Vishnu V. Narayan, Denis Pankratov
We introduce a new type of adversary for online graph problems. The new adversary is parameterized by a single integer , which upper bounds the number of connected components th…
One Dollar Each Eliminates Envy
Johannes Brustle, Jack Dippel, Vishnu V. Narayan +2
We study the fair division of a collection of indivisible goods amongst a set of agents. Whilst envy-free allocations typically do not exist in the indivisible goods settin…
The Declining Price Anomaly is not Universal in Multi-Buyer Sequential Auctions (but almost is)
Vishnu V. Narayan, Enguerrand Prebet, Adrian Vetta
The declining price anomaly states that the price weakly decreases when multiple copies of an item are sold sequentially over time. The anomaly has been observed in a plethora of p…
The Matching Augmentation Problem: A -Approximation Algorithm
Joe Cheriyan, Jack Dippel, Fabrizio Grandoni +2
We present a approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost ze…
A 17/12-Approximation Algorithm for 2-Vertex-Connected Spanning Subgraphs on Graphs with Minimum Degree At Least 3
Vishnu V. Narayan
We obtain a polynomial-time 17/12-approximation algorithm for the minimum-cost 2-vertex-connected spanning subgraph problem, restricted to graphs of minimum degree at least 3. Our…