Nicolas Küchler, Reducing Bidding Complexity in Machine Learning-based Combinatorial Auctions, University of Zurich, Faculty of Business, Economics and Informatics, 2017. (Bachelor's Thesis)
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.
|
|
Gianluca Brero, Benjamin Lubin, Sven Seuken, Probably Approximately Efficient Combinatorial Auctions via Machine Learning, In: AAAI-17: Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, California, United States, 2017. (Conference or Workshop Paper published in Proceedings)
|
|
Steffen Schuldenzucker, Sven Seuken, Stefano Battiston, Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-complete, In: The 8th Innovations in Theoretical Computer Science (ITCS) Conference, Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik, New York, NY, USA, 2017-01-09. (Conference or Workshop Paper published in Proceedings)
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. |
|
Johannes Hool, Human-Supported Recommender Systems - An Experimental Evaluation, University of Zurich, Faculty of Business, Economics and Informatics, 2016. (Master's Thesis)
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. |
|
Timo Mennle, Sven Seuken, The Pareto frontier for random mechanisms, In: The 2016 ACM Conference on Economics and Computation, ACM Press, New York, New York, USA, 2016-08-24. (Conference or Workshop Paper published in Proceedings)
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. |
|
Steffen Schuldenzucker, Sven Seuken, Stefano Battiston, Clearing Payments in Financial Networks with Credit Default Swaps [Extended Abstract], In: EC'16, ACM Press, New York, New York, USA, 2016. (Conference or Workshop Paper published in Proceedings)
|
|
Michael Weiss, SATS: A Spectrum Auction Test Suite, University of Zurich, Faculty of Business, Economics and Informatics, 2016. (Master's Thesis)
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. |
|
Dmitrii Moor, Sven Seuken, Tobias Grubenmann, Abraham Bernstein, Core-selecting payment rules for combinatorial auctions with uncertain availability of goods , In: The Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016. (Conference or Workshop Paper published in Proceedings)
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. |
|
Dmitry Moor, Sven Seuken, Tobias Grubenmann, Abraham Bernstein, Core-selecting payment rules for combinatorial auctions with uncertain availability of goods, In: Twenty-Fifth International Joint Conference on Artificial Intelligence, AAAI Press / International Joint Conferences on Artificial Intelligence, New York, USA, 2016-07-09. (Conference or Workshop Paper published in Proceedings)
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. |
|
Alper T. Alan, Michael Shann, Enrico Costanza, Sarvapali D. Ramchurn, Sven Seuken, It is too Hot: An In-Situ Study of Three Designs for Heating, In: Conference on Human Factors in Computing Systems (CHI), ACM, New York, USA, 2016. (Conference or Workshop Paper published in Proceedings)
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. |
|
Michael Kündig, Developing a Sate-of-the-Art Recommender Algorithm for CoRe, University of Zurich, Faculty of Economics, Business Administration and Information Technology, 2016. (Master's Thesis)
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. |
|
Timo Mennle, Trade-offs between strategyproofness and efficiency of ordinal mechanisms, University of Zurich, Faculty of Economics, Business Administration and Information Technology, 2016. (Dissertation)
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. |
|
Andreas Perschak, A Computational Bayes-Nash Equilibrium Analysis of Overbidding Strategies in Combinatorial Auctions, University of Zurich, Faculty of Economics, Business Administration and Information Technology, 2015. (Bachelor's Thesis)
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. |
|
Balthasar Caflisch, Charging Electric Vehicles with MDPs and GPs, University of Zurich, Faculty of Economics, Business Administration and Information Technology, 2015. (Master's Thesis)
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. |
|
Benjamin Lubin, Benedikt Bünz, Sven Seuken, New Core-Selecting Payment Rules with Better Fairness and Incentive Properties, In: The Third Conference on Auctions, Market Mechanisms and Their Applications, ACM, New York, USA, 2015-09-08. (Conference or Workshop Paper published in Proceedings)
|
|
Dmitry Moor, Tobias Grubenmann, Sven Seuken, Abraham Bernstein, A Double Auction for Querying the Web of Data, In: The Third Conference on Auctions, Market Mechanisms and Their Applications, ACM, New York, USA, 2015-09-08. (Conference or Workshop Paper published in Proceedings)
|
|
Daniel Abächerli, Computing Pareto Frontiers for Randomized Mechanisms, University of Zurich, Faculty of Economics, Business Administration and Information Technology, 2015. (Bachelor's Thesis)
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. |
|
Timo Mennle, Michael Weiss, Basil Philipp, Sven Seuken, The Power of Local Manipulation Strategies in Assignment Mechanisms, In: Twenty-Fourth International Joint Conference on Artificial Intelligence, AAAI Press / International Joint Conferences on Artificial Intelligence, Palo Alto, California, USA, 2015. (Conference or Workshop Paper published in Proceedings)
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. |
|
Gianluca Brero, Giacomo Como, Fabio Fagnani, Dynamics in network games with local coordination and global congestion effects, In: 53rd IEEE Conference on Decision and Control. 2014. (Conference Presentation)
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. |
|
Stefan Cortali, Using Combinatorial Auctions to Optimize Querying the Web of Data, University of Zurich, Faculty of Economics, Business Administration and Information Technology, 2014. (Master's Thesis)
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. |
|