10 Search Results for "Hemaspaandra, Lane A."


Document
Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting

Authors: Lane A. Hemaspaandra, Mandar Juvekar, Arian Nadjimzadah, and Patrick A. Phillips

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ⊕ P (and thus that FewP ⊆ ⊕ P). In this paper, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed "nongappy"-ness) of the easy-to-find "targets" used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant’s unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra-Pomerance-Wagstaff Conjecture implies that all O(log log n)-ambiguity NP sets are in the restricted counting class RC_PRIMES.

Cite as

Lane A. Hemaspaandra, Mandar Juvekar, Arian Nadjimzadah, and Patrick A. Phillips. Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hemaspaandra_et_al:LIPIcs.MFCS.2022.57,
  author =	{Hemaspaandra, Lane A. and Juvekar, Mandar and Nadjimzadah, Arian and Phillips, Patrick A.},
  title =	{{Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{57:1--57:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.57},
  URN =		{urn:nbn:de:0030-drops-168552},
  doi =		{10.4230/LIPIcs.MFCS.2022.57},
  annote =	{Keywords: structural complexity theory, computational complexity theory, ambiguity-limited NP, counting classes, P-printable sets}
}
Document
Finding Optimal Solutions With Neighborly Help

Authors: Elisabet Burjons, Fabian Frei, Edith Hemaspaandra, Dennis Komm, and David Wehner

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighboring (i.e., locally modified) instances? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems; most notably graph theory’s core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, Colorability and Vertex Cover. For example, we show that it is NP-hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in P. We observe that Vertex Cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for DP (differences of NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For Vertex Cover, we show that recognizing beta-vertex-critical graphs is complete for Theta_2^p (parallel access to NP), obtaining the first completeness result for a criticality problem for this class.

Cite as

Elisabet Burjons, Fabian Frei, Edith Hemaspaandra, Dennis Komm, and David Wehner. Finding Optimal Solutions With Neighborly Help. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{burjons_et_al:LIPIcs.MFCS.2019.78,
  author =	{Burjons, Elisabet and Frei, Fabian and Hemaspaandra, Edith and Komm, Dennis and Wehner, David},
  title =	{{Finding Optimal Solutions With Neighborly Help}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{78:1--78:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.78},
  URN =		{urn:nbn:de:0030-drops-110221},
  doi =		{10.4230/LIPIcs.MFCS.2019.78},
  annote =	{Keywords: Critical Graphs, Computational Complexity, Structural Self-Reducibility, Minimality Problems, Colorability, Vertex Cover, Satisfiability, Reoptimization, Advice}
}
Document
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction

Authors: Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, and Osamu Watanabe

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)


Abstract
We show that the counting class LWPP [S. Fenner et al., 1994] remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossible to improve this from polynomially many gap values to a superpolynomial number of gap values by relativizable proof techniques. The first of these results implies that the Legitimate Deck Problem (from the study of graph reconstruction) is in LWPP (and thus low for PP, i.e., PP^{Legitimate Deck} = PP) if the weakened version of the Reconstruction Conjecture holds in which the number of nonisomorphic preimages is assumed merely to be polynomially bounded. This strengthens the 1992 result of Köbler, Schöning, and Torán [J. Köbler et al., 1992] that the Legitimate Deck Problem is in LWPP if the Reconstruction Conjecture holds, and provides strengthened evidence that the Legitimate Deck Problem is not NP-hard. We additionally show on the one hand that our main LWPP robustness result also holds for WPP, and also holds even when one allows both the rejection- and acceptance- gap-value targets to simultaneously be polynomial-sized lists; yet on the other hand, we show that for the #P-based analog of LWPP the behavior much differs in that, in some relativized worlds, even two target values already yield a richer class than one value does.

Cite as

Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, and Osamu Watanabe. The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{hemaspaandra_et_al:LIPIcs.MFCS.2018.51,
  author =	{Hemaspaandra, Edith and Hemaspaandra, Lane A. and Spakowski, Holger and Watanabe, Osamu},
  title =	{{The Robustness of LWPP and WPP, with an Application to Graph Reconstruction}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.51},
  URN =		{urn:nbn:de:0030-drops-96330},
  doi =		{10.4230/LIPIcs.MFCS.2018.51},
  annote =	{Keywords: structural complexity theory, robustness of counting classes, the legitimate deck problem, PP-lowness, the Reconstruction Conjecture}
}
Document
Search versus Decision for Election Manipulation Problems

Authors: Edith Hemaspaandra, Lane A. Hemaspaandra, and Curtis Menton

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)


Abstract
Most theoretical definitions about the complexity of manipulating elections focus on the decision problem of recognizing which instances can be successfully manipulated, rather than the search problem of finding the successful manipulative actions. Since the latter is a far more natural goal for manipulators, that definitional focus may be misguided if these two complexities can differ. Our main result is that they probably do differ: If integer factoring is hard, then for election manipulation, election bribery, and some types of election control, there are election systems for which recognizing which instances can be successfully manipulated is in polynomial time but producing the successful manipulations cannot be done in polynomial time.

Cite as

Edith Hemaspaandra, Lane A. Hemaspaandra, and Curtis Menton. Search versus Decision for Election Manipulation Problems. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 377-388, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{hemaspaandra_et_al:LIPIcs.STACS.2013.377,
  author =	{Hemaspaandra, Edith and Hemaspaandra, Lane A. and Menton, Curtis},
  title =	{{Search versus Decision for Election Manipulation Problems}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{377--388},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.377},
  URN =		{urn:nbn:de:0030-drops-39498},
  doi =		{10.4230/LIPIcs.STACS.2013.377},
  annote =	{Keywords: Search vs. decision, application of structural complexity theory}
}
Document
10101 Abstracts Collection – Computational Foundations of Social Choice

Authors: Felix Brandt, Vincent Conitzer, Lane A. Hemaspaandra, Jean-Francois Laslier, and William S. Zwicker

Published in: Dagstuhl Seminar Proceedings, Volume 10101, Computational Foundations of Social Choice (2010)


Abstract
From March 7 to March 12, 2010, the Dagstuhl Seminar 10101 ``Computational Foundations of Social Choice '' 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

Felix Brandt, Vincent Conitzer, Lane A. Hemaspaandra, Jean-Francois Laslier, and William S. Zwicker. 10101 Abstracts Collection – Computational Foundations of Social Choice. In Computational Foundations of Social Choice. Dagstuhl Seminar Proceedings, Volume 10101, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{brandt_et_al:DagSemProc.10101.1,
  author =	{Brandt, Felix and Conitzer, Vincent and Hemaspaandra, Lane A. and Laslier, Jean-Francois and Zwicker, William S.},
  title =	{{10101 Abstracts Collection – Computational Foundations of Social Choice}},
  booktitle =	{Computational Foundations of Social Choice},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10101},
  editor =	{Felix Brandt and Vincent Conitzer and Lane A. Hemaspaandra and Jean-Francois Laslier and William S. Zwicker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10101.1},
  URN =		{urn:nbn:de:0030-drops-25644},
  doi =		{10.4230/DagSemProc.10101.1},
  annote =	{Keywords: Social Choice Theory, Voting, Fair Division, Algorithms, Computational Complexity, Multiagent Systems}
}
Document
10101 Executive Summary – Computational Foundations of Social Choice

