22 Search Results for "Lehmann, Daniel"


Document
Spoofax at Oracle: Domain-Specific Language Engineering for Large-Scale Graph Analytics

Authors: Houda Boukham, Guido Wachsmuth, Toine Hartman, Hamza Boucherit, Oskar van Rest, Hassan Chafi, Sungpack Hong, Martijn Dwars, Arnaud Delamare, and Dalila Chiadmi

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)


Abstract
For the last decade, teams at Oracle relied on the Spoofax language workbench to develop a family of domain-specific languages for graph analytics in research projects and in product development. In this paper, we analyze the requirements for integrating language processors into large-scale graph analytics toolkits and for the development of these language processors as part of a larger product development process. We discuss how Spoofax helps to meet these requirements and point out the need for future improvements.

Cite as

Houda Boukham, Guido Wachsmuth, Toine Hartman, Hamza Boucherit, Oskar van Rest, Hassan Chafi, Sungpack Hong, Martijn Dwars, Arnaud Delamare, and Dalila Chiadmi. Spoofax at Oracle: Domain-Specific Language Engineering for Large-Scale Graph Analytics. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 5:1-5:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{boukham_et_al:OASIcs.EVCS.2023.5,
  author =	{Boukham, Houda and Wachsmuth, Guido and Hartman, Toine and Boucherit, Hamza and van Rest, Oskar and Chafi, Hassan and Hong, Sungpack and Dwars, Martijn and Delamare, Arnaud and Chiadmi, Dalila},
  title =	{{Spoofax at Oracle: Domain-Specific Language Engineering for Large-Scale Graph Analytics}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{5:1--5:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.5},
  URN =		{urn:nbn:de:0030-drops-177756},
  doi =		{10.4230/OASIcs.EVCS.2023.5},
  annote =	{Keywords: language workbench, domain-specific language}
}
Document
Automated Mechanism Design

Authors: Tuomas Sandholm

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


Abstract
Mechanisms design has traditionally been a manual endeavor. In 2002, Conitzer and Sandholm introduced the automated mechanism design (AMD) approach, where the mechanism is computationally created for the specific problem instance at hand. This has several advantages: 1) it can yield better mechanisms than the ones known to date, 2) it applies beyond the problem classes studied manually to date, 3) it can circumvent seminal economic impossibility results that hold for classes of problems but not all instances, and 4) it shifts the burden of design from man to machine. In this talk I will overview our results on AMD to date. I will cover problem representations and the computational complexity of different variants of the design problem. Initial applications include revenue-maximizing combinatorial auctions and (combinatorial) public goods problems. Algorithms for AMD will be discussed. To reduce the computational complexity of designing optimal combinatorial auctions, I introduce an incentive compatible, individually rational subfamily called Virtual Valuations Combinatorial Auctions. The auction mechanism's revenue can be boosted (started, for example, from the VCG) by hill-climbing in this subspace. I will also present computational complexity and communication complexity results that motivate multi-stage and non-truth-promoting mechanisms. Finally, I present our first steps toward automatically designing multi-stage mechanisms.

Cite as

Tuomas Sandholm. Automated Mechanism Design. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{sandholm:DagSemProc.05011.5,
  author =	{Sandholm, Tuomas},
  title =	{{Automated Mechanism Design}},
  booktitle =	{Computing and Markets},
  pages =	{1--2},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.5},
  URN =		{urn:nbn:de:0030-drops-2677},
  doi =		{10.4230/DagSemProc.05011.5},
  annote =	{Keywords: Automated mechanism design, mechanism design}
}
Document
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-dev.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
05011 Abstracts Collection – Computing and Markets

Authors: Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm

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


Abstract
From 03.01.05 to 07.01.05, the Dagstuhl Seminar 05011``Computing and Markets'' 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

Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm. 05011 Abstracts Collection – Computing and Markets. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{lehmann_et_al:DagSemProc.05011.1,
  author =	{Lehmann, Daniel and M\"{u}ller, Rudolf and Sandholm, Tuomas},
  title =	{{05011 Abstracts Collection – Computing and Markets}},
  booktitle =	{Computing and Markets},
  pages =	{1--26},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.1},
  URN =		{urn:nbn:de:0030-drops-2250},
  doi =		{10.4230/DagSemProc.05011.1},
  annote =	{Keywords: Algorithms, complexity, game theory, social choice, auctions, equilibrium}
}
Document
05011 Executive Summary – Computing and Markets

Authors: Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm

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


Abstract
The seminar Computing and Markets 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 markets that takes into account both the economic and the computational issues---and their deep interaction.

