Matroid optimization in auction theory

Rieken, Niklas; Kittsteiner, Thomas; Peis, Britta

doi:10.18154/RWTH-2025-10701

Matroid optimization in auction theory

Rieken, Niklas^RWTH*

2025

Verantwortlichkeitsangabevorgelegt von Niklas Rieken, M. Sc.

ImpressumAachen : RWTH Aachen University 2025

Umfang1 Online-Ressource : Illustrationen

Dissertation, Rheinisch-Westfälische Technische Hochschule Aachen, 2025

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak08

Hauptberichter/Gutachter
Peis, Britta (Thesis advisor)^RWTH* ; Kittsteiner, Thomas (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2025-11-11

Online
DOI: 10.18154/RWTH-2025-10701
URL: https://publications.rwth-aachen.de/record/1023729/files/1023729.pdf

Einrichtungen

Lehrstuhl für Management Science (815110)

Inhaltliche Beschreibung (Schlagwörter)
auction theory (frei) ; combinatorial optimization (frei) ; matchings (frei) ; matroids (frei) ; mechanism design (frei)

Thematische Einordnung (Klassifikation)
DDC: 330

Kurzfassung
Diese Arbeit befasst sich vor allem mit der Theorie iterativer Auktionen in denen mehrere Güter gleichzeitig zum Verkauf stehen. D.h. wir betrachten Prozesse, bei denen über die Zeit Kommunikation zwischen Käuferinnen und einem Auktionator stattfindet, welcher die Preise der Güter basierend auf dieser Kommunikation anpasst. Es gibt eine Vielzahl spannender Fragen zu diesen Prozessen, sowohl aus ökonomischer als auch aus mathematisch-informatischer Sicht. Walras-Gleichgewichte – gegeben durch Preisvektoren und Verteilungen der zum Verkauf stehenden Güter mit der Eigenschaft, dass alle Käuferinnen eine nutzenmaximale Menge von Gütern erhalten und dass der Markt geräumt wird – sind ein zentrales Konzept der allgemeinen Gleichgewichtstheorie. Es ist bekannt, dass Walras-Gleichgewichte garantiert existieren, wenn die Bewertungsfunktionen der Käuferinnen die Güter als Bruttosubstitute (gross substitutes) behandeln. Die Ermittlung dieser Gleichgewichte mittels natürlicher dynamischer Auktionen (oder Tâtonnement) wirft ein interessantes, kombinatorisches Problem auf, nämlich die Suche nach Gütern mit Nachfrageüberschuss auf denen der Preis erhöht werden soll. Bisher wurde dieses Problem mithilfe von Minimierung submodularer Funktionen gelöst, was ein sehr involvierter Prozess ist. Wir zeigen, dass dieses Problem mit einfacheren Mitteln, aber auch schneller gelöst werden kann. Dies kann entweder durch sehr einfache Maximalflussberechnungen erreicht werden, wenn die Bewertungsfunktionen einfach genug sind, oder durch die Lösung eines Polymatroid-Summenproblems, wenn wir beliebige Bruttosubstitutsbewertungen behandeln wollen. In beiden Fällen ergibt die zugehörige duale Lösung die gewünschte Menge an Gütern mit Nachfrageüberschuss. Wir beweisen außerdem einige strukturelle Eigenschaften von Walras-Preisen (die einen Verband bilden) und deren Beziehung zu schwächeren Gleichgewichtskonzepten. Unsere Ergebnisse schlagen eine Brücke zwischen theoretischen Wirtschaftswissenschaften und algorithmischem Auktionsdesign und bieten sowohl eine neuartige informatische Perspektive als auch praktische Auktionsprotokolle zur Gleichgewichtsfindung. Für eine verwandte aufsteigende Auktion zum Verkauf einer Basis eines Matroids zeigen wir, dass ihre Analyse durch die Verwendung nur weniger Lemmata aus der Matroidentheorie vereinfacht werden kann. Diese Auktion hat die interessante Eigenschaft, dass wahrheitsgemäße Kommunikation als Käuferin eine Gleichgewichtsstrategie darstellt – typischerweise ist bei dynamischen Auktionen mit mehreren Artikeln dies nicht gegeben, es sei denn, alle Käuferinnen sind an maximal einem Gut interessiert. Darüber hinaus liefert die Auktion (vermöge wahrheitsgemäßer Gebote) das utilitaristische Optimum, d.h. eine Matroid-Basis mit maximalem Gewicht. Wir geben außerdem zusätzliche Diskussionen zu den Kommunikationskosten und Datenschutzaspekten dieser Auktion. Abschließend untersuchen wir eine natürliche Erweiterung eines Greedy-Algorithmus für submodulare Überdeckungsprobleme, die es ermöglicht, zuvor ausgewählte Elemente zu entfernen, wenn diese als redundant erkannt werden. Wir können zeigen, dass eine für diesen Greedy-Algorithmus natürliche Unterklasse submodularer Funktionen interessante Eigenschaften aufweist, die als Verallgemeinerungen für Eigenschaften von Matroid-Rangfunktionen angesehen werden können. Für einige dieser Funktionen können wir zeigen, dass der Algorithmus, vermöge einer linearen Kostenfunktion, garantiert eine optimale Lösung für das submodulare Überdeckungsproblem berechnet.

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.

OpenAccess:
PDF
(additional files)