Search Results

Documents authored by Tennenholtz, Moshe

Document
DOI: 10.4230/LIPIcs.ESA.2016.41
Distributed Signaling Games

Authors: Moran Feldman, Moshe Tennenholtz, and Omri Weinstein

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
The study of the algorithmic and computational complexity of designing efficient signaling schemes for mechanisms aiming to optimize social welfare or revenue is a recurring theme in recent computer science literature. In reality, however, information is typically not held by a central authority, but is distributed among multiple sources (third-party "mediators"), a fact that dramatically changes the strategic and combinatorial nature of the signaling problem. In this paper we introduce distributed signaling games, while using display advertising as a canonical example for introducing this foundational framework. A distributed signaling game may be a pure coordination game (i.e., a distributed optimization task), or a non-cooperative game. In the context of pure coordination games, we show a wide gap between the computational complexity of the centralized and distributed signaling problems, proving that distributed coordination on revenue-optimal signaling is a much harder problem than its "centralized" counterpart. In the context of non-cooperative games, the outcome generated by the mediators' signals may have different value to each. The reason for that is typically the desire of the auctioneer to align the incentives of the mediators with his own by a compensation relative to the marginal benefit from their signals. We design a mechanism for this problem via a novel application of Shapley's value, and show that it possesses a few interesting economical properties.
Cite as

Moran Feldman, Moshe Tennenholtz, and Omri Weinstein. Distributed Signaling Games. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.ESA.2016.41,
  author =	{Feldman, Moran and Tennenholtz, Moshe and Weinstein, Omri},
  title =	{{Distributed Signaling Games}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.41},
  URN =		{urn:nbn:de:0030-drops-63536},
  doi =		{10.4230/LIPIcs.ESA.2016.41},
  annote =	{Keywords: Signaling, display advertising, mechanism design, shapley value}
}
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.07271.1
07271 Abstracts Collection – Computational Social Systems and the Internet

Authors: Peter Cramton, Rudolf Müller, Eva Tardos, and Moshe Tennenholtz

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

Abstract
From 01.07. to 06.07.2007, the Dagstuhl Seminar 07271 ``Computational Social Systems and the Internet'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. 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

Peter Cramton, Rudolf Müller, Eva Tardos, and Moshe Tennenholtz. 07271 Abstracts Collection – Computational Social Systems and the Internet. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{cramton_et_al:DagSemProc.07271.1,
  author =	{Cramton, Peter and M\"{u}ller, Rudolf and Tardos, Eva and Tennenholtz, Moshe},
  title =	{{07271 Abstracts Collection – Computational Social Systems and the Internet }},
  booktitle =	{Computational Social Systems and the Internet},
  pages =	{1--25},
  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.1},
  URN =		{urn:nbn:de:0030-drops-11666},
  doi =		{10.4230/DagSemProc.07271.1},
  annote =	{Keywords: Mechanism Design, Combinatorial Auctions, Social Choice Theory, Behavioral Economics, Computational Game Theory, Social Networks}
}
Document
DOI: 10.4230/DagSemProc.07271.2
07271 Summary – Computational Social Systems and the Internet

Authors: Peter Cramton, Rudolf Müller, Eva Tardos, and Moshe Tennenholtz

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

Abstract
The seminar "Computational Social Systems and the Internet" facilitated a very fruitful interaction between economists and computer scientists, which intensified the understanding of the other disciplines' tool sets. The seminar helped to pave the way to a unified theory of social systems on the Internet that takes into account both the economic and the computational issues---and their deep interaction.
Cite as

Peter Cramton, Rudolf Müller, Eva Tardos, and Moshe Tennenholtz. 07271 Summary – Computational Social Systems and the Internet. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{cramton_et_al:DagSemProc.07271.2,
  author =	{Cramton, Peter and M\"{u}ller, Rudolf and Tardos, Eva and Tennenholtz, Moshe},
  title =	{{07271 Summary – Computational Social Systems and the Internet }},
  booktitle =	{Computational Social Systems and the Internet},
  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.2},
  URN =		{urn:nbn:de:0030-drops-11642},
  doi =		{10.4230/DagSemProc.07271.2},
  annote =	{Keywords: Mechanism Design, Combinatorial Auctions, Social Choice Theory, Behavioral Economics, Computational Game Theory, Social Networks}
}
Document
DOI: 10.4230/DagSemProc.07271.3
An Axiomatic Approach to Personalized Ranking Systems

