Denys Trieskunov, Machine Learning Approaches to Accelerate Column Generation, University of Zurich, Faculty of Business, Economics and Informatics, 2023. (Master's Thesis)
Column Generation is a method in operations research that allows you to solve large-scale optimization problems. It is mostly used when solving the problem with all variables all at once is either too memory/time-consuming. The method can be divided into two distinct parts: solving the master problem and solving sub-problems. The method itself alternates between the two. The master problem is updated with new columns that are solutions of sub-problems, while sub-problems use updated duals from the latest master problem solution. This loop goes on until the master problem is optimized. Due to the nature of the algorithm as well as the problems it is usually being used to solve, Column Generation often requires a large amount of time to converge and uses a large volume of memory. There are different ways to improve the run-time, as well as several research papers that involve using machine learning for doing it. However, the idea of selecting and executing only sub-problems that would lead to reaching the optimum faster was largely unexplored. In this work, we would like to focus on this particular part of the Column Generation algorithm and show that if we find a way to not run the sub-problems that don’t contribute to master problem convergence, the run-time of the algorithm might be improved. Our approach is to use a Logistic regression model to determine which sub-problems we should execute and which should be dismissed. The features that we use for prediction are simple, scalable, transferable features that can be easily extracted dynamically without sacrificing too much run-time. The model, being an LR model makes predictions rather fast as well. The approach was implemented and tested by adapting the existing Column Generation implementation for solving crew diagramming problems. In our implementation, we enhanced the algorithm by adopting the ML model to execute only sub-problems selected by the model. The original algorithm is developed by Algomia GmbH for Swiss Railways. Our approach was implemented and tested on the same Swiss Federal Railways data the original algorithm uses. The reasoning for this is easier data mining and being able to meaningfully compare our approach to the baseline algorithm. |
|
Jakob Weissteiner, Jakob Heiss, Julien Siems, Sven Seuken, Bayesian Optimization-based Combinatorial Assignment, In: 37th AAAI Conference on Artificial Intelligence (AAAI'23), AAAI Press, 2023-02-07. (Conference or Workshop Paper published in Proceedings)
We study the combinatorial assignment domain, which includes combinatorial auctions and course allocation. The main challenge in this domain is that the bundle space grows exponentially in the number of items. To address this, several papers have recently proposed machine learning-based preference elicitation algorithms that aim to elicit only the most important information from agents. However, the main shortcoming of this prior work is that it does not model a mechanism's uncertainty over values for not yet elicited bundles. In this paper, we address this shortcoming by presenting a Bayesian optimization-based combinatorial assignment (BOCA) mechanism. Our key technical contribution is to integrate a method for capturing model uncertainty into an iterative combinatorial auction mechanism. Concretely, we design a new method for estimating an upper uncertainty bound that can be used to define an acquisition function to determine the next query to the agents. This enables the mechanism to properly explore (and not just exploit) the bundle space during its preference elicitation phase. We run computational experiments in several spectrum auction domains to evaluate BOCA's performance. Our results show that BOCA achieves higher allocative efficiency than state-of-the-art approaches. |
|
Hsuan-Pin Wu, Alternative Algorithmic Approaches for Crew Diagramming, University of Zurich, Faculty of Business, Economics and Informatics, 2022. (Master's Thesis)
The crew diagramming problem has been a challenging task in the railway industry. The massive amount of tasks, requiring multiple crew members to work together under a large set of constrains, create a large scale optimization problem. The common approach to solve this problem which is widely used by the railway companies, is to formulate an integer linear program and decompose it by column generation into a master problem and a sub-problem. However, the sub-problem is often a resource constrained shortest path problem which is NP-hard and the computational time is in the order of hours to days.

We designed an alternative algorithmic approach for the crew diagramming by performing Danztig-Wolfe decomposition on a flow based linear program with set partition constraint. Even though the master problem is still a set partition LP with column generation and minimum cost flow pricing problem, we reduced the number of constraints and avoided solving an NP-hard problem. In order to speed up solving the pricing problem, we split the original network into multiple sub-networks and paralellized the computation of the pricing models. In the end we solved the master problem as an integer programming problem only with the variables selected by the column generation.

This optimization approach was then implemented on real world data provided by Swiss Railways. We compared the results in terms of computational time with the flow based optimizer developed by Algomia GmbH and found that for small and medium-sized depots, our approach is faster on average when compared to the computation time required to arrive only at the LP-solution with Algomia's algorithm. When comparing our results in terms of the number of diagrams with those produced by manual planners, we found a consistent improvement for larger-size depots, where slight adjustments to the constraints often performed by planners have less of an impact on the overall result. |
|
Jakob Weissteiner, Jakob Heiss, Julien Siems, Sven Seuken, Monotone-Value Neural Networks: Exploiting Preference Monotonicity in Combinatorial Assignment, In: Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, International Joint Conferences on Artificial Intelligence Organization, 2022-07-23. (Conference or Workshop Paper published in Proceedings)
Many important resource allocation problems involve the combinatorial assignment of items, e.g., auctions or course allocation. Because the bundle space grows exponentially in the number of items, preference elicitation is a key challenge in these domains. Recently, researchers have proposed ML-based mechanisms that outperform traditional mechanisms while reducing preference elicitation costs for agents. However, one major shortcoming of the ML algorithms that were used is their disregard of important prior knowledge about agents' preferences. To address this, we introduce monotone-value neural networks (MVNNs), which are designed to capture combinatorial valuations, while enforcing monotonicity and normality. On a technical level, we prove that our MVNNs are universal in the class of monotone and normalized value functions, and we provide a mixed-integer linear program (MILP) formulation to make solving MVNN-based winner determination problems (WDPs) practically feasible. We evaluate our MVNNs experimentally in spectrum auction domains. Our results show that MVNNs improve the prediction performance, they yield state-of-the-art allocative efficiency in the auction, and they also reduce the run-time of the WDPs. Our code is available on GitHub: https://github.com/marketdesignresearch/MVNN. |
|
Jakob Weissteiner, Chris Wendler, Sven Seuken, Benjamin Lubin, Markus Püschel, Fourier Analysis-based Iterative Combinatorial Auctions, In: Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, International Joint Conferences on Artificial Intelligence Organization, 2022-07-23. (Conference or Workshop Paper published in Proceedings)
Recent advances in Fourier analysis have brought new tools to efficiently represent and learn set functions. In this paper, we bring the power of Fourier analysis to the design of combinatorial auctions (CAs). The key idea is to approximate bidders' value functions using Fourier-sparse set functions, which can be computed using a relatively small number of queries. Since this number is still too large for practical CAs, we propose a new hybrid design: we first use neural networks (NNs) to learn bidders’ values and then apply Fourier analysis to the learned representations. On a technical level, we formulate a Fourier transform-based winner determination problem and derive its mixed integer program formulation. Based on this, we devise an iterative CA that asks Fourier-based queries. We experimentally show that our hybrid ICA achieves higher efficiency than prior auction designs, leads to a fairer distribution of social welfare, and significantly reduces runtime. With this paper, we are the first to leverage Fourier analysis in CA design and lay the foundation for future work in this area. Our code is available on GitHub: https://github.com/marketdesignresearch/FA-based-ICAs. |
|
Jakob M Heiss, Jakob Weissteiner, Hanna S Wutte, Sven Seuken, Josef Teichmann, NOMU: Neural Optimization-based Model Uncertainty, In: Proceedings of the 39th International Conference on Machine Learning (ICML'22), PMLR, 2022-07-17. (Conference or Workshop Paper published in Proceedings)
We study methods for estimating model uncertainty for neural networks (NNs) in regression. To isolate the effect of model uncertainty, we focus on a noiseless setting with scarce training data. We introduce five important desiderata regarding model uncertainty that any method should satisfy. However, we find that established benchmarks often fail to reliably capture some of these desiderata, even those that are required by Bayesian theory. To address this, we introduce a new approach for capturing model uncertainty for NNs, which we call Neural Optimization-based Model Uncertainty (NOMU). The main idea of NOMU is to design a network architecture consisting of two connected sub-NNs, one for model prediction and one for model uncertainty, and to train it using a carefully-designed loss function. Importantly, our design enforces that NOMU satisfies our five desiderata. Due to its modular architecture, NOMU can provide model uncertainty for any given (previously trained) NN if given access to its training data. We evaluate NOMU in various regressions tasks and noiseless Bayesian optimization (BO) with costly evaluations. In regression, NOMU performs at least as well as state-of-the-art methods. In BO, NOMU even outperforms all considered benchmarks. |
|
Raphael Haemmerli, Shapley-Based Core-Selecting Payment Rules, University of Zurich, Faculty of Business, Economics and Informatics, 2022. (Bachelor's Thesis)
Recent research has found Shapley-based core-selecting payment rules to perform well in combinatorial auctions, but we still lack a satisfactory explanation for their good performance. We investigate the hypothesis that low local manipulability can explain the good performance of Shapley-nearest, one Shapley-based payment rule. To this end, we define a local manipulability metric that measures the expected influence bidders can exert on their own payments. In order to measure the local manipulability, we develop a method for finding the derivatives of core-selecting payment rules in any domain. We provide analytical and experimental results for the well-known LLG domain and for the L3G domain, a slightly more complex domain we introduce. We show that
Shapley-nearest does not have a particularly low local manipulability compared to other core-selecting payment rules. Further, we show that local manipulability generally is not a good predictor for the performance of payment rules. Lastly, we introduce a novel core- selecting payment rule that we call SVCG-nearest. It is a hybrid between Shapley-nearest
and Quadratic, the payment rule used most commonly in practice. We find SVCG-nearest to have good performance and show that it has very low local manipulability. |
|
Sven Seuken, Paul Friedrich, Ludwig Dierks, Market Design for Drone Traffic Management, In: 36th AAAI Conference on Artificial Intelligence, Palo Alto, USA, 2022. (Conference or Workshop Paper published in Proceedings)
The rapid development of drone technology is leading to more and more use cases being proposed. In response, regulators are drawing up drone traffic management frameworks. However, to design solutions that are efficient, fair, simple, non-manipulable, and scalable, we need market design and AI expertise. To this end, we introduce the drone traffic management problem as a new research challenge to the market design and AI communities. We present five design desiderata
that we have derived from our interviews with stakeholders from the regulatory side as well as from public and private enterprises. Finally, we provide an overview of the solution space to point out possible directions for future research. |
|
Vitor Bosshard, Understanding Incentives in Combinatorial Auctions under Incomplete Information, University of Zurich, Faculty of Business, Economics and Informatics, 2022. (Dissertation)
|
|
Ludwig Dierks, Sven Seuken, Cloud Pricing: The Spot Market Strikes Back, Management Science, 2022. (Journal Article)
|
|
Luca Locher, Estimating Preferences, Search Friction and the Impact of Search Technology in the Adoption Market, University of Zurich, Faculty of Business, Economics and Informatics, 2021. (Bachelor's Thesis)
In the United States, more than 100,000 children are currently waiting for an adoptive placement. Olberg et al. (2021) study the economic effects of two search approaches that adoption agencies use to match children with prospective parents, family-driven search and caseworker-driven search. They introduce a search-and-matching model with different exogenous parameters, subject the model to a game-theoretic analysis and evaluate it numerically. In this thesis, I address the fact that in the work of Olberg et al. (2021) the parameters for the numerical evaluation of the model are arbitrarily chosen and it remains unclear, how realistic the chosen parameters are. Using data from the adoption market, I estimate the different parameters of the model and thereby provide an empirical foundation for the numerical evaluation. Furthermore, the theoretical and numerical results of Olberg et al. (2021) have not yet been empirically tested. Using a difference-in-differences estimator, I study the effect of a switch from family-driven search to caseworker-driven search that occurred in four Florida counties in 2018. While Olberg et al. (2021) identify various advantages of caseworker-driven search over family-driven search, I estimate the effect of caseworker-driven search to be negative. |
|
Tim Ehrensperger, Revenue Implications of Single Software Subscriptions, University of Zurich, Faculty of Business, Economics and Informatics, 2021. (Bachelor's Thesis)
This thesis investigates the revenue potential of different pricing strategies for a single software distribution. The game-theoretic model presented is tailor-made to analyze software revenue in the domain of consumer software such as video games. A publisher is maximizing his expected revenue in a system with many different user types, each of them responding optimally to the publishers' pricing strategy. The publisher has three choices, to offer perpetual licenses only, subscription licenses only, or both. To attract more users, the publisher can adjust prices over time. The users' equilibrium strategies for this Markov Decision Process are found through backward induction. The publisher's revenue is searched via differential evolution. Numerical analysis finds that although many publishers in practice only provide perpetual licenses, by offering a subscription option they can increase revenue significantly. Revenue can be raised again if both options are offered in parallel. In this last setting, the majority of revenue is attributed to selling subscription licenses. |
|
Vitor Bosshard, Sven Seuken, The Cost of Simple Bidding in Combinatorial Auctions, In: The 22nd ACM Conference on Economics and Computation, Proceedings of the 22nd ACM Conference on Economics and Computation, 2021. (Conference or Workshop Paper published in Proceedings)
We study a class of manipulations in combinatorial auctions where bidders fundamentally misrepresent what goods they are interested in. Prior work has largely assumed that bidders only submit bids on their bundles of interest, which we call simple bidding: strategizing over the bid amounts, but not the bundle identities. However, we show that there exists an entire class of auction instances for which simple bids are never optimal in BNE, always being strictly dominated by complex bids (where bidders bid on goods they are not interested in). We show this result for the two most widely used auction mechanisms: first price and VCG-nearest. We also explore the structural properties of the winner determination problem that cause this phenomenon, and we use the insights gained to investigate how impactful complex bidding manipulations may be. We find that, in the worst case, a bidder’s optimal complex bid may require bidding on an exponential number of bundles, even if the bidder is interested only in a single good. Thus, this phenomenon can greatly impact the auction’s outcome, and should not be ignored by bidders and auction designers alike. |
|
Ludwig Dierks, Sven Seuken, Ian Kash, On the cluster admission problem for cloud computing, Journal of Artificial Intelligence Research, 2021. (Journal Article)
|
|
Marius Högger, Bayesian Optimization with Uncertainty Bounds for Neural Networks, University of Zurich, Faculty of Business, Economics and Informatics, 2021. (Master's Thesis)
This thesis studies the application of neural networks (NNs) as estimators in Bayesian optimization and assesses if and how they can overcome this curse of dimensionality. Since quantifying the uncertainty of predictions is key in Bayesian optimization, several methods of representing predictive uncertainty for NNs are considered. Specifically, this thesis compares a very recent approach introduced by Heiss et al. (2021) called "neural optimization-based model uncertainty" (NOMU), against "Deep Ensembles" and "MC Dropout", two more established NN-based methods, and Gaussian processes. Experimental evaluations on synthetic data confirm that Gaussian processes outperform the NN-based methods in low dimensional settings (1D-2D) and show that NOMU performs as good or better than the other NN-based methods. However, the experiments in higher dimensions suggest that the NN-based methods improve and finally manage to outperform Gaussian processes with standard configurations. Furthermore, the results indicate that especially in higher dimensions, NOMU performs robustly as good or better than the other NN-based methods. |
|
Ludwig Dierks, Sven Seuken, The Competitive Effects of Variance-based Pricing, In: Proceedings of the 29th International Joint Conference on Artificial Intelligence, Yokohama, Japan, 2021. (Conference or Workshop Paper published in Proceedings)
In many markets, like electricity or cloud computing markets, providers incur large costs for keeping sufficient capacity in reserve to accommodate demand fluctuations of a mostly fixed user base. These costs are significantly affected by the unpredictability of the users' demand. Nevertheless, standard mechanisms charge fixed per-unit prices that do not depend on the variability of the users' demand. In this paper, we study a variance-based pricing rule in a two-provider market setting and perform a game-theoretic analysis of the resulting competitive effects. We show that an innovative provider who employs variance-based pricing can choose a pricing strategy that guarantees himself a higher profit than using fixed per-unit prices for any individually rational response of a provider playing a fixed pricing strategy. We then characterize all equilibria for the setting where both providers use variance-based pricing strategies. We show that, in equilibrium, the providers' profits may increase or decrease, depending on their cost functions. However, social welfare always weakly increases. |
|
Sven Seuken, Timo Mennle, Partial strategyproofness: Relaxing strategyproofness for the random assignment problem, Journal of Economic Theory, Vol. 191, 2021. (Journal Article)
We present partial strategyproofness, a new, relaxed notion of strategyproofness for studying the incentive properties of non-strategyproof assignment mechanisms. Informally, a mechanism is partially strategyproof if it makes truthful reporting a dominant strategy for those agents whose preference intensities differ sufficiently between any two objects. We demonstrate that partial strategyproofness is axiomatically motivated and yields a parametric measure for “how strategyproof” an assignment mechanism is. We apply this new concept to derive novel insights about the incentive properties of the probabilistic serial mechanism and different variants of the Boston mechanism. |
|
Vitor Bosshard, Benedikt Bünz, Benjamin Lubin, Sven Seuken, Computing bayes-nash equilibria in combinatorial auctions with verification, Journal of Artificial Intelligence Research, Vol. 69, 2020. (Journal Article)
We present a new algorithm for computing pure-strategy ε-Bayes-Nash equilibria (ε-BNEs) in combinatorial auctions. The main innovation of our algorithm is to separate the algorithm’s search phase (for finding the ε-BNE) from the verification phase (for computing the ε). Using this approach, we obtain an algorithm that is both very fast and provides theoretical guarantees on the ε it finds. Our main contribution is a verification method which, surprisingly, allows us to upper bound the ε across the whole continuous value space without making assumptions about the mechanism. Using our algorithm, we can now compute ε-BNEs in multi-minded domains that are significantly more complex than what was previously possible to solve. We release our code under an open-source license to enable researchers to perform algorithmic analyses of auctions, to enable bidders to analyze different strategies, and many other applications. |
|
Steffen Schuldenzucker, Sven Seuken, Stefano Battiston, Default Ambiguity: Credit Default Swaps Create New Systemic Risks in Financial Networks, Management Science, Vol. 66 (5), 2020. (Journal Article)
We study financial networks and reveal a new kind of systemic risk arising from what we call default ambiguity — that is, a situation where it is impossible to decide which banks are in default. Specifically, we study the clearing problem: given a network of banks interconnected by financial contracts, determine which banks are in default and what percentage of their liabilities they can pay. Prior work has shown that when banks can only enter into debt contracts with each other, this problem always has a unique maximal solution. We first prove that when banks can also enter into credit default swaps (CDSs), the clearing problem may have no solution or multiple conflicting solutions, thus leading to default ambiguity. We then derive sufficient conditions on the network structure to eliminate these issues. Finally, we discuss policy implications for the CDS market. |
|
Jakob Weissteiner, Sven Seuken, Deep Learning-powered Iterative Combinatorial Auctions, In: Proceedings of the 34th AAAI Conference of Artificial Intelligence, AAAI, 2020-02-07. (Conference or Workshop Paper published in Proceedings)
In this paper, we study the design of deep learning-powered iterative combinatorial auctions (ICAs). We build on prior work where preference elicitation was done via kernelized support vector regressions (SVRs). However, the SVR-based approach has limitations because it requires solving a machine learning (ML)-based winner determination problem (WDP). With expressive kernels (like gaussians), the ML-based WDP cannot be solved for large domains. While linear or quadratic kernels have better computational scalability, these kernels have limited expressiveness. In this work, we address these shortcomings by using deep neural networks (DNNs) instead of SVRs. We first show how the DNN-based WDP can be reformulated into a mixed integer program (MIP). Second, we experimentally compare the prediction performance of DNNs against SVRs. Third, we present experimental evaluations in two medium-sized domains which show that even ICAs based on relatively small-sized DNNs lead to higher economic efficiency than ICAs based on kernelized SVRs. Finally, we show that our DNN-powered ICA also scales well to very large CA domains. |
|