Contributions published at Computation and Economics (Sven Seuken)

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.

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.

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.

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.

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.

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.

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.

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.

null

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.

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.

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.

null

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.

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.

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.

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.

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.

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.