Authors: Alon Altman and Moshe Tennenholtz

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

Abstract
Personalized ranking systems and trust systems are an essential tool for collaboration in a multi-agent environment. In these systems, trust relations between many agents are aggregated to produce a personalized trust rating of the agents. In this paper we introduce the first extensive axiomatic study of this setting, and explore a wide array of well-known and new personalized ranking systems. We adapt several axioms (basic criteria) from the literature on global ranking systems to the context of personalized ranking systems, and fully classify the set of systems that satisfy all of these axioms. We further show that all these axioms are necessary for this result.
Cite as

Alon Altman and Moshe Tennenholtz. An Axiomatic Approach to Personalized Ranking Systems. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{altman_et_al:DagSemProc.07271.3,
  author =	{Altman, Alon and Tennenholtz, Moshe},
  title =	{{An Axiomatic Approach to Personalized Ranking Systems}},
  booktitle =	{Computational Social Systems and the Internet},
  pages =	{1--25},
  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.3},
  URN =		{urn:nbn:de:0030-drops-11527},
  doi =		{10.4230/DagSemProc.07271.3},
  annote =	{Keywords: Ranking systems, trust, axiomatization, incentives, mechanism design, game theory}
}
Document
DOI: 10.4230/DagSemProc.05011.20
The Value of Correlation in Strategic Form Games

Authors: Itai Ashlagi, Dov Monderer, and Moshe Tennenholtz

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
Every game in strategic form can be extended by adding a correlation device. Any Equilibrium in such an extended game is called a correlated equilibrium (Aumann 1974). Aumann showed that there exist games, where the agents surplus in a correlated equilibrium is greater than their surplus in every equilibrium. This suggests the study of two major measures for the value of correlation: 1. The ratio between the maximal surplus obtained in an correlated equilibrium to the maximal surplus obtained in equilibrium. We refer to this ratio as the mediation value. 2. The ratio between the optimal surplus to the maximal surplus obtained in correlated equilibrium. We refer to this ratio as the enforcement value. In this work we initiate the study of the mediation value and of the enforcement value, providing several general results on the value of correlation as captured by these concepts. We also present a set of results for the more specialized case of congestion games, a class of games that received a lot attention in the recent computer science and e-commerce communities. Indeed, while much work in computer science has been devoted to the study of the ratio between the surplus in optimal strategies to the surplus in the worst Nash equilibrium (the so called "price of anarchy") for congestion games, our work presents and initiates the study of two other complementary measures.
Cite as

Itai Ashlagi, Dov Monderer, and Moshe Tennenholtz. The Value of Correlation in Strategic Form Games. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{ashlagi_et_al:DagSemProc.05011.20,
  author =	{Ashlagi, Itai and Monderer, Dov and Tennenholtz, Moshe},
  title =	{{The Value of Correlation in Strategic Form Games}},
  booktitle =	{Computing and Markets},
  pages =	{1--29},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.20},
  URN =		{urn:nbn:de:0030-drops-2317},
  doi =		{10.4230/DagSemProc.05011.20},
  annote =	{Keywords: Correlation, mediation, enforcement, equilibrium, mediator}
}
Document
DOI: 10.4230/DagSemProc.05011.11
Local-Effect Games

Authors: Kevin Leyton-Brown and Moshe Tennenholtz

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
This talk will survey two graphical models which the authors have proposed for compactly representing single-shot, finite-action games in which a large number of agents contend for scarce resources. The first model considered is Local-Effect Games (LEGs). These games often (but not always) have pure-strategy Nash equilibria. Finding a potential function is a good technique for finding such equilibria. We give a complete characterization of which LEGs have potential functions and provide the functions in each case; we also show a general case where pure-strategy equilibria exist in the absence of potential functions. Action-graph games (AGGs) are a fully expressive game representation which can compactly express both strict and context-specific independence between players' utility functions, and which generalize LEGs. We present algorithms for computing both symmetric and arbitrary equilibria of AGGs, based on a continuation method proposed by Govindan and Wilson. We analyze the worst- case cost of computing the Jacobian of the payoff function, the exponential- time bottleneck step of this algorithm, and in all cases achieve exponential speedup. When the indegree of G is bounded by a constant and the game is symmetric, the Jacobian can be computed in polynomial time.
Cite as

