Earning Limits in Fisher Markets with Spending-Constraint Utilities View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2017-08-19

AUTHORS

Xiaohui Bei , Jugal Garg , Martin Hoefer , Kurt Mehlhorn

ABSTRACT

Earning limits are an interesting novel aspect in the classic Fisher market model. Here sellers have bounds on their income and can decide to lower the supply they bring to the market if income exceeds the limit. Beyond several applications, in which earning limits are natural, equilibria of such markets are a central concept in the allocation of indivisible items to maximize Nash social welfare.In this paper, we analyze earning limits in Fisher markets with linear and spending-constraint utilities. We show a variety of structural and computational results about market equilibria. The equilibrium price vectors form a lattice, and the spending of buyers is unique in non-degenerate markets. We provide a scaling-based algorithm that computes an equilibrium in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^3\ell \log (\ell + nU))$$\end{document}, where n is the number of agents, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell \ge n$$\end{document} a bound on the segments in the utility functions, and U the largest integer in the market representation. Moreover, we show how to refine any equilibrium in polynomial time to one with minimal prices, or one with maximal prices (if it exists). Finally, we discuss how our algorithm can be used to obtain in polynomial time a 2-approximation for Nash social welfare in multi-unit markets with indivisible items that come in multiple copies. More... »

PAGES

67-79

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-66700-3_6

DOI

http://dx.doi.org/10.1007/978-3-319-66700-3_6

DIMENSIONS

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


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/14", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Economics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1402", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Economics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Nanyang Technological University, Singapore, Singapore", 
          "id": "http://www.grid.ac/institutes/grid.59025.3b", 
          "name": [
            "Nanyang Technological University, Singapore, Singapore"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bei", 
        "givenName": "Xiaohui", 
        "id": "sg:person.015064365275.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015064365275.26"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Illinois at Urbana-Champaign, Champaign, USA", 
          "id": "http://www.grid.ac/institutes/grid.35403.31", 
          "name": [
            "University of Illinois at Urbana-Champaign, Champaign, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Garg", 
        "givenName": "Jugal", 
        "id": "sg:person.012247175647.87", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012247175647.87"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Goethe University Frankfurt, Frankfurt, Germany", 
          "id": "http://www.grid.ac/institutes/grid.7839.5", 
          "name": [
            "Goethe University Frankfurt, Frankfurt, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hoefer", 
        "givenName": "Martin", 
        "id": "sg:person.015374712313.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015374712313.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MPI Informatik, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "MPI 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": "2017-08-19", 
    "datePublishedReg": "2017-08-19", 
    "description": "Earning limits are an interesting novel aspect in the classic Fisher market model. Here sellers have bounds on their income and can decide to lower the supply they bring to the market if income exceeds the limit. Beyond several applications, in which earning limits are natural, equilibria of such markets are a central concept in the allocation of indivisible items to maximize Nash social welfare.In this paper, we analyze earning limits in Fisher markets with linear and spending-constraint utilities. We show a variety of structural and computational results about market equilibria. The equilibrium price vectors form a lattice, and the spending of buyers is unique in non-degenerate markets. We provide a scaling-based algorithm that computes an equilibrium in time \\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(n^3\\ell \\log (\\ell + nU))$$\\end{document}, where n is the number of agents, \\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}$$\\ell \\ge n$$\\end{document} a bound on the segments in the utility functions, and U the largest integer in the market representation. Moreover, we show how to refine any equilibrium in polynomial time to one with minimal prices, or one with maximal prices (if it exists). Finally, we discuss how our algorithm can be used to obtain in polynomial time a 2-approximation for Nash social welfare in multi-unit markets with indivisible items that come in multiple copies.", 
    "editor": [
      {
        "familyName": "Bil\u00f2", 
        "givenName": "Vittorio", 
        "type": "Person"
      }, 
      {
        "familyName": "Flammini", 
        "givenName": "Michele", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-66700-3_6", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-66699-0", 
        "978-3-319-66700-3"
      ], 
      "name": "Algorithmic Game Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "Nash social welfare", 
      "Fisher markets", 
      "social welfare", 
      "indivisible items", 
      "multi-unit markets", 
      "equilibrium price vector", 
      "Fisher market model", 
      "market equilibrium", 
      "price vector", 
      "maximal price", 
      "market model", 
      "such markets", 
      "interesting novel aspect", 
      "market representation", 
      "minimal price", 
      "utility function", 
      "market", 
      "prices", 
      "income", 
      "welfare", 
      "number of agents", 
      "equilibrium", 
      "spending", 
      "sellers", 
      "buyers", 
      "allocation", 
      "supply", 
      "utility", 
      "central concept", 
      "model", 
      "items", 
      "novel aspects", 
      "polynomial time", 
      "aspects", 
      "time", 
      "concept", 
      "results", 
      "bounds", 
      "segments", 
      "linear", 
      "computational results", 
      "agents", 
      "number", 
      "limit", 
      "variety", 
      "function", 
      "representation", 
      "applications", 
      "algorithm", 
      "vector", 
      "large integers", 
      "integers", 
      "copies", 
      "multiple copies", 
      "paper", 
      "lattice"
    ], 
    "name": "Earning Limits in Fisher Markets with Spending-Constraint Utilities", 
    "pagination": "67-79", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1091272448"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-66700-3_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-66700-3_6", 
      "https://app.dimensions.ai/details/publication/pub.1091272448"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:53", 
    "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_426.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-66700-3_6"
  }
]
 

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-319-66700-3_6'

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-319-66700-3_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-66700-3_6'

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-319-66700-3_6'


 

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

150 TRIPLES      22 PREDICATES      80 URIs      73 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-66700-3_6 schema:about anzsrc-for:14
2 anzsrc-for:1402
3 schema:author N4d067d14c34a44328c8fe847cc06598c
4 schema:datePublished 2017-08-19
5 schema:datePublishedReg 2017-08-19
6 schema:description Earning limits are an interesting novel aspect in the classic Fisher market model. Here sellers have bounds on their income and can decide to lower the supply they bring to the market if income exceeds the limit. Beyond several applications, in which earning limits are natural, equilibria of such markets are a central concept in the allocation of indivisible items to maximize Nash social welfare.In this paper, we analyze earning limits in Fisher markets with linear and spending-constraint utilities. We show a variety of structural and computational results about market equilibria. The equilibrium price vectors form a lattice, and the spending of buyers is unique in non-degenerate markets. We provide a scaling-based algorithm that computes an equilibrium in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^3\ell \log (\ell + nU))$$\end{document}, where n is the number of agents, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell \ge n$$\end{document} a bound on the segments in the utility functions, and U the largest integer in the market representation. Moreover, we show how to refine any equilibrium in polynomial time to one with minimal prices, or one with maximal prices (if it exists). Finally, we discuss how our algorithm can be used to obtain in polynomial time a 2-approximation for Nash social welfare in multi-unit markets with indivisible items that come in multiple copies.
7 schema:editor Ne989aaf4fae5448f96fb59d37c0573a1
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nc3c6947997c64d4f9d1752c14ba9cdaf
11 schema:keywords Fisher market model
12 Fisher markets
13 Nash social welfare
14 agents
15 algorithm
16 allocation
17 applications
18 aspects
19 bounds
20 buyers
21 central concept
22 computational results
23 concept
24 copies
25 equilibrium
26 equilibrium price vector
27 function
28 income
29 indivisible items
30 integers
31 interesting novel aspect
32 items
33 large integers
34 lattice
35 limit
36 linear
37 market
38 market equilibrium
39 market model
40 market representation
41 maximal price
42 minimal price
43 model
44 multi-unit markets
45 multiple copies
46 novel aspects
47 number
48 number of agents
49 paper
50 polynomial time
51 price vector
52 prices
53 representation
54 results
55 segments
56 sellers
57 social welfare
58 spending
59 such markets
60 supply
61 time
62 utility
63 utility function
64 variety
65 vector
66 welfare
67 schema:name Earning Limits in Fisher Markets with Spending-Constraint Utilities
68 schema:pagination 67-79
69 schema:productId N275ad01198ae4d2ebb7cb845ce243cd9
70 N792c14a864cd4ceeb7b9e4345110a576
71 schema:publisher N44b5353b5ac44618aafcc8a5d6e1ff1c
72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091272448
73 https://doi.org/10.1007/978-3-319-66700-3_6
74 schema:sdDatePublished 2022-12-01T06:53
75 schema:sdLicense https://scigraph.springernature.com/explorer/license/
76 schema:sdPublisher N9f364aed6b934344a7a53d4d026d0d6c
77 schema:url https://doi.org/10.1007/978-3-319-66700-3_6
78 sgo:license sg:explorer/license/
79 sgo:sdDataset chapters
80 rdf:type schema:Chapter
81 N028bffa134c6487d980676dca6fcc13e rdf:first sg:person.015374712313.48
82 rdf:rest N1d76b4d57142468e97ea725506d3d57f
83 N113b415eadee4e2f8a22ee4bec91348c rdf:first sg:person.012247175647.87
84 rdf:rest N028bffa134c6487d980676dca6fcc13e
85 N1d76b4d57142468e97ea725506d3d57f rdf:first sg:person.011757371347.43
86 rdf:rest rdf:nil
87 N2329b684d01f40a88fdd44fa9d74a0f3 rdf:first Na9a477f1b068490e920ff879dc07b352
88 rdf:rest rdf:nil
89 N275ad01198ae4d2ebb7cb845ce243cd9 schema:name dimensions_id
90 schema:value pub.1091272448
91 rdf:type schema:PropertyValue
92 N44b5353b5ac44618aafcc8a5d6e1ff1c schema:name Springer Nature
93 rdf:type schema:Organisation
94 N4d067d14c34a44328c8fe847cc06598c rdf:first sg:person.015064365275.26
95 rdf:rest N113b415eadee4e2f8a22ee4bec91348c
96 N792c14a864cd4ceeb7b9e4345110a576 schema:name doi
97 schema:value 10.1007/978-3-319-66700-3_6
98 rdf:type schema:PropertyValue
99 N9f364aed6b934344a7a53d4d026d0d6c schema:name Springer Nature - SN SciGraph project
100 rdf:type schema:Organization
101 Na9a477f1b068490e920ff879dc07b352 schema:familyName Flammini
102 schema:givenName Michele
103 rdf:type schema:Person
104 Nc3c6947997c64d4f9d1752c14ba9cdaf schema:isbn 978-3-319-66699-0
105 978-3-319-66700-3
106 schema:name Algorithmic Game Theory
107 rdf:type schema:Book
108 Nc9fb2faaafd14e538ade8e52e1721877 schema:familyName Bilò
109 schema:givenName Vittorio
110 rdf:type schema:Person
111 Ne989aaf4fae5448f96fb59d37c0573a1 rdf:first Nc9fb2faaafd14e538ade8e52e1721877
112 rdf:rest N2329b684d01f40a88fdd44fa9d74a0f3
113 anzsrc-for:14 schema:inDefinedTermSet anzsrc-for:
114 schema:name Economics
115 rdf:type schema:DefinedTerm
116 anzsrc-for:1402 schema:inDefinedTermSet anzsrc-for:
117 schema:name Applied Economics
118 rdf:type schema:DefinedTerm
119 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
120 schema:familyName Mehlhorn
121 schema:givenName Kurt
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
123 rdf:type schema:Person
124 sg:person.012247175647.87 schema:affiliation grid-institutes:grid.35403.31
125 schema:familyName Garg
126 schema:givenName Jugal
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012247175647.87
128 rdf:type schema:Person
129 sg:person.015064365275.26 schema:affiliation grid-institutes:grid.59025.3b
130 schema:familyName Bei
131 schema:givenName Xiaohui
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015064365275.26
133 rdf:type schema:Person
134 sg:person.015374712313.48 schema:affiliation grid-institutes:grid.7839.5
135 schema:familyName Hoefer
136 schema:givenName Martin
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015374712313.48
138 rdf:type schema:Person
139 grid-institutes:grid.35403.31 schema:alternateName University of Illinois at Urbana-Champaign, Champaign, USA
140 schema:name University of Illinois at Urbana-Champaign, Champaign, USA
141 rdf:type schema:Organization
142 grid-institutes:grid.419528.3 schema:alternateName MPI Informatik, Saarbrücken, Germany
143 schema:name MPI Informatik, Saarbrücken, Germany
144 rdf:type schema:Organization
145 grid-institutes:grid.59025.3b schema:alternateName Nanyang Technological University, Singapore, Singapore
146 schema:name Nanyang Technological University, Singapore, Singapore
147 rdf:type schema:Organization
148 grid-institutes:grid.7839.5 schema:alternateName Goethe University Frankfurt, Frankfurt, Germany
149 schema:name Goethe University Frankfurt, Frankfurt, Germany
150 rdf:type schema:Organization
 




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


...