Cite as

Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm. 05011 Executive Summary – Computing and Markets. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{lehmann_et_al:DagSemProc.05011.2,
  author =	{Lehmann, Daniel and M\"{u}ller, Rudolf and Sandholm, Tuomas},
  title =	{{05011 Executive Summary – Computing and Markets}},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.2},
  URN =		{urn:nbn:de:0030-drops-2248},
  doi =		{10.4230/DagSemProc.05011.2},
  annote =	{Keywords: Algorithms, complexity, game theory, social choice, auctions, equilibrium}
}
Document
Computing Nash Equilibria of Action-Graph Games

Authors: Kevin Leyton-Brown and Navin A.R. Bhat

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 Navin A.R. Bhat. Computing Nash Equilibria of Action-Graph Games. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{leytonbrown_et_al:DagSemProc.05011.6,
  author =	{Leyton-Brown, Kevin and Bhat, Navin A.R.},
  title =	{{Computing Nash Equilibria of Action-Graph Games}},
  booktitle =	{Computing and Markets},
  pages =	{1--8},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.6},
  URN =		{urn:nbn:de:0030-drops-2209},
  doi =		{10.4230/DagSemProc.05011.6},
  annote =	{Keywords: compact representation of games, action-graph games, Nash equilibria}
}
Document
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-dev.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
A Contract and Balancing Mechanism for Sharing Capacity in a Communication Network

Authors: Edward Anderson, Frank Kelly, and Richard Steinberg

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


Abstract
We propose a method for determining how much to charge users of a communication network when they share bandwidth. Our approach can be employed either when a network owner wishes to sell bandwidth for a specified period of time to a number of different users, or when users cooperate to build a network to be shared among themselves. We show how a Contract and Balancing Mechanism can be defined to mediate between rapidly fluctuating prices and the longer time scales over which bandwidth contracts might be traded. An important property of the process is that it avoids introducing perverse incentives for a capacity provider to increase congestion.

Cite as

Edward Anderson, Frank Kelly, and Richard Steinberg. A Contract and Balancing Mechanism for Sharing Capacity in a Communication Network. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.05011.3,
  author =	{Anderson, Edward and Kelly, Frank and Steinberg, Richard},
  title =	{{A Contract and Balancing Mechanism for Sharing Capacity in a Communication Network}},
  booktitle =	{Computing and Markets},
  pages =	{1--31},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.3},
  URN =		{urn:nbn:de:0030-drops-2041},
  doi =		{10.4230/DagSemProc.05011.3},
  annote =	{Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio}
}
Document
A Network Approach to Bayes-Nash Incentive Compatible Mechanisms

Authors: Rudolf Müller, Andres Perea, and Sascha Wolf

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


Abstract
This paper provides a characterization of Bayes-Nash incentive compatible mechanisms in settings where agents have one-dimensional or multi-dimensional types, quasi-linear utility functions and interdependent valuations. The characterization is derived in terms of conditions for the underlying allocation function. We do this by making a link to network theory and building complete directed graphs for agents type spaces. We show that an allocation rule is Bayes-Nash incentive compatible if and only if these graphs have no negative, finite cycles. In the case of one-dimensional types and given certain properties for agents valuation functions, we show that this condition reduces to the absence of negative 2-cycles. In the case of multi-dimensional types and given a linearity requirement on the valuation functions, we show that this condition reduces to the absence of negative 2-cycles and an integratebility condition on the valuation functions.

Cite as

Rudolf Müller, Andres Perea, and Sascha Wolf. A Network Approach to Bayes-Nash Incentive Compatible Mechanisms. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{muller_et_al:DagSemProc.05011.4,
  author =	{M\"{u}ller, Rudolf and Perea, Andres and Wolf, Sascha},
  title =	{{A Network Approach to Bayes-Nash Incentive Compatible Mechanisms}},
  booktitle =	{Computing and Markets},
  pages =	{1--10},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.4},
  URN =		{urn:nbn:de:0030-drops-2056},
  doi =		{10.4230/DagSemProc.05011.4},
  annote =	{Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio}
}
Document
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-dev.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
Dominant Strategy Mechanisms with Multidimensional Types

Authors: Hongwei Gui, Rudolf Müller, and Rakesh V. Vohra

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


Abstract
This paper provides a characterization of dominant strategy mechanisms with quasi-linear utilities and multi-dimensional types for a variety of preference domains. These characterizations are in terms of a monotonicity property on the underlying allocation rule.

Cite as

Hongwei Gui, Rudolf Müller, and Rakesh V. Vohra. Dominant Strategy Mechanisms with Multidimensional Types. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{hongweigui_et_al:DagSemProc.05011.8,
  author =	{Hongwei Gui and M\"{u}ller, Rudolf and Vohra, Rakesh V.},
  title =	{{Dominant Strategy Mechanisms with Multidimensional Types}},
  booktitle =	{Computing and Markets},
  pages =	{1--23},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.8},
  URN =		{urn:nbn:de:0030-drops-2107},
  doi =		{10.4230/DagSemProc.05011.8},
  annote =	{Keywords: Dominant Strategy, Farkas Lemma,}
}
Document
Fundamentals in Discrete Convex Analysis

