Search Results

Documents authored by Tang, Bo

Document
DOI: 10.4230/LIPIcs.ITCS.2017.57
Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games

Authors: Xi Chen, Yu Cheng, and Bo Tang

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
In this paper we present a generic reduction from the problem of finding an \epsilon-well-supported Nash equilibrium (WSNE) to that of finding an \Theta(\epsilon)-approximate Nash equilibrium (ANE), in large games with n players and a bounded number of strategies for each player. Our reduction complements the existing literature on relations between WSNE and ANE, and can be applied to extend hardness results on WSNE to similar results on ANE. This allows one to focus on WSNE first, which is in general easier to analyze and control in hardness constructions. As an application we prove a 2^{\Omega(n/\log n)} lower bound on the randomized query complexity of finding an \epsilon-ANE in binary-action n-player games, for some constant \epsilon>0. This answers an open problem posed by Hart and Nisan and Babichenko, and is very close to the trivial upper bound of 2^n. Previously for WSNE, Babichenko showed a 2^{\Omega(n)} lower bound on the randomized query complexity of finding an \epsilon-WSNE for some constant epsilon>0. Our result follows directly from combining Babichenko's result and our new reduction from WSNE to ANE.
Cite as

Xi Chen, Yu Cheng, and Bo Tang. Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 57:1-57:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2017.57,
  author =	{Chen, Xi and Cheng, Yu and Tang, Bo},
  title =	{{Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{57:1--57:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.57},
  URN =		{urn:nbn:de:0030-drops-81636},
  doi =		{10.4230/LIPIcs.ITCS.2017.57},
  annote =	{Keywords: Equilibrium Computation, Query Complexity, Large Games}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.478
The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems

Authors: Tengyu Ma, Bo Tang, and Yajun Wang

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We study the matroid secretary problems with submodular valuation functions. In these problems, the elements arrive in random order. When one element arrives, we have to make an immediate and irrevocable decision on whether to accept it or not. The set of accepted elements must form an independent set in a predefined matroid. Our objective is to maximize the value of the accepted elements. In this paper, we focus on the case that the valuation function is a non-negative and monotonically non-decreasing submodular function. We introduce a general algorithm for such submodular matroid secretary problems. In particular, we obtain constant competitive algorithms for the cases of laminar matroids and transversal matroids. Our algorithms can be further applied to any independent set system defined by the intersection of a constant number of laminar matroids, while still achieving constant competitive ratios. Notice that laminar matroids generalize uniform matroids and partition matroids. On the other hand, when the underlying valuation function is linear, our algorithm achieves a competitive ratio of 9.6 for laminar matroids, which significantly improves the previous result.
Cite as

Tengyu Ma, Bo Tang, and Yajun Wang. The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 478-489, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{ma_et_al:LIPIcs.STACS.2013.478,
  author =	{Ma, Tengyu and Tang, Bo and Wang, Yajun},
  title =	{{The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{478--489},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.478},
  URN =		{urn:nbn:de:0030-drops-39586},
  doi =		{10.4230/LIPIcs.STACS.2013.478},
  annote =	{Keywords: secretary problem, submodular function, matroid, online algorithm}
}
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 About DROPS Imprint Privacy Contact