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-10-01T06:52", 
    "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_106.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 N62029edd962d4e88ad63bc909a88ee7c
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 N8a82992922924a15bbc6c79114e30131
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nb954eac667fd447f93a46c5fa403fbe9
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 N221cea66948443eabb1a9ce3c39abb63
70 N9f7124ffbaf94ddeb94e822ae888765e
71 schema:publisher N0122ea31275a4d24b4c7fe14cabe730e
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-10-01T06:52
75 schema:sdLicense https://scigraph.springernature.com/explorer/license/
76 schema:sdPublisher Ncbf769d29e00483b884d9f6da0107e8d
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 N0122ea31275a4d24b4c7fe14cabe730e schema:name Springer Nature
82 rdf:type schema:Organisation
83 N221cea66948443eabb1a9ce3c39abb63 schema:name doi
84 schema:value 10.1007/978-3-319-66700-3_6
85 rdf:type schema:PropertyValue
86 N29c74e88ac174dbdbc50bf6303b09f02 rdf:first sg:person.012247175647.87
87 rdf:rest N92a77bfbb57f4d5ca2dfbaa5887496c2
88 N62029edd962d4e88ad63bc909a88ee7c rdf:first sg:person.015064365275.26
89 rdf:rest N29c74e88ac174dbdbc50bf6303b09f02
90 N7ac67955bd2648deaabc9214ebf1ead1 schema:familyName Bilò
91 schema:givenName Vittorio
92 rdf:type schema:Person
93 N7b14907cd6124df28f730b1f8326cb48 rdf:first sg:person.011757371347.43
94 rdf:rest rdf:nil
95 N8a82992922924a15bbc6c79114e30131 rdf:first N7ac67955bd2648deaabc9214ebf1ead1
96 rdf:rest Nbbf1d3da30e747bf983b72e88e4d0a17
97 N92a77bfbb57f4d5ca2dfbaa5887496c2 rdf:first sg:person.015374712313.48
98 rdf:rest N7b14907cd6124df28f730b1f8326cb48
99 N9f7124ffbaf94ddeb94e822ae888765e schema:name dimensions_id
100 schema:value pub.1091272448
101 rdf:type schema:PropertyValue
102 Nb954eac667fd447f93a46c5fa403fbe9 schema:isbn 978-3-319-66699-0
103 978-3-319-66700-3
104 schema:name Algorithmic Game Theory
105 rdf:type schema:Book
106 Nbbf1d3da30e747bf983b72e88e4d0a17 rdf:first Ne71d04d070504944a12556a4f9c96be1
107 rdf:rest rdf:nil
108 Ncbf769d29e00483b884d9f6da0107e8d schema:name Springer Nature - SN SciGraph project
109 rdf:type schema:Organization
110 Ne71d04d070504944a12556a4f9c96be1 schema:familyName Flammini
111 schema:givenName Michele
112 rdf:type schema:Person
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)


...