Contributions published at Computation and Economics (Sven Seuken)

Combinatorial Auctions (CAs) allowing multiple items to be auctioned at the same time, have a wide variety of applications in the public sector. One of the main problems of CAs is that it is complex for a bidder to express his valuation of all possible bundles and recent literature has shown that this is a major cause of inefficiencies. To counter these inefficiencies Brero, Lubin and Seuken (2017) introduced a new machine learning-based CA design reducing bidding complexity significantly. This thesis focuses on further reducing bidding complexity by exploring two ideas: allowing a bidder to submit range bids with a lower- and upper-bound and to report preferences in the form of: "I prefer bundle s1 at price p1 over s2 at price p2". Experimental results show that allowing a bidder to submit range bids comes at the price of a small efficiency loss but also leads to a significant reduction of runtime. This computational advantage is an interesting result for applying the design in bigger auctions. The results suggest further, that allowing preferences in the form of: "I prefer bundle s1 at price p1 over s2 at price p2" leads to higher efficiency but at the price of a longer runtime.

null

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.

During the past decades, recommender systems have become a valuable tool for operators of e-commerce and information systems to reduce consumer choice overload. Traditional recommender techniques succeed in producing useful recommendations in many domains. However, recent research is investigating new recommender system designs for domains with complex constraints where traditional techniques fail to provide suitable recommendations. Those designs often employ complex models and depend upon an extensive data basis. In many cases such systems turn out to be impracticable due to scalability and usability concerns. The broad availability of social network information allows for new recommender system designs, where user networks are utilized to let friends recommend products to each other. By computationally supporting peers in social networks to apply their knowledge and cognitive capabilities, we can make use of human intelligence whose computational reproduction would be unfeasible. Based on these new possibilities, we present the paradigm of human-supported recommender systems, where the computational power of computers is combined with the abilities of humans to remedy shortcomings of previous systems. To evaluate this new paradigm, we compare a general purpose human-supported recommender system with a traditional system in the domain of course recommendations. Our experiment demonstrates that by applying this design, overall user satisfaction can be significantly improved. In addition, we gather experimental evidence that user satisfaction can not only be increased due to a gain in recommendation attractiveness, but also due to behavioral factors such as social influence and trust in the system. These findings demonstrate the potential of human-supported systems to generate recommendations for domains hitherto hard to administer, thus legitimizing further research in this field.

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. This allows a concise representation of the Pareto frontier in terms of a finite number of optimal mechanisms and their hybrids. In combination with linear programming, we can exploit this characterization to compute the whole Pareto frontier algorithmically. To illustrate its shape, we apply our results to determine the Pareto frontier for two different desiderata, namely Plurality and Veto scoring, in settings with 3 alternatives and up to 18 agents.

null

For the past 16 years, much of the work on combinatorial auctions (CAs) has used the CATS instance generator by Leyton-Brown_2000_CATS. While this test suite has been very beneficial to the community, it does not model spectrum auctions particularly well, which in recent years have become the most important application of CAs. We propose a novel value model that captures the important and difficult to model geographic complementaries of auctions such as the 2014 Canadian auction. Second, we introduce SATS, a new ìspectrum auction test suite,î providing a unified framework and code base for several of the spectrum auction models that have been proposed in the literature, as well as our new model. Third we show how SATS can be used to parametrize our new value model to represent a specific auction.

In some auction domains, there is uncertainty regarding the final availability of the goods being auctioned off. For example, a government may auction off spectrum from its public safety network, but it may need this spectrum back in times of emergency. In such a domain, standard combinatorial auctions perform poorly because they lead to violations of individual rationality (IR), even in expectation, and to very low efficiency. In this paper, we study the design of core-selecting payment rules for such domains. Surprisingly, we show that in this new domain, there does not exist a payment rule with is guaranteed to be ex-post core-selecting. However, we show that by designing rules that are "execution-contingent," i.e., by charging payments that are conditioned on the realization of the availability of the goods, we can reduce IR violations. We design two core-selecting rules that always satisfy IR in expectation. To study the performance of our rules we perform a computational Bayes-Nash equilibrium analysis. We show that, in equilibrium, our new rules have better incentives, higher efficiency, and a lower rate of ex-post IR violations than standard core-selecting rules.

In some auction domains, there is uncertainty regarding the final availability of the goods being auctioned off. For example, a government may auction off spectrum from its public safety network, but it may need this spectrum back in times of emergency. In such a domain, standard combinatorial auctions perform poorly because they lead to violations of individual rationality (IR), even in expectation, and to very low efficiency. In this paper, we study the design of core-selecting payment rules for such domains. Surprisingly, we show that in this new domain, there does not exist a payment rule with is guaranteed to be ex-post core-selecting. However, we show that by designing rules that are “execution-contingent,” i.e., by charging payments that are conditioned on the realization of the availability of the goods, we can reduce IR violations. We design two core-selecting rules that always satisfy IR in expectation. To study the performance of our rules we perform a computational Bayes-Nash equilibrium analysis. We show that, in equilibrium, our new rules have better incentives, higher efficiency, and a lower rate of ex-post IR violations than standard core-selecting rules.

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.

Since the early 1990s, recommender systems have found application in a variety of fields. This thesis presents the development of a hybrid recommender algorithm for CoRe, a web-based course recommendation system and study planning tool at the University of Zurich. In order to overcome the typical drawbacks that the previously deployed collaborative filtering algorithm suffered from, the hybrid algorithm combines a collaborative filtering algorithm with a content-based algorithm. An offline evaluation demonstrates that the combination of the two algorithms leads to a higher degree of rating prediction accuracy. Additionally, the collaborative filtering algorithm surpasses the performance of the content-based algorithm as greater numbers of ratings are added to the dataset. A user survey was conducted to find out whether this effect is reflected in the usefulness of the system as perceived by the students. While the results are not statistically significant, the data suggests that students perceive recommendations from the content-based algorithm as superior.

There are some things that money cannot buy. For various reasons, moral or otherwise, society has set boundaries regarding the use of money for certain resources and transactions. Such restrictions often arise in situations that are of great importance to people's lives: subsidized housing must be assigned to tenants, seats at public schools must be assigned to students, or a new president must be elected. The design of mechanisms for these problems is plagued by severe impossibility results pertaining to strategyproofness. In this thesis we address the research question of how to trade off strategyproofness and other desiderata in the design of ordinal mechanisms. For the assignment domain we introduce the new relaxed incentive concept of partial strategyproofness which can be used to measure the incentive properties of non-strategyproof mechanisms. We employ this concept to show that a choice between three popular school choice mechanisms, the Deferred Acceptance mechanism and two variants of the Boston mechanism, involves an implicit trade-off between strategyproofness and efficiency. Next, we give conditions under which hybrid mechanisms facilitate meaningful trade-offs between strategyproofness and efficiency in the assignment domain. Finally, in the general ordinal domain we introduce a new framework to assess mechanisms by their manipulability and their welfare deficit. The welfare deficit is a measure for their ability to achieve another desideratum, such as efficiency, stability, or fairness. Within this framework the Pareto frontier consists of those mechanisms that trade off manipulability and deficit optimally. Our main result is a structural characterization of this Pareto frontier.

In recent years, combinatorial auctions have been very successfully used to allocate goods worth billions of dollars. Many of these practical auctions use a minimum-revenue core-selecting payment rule to calculate payments of the winners. Interestingly, the nature of these rules create incentives for overbidding, but not much is known about equilibria outcomes that involve overbidding, as most literature neglected these incentives for simplicity. Beck and Ott (2013) recently found new equilibria with overbidding strategies, both with partially informed bidders and independent private values. Their result for the latter, though, is based on a stylized minimum-revenue core-selecting payment rule. In this thesis, we present new overbidding equilibria in more realistic payment rules. As the equilibrium analysis is very complex, we use computational methods to derive the new equilibria. This thesis also seeks to contribute to the understanding of overbidding in combinatorial auctions.

