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-12-01T06:50", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_285.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 Ncc49a529a1504e0bbc847a99baeac143
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 N36b2624d6ad848579c8c72cfcf8c527e
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N36b9e7e94cb44b51808da70703507d92
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 N685156a4e3584798a294f5502348a7eb
56 N7541708df9ba44c2a6cf9293b51bc434
57 schema:publisher Ne5af2037795e4225b9c12f1acf4ebf11
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-12-01T06:50
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N8fed3f3786b54999ac0b721735710f9c
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 N316ea8e6de0b4d80a60c65eb081c3cbf schema:familyName Freivalds
68 schema:givenName Rūsiņš
69 rdf:type schema:Person
70 N36b2624d6ad848579c8c72cfcf8c527e rdf:first N7af0c18b53a0473c9b1426fccc75ea9e
71 rdf:rest N63e4425e3f014b4ba8d1c33337e292fc
72 N36b9e7e94cb44b51808da70703507d92 schema:isbn 978-3-642-39205-4
73 978-3-642-39206-1
74 schema:name Automata, Languages, and Programming
75 rdf:type schema:Book
76 N37411430a2834b70b847d9d613543573 rdf:first sg:person.011757371347.43
77 rdf:rest rdf:nil
78 N524df86eee65495291ec4b0ee7652981 schema:familyName Peleg
79 schema:givenName David
80 rdf:type schema:Person
81 N63e4425e3f014b4ba8d1c33337e292fc rdf:first N316ea8e6de0b4d80a60c65eb081c3cbf
82 rdf:rest N75583fac5deb4a0abffd860fc9a91609
83 N685156a4e3584798a294f5502348a7eb schema:name doi
84 schema:value 10.1007/978-3-642-39206-1_36
85 rdf:type schema:PropertyValue
86 N7541708df9ba44c2a6cf9293b51bc434 schema:name dimensions_id
87 schema:value pub.1034211474
88 rdf:type schema:PropertyValue
89 N75583fac5deb4a0abffd860fc9a91609 rdf:first Ne8d13f275b4345a3896423ba633124f2
90 rdf:rest N87ac6fc5c7ee4977bb4c33f65ac3aba8
91 N7af0c18b53a0473c9b1426fccc75ea9e schema:familyName Fomin
92 schema:givenName Fedor V.
93 rdf:type schema:Person
94 N87ac6fc5c7ee4977bb4c33f65ac3aba8 rdf:first N524df86eee65495291ec4b0ee7652981
95 rdf:rest rdf:nil
96 N8fed3f3786b54999ac0b721735710f9c schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
98 Ncc49a529a1504e0bbc847a99baeac143 rdf:first sg:person.015064317327.50
99 rdf:rest N37411430a2834b70b847d9d613543573
100 Ne5af2037795e4225b9c12f1acf4ebf11 schema:name Springer Nature
101 rdf:type schema:Organisation
102 Ne8d13f275b4345a3896423ba633124f2 schema:familyName Kwiatkowska
103 schema:givenName Marta
104 rdf:type schema:Person
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)


...