We present an algorithm for computing pure-strategy epsilon-perfect Bayesian equilibria in sequential auctions with continuous action and value spaces. Importantly, our algorithm includes a verification phase that computes an upper bound on the utility loss of the found strategies. Prior work on equilibrium computation in auctions with verification has focussed on the single-round case, but the methods do not work for sequential auctions because of two main challenges: (1) there are infinitely many subgames, and (2) the setting has no optimal substructure as bidders' beliefs and best response strategies depend on the strategies of previous rounds. We make two contributions. First, we introduce a tailor-made game abstraction that discretizes the auction and augments the state space with the public beliefs, such that an approximate equilibrium can be computed via dynamic programming. Second, we prove a decomposition theorem to upper bound the utility loss of the computed equilibrium. This is essential because it is neither guaranteed that the auction has an equilibrium nor that any algorithm converges to it. We validate our algorithm on multiple settings with known equilibria and apply it to a new multi-round combinatorial auction.

We study the design of *iterative combinatorial auctions (ICAs)*. The main challenge in this domain is that the bundle space grows exponentially in the number of items. To address this, recent work has proposed machine learning (ML)-based preference elicitation algorithms that aim to elicit only the most critical information from bidders to maximize efficiency. However, while the SOTA ML-based algorithms elicit bidders' preferences via *value queries*, ICAs that are used in practice elicit information via *demand queries*. In this paper, we introduce a novel ML algorithm that provably makes use of the full information from both value and demand queries, and we show via experiments that combining both query types results in significantly better learning performance in practice. Building on these insights, we present MLHCA, a new ML-powered auction that uses value and demand queries. MLHCA significantly outperforms the previous SOTA, reducing efficiency loss by up to a factor 10, with up to 58% fewer queries. Thus, MLHCA achieves large efficiency improvements while also reducing bidders' cognitive load, establishing a new benchmark for both practicability and efficiency. Our code is available at https://github.com/marketdesignresearch/MLHCA.

The next frontier of online advertising is revenue generation from LLM-generated content. We consider a setting where advertisers aim to influence the responses of an LLM, while platforms seek to maximize advertiser value and ensure user satisfaction. The challenge is that advertisers' preferences generally conflict with those of the user, and advertisers may misreport their preferences. To address this, we introduce MOSAIC, an auction mechanism that ensures that truthful reporting is a dominant strategy for advertisers and that aligns the utility of each advertiser with their contribution to social welfare. Importantly, the mechanism operates without LLM fine-tuning or access to model weights and provably converges to the output of the optimally fine-tuned LLM as computational resources increase. Additionally, it can incorporate contextual information about advertisers, which significantly improves social welfare. Via experiments with publicly available LLMs, we show that MOSAIC leads to high advertiser value and platform revenue with low computational costs. While our motivating application is online advertising, our mechanism can be applied in any setting with monetary transfers, making it a general-purpose solution for truthfully aggregating the preferences of self-interested agents over LLM-generated replies.

Dynamic mechanism design is a challenging extension to ordinary mechanism design in which the mechanism designer must make a sequence of decisions over time in the face of possibly untruthful reports of participating agents. Optimizing dynamic mechanisms for welfare is relatively well understood. However, there has been less work on optimizing for other goals (e.g., revenue), and without restrictive assumptions on valuations, it is remarkably challenging to characterize good mechanisms. Instead, we turn to automated mechanism design to find mechanisms with good performance in specific problem instances. We extend the class of affine maximizer mechanisms to MDPs where agents may untruthfully report their rewards. This extension results in a challenging bilevel optimization problem in which the upper problem involves choosing optimal mechanism parameters, and the lower problem involves solving the resulting MDP. Our approach can find truthful dynamic mechanisms that achieve strong performance on goals other than welfare, and can be applied to essentially any problem setting---without restrictions on valuations---for which RL can learn optimal policies.

