Tomasz Wąs

AAAI Conference 2026 Conference Paper

Diversity of Structured Domains via k-Kemeny Scores

• Piotr Faliszewski
• Krzysztof Sornat
• Stanisław Szufa
• Tomasz Wąs

In the k-Kemeny problem, we are given an ordinal election, i.e., a collection of votes ranking the candidates from best to worst, and we seek the smallest number of swaps of adjacent candidates that ensure that the election has at most k different rankings. We study this problem for a number of structured domains, including the single-peaked, single-crossing, group-separable, and Euclidean ones. We obtain two kinds of results: (1) We show that k-Kemeny remains intractable under most of these domains, even for k=2, and (2) we use k-Kemeny to rank these domains in terms of their diversity.

AAAI Conference 2025 Conference Paper

Distances Between Top-Truncated Elections of Different Sizes

• Piotr Faliszewski
• Jitka Mertlová
• Pierre Nunn
• Stanisław Szufa
• Tomasz Wąs

The map of elections framework is a methodology for visualizing and analyzing election datasets. So far, the framework was restricted to elections that have equal numbers of candidates, equal numbers of voters, and where all the (ordinal) votes rank all the candidates. We extend it to the case of elections of different sizes, where the votes can be top-truncated. We use our results to present a visualization of a large fragment of the Preflib database.

AIJ Journal 2025 Journal Article

Fair distribution of delivery orders

• Hadi Hosseini
• Shivika Narang
• Tomasz Wąs

IJCAI Conference 2024 Conference Paper

Fair Distribution of Delivery Orders

• Hadi Hosseini
• Shivika Narang
• Tomasz Wąs

We initiate the study of fair distribution of delivery tasks among a set of agents wherein delivery jobs are placed along the vertices of a graph. Our goal is to fairly distribute delivery costs (modeled as a submodular function) among a fixed set of agents while satisfying some desirable notions of economic efficiency. We adopt well-established fairness concepts—such as envy-freeness up to one item (EF1) and minimax share (MMS)—to our setting and show that fairness is often incompatible with the efficiency notion of social optimality. Yet, we characterize instances that admit fair and socially optimal solutions by exploiting graph structures. We further show that achieving fairness along with Pareto optimality is computationally intractable. Nonetheless, we design an XP algorithm (parameterized by the number of agents) for finding MMS and Pareto optimal solutions on every tree instance, and show that the same algorithm can be modified to find efficient solutions along with EF1, when such solutions exist. We complement these results by theoretically and experimentally analyzing the price of fairness.

IJCAI Conference 2024 Conference Paper

Guide to Numerical Experiments on Elections in Computational Social Choice

• Niclas Boehmer
• Piotr Faliszewski
• Łukasz Janeczko
• Andrzej Kaczmarczyk
• Grzegorz Lisowski
• Grzegorz Pierczyński
• Simon Rey
• Dariusz Stolicki

We analyze how numerical experiments regarding elections were conducted within computational social choice literature (focusing on papers published in the IJCAI, AAAI, and AAMAS conferences). We analyze the sizes of the studied elections and the methods of generating preference data, thereby making previously hidden standards and practices explicit. In particular, we survey a number of statistical cultures for generating elections and their commonly used parameters.

AIJ Journal 2023 Journal Article

Axiomatic characterization of PageRank

• Tomasz Wąs
• Oskar Skibski

IJCAI Conference 2023 Conference Paper

Diversity, Agreement, and Polarization in Elections

• Piotr Faliszewski
• Andrzej Kaczmarczyk
• Krzysztof Sornat
• Stanisław Szufa
• Tomasz Wąs

We consider the notions of agreement, diversity, and polarization in ordinal elections (that is, in elections where voters rank the candidates). While (computational) social choice offers good measures of agreement between the voters, such measures for the other two notions are lacking. We attempt to rectify this issue by designing appropriate measures, providing means of their (approximate) computation, and arguing that they, indeed, capture diversity and polarization well. In particular, we present "maps of preference orders" that highlight relations between the votes in a given election and which help in making arguments about their nature.

IJCAI Conference 2023 Conference Paper

Fairly Allocating Goods and (Terrible) Chores

• Hadi Hosseini
• Aghaheybat Mammadov
• Tomasz Wąs

We study the fair allocation of mixture of indivisible goods and chores under lexicographic preferences---a subdomain of additive preferences. A prominent fairness notion for allocating indivisible items is envy-freeness up to any item (EFX). Yet, its existence and computation has remained a notable open problem. By identifying a class of instances with "terrible chores", we show that determining the existence of an EFX allocation is NP-complete. This result immediately implies the intractability of EFX under additive preferences. Nonetheless, we propose a natural subclass of lexicographic preferences for which an EFX and Pareto optimal (PO) allocation is guaranteed to exist and can be computed efficiently for any mixed instance. Focusing on two weaker fairness notions, we investigate finding EF1 and Pareto optimal allocations for special instances with terrible chores, and show that MMS and PO allocations can be computed efficiently for any mixed instance with lexicographic preferences.

