Search Results

Documents authored by Elkind, Edith

Document
DOI: 10.4230/LIPIcs.ESA.2024.82
A Lower Bound for Local Search Proportional Approval Voting

Authors: Sonja Kraiczy and Edith Elkind

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Selecting k out of m items based on the preferences of n heterogeneous agents is a widely studied problem in algorithmic game theory. If agents have approval preferences over individual items and harmonic utility functions over bundles - an agent receives ∑_{j = 1}^t1/j utility if t of her approved items are selected - then welfare optimisation is captured by a voting rule known as Proportional Approval Voting (PAV). PAV also satisfies demanding fairness axioms. However, finding a winning set of items under PAV is NP-hard. In search of a tractable method with strong fairness guarantees, a bounded local search version of PAV was proposed [Aziz et al., 2018]. It proceeds by starting with an arbitrary size-k set W and, at each step, checking if there is a pair of candidates a ∈ W, b ̸ ∈ W such that swapping a and b increases the total welfare by at least ε; if yes, it performs the swap. Aziz et al. show that setting ε = n/(k²) ensures both the desired fairness guarantees and polynomial running time. However, they leave it open whether the algorithm converges in polynomial time if ε is very small (in particular, if we do not stop until there are no welfare-improving swaps). We resolve this open question, by showing that if ε can be arbitrarily small, the running time of this algorithm may be super-polynomial. Specifically, we prove a lower bound of Ω(k^{log k}) if improvements are chosen lexicographically. To complement our lower bound, we provide an empirical comparison of two variants of local search - better-response and best-response - on several real-life data sets and a variety of synthetic data sets. Our experiments indicate that, empirically, better response exhibits faster running time than best response.
Cite as

