10 papers
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…
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…
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…