AAAI Conference 2023 Conference Paper

Properties of Position Matrices and Their Elections

• Niclas Boehmer
• Jin-Yi Cai
• Piotr Faliszewski
• Austen Z. Fan
• Łukasz Janeczko
• Andrzej Kaczmarczyk
• Tomasz Wąs

We study the properties of elections that have a given position matrix (in such elections each candidate is ranked on each position by a number of voters specified in the matrix). We show that counting elections that generate a given position matrix is #P-complete. Consequently, sampling such elections uniformly at random seems challenging and we propose a simpler algorithm, without hard guarantees. Next, we consider the problem of testing if a given matrix can be implemented by an election with a certain structure (such as single-peakedness or group-separability). Finally, we consider the problem of checking if a given position matrix can be implemented by an election with a Condorcet winner. We complement our theoretical findings with experiments.

AAAI Conference 2022 Conference Paper

PageRank for Edges: Axiomatic Characterization

• Natalia Kucharczuk
• Tomasz Wąs
• Oskar Skibski

Edge centrality measures are functions that evaluate the importance of edges in a network. They can be used to assess the role of a backlink for the popularity of a website as well as the importance of a flight in virus spreading. Various node centralities have been translated to apply for edges, including Edge Betweenness, Eigenedge (edge version of Eigenvector centrality), and Edge PageRank. With this paper, we initiate the discussion on the axiomatic properties of edge centrality measures. We do it by proposing an axiomatic characterization of Edge PageRank. Our characterization is the first characterization of any edge centrality measure in the literature.

IJCAI Conference 2022 Conference Paper

Understanding Distance Measures Among Elections

• Niclas Boehmer
• Piotr Faliszewski
• Rolf Niedermeier
• Stanisław Szufa
• Tomasz Wąs

Motivated by putting empirical work based on (synthetic) election data on a more solid mathematical basis, we analyze six distances among elections, including, e. g. , the challenging-to-compute but very precise swap distance and the distance used to form the so-called map of elections. Among the six, the latter seems to strike the best balance between its computational complexity and expressiveness.

IJCAI Conference 2021 Conference Paper

An Axiom System for Feedback Centralities

• Tomasz Wąs
• Oskar Skibski

In recent years, the axiomatic approach to centrality measures has attracted attention in the literature. However, most papers propose a collection of axioms dedicated to one or two considered centrality measures. In result, it is hard to capture the differences and similarities between various measures. In this paper, we propose an axiom system for four classic feedback centralities: Eigenvector centrality, Katz centrality, Katz prestige and PageRank. We prove that each of these four centrality measures can be uniquely characterized with a subset of our axioms. Our system is the first one in the literature that considers all four feedback centralities.

AAAI Conference 2019 Conference Paper

Random Walk Decay Centrality

• Tomasz Wąs
• Talal Rahwan
• Oskar Skibski

We propose a new centrality measure, called the Random Walk Decay centrality. While most centralities in the literature are based on the notion of shortest paths, this new centrality measure stems from the random walk on the network. We provide an axiomatic characterization and show that the new centrality is closely related to PageRank. More in detail, we show that replacing only one axiom, called Lack of Self- Impact, with another one, called Edge Swap, results in the new axiomatization of PageRank. Finally, we argue that Lack of Self-Impact is desirable in various settings and explain why violating Edge Swap may be beneficial and may contribute to promoting diversity in the centrality measure.

AAAI Conference 2018 Conference Paper

An Axiomatization of the Eigenvector and Katz Centralities

• Tomasz Wąs
• Oskar Skibski

Feedback centralities are one of the key classes of centrality measures. They assess the importance of a vertex recursively, based on the importance of its neighbours. Feedback centralities includes the Eigenvector Centrality, as well as its variants, such as the Katz Centrality or the PageRank, and are used in various AI applications, such as ranking the importance of websites on the Internet and most influential users in the Twitter social network. In this paper, we study the theoretical underpinning of the feedback centralities. Specifically, we propose a novel axiomatization of the Eigenvector Centrality and the Katz Centrality based on six simple requirements. Our approach highlights the similarities and differences between both centralities which may help in choosing the right centrality for a specific application.

IJCAI Conference 2018 Conference Paper

Axiomatization of the PageRank Centrality

• Tomasz Wąs
• Oskar Skibski

We propose an axiomatization of PageRank. Specifically, we introduce five simple axioms—Foreseeability, Outgoing Homogeneity, Monotonicity, Merging, and Dummy Node—and show that PageRank is the only centrality measure that satisfies all of them. Our axioms give a new conceptual and theoretical underpinnings of PageRank and show how it differs from other centralities.