Authors: Felix Brandt, Vincent Conitzer, Lane A. Hemaspaandra, Jean-Francois Laslier, and William S. Zwicker

Published in: Dagstuhl Seminar Proceedings, Volume 10101, Computational Foundations of Social Choice (2010)


Abstract
This seminar addressed some of the key issues in computational social choice, a novel interdisciplinary field of study at the interface of social choice theory and computer science. Computational social choice is concerned with the application of computational techniques to the study of social choice mechanisms, such as voting rules and fair division protocols, as well as with the integration of social choice paradigms into computing. The seminar brought together many of the most active researchers in the field and focussed the research community currently forming around these important and exciting topics.

Cite as

Felix Brandt, Vincent Conitzer, Lane A. Hemaspaandra, Jean-Francois Laslier, and William S. Zwicker. 10101 Executive Summary – Computational Foundations of Social Choice. In Computational Foundations of Social Choice. Dagstuhl Seminar Proceedings, Volume 10101, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{brandt_et_al:DagSemProc.10101.2,
  author =	{Brandt, Felix and Conitzer, Vincent and Hemaspaandra, Lane A. and Laslier, Jean-Francois and Zwicker, William S.},
  title =	{{10101 Executive Summary – Computational Foundations of Social Choice}},
  booktitle =	{Computational Foundations of Social Choice},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10101},
  editor =	{Felix Brandt and Vincent Conitzer and Lane A. Hemaspaandra and Jean-Francois Laslier and William S. Zwicker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10101.2},
  URN =		{urn:nbn:de:0030-drops-25637},
  doi =		{10.4230/DagSemProc.10101.2},
  annote =	{Keywords: Social Choice Theory, Voting, Fair Division, Algorithms, Computational Complexity, Multiagent Systems}
}
Document
False-name-Proof Combinatorial Auction Mechanisms