We study the design of iterative combinatorial auctions (ICAs). 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 (ML)-based preference elicitation algorithms that aim to elicit only the most important information from bidders. However, from a practical point of view, the main shortcoming of this prior work is that those designs elicit bidders' preferences via value queries (i.e., “What is your value for the bundle {A, B}?''). In most real-world ICA domains, value queries are considered impractical, since they impose an unrealistically high cognitive burden on bidders, which is why they are not used in practice. In this paper, we address this shortcoming by designing an ML-powered combinatorial clock auction that elicits information from the bidders only via demand queries (i.e., “At prices p, what is your most preferred bundle of items?''). We make two key technical contributions: First, we present a novel method for training an ML model on demand queries. Second, based on those trained ML models, we introduce an efficient method for determining the demand query with the highest clearing potential, for which we also provide a theoretical foundation. We experimentally evaluate our ML-based demand query mechanism in several spectrum auction domains and compare it against the most established real-world ICA: the combinatorial clock auction (CCA). Our mechanism significantly outperforms the CCA in terms of efficiency in all domains, it achieves higher efficiency in a significantly reduced number of rounds, and, using linear prices, it exhibits vastly higher clearing potential. Thus, with this paper we bridge the gap between research and practice and propose the first practical ML-powered ICA.

We study the course allocation problem, where universities assign course schedules to students. The current state-of-the-art mechanism, Course Match, has one major shortcoming: students make significant mistakes when reporting their preferences, which negatively affects welfare and fairness. To address this issue, we introduce a new mechanism, Machine Learning-powered Course Match (MLCM). At the core of MLCM is a machine learning-powered preference elicitation module that iteratively asks personalized pairwise comparison queries to alleviate students' reporting mistakes. Extensive computational experiments, grounded in real-world data, demonstrate that MLCM, with only ten comparison queries, significantly increases both average and minimum student utility by 7%--11% and 17%--29%, respectively. Finally, we highlight MLCM's robustness to changes in the environment and show how our design minimizes the risk of upgrading to MLCM while making the upgrade process simple for universities and seamless for their students.

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 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.

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.

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 the design of iterative combinatorial auctions for domains with a large number of items. In such domains, preference elicitation is a major challenge because the bundle space grows exponentially in the number of items. To keep preference elicitation manageable, recent work has employed machine learning (ML) algorithms that identify a small set of bundles to query from each bidder. However, a major limitation of this prior work is that bidders must submit exact values for the queried bundles, which can be quite costly for them. To address this, we propose iMLCA, a new ML-powered auction with interval bidding (i.e., where bidders submit upper and lower bounds for the queried bundles). To steer the auction towards an efficient allocation, we introduce a new price-based activity rule, asking bidders to tighten bounds on relevant bundles only. The activity rule is designed such that the auctioneer receives enough information about bidders' preferences to achieve high efficiency and good incentives, while minimizing elicitation costs. Our experiments show that iMLCA, despite only eliciting interval bids, achieves almost the same allocative efficiency as the prior auction design that required bidders to submit exact values. Finally, we show that iMLCA beats the well-known combinatorial clock auction in a realistically-sized domain.

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 andVCG-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.

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.

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 study portfolio compression, a procedure that removes cycles of liabilities in a financial network. We analyze the incentives for banks to engage in compression and its systemic effects in terms of all banks' equities. We show that, contrary to conventional wisdom, portfolio compression may be socially and individually detrimental and banks' incentives may be misaligned with social welfare. We then present sufficient conditions under which banks involved in the compression have an incentive to agree to it or under which the compression is even a Pareto improvement for all banks. Our results contribute to a better understanding of the implications of recent regulatory policy.

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.

Iterative combinatorial auctions (CAs) are often used in multibillion dollar domains like spectrum auctions, and speed of convergence is one of the crucial factors behind the choice of a specific design for practical applications. To achieve fast convergence, current CAs require careful tuning of the price update rule to balance convergence speed and allocative efficiency. Brero and Lahaie (2018) recently introduced a Bayesian iterative auction design for settings with singleminded bidders. The Bayesian approach allowed them to incorporate prior knowledge into the price update algorithm, reducing the number of rounds to convergence with minimal parameter tuning. In this paper, we generalize their work to settings with no restrictions on bidder valuations. We introduce a new Bayesian CA design for this general setting which uses Monte Carlo Expectation Maximization to update prices at each round of the auction. We evaluate our approach via simulations on CATS instances. Our results show that our Bayesian CA outperforms even a highly optimized benchmark in terms of clearing percentage and convergence speed.