Sonja Kraiczy and Edith Elkind. A Lower Bound for Local Search Proportional Approval Voting. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 82:1-82:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kraiczy_et_al:LIPIcs.ESA.2024.82,
  author =	{Kraiczy, Sonja and Elkind, Edith},
  title =	{{A Lower Bound for Local Search Proportional Approval Voting}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{82:1--82:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.82},
  URN =		{urn:nbn:de:0030-drops-211538},
  doi =		{10.4230/LIPIcs.ESA.2024.82},
  annote =	{Keywords: Computational Social Choice, Committee Elections, Local Search, Fairness}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2024.2
Group Fairness: Multiwinner Voting and Beyond (Invited Talk)

Authors: Edith Elkind

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In multiwinner voting with approval ballots the agents are presented with a set of alternatives, each agent indicates which of these alternatives they approve, and the goal is to select a fixed-size subset of the alternatives, in a way that reflects the voters' preferences. This framework captures a variety of group decision-making scenarios, from choosing a list of speakers for an event to appointing a set of validators in a proof-of-stake blockchain. An important concern in many of these scenarios is group fairness: every sufficiently large group of agents with similar preferences should be represented in the winning set of alternatives. In this talk, we discuss how to formalise this idea and whether the resulting axioms can be satisfied by efficiently computable voting rules. We also discuss extensions of our framework to the more expressive setting of participatory budgeting, where the agents are presented with a slate of projects (which may have different costs) and the goal is to select a subset of projects subject to a budget constraint.
Cite as

Edith Elkind. Group Fairness: Multiwinner Voting and Beyond (Invited Talk). In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{elkind:LIPIcs.ICALP.2024.2,
  author =	{Elkind, Edith},
  title =	{{Group Fairness: Multiwinner Voting and Beyond}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.2},
  URN =		{urn:nbn:de:0030-drops-201459},
  doi =		{10.4230/LIPIcs.ICALP.2024.2},
  annote =	{Keywords: multiwinner voting, participatory budgeting, justified representation}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2023.1
Group Fairness: From Multiwinner Voting to Participatory Budgeting (Invited Talk)

Authors: Edith Elkind

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Many cities around the world allocate a part of their budget based on residents' votes, following a process known as participatory budgeting. It is important to understand which outcomes of this process should be viewed as fair, and whether fair outcomes could be computed efficiently. We summarise recent progress on this topic. We first focus on a special case of participatory budgeting where all candidate projects have the same cost (known as multiwinner voting), formulate progressively more demanding notions of fairness for this setting, and identify efficiently computable voting rules that satisfy them. We then discuss the challenges of extending these ideas to the general model.
Cite as

Edith Elkind. Group Fairness: From Multiwinner Voting to Participatory Budgeting (Invited Talk). In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 1:1-1:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{elkind:LIPIcs.ISAAC.2023.1,
  author =	{Elkind, Edith},
  title =	{{Group Fairness: From Multiwinner Voting to Participatory Budgeting}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{1:1--1:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.1},
  URN =		{urn:nbn:de:0030-drops-193038},
  doi =		{10.4230/LIPIcs.ISAAC.2023.1},
  annote =	{Keywords: multiwinner voting, participatory budgeting, justified representation}
}
Document
DOI: 10.4230/DagRep.11.7.1
Coalition Formation Games (Dagstuhl Seminar 21331)

Authors: Edith Elkind, Judy Goldsmith, Anja Rey, and Jörg Rothe

Published in: Dagstuhl Reports, Volume 11, Issue 7 (2021)

Abstract
There are many situations in which individuals will choose to act as a group, or coalition. Examples include social clubs, political parties, partnership formation, and legislative voting. Coalition formation games are a class of cooperative games where the aim is to partition a set of agents into coalitions, according to some criteria, such as coalitional stability or maximization of social welfare. In our seminar we discussed applications, results, and new directions of research in the field of coalition formation games.
Cite as

Edith Elkind, Judy Goldsmith, Anja Rey, and Jörg Rothe. Coalition Formation Games (Dagstuhl Seminar 21331). In Dagstuhl Reports, Volume 11, Issue 7, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{elkind_et_al:DagRep.11.7.1,
  author =	{Elkind, Edith and Goldsmith, Judy and Rey, Anja and Rothe, J\"{o}rg},
  title =	{{Coalition Formation Games (Dagstuhl Seminar 21331)}},
  pages =	{1--15},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{7},
  editor =	{Elkind, Edith and Goldsmith, Judy and Rey, Anja and Rothe, J\"{o}rg},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.7.1},
  URN =		{urn:nbn:de:0030-drops-155885},
  doi =		{10.4230/DagRep.11.7.1},
  annote =	{Keywords: Coalition Formation, Cooperative Games}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.1
Justified Representation in Multiwinner Voting: Axioms and Algorithms

Authors: Edith Elkind

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
Suppose that a group of voters wants to select k 1 alternatives from a given set, and each voter indicates which of the alternatives are acceptable to her: the alternatives could be conference submissions, applicants for a scholarship or locations for a fast food chain. In this setting it is natural to require that the winning set represents the voters fairly, in the sense that large groups of voters with similar preferences have at least some of their approved alternatives in the winning set. We describe several ways to formalize this idea, and show how to use it to classify voting rules; surprisingly, two voting rules proposed in the XIXth century turn out to play an important role in our analysis.
Cite as

Edith Elkind. Justified Representation in Multiwinner Voting: Axioms and Algorithms. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 1:1-1:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{elkind:LIPIcs.FSTTCS.2017.1,
  author =	{Elkind, Edith},
  title =	{{Justified Representation in Multiwinner Voting: Axioms and Algorithms}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{1:1--1:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.1},
  URN =		{urn:nbn:de:0030-drops-84179},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.1},
  annote =	{Keywords: voting, committee selection, axioms, PAV}
}
Document
DOI: 10.4230/DagRep.2.3.1
Computation and Incentives in Social Choice (Dagstuhl Seminar 12101)

Authors: Edith Elkind, Christian Klamler, Jeffrey S. Rosenschein, and M. Remzi Sanver

Published in: Dagstuhl Reports, Volume 2, Issue 3 (2012)

Abstract
Computational social choice is an active research area that combines tools and techniques of theoretical computer science and AI with those of mathematics, social sciences and economics. The aim of the Dagstuhl Seminar 12101 ``Computation and Incentives in Social Choice'' was to bring together the experts in these areas in order to discuss recent advances in this field and share open problems. This report collects the material presented during the course of the seminar.
Cite as

Edith Elkind, Christian Klamler, Jeffrey S. Rosenschein, and M. Remzi Sanver. Computation and Incentives in Social Choice (Dagstuhl Seminar 12101). In Dagstuhl Reports, Volume 2, Issue 3, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{elkind_et_al:DagRep.2.3.1,
  author =	{Elkind, Edith and Klamler, Christian and Rosenschein, Jeffrey S. and Sanver, M. Remzi},
  title =	{{Computation and Incentives in Social Choice (Dagstuhl Seminar 12101)}},
  pages =	{1--22},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{2},
  number =	{3},
  editor =	{Elkind, Edith and Klamler, Christian and Rosenschein, Jeffrey S. and Sanver, M. Remzi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.3.1},
  URN =		{urn:nbn:de:0030-drops-35322},
  doi =		{10.4230/DagRep.2.3.1},
  annote =	{Keywords: Computational Social Choice, Voting, Incentives, Algorithmic Game Theory}
}
Document
DOI: 10.4230/DagSemProc.10171.1
10171 Abstracts Collection – Equilibrium Computation

Authors: Edith Elkind, Nimrod Megiddo, Peter Bro Miltersen, Bernhard von Stengel, and Vijay V. Vazirani

Published in: Dagstuhl Seminar Proceedings, Volume 10171, Equilibrium Computation (2010)

Abstract
From April 25 to April 30, 2010, the Dagstuhl Seminar 10171 ``Equilibrium Computation'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Edith Elkind, Nimrod Megiddo, Peter Bro Miltersen, Bernhard von Stengel, and Vijay V. Vazirani. 10171 Abstracts Collection – Equilibrium Computation. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 10171, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{elkind_et_al:DagSemProc.10171.1,
  author =	{Elkind, Edith and Megiddo, Nimrod and Miltersen, Peter Bro and von Stengel, Bernhard and Vazirani, Vijay V.},
  title =	{{10171 Abstracts Collection – Equilibrium Computation}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10171},
  editor =	{Edith Elkind and Nimrod Megiddo and Peter Bro Miltersen and Vijay V. Vazirani and Bernahrd von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.1},
  URN =		{urn:nbn:de:0030-drops-26738},
  doi =		{10.4230/DagSemProc.10171.1},
  annote =	{Keywords: Equilibrium computation, algorithmic game theory}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact