2013/07/10 by Johannes Müller, Johannes C. Müller, Müller, Johannes C.
Business, Management and Accounting · Computer Science · Decision Sciences · Mathematics · #90C11 #90C33 #91A46 #91B15 #91B26 #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Consumer Market Behavior and Pricing #FOS: Computer and information sciences #FOS: Mathematics #G.1.6 #K.6.0 #Optimization and Control (math.OC) #Optimization and Search Problems #acm:90C11 #acm:90C33 #acm:91A46 #acm:91B15 #acm:91B26 #cs.GT #math.OC #msc:90C11 #msc:90C33 #msc:91A46 #msc:91B15 #msc:91B26
paper · pdf · doi:10.48550/arxiv.1307.2852
26 pages, 3 figures. (Minor revision: some reformulations, simplified proof of Theorem 13, one additional figure.)
openalex publication_date 2013/07/10 · arxiv created 2013/09/03 · arxiv updated 2013/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The goal of an auction is to determine commodity prices such that all participants are perfectly happy. Such a solution is called a competitive equilibrium and does not exist in general. For this reason we are interested in solutions which are similar to a competitive equilibrium. The article introduces two relaxations of a competitive equilibrium for general auctions. Both relaxations determine one price per commodity by solving a difficult non-convex optimization problem. The first model is a mathematical program with equilibrium constraints (MPEC), which ensures that each participant is either perfectly happy or his bid is rejected. An exact algorithm and a heuristic are provided for this model. The second model is a relaxation of the first one and only ensures that no participant incurs a loss. In an optimal solution to the second model, no participant can be made better off without making another one worse off.