25 Search Results for "Sandholm, Tuomas"

Document
DOI: 10.4230/LIPIcs.ITCS.2024.5
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games

Authors: Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm, and Manolis Zampetakis

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Characterizing the performance of no-regret dynamics in multi-player games is a foundational problem at the interface of online learning and game theory. Recent results have revealed that when all players adopt specific learning algorithms, it is possible to improve exponentially over what is predicted by the overly pessimistic no-regret framework in the traditional adversarial regime, thereby leading to faster convergence to the set of coarse correlated equilibria (CCE) - a standard game-theoretic equilibrium concept. Yet, despite considerable recent progress, the fundamental complexity barriers for learning in normal- and extensive-form games are poorly understood. In this paper, we make a step towards closing this gap by first showing that - barring major complexity breakthroughs - any polynomial-time learning algorithms in extensive-form games need at least 2^{log^{1/2 - o(1)} |𝒯|} iterations for the average regret to reach below even an absolute constant, where |𝒯| is the number of nodes in the game. This establishes a superpolynomial separation between no-regret learning in normal- and extensive-form games, as in the former class a logarithmic number of iterations suffices to achieve constant average regret. Furthermore, our results imply that algorithms such as multiplicative weights update, as well as its optimistic counterpart, require at least 2^{(log log m)^{1/2 - o(1)}} iterations to attain an O(1)-CCE in m-action normal-form games under any parameterization. These are the first non-trivial - and dimension-dependent - lower bounds in that setting for the most well-studied algorithms in the literature. From a technical standpoint, we follow a beautiful connection recently made by Foster, Golowich, and Kakade (ICML '23) between sparse CCE and Nash equilibria in the context of Markov games. Consequently, our lower bounds rule out polynomial-time algorithms well beyond the traditional online learning framework, capturing techniques commonly used for accelerating centralized equilibrium computation.
Cite as

Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm, and Manolis Zampetakis. On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{anagnostides_et_al:LIPIcs.ITCS.2024.5,
  author =	{Anagnostides, Ioannis and Kalavasis, Alkis and Sandholm, Tuomas and Zampetakis, Manolis},
  title =	{{On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.5},
  URN =		{urn:nbn:de:0030-drops-195334},
  doi =		{10.4230/LIPIcs.ITCS.2024.5},
  annote =	{Keywords: No-regret learning, extensive-form games, multiplicative weights update, optimism, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.3
Improved Sample Complexity Bounds for Branch-And-Cut

Authors: Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
The branch-and-cut algorithm for integer programming has a wide variety of tunable parameters that have a huge impact on its performance, but which are challenging to tune by hand. An increasingly popular approach is to use machine learning to configure these parameters based on a training set of integer programs from the application domain. We bound how large the training set should be to ensure that for any configuration, its average performance over the training set is close to its expected future performance. Our guarantees apply to parameters that control the most important aspects of branch-and-cut: node selection, branching constraint selection, and cut selection, and are sharper and more general than those from prior research.
Cite as

Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Improved Sample Complexity Bounds for Branch-And-Cut. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{balcan_et_al:LIPIcs.CP.2022.3,
  author =	{Balcan, Maria-Florina and Prasad, Siddharth and Sandholm, Tuomas and Vitercik, Ellen},
  title =	{{Improved Sample Complexity Bounds for Branch-And-Cut}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.3},
  URN =		{urn:nbn:de:0030-drops-166321},
  doi =		{10.4230/LIPIcs.CP.2022.3},
  annote =	{Keywords: Automated algorithm configuration, integer programming, machine learning theory, tree search, branch-and-bound, branch-and-cut, cutting planes, sample complexity, generalization guarantees, data-driven algorithm design}
}
Document
DOI: 10.4230/DagSemProc.07431.1
07431 Abstracts Collection – Computational Issues in Social Choice

Authors: Ulle Endriss, Jérôme Lang, Francesca Rossi, and Tuomas Sandholm

Published in: Dagstuhl Seminar Proceedings, Volume 7431, Computational Issues in Social Choice (2007)

Abstract
From the 21st to the 26th of October 2007, the Dagstuhl Seminar 07431 on ``Computational Issues in Social Choice'' was held at the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their recent research, and ongoing work and open problems were discussed. The abstracts of the talks given during the seminar are collected in this paper. The first section summarises the seminar topics and goals in general. Links to full papers are provided where available.
Cite as

Ulle Endriss, Jérôme Lang, Francesca Rossi, and Tuomas Sandholm. 07431 Abstracts Collection – Computational Issues in Social Choice. In Computational Issues in Social Choice. Dagstuhl Seminar Proceedings, Volume 7431, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{endriss_et_al:DagSemProc.07431.1,
  author =	{Endriss, Ulle and Lang, J\'{e}r\^{o}me and Rossi, Francesca and Sandholm, Tuomas},
  title =	{{07431 Abstracts Collection – Computational Issues in Social Choice}},
  booktitle =	{Computational Issues in Social Choice},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7431},
  editor =	{Ulle Endriss and J\'{e}r\^{o}me Lang and Francesca Rossi 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.07431.1},
  URN =		{urn:nbn:de:0030-drops-12736},
  doi =		{10.4230/DagSemProc.07431.1},
  annote =	{Keywords: Computational social choice, voting theory, fair division, mechanism design, coalition formation, complexity theory, preference representation, algorithms}
}
Document
DOI: 10.4230/DagSemProc.07431.2
07431 Executive Summary – Computational Issues in Social Choice

Authors: Ulle Endriss, Jérôme Lang, Francesca Rossi, and Tuomas Sandholm

Published in: Dagstuhl Seminar Proceedings, Volume 7431, Computational Issues in Social Choice (2007)

Abstract
Computational social choice is an interdisciplinary field of study at the interface of social choice theory and computer science, with knowledge flowing in either direction. On the one hand, computational social choice is concerned with importing concepts and procedures from social choice theory for solving questions that arise in computer science and AI application domains. This is typically the case for managing societies of autonomous agents, which calls for negotiation and voting procedures. On the other hand, computational social choice is concerned with importing notions and methods from computer science for solving questions originally stemming from social choice, for instance by providing new perspectives on the problem of manipulation and control in elections. This Dagstuhl Seminar has been devoted to the presentation of recent results and an exchange of ideas in this growing research field.
Cite as

Ulle Endriss, Jérôme Lang, Francesca Rossi, and Tuomas Sandholm. 07431 Executive Summary – Computational Issues in Social Choice. In Computational Issues in Social Choice. Dagstuhl Seminar Proceedings, Volume 7431, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{endriss_et_al:DagSemProc.07431.2,
  author =	{Endriss, Ulle and Lang, J\'{e}r\^{o}me and Rossi, Francesca and Sandholm, Tuomas},
  title =	{{07431 Executive Summary – Computational Issues in Social Choice}},
  booktitle =	{Computational Issues in Social Choice},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7431},
  editor =	{Ulle Endriss and J\'{e}r\^{o}me Lang and Francesca Rossi 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.07431.2},
  URN =		{urn:nbn:de:0030-drops-12749},
  doi =		{10.4230/DagSemProc.07431.2},
  annote =	{Keywords: Computational social choice, voting theory, fair division, mechanism design, coalition formation, complexity theory, preference representation, algorithms}
}
Document
DOI: 10.4230/DagSemProc.05011.5
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
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-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
DOI: 10.4230/DagSemProc.05011.1
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
DOI: 10.4230/DagSemProc.05011.2
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
DOI: 10.4230/DagSemProc.05011.6
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
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-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
DOI: 10.4230/DagSemProc.05011.3
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
DOI: 10.4230/DagSemProc.05011.4
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
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-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
DOI: 10.4230/DagSemProc.05011.8
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
DOI: 10.4230/DagSemProc.05011.10
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}
}
  • Refine by Author
  • 10 Sandholm, Tuomas
  • 5 Müller, Rudolf
  • 4 Tennenholtz, Moshe
  • 3 Lehmann, Daniel
  • 2 Endriss, Ulle
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Convergence and learning in games
  • 1 Theory of computation → Integer programming
  • 1 Theory of computation → Sample complexity and generalization bounds

  • 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
  • 25 document

  • Refine by Publication Year
  • 20 2005
  • 2 2007
  • 1 2002
  • 1 2022
  • 1 2024

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