On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2014-06-14

AUTHORS

Khaled Elbassioni, Kazuhisa Makino, Kurt Mehlhorn, Fahimeh Ramezani

ABSTRACT

Given two bounded convex sets X⊆Rm\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X\subseteq \mathbb R^m$$\end{document} and Y⊆Rn,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Y\subseteq \mathbb R^n,$$\end{document} specified by membership oracles, and a continuous convex–concave function F:X×Y→R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F:X\times Y\rightarrow \mathbb R$$\end{document}, we consider the problem of computing an ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}-approximate saddle point, that is, a pair (x∗,y∗)∈X×Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(x^*,y^*)\in X\times Y$$\end{document} such that supy∈YF(x∗,y)≤infx∈XF(x,y∗)+ε.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sup _{y\in Y} F(x^*,y)\le \inf _{x\in X}F(x,y^*)+\varepsilon .$$\end{document} Grigoriadis and Khachiyan (Oper Res Lett 18(2):53–58, 1995) gave a simple randomized variant of fictitious play for computing an ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}-approximate saddle point for matrix games, that is, when F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F$$\end{document} is bilinear and the sets X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X$$\end{document} and Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Y$$\end{document} are simplices. In this paper, we extend their method to the general case. In particular, we show that, for functions of constant “width”, an ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}-approximate saddle point can be computed using O∗((n+m)ε2lnR)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^* \big (\frac{(n+m)}{\varepsilon ^2}\ln R \big )$$\end{document} random samples from log-concave distributions over the convex sets X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X$$\end{document} and Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Y$$\end{document}. It is assumed that X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X$$\end{document} and Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Y$$\end{document} have inscribed balls of radius 1/R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/R$$\end{document} and circumscribing balls of radius R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R$$\end{document}. As a consequence, we obtain a simple randomized polynomial-time algorithm that computes such an approximation faster than known methods for problems with bounded width and when ε∈(0,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon \in (0,1)$$\end{document} is a fixed, but arbitrarily small constant. Our main tool for achieving this result is the combination of the randomized fictitious play with the recently developed results on sampling from convex sets. More... »

PAGES

441-459

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-014-9902-8

DOI

http://dx.doi.org/10.1007/s00453-014-9902-8

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1001176399


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Masdar Institute of Science and Technology, Abu Dhabi, UAE", 
          "id": "http://www.grid.ac/institutes/grid.440568.b", 
          "name": [
            "Masdar Institute of Science and Technology, Abu Dhabi, UAE"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Elbassioni", 
        "givenName": "Khaled", 
        "id": "sg:person.012561735335.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012561735335.16"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Research Institute for Mathematical Sciences (RIMS), Kyoto University, 606-8502, Kyoto, Japan", 
          "id": "http://www.grid.ac/institutes/grid.258799.8", 
          "name": [
            "Research Institute for Mathematical Sciences (RIMS), Kyoto University, 606-8502, Kyoto, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Makino", 
        "givenName": "Kazuhisa", 
        "id": "sg:person.07741653331.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07741653331.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbruecken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbruecken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbruecken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbruecken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ramezani", 
        "givenName": "Fahimeh", 
        "id": "sg:person.011016565440.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011016565440.58"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/11776420_37", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033945667", 
          "https://doi.org/10.1007/11776420_37"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00535467", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041597985", 
          "https://doi.org/10.1007/bf00535467"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-02927-1_48", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053741214", 
          "https://doi.org/10.1007/978-3-642-02927-1_48"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-30140-0_34", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011326710", 
          "https://doi.org/10.1007/978-3-540-30140-0_34"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-78240-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033583445", 
          "https://doi.org/10.1007/978-3-642-78240-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01903847", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000811868", 
          "https://doi.org/10.1007/bf01903847"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2014-06-14", 
    "datePublishedReg": "2014-06-14", 
    "description": "Given two bounded convex sets X\u2286Rm\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$X\\subseteq \\mathbb R^m$$\\end{document} and Y\u2286Rn,\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$Y\\subseteq \\mathbb R^n,$$\\end{document} specified by membership oracles, and a continuous convex\u2013concave function F:X\u00d7Y\u2192R\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$F:X\\times Y\\rightarrow \\mathbb R$$\\end{document}, we consider the problem of computing an \u03b5\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\varepsilon $$\\end{document}-approximate saddle point, that is, a pair (x\u2217,y\u2217)\u2208X\u00d7Y\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$(x^*,y^*)\\in X\\times Y$$\\end{document} such that supy\u2208YF(x\u2217,y)\u2264infx\u2208XF(x,y\u2217)+\u03b5.\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\sup _{y\\in Y} F(x^*,y)\\le \\inf _{x\\in X}F(x,y^*)+\\varepsilon .$$\\end{document} Grigoriadis and Khachiyan (Oper Res Lett 18(2):53\u201358, 1995) gave a simple randomized variant of fictitious play for computing an \u03b5\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\varepsilon $$\\end{document}-approximate saddle point for matrix games, that is, when F\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$F$$\\end{document} is bilinear and the sets X\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$X$$\\end{document} and Y\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$Y$$\\end{document} are simplices. In this paper, we extend their method to the general case. In particular, we show that, for functions of constant \u201cwidth\u201d, an \u03b5\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\varepsilon $$\\end{document}-approximate saddle point can be computed using O\u2217((n+m)\u03b52lnR)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O^* \\big (\\frac{(n+m)}{\\varepsilon ^2}\\ln R \\big )$$\\end{document} random samples from log-concave distributions over the convex sets X\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$X$$\\end{document} and Y\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$Y$$\\end{document}. It is assumed that X\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$X$$\\end{document} and Y\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$Y$$\\end{document} have inscribed balls of radius 1/R\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$1/R$$\\end{document} and circumscribing balls of radius R\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$R$$\\end{document}. As a consequence, we obtain a simple randomized polynomial-time algorithm that computes such an approximation faster than known methods for problems with bounded width and when \u03b5\u2208(0,1)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\varepsilon \\in (0,1)$$\\end{document} is a fixed, but arbitrarily small constant. Our main tool for achieving this result is the combination of the randomized fictitious play with the recently developed results on sampling from convex sets.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-014-9902-8", 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.6129362", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.6077061", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "73"
      }
    ], 
    "keywords": [
      "convex sets", 
      "approximate saddle point", 
      "saddle point", 
      "set", 
      "membership oracle", 
      "function f", 
      "problem", 
      "point", 
      "Grigoriadis", 
      "Khachiyan", 
      "fictitious play", 
      "play", 
      "matrix games", 
      "bilinear", 
      "simplices", 
      "general case", 
      "random sample", 
      "log-concave distributions", 
      "ball of radius", 
      "polynomial time algorithm", 
      "algorithm", 
      "approximation", 
      "main tool", 
      "oracle", 
      "pairs", 
      "variants", 
      "game", 
      "paper", 
      "method", 
      "cases", 
      "function", 
      "width", 
      "samples", 
      "distribution", 
      "ball", 
      "radius", 
      "consequences", 
      "tool", 
      "results", 
      "combination"
    ], 
    "name": "On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets", 
    "pagination": "441-459", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001176399"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-014-9902-8"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-014-9902-8", 
      "https://app.dimensions.ai/details/publication/pub.1001176399"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:39", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_644.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-014-9902-8"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9902-8'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9902-8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9902-8'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-014-9902-8'


 

This table displays all metadata directly associated to this object as RDF triples.

152 TRIPLES      21 PREDICATES      70 URIs      56 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-014-9902-8 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N108f518ff02f4ca49226799493f3e7b1
4 schema:citation sg:pub.10.1007/11776420_37
5 sg:pub.10.1007/978-3-540-30140-0_34
6 sg:pub.10.1007/978-3-642-02927-1_48
7 sg:pub.10.1007/978-3-642-78240-4
8 sg:pub.10.1007/bf00535467
9 sg:pub.10.1007/bf01903847
10 schema:datePublished 2014-06-14
11 schema:datePublishedReg 2014-06-14
12 schema:description Given two bounded convex sets X⊆Rm\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X\subseteq \mathbb R^m$$\end{document} and Y⊆Rn,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Y\subseteq \mathbb R^n,$$\end{document} specified by membership oracles, and a continuous convex–concave function F:X×Y→R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F:X\times Y\rightarrow \mathbb R$$\end{document}, we consider the problem of computing an ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}-approximate saddle point, that is, a pair (x∗,y∗)∈X×Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(x^*,y^*)\in X\times Y$$\end{document} such that supy∈YF(x∗,y)≤infx∈XF(x,y∗)+ε.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sup _{y\in Y} F(x^*,y)\le \inf _{x\in X}F(x,y^*)+\varepsilon .$$\end{document} Grigoriadis and Khachiyan (Oper Res Lett 18(2):53–58, 1995) gave a simple randomized variant of fictitious play for computing an ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}-approximate saddle point for matrix games, that is, when F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F$$\end{document} is bilinear and the sets X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X$$\end{document} and Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Y$$\end{document} are simplices. In this paper, we extend their method to the general case. In particular, we show that, for functions of constant “width”, an ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}-approximate saddle point can be computed using O∗((n+m)ε2lnR)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O^* \big (\frac{(n+m)}{\varepsilon ^2}\ln R \big )$$\end{document} random samples from log-concave distributions over the convex sets X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X$$\end{document} and Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Y$$\end{document}. It is assumed that X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X$$\end{document} and Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Y$$\end{document} have inscribed balls of radius 1/R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/R$$\end{document} and circumscribing balls of radius R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R$$\end{document}. As a consequence, we obtain a simple randomized polynomial-time algorithm that computes such an approximation faster than known methods for problems with bounded width and when ε∈(0,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon \in (0,1)$$\end{document} is a fixed, but arbitrarily small constant. Our main tool for achieving this result is the combination of the randomized fictitious play with the recently developed results on sampling from convex sets.
13 schema:genre article
14 schema:isAccessibleForFree true
15 schema:isPartOf N1aa5f435c61349eea36859cc994a3b4c
16 N720be1af2aa0440bb0e556328274a90a
17 sg:journal.1047644
18 schema:keywords Grigoriadis
19 Khachiyan
20 algorithm
21 approximate saddle point
22 approximation
23 ball
24 ball of radius
25 bilinear
26 cases
27 combination
28 consequences
29 convex sets
30 distribution
31 fictitious play
32 function
33 function f
34 game
35 general case
36 log-concave distributions
37 main tool
38 matrix games
39 membership oracle
40 method
41 oracle
42 pairs
43 paper
44 play
45 point
46 polynomial time algorithm
47 problem
48 radius
49 random sample
50 results
51 saddle point
52 samples
53 set
54 simplices
55 tool
56 variants
57 width
58 schema:name On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets
59 schema:pagination 441-459
60 schema:productId N13c9e0fd2f59485fb4ee8c3667f9aae3
61 N4b8596b185444d878d7700140ac3710b
62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001176399
63 https://doi.org/10.1007/s00453-014-9902-8
64 schema:sdDatePublished 2022-10-01T06:39
65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
66 schema:sdPublisher Nc7c65c76a18a464dbb3b4345596821a7
67 schema:url https://doi.org/10.1007/s00453-014-9902-8
68 sgo:license sg:explorer/license/
69 sgo:sdDataset articles
70 rdf:type schema:ScholarlyArticle
71 N108f518ff02f4ca49226799493f3e7b1 rdf:first sg:person.012561735335.16
72 rdf:rest N43ab5c36534444269c18c635307cb296
73 N13c9e0fd2f59485fb4ee8c3667f9aae3 schema:name dimensions_id
74 schema:value pub.1001176399
75 rdf:type schema:PropertyValue
76 N1aa5f435c61349eea36859cc994a3b4c schema:volumeNumber 73
77 rdf:type schema:PublicationVolume
78 N43ab5c36534444269c18c635307cb296 rdf:first sg:person.07741653331.03
79 rdf:rest N96ddf2dc431444bb815cb9bbbb3b2b02
80 N4a114f5196dd4435baf0ac21af2d16cc rdf:first sg:person.011016565440.58
81 rdf:rest rdf:nil
82 N4b8596b185444d878d7700140ac3710b schema:name doi
83 schema:value 10.1007/s00453-014-9902-8
84 rdf:type schema:PropertyValue
85 N720be1af2aa0440bb0e556328274a90a schema:issueNumber 2
86 rdf:type schema:PublicationIssue
87 N96ddf2dc431444bb815cb9bbbb3b2b02 rdf:first sg:person.011757371347.43
88 rdf:rest N4a114f5196dd4435baf0ac21af2d16cc
89 Nc7c65c76a18a464dbb3b4345596821a7 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information and Computing Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
95 schema:name Computation Theory and Mathematics
96 rdf:type schema:DefinedTerm
97 sg:grant.6077061 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-014-9902-8
98 rdf:type schema:MonetaryGrant
99 sg:grant.6129362 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-014-9902-8
100 rdf:type schema:MonetaryGrant
101 sg:journal.1047644 schema:issn 0178-4617
102 1432-0541
103 schema:name Algorithmica
104 schema:publisher Springer Nature
105 rdf:type schema:Periodical
106 sg:person.011016565440.58 schema:affiliation grid-institutes:grid.419528.3
107 schema:familyName Ramezani
108 schema:givenName Fahimeh
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011016565440.58
110 rdf:type schema:Person
111 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
112 schema:familyName Mehlhorn
113 schema:givenName Kurt
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
115 rdf:type schema:Person
116 sg:person.012561735335.16 schema:affiliation grid-institutes:grid.440568.b
117 schema:familyName Elbassioni
118 schema:givenName Khaled
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012561735335.16
120 rdf:type schema:Person
121 sg:person.07741653331.03 schema:affiliation grid-institutes:grid.258799.8
122 schema:familyName Makino
123 schema:givenName Kazuhisa
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07741653331.03
125 rdf:type schema:Person
126 sg:pub.10.1007/11776420_37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033945667
127 https://doi.org/10.1007/11776420_37
128 rdf:type schema:CreativeWork
129 sg:pub.10.1007/978-3-540-30140-0_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011326710
130 https://doi.org/10.1007/978-3-540-30140-0_34
131 rdf:type schema:CreativeWork
132 sg:pub.10.1007/978-3-642-02927-1_48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053741214
133 https://doi.org/10.1007/978-3-642-02927-1_48
134 rdf:type schema:CreativeWork
135 sg:pub.10.1007/978-3-642-78240-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033583445
136 https://doi.org/10.1007/978-3-642-78240-4
137 rdf:type schema:CreativeWork
138 sg:pub.10.1007/bf00535467 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041597985
139 https://doi.org/10.1007/bf00535467
140 rdf:type schema:CreativeWork
141 sg:pub.10.1007/bf01903847 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000811868
142 https://doi.org/10.1007/bf01903847
143 rdf:type schema:CreativeWork
144 grid-institutes:grid.258799.8 schema:alternateName Research Institute for Mathematical Sciences (RIMS), Kyoto University, 606-8502, Kyoto, Japan
145 schema:name Research Institute for Mathematical Sciences (RIMS), Kyoto University, 606-8502, Kyoto, Japan
146 rdf:type schema:Organization
147 grid-institutes:grid.419528.3 schema:alternateName Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbruecken, Germany
148 schema:name Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbruecken, Germany
149 rdf:type schema:Organization
150 grid-institutes:grid.440568.b schema:alternateName Masdar Institute of Science and Technology, Abu Dhabi, UAE
151 schema:name Masdar Institute of Science and Technology, Abu Dhabi, UAE
152 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...