9 papers
Non-Existence of PMMS Allocations and a -PMMS Guarantee for Additive Chores
Xiaohui Bei, Zehan Lin, Shengxin Liu +2
We study pairwise maximin share (PMMS) fairness for indivisible items with additive preferences. We give a polynomial-time reduction from chores to goods that preserves the existen…
Multi-Winner Elections: Justified Representation, Strategyproofness, and Risk-Avoiding Truthfulness
Yizhou Ai, Biaoshuai Tao
We study approval-based multi-winner elections with justified representation (JR) when voters strategically report their ballots. We prove that there does not exist a strategy-proo…
Computational Complexity of Strong and Average Justified Representation
Yizhou Ai, Biaoshuai Tao
We study the approval-based multiwinner election problem where a set of voters cast approval-based ballots to a set of candidates, and we are to select a winner committee c…
Algorithms and Complexity of Influence Maximization on Directed Acyclic Graphs
Panfeng Liu, Biaoshuai Tao
This paper investigates the influence maximization problem under the Independent Cascade(IC) and Linear Threshold (LT) models. While this problem is known to be APX-hard on general…
Likelihood of the Existence of Average Justified Representation
Qishen Han, Biaoshuai Tao, Lirong Xia +2
We study the approval-based multi-winner election problem where voters jointly decide a committee of winners from candidates. We focus on the axiom \emph{average justif…
It's Not All Black and White: Degree of Truthfulness for Risk-Avoiding Agents
Eden Hartman, Erel Segal-Halevi, Biaoshuai Tao
The classic notion of \emph{truthfulness} requires that no agent has a profitable manipulation -- an untruthful report that, for \emph{some} combination of reports of the other age…