Authors: Kazuo Murota

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


Abstract
This talk describes fundamental properties of M-convex and L-convex functions that play the central roles in discrete convex analysis. These concepts were originally introduced in combinatorial optimization, but turned out to be relevant in economics. Emphasis is put on discrete duality and conjugacy respect to the Legendre-Fenchel transformation. Monograph information: http://www.misojiro.t.u-tokyo.ac.jp/~murota/mybooks.html#DCAsiam2003

Cite as

Kazuo Murota. Fundamentals in Discrete Convex Analysis. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{murota:DagSemProc.05011.10,
  author =	{Murota, Kazuo},
  title =	{{Fundamentals in Discrete Convex Analysis}},
  booktitle =	{Computing and Markets},
  pages =	{1--2},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.10},
  URN =		{urn:nbn:de:0030-drops-2167},
  doi =		{10.4230/DagSemProc.05011.10},
  annote =	{Keywords: gross substitute, discrete convex functions, M-convex function, Fenchel-Legendre transformation}
}
Document
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-dev.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}
}
Document
Reference-Dependent Preferences in Multi-Issue Bargaining

Authors: Henner Gimpel

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


Abstract
Game theoretic bargaining models usually assume parties to have exogenously given preferences from the beginning of a negotiation on. Preferences in these models do not depend on the history of offers made during a negotiation. This paper argues that preferences are based on issue-wise reference points changing during the bargaining process as result of the counterpartys offers.

Cite as

Henner Gimpel. Reference-Dependent Preferences in Multi-Issue Bargaining. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{gimpel:DagSemProc.05011.13,
  author =	{Gimpel, Henner},
  title =	{{Reference-Dependent Preferences in Multi-Issue Bargaining}},
  booktitle =	{Computing and Markets},
  pages =	{1--5},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.13},
  URN =		{urn:nbn:de:0030-drops-2038},
  doi =		{10.4230/DagSemProc.05011.13},
  annote =	{Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio}
}
Document
Self-Confirming Price Prediction for Bidding in Simultaneous Ascending Auctions

Authors: Anna Osepayshvili, Michael Wellman, Daniel Reeves, and Jeffrey MacKie-Mason

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


Abstract
Simultaneous, separate ascending auctions are ubiquitous, even when agents have preferences over combinations of goods, from which arises the emph{exposure problem}. Little is known about strategies that perform well when the exposure problem is important. We present a new family of bidding strategies for this situation, in which agents form and utilize various amounts of information from predictions of the distribution of final prices. The predictor strategies we define differ in their choice of method for generating the initial (pre-auction) prediction. We explore several methods, but focus on emph{self-confirming} predictions. An agents prediction of characteristics of the distribution of closing prices is self-confirming if, when all agents follow the same predictor bidding strategy, the final price distributions that actually result are consistent with the utilized characteristics of the prediction. We extensively analyze an auction environment with five goods, and five agents who each can choose from 53 different bidding strategies (resulting in over 4.2 million distinct strategy combinations). We find that the self-confirming distribution predictor is a highly stable, pure-strategy Nash equilibrium. We have been unable to find any other Nash strategies in this environment. In limited experiments in other environments the self-confirming distribution predictor consistently performs well, but is not generally a pure-strategy Nash equilibrium.

Cite as

Anna Osepayshvili, Michael Wellman, Daniel Reeves, and Jeffrey MacKie-Mason. Self-Confirming Price Prediction for Bidding in Simultaneous Ascending Auctions. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{osepayshvili_et_al:DagSemProc.05011.14,
  author =	{Osepayshvili, Anna and Wellman, Michael and Reeves, Daniel and MacKie-Mason, Jeffrey},
  title =	{{Self-Confirming Price Prediction for Bidding in Simultaneous Ascending Auctions}},
  booktitle =	{Computing and Markets},
  pages =	{1--9},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.14},
  URN =		{urn:nbn:de:0030-drops-2020},
  doi =		{10.4230/DagSemProc.05011.14},
  annote =	{Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategies}
}
  • Refine by Author
  • 6 Sandholm, Tuomas
  • 5 Müller, Rudolf
  • 4 Tennenholtz, Moshe
  • 3 Lehmann, Daniel
  • 2 Leyton-Brown, Kevin
  • Show More...

  • Refine by Classification
  • 1 Software and its engineering → Domain specific languages
  • 1 Software and its engineering → Translator writing systems and compiler generators

  • Refine by Keyword
  • 9 compact representation of games
  • 8 congestion games
  • 7 local-effect games
  • 6 action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio
  • 3 auctions
  • Show More...

  • Refine by Type
  • 22 document

  • Refine by Publication Year
  • 20 2005
  • 1 2002
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail