h1

001023729 001__ 1023729
001023729 005__ 20251222085425.0
001023729 0247_ $$2HBZ$$aHT031357387
001023729 0247_ $$2Laufende Nummer$$a44842
001023729 0247_ $$2datacite_doi$$a10.18154/RWTH-2025-10701
001023729 037__ $$aRWTH-2025-10701
001023729 041__ $$aEnglish
001023729 082__ $$a330
001023729 1001_ $$0P:(DE-82)IDM07267$$aRieken, Niklas$$b0$$urwth
001023729 245__ $$aMatroid optimization in auction theory$$cvorgelegt von Niklas Rieken, M. Sc.$$honline
001023729 260__ $$aAachen$$bRWTH Aachen University$$c2025
001023729 300__ $$a1 Online-Ressource : Illustrationen
001023729 3367_ $$02$$2EndNote$$aThesis
001023729 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
001023729 3367_ $$2BibTeX$$aPHDTHESIS
001023729 3367_ $$2DRIVER$$adoctoralThesis
001023729 3367_ $$2DataCite$$aOutput Types/Dissertation
001023729 3367_ $$2ORCID$$aDISSERTATION
001023729 502__ $$aDissertation, Rheinisch-Westfälische Technische Hochschule Aachen, 2025$$bDissertation$$cRheinisch-Westfälische Technische Hochschule Aachen$$d2025$$gFak08$$o2025-11-11
001023729 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University
001023729 5203_ $$aDiese 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.$$lger
001023729 520__ $$aThis 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.$$leng
001023729 588__ $$aDataset connected to Lobid/HBZ
001023729 591__ $$aGermany
001023729 653_7 $$aauction theory
001023729 653_7 $$acombinatorial optimization
001023729 653_7 $$amatchings
001023729 653_7 $$amatroids
001023729 653_7 $$amechanism design
001023729 7001_ $$0P:(DE-82)IDM02810$$aPeis, Britta$$b1$$eThesis advisor$$urwth
001023729 7001_ $$0P:(DE-82)IDM07293$$aKittsteiner, Thomas$$b2$$eThesis advisor$$urwth
001023729 8564_ $$uhttps://publications.rwth-aachen.de/record/1023729/files/1023729_source.zip$$yRestricted
001023729 8564_ $$uhttps://publications.rwth-aachen.de/record/1023729/files/1023729.pdf$$yOpenAccess
001023729 909CO $$ooai:publications.rwth-aachen.de:1023729$$pdnbdelivery$$pdriver$$pVDB$$popen_access$$popenaire
001023729 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
001023729 9141_ $$y2025
001023729 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM07267$$aRWTH Aachen$$b0$$kRWTH
001023729 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM02810$$aRWTH Aachen$$b1$$kRWTH
001023729 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM07293$$aRWTH Aachen$$b2$$kRWTH
001023729 9201_ $$0I:(DE-82)815110_20140620$$k815110$$lLehrstuhl für Management Science$$x0
001023729 961__ $$c2025-12-19T15:07:48.005616$$x2025-12-15T13:21:50.550443$$z2025-12-19T15:07:48.005616
001023729 980__ $$aI:(DE-82)815110_20140620
001023729 980__ $$aVDB
001023729 980__ $$aUNRESTRICTED
001023729 980__ $$aphd
001023729 9801_ $$aFullTexts