13 Search Results for "Conitzer, Vincent"

Document
DOI: 10.4230/LIPIcs.ESA.2025.111
Hardness of Median and Center in the Ulam Metric

Authors: Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C. S.

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The classical rank aggregation problem seeks to combine a set X of n permutations into a single representative "consensus" permutation. In this paper, we investigate two fundamental rank aggregation tasks under the well-studied Ulam metric: computing a median permutation (which minimizes the sum of Ulam distances to X) and computing a center permutation (which minimizes the maximum Ulam distance to X) in two settings. - Continuous Setting: In the continuous setting, the median/center is allowed to be any permutation. It is known that computing a center in the Ulam metric is NP-hard and we add to this by showing that computing a median is NP-hard as well via a simple reduction from the Max-Cut problem. While this result may not be unexpected, it had remained elusive until now and confirms a speculation by Chakraborty, Das, and Krauthgamer [SODA '21]. - Discrete Setting: In the discrete setting, the median/center must be a permutation from the input set. We fully resolve the fine-grained complexity of the discrete median and discrete center problems under the Ulam metric, proving that the naive Õ(n² L)-time algorithm (where L is the length of the permutation) is conditionally optimal. This resolves an open problem raised by Abboud, Bateni, Cohen-Addad, Karthik C. S., and Seddighin [APPROX '23]. Our reductions are inspired by the known fine-grained lower bounds for similarity measures, but we face and overcome several new highly technical challenges.
Cite as

Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C. S.. Hardness of Median and Center in the Ulam Metric. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 111:1-111:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.ESA.2025.111,
  author =	{Fischer, Nick and Goldenberg, Elazar and Habib, Mursalin and Karthik C. S.},
  title =	{{Hardness of Median and Center in the Ulam Metric}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{111:1--111:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.111},
  URN =		{urn:nbn:de:0030-drops-245809},
  doi =		{10.4230/LIPIcs.ESA.2025.111},
  annote =	{Keywords: Ulam distance, median, center, rank aggregation, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.19
An Application of SAT Solvers in Integer Programming Games

Authors: Pravesh Koirala, Aditya Shrey, and Forrest Laine

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
Integer programming games (IPGs) are a popular game-theoretic tool to model an array of games where each player has a discrete strategy set. These games arise in important domains such as economics, transportation, cybersecurity, etc., but solving them is non-trivial as it is known that checking for the existence of pure Nash equilibria in an IPG is Σ₂^p-complete. Recent works have proposed a class of relaxed solution concepts for IPGs called locally optimal integer solutions (LOIS) and shown it to be an efficient alternative for pure Nash equilibria. While LOIS are significantly simpler to compute, they still do not scale when solved using traditional mathematical solvers, especially when high-quality solutions are desired. In this paper, we apply commercially available SAT solvers to find LOIS in IPGs. We investigate efficient encodings for a cybersecurity game and compare solution times when using SAT solvers vs mathematical program solvers. We also investigate the application of SAT solvers in graph games using a graph interdiction example and compare against the obtained LOI solutions against existing heuristics-based solutions. Our results indicate that with appropriate encodings, large-scale IPGs can be solved much more efficiently using SAT solvers. We also show that SAT solvers can be applied to graph games in conjunction with LOIS for obtaining high-quality solutions. Our results emphasize the potential of SAT solvers combined with LOIS to solve significant game theory problems.
Cite as

Pravesh Koirala, Aditya Shrey, and Forrest Laine. An Application of SAT Solvers in Integer Programming Games. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 19:1-19:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koirala_et_al:LIPIcs.SAT.2025.19,
  author =	{Koirala, Pravesh and Shrey, Aditya and Laine, Forrest},
  title =	{{An Application of SAT Solvers in Integer Programming Games}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{19:1--19:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.19},
  URN =		{urn:nbn:de:0030-drops-237534},
  doi =		{10.4230/LIPIcs.SAT.2025.19},
  annote =	{Keywords: Game Theory, Integer Programming Games, SAT Solvers, Local Solutions, Graph Games}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.18
q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations

Authors: Kiril Bangachev and S. Matthew Weinberg

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
For a set M of m elements, we define a decreasing chain of classes of normalized monotone-increasing valuation functions from 2^M to ℝ_{≥ 0}, parameterized by an integer q ∈ [2,m]. For a given q, we refer to the class as q-partitioning. A valuation function is subadditive if and only if it is 2-partitioning, and fractionally subadditive if and only if it is m-partitioning. Thus, our chain establishes an interpolation between subadditive and fractionally subadditive valuations. We show that this interpolation is smooth (q-partitioning valuations are "nearly" (q-1)-partitioning in a precise sense, Theorem 6), interpretable (the definition arises by analyzing the core of a cost-sharing game, à la the Bondareva-Shapley Theorem for fractionally subadditive valuations, Section 3.1), and non-trivial (the class of q-partitioning valuations is distinct for all q, Proposition 3). For domains where provable separations exist between subadditive and fractionally subadditive, we interpolate the stronger guarantees achievable for fractionally subadditive valuations to all q ∈ {2,…, m}. Two highlights are the following: 1) An Ω ((log log q)/(log log m))-competitive posted price mechanism for q-partitioning valuations. Note that this matches asymptotically the state-of-the-art for both subadditive (q = 2) [Paul Dütting et al., 2020], and fractionally subadditive (q = m) [Feldman et al., 2015]. 2) Two upper-tail concentration inequalities on 1-Lipschitz, q-partitioning valuations over independent items. One extends the state-of-the-art for q = m to q < m, the other improves the state-of-the-art for q = 2 for q > 2. Our concentration inequalities imply several corollaries that interpolate between subadditive and fractionally subadditive, for example: 𝔼[v(S)] ≤ (1 + 1/log q)Median[v(S)] + O(log q). To prove this, we develop a new isoperimetric inequality using Talagrand’s method of control by q points, which may be of independent interest. We also discuss other probabilistic inequalities and game-theoretic applications of q-partitioning valuations, and connections to subadditive MPH-k valuations [Tomer Ezra et al., 2019].
Cite as

Kiril Bangachev and S. Matthew Weinberg. q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bangachev_et_al:LIPIcs.ICALP.2025.18,
  author =	{Bangachev, Kiril and Weinberg, S. Matthew},
  title =	{{q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.18},
  URN =		{urn:nbn:de:0030-drops-233956},
  doi =		{10.4230/LIPIcs.ICALP.2025.18},
  annote =	{Keywords: Subadditive Functions, Fractionally Subadditive Functions, Posted Price Mechanisms, Concentration Inequalities}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.10
Algorithmic Collusion Without Threats

Authors: Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron Roth, and Juba Ziani

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
There has been substantial recent concern that automated pricing algorithms might learn to "collude." Supra-competitive prices can emerge as a Nash equilibrium of repeated pricing games, in which sellers play strategies which threaten to punish their competitors if they ever "defect" from a set of supra-competitive prices, and these strategies can be automatically learned. But threats are anti-competitive on their face. In fact, a standard economic intuition is that supra-competitive prices emerge from either the use of threats, or a failure of one party to correctly optimize their payoff. Is this intuition correct? Would explicitly preventing threats in algorithmic decision-making prevent supra-competitive prices when sellers are optimizing for their own revenue? No. We show that supra-competitive prices can robustly emerge even when both players are using algorithms which do not explicitly encode threats, and which optimize for their own revenue. Since deploying an algorithm is a form of commitment, we study sequential Bertrand pricing games (and a continuous variant) in which a first mover deploys an algorithm and then a second mover optimizes within the resulting environment. We show that if the first mover deploys any algorithm with a no-regret guarantee, and then the second mover even approximately optimizes within this now static environment, monopoly-like prices arise. The result holds for any no-regret learning algorithm deployed by the first mover and for any pricing policy of the second mover that obtains them profit at least as high as a random pricing would - and hence the result applies even when the second mover is optimizing only within a space of non-responsive pricing distributions which are incapable of encoding threats. In fact, there exists a set of strategies, neither of which explicitly encode threats that form a Nash equilibrium of the simultaneous pricing game in algorithm space, and lead to near monopoly prices. This suggests that the definition of "algorithmic collusion" may need to be expanded, to include strategies without explicitly encoded threats.
Cite as

Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron Roth, and Juba Ziani. Algorithmic Collusion Without Threats. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{arunachaleswaran_et_al:LIPIcs.ITCS.2025.10,
  author =	{Arunachaleswaran, Eshwar Ram and Collina, Natalie and Kannan, Sampath and Roth, Aaron and Ziani, Juba},
  title =	{{Algorithmic Collusion Without Threats}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.10},
  URN =		{urn:nbn:de:0030-drops-226386},
  doi =		{10.4230/LIPIcs.ITCS.2025.10},
  annote =	{Keywords: Algorithmic Game Theory, Algorithmic Collusion, No-Regret Dynamics}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.84
Quantum Communication Complexity of Classical Auctions

Authors: Aviad Rubinstein and Zixin Zhou

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study the fundamental, classical mechanism design problem of single-buyer multi-item Bayesian revenue-maximizing auctions under the lens of communication complexity between the buyer and the seller. Specifically, we ask whether using quantum communication can be more efficient than classical communication. We have two sets of results, revealing a surprisingly rich landscape - which looks quite different from both quantum communication in non-strategic parties, and classical communication in mechanism design. We first study the expected communication complexity of approximately optimal auctions. We give quantum auction protocols for buyers with unit-demand or combinatorial valuations that obtain an arbitrarily good approximation of the optimal revenue while running in exponentially more efficient communication compared to classical approximately optimal auctions. However, these auctions come with the caveat that they may require the seller to charge exponentially large payments from a deviating buyer. We show that this caveat is necessary - we give an exponential lower bound on the product of the expected quantum communication and the maximum payment. We then study the worst-case communication complexity of exactly optimal auctions in an extremely simple setting: additive buyer’s valuations over two items. We show the following separations: - There exists a prior where the optimal classical auction protocol requires infinitely many bits, but a one-way message of 1 qubit and 2 classical bits suffices. - There exists a prior where no finite one-way quantum auction protocol can obtain the optimal revenue. However, there is a barely-interactive revenue-optimal quantum auction protocol with the following simple structure: the seller prepares a pair of qubits in the EPR state, sends one of them to the buyer, and then the buyer sends 1 qubit and 2 classical bits. - There exists a prior where no multi-round quantum auction protocol with a finite bound on communication complexity can obtain the optimal revenue.
Cite as

Aviad Rubinstein and Zixin Zhou. Quantum Communication Complexity of Classical Auctions. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 84:1-84:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2025.84,
  author =	{Rubinstein, Aviad and Zhou, Zixin},
  title =	{{Quantum Communication Complexity of Classical Auctions}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{84:1--84:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.84},
  URN =		{urn:nbn:de:0030-drops-227124},
  doi =		{10.4230/LIPIcs.ITCS.2025.84},
  annote =	{Keywords: Mechanism design, Communication complexity, Quantum computing}
}
Document
DOI: 10.4230/DagSemProc.10101.1
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
DOI: 10.4230/DagSemProc.10101.2
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
DOI: 10.4230/DagSemProc.10101.3
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.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
DOI: 10.4230/DagSemProc.10101.4
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.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
DOI: 10.4230/DagSemProc.10101.5
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.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
DOI: 10.4230/DagSemProc.10101.6
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.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}
}
Document
DOI: 10.4230/DagSemProc.07271.4
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
DOI: 10.4230/DagSemProc.07271.10
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}
}
  • Refine by Type
  • 13 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 6 2010
  • 2 2007

  • Refine by Author
  • 4 Conitzer, Vincent
  • 2 Brandt, Felix
  • 2 Hemaspaandra, Lane A.
  • 2 Laslier, Jean-Francois
  • 2 Zwicker, William S.
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 8 DagSemProc

  • Refine by Classification
  • 2 Theory of computation → Algorithmic mechanism design
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Permutations and combinations
  • 1 Mathematics of computing → Probability and statistics
  • 1 Security and privacy → Network security
  • Show More...

  • Refine by Keyword
  • 3 Mechanism design
  • 2 Algorithms
  • 2 Computational Complexity
  • 2 Fair Division
  • 2 Multiagent Systems
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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