h1

% IMPORTANT: The following is UTF-8 encoded.  This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.

@PHDTHESIS{Rieken:1023729,
      author       = {Rieken, Niklas},
      othercontributors = {Peis, Britta and Kittsteiner, Thomas},
      title        = {{M}atroid optimization in auction theory},
      school       = {Rheinisch-Westfälische Technische Hochschule Aachen},
      type         = {Dissertation},
      address      = {Aachen},
      publisher    = {RWTH Aachen University},
      reportid     = {RWTH-2025-10701},
      pages        = {1 Online-Ressource : Illustrationen},
      year         = {2025},
      note         = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
                      University; Dissertation, Rheinisch-Westfälische Technische
                      Hochschule Aachen, 2025},
      abstract     = {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.},
      cin          = {815110},
      ddc          = {330},
      cid          = {$I:(DE-82)815110_20140620$},
      typ          = {PUB:(DE-HGF)11},
      doi          = {10.18154/RWTH-2025-10701},
      url          = {https://publications.rwth-aachen.de/record/1023729},
}