Combinatorial auctions are used to allocate resources in domains where bidders have complex preferences over bundles of goods. However, the behavior of bidders under different payment rules is not well understood, and there has been limited success in finding Bayes-Nash equilibria of such auctions due to the computational difficulties involved. In this paper, we introduce non-decreasing payment rules. Under such a rule, the payment of a bidder cannot decrease when he increases his bid, which is a natural and desirable property. VCG-nearest, the payment rule most commonly used in practice, violates this property and can thus be manipulated in surprising ways. In contrast, we show that many other payment rules are non-decreasing. We also show that a non-decreasing payment rule imposes a structure on the auction game that enables us to search for an approximate Bayes-Nash equilibrium much more efficiently than in the general case. Finally, we introduce the utility planes BNE algorithm, which exploits this structure and outperforms a state-of-the-art algorithm by multiple orders of magnitude.

Combinatorial auctions (CAs) are used to allocate multiple items among bidders with complex valuations. Since the value space grows exponentially in the number of items, it is impossible for bidders to report their full value function even in medium-sized settings. Prior work has shown that current designs often fail to elicit the most relevant values of the bidders, thus leading to inefficiencies. We address this problem by introducing a machine learning-based elicitation algorithm to identify which values to query from the bidders. Based on this elicitation paradigm we design a new CA mechanism we call PVM, where payments are determined so that bidders’ incentives are aligned with allocative efficiency. We validate PVM experimentally in several spectrum auction domains, and we show that it achieves high allocative efficiency even when only few values are elicited from the bidders.

We study the design of core-selecting payment rules for combinatorial auctions (CAs), a challenging setting where no strategyproof rules exist. Unfortunately, under the rule most commonly used in practice, the Quadratic rule (Day and Cramton, 2012), the Bayes-Nash equilibrium strategies are untruthful enough such that truthful play may be an implausible model of bidder behavior, which also raises concerns about revenue and efficiency. In this paper, we present a computational approach for finding good core-selecting payment rules. We present a parametrized payment rule we call Fractional* that takes three parameters (reference point, weights, and amplification) as inputs. This way, we construct and analyze 366 rules across 29 different domains. To evaluate each rule in each domain, we employ a computational Bayes-Nash equilibrium solver. We first use our approach to study the well-known Local-Local Global domain in detail, and identify a set of 20 "all-rounder rules" which beat Quadratic by a significant margin on efficiency, incentives, and revenue in all, or almost all domains. To demonstrate robustness of our findings,we take four of these all-rounder rules and evaluate them in the significantly larger LLLLGG domain (with six bidders and eight goods), where we show that all four rules also beat Quadratic. This suggests that, in practice, auctioneers may want to consider using alternative core-selecting payment rules because of the large improvements over Quadratic that may be available. Overall, our results demonstrate the power of a computational search approach in a properly parametrized mechanism design space.

We investigate the class of school choice mechanisms that are first-choice maximal (FCM) (i.e., they match a maximal number of students to their reported first choices) and first-choice stable (FCS) (i.e., no students form blocking pairs with their reported first choices). FCM is a ubiquitous desideratum in school choice, and we show that FCS is the only rank-based relaxation of stability that is compatible with FCM. The class of FCM and FCS mechanisms includes variants of the well-known Boston mechanism as well as certain Asymmetric Chinese Parallel mechanisms. Regarding incentives, we show that while no mechanism in this class is strategyproof, the Pareto efficient ones are least susceptible to manipulation. Regarding student welfare, we show that the Nash equilibrium outcomes of these mechanisms correspond precisely to the set of stable matchings. By contrast, when some students are sincere, we show that more students may be matched to their true first choices in equilibrium than under any stable matching. Finally, we show how our results can be used to obtain a new characterization of the Boston mechanism (i.e., the most widely used FCM and FCS mechanism). On a technical level, this paper provides new insights about an influential class of school choice mechanisms. For practical market design, our results yield a potential rationale for the popularity of FCM and FCS mechanisms in practice.

The World Wide Web is a massive network of interlinked documents. One of the reasons the World Wide Web is so successful is the fact that most content is available free of any charge. Inspired by the success of the World Wide Web, the Web of Data applies the same strategy of interlinking to data. To this point, most of data in the Web of Data is also free of charge. The fact that the data is freely available raises the question of financing these services, however. As we will discuss in this paper, advertisement and donations cannot easily be applied to this new setting. To create incentives to subsidize data providers, we propose that sponsors should pay the providers to promote sponsored data. In return, sponsored data will be privileged over non-sponsored data. Since it is not possible to enforce a certain ordering on the data the user will receive, we propose to split up the data into different batches and deliver these batches with different delays. In this way, we can privilege sponsored data without withholding any non-sponsored data from the user. In this paper, we introduce a new concept of a delayed-answer auction, where sponsors can pay to prioritize their data. We introduce a new model which captures the particular situation when a user access data in the Web of Data. We show how the weighted Vickrey-Clarke-Groves auction mechanism can be applied to our scenario and we discuss how certain parameters can influence the nature of our auction. With our new concept, we build a first step to a free yet financial sustainable Web of Data.

A well-known problem in combinatorial auctions (CAs) is that the value space grows exponentially in the number of goods, which often puts a large burden on the bidders and on the auctioneer. In this paper, we introduce a new design paradigm for CAs based on machine learning (ML). Bidders report their values (bids) to a proxy agent by answering a small number of value queries. The proxy agent then uses an ML algorithm to generalize from those bids to the whole value space, and the efficient allocation is computed based on the generalized valuations. We introduce the concept of "probably approximate efficiency (PAE)" to measure the efficiency of the new ML-based auctions, and we formally show how the generelizability of an ML algorithm relates to the efficiency loss incurred by the corresponding ML-based auction. To instantiate our paradigm, we use support vector regression (SVR) as our ML algorithm, which enables us to keep the winner determination problem of the CA tractable. Different parameters of the SVR algorithm allow us to trade off the expressiveness, economic efficiency, and computational efficiency of the CA. Finally, we demonstrate experimentally that, even with a small number of bids, our ML-based auctions are highly efficient with high probability.

Combinatorial auctions (CAs) are widely used in practice, which is why understanding their incentive properties is an important problem. However, finding Bayes-Nash equilibria (BNEs) of CAs analytically is tedious, and prior algorithmic work has only considered limited solution concepts (e.g. restricted action spaces). In this paper, we present a fast, general algorithm for computing symmetric pure ε-BNEs in CAs with continuous values and actions. In contrast to prior work, we separate the search phase (for finding the BNE) from the verification step (for estimating the ε), and always consider the full (continuous) action space in the best response computation. We evaluate our method in the well-studied LLG domain, against a benchmark of 16 CAs for which analytical BNEs are known. In all cases, our algorithm converges quickly, matching the known results with high precision. Furthermore, for CAs with quasi-linear utility functions and independently distributed valuations, we derive a theoretical bound on ε. Finally, we introduce the new Multi-Minded LLLLGG domain with eight goods and six bidders, and apply our algorithm to finding an equilibrium in this domain. Our algorithm is the first to find an accurate BNE in a CA of this size.

We consider the problem of clearing a system of interconnected banks that have been exposed to a shock on their assets. Eisenberg and Noe (2001) showed that when banks can only enter into simple debt contracts with each other, then a clearing vector of payments can be computed in polynomial time. In this paper, we show that the situation changes radically when banks can also enter into credit default swaps (CDSs), i.e., financial derivative contracts that depend on the default of another bank. We prove that computing an approximate solution to the clearing problem with sufficiently small constant error is PPAD-complete. To do this, we demonstrate how financial networks with debt and CDSs can encode arithmetic operations such as addition and multiplication. Our results have practical impact for network stress tests and reveal computational complexity as a new concern regarding the stability of the financial system.

Smart energy systems that leverage machine learning techniques are increasingly integrated in all aspects of our lives. To better understand how to design user interaction with such systems, we implemented three different smart thermostats that automate heating based on users' heating preferences and real-time price variations. We evaluated our designs through a field study, where 30 UK households used our thermostats to heat their homes over a month. Our findings through thematic analysis show that the participants formed different understandings and expectations of our smart thermostat, and used it in various ways to effectively respond to real-time prices while maintaining their thermal comfort. Based on the findings, we present a number of design and research implications, specifically for designing future smart thermostats that will assist us in controlling home heating with real-time pricing, and for future intelligent autonomous systems.

In many situations, a group of individuals (called "agents") must collectively decide on one of several alternatives, e.g., elect the next president. "Ordinal mechanisms" are systematic procedures to make such decisions based on the agents' preference orders over the alternatives. A mechanism is "strategyproof" if it makes truthful reporting of preferences a dominant strategy. Strategyproofness is therefore the gold standard among the incentive concepts. However, the seminal impossibility result of Gibbard [1977] showed that strategyproofness also greatly restricts the design space of ordinal mechanisms even if they can use randomization. In particular, it is incompatible with many other common desiderata, such as Condorcet consistency, stability, or egalitarian fairness. Thus, trade-offs between strategyproofness and other desiderata are necessary. In this paper, we study these trade-offs. We use approximate strategyproofness to define "manipulability," a measure to quantify the incentive properties of non-strategyproof mechanisms, and we introduce "deficit," a measure to quantify the performance of mechanisms with respect to another desideratum. A mechanism that minimizes the deficit subject to a particular bound on manipulability is called "optimal" at this bound; and the mechanisms that are optimal at some bound form the "Pareto frontier." Our main contribution is a structural characterization of this Pareto frontier: we show that there exists a finite set of "supporting manipulability bounds," such that it suffices to identify optimal mechanisms at each of them. Other mechanisms along the Pareto frontier can then be constructed as "hybrids" (i.e., convex combinations) of these optimal mechanisms.

We consider the problem of clearing a system of interconnected banks that have been exposed to a shock on their assets. Due to this shock, some of the banks may go into bankruptcy and default on their obligations towards other banks. Clearing means computing the payments to be made from each bank to each other bank in accordance with bankruptcy law. The design of good clearing mechanisms is challenging because of the complex and often cyclic interdependencies in realistic financial networks. Eisenberg and Noe (2001) showed that when banks can only enter into debt contracts with each other, then there always exists a unique Pareto efficient clearing payment vector and it can be computed in polynomial time. Rogers and Veraart (2013) extended this result to a setting where defaulting banks can only recover part of their assets.

Computing prices in core-selecting combinatorial auctions is a computationally hard problem. Auctions with many bids can only be solved using a recently proposed core constraint generation (CCG) algorithm, which may still take days on hard instances. In this paper, we present a new algorithm that significantly outperforms the current state of the art. Towards this end, we first provide an alternative definition of the set of core constraints, where each constraint is weakly stronger, and prove that together these constraints define the identical polytope to the previous definition. Using these new theoretical insights we develop two new algorithmic techniques which generate additional constraints in each iteration of the CCG algorithm by 1) exploiting separability in allocative conflicts between participants in the auction, and 2) by leveraging non-optimal solutions. We show experimentally that our new algorithm leads to significant speed-ups on a variety of large combinatorial auction problems. Our work provides new insights into the structure of core constraints and advances the state of the art in fast algorithms for computing core prices in large combinatorial auctions.

No abstract available.

Despite the pervasiveness of markets in our lives, little is known about the role of user interfaces (UIs) in promoting good decisions in market domains. How does the way we display market information to end users, and the set of choices we offer, influence users' decisions? In this paper, we introduce a new research agenda on "market user interface design." Our goal is to find the optimal market UI, taking into account that users incur cognitive costs and are boundedly rational. Via lab experiments we systematically explore the market UI design space, and we study the automatic optimization of market UIs given a behavioral (quantal response) model of user behavior. Surprisingly, we find that the behaviorally-optimized UI performs worse than the standard UI, suggesting that the quantal response model did not predict user behavior well. Subsequently, we identify important behavioral factors that are missing from the user model, including loss aversion and position effects, which motivates follow-up studies. Furthermore, we find significant differences between individual users in terms of rationality. This suggests future research on personalized UI designs, with interfaces that are tailored towards each individual user's needs, capabilities, and preferences.

The most prominent way to establish trust between buyers and sellers on online auction sites are reputation mechanisms. Two drawbacks of this approach are the reliance on the seller being long-lived and the susceptibility to whitewashing. In this paper, we introduce so-called escrow mechanisms that avoid these problems by installing a trusted intermediary which forwards the payment to the seller only if the buyer acknowledges that the good arrived in the promised condition. We address the incentive issues that arise and design an escrow mechanism that is incentive-compatible, efficient, interim individually rational and ex ante budget-balanced. In contrast to previous work on trust and reputation, our approach does not rely on knowing the sellers' cost functions or the distribution of buyer valuations.

The next decade will see an abundance of new intelligent systems, many of which will be market-based. Soon, users will interact with many new markets, perhaps without even knowing it: when driving their car, when listening to a song, when backing up their files, or when surfing the web. We argue that these new systems can only be successful if a new approach is chosen towards designing them. In this paper we introduce the general problem of "Hidden Market Design." The design of a "weakly hidden" market involves reducing some of the market complexities and providing a user interface (UI) that makes the interaction seamless for the user. A "strongly hidden market" is one where some semantic aspect of a market is hidden altogether (e.g., budgets, prices, combinatorial constraints). We show that the intersection of UI design and market design is of particular importance for this research agenda. To illustrate hidden market design, we give a series of potential applications. We hope that the problem of hidden market design will inspire other researchers and lead to new research in this direction, paving the way for more successful market-based systems in the future.

In distributed work systems, individual users perform work for other users. A significant challenge in these systems is to provide proper incentives for users to contribute as much work as they consume, even when monitoring is not possible. We formalize the problem of designing "incentive-compatible accounting mechanisms" that measure the net contributions of users, despite relying on voluntary reports. We introduce the Drop-Edge Mechanism that removes any incentive for a user to manipulate via misreports about work contributed or consumed. We prove that Drop-Edge provides a good approximation to a user's net contribution, and is accurate in the limit as the number of users grows. We demonstrate very good welfare properties in simulation compared to an existing, manipulable mechanism. In closing, we show the power of sybil attacks in accounting mechanisms and discuss our ongoing work, including a real-world implementation and evaluation of the Drop-Edge Mechanism in a BitTorrent client.

The Internet has allowed market-based systems to become increasingly pervasive. In this paper we explore the role of user interface (UI) design for these markets. Different UIs induce different mental models which in turn determine how users understand and interact with a market. Thus, the intersection of UI design and economics is a novel and important research area. We make three contributions at this intersection. First, we present a novel design paradigm which we call hidden markets. The primary goal of hidden markets is to hide as much of the market complexities as possible. Second, we explore this new design paradigm using one particular example: a P2P backup application. We explain the market underlying this system and provide a detailed description of the new UI we developed. Third, we present results from a formative usability study. Our findings indicate that a number of users could benefit from a market-based P2P backup system. Most users intuitively understood the give & take principle as well as the bundle constraints of the market. However, the pricing aspect was difficult to discover/understand for many users and thus needs further investigation. Overall, the results are encouraging and show promise for the hidden market paradigm.

In this paper we take the problem of a market-based P2P backup application and carry it through market design, to implementation, to theoretical and experimental analysis. While the long-term goal is an open market using real money, here we consider a system where monetary transfers are prohibited. We first describe the design of the P2P resource exchange market and the UI we developed. Second, we prove theorems on equilibrium existence and uniqueness. Third, we prove a surprising impossibility result regarding the limited controllability of the equilibrium and show how to address this. Fourth, we present a price update algorithm that uses daily supply and demand information to move prices towards the equilibrium and we provide a theoretical and experimental convergence analysis. The market design described in this paper is already implemented as part of a Microsoft research project on P2P backup systems and an alpha version of the software has been successfully tested.