2 citations · 10 across the 20 of their papers we have counts for
17 papers · 1 filter
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…
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…
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…
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…
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…
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…