Sujoy Sikdar

Sujoy Sikdar

Auto-generated profile, based on publicly available information

Sujoy Sikdar

Rensselaer Polytechnic Institute

Research Focus & Metrics

Academic Career Length

11Years (2016-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
17 July 2019 in Proceedings of the AAAI Conference on Artificial Intelligence
Verified
Journal Article
Open access
PDF file
JWJun Wang
Jun Wang
SSSujoy Sikdar
Sujoy Sikdar
TSTyler Shepherd
Tyler Shepherd
ZZZhibing Zhao
Zhibing Zhao
CJChunheng Jiang
Chunheng Jiang
LXLirong Xia
Lirong Xia
STV and ranked pairs (RP) are two well-studied voting rules for group decision-making. They proceed in multiple rounds, and are affected by how ties are broken in each round. However, the literature is surprisingly vague about how ties should be broken. We propose the first algorithms for computing the set of alternatives that are winners under some tiebreaking mechanism under STV and RP, which is also known as parallel-universes tiebreaking (PUT). Unfortunately, PUT-winners are NP-complete to compute under STV and RP, and standard search algorithms from AI do not apply. We propose multiple DFS-based algorithms along with pruning strategies, heuristics, sampling and machine learning to prioritize search direction to significantly improve the performance. We also propose novel ILP formulations for PUT-winners under STV and RP, respectively. Experiments on synthetic and realworld data show that our algorithms are overall faster than ILP.

17 July 2019 in Proceedings of the AAAI Conference on Artificial Intelligence
Verified
Journal Article
Open access
PDF file
SSSujoy Sikdar
Sujoy Sikdar
SASibel Adalı
Sibel Adalı
LXLirong Xia
Lirong Xia
We extend the Top-Trading-Cycles (TTC) mechanism to select strict core allocations for housing markets with multiple types of items, where each agent may be endowed and allocated with multiple items of each type. In doing so, we advance the state of the art in mechanism design for housing markets along two dimensions: First, our setting is more general than multi-type housing markets (Moulin 1995; Sikdar, Adali, and Xia 2017) and the setting of Fujita et al. (2015). Further, we introduce housing markets with acceptable bundles (HMABs) as a more general setting where each agent may have arbitrary sets of acceptable bundles. Second, our extension of TTC is strict core selecting under the weaker restriction on preferences of CMI-trees, which we introduce as a new domain restriction on preferences that generalizes commonly-studied languages in previous works.

28 May 2019 in arXiv
Verified
Preprint
Open access
PDF file
HLHaoming Li
Haoming Li
SSSujoy Sikdar
Sujoy Sikdar
RVRohit Vaish
Rohit Vaish
JWJunming Wang
Junming Wang
LXLirong Xia
Lirong Xia
CYChaonan Ye
Chaonan Ye
Consider the following problem faced by an online voting platform: A user is provided with a list of alternatives, and is asked to rank them in order of preference using only drag-and-drop operations. The platform's goal is to recommend an initial ranking that minimizes the time spent by the user in arriving at her desired ranking. We develop the first optimization framework to address this problem, and make theoretical as well as practical contributions. On the practical side, our experiments on Amazon Mechanical Turk provide two interesting insights about user behavior: First, that users' ranking strategies closely resemble selection or insertion sort, and second, that the time taken for a drag-and-drop operation depends linearly on the number of positions moved. These insights directly motivate our theoretical model of the optimization problem. We show that computing an optimal recommendation is NP-hard, and provide exact and approximation algorithms for a variety of special cases of the problem. Experimental evaluation on MTurk shows that, compared to a random recommendation strategy, the proposed approach reduces the (average) time-to-rank by up to 50%.

16 January 2019 in arXiv
Verified
Preprint
Open access
PDF file
JWJun Wang
Jun Wang
SSSujoy Sikdar
Sujoy Sikdar
TSTyler Shepherd
Tyler Shepherd
ZZZhibing Zhao
Zhibing Zhao
CJChunheng Jiang
Chunheng Jiang
LXLirong Xia
Lirong Xia
STV and ranked pairs (RP) are two well-studied voting rules for group decision-making. They proceed in multiple rounds, and are affected by how ties are broken in each round. However, the literature is surprisingly vague about how ties should be broken. We propose the first algorithms for computing the set of alternatives that are winners under some tiebreaking mechanism under STV and RP, which is also known as parallel-universes tiebreaking (PUT). Unfortunately, PUT-winners are NP-complete to compute under STV and RP, and standard search algorithms from AI do not apply. We propose multiple DFS-based algorithms along with pruning strategies, heuristics, sampling and machine learning to prioritize search direction to significantly improve the performance. We also propose novel ILP formulations for PUT-winners under STV and RP, respectively. Experiments on synthetic and real-world data show that our algorithms are overall faster than ILP.

7 May 2017 in arXiv
Verified
Preprint
Open access
PDF file
BHBenjamin D. Horne
Benjamin D. Horne
SASibel Adali
Sibel Adali
SSSujoy Sikdar
Sujoy Sikdar
Increasingly people form opinions based on information they consume on online social media. As a result, it is crucial to understand what type of content attracts people's attention on social media and drive discussions. In this paper we focus on online discussions. Can we predict which comments and what content gets the highest attention in an online discussion? How does this content differ from community to community? To accomplish this, we undertake a unique study of Reddit involving a large sample comments from 11 popular subreddits with different properties. We introduce a large number of sentiment, relevance, content analysis features including some novel features customized to reddit. Through a comparative analysis of the chosen subreddits, we show that our models are correctly able to retrieve top replies under a post with great precision. In addition, we explain our findings with a detailed analysis of what distinguishes high scoring posts in different communities that differ along the dimensions of the specificity of topic and style, audience and level of moderation.

23 November 2016 in arXiv
Verified
Preprint
Open access
PDF file
SASibel Adali
Sibel Adali
SSSujoy Sikdar
Sujoy Sikdar
LXLirong Xia
Lirong Xia
We study multi-type housing markets, where there are $p\ge 2$ types of items, each agent is initially endowed one item of each type, and the goal is to design mechanisms without monetary transfer to (re)allocate items to the agents based on their preferences over bundles of items, such that each agent gets one item of each type. In sharp contrast to classical housing markets, previous studies in multi-type housing markets have been hindered by the lack of natural solution concepts, because the strict core might be empty. We break the barrier in the literature by leveraging AI techniques and making natural assumptions on agents' preferences. We show that when agents' preferences are lexicographic, even with different importance orders, the classical top-trading-cycles mechanism can be extended while preserving most of its nice properties. We also investigate computational complexity of checking whether an allocation is in the strict core and checking whether the strict core is empty. Our results convey an encouragingly positive message: it is possible to design good mechanisms for multi-type housing markets under natural assumptions on preferences.