Search Results

Documents authored by Conitzer, Vincent


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.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.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
Anonymity-Proof Voting Rules

Authors: Vincent Conitzer

Published in: Dagstuhl Seminar Proceedings, Volume 7271, Computational Social Systems and the Internet (2007)


Abstract
A (randomized, anonymous) voting rule maps any multiset of total orders of (aka. votes over) a fixed set of alternatives to a probability distribution over these alternatives. A voting rule f is neutral if it treats all alternatives symmetrically. It satisfies participation if no voter ever benefits from not casting her vote. It is falsename-proof if no voter ever benefits from casting additional (potentially different) votes. It is anonymity-proof if it satisfies participation and it is false-name-proof. We show that the class of anonymity-proof neutral voting rules consists exactly of the rules of the following form. With some probability kf in [0, 1], the rule chooses an alternative at random. With probability 1-kf , the rule first draws a pair of alternatives at random. If every vote prefers the same alternative between the two (and there is at least one vote), then the rule chooses that alternative. Otherwise, the rule flips a fair coin to decide between the two alternatives.

Cite as

Vincent Conitzer. Anonymity-Proof Voting Rules. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{conitzer:DagSemProc.07271.4,
  author =	{Conitzer, Vincent},
  title =	{{Anonymity-Proof Voting Rules}},
  booktitle =	{Computational Social Systems and the Internet},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7271},
  editor =	{Peter Cramton and Rudolf M\"{u}ller and Eva Tardos and Moshe Tennenholtz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07271.4},
  URN =		{urn:nbn:de:0030-drops-11658},
  doi =		{10.4230/DagSemProc.07271.4},
  annote =	{Keywords: Mechanism design, social choice, false-name-proofness, verifying identities, combinatorial auctions}
}
Document
Limited Verification of Identities to Induce False-Name-Proofness

Authors: Vincent Conitzer

Published in: Dagstuhl Seminar Proceedings, Volume 7271, Computational Social Systems and the Internet (2007)


Abstract
In open, anonymous environments such as the Internet, mechanism design is complicated by the fact that a single agent can participate in the mechanism under multiple identifiers. One way to address this is to design false-name-proof mechanisms, which choose the outcome in such a way that agents have no incentive to use more than one identifier. Unfortunately, there are inherent limitations on what can be achieved with false-name-proof mechanisms, and at least in some cases, these limitations are crippling. An alternative approach is to verify the identities of all agents. This imposes significant overhead and removes any benefits from anonymity. In this paper, we propose a middle ground. Based on the reported preferences, we check, for various subsets of the reports, whether the reports in the subset were all submitted by different agents. If they were not, then we discard some of them. We characterize when such a limited verification protocol induces false-name-proofness for a mechanism, that is, when the combination of the mechanism and the verification protocol gives the agents no incentive to use multiple identi- fiers. This characterization leads to various optimization problems for minimizing verification effort. We study how to solve these problems. Throughout, we use combinatorial auctions (using the Clarke mechanism) and majority voting as examples.

Cite as

Vincent Conitzer. Limited Verification of Identities to Induce False-Name-Proofness. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{conitzer:DagSemProc.07271.10,
  author =	{Conitzer, Vincent},
  title =	{{Limited Verification of Identities to Induce False-Name-Proofness}},
  booktitle =	{Computational Social Systems and the Internet},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7271},
  editor =	{Peter Cramton and Rudolf M\"{u}ller and Eva Tardos and Moshe Tennenholtz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07271.10},
  URN =		{urn:nbn:de:0030-drops-11569},
  doi =		{10.4230/DagSemProc.07271.10},
  annote =	{Keywords: Mechanism design, social choice, false-name-proofness, verifying identities, combinatorial auctions}
}
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