Kevin Leyton-Brown and Moshe Tennenholtz. Local-Effect Games. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{leytonbrown_et_al:DagSemProc.05011.11,
  author =	{Leyton-Brown, Kevin and Tennenholtz, Moshe},
  title =	{{Local-Effect Games}},
  booktitle =	{Computing and Markets},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.11},
  URN =		{urn:nbn:de:0030-drops-2190},
  doi =		{10.4230/DagSemProc.05011.11},
  annote =	{Keywords: compact representation of games, congestion games, local-effect}
}
Document
DOI: 10.4230/DagSemProc.05011.7
Congestion games with failures

Authors: Michal Penn, Maria Polukarov, and Moshe Tennenholtz

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
We introduce a new class of games, congestion games with failures (CGFs), which extends the class of congestion games to allow for facility failures. In a CGF agents share a common set of facilities (service providers), where each service provider (SP) may fail with some known probability. For reliability reasons, an agent may choose a subset of the SPs in order to try and perform his task. The cost of an agent for utilizing any SP is an agent-specific function of the total number of agents using this SP. A main feature of this setting is that the cost for an agent for successful completion of his task is the minimum of the costs of his successful attempts. We show that although congestion games with failures do not admit a potential function, and thus are not isomorphic to classic congestion games, they always possess a pure-strategy Nash equilibrium. Moreover, an efficient algorithm for the construction of pure-strategy Nash equilibrium profile is presented. We also show that the SPs congestion experienced in different Nash equilibria is (almost) unique. For the subclass of symmetric CGFs we give a characterization of best and worst Nash equilibria, present algorithms for their construction, and compare the social disutilities of the agents at these points.
Cite as

Michal Penn, Maria Polukarov, and Moshe Tennenholtz. Congestion games with failures. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{penn_et_al:DagSemProc.05011.7,
  author =	{Penn, Michal and Polukarov, Maria and Tennenholtz, Moshe},
  title =	{{Congestion games with failures}},
  booktitle =	{Computing and Markets},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.7},
  URN =		{urn:nbn:de:0030-drops-2098},
  doi =		{10.4230/DagSemProc.05011.7},
  annote =	{Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio}
}
Document
DOI: 10.4230/DagSemProc.05011.12
Overcoming Free Riding in Multi-Party Computations

Authors: Rann Smordinsky and Moshe Tennenholtz

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
This paper addresses the question of multi party computation in a model with asymmetric information. Each agent has a private value (secret), but in contrast to standard models, the agent incurs a cost when retrieving the secret. There is a social choice function the agents would like to compute and implement. All agents would like to perform a joint computation, which input is their vector of secrets. However, agents would like to free-ride on others contribution. A mechanism which elicits players secrets and performs the desired computation defines a game. A mechanism is `appropriate if it (weakly) implements the social choice function for all secret vectors. namely, if there exists an equilibrium in which it is able to elicit (sufficiently many) agents secrets and perform the computation, for all possible secret vectors. We show that `appropriate mechanisms approach agents sequentially and that they have low communication complexity.
Cite as

Rann Smordinsky and Moshe Tennenholtz. Overcoming Free Riding in Multi-Party Computations. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{smordinsky_et_al:DagSemProc.05011.12,
  author =	{Smordinsky, Rann and Tennenholtz, Moshe},
  title =	{{Overcoming Free Riding in Multi-Party Computations}},
  booktitle =	{Computing and Markets},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.12},
  URN =		{urn:nbn:de:0030-drops-2061},
  doi =		{10.4230/DagSemProc.05011.12},
  annote =	{Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio}
}
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