Weekly research seminar

2021-04-15, 10:15, on-line

Tomasz Wąs (Instytut Informatyki, UW)

**An Axiom System for Feedback Centralities**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 meas...

2021-03-18, 10:15, on-line

Grzegorz Pierczyński (Instytut Informatyki, UW)

**Market-Based Explanations of Collective Decisions**We consider approval-based committee elections, in which a size-k subset of available candidates must be selected given approval sets for each voter, indicating the candidates approved by the voter. A number of axioms capturing ideas of fairness and proportionality have been proposed for this framew...

2021-03-04, 10:15, on-line

Dorota Celińska-Kopczyńska (Instytut Informatyki, UW)

**Discrete Hyperbolic Random Graph Model**The hyperbolic random graph model (HRG) has proven useful in the analysis of scale-free networks, which are ubiquitous in many fields, from social network analysis to biology. However, working with this model is algorithmically and conceptually challenging because of the nature of the distances in t...

Oskar Skibski (Instytut Informatyki, UW)

**Signed Graph Games: Coalitional Games with Friends, Enemies and Allies**We extend the well-known model of graph-restricted games due to Myerson to signed graphs, where the link between any two players may be either positive or negative. Hence, in our model, it is possible to explicitly define not only that some players are friends (as in Myerson’s model) but also that...

Michał Godziszewski (Instytut Informatyki, UW)

**An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections**We study approval-based committee elections for the case where the voters' preferences come from a 2D-Euclidean model. We consider two main issues: First, we ask for the complexity of computing election results. Second, we evaluate election outcomes experimentally, following the visualization te...

Michał Lewandowski i Paweł Kalczyński (Zakład Analizy i Wspomagania Decyzji, SGH, College of Business and Economics, California State University – Fullerton)

We define a new carpooling game (or more generally a task completion game) as an extension of the cost-sharing game and propose optimization algorithms to find stable allocations, i.e. match players to carpools and determine the distance they traveled. The game key features include: coalition size i...

Michał Jaworski (Instytut Informatyki, UW)

**Phragmén Rules for Degressive and Regressive Proportionality**We study two concepts of proportionality in the model of approval-based committee elections. In degressive proportionality small minorities of voters are favored in comparison with the standard linear proportionality. Regressive proportionality, on the other hand, requires that larger subdivisions o...

2020-11-12, 10:15, 4050

Tomasz Wąs (Instytut Informatyki UW)

**PageRank vs. Random Walk Decay Centrality**PageRank is one of the most important measures of node importance. However, multiple methods of manipulating PageRank have been identified. Recently, Random Walk Decay centrality was introduced as a harder to manipulate alternative to PageRank. It has been shown that it retains a vast majority of pr...

2020-10-22, 10:15, 4050

Grzegorz Pierczyński (Intytut Informatyki, UW)

**Proportional Participatory Budgeting with Cardinal Utilities**We study voting rules for participatory budgeting, where a group of voters collectively decides which projects should be funded using a common budget. We allow the projects to have arbitrary costs, and the voters to have arbitrary additive valuations over the projects. We formulate two axioms that g...

2020-10-08, 10:15, on-line

Marcin Dziubiński (Instytut Informatyki, UW)

**Peer selection with external referees**The problem of peer selection is a problem facing a social planner who aims to choose a project of the highest quality from the set of projects submitted by a number of strategic agents. To resolve this problem the planner asks the agents to evaluate the projects and report on their quality. We stud...