1 of 26

Fatih Erdem Kizilkaya

University of Southern California

Optimal Deterministic

Metric Distortion

2 of 26

Metric Distortion

INPUT

OUTPUT

3 of 26

Metric Distortion — Motivation

4 of 26

Political Spectrum

5 of 26

Political Compass

6 of 26

Metric Distortion — Definition

7 of 26

INPUT

OUTPUT

Metric Distortion — Example

8 of 26

INPUT

OUTPUT

Metric Distortion — Example

9 of 26

Optimal Metric Distortion Problem:

Is there a voting rule with metric distortion 3?

10 of 26

2015

2017

2019

2020

Gkatzelis, Halpern & Shah FOCS

Resolved Positively: sufficient conditions can be met!
the proof is non-constructive and the voting rule itself is a complicated exhaustive search

11 of 26

Voters

12 of 26

Distortion	Voting Rule	Citatition
	SPV	[Kizilkaya & Kempe, 2023]
	PLURALITYVETO	[Kizilkaya & Kempe, 2022]
	PLURALITYMATCHING	[Gkatzelis et al., 2020]
	Weighted Uncovered Set	[Munagala & Wang, 2019]
	Copeland’s Rule, Uncovered Set	[Anshelevich et al., 2015]
	Single Transferable Vote	[Skowron & Elkind, 2017]
	Harmonic Rule	[Anshelevich et al., 2017]
	Ranked Pairs, Schulze’s Rule	[Kempe, 2020]
	Plurality, Borda Count	[Anshelevich et al., 2015]
	Approval, Veto	[Anshelevich et al., 2017]

13 of 26

PLURALITYVETO

Each candidate starts with a score

equal to his number of first-place votes.

These scores are then gradually decreased;

a candidate drops out when his score reaches 0.

One after the other, voters decrement the score of their bottom choice among the standing

candidates, and the last standing

candidate wins.

[Kizilkaya & Kempe, 2022]

14 of 26

PLURALITYVETO

Example:

Each candidate starts with a score

equal to his number of first-place votes.

These scores are then gradually decreased;

a candidate drops out when his score reaches 0.

One after the other, voters decrement the score of their bottom choice among the standing

candidates, and the last standing

candidate wins.

[Kizilkaya & Kempe, 2022]

15 of 26

PLURALITYVETO

Example:

X

Each candidate starts with a score

equal to his number of first-place votes.

These scores are then gradually decreased;

a candidate drops out when his score reaches 0.

One after the other, voters decrement the score of their bottom choice among the standing

candidates, and the last standing

candidate wins.

[Kizilkaya & Kempe, 2022]

16 of 26

PLURALITYVETO

PLURALITYVETO constructs a perfect matching�in the domination graph of the winning candidate!

Each candidate starts with a score

equal to his number of first-place votes.

These scores are then gradually decreased;

a candidate drops out when his score reaches 0.

One after the other, voters decrement the score of their bottom choice among the standing

candidates, and the last standing

candidate wins.

[Kizilkaya & Kempe, 2022]

17 of 26

18 of 26

PLURALITYVETO

Issues with Adoption in Practice

The order of voters changes the outcome. Thus, the voting rule is not anonymous.

( PLURALITYMATCHING is anonymous but not neutral. )

The rule insists on picking a single winner even for elections with obvious ties.

A candidate may never win PLURALITYVETO even though he admits a perfect matching.

Each candidate starts with a score

equal to his number of first-place votes.

These scores are then gradually decreased;

a candidate drops out when his score reaches 0.

One after the other, voters decrement the score of their bottom choice among the standing

candidates, and the last standing

candidate wins.

[Kizilkaya & Kempe, 2022]

19 of 26

PLURALITYVETO

Issues with Adoption in Practice

Each candidate starts with a score

equal to his number of first-place votes.

These scores are then gradually decreased;

a candidate drops out when his score reaches 0.

One after the other, voters decrement the score of their bottom choice among the standing

candidates, and the last standing

candidate wins.

[Kizilkaya & Kempe, 2022]

The order of voters changes the outcome. Thus, the voting rule is not anonymous.

( PLURALITYMATCHING is anonymous but not neutral. )

The rule insists on picking a single winner even for elections with obvious ties.

A candidate may never win PLURALITYVETO even though he admits a perfect matching.

20 of 26

When to Call It a Draw?

PLURALITYVETO

Theorem: No voting rule without ties can be both anonymous & neutral.

[Smith, 1973; Moulin, 1983]

21 of 26

When to Call It a Draw?

PLURALITYVETO

Theorem: No voting rule without ties can be both anonymous & neutral.

[Smith, 1973; Moulin, 1983]

22 of 26

PLURALITYVETO

Each candidate starts with a score

equal to his number of first-place votes.

These scores are then gradually decreased;

a candidate drops out when his score reaches 0

but only if there is still a voter who opposes him.

One after the other, voters decrement the score of their bottom choice among the standing

candidates, and the last standing

candidate(s) win.

w/ Ties

23 of 26

A Practical Voting Rule with �Optimal Metric Distortion

VETOBYCONSUMPTION by Ianovski & Kondratev [2021] picking a candidate from the proportional veto core [Moulin, 1981] is essentially the same rule!

PLURALITYVETO

SIMULTANEOUS

24 of 26

A Practical Voting Rule with �Optimal Metric Distortion

PLURALITYVETO

SIMULTANEOUS

SPV guarantees…

25 of 26

Other Objectives

[Kizilkaya & Kempe, in submission]

26 of 26

Metric Distortion Framework

allows for a finer grained comparison of existing voting rules
motivated the discovery of theoretically appealing voting rules:

Weighted Uncovered Set [Munagala & Wang, 2019]
PLURALITYMATCHING [Gkatzelis et al., 2020]

natural and practical voting rules:

PLURALITYVETO [Kizilkaya & Kempe, 2022]
SPV [Kizilkaya & Kempe, 2023]�

Conclusion