Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices

We show the strong substitutes product-mix auction bidding language provides an intuitive and geometric interpretation of strong substitutes as Minkowski differences between sets that are easy to identify. We prove that competitive equilibrium prices for agents with strong substitutes preferences ca...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2024-01, Vol.203 (1-2), p.611-643
Main Authors: Baldwin, Elizabeth, Bichler, Martin, Fichtl, Maximilian, Klemperer, Paul
Format: Article
Language:English
Subjects:
Algorithms
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Competition (Economics)
Computer science
Full Length Paper
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Substitutes
Theoretical
Valuation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c468t-a8e0b0d5889689e8ad7864a3c2580794287fce2270981260559da426727e2f9d3
cites cdi_FETCH-LOGICAL-c468t-a8e0b0d5889689e8ad7864a3c2580794287fce2270981260559da426727e2f9d3
container_end_page 643
container_issue 1-2
container_start_page 611
container_title Mathematical programming
container_volume 203
creator Baldwin, Elizabeth
Bichler, Martin
Fichtl, Maximilian
Klemperer, Paul
description We show the strong substitutes product-mix auction bidding language provides an intuitive and geometric interpretation of strong substitutes as Minkowski differences between sets that are easy to identify. We prove that competitive equilibrium prices for agents with strong substitutes preferences can be computed by minimizing the difference between two linear programs for the positive and the negative bids with suitably relaxed resource constraints. This also leads to a new algorithm for computing competitive equilibrium prices which is competitive with standard steepest descent algorithms in extensive experiments.
doi_str_mv 10.1007/s10107-022-01792-w
format article
fullrecord <record><control><sourceid>gale_proqu</sourceid><recordid>TN_cdi_proquest_journals_2924290604</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><galeid>A781950761</galeid><sourcerecordid>A781950761</sourcerecordid><originalsourceid>FETCH-LOGICAL-c468t-a8e0b0d5889689e8ad7864a3c2580794287fce2270981260559da426727e2f9d3</originalsourceid><addsrcrecordid>eNp9kEtr3TAQhUVJoDdJ_0BXgm7jdCTLenQXQh6FQBZJ10JXHt8q2NaNJOeSf1-lDnRXZjEwnG_mzCHkK4MLBqC-ZwYMVAOcN8CU4c3hE9kw0cpGSCGPyAaAd00nGXwmJzk_AwBrtd4Q91hSnHc0L9tcQlkK5h80l7T4siQ30n2Ke0wlYD6nbu6pozMeqBt3MYXye6JDTNTHaY8VDq9I8WUJY9imsEyVDR7zGTke3Jjxy0c_Jb9urp-u7pr7h9ufV5f3jRdSl8ZphC30ndZGaoPa9UpL4VrPOw3KCK7V4JFzBUYzLqHrTO8El4or5IPp21Pybd1bLb8smIt9jkua60nLDRfcgARRVReraudGtGEeYknO1-pxCj7OOIQ6v1SamQ6UZBXgK-BTzDnhYOtbk0tvloF9z96u2duavf2bvT1UqF2hXMXzDtM_L_-h_gBXkIfS</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2924290604</pqid></control><display><type>article</type><title>Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices</title><source>EBSCOhost Business Source Ultimate</source><source>Springer Link</source><creator>Baldwin, Elizabeth ; Bichler, Martin ; Fichtl, Maximilian ; Klemperer, Paul</creator><creatorcontrib>Baldwin, Elizabeth ; Bichler, Martin ; Fichtl, Maximilian ; Klemperer, Paul</creatorcontrib><description>We show the strong substitutes product-mix auction bidding language provides an intuitive and geometric interpretation of strong substitutes as Minkowski differences between sets that are easy to identify. We prove that competitive equilibrium prices for agents with strong substitutes preferences can be computed by minimizing the difference between two linear programs for the positive and the negative bids with suitably relaxed resource constraints. This also leads to a new algorithm for computing competitive equilibrium prices which is competitive with standard steepest descent algorithms in extensive experiments.</description><identifier>ISSN: 0025-5610</identifier><identifier>EISSN: 1436-4646</identifier><identifier>DOI: 10.1007/s10107-022-01792-w</identifier><language>eng</language><publisher>Berlin/Heidelberg: Springer Berlin Heidelberg</publisher><subject>Algorithms ; Calculus of Variations and Optimal Control; Optimization ; Combinatorics ; Competition (Economics) ; Computer science ; Full Length Paper ; Mathematical and Computational Physics ; Mathematical Methods in Physics ; Mathematics ; Mathematics and Statistics ; Mathematics of Computing ; Numerical Analysis ; Substitutes ; Theoretical ; Valuation</subject><ispartof>Mathematical programming, 2024-01, Vol.203 (1-2), p.611-643</ispartof><rights>The Author(s) 2022</rights><rights>COPYRIGHT 2024 Springer</rights><rights>The Author(s) 2022. This work is published under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c468t-a8e0b0d5889689e8ad7864a3c2580794287fce2270981260559da426727e2f9d3</citedby><cites>FETCH-LOGICAL-c468t-a8e0b0d5889689e8ad7864a3c2580794287fce2270981260559da426727e2f9d3</cites><orcidid>0000-0002-5353-1839 ; 0000-0002-9033-210X</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27903,27904</link.rule.ids></links><search><creatorcontrib>Baldwin, Elizabeth</creatorcontrib><creatorcontrib>Bichler, Martin</creatorcontrib><creatorcontrib>Fichtl, Maximilian</creatorcontrib><creatorcontrib>Klemperer, Paul</creatorcontrib><title>Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices</title><title>Mathematical programming</title><addtitle>Math. Program</addtitle><description>We show the strong substitutes product-mix auction bidding language provides an intuitive and geometric interpretation of strong substitutes as Minkowski differences between sets that are easy to identify. We prove that competitive equilibrium prices for agents with strong substitutes preferences can be computed by minimizing the difference between two linear programs for the positive and the negative bids with suitably relaxed resource constraints. This also leads to a new algorithm for computing competitive equilibrium prices which is competitive with standard steepest descent algorithms in extensive experiments.</description><subject>Algorithms</subject><subject>Calculus of Variations and Optimal Control; Optimization</subject><subject>Combinatorics</subject><subject>Competition (Economics)</subject><subject>Computer science</subject><subject>Full Length Paper</subject><subject>Mathematical and Computational Physics</subject><subject>Mathematical Methods in Physics</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Mathematics of Computing</subject><subject>Numerical Analysis</subject><subject>Substitutes</subject><subject>Theoretical</subject><subject>Valuation</subject><issn>0025-5610</issn><issn>1436-4646</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2024</creationdate><recordtype>article</recordtype><recordid>eNp9kEtr3TAQhUVJoDdJ_0BXgm7jdCTLenQXQh6FQBZJ10JXHt8q2NaNJOeSf1-lDnRXZjEwnG_mzCHkK4MLBqC-ZwYMVAOcN8CU4c3hE9kw0cpGSCGPyAaAd00nGXwmJzk_AwBrtd4Q91hSnHc0L9tcQlkK5h80l7T4siQ30n2Ke0wlYD6nbu6pozMeqBt3MYXye6JDTNTHaY8VDq9I8WUJY9imsEyVDR7zGTke3Jjxy0c_Jb9urp-u7pr7h9ufV5f3jRdSl8ZphC30ndZGaoPa9UpL4VrPOw3KCK7V4JFzBUYzLqHrTO8El4or5IPp21Pybd1bLb8smIt9jkua60nLDRfcgARRVReraudGtGEeYknO1-pxCj7OOIQ6v1SamQ6UZBXgK-BTzDnhYOtbk0tvloF9z96u2duavf2bvT1UqF2hXMXzDtM_L_-h_gBXkIfS</recordid><startdate>20240101</startdate><enddate>20240101</enddate><creator>Baldwin, Elizabeth</creator><creator>Bichler, Martin</creator><creator>Fichtl, Maximilian</creator><creator>Klemperer, Paul</creator><general>Springer Berlin Heidelberg</general><general>Springer</general><general>Springer Nature B.V</general><scope>C6C</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0002-5353-1839</orcidid><orcidid>https://orcid.org/0000-0002-9033-210X</orcidid></search><sort><creationdate>20240101</creationdate><title>Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices</title><author>Baldwin, Elizabeth ; Bichler, Martin ; Fichtl, Maximilian ; Klemperer, Paul</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c468t-a8e0b0d5889689e8ad7864a3c2580794287fce2270981260559da426727e2f9d3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2024</creationdate><topic>Algorithms</topic><topic>Calculus of Variations and Optimal Control; Optimization</topic><topic>Combinatorics</topic><topic>Competition (Economics)</topic><topic>Computer science</topic><topic>Full Length Paper</topic><topic>Mathematical and Computational Physics</topic><topic>Mathematical Methods in Physics</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Mathematics of Computing</topic><topic>Numerical Analysis</topic><topic>Substitutes</topic><topic>Theoretical</topic><topic>Valuation</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Baldwin, Elizabeth</creatorcontrib><creatorcontrib>Bichler, Martin</creatorcontrib><creatorcontrib>Fichtl, Maximilian</creatorcontrib><creatorcontrib>Klemperer, Paul</creatorcontrib><collection>SpringerOpen</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Mathematical programming</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Baldwin, Elizabeth</au><au>Bichler, Martin</au><au>Fichtl, Maximilian</au><au>Klemperer, Paul</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices</atitle><jtitle>Mathematical programming</jtitle><stitle>Math. Program</stitle><date>2024-01-01</date><risdate>2024</risdate><volume>203</volume><issue>1-2</issue><spage>611</spage><epage>643</epage><pages>611-643</pages><issn>0025-5610</issn><eissn>1436-4646</eissn><abstract>We show the strong substitutes product-mix auction bidding language provides an intuitive and geometric interpretation of strong substitutes as Minkowski differences between sets that are easy to identify. We prove that competitive equilibrium prices for agents with strong substitutes preferences can be computed by minimizing the difference between two linear programs for the positive and the negative bids with suitably relaxed resource constraints. This also leads to a new algorithm for computing competitive equilibrium prices which is competitive with standard steepest descent algorithms in extensive experiments.</abstract><cop>Berlin/Heidelberg</cop><pub>Springer Berlin Heidelberg</pub><doi>10.1007/s10107-022-01792-w</doi><tpages>33</tpages><orcidid>https://orcid.org/0000-0002-5353-1839</orcidid><orcidid>https://orcid.org/0000-0002-9033-210X</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0025-5610
ispartof Mathematical programming, 2024-01, Vol.203 (1-2), p.611-643
issn 0025-5610
1436-4646
language eng
recordid cdi_proquest_journals_2924290604
source EBSCOhost Business Source Ultimate; Springer Link
subjects Algorithms
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Competition (Economics)
Computer science
Full Length Paper
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Substitutes
Theoretical
Valuation
title Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-25T20%3A36%3A26IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-gale_proqu&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Strong%20substitutes:%20structural%20properties,%20and%20a%20new%20algorithm%20for%20competitive%20equilibrium%20prices&rft.jtitle=Mathematical%20programming&rft.au=Baldwin,%20Elizabeth&rft.date=2024-01-01&rft.volume=203&rft.issue=1-2&rft.spage=611&rft.epage=643&rft.pages=611-643&rft.issn=0025-5610&rft.eissn=1436-4646&rft_id=info:doi/10.1007/s10107-022-01792-w&rft_dat=%3Cgale_proqu%3EA781950761%3C/gale_proqu%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c468t-a8e0b0d5889689e8ad7864a3c2580794287fce2270981260559da426727e2f9d3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2924290604&rft_id=info:pmid/&rft_galeid=A781950761&rfr_iscdi=true