Authors: Makoto Yokoo

Published in: Dagstuhl Seminar Proceedings, Volume 10101, Computational Foundations of Social Choice (2010)


Abstract
In Internet auctions, it is easy for a bidder to submit multiple bids under multiple identifiers (e.g., multiple e-mail addresses). If only one good is sold, a bidder cannot make any additional profit by using multiple bids. However, in combinatorial auctions, where multiple goods are sold simultaneously, submitting multiple bids under fictitious names can be profitable. A bid made under a fictitious name is called a {em false-name bid}. In this talk, I describe the summary of existing works and open problems on false-name bids.

Cite as

Makoto Yokoo. False-name-Proof Combinatorial Auction Mechanisms. In Computational Foundations of Social Choice. Dagstuhl Seminar Proceedings, Volume 10101, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{yokoo:DagSemProc.10101.3,
  author =	{Yokoo, Makoto},
  title =	{{False-name-Proof Combinatorial Auction Mechanisms}},
  booktitle =	{Computational Foundations of Social Choice},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10101},
  editor =	{Felix Brandt and Vincent Conitzer and Lane A. Hemaspaandra and Jean-Francois Laslier and William S. Zwicker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10101.3},
  URN =		{urn:nbn:de:0030-drops-25621},
  doi =		{10.4230/DagSemProc.10101.3},
  annote =	{Keywords: Combinatorial auctions, mechanism design, false-name bids}
}
Document
Manipulability of Single Transferable Vote

Authors: Toby Walsh

Published in: Dagstuhl Seminar Proceedings, Volume 10101, Computational Foundations of Social Choice (2010)


Abstract
For many voting rules, it is NP-hard to compute a successful manipulation. However, NP-hardness only bounds the worst-case complexity. Recent theoretical results suggest that manipulation may often be easy in practice. We study empirically the cost of manipulating the single transferable vote (STV) rule. This was one of the first rules shown to be NP-hard to manipulate. It also appears to be one of the harder rules to manipulate since it involves multiple rounds and since, unlike many other rules, it is NP-hard for a single agent to manipulate without weights on the votes or uncertainty about how the other agents have voted. In almost every election in our experiments, it was easy to compute how a single agent could manipulate the election or to prove that manipulation by a single agent was impossible. It remains an interesting open question if manipulation by a coalition of agents is hard to compute in practice.

Cite as

Toby Walsh. Manipulability of Single Transferable Vote. In Computational Foundations of Social Choice. Dagstuhl Seminar Proceedings, Volume 10101, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{walsh:DagSemProc.10101.4,
  author =	{Walsh, Toby},
  title =	{{Manipulability of Single Transferable Vote}},
  booktitle =	{Computational Foundations of Social Choice},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10101},
  editor =	{Felix Brandt and Vincent Conitzer and Lane A. Hemaspaandra and Jean-Francois Laslier and William S. Zwicker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10101.4},
  URN =		{urn:nbn:de:0030-drops-25585},
  doi =		{10.4230/DagSemProc.10101.4},
  annote =	{Keywords: Computational social choice, manipulability, STV voting, NP-hardness}
}
Document
Nonmanipulable Selections from a Tournament

Authors: Alon Altman, Ariel D. Procaccia, and Moshe Tennenholtz

Published in: Dagstuhl Seminar Proceedings, Volume 10101, Computational Foundations of Social Choice (2010)


