Author name cluster

Tomasz Was

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Complexity of (Non-)Convergence in Iterative Voting

Paul W. Goldberg
Marios Mavronicolas
Tomasz Was

Iterative voting is a well-studied model of repeated decision-making, introduced in 2010 by Meir et al. [19], where strategic voters may repeatedly revise their votes, given information about other voters’ interim votes, before convergence to a stable state where no voter has an incentive to revise. Despite considerable previous convergence and non-convergence results for iterative voting under various voting rules and information and behavioral assumptions in the last 15 years, the computational complexity of detecting convergence and non-convergence has not been explored before. In this work, we present the first such complexity results. Specifically, we establish, as our main results, the NP-completeness of the following two decision problems about plurality elections when an arbitrary group of voters can revise their votes as long as the updates are direct and beneficial for each member of the group: • Does a given election converge to a strong Nash equilibrium within at most ℓ revision steps? We exhibit instances where a strong Nash equilibrium does exist but is unreachable by any number of such steps. • Does a given election create voting cycles of ℓ revision steps? We also prove general results for Pareto efficient voting rules. Specifically, for two voters and three candidates, if in each step a single voter updates their vote using the natural TB heuristic [16], then for every Pareto-efficient voting rule there is no cycle of length more than two. In contrast, when both voters update their votes using the same heuristic simultaneously, and we have𝑚 ≥ 3 candidates, every rule satisfying a slight refinement of Pareto efficiency can end up in a cycle of length𝑚.

PDF

AAMAS Conference 2026 Conference Paper

Outer Diversity of Structured Domains

Piotr Faliszewski
Krzysztof Sornat
Stanislaw Szufa
Tomasz Was

An ordinal preference domain is a subset of preference orders that thevotersareallowedtocastinanelection. Weintroduceandstudy the notion of outer diversity of a domain and evaluate its value for a number of well-known structured domains, such as the singlepeaked, single-crossing, group-separable, and Euclidean ones.

PDF

AAMAS Conference 2026 Conference Paper

Strengthening Proportionality in Temporal Voting

Bradley Phillips
Edith Elkind
Nicholas Teh
Tomasz Was

We study proportional representation in the framework of temporal voting with approval ballots. Prior work adapted basic proportional representation concepts—justified representation (JR), proportional JR (PJR), and extended JR (EJR)—from the multiwinner setting to the temporal setting. Our work introduces and examines ways of going beyond EJR. Specifically, we consider stronger variants of JR, PJR, and EJR, and introduce temporal adaptations of more demanding multiwinner axioms, such as EJR+, full JR (FJR), full proportionalJR(FPJR), andcorestability. Foreachoftheseconcepts, we investigate its existence and study its relationship to existing notions, thereby establishing a rich hierarchy of proportionality concepts. Notably, we show that two of our proposed axioms— EJR+ and FJR—strengthen EJR while remaining satisfiable in every temporal election.

PDF

AAMAS Conference 2025 Conference Paper

Selecting Interlacing Committees

Chris Dong
Martin Bullinger
Tomasz Was
Larry Birnbaum
Edith Elkind

Polarization is a major concern for a well-functioning society. Often, mass polarization of a society is driven by polarizing political representation, even when the latter is easily preventable. The existing computational social choice methods for the task of committee selection are not designed to address this issue. We enrich the standard approach to committee selection by defining two quantitative measures that evaluate how well a given committee interconnects the voters. Maximizing these measures aims at avoiding polarizing committees. While the corresponding maximization problems are NP-complete in general, we obtain efficient algorithms for profiles in the voter-candidate interval domain. Moreover, we analyze the compatibility of our goals with other representation objectives, such as excellence, diversity, and proportionality. We identify tradeoffs between approximation guarantees, and describe algorithms that achieve simultaneous constant-factor approximations.

PDF

ECAI Conference 2024 Conference Paper

Distribution of Chores with Information Asymmetry

Hadi Hosseini
Joshua Kavner
Tomasz Was
Lirong Xia

A well-regarded fairness notion when dividing indivisible chores is envy-freeness up to one item (EF1), which requires that pairwise envy can be eliminated by the removal of a single item. While an EF1 and Pareto optimal (PO) allocation of goods can always be found via well-known algorithms, even the existence of such solutions for chores remains open, to date. We take an epistemic approach utilizing information asymmetry by introducing dubious chores–items that inflict no cost on receiving agents but are perceived costly by others. On a technical level, dubious chores provide a more fine-grained approximation of envy-freeness than EF1. We show that finding allocations with minimal number of dubious chores is computationally hard. Nonetheless, we prove the existence of envy-free and fractional PO allocations for n agents with only 2n−2 dubious chores and strengthen it to n−1 dubious chores in four special classes of valuations. Our experimental analysis demonstrates that often only a few dubious chores are needed to achieve envy-freeness.

Details