Sujoy Sikdar

AAMAS Conference 2023 Conference Paper

Fairly Dividing Mixtures of Goods and Chores under Lexicographic Preferences

• Hadi Hosseini
• Sujoy Sikdar
• Rohit Vaish
• Lirong Xia

We study fair allocation of indivisible goods and chores among agents with lexicographic preferences—a subclass of additive valuations. In sharp contrast to the goods-only setting, we show that an allocation satisfying envy-freeness up to any item (EFX) could fail to exist for a mixture of objective goods and chores. To our knowledge, this negative result provides the first counterexample for EFX over (any subdomain of) additive valuations. To complement this non-existence result, we identify a class of instances with (possibly subjective) mixed items where an EFX and Pareto optimal allocation always exists and can be efficiently computed. When the fairness requirement is relaxed to maximin share (MMS), we show positive existence and computation for any mixed instance. More broadly, our work examines the existence and computation of fair and efficient allocations both for mixed items as well as chores-only instances, and highlights the additional difficulty of these problems vis-à-vis their goods-only counterparts.

JAIR Journal 2023 Journal Article

Favoring Eagerness for Remaining Items: Designing Efficient, Fair, and Strategyproof Mechanisms

• Xiaoxi Guo
• Sujoy Sikdar
• Lirong Xia
• Yongzhi Cao
• Hanpin Wang

In the assignment problem, the goal is to assign indivisible items to agents who have ordinal preferences, efficiently and fairly, in a strategyproof manner. In practice, first-choice maximality, i.e., assigning a maximal number of agents their top items, is often identified as an important efficiency criterion and measure of agents' satisfaction. In this paper, we propose a natural and intuitive efficiency property, favoring-eagerness-for-remaining-items (FERI), which requires that each item is allocated to an agent who ranks it highest among remaining items, thereby implying first-choice maximality. Using FERI as a heuristic, we design mechanisms that satisfy ex-post or ex-ante variants of FERI together with combinations of other desirable properties of efficiency (Pareto-efficiency), fairness (strong equal treatment of equals and sd-weak-envy-freeness), and strategyproofness (sd-weak-strategyproofness). We also explore the limits of FERI mechanisms in providing stronger efficiency, fairness, or strategyproofness guarantees through impossibility results.

IJCAI Conference 2023 Conference Paper

First-Choice Maximality Meets Ex-ante and Ex-post Fairness

• Xiaoxi Guo
• Sujoy Sikdar
• Lirong Xia
• Yongzhi Cao
• Hanpin Wang

For the assignment problem where multiple indivisible items are allocated to a group of agents given their ordinal preferences, we design randomized mechanisms that satisfy first-choice maximality (FCM), i. e. , maximizing the number of agents assigned their first choices, together with Pareto efficiency (PE). Our mechanisms also provide guarantees of ex-ante and ex-post fairness. The generalized eager Boston mechanism is ex-ante envy-free, and ex-post envy-free up to one item (EF1). The generalized probabilistic Boston mechanism is also ex-post EF1, and satisfies ex-ante efficiency instead of fairness. We also show that no strategyproof mechanism satisfies ex-post PE, EF1, and FCM simultaneously. In doing so, we expand the frontiers of simultaneously providing efficiency and both ex-ante and ex-post fairness guarantees for the assignment problem.

AIJ Journal 2023 Journal Article

Multi resource allocation with partial preferences

• Haibin Wang
• Sujoy Sikdar
• Xiaoxi Guo
• Lirong Xia
• Yongzhi Cao
• Hanpin Wang

