7 Search Results for "Elkind, Edith"

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-dev.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-dev.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-dev.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-dev.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-dev.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}
}
Document
DOI: 10.4230/DagSemProc.10171.2
Improved Algorithms for Computing Fisher's Market Clearing Prices

Authors: James B. Orlin

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

Abstract
We give the first strongly polynomial time algorithm for computing an equilibrium for the linear utilities case of Fisher's market model. We consider a problem with a set $B$ of buyers and a set $G$ of divisible goods. Each buyer $i$ starts with an initial integral allocation $e_i$ of money. The integral utility for buyer $i$ of good $j$ is $U_{ij}$. We first develop a weakly polynomial time algorithm that runs in $O(n^4 log U_{max} + n^3 e_{max})$ time, where $n = |B| + |G|$. We further modify the algorithm so that it runs in $O(n^4 log n)$ time. These algorithms improve upon the previous best running time of $O(n^8 log U_{max} + n^7 log e_{max})$, due to Devanur et al.
Cite as

James B. Orlin. Improved Algorithms for Computing Fisher's Market Clearing Prices. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 10171, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{orlin:DagSemProc.10171.2,
  author =	{Orlin, James B.},
  title =	{{Improved Algorithms for Computing Fisher's Market Clearing Prices}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--19},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.2},
  URN =		{urn:nbn:de:0030-drops-26720},
  doi =		{10.4230/DagSemProc.10171.2},
  annote =	{Keywords: Market equilibrium, Fisher, strongly polynomial}
}
Document
DOI: 10.4230/DagSemProc.10171.3
Proportional Response as Iterated Cobb-Douglas

Authors: Michael J. Todd

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

Abstract
We show that the proportional response algorithm for computing an economic equilibrium in a Fisher market model can be interpreted as iteratively approximating the economy by one with Cobb-Douglas utilities, for which a closed-form equilibrium can be obtained. We also extend the method to allow elasticities of substitution at most one.
Cite as

Michael J. Todd. Proportional Response as Iterated Cobb-Douglas. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 10171, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{todd:DagSemProc.10171.3,
  author =	{Todd, Michael J.},
  title =	{{Proportional Response as Iterated Cobb-Douglas}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--6},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.3},
  URN =		{urn:nbn:de:0030-drops-26713},
  doi =		{10.4230/DagSemProc.10171.3},
  annote =	{Keywords: Computing equilibria, Fisher market, proportional response algorithm, Cobb-Douglas utilities}
}
  • Refine by Author
  • 5 Elkind, Edith
  • 1 Goldsmith, Judy
  • 1 Klamler, Christian
  • 1 Megiddo, Nimrod
  • 1 Miltersen, Peter Bro
  • Show More...

  • Refine by Classification
  • 1 Applied computing
  • 1 Theory of computation → Algorithmic game theory

  • Refine by Keyword
  • 1 Algorithmic Game Theory
  • 1 Coalition Formation
  • 1 Cobb-Douglas utilities
  • 1 Computational Social Choice
  • 1 Computing equilibria
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 3 2010
  • 1 2012
  • 1 2018
  • 1 2021
  • 1 2023

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