Today: COMSOC Video Seminar - Emin Berker and Hannaneh Akrami

[Dominik Peters]

Dear all,

Later today we are meeting for the COMSOC Video Seminar, at 09:00 Pittsburgh time / 15:00 Bonn time (in about 4 hours from now). You can join the meeting via https://meeting.comsocseminar.org. We will hear from Ratip Emin Berker (CMU) and Hannaneh Akrami (Bonn). Abstracts below.

See you soon,

Dominik

on behalf of the organizing committee

Ratip Emin Berker (CMU)

How Many Votes Is a Lie Worth? Measuring Strategyproofness through Resource Augmentation

It is well known, by the Gibbard–Satterthwaite Theorem, that when there are more than two candidates, any non-dictatorial voting rule can be manipulated by untruthful voters.  But how strong is the incentive to manipulate under different voting rules? We suggest measuring the potential advantage of a strategic voter by asking how many copies of their (truthful) vote must be added to the election in order to achieve an outcome as good as their best manipulation. Intuitively, this definition quantifies what a voter can gain by manipulating in comparison to what they would have gained by finding like-minded voters to join the election. The higher the former is, the more incentive a voter will have to manipulate, even when it is computationally costly.

Using this framework, we obtain a principled method to measure and compare the manipulation potential for different voting rules. We analyze and report this potential for well-known and broad classes of social choice functions. In particular, we show that the positional scoring rule with the smallest manipulation potential will always be either Borda Count (if the number of voters outweighs the number of candidates) or Plurality (vice versa). Further, we prove that any rule satisfying a very weak form of majority consistency (and therefore any Condorcet-consistent rule) cannot outperform Plurality, and that any majoritarian Condorcet rule will perform significantly worse. Consequently, out of the voting rules we analyze, Borda Count stands out as the only one with a manipulation potential that does not grow with the number of the voters. By establishing a clear separation between different rules in terms of manipulation potential, our work paves the way for the search for rules that provide voters with minimal incentive to manipulate.

Joint work with Vincent Conitzer, Eden Hartman, Jiayuan Liu, and Caspar Oesterheld

--

Hannaneh Akrami (Bonn)

Achieving EF1 and Epistemic EFX Guarantees Simultaneously

We study the fundamental problem of fairly dividing a set of indivisible goods among agents with additive valuations. Here, envy-freeness up to any good (EFX) is a central fairness notion and resolving its existence is regarded as one of the most important open problems in this area of research. Two prominent relaxations of EFX are envy-freeness up to one good (EF1) and epistemic EFX (EEFX). While allocations satisfying each of these notions individually are known to exist even for general monotone valuations, whether both can be satisfied simultaneously remains open for all instances in which the EFX problem is itself unresolved.

In this work, we show that there always exists an allocation that is both EF1 and EEFX for additive valuations. We introduce a new share-based fairness notion, termed strong EEFX share, which may be of independent interest and which implies EEFX feasibility of bundles. We show that this notion is compatible with EF1, leading to the desired existence result.

This is based on a joint work with Ryoga Mahara, Kurt Mehlhorn, and Nidhi Rathi.