Electric vehicle sales are rising, which not only has ecological benefits, but also brings about some new challenges. Assuming dynamic prices for end users, we try to optimize the charging process of such vehicles with the help of a smart charging agent. At the beginning of each charging process our agent refines its knowledge about the user's preferences, predicts energy prices using Gaussian processes, and then solves a Markov decision problem to define a charging policy. A number of experiments show that our agent is more efficient and economical than our simpler comparison charging agents. Additionally, our agent reacts to price peaks by lowering its demand, which would help to reduce local energy consumption during peak times.

In mechanism design we usually want to achieve strategy proofness. Unfortunately, this is often in conflict with other designing goals, such as efficiency. Mennle and Seuken (2015) formulated a linear program and created an algorithm that finds a most efficient mechanism for every degree of manipulability. They called the resulting mechanisms the Pareto frontier. In this thesis we first prove a theorem that reduces a linear program using equivalence relations based on symmetry arguments, such as anonymity and neutrality. Second, we implement the algorithm with Java and compute the Pareto frontier for different settings. These computational results allow us to formulate three new conjectures about the structure of the Pareto frontier.

We consider three important, non-strategyproof assignment mechanisms: Probabilistic Serial and two variants of the Boston mechanism. Under each of these mechanisms, we study the agent’s manipulation problem of determining a best response, i.e., a report that maximizes the agent’s expected utility. In particular, we consider local manipulation strategies, which are simple heuristics based on local, greedy search. We make three main contributions. First, we present results from a behavioral experiment (conducted on Amazon Mechanical Turk) which demonstrate that human manipulation strategies can largely be explained by local manipulation strategies. Second, we prove that local manipulation strategies may fail to solve the manipulation problem optimally. Third, we show via large-scale simulations that despite this nonoptimality, these strategies are very effective on average. Our results demonstrate that while the manipulation problem may be hard in general, even cognitively or computationally bounded (human) agents can find near-optimal solutions almost all the time via simple local search strategies.

Several strategic interactions over social networks display both negative and positive externalities at the same time. E.g., participation to a social media website with limited resources is more appealing the more of your friends participate, while a large total number of participants may slow down the website (because of congestion effects) thus making it less appealing. Similarly, while there are often incentives to choose the same telephone company as the friends and relatives with whom you interact the most frequently, concentration of the market share in the hands of a single firm typically leads to higher costs because of the lack of competition. In this work, we study evolutionary dynamics in network games where the payoff of each player is influenced both by the actions of her neighbours in the network, and by the aggregate of the actions of all the players in the network. In particular, we consider cases where the payoff increases in the number of neighbours who choose the same action (local coordination effect) and decreases in the total number of players choosing the same action (global congestion effect). We study noisy best- response dynamics in networks which are the union of two complete graphs, and prove that the asymptotic behaviour of the invariant probability distribution is characterised by two phase transitions with respect to a parameter measuring the relative strength of the local coordination and the global congestion effects. Extensions to connected networks with strong community structure are studied through Monte Carlo simulations.

The Semantic Web is to computers what the traditional web is to humans. It structures data in a way that is easily accessible for computers and allows them to run efficient queries on this data. Unfortunately, this excludes advertisement, the main source of income of traditional websites, which makes it difficult to make money by providing up-to-date data. Most existing semantic web databases started as a part of research projects, funded by subsidies, and run out of date or disappear once these projects end. We want to tackle this problem by introducing a new platform which uses a market-based approach, namely a combinatorial auction, to auction off access to semantic web data and determine prices based on supply and demand. A planner is used to find data sources that promise good results for the queries, which then compete in terms of cost and data quality. We show the results of our simulations with a simplified environment and discuss future work that still needs to be done. The ultimate goal is to set up a platform that can provide a marketplace for semantic web queries and providers of semantic web data and determine prices that provide value for query requesters and encourage providers to keep their data up-to-date and offer it to the public.