Weekly research seminar

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...

2020-03-05, 10:15, 4050

Michał Godziszewski (Instytut Informatyki, UW)

For a given election E=(V,C) the preferences \{\leq_i\}_{i \in V} of voters are single-peaked when, intuitively speaking, a single issue dominates their formation. This single dominating issue is normally represented by a one-dimensional real axis and each voter is characterized by a single point on...

2020-01-30, 10:15, 4050

Piotr Skowron (Instytut Informatyki, UW)

**Proportionality and the Limits of Welfarism: Fairness with respect to power**We study two influential voting rules proposed in the 1890s by Phragmen and Thiele, which elect a committee or parliament of k candidates which proportionally represents the voters. Voters provide their preferences by approving an arbitrary number of candidates. Previous work has proposed proportion...

2020-01-23, 10:15, 4050

Piotr Skowron (Instytut Informatyki, UW)

**Proportionality and the Limits of Welfarism**We study two influential voting rules proposed in the 1890s by Phragmen and Thiele, which elect a committee or parliament of k candidates which proportionally represents the voters. Voters provide their preferences by approving an arbitrary number of candidates. Previous work has proposed proportion...

2020-01-09, 10:15, 4050

Gleb Polevoy (Instytut Informatyki, UW)

A number of recent models in the literature studied various versions of the adversarial social network analysis problem. Generally speaking, this problem involves some members of a network---e.g. leaders of a covert network, political activists, or simply privacy-concerned members of the public---at...

2019-12-19, 10:15, 4050

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

**Hyperbolic pseudo-betweenness -- initial proposition**Centrality measures identify nodes that play an important role within the network. Betweenness centrality is interpreted roughly as the fraction of all shortest paths in the network between two nodes that contain the given node. The node is more important, the more shortest paths go through it. T...

2019-10-17, 10:15, 4050

Oskar Skibski (Instytut Informatyki, UW)

**Complexity of Computing the Shapley Value in Games with Externalities**We study the complexity of computing the Shapley value in games with externalities. We focus on two representations based on marginal contribution nets (embedded MC-nets and weighted MC-nets). We show that every embedded/weighted MC-nets rule can be represented as (one or more) graphs and that each ...

2019-09-26, 10:15, 4050

Michał Godziszewski

**Proportionality and Consistency in Judgment Aggregation and Belief Merging**Proportionality of a voting rule can be characterized as the ability to reflect all shades of political opinion of a society within the winning committee. The purpose of our project is to apply the voting theory tools concerning proportionality with respect to the rules which take approval ballots a...