Guest lectures
Current semester
On the pay-as-bid auction game
Speaker: Dr. Martina Vanelli
Motivated by the current structure of ancillary services markets in wholesale electricity markets, we introduce and analyze the pay-as-bid auction game, a supply function model with discriminatory pricing and asymmetric firms. In contrast to the existing models in the literature typically based on uniform-price auctions (where participants are rewarded at the market-clearing price), in the pay-as-bid auction game, firms are remunerated based on their bid prices. In this game, strategies are non-decreasing supply functions relating price to quantity and the exact choice of the strategy space turns out to be a crucial issue. We first observe that (pure-strategy) Nash equilibria do not generally exist when the strategy space includes all non-decreasing continuous functions. To overcome this, we restrict the strategy space to the set of K-Lipschitz supply functions. In this setting, we are able to prove that Nash equilibria always exist and consist of functions that are affine on their own support and have slope K. We further show that, when the demand is affine and the marginal costs are homogenous in zero, the Nash equilibrium is unique and a characterization can be given. Finally, for quadratic costs, we derive a closed-form expression for the limit as K approaches infinity. Our findings show that the pay-as-bid auction game lies between Bertrand and Cournot oligopoly models and results in a lower market-clearing price compared to supply function models based on uniform price auctions.
- 27.11.2024
- 10:00 p.m. - 11:00 p.m.
- (HK 30) Room 128
Previous semesters
Diagrams, clustering, and coresets,and their application to the representation of polycrystals
Speaker: Prof. Peter Gritzman
We study geometric diagrams and their relation to constrained clustering with a view towards representing and analyzing polycrystalline materials and their dynamics. We introduce various techniques for converting grain maps into geometric diagrams. In particular, weight-constrained anisotropic clustering allows to compute diagram representations from data on the volume, center and moments of the grains which are available through tomographic measurements. Also we develop new coreset techniques, interesting in their own right, which are utilized to significantly accelerate the computations. This effect is demonstrated on 3D real-world data sets.
(The talk is based on recent joint work with A. Alpers, M. Fiedler, F. Klemm.)
A branch-and-bound algorithm for non-convex Nash equilibrium problems
Speaker: Prof. Dr. Oliver Stein
We present the first spatial branch-and-bound method for the computation of the set of all epsilon-Nash equilibria of continuous box-constrained non-convex Nash equilibrium problems with an approximation guarantee. Thereby, the existence of epsilon-Nash equilibria is not assumed, but the algorithm is also able to detect their absence. After a brief introduction to branch-and-bound ideas in global optimization, we explain appropriate discarding and fathoming techniques for Nash equilibrium problems, formulate convergence results for the proposed algorithm, and report our computational experience.
Solving Mixed-Integer Semidefinite Programs
Speaker: Prof. Dr. Marc Pfetsch
Semidefinite programs try to optimize a positive semidefinite matrix subject to linear inequality constraints. This class can be extended to mixed-integer semidefinite programs in which some of the variables are required to be integer. This forms an interesting class of optimization problems with many applications. This talk will introduce new methods as well as techniques that can be generalized from the linear to the semidefinite world. This includes presolving methods, e.g., fixing of variables, bound strengthening etc. Moreover, handling of symmetries and so-called conflict analysis can be adapted and have a positive impact on the performance. The impact of the methods will be illustrated computationally, using SCIP-SDP, an open-source solver for mixed-integer semidefinite programs based on SCIP.
Bicriteria Nash Flows over Time
Speaker: Dr. Tim Oosterwijk
Flows over time are a natural way to incorporate flow dynamics that arise in various applications such as traffic networks. In this talk I will introduce a natural variant
of the deterministic fluid queuing model in which users aim to minimize their costs subject to arrival at their destination before a prespecified deadline. We determine
the existence and the structure of Nash flows over time and fully characterize the price of anarchy for this model.
The price of anarchy measures the ratio of the quality of the equilibrium and the quality of the optimum flow, where we evaluate the quality using two different natural
performance measures: the throughput for a given deadline and the makespan for a given amount of flow. While it turns out that both prices of anarchy can be unbounded
in general, we provide tight bounds for the important subclass of parallel path graphs.
Convergence of approximate and packet-routing equilibria to Nash flows over time
Speaker: Dr. Leon Sering
We consider a dynamic model of traffic that has received a lot of attention in the past few years. Infinitesimally small agents aim to travel from a source to a destination as quickly as possible. Flow patterns vary over time, and congestion effects are modeled via queues, which form based on the deterministic queueing model whenever the inflow into a link exceeds its capacity.
Are equilibria in this model meaningful as a prediction of traffic behavior? For this to be the case, a certain notion of stability under ongoing perturbations is needed. Real traffic consists of discrete, atomic "packets", rather than being a continuous flow of nonatomic agents. Users may not choose an absolutely quickest route available, if there are multiple routes with very similar travel times. We would hope that in both these situations --- a discrete packet model, with packet size going to 0, and ε-equilibria, with ε going to 0 --- equilibria converge to dynamic equilibria in the flow-over-time model. No such convergence results were known.
We show that such a convergence result does hold for both of these settings, in a unified way. More precisely, we introduce a notion of "strict" ε-equilibria, and show that these must converge to the exact dynamic equilibrium in the limit as ε goes to 0. We then show that results for the two settings mentioned can be deduced from
This research is joint work with Neil Olver (LSE London) and Laura Vargas Koch (ETH Zürich).
Share this page