We provide efficient, fair, and non-manipulable mechanisms for the multi-type resource allocation problems (MTRAs) and multiple assignment problems where agents have partial preferences over bundles consisting of multiple divisible items. We uncover a natural reduction from multiple assignment problems to MTRAs, which preserves the properties of MTRA mechanisms. We extend the well-known random priority (RP) and probabilistic serial (PS) mechanisms to MTRAs with partial preferences as multi-type PS (MPS) and multi-type RP (MRP) and propose a new mechanism, multi-type general dictatorship (MGD), which combines the ideas of MPS and MRP. We show that for the unrestricted domain of partial order preferences, unfortunately, no mechanism satisfies both sd-efficiency and sd-envy-freeness, even as they each satisfy different weaker notions of the desirable properties of efficiency, fairness, and non-manipulability we consider. Notwithstanding this impossibility result, our main message is positive: When agents' preferences are represented by acyclic CP-nets, MRP satisfies ex-post-efficiency, sd-strategyproofness, and upper invariance, while MPS satisfies sd-efficiency, sd-envy-freeness, ordinal fairness, and upper invariance, recovering the properties of RP and PS; the MGD satisfies sd-efficiency, equal treatment of equals, and decomposability under the unrestricted domain of partial preferences. We introduce a natural domain of bundle net preferences, which generalizes previously studied domain restrictions of partial preferences for multiple assignment problems and is incomparable to the domain of acyclic CP-nets. We show that MRP and MPS satisfy all properties of the RP and PS under bundle net preferences as well.

AAMAS Conference 2022 Conference Paper

Anti-Malware Sandbox Games

• Sujoy Sikdar
• Sikai Ruan
• Qishen Han
• Paween Pitimanaaree
• Jeremy Blackthorne
• Bulent Yener
• Lirong Xia

We develop a game theoretic model of malware protection using the state-of-the-art sandbox method, to characterize and compute optimal defense strategies for anti-malware. We model the strategic interaction between developers of malware (M) and anti-malware (AM) as a two player game, where AM commits to a strategy of generating sandbox environments, and M responds by choosing to either attack or hide malicious activity based on the environment it senses. We characterize the condition for AM to protect all its machines, and identify conditions under which an optimal AM strategy can be computed efficiently. For other cases, we provide a quadratically constrained quadratic program (QCQP)-based optimization framework to compute the optimal AM strategy. In addition, we identify a natural and easy to compute strategy for AM, which as we show empirically, achieves AM utility that is close to the optimal AM utility, in equilibrium.

AAMAS Conference 2022 Conference Paper

Designing Efficient and Fair Mechanisms for Multi-Type Resource Allocation

• Xiaoxi Guo
• Sujoy Sikdar
• Haibin Wang
• Lirong Xia
• Yongzhi Cao
• Hanpin Wang

In the multi-type resource allocation problem (MTRA), there are 𝑑 ≥ 2 types of items, and 𝑛 agents who each demand one unit of items of each type and have strict linear preferences over bundles consisting of one item of each type. For MTRAs with indivisible items, we first present an impossibility result that no mechanism can satisfy both sd-efficiency and sd-envy-freeness. We show that this impossibility result is circumvented under the natural assumption of lexicographic preferences by providing lexicographic probabilistic serial (LexiPS) as an extension of the probabilistic serial (PS) mechanism. We also prove that LexiPS satisfies sd-efficiency and sd-envy-freeness. Moreover, LexiPS satisfies sd-weak-strategy proofness when agents are not allowed to misreport their importance orders. The multi-type probabilistic serial cannot deal with indivisible items, but provides a stronger efficiency guarantee under the unrestricted domain of strict linear preferences for divisible items, while also retaining desirable fairness guarantees.

AAAI Conference 2021 Conference Paper

Fair and Efficient Allocations under Lexicographic Preferences

• Hadi Hosseini
• Sujoy Sikdar
• Rohit Vaish
• Lirong Xia

Envy-freeness up to any good (EFX) provides a strong and intuitive guarantee of fairness in the allocation of indivisible goods. But whether such allocations always exist or whether they can be efficiently computed remains an important open question. We study the existence and computation of EFX in conjunction with various other economic properties under lexicographic preferences–a well-studied preference model in artificial intelligence and economics. In sharp contrast to the known results for additive valuations, we not only prove the existence of EFX and Pareto optimal allocations, but in fact provide an algorithmic characterization of these two properties. We also characterize the mechanisms that are, in addition, strategyproof, non-bossy, and neutral. When the efficiency notion is strengthened to rank-maximality, we obtain non-existence and computational hardness results, and show that tractability can be restored when EFX is relaxed to another well-studied fairness notion called maximin share guarantee (MMS).

AAAI Conference 2021 Conference Paper

Necessarily Optimal One-Sided Matchings

• Hadi Hosseini
• Vijay Menon
• Nisarg Shah
• Sujoy Sikdar

We study the classical problem of matching n agents to n objects, where the agents have ranked preferences over the objects. We focus on two popular desiderata from the matching literature: Pareto optimality and rank-maximality. Instead of asking the agents to report their complete preferences, our goal is to learn a desirable matching from partial preferences, specifically a matching that is necessarily Pareto optimal (NPO) or necessarily rank-maximal (NRM) under any completion of the partial preferences. We focus on the topk model in which agents reveal a prefix of their preference rankings. We design efficient algorithms to check if a given matching is NPO or NRM, and to check whether such a matching exists given top-k partial preferences. We also study online algorithms for eliciting partial preferences adaptively, and prove bounds on their competitive ratio.

JAAMAS Journal 2021 Journal Article

Probabilistic serial mechanism for multi-type resource allocation

• Xiaoxi Guo
• Sujoy Sikdar
• Hanpin Wang

Abstract In multi-type resource allocation (MTRA) problems, there are \(d\ge 2\) types of items, and n agents who each demand one unit of items of each type and have strict linear preferences over bundles consisting of one item of each type. For MTRAs with indivisible items, our first result is an impossibility theorem that is in direct contrast to the single type ( \(d=1\) ) setting: no mechanism, the output of which is always decomposable into a probability distribution over discrete assignments (where no item is split between agents), can satisfy both sd-efficiency and sd-envy-freeness. We show that this impossibility result is circumvented under the natural assumption of lexicographic preferences. We provide lexicographic probabilistic serial (LexiPS) as an extension of the probabilistic serial (PS) mechanism for MTRAs with lexicographic preferences, and prove that LexiPS satisfies sd-efficiency and sd-envy-freeness, retaining the desirable properties of PS. Moreover, LexiPS satisfies sd-weak-strategyproofness when agents are not allowed to misreport their importance orders. For MTRAs with divisible items, we show that the existing multi-type probabilistic serial (MPS) mechanism satisfies the stronger efficiency notion of lexi-efficiency, and is sd-envy-free under strict linear preferences and sd-weak-strategyproof under lexicographic preferences. We also prove that MPS can be characterized both by leximin-optimality and by item-wise ordinal fairness, and the family of eating algorithms which MPS belongs to can be characterized by lexi-efficiency.

AAMAS Conference 2021 Conference Paper

Sequential Mechanisms for Multi-type Resource Allocation

• Sujoy Sikdar
• Xiaoxi Guo
• Haibin Wang
• Lirong Xia
• Yongzhi Cao

Several resource allocation problems involve multiple types of resources, with a different agency being responsible for “locally” allocating the resources of each type, while a central planner wishes to provide a guarantee on the properties of the final allocation given agents’ preferences. We study the relationship between properties of the local mechanisms, each responsible for assigning all of the resources of a designated type, and the properties of a sequential mechanism which is composed of these local mechanisms, one for each type, applied sequentially, under lexicographic preferences, a well studied model of preferences over multiple types of resources in artificial intelligence and economics. We show that when preferences are 𝑂-legal, meaning that agents share a common importance order on the types, sequential mechanisms satisfy the desirable properties of anonymity, neutrality, non-bossiness, or Pareto-optimality if and only if every local mechanism also satisfies the same property, and they are applied sequentially according to the order 𝑂. Our main results are that under 𝑂-legal lexicographic preferences, every mechanism satisfying strategyproofness and a combination of these properties must be a sequential composition of local mechanisms that are also strategyproof, and satisfy the same combinations of properties.

AAAI Conference 2020 Conference Paper

Fair Division Through Information Withholding

• Hadi Hosseini
• Sujoy Sikdar
• Rohit Vaish
• Hejun Wang
• Lirong Xia

Envy-freeness up to one good (EF1) is a well-studied fairness notion for indivisible goods that addresses pairwise envy by the removal of at most one good. In the worst case, each pair of agents might require the (hypothetical) removal of a different good, resulting in a weak aggregate guarantee. We study allocations that are nearly envy-free in aggregate, and define a novel fairness notion based on information withholding. Under this notion, an agent can withhold (or hide) some of the goods in its bundle and reveal the remaining goods to the other agents. We observe that in practice, envyfreeness can be achieved by withholding only a small number of goods overall. We show that finding allocations that withhold an optimal number of goods is computationally hard even for highly restricted classes of valuations. In contrast to the worst-case results, our experiments on synthetic and realworld preference data show that existing algorithms for finding EF1 allocations withhold a close-to-optimal amount of information.

AAAI Conference 2020 Conference Paper

Multi-Type Resource Allocation with Partial Preferences

• Haibin Wang
• Sujoy Sikdar
• Xiaoxi Guo
• Lirong Xia
• Yongzhi Cao
• Hanpin Wang

We propose multi-type probabilistic serial (MPS) and multitype random priority (MRP) as extensions of the well-known PS and RP mechanisms to the multi-type resource allocation problems (MTRAs) with partial preferences. In our setting, there are multiple types of divisible items, and a group of agents who have partial order preferences over bundles consisting of one item of each type. We show that for the unrestricted domain of partial order preferences, no mechanism satisfies both sd-efficiency and sd-envy-freeness. Notwithstanding this impossibility result, our main message is positive: When agents’ preferences are represented by acyclic CPnets, MPS satisfies sd-efficiency, sd-envy-freeness, ordinal fairness, and upper invariance, while MRP satisfies ex-postefficiency, sd-strategyproofness, and upper invariance, recovering the properties of PS and RP. Besides, we propose a hybrid mechanism, multi-type general dictatorship (MGD), combining the ideas of MPS and MRP, which satisfies sd-efficiency, equal treatment of equals and decomposability under the unrestricted domain of partial order preferences.

IJCAI Conference 2019 Conference Paper

Equitable Allocations of Indivisible Goods

• Rupert Freeman
• Sujoy Sikdar
• Rohit Vaish
• Lirong Xia

In fair division, equitability dictates that each participant receives the same level of utility. In this work, we study equitable allocations of indivisible goods among agents with additive valuations. While prior work has studied (approximate) equitability in isolation, we consider equitability in conjunction with other well-studied notions of fairness and economic efficiency. We show that the Leximin algorithm produces an allocation that satisfies equitability up to any good and Pareto optimality. We also give a novel algorithm that guarantees Pareto optimality and equitability up to one good in pseudopolynomial time. Our experiments on real-world preference data reveal that approximate envy-freeness, approximate equitability, and Pareto optimality can often be achieved simultaneously.

AAAI Conference 2019 Conference Paper

Mechanism Design for Multi-Type Housing Markets with Acceptable Bundles

• Sujoy Sikdar
• Sibel Adalı
• 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.

IJCAI Conference 2019 Conference Paper

Minimizing Time-to-Rank: A Learning and Recommendation Approach

• Haoming Li
• Sujoy Sikdar
• Rohit Vaish
• Junming Wang
• Lirong Xia
• 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 the Amazon Mechanical Turk platform 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%.

AAAI Conference 2019 Conference Paper

Practical Algorithms for Multi-Stage Voting Rules with Parallel Universes Tiebreaking

• Jun Wang
• Sujoy Sikdar
• Tyler Shepherd
• Zhibing Zhao
• Chunheng Jiang
• 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, PUTwinners 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.

IJCAI Conference 2018 Conference Paper

Optimal Multi-Attribute Decision Making in Social Choice Problems

• Sujoy Sikdar

My thesis solves problems of decision making when alternatives are characterized by multiple attributes, under natural restrictions on agents’ preferences that are motivated by practical and cognitive considerations. Computing optimal decisions in these settings is often hard in general. Fortunately, agents’ preferences often have some natural structure, which have been studied in cognitive psychology literature. This makes several important problems tractable. I identify cases where such structure accurately models preferences in real world data, and provide efficient mechanisms to compute optimal outcomes for important social choice problems with theoretical guarantees.

AAMAS Conference 2017 Conference Paper

Condorcet Consistent Bundling with Social Choice

• Shreyas Sekar
• Sujoy Sikdar
• Lirong Xia

AAAI Conference 2017 Conference Paper

Mechanism Design for Multi-Type Housing Markets

• Sujoy Sikdar
• Sibel Adali
• Lirong Xia

We study multi-type housing markets, where there are p ≥ 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.

AAMAS Conference 2017 Conference Paper

Optimal Decision Making with CP-nets and PCP-nets

• Sujoy Sikdar
• Sibel Adali
• Lirong Xia