Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2016-09-17

AUTHORS

Khaled Elbassioni, Kurt Mehlhorn, Fahimeh Ramezani

ABSTRACT

R. Lavi and C. Swamy (FOCS 2005, J. ACM 58(6), 25, 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees. More... »

PAGES

641-663

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00224-016-9704-2

DOI

http://dx.doi.org/10.1007/s00224-016-9704-2

DIMENSIONS

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


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, United Arab Emirates", 
          "id": "http://www.grid.ac/institutes/grid.440568.b", 
          "name": [
            "Masdar Institute of Science and Technology, Abu Dhabi, United Arab Emirates"
          ], 
          "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": "Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbrucken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbrucken, 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": "Department of Mathematics, University of Isfahan, 81746-73441, Isfahan, Iran", 
          "id": "http://www.grid.ac/institutes/grid.411750.6", 
          "name": [
            "Department of Mathematics, University of Isfahan, 81746-73441, Isfahan, Iran"
          ], 
          "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/978-3-319-13129-0_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039301089", 
          "https://doi.org/10.1007/978-3-319-13129-0_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-97881-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051732087", 
          "https://doi.org/10.1007/978-3-642-97881-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-48433-3_8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021943040", 
          "https://doi.org/10.1007/978-3-662-48433-3_8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-69346-7_12", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003337212", 
          "https://doi.org/10.1007/3-540-69346-7_12"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-17572-5_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024906405", 
          "https://doi.org/10.1007/978-3-642-17572-5_14"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2016-09-17", 
    "datePublishedReg": "2016-09-17", 
    "description": "R. Lavi and C. Swamy (FOCS 2005, J. ACM 58(6), 25, 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00224-016-9704-2", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "59"
      }
    ], 
    "keywords": [
      "LAVI", 
      "weight", 
      "method", 
      "mechanism", 
      "use", 
      "practice", 
      "linear programming", 
      "ellipsoid method", 
      "algorithmic mechanism design", 
      "truthfulness guarantee", 
      "technique", 
      "approximation algorithm", 
      "direct implementation", 
      "multiplicative weights", 
      "cost", 
      "mechanism design", 
      "programming", 
      "implementation", 
      "design", 
      "algorithm", 
      "guarantees", 
      "general method", 
      "expectation mechanisms", 
      "weak approximation", 
      "simplification", 
      "Swamy", 
      "approximation"
    ], 
    "name": "Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design", 
    "pagination": "641-663", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1003152366"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00224-016-9704-2"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00224-016-9704-2", 
      "https://app.dimensions.ai/details/publication/pub.1003152366"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:42", 
    "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_699.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00224-016-9704-2"
  }
]
 

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/s00224-016-9704-2'

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/s00224-016-9704-2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-016-9704-2'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-016-9704-2'


 

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

124 TRIPLES      21 PREDICATES      56 URIs      43 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00224-016-9704-2 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N58fd60026b6841578b8ac004537e2d95
4 schema:citation sg:pub.10.1007/3-540-69346-7_12
5 sg:pub.10.1007/978-3-319-13129-0_9
6 sg:pub.10.1007/978-3-642-17572-5_14
7 sg:pub.10.1007/978-3-642-97881-4
8 sg:pub.10.1007/978-3-662-48433-3_8
9 schema:datePublished 2016-09-17
10 schema:datePublishedReg 2016-09-17
11 schema:description R. Lavi and C. Swamy (FOCS 2005, J. ACM 58(6), 25, 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees.
12 schema:genre article
13 schema:isAccessibleForFree true
14 schema:isPartOf N4a5e9816b81440a189fa546ef281ade6
15 N9b6d62b7cc1a44c8bae4afb43c2d2473
16 sg:journal.1052098
17 schema:keywords LAVI
18 Swamy
19 algorithm
20 algorithmic mechanism design
21 approximation
22 approximation algorithm
23 cost
24 design
25 direct implementation
26 ellipsoid method
27 expectation mechanisms
28 general method
29 guarantees
30 implementation
31 linear programming
32 mechanism
33 mechanism design
34 method
35 multiplicative weights
36 practice
37 programming
38 simplification
39 technique
40 truthfulness guarantee
41 use
42 weak approximation
43 weight
44 schema:name Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design
45 schema:pagination 641-663
46 schema:productId N7b8facc8407c449195e27801006ba989
47 Ned5a273bf7834abd84e432d9a04e8eb3
48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003152366
49 https://doi.org/10.1007/s00224-016-9704-2
50 schema:sdDatePublished 2022-10-01T06:42
51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
52 schema:sdPublisher Nab6e8ebf4454486c91141837e4341976
53 schema:url https://doi.org/10.1007/s00224-016-9704-2
54 sgo:license sg:explorer/license/
55 sgo:sdDataset articles
56 rdf:type schema:ScholarlyArticle
57 N33f8a949e41d410ca32ca598ca561143 rdf:first sg:person.011757371347.43
58 rdf:rest N453680b39e6244899243280dc121b3c6
59 N453680b39e6244899243280dc121b3c6 rdf:first sg:person.011016565440.58
60 rdf:rest rdf:nil
61 N4a5e9816b81440a189fa546ef281ade6 schema:issueNumber 4
62 rdf:type schema:PublicationIssue
63 N58fd60026b6841578b8ac004537e2d95 rdf:first sg:person.012561735335.16
64 rdf:rest N33f8a949e41d410ca32ca598ca561143
65 N7b8facc8407c449195e27801006ba989 schema:name doi
66 schema:value 10.1007/s00224-016-9704-2
67 rdf:type schema:PropertyValue
68 N9b6d62b7cc1a44c8bae4afb43c2d2473 schema:volumeNumber 59
69 rdf:type schema:PublicationVolume
70 Nab6e8ebf4454486c91141837e4341976 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 Ned5a273bf7834abd84e432d9a04e8eb3 schema:name dimensions_id
73 schema:value pub.1003152366
74 rdf:type schema:PropertyValue
75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
76 schema:name Information and Computing Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
79 schema:name Computation Theory and Mathematics
80 rdf:type schema:DefinedTerm
81 sg:journal.1052098 schema:issn 1432-4350
82 1433-0490
83 schema:name Theory of Computing Systems
84 schema:publisher Springer Nature
85 rdf:type schema:Periodical
86 sg:person.011016565440.58 schema:affiliation grid-institutes:grid.411750.6
87 schema:familyName Ramezani
88 schema:givenName Fahimeh
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011016565440.58
90 rdf:type schema:Person
91 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
92 schema:familyName Mehlhorn
93 schema:givenName Kurt
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
95 rdf:type schema:Person
96 sg:person.012561735335.16 schema:affiliation grid-institutes:grid.440568.b
97 schema:familyName Elbassioni
98 schema:givenName Khaled
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012561735335.16
100 rdf:type schema:Person
101 sg:pub.10.1007/3-540-69346-7_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003337212
102 https://doi.org/10.1007/3-540-69346-7_12
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/978-3-319-13129-0_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039301089
105 https://doi.org/10.1007/978-3-319-13129-0_9
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/978-3-642-17572-5_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024906405
108 https://doi.org/10.1007/978-3-642-17572-5_14
109 rdf:type schema:CreativeWork
110 sg:pub.10.1007/978-3-642-97881-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051732087
111 https://doi.org/10.1007/978-3-642-97881-4
112 rdf:type schema:CreativeWork
113 sg:pub.10.1007/978-3-662-48433-3_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021943040
114 https://doi.org/10.1007/978-3-662-48433-3_8
115 rdf:type schema:CreativeWork
116 grid-institutes:grid.411750.6 schema:alternateName Department of Mathematics, University of Isfahan, 81746-73441, Isfahan, Iran
117 schema:name Department of Mathematics, University of Isfahan, 81746-73441, Isfahan, Iran
118 rdf:type schema:Organization
119 grid-institutes:grid.419528.3 schema:alternateName Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbrucken, Germany
120 schema:name Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbrucken, Germany
121 rdf:type schema:Organization
122 grid-institutes:grid.440568.b schema:alternateName Masdar Institute of Science and Technology, Abu Dhabi, United Arab Emirates
123 schema:name Masdar Institute of Science and Technology, Abu Dhabi, United Arab Emirates
124 rdf:type schema:Organization
 




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


...