Yinyu Ye Department if Management Science and Engineering Stanford University ISMP 2006
Outline Proving Theorems using LP - Walras-Arrow-Debreu Equilibrium
- Linear Conic Programming
Photo Album of George (Applications presented here are by no means complete)
Outline LP in Auction Pricing Proving Theorems using LP - Uncapacitated Facility Location
- Core of Cooperative Game
Applications of LP Algorithms - Walras-Arrow-Debreu equilibrium
- Linear Conic Programming
Photo Album of George
World Cup Betting Example Market for World Cup Winner - Assume 5 teams have a chance to win the 2006 World Cup:
- Argentina, Brazil, Italy, Germany and France
- We’d like to have a standard payout of $1 if a participant has a claim where his selected team won
Sample Orders
Markets for Contingent Claims A Contingent Claim Market - S possible states of the world (one will be realized).
- N participants who (say j), submit orders to a market organizer containing the following information:
- ai,j - State bid (either 1 or 0)
- qj – Limit contract quantity
- πj – Limit price per contract
- Call auction mechanism is used by one market organizer.
- If orders are filled and correct state is realized, the organizer will pay the participant a fixed amount w for each winning contract.
- The organizer would like to determine the following:
- pi – State price
- xj – Order fill
Central Organization of the Market Belief-based - Central organizer will determine prices for each state based on his beliefs of their likelihood
- This is similar to the manner in which fixed odds bookmakers operate in the betting world
- Generally not self-funding
Parimutuel - A self-funding technique popular in horseracing betting
Parimutuel Methods Definition - Etymology: French pari mutuel, literally, mutual stake A system of betting on races whereby the winners divide the total amount bet, after deducting management expenses, in proportion to the sums they have wagered individually.
Example: Parimutuel Horseracing Betting
Parimutuel Market Microstructure
World Cup Betting Results
Outline LP in Auction Pricing Proving Theorems using LP - Uncapacitated Facility Location
- Core of Cooperative Game
Applications of LP Algorithms - Walras-Arrow-Debreu equilibrium
- Linear Conic Programming
Photo Album of George
Facility Location Problem Input A set of clients or cities D A set of facilities F with facility cost fi Connection cost Cij, (obey triangle inequality) Output A subset of facilities F’ An assignment of clients to facilities in F’ Objective Minimize the total cost (facility + connection)
Facility Location Problem
Facility Location Problem
Hardness Results
Time = 0
Time = 1
Time = 2
Time = 3
Time = 4
Time = 5
Time = 5
Time = 6
Time = 6
Approximation Results
Other Revealing LP Examples N. Bansal et al. on “Further improvements in competitive guarantees for QoS buffering,” 2004. Mehta et al on “Adwords and Generalized Online Matching,” 2005
Core of Cooperative Game A set of alliance-proof allocations of profit (Scarf [1967]) Deterministic game (using linear programming duality, Dantzig/Von Neumann [1948]) - Linear Production, MST, flow game, some location games (Owen [1975]), Samet and Zemel [1984], Tamir [1991], Deng et al. [1994], Feigle et al. [1997], Goemans and Skutella [2004], etc.)
Stochastic game (using stochastic linear programming duality, Rockafellar and Wets [1976]) - Inventory game, Newsvendor (Anupindi et al. [2001], Muller et al. [2002], Slikker et al. [2005], Chen and Zhang [2006], etc. )
Outline LP in Auction Pricing Proving Theorems using LP - Uncapacitated Facility Location
- Core of Alliance
Applications of LP Algorithms - Walras-Arrow-Debreu equilibrium
- Linear Conic Programming
Photo Album of George
Walras-Arrow-Debreu Equilibrium The problem was first formulated by Leon Walras in 1874, Elements of Pure Economics, or the Theory of Social Wealth n players, each with an initial endowment of a divisible good utility function for consuming all goods—own and others. Every player sells the entire initial endowment uses the revenue to buy a bundle of goods such that his or her utility function is maximized. Walras asked: Can prices be set for all the goods such that the market clears? Answer by Arrow and Debreu in 1954: yes, under mild conditions if the utility functions are concave.
Walras-Arrow-Debreu Equilibrium
Fisher Equilibrium
Utility Functions
Equilibrium Computation
Equilibrium Computation
Equilibrium Computation
Equilibrium Computation
Linear Conic Programming
Outline LP in Auction Pricing - Parimutuel Call Auction
- Core of Alliance
Proving Theorems using LP - Uncapacitated Facility Location
Applications of LP Algorithms - Walras-Arrow-Debreu equilibrium
- Linear Conic Programming
Photo Album of George
Childhood Years
University Student Years
1967 Stanford OR
1975 National Medal of Science
1975 Nobel Laureate
1987 Student Graduation
2003 Science Fiction
2004 90th Birthday Party
2004 90th Birthday Party
2004 90th Birthday Party
LP/Dantzig Legacy Continues …
Dostları ilə paylaş: |