h1

TY  - THES
AU  - Rieken, Niklas
TI  - Matroid optimization in auction theory
PB  - Rheinisch-Westfälische Technische Hochschule Aachen
VL  - Dissertation
CY  - Aachen
M1  - RWTH-2025-10701
SP  - 1 Online-Ressource : Illustrationen
PY  - 2025
N1  - Veröffentlicht auf dem Publikationsserver der RWTH Aachen University
N1  - Dissertation, Rheinisch-Westfälische Technische Hochschule Aachen, 2025
AB  - This thesis is mainly concerned with the theory of dynamic multi-item auctions, i.e., a processes in which, over time, there is communication between buyers and an auctioneer, who adjusts prices for the items based on that communication. There is a vast number of intriguing questions on those processes, both from an economic and a computational point of view. A Walrasian equilibrium—characterized by a price vector and an allocation of goods such that all agents maximize utility and the market clears—represents a central concept in general equilibrium theory. It is well-known that Walrasian equilibria are guaranteed to exist if all buyers have gross substitute valuation functions. Finding these equilibria by means of natural dynamic auctions (or tâtonnement) poses an interesting computational problem—finding excess demand sets to increase prices on—that previously involved submodular function minimization, which is a highly non-trivial process. We show that this process can be simplified in cognitive complexity and running time. This can either be achieved by very easy maximum flow computations if the valuation functions are simple enough, or by solving a polymatroid sum problem if we want to handle arbitrary gross substitute valuations. In both cases, the corresponding dual solution reveals the desired excess demand set. We also prove some structural properties about Walrasian prices (which form a lattice) and their relation to weaker notions of market equilibria. Our results bridge theoretical economics and algorithmic mechanism design, offering both a novel computational perspective and practical auction protocols to find equilibria. For a related ascending auction, to sell a base of a matroid, we show that its analysis can be simplified by using only a few folklore lemmas from matroid theory. This auction has the neat property that acting truthfully as a buyer is an equilibrium strategy—a feature that is typically not present in dynamic multi-item auctions with buyers having valuations that are not unit-demand; moreover, the auctions also output (under truthful signals) the utilitarian optimum, i.e., a matroid base of maximum weight. We also give additional remarks regarding communication cost and privacy matters of this auction. Finally, we study a natural extension of a greedy algorithm for submodular covering problems, which allows to remove previously chosen elements if they are recognized to be redundant. We are able to show that for this greedy algorithm natural subclass of submodular functions exhibits neat properties that can be seen as generalizations for properties of matroid rank functions. For some of these functions, we can show that the algorithm is guaranteed to compute an optimal solution to the submodular covering problem given any linear cost function.
LB  - PUB:(DE-HGF)11
DO  - DOI:10.18154/RWTH-2025-10701
UR  - https://publications.rwth-aachen.de/record/1023729
ER  -