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


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015-12-10

AUTHORS

Khaled Elbassioni , Kurt Mehlhorn , Fahimeh Ramezani

ABSTRACT

R. Lavy and C. Swamy (FOCS 2005, J. ACM 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

98-109

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-48433-3_8

DOI

http://dx.doi.org/10.1007/978-3-662-48433-3_8

DIMENSIONS

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


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": "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": "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": "Ramezani", 
        "givenName": "Fahimeh", 
        "id": "sg:person.011016565440.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011016565440.58"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-12-10", 
    "datePublishedReg": "2015-12-10", 
    "description": "R.\u00a0Lavy and C.\u00a0Swamy (FOCS 2005, J.\u00a0ACM 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.", 
    "editor": [
      {
        "familyName": "Hoefer", 
        "givenName": "Martin", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-48433-3_8", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-48432-6", 
        "978-3-662-48433-3"
      ], 
      "name": "Algorithmic Game Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "linear programming", 
      "algorithmic mechanism design", 
      "approximation algorithm", 
      "truthfulness guarantee", 
      "direct implementation", 
      "multiplicative weights", 
      "mechanism design", 
      "programming", 
      "algorithm", 
      "guarantees", 
      "ellipsoid method", 
      "implementation", 
      "general method", 
      "method", 
      "expectation mechanisms", 
      "cost", 
      "simplification", 
      "technique", 
      "design", 
      "use", 
      "approximation", 
      "practice", 
      "mechanism", 
      "weight", 
      "weak approximation", 
      "Swamy", 
      "Lavy"
    ], 
    "name": "Towards More Practical Linear Programming-Based Techniques for Algorithmic Mechanism Design", 
    "pagination": "98-109", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021943040"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-48433-3_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-48433-3_8", 
      "https://app.dimensions.ai/details/publication/pub.1021943040"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:59", 
    "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/chapter/chapter_424.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-48433-3_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/978-3-662-48433-3_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/978-3-662-48433-3_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48433-3_8'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48433-3_8'


 

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

103 TRIPLES      22 PREDICATES      51 URIs      44 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-48433-3_8 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N87a75d56aede4b959468d80be2f1a535
4 schema:datePublished 2015-12-10
5 schema:datePublishedReg 2015-12-10
6 schema:description R. Lavy and C. Swamy (FOCS 2005, J. ACM 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.
7 schema:editor Ne758738700e341fd86cd18bf5a7da227
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N1370cce86a2f419997cd8f3f368eb14e
11 schema:keywords Lavy
12 Swamy
13 algorithm
14 algorithmic mechanism design
15 approximation
16 approximation algorithm
17 cost
18 design
19 direct implementation
20 ellipsoid method
21 expectation mechanisms
22 general method
23 guarantees
24 implementation
25 linear programming
26 mechanism
27 mechanism design
28 method
29 multiplicative weights
30 practice
31 programming
32 simplification
33 technique
34 truthfulness guarantee
35 use
36 weak approximation
37 weight
38 schema:name Towards More Practical Linear Programming-Based Techniques for Algorithmic Mechanism Design
39 schema:pagination 98-109
40 schema:productId N5d4282f2731b40f99a79cb9d5c4e4f3a
41 Nf9276805302a40d48d717574283e4345
42 schema:publisher N87a099cd7f0e4e6b8ff62a7258caa070
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021943040
44 https://doi.org/10.1007/978-3-662-48433-3_8
45 schema:sdDatePublished 2022-10-01T06:59
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N3c35a6381d56454bbb3118db88204f91
48 schema:url https://doi.org/10.1007/978-3-662-48433-3_8
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N07df42535d4646a68ebe884aba94741b rdf:first sg:person.011016565440.58
53 rdf:rest rdf:nil
54 N1370cce86a2f419997cd8f3f368eb14e schema:isbn 978-3-662-48432-6
55 978-3-662-48433-3
56 schema:name Algorithmic Game Theory
57 rdf:type schema:Book
58 N3c35a6381d56454bbb3118db88204f91 schema:name Springer Nature - SN SciGraph project
59 rdf:type schema:Organization
60 N5d4282f2731b40f99a79cb9d5c4e4f3a schema:name dimensions_id
61 schema:value pub.1021943040
62 rdf:type schema:PropertyValue
63 N87a099cd7f0e4e6b8ff62a7258caa070 schema:name Springer Nature
64 rdf:type schema:Organisation
65 N87a75d56aede4b959468d80be2f1a535 rdf:first sg:person.012561735335.16
66 rdf:rest N8977833e511e488e8f8082f8284e4685
67 N8977833e511e488e8f8082f8284e4685 rdf:first sg:person.011757371347.43
68 rdf:rest N07df42535d4646a68ebe884aba94741b
69 N92b221851fcb44a78e355f7a3f9d0190 schema:familyName Hoefer
70 schema:givenName Martin
71 rdf:type schema:Person
72 Ne758738700e341fd86cd18bf5a7da227 rdf:first N92b221851fcb44a78e355f7a3f9d0190
73 rdf:rest rdf:nil
74 Nf9276805302a40d48d717574283e4345 schema:name doi
75 schema:value 10.1007/978-3-662-48433-3_8
76 rdf:type schema:PropertyValue
77 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
78 schema:name Information and Computing Sciences
79 rdf:type schema:DefinedTerm
80 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
81 schema:name Computation Theory and Mathematics
82 rdf:type schema:DefinedTerm
83 sg:person.011016565440.58 schema:affiliation grid-institutes:grid.419528.3
84 schema:familyName Ramezani
85 schema:givenName Fahimeh
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011016565440.58
87 rdf:type schema:Person
88 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
89 schema:familyName Mehlhorn
90 schema:givenName Kurt
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
92 rdf:type schema:Person
93 sg:person.012561735335.16 schema:affiliation grid-institutes:grid.440568.b
94 schema:familyName Elbassioni
95 schema:givenName Khaled
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012561735335.16
97 rdf:type schema:Person
98 grid-institutes:grid.419528.3 schema:alternateName Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbrucken, Germany
99 schema:name Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbrucken, Germany
100 rdf:type schema:Organization
101 grid-institutes:grid.440568.b schema:alternateName Masdar Institute of Science and Technology, Abu Dhabi, UAE
102 schema:name Masdar Institute of Science and Technology, Abu Dhabi, UAE
103 rdf:type schema:Organization
 




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


...