Abstract
A tournament is a binary dominance relation on a set of alternatives. Tournaments arise in many contexts that are relevant to AI, most notably in voting (as a method to aggregate the preferences of agents). There are many works that deal with choice rules that select a desirable alternative from a tournament, but very few of them deal directly with incentive issues, despite the fact that game-theoretic considerations are crucial with respect to systems populated by selfish agents. We deal with the problem of the manipulation of choice rules by considering two types of manipulation. We say that a choice rule is emph{monotonic} if an alternative cannot get itself selected by losing on purpose, and emph{pairwise nonmanipulable} if a pair of alternatives cannot make one of them the winner by reversing the outcome of the match between them. Our main result is a combinatorial construction of a choice rule that is monotonic, pairwise nonmanipulable, and onto the set of alternatives, for any number of alternatives besides three.

Cite as

Alon Altman, Ariel D. Procaccia, and Moshe Tennenholtz. Nonmanipulable Selections from a Tournament. In Computational Foundations of Social Choice. Dagstuhl Seminar Proceedings, Volume 10101, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{altman_et_al:DagSemProc.10101.5,
  author =	{Altman, Alon and Procaccia, Ariel D. and Tennenholtz, Moshe},
  title =	{{Nonmanipulable Selections from a Tournament}},
  booktitle =	{Computational Foundations of Social Choice},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10101},
  editor =	{Felix Brandt and Vincent Conitzer and Lane A. Hemaspaandra and Jean-Francois Laslier and William S. Zwicker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10101.5},
  URN =		{urn:nbn:de:0030-drops-25607},
  doi =		{10.4230/DagSemProc.10101.5},
  annote =	{Keywords: Tournament, manipulation}
}
Document
On the stability of a scoring rules set under the IAC

Authors: Vincent Merlin, Mostapha Diss, Ahmed Louichi, and Hatem Smaoui

Published in: Dagstuhl Seminar Proceedings, Volume 10101, Computational Foundations of Social Choice (2010)


Abstract
A society facing a choice problem has also to choose the voting rule itself from a set of different possible voting rules. In such situations, the consequentialism property allows us to induce voters' preferences on voting rules from preferences over alternatives. A voting rule employed to resolve the society's choice problem is self-selective if it chooses itself when it is also used in choosing the voting rule. A voting rules set is said to be stable if it contains at least one self-selective voting rule at each profile of preferences on voting rules. We consider in this paper a society which will make a choice from a set constituted by three alternatives {a, b, c} and a set of the three well-known scoring voting rules {Borda, Plurality, Antiplurality}. Under the Impartial Anonymous Culture assumption (IAC), we will derive a probability for the stability of this triplet of voting rules. We use Ehrhart polynomials in order to solve our problems. This method counts the number of lattice points inside a convex bounded polyhedron (polytope). We discuss briefly recent algorithmic solutions to this method and use it to determine the probability of stabillity of {Borda, Plurality, Antiplurality} set.

Cite as

Vincent Merlin, Mostapha Diss, Ahmed Louichi, and Hatem Smaoui. On the stability of a scoring rules set under the IAC. In Computational Foundations of Social Choice. Dagstuhl Seminar Proceedings, Volume 10101, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{merlin_et_al:DagSemProc.10101.6,
  author =	{Merlin, Vincent and Diss, Mostapha and Louichi, Ahmed and Smaoui, Hatem},
  title =	{{On the stability of a scoring rules set under the IAC}},
  booktitle =	{Computational Foundations of Social Choice},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10101},
  editor =	{Felix Brandt and Vincent Conitzer and Lane A. Hemaspaandra and Jean-Francois Laslier and William S. Zwicker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10101.6},
  URN =		{urn:nbn:de:0030-drops-25610},
  doi =		{10.4230/DagSemProc.10101.6},
  annote =	{Keywords: Self-selectivity, Stability, Consequentialism, Ehrhart polynomials}
}
  • Refine by Author
  • 5 Hemaspaandra, Lane A.
  • 3 Hemaspaandra, Edith
  • 2 Brandt, Felix
  • 2 Conitzer, Vincent
  • 2 Laslier, Jean-Francois
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Complexity classes
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 3 Computational Complexity
  • 2 Algorithms
  • 2 Fair Division
  • 2 Multiagent Systems
  • 2 Social Choice Theory
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 6 2010
  • 1 2013
  • 1 2018
  • 1 2019
  • 1 2022

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