Equilibrium problems in Bayesian auction games can be described as systems of differential equations. Depending on the model assumptions, these equations might be such that we do not have a rigorous mathematical solution theory. The lack of analytical or numerical techniques with guaranteed convergence for the equilibrium problem has plagued the field and limited equilibrium analysis to rather simple auction models such as single-object auctions. Recent advances in equilibrium learning led to algorithms that find equilibrium under a wide variety of model assumptions. Monotonicity and the Minty condition are the known sufficient conditions for learning algorithms to converge to an equilibrium in games. Not much is known about convergence of learning algorithms beyond these conditions. We analyze first- and second-price auctions where simple learning algorithms consistently converge to an equilibrium. The analysis is challenging, because these properties need to be shown in infinite dimensions. Interestingly, we show that neither monotonicity nor pseudo- or quasi-monotonicity holds for the respective variational inequalities (VIs). The second-price auction's equilibrium is a Minty-type solution, but the first-price auction is not. However, the analysis via infinite-dimensional VIs allows us to get ex-post guarantees for gradient-based algorithms. We show that the Bayes--Nash equilibrium is the unique solution to the VI within the class of uniformly increasing bid functions, which ensures that gradient-based algorithms attain the equilibrium in case of convergence, as also observed in numerical experiments.

Projected gradient ascent is known to satisfy no-external regret as a learning algorithm. However, recent empirical work shows that projected gradient ascent often finds the Nash equilibrium in settings beyond two-player zero-sum interactions or potential games, including those where the set of coarse correlated equilibria is very large. We show that gradient ascent in fact satisfies a stronger class of linear Φ-regret in normal-form games; resulting in a refined solution concept which we dub semicoarse correlated equilibria. Our theoretical analysis of the discretised Bertrand competition mirrors those recently established for mean-based learning in first-price auctions. With at least two firms of lowest marginal cost, Nash equilibria emerge as the only semicoarse equilibria under concavity conditions on firm profits. In first-price auctions, the granularity of the bid space affects semicoarse equilibria, but finer granularity for lower bids also induces convergence to Nash equilibria. Unlike previous work that aims to prove convergence to a Nash equilibrium that often relies on epoch based analysis and probability theoretic machinery, our LP-based duality approach enables a simple and tractable analysis of equilibrium selection under gradient-based learning.

We study the Bayesian coarse correlated equilibrium (BCCE) of continuous and discretised first-price and all-pay auctions under the standard symmetric independent private-values model. Our goal is to determine how the canonical Bayes-Nash equilibrium (BNE) of the auction relates to the outcome when all buyers bid following no-regret algorithms. Numerical experiments show that in two buyer first-price auctions the Wasserstein-2 distance of buyers’ marginal bid distributions decline as O (1/n ) in the discretisation size in instances where the prior distribution is concave, whereas all-pay auctions exhibit similar behaviour without prior dependence. To explain this convergence to a near-equilibrium, we study uniqueness of the BCCE of the continuous auction, resulting in proofs of convergence of deterministic self-play to a near equilibrium outcome in these auctions. In the all-pay auction, we show that independent of the prior distribution there is a unique BCCE with symmetric, differentiable, and increasing bidding strategies, which is equivalent to the unique strict BNE. In the first-price auction, either the prior is strictly concave or the learning algorithm has to be restricted to strictly increasing strategies. Without such strong assumptions, no-regret algorithms can end up in low-price pooling strategies.

Game theory relies heavily on the availability of cardinal utility functions, but in fields such as matching markets, only ordinal preferences are typically elicited. The literature focuses on mechanisms with simple dominant strategies, but many real-world applications lack dominant strategies, making the intensity of preferences between outcomes important for determining strategies. Even though precise information about cardinal utilities is not available, some data about the likelihood of utility functions is often accessible. We propose to use Bayesian games to formalize uncertainty about the decision-makers' utilities by viewing them as a collection of normal-form games. Instead of searching for the Bayes-Nash equilibrium, we study how uncertainty in utilities is reflected in uncertainty of strategic play. To do this, we introduce a novel solution concept called α-Rank-collections, which extends α-Rank to Bayesian games. This allows us to analyze strategic play in, for example, non-strategyproof matching markets, for which appropriate solution concepts are currently lacking. α-Rank-collections characterize the expected probability of encountering a certain strategy profile under replicator dynamics in the long run, rather than predicting a specific equilibrium strategy profile. We experimentally evaluate α-Rank-collections using instances of the Boston mechanism, finding that our solution concept provides more nuanced predictions compared to Bayes-Nash equilibria. Additionally, we prove that α-Rank-collections are invariant to positive affine transformations, a standard property for a solution concept, and are efficient to approximate. By extending the α-Rank framework to account for Bayesian games, we provide a robust tool for analyzing strategic interactions in environments where uncertainty in preferences plays a critical role. This method offers a significant improvement in understanding and predicting strategic behaviors in various applications beyond matching markets, highlighting the versatility and efficiency of α-Rank-collections. Our approach opens new avenues for exploring complex strategic scenarios and provides a comprehensive framework for future research in game theory and economic computation. The full version of the paper can be found here https://arxiv.org/abs/2211.10317.

Understanding and analyzing markets is crucial, yet analytical equilibrium solutions remain largely infeasible. Recent breakthroughs in equilibrium computation rely on zeroth-order policy gradient estimation. These approaches commonly suffer from high variance and are computationally expensive. The use of fully differentiable simulators would enable more efficient gradient estimation. However, the discrete allocation of goods in economic simulations is a non-differentiable operation. This renders the first-order Monte Carlo gradient estimator inapplicable and the learning feedback systematically misleading. We propose a novel smoothing technique that creates a surrogate market game, in which first-order methods can be applied. We provide theoretical bounds on the resulting bias which justifies solving the smoothed game instead. These bounds also allow choosing the smoothing strength a priori such that the resulting estimate has low variance. Furthermore, we validate our approach via numerous empirical experiments. Our method theoretically and empirically outperforms zeroth-order methods in approximation quality and computational efficiency.

According to the fundamental theorems of welfare economics, any competitive equilibrium is Pareto efficient. Unfortunately, competitive equilibrium prices only exist under strong assumptions such as perfectly divisible goods and convex preferences. In many real-world markets, participants have non-convex preferences and the allocation problem needs to consider complex constraints. Electricity markets are a prime example, but similar problems appear in many real-world markets, which has led to a growing literature in market design.

Numerous games studied in microeconomic theory, such as auctions and contests, are modeled as Bayesian games with continuous type and action spaces. However, explicit solutions in the form of Bayes-Nash equilibria for such games are only known under highly specific assumptions regarding the agents' prior distributions or utility functions. Given the continuous nature of these games, existing equilibrium solvers cannot be straightforwardly applied and necessitate an additional discretization step.

Computing Bayesian Nash equilibrium strategies in auction games is a challenging problem that is not well-understood. Such equilibria can be modeled as systems of nonlinear partial differential equations. It was recently shown that neural pseudogradient ascent (NPGA), an implementation of simultaneous gradient ascent via neural networks, converges to a Bayesian Nash equilibrium for a wide variety of symmetric auction games. Whereas symmetric auction models are widespread in the theoretical literature, in most auction markets in the field, one can observe different classes of bidders having different valuation distributions and strategies. Asymmetry of this sort is almost always an issue in real-world multiobject auctions, in which different bidders are interested in different packages of items. Such environments require a different implementation of NPGA with multiple interacting neural networks having multiple outputs for the different allocations in which the bidders are interested. In this paper, we analyze a wide variety of asymmetric auction models. Interestingly, our results show that we closely approximate Bayesian Nash equilibria in all models in which the analytical Bayes–Nash equilibrium is known. Additionally, we analyze new and larger environments for which no analytical solution is known and verify that the solution found approximates equilibrium closely. The results provide a foundation for generic equilibrium solvers that can be used in a wide range of auction games. History: Accepted by Ram Ramesh, Area Editor for Data Science & Machine Learning. Funding: This work was supported by Deutsche Forschungsgemeinschaft [Grant BI-1056/I-9]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.1281 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0151 ) at ( http://dx.doi.org/10.5281/zenodo.7407158 ).

We study markets where a set of indivisible items is sold to bidders with unit-demand valuations, subject to a hard budget limit. Without financial constraints and pure quasilinear bidders, this assignment model allows for a simple ascending auction format that maximizes welfare and is incentive-compatible and core-stable. Introducing budget constraints, the ascending auction requires strong additional conditions on the unit-demand preferences to maintain its properties. We show that, without these conditions, we cannot hope for an incentive-compatible and core-stable mechanism. We design an iterative algorithm that depends solely on a trivially verifiable ex-post condition and demand queries, and with appropriate decisions made by an auctioneer, always yields a welfare-maximizing and core-stable outcome. If these conditions do not hold, we cannot hope for incentive-compatibility and computing welfare-maximizing assignments and core-stable prices is hard: Even in the presence of value queries, where bidders reveal their valuations and budgets truthfully, we prove that the problem becomes NP-complete for the assignment market model. The analysis complements complexity results for markets with more complex valuations and shows that even with simple unit-demand bidders the problem becomes intractable. This raises doubts on the efficiency of simple auction designs as they are used in high-stakes markets, where budget constraints typically play a role.

Nowadays corporate data centers leverage virtualization technology to cut operational and management costs. Virtualization allows splitting and assigning physical servers to virtual machines (VM) that run particular business applications. This has led to a new stream in the capacity planning literature dealing with the problem of assigning VMs with volatile demands to physical servers in a static way such that energy costs are minimized. Live migration technology allows for dynamic resource allocation, where a controller responds to overload or underload on a server during runtime and reallocates VMs in order to maximize energy efficiency. Dynamic resource allocation is often seen as the most efficient means to allocate hardware resources in a data center. Unfortunately, there is hardly any experimental evidence for this claim. In this paper, we provide the results of an extensive experimental analysis of both capacity management approaches on a data center infrastructure. We show that with typical workloads of transactional business applications dynamic resource allocation does not increase energy efficiency over the static allocation of VMs to servers and can even come at a cost, because migrations lead to overheads and service disruptions.

Running emerging main-memory database systems within virtual machines causes huge overhead, because these systems are highly optimized to get the most out of bare metal servers. But running these systems on bare metal servers results in low resource utilization, because database servers often have to be sized for peak loads, much higher than the average load. Instead, we propose to deploy them within light-weight containers that allow to control resource usage and to make use of spare resources by temporarily running other applications on the database server using virtual machines (VMs). The servers on which these VMs would normally run can be suspended, to save energy costs. But current database systems do not handle dynamic changes to resource allocation well and accurate estimates on resource demand are required to maintain SLAs. We focus on emerging main-memory database systems that support the mixed workloads of today's business intelligence applications and propose an cooperative approach in which the DBMS communicates its resource demand, gets informed about currently assigned resources and adapts its resource usage accordingly. We analyze the performance impact on the database system when spare resources are used by VMs and monitor SLA compliance.

Combinatorial auctions have been suggested as a mean to raise efficiency in multi-item negotiations with complementarities as they can be found in procurement, in energy markets, in transportation, and for the sale of spectrum auctions. Anonymous linear ask prices are desirable and sometimes even essential for many of these applications. The Combinatorial Clock (CC) auction [4] has become very popular in these markets for its simplicity and as it "produces highly usable price discovery, because of the item prices (linear pricing)" [1]. Unfortunately, the CC auction fails to lead always to efficient outcomes, and there is no theory on equilibrium bidding strategies in such auctions. Given the importance of the CC auction in the field, it is desirable to better understand this auction format.

Today's data centers offer IT services mostly hosted on dedicated physical servers. Server virtualization provides a technical means for server consolidation. Thus, multiple virtual servers can be hosted on a single server. Server consolidation describes the process of combining the workloads of several different servers on a set of target servers. We focus on server consolidation with dozens or hundreds of servers, which can be regularly found in enterprise data centers. Cost saving is among the key drivers for such projects. This paper presents decision models to optimally allocate source servers to physical target servers while considering real-world constraints. Our central model is proven to be an NP-hard problem. Therefore, besides an exact solution method, a heuristic is presented to address large-scale server consolidation projects. In addition, a preprocessing method for server load data is introduced allowing for the consideration of quality-of-service levels. Extensive experiments were conducted based on a large set of server load data from a data center provider focusing on managerial concerns over what types of problems can be solved. Results show that, on average, server savings of 31 percent can be achieved only by taking cycles in the server workload into account.

Electronic auction markets collect large amounts of auction field data. This enables a structural estimation of the bid distributions and the possibility to derive optimal reserve prices. In this paper we propose a new approach to setting reserve prices. In contrast to traditional auction theory we use the buyer's risk statement for getting a winning bid as a key criterion to set an optimal reserve price. The reserve price for a given probability can then be derived from the distribution function of the observed drop-out bids. In order to get an accurate model of this function, we propose a nonparametric technique based on kernel distribution function estimators and the use of order statistics. We improve our estimatior by additional information, which can be observed about bidders and qualitative differences of goods in past auctions rounds (e.g. different delivery times). This makes the technique applicable to RFQs and multi-attribute auctions, with qualitatively differentiated offers.

Distributed object standards provide a key to building interoperable applications that can run on a range of platforms. The paper describes a CORBA-based research prototype for an electronic broker in business-to-business electronic commerce. High-level IDL specifications are used to achieve interoperability between components of the electronic marketplace. The two key functionalities of the electronic broker are the ability to dynamically gather information from remote electronic catalogs and the support for negotiations through auction mechanisms. The paper discusses the functionality and the design of the electronic broker and gives an overview of current extensions of the prototype. As application-level interoperability is a crucial precondition for many brokerage services, we put special emphasis on electronic commerce protocol standards.