A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Ran Duan , Kurt Mehlhorn

ABSTRACT

We present the first combinatorial polynomial time algorithm for computing the equilibrium of the Arrow-Debreu market model with linear utilities. Our algorithm views the allocation of money as flows and iteratively improves the balanced flow as in [Devanur et al. 2008] for Fisher’s model. We develop new methods to carefully deal with the flows and surpluses during price adjustments. In our algorithm, we need O(n6log(nU)) maximum flow computations, where n is the number of persons and U is the maximum integer utility, and the length of the numbers is at most O(nlog(nU)) to guarantee an exact solution. The previous polynomial time algorithms [Nenakov and Primak 1983, Jain 2007, Ye 2007] for this problem are based on solving convex programs using the ellipsoid algorithm or interior-point method. More... »

PAGES

425-436

Book

TITLE

Automata, Languages, and Programming

ISBN

978-3-642-39205-4
978-3-642-39206-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-39206-1_36

DOI

http://dx.doi.org/10.1007/978-3-642-39206-1_36

DIMENSIONS

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


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": "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Duan", 
        "givenName": "Ran", 
        "id": "sg:person.015064317327.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015064317327.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, 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"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We present the first combinatorial polynomial time algorithm for computing the equilibrium of the Arrow-Debreu market model with linear utilities. Our algorithm views the allocation of money as flows and iteratively improves the balanced flow as in [Devanur et al. 2008] for Fisher\u2019s model. We develop new methods to carefully deal with the flows and surpluses during price adjustments. In our algorithm, we need O(n6log(nU)) maximum flow computations, where n is the number of persons and U is the maximum integer utility, and the length of the numbers is at most O(nlog(nU)) to guarantee an exact solution. The previous polynomial time algorithms [Nenakov and Primak 1983, Jain 2007, Ye 2007] for this problem are based on solving convex programs using the ellipsoid algorithm or interior-point method.", 
    "editor": [
      {
        "familyName": "Fomin", 
        "givenName": "Fedor V.", 
        "type": "Person"
      }, 
      {
        "familyName": "Freivalds", 
        "givenName": "R\u016bsi\u0146\u0161", 
        "type": "Person"
      }, 
      {
        "familyName": "Kwiatkowska", 
        "givenName": "Marta", 
        "type": "Person"
      }, 
      {
        "familyName": "Peleg", 
        "givenName": "David", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-39206-1_36", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-39205-4", 
        "978-3-642-39206-1"
      ], 
      "name": "Automata, Languages, and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "linear Arrow\u2013Debreu market", 
      "polynomial time algorithm", 
      "Arrow-Debreu market model", 
      "first combinatorial polynomial-time algorithm", 
      "interior point method", 
      "combinatorial polynomial-time algorithm", 
      "Arrow-Debreu markets", 
      "time algorithm", 
      "maximum flow computations", 
      "combinatorial polynomial algorithm", 
      "previous polynomial-time algorithms", 
      "convex program", 
      "exact solution", 
      "ellipsoid algorithm", 
      "flow computations", 
      "balanced flow", 
      "polynomial algorithm", 
      "linear utility", 
      "Fisher model", 
      "market model", 
      "algorithm", 
      "new method", 
      "model", 
      "computation", 
      "flow", 
      "problem", 
      "solution", 
      "equilibrium", 
      "number", 
      "allocation", 
      "allocation of money", 
      "price adjustment", 
      "length", 
      "utility", 
      "market", 
      "adjustment", 
      "program", 
      "surplus", 
      "number of persons", 
      "money", 
      "persons", 
      "method"
    ], 
    "name": "A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market", 
    "pagination": "425-436", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1034211474"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-39206-1_36"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-39206-1_36", 
      "https://app.dimensions.ai/details/publication/pub.1034211474"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:18", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_447.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-39206-1_36"
  }
]
 

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-642-39206-1_36'

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-642-39206-1_36'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-39206-1_36'

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-642-39206-1_36'


 

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

123 TRIPLES      22 PREDICATES      67 URIs      60 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-39206-1_36 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N47cbfec2ec9b43b1b2695540bdd182d5
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description We present the first combinatorial polynomial time algorithm for computing the equilibrium of the Arrow-Debreu market model with linear utilities. Our algorithm views the allocation of money as flows and iteratively improves the balanced flow as in [Devanur et al. 2008] for Fisher’s model. We develop new methods to carefully deal with the flows and surpluses during price adjustments. In our algorithm, we need O(n6log(nU)) maximum flow computations, where n is the number of persons and U is the maximum integer utility, and the length of the numbers is at most O(nlog(nU)) to guarantee an exact solution. The previous polynomial time algorithms [Nenakov and Primak 1983, Jain 2007, Ye 2007] for this problem are based on solving convex programs using the ellipsoid algorithm or interior-point method.
7 schema:editor N85b3684d7e5d401d9a88c8bab099bbd5
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N57703dda0dd24ce69b498a95c4dedd5a
11 schema:keywords Arrow-Debreu market model
12 Arrow-Debreu markets
13 Fisher model
14 adjustment
15 algorithm
16 allocation
17 allocation of money
18 balanced flow
19 combinatorial polynomial algorithm
20 combinatorial polynomial-time algorithm
21 computation
22 convex program
23 ellipsoid algorithm
24 equilibrium
25 exact solution
26 first combinatorial polynomial-time algorithm
27 flow
28 flow computations
29 interior point method
30 length
31 linear Arrow–Debreu market
32 linear utility
33 market
34 market model
35 maximum flow computations
36 method
37 model
38 money
39 new method
40 number
41 number of persons
42 persons
43 polynomial algorithm
44 polynomial time algorithm
45 previous polynomial-time algorithms
46 price adjustment
47 problem
48 program
49 solution
50 surplus
51 time algorithm
52 utility
53 schema:name A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
54 schema:pagination 425-436
55 schema:productId N21c67b6286e344ef8cac58d59ce8dcb5
56 N43e0ede440e8456e825dfb5700dc2262
57 schema:publisher N50e51e4dd2b64039b0b7524e765746f3
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034211474
59 https://doi.org/10.1007/978-3-642-39206-1_36
60 schema:sdDatePublished 2022-09-02T16:18
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N0d229de88d1e476c9cdf2a88a83759cd
63 schema:url https://doi.org/10.1007/978-3-642-39206-1_36
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N0d229de88d1e476c9cdf2a88a83759cd schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 N21c67b6286e344ef8cac58d59ce8dcb5 schema:name doi
70 schema:value 10.1007/978-3-642-39206-1_36
71 rdf:type schema:PropertyValue
72 N3343fad69d36466aaafbd99dec1cb37d schema:familyName Kwiatkowska
73 schema:givenName Marta
74 rdf:type schema:Person
75 N3be2f719428d4fcfb096f4668937f0fb rdf:first N6a264f9befd44990ac9ba8fd09ff069f
76 rdf:rest Nda9cfb8d0a9a4472bc3493520407f14e
77 N43e0ede440e8456e825dfb5700dc2262 schema:name dimensions_id
78 schema:value pub.1034211474
79 rdf:type schema:PropertyValue
80 N47cbfec2ec9b43b1b2695540bdd182d5 rdf:first sg:person.015064317327.50
81 rdf:rest Ned3890b495b74559ae34e46e0e191cdf
82 N50e51e4dd2b64039b0b7524e765746f3 schema:name Springer Nature
83 rdf:type schema:Organisation
84 N57703dda0dd24ce69b498a95c4dedd5a schema:isbn 978-3-642-39205-4
85 978-3-642-39206-1
86 schema:name Automata, Languages, and Programming
87 rdf:type schema:Book
88 N6a264f9befd44990ac9ba8fd09ff069f schema:familyName Freivalds
89 schema:givenName Rūsiņš
90 rdf:type schema:Person
91 N7bec17c3b1c14ed3a1d408b6b09997b3 rdf:first Na054972aa63b4ae0ab8f777c3149c6a2
92 rdf:rest rdf:nil
93 N85b3684d7e5d401d9a88c8bab099bbd5 rdf:first Nbdd0c42fe4a447acbe7c155ccf531099
94 rdf:rest N3be2f719428d4fcfb096f4668937f0fb
95 Na054972aa63b4ae0ab8f777c3149c6a2 schema:familyName Peleg
96 schema:givenName David
97 rdf:type schema:Person
98 Nbdd0c42fe4a447acbe7c155ccf531099 schema:familyName Fomin
99 schema:givenName Fedor V.
100 rdf:type schema:Person
101 Nda9cfb8d0a9a4472bc3493520407f14e rdf:first N3343fad69d36466aaafbd99dec1cb37d
102 rdf:rest N7bec17c3b1c14ed3a1d408b6b09997b3
103 Ned3890b495b74559ae34e46e0e191cdf rdf:first sg:person.011757371347.43
104 rdf:rest rdf:nil
105 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
106 schema:name Information and Computing Sciences
107 rdf:type schema:DefinedTerm
108 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
109 schema:name Computation Theory and Mathematics
110 rdf:type schema:DefinedTerm
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.015064317327.50 schema:affiliation grid-institutes:grid.419528.3
117 schema:familyName Duan
118 schema:givenName Ran
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015064317327.50
120 rdf:type schema:Person
121 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Saarbrücken, Germany
122 schema:name Max-Planck-Institut für Informatik, Saarbrücken, Germany
123 rdf:type schema:Organization
 




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


...