2 citations · 10 across the 20 of their papers we have counts for
23 papers
Axiom Satisfiability of Linear Rewards in Alignment
Soumya Nasipuri, Sayak Ray Chowdhury, Sanjukta Roy
Learning from human preference data is the dominant route to aligning language models with human values. In linear social choice, where rewards are linear in a fixed feature repres…
Menu Selection: A Computational Approach to Minimizing Food Waste
Haris Aziz, Nicholas Mattei, Shivika Narang +1
We introduce a novel collective decision making problem that captures the ubiquitous issue of ordering food to cater for varied dietary preferences and requirements. Our settings i…
Complexity of Eliminating (Majority) Illusion in Directed Networks
Sougata Jana, Sanjukta Roy
We study illusion elimination problems on directed social networks where each vertex is colored either red or blue. A vertex is under \textit{majority illusion} if it has more red…
Fair Societies: Algorithms for House Allocations
Hadi Hosseini, Sanjukta Roy, Aditi Sethia
House Allocations concern with matchings involving one-sided preferences, where houses serve as a proxy encoding valuable indivisible resources (e.g. organs, course seats, subsidiz…
Algorithms for Stable Roommate with Externalities
Jing Leng, Sanjukta Roy
In the roommate matching model, given a set of 2n agents and n rooms, we find an assignment of a pair of agents to a room. Although the roommate matching problem is well studied, t…
FPT-Approximability of Stable Matching Problems
Jiehua Chen, Sanjukta Roy, Sofia Simola
We study parameterized approximability of three optimization problems related to stable matching: (1) Min-BP-SMI: Given a stable marriage instance and a number k, find a size-at-le…
Quantile agent utility and implications to randomized social choice
Ioannis Caragiannis, Fabian Frank, Sanjukta Roy
We initiate a novel direction in randomized social choice by proposing a new definition of agent utility for randomized outcomes. Each agent has a preference over all outcomes and…
Strategyproof Matching of Roommates and Rooms
Hadi Hosseini, Shivika Narang, Sanjukta Roy
We initiate the study of matching roommates and rooms wherein the preferences of agents over other agents and rooms are complementary and represented by Leontief utilities. In this…
Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning
Hadi Hosseini, Sanjukta Roy, Duohan Zhang
Two-sided matching markets describe a large class of problems wherein participants from one side of the market must be matched to those from the other side according to their prefe…
Eliminating Majority Illusion is Easy
Jack Dippel, Max Dupré la Tour, April Niu +2
Majority Illusion is a phenomenon in social networks wherein the decision by the majority of the network is not the same as one's personal social circle's majority, leading to an i…
The Degree of Fairness in Efficient House Allocation
Hadi Hosseini, Medha Kumar, Sanjukta Roy
The classic house allocation problem is primarily concerned with finding a matching between a set of agents and a set of houses that guarantees some notion of economic efficiency (…
Gerrymandering Planar Graphs
Jack Dippel, Max Dupré la Tour, April Niu +2
We study the computational complexity of the map redistricting problem (gerrymandering). Mathematically, the electoral district designer (gerrymanderer) attempts to partition a wei…
Maximizing Social Welfare in Score-Based Social Distance Games
Robert Ganian, Thekla Hamm, Dušan Knop +3
Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function that t…
Maximizing Social Welfare in Score-Based Social Distance Games
Robert Ganian, Thekla Hamm, Dušan Knop +3
Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function u that too…
Optimal Seat Arrangement: What Are the Hard and Easy Cases?
Esra Ceylan, Jiehua Chen, Sanjukta Roy
We study four NP-hard optimal seat arrangement problems [Bodlaender et al., 2020a], which each have as input a set of n agents, where each agent has cardinal preferences over other…
Degreewidth: a New Parameter for Solving Problems on Tournaments
Tom Davot, Lucas Isenmann, Sanjukta Roy +1
In the paper, we define a new parameter for tournaments called degreewidth which can be seen as a measure of how far is the tournament from being acyclic. The degreewidth of a tour…
Hedonic Games With Friends, Enemies, and Neutrals: Resolving Open Questions and Fine-Grained Complexity
Jiehua Chen, Gergely Csáji, Sanjukta Roy +1
We investigate verification and existence problems for prominent stability concepts in hedonic games with friends, enemies, and optionally with neutrals [8, 16]. We resolve several…
Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule
Jiehua Chen, Sanjukta Roy
Answering an open question by Betzler et al. [Betzler et al., JAIR'13], we resolve the parameterized complexity of the multi-winner determination problem under two famous represent…
Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space
Jiehua Chen, Sanjukta Roy
We investigate the Euclidean -Dimensional Stable Roommates problem, which asks whether a given set~ of points from the 2-dimensional Euclidean space can be partit…
Gerrymandering on graphs: Computational complexity and parameterized algorithms
Sushmita Gupta, Pallavi Jain, Fahad Panolan +2
Partitioning a region into districts to favor a particular candidate or a party is commonly known as gerrymandering. In this paper, we investigate the gerrymandering problem in gra…
Fractional Matchings under Preferences: Stability and Optimality
Jiehua Chen, Sanjukta Roy, Manuel Sorge
We thoroughly study a generalized version of the classic Stable Marriage and Stable Roommates problems where agents may share partners. We consider two prominent stability concepts…
On the (Parameterized) Complexity of Almost Stable Marriage
Sushmita Gupta, Pallavi Jain, Sanjukta Roy +2
In the Stable Marriage problem. when the preference lists are complete, all agents of the smaller side can be matched. However, this need not be true when preference lists are inco…
Balanced Stable Marriage: How Close is Close Enough?
Sushmita Gupta, Sanjukta Roy, Saket Saurabh +1
The Balanced Stable Marriage problem is a central optimization version of the classic Stable Marriage problem. Here, the output cannot be an arbitrary stable matching, but one that…