東華大學圖書館 |

New Optimization Models and Methods for Classical, Infinite-Dimensional, and Online Fisher Markets.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	New Optimization Models and Methods for Classical, Infinite-Dimensional, and Online Fisher Markets./
作者:	Gao, Yuan.
面頁冊數:	1 online resource (209 pages)
附註:	Source: Dissertations Abstracts International, Volume: 84-02, Section: B.
Contained By:	Dissertations Abstracts International84-02B.
標題:	Operations research. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=29256641click for full text (PQDT)
ISBN:	9798834063087

New Optimization Models and Methods for Classical, Infinite-Dimensional, and Online Fisher Markets.
Gao, Yuan.

New Optimization Models and Methods for Classical, Infinite-Dimensional, and Online Fisher Markets. - 1 online resource (209 pages)

Source: Dissertations Abstracts International, Volume: 84-02, Section: B.

Thesis (Ph.D.)--Columbia University, 2022.

Includes bibliographical references

Fisher market models and market equilibrium computation algorithms have long been central research topics in economics, operations research, and theoretical computer science. Recently, they have found diverse applications in the design of Internet marketplaces. In this thesis, we develop tractable optimization models and algorithms for computing market equilibria under various practically relevant settings.In Chapter 1, we study first-order methods for computing market equilibria under a finite number of buyers with linear, quasilinear or Leontief utilities. For linear and Leontief utilities, we show that their corresponding convex programs---whose solutions are market equilibria and vice versa---exhibits strong-convexity-like structures after simple reformulations. This allows us to design the first gradient-based algorithms that achieve a linear rate of convergence for computing market equilibria. For buyers with quasilinear utility functions, we propose a new convex program capturing market equilibria, which is analogous to the Shmyrev convex program for linear utilities. Applying the mirror descent algorithm to this convex program leads to a distributed and interpretable Proportional Response (PR) dynamics that converges to equilibrium prices and utilities. This generalizes the classical PR dynamics and its convergence guarantees, previously known for linear utilities, to the case of quasilinear utilities.In Chapter 2, we consider a generalization of a linear Fisher market where there is a finite set of buyers and a measurable item space. We introduce generalizations of the Eisenberg-Gale convex program and its dual to this setting, which leads to infinite-dimensional Banach-space optimization problems. We show that these convex programs always have optimal solutions and these optimal solutions correspond to market equilibria. In particular, a market equilibrium always exists. We also show that KKT-type optimality conditions for these convex programs imply the defining properties of market equilibria and are necessary and sufficient for a solution pair to be optimal. Then, we show that, similar to the classical finite-dimensional case, a market equilibrium is Pareto optimal, envy-free and proportional. Moreover, when the item space measure is atomless, we show that there always exists a pure equilibrium allocation, which can be viewed as a generalized fair division, that is, a Pareto optimal, envy-free, and proportional partition of the item space. This leads to generalizations of classical results on the existence and characterizations of fair divisions of a measurable set. When the item space is a closed interval and buyers have piecewise linear valuations, we show that the infinite-dimensional Eisenberg-Gale-type convex program can be reformulated as a finite-dimensional convex conic program, which can be solved efficiently using off-the-shelf optimization software. Based on the convex conic reformulation, we also develop the first polynomial-time algorithm for finding a fair division of an interval under piecewise linear valuations. For general buyer valuations or a very large number of buyers, we propose computing market equilibria using stochastic optimization and give high-probability convergence guarantees. Finally, we show that most of the above results easily extend to the case of quasilinear utilities.In Chapter 3, we consider an online market setting where items arrive sequentially and must be allocated to buyers irrevocably. We define the notion of an online market equilibrium as time-indexed allocations and prices which guarantee buyer optimality and market clearance in hindsight. We propose simple, scalable and interpretable allocation and pricing dynamics termed as PACE (Pacing ACcording to Estimated utilities). When items are drawn independently from an unknown distribution with a possibly continuous support, we show that PACE leads to an online market equilibrium asymptotically. In particular, PACE ensures that buyers' time-averaged utilities converge to the equilibrium utilities of a static market with item supplies being the unknown distribution and that buyers' time-averaged expenditures converge to their per-period budget. Hence, many desirable properties of market equilibrium-based fair division such as envy-freeness, Pareto optimality, and the proportional-share guarantee are also attained asymptotically in the online setting. Next, we extend the dynamics to handle quasilinear buyer utilities, which gives the first online algorithm for computing pacing equilibria in first-price auctions. Finally, numerical experiments show that the dynamics converges quickly under various metrics.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2023

Mode of access: World Wide Web

ISBN: 9798834063087Subjects--Topical Terms:

547123
Operations research.
Subjects--Index Terms:

Convex optimizationIndex Terms--Genre/Form:

542853
Electronic books.

New Optimization Models and Methods for Classical, Infinite-Dimensional, and Online Fisher Markets.
LDR:06128nmm a2200409K 4500 001 2356454
005 20230612110826.5
006 m o d
007 cr mn ---uuuuu
008 241011s2022 xx obm 000 0 eng d
020 $a 9798834063087
035 $a (MiAaPQ)AAI29256641
035 $a AAI29256641
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Gao, Yuan. $3 1244884
245 1 0 $a New Optimization Models and Methods for Classical, Infinite-Dimensional, and Online Fisher Markets.
264 0 $c 2022
300 $a 1 online resource (209 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 84-02, Section: B.
500 $a Advisor: Kroer, Christian.
502 $a Thesis (Ph.D.)--Columbia University, 2022.
504 $a Includes bibliographical references
520 $a Fisher market models and market equilibrium computation algorithms have long been central research topics in economics, operations research, and theoretical computer science. Recently, they have found diverse applications in the design of Internet marketplaces. In this thesis, we develop tractable optimization models and algorithms for computing market equilibria under various practically relevant settings.In Chapter 1, we study first-order methods for computing market equilibria under a finite number of buyers with linear, quasilinear or Leontief utilities. For linear and Leontief utilities, we show that their corresponding convex programs---whose solutions are market equilibria and vice versa---exhibits strong-convexity-like structures after simple reformulations. This allows us to design the first gradient-based algorithms that achieve a linear rate of convergence for computing market equilibria. For buyers with quasilinear utility functions, we propose a new convex program capturing market equilibria, which is analogous to the Shmyrev convex program for linear utilities. Applying the mirror descent algorithm to this convex program leads to a distributed and interpretable Proportional Response (PR) dynamics that converges to equilibrium prices and utilities. This generalizes the classical PR dynamics and its convergence guarantees, previously known for linear utilities, to the case of quasilinear utilities.In Chapter 2, we consider a generalization of a linear Fisher market where there is a finite set of buyers and a measurable item space. We introduce generalizations of the Eisenberg-Gale convex program and its dual to this setting, which leads to infinite-dimensional Banach-space optimization problems. We show that these convex programs always have optimal solutions and these optimal solutions correspond to market equilibria. In particular, a market equilibrium always exists. We also show that KKT-type optimality conditions for these convex programs imply the defining properties of market equilibria and are necessary and sufficient for a solution pair to be optimal. Then, we show that, similar to the classical finite-dimensional case, a market equilibrium is Pareto optimal, envy-free and proportional. Moreover, when the item space measure is atomless, we show that there always exists a pure equilibrium allocation, which can be viewed as a generalized fair division, that is, a Pareto optimal, envy-free, and proportional partition of the item space. This leads to generalizations of classical results on the existence and characterizations of fair divisions of a measurable set. When the item space is a closed interval and buyers have piecewise linear valuations, we show that the infinite-dimensional Eisenberg-Gale-type convex program can be reformulated as a finite-dimensional convex conic program, which can be solved efficiently using off-the-shelf optimization software. Based on the convex conic reformulation, we also develop the first polynomial-time algorithm for finding a fair division of an interval under piecewise linear valuations. For general buyer valuations or a very large number of buyers, we propose computing market equilibria using stochastic optimization and give high-probability convergence guarantees. Finally, we show that most of the above results easily extend to the case of quasilinear utilities.In Chapter 3, we consider an online market setting where items arrive sequentially and must be allocated to buyers irrevocably. We define the notion of an online market equilibrium as time-indexed allocations and prices which guarantee buyer optimality and market clearance in hindsight. We propose simple, scalable and interpretable allocation and pricing dynamics termed as PACE (Pacing ACcording to Estimated utilities). When items are drawn independently from an unknown distribution with a possibly continuous support, we show that PACE leads to an online market equilibrium asymptotically. In particular, PACE ensures that buyers' time-averaged utilities converge to the equilibrium utilities of a static market with item supplies being the unknown distribution and that buyers' time-averaged expenditures converge to their per-period budget. Hence, many desirable properties of market equilibrium-based fair division such as envy-freeness, Pareto optimality, and the proportional-share guarantee are also attained asymptotically in the online setting. Next, we extend the dynamics to handle quasilinear buyer utilities, which gives the first online algorithm for computing pacing equilibria in first-price auctions. Finally, numerical experiments show that the dynamics converges quickly under various metrics.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2023
538 $a Mode of access: World Wide Web
650 4 $a Operations research. $3 547123
650 4 $a Computer science. $3 523869
653 $a Convex optimization
653 $a Equilibrium computation
653 $a Fair division
653 $a Fisher market
653 $a Market design
653 $a Resource allocation
655 7 $a Electronic books. $2 lcsh $3 542853
690 $a 0796
690 $a 0984
690 $a 0511
710 2 $a ProQuest Information and Learning Co. $3 783688
710 2 $a Columbia University. $b Operations Research. $3 2096452
773 0 $t Dissertations Abstracts International $g 84-02B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=29256641 $z click for full text (PQDT)