Algorithmic Mechanism Design and Optimization Problems with Economic Applications
Lead Research Organisation:
University of Liverpool
Department Name: Computer Science
Abstract
Our day-to-day life activities are influenced by various communication networking facilities, like electronic mail, electronic trade and banking systems. Their common underlying infrastructure is the Internet, probably one of the mostinfluential human creations of the last century. The Internet is decentralized, i.e.,created and operated by independent entities (humans, servers, companies)which mostly realize their own, usually selfish, goals. In classic optimization problems which are mostly NP-hard, the complete input data is available to the algorithm. The selfish setting raises new, challenging optimization problems withthe added difficulty that part of the input data is private data of these entities to be elicited. The very successful theory of approximation algorithms is usually used to treat NP-hard problems. On the other hand, the standard tool to cope with selfish behavior is economic non-cooperative game theory and mechanism design, with the prominent notion of Nash equilibria. The synergy between these two areas,algorithmic game theory (AGT), has been a major research area in computer science recently. This vibrant research area is establishing the mathematical platform for problems arising in context of the Internet. Despite efforts, many problems still await their solutions, and many applications call for newmathematical models. We propose to contribute to this fascinating and important research endeavor from many different perspectives, by attacking both fundamental, basic problems and opening new lines of thinking.Our main high level goal is to develop new techniques for mathematical analysis of algorithmic models, and to develop new models, motivated by economic and network design applications, using as basis approximation algorithms and linear programming (duality) techniques. The main classes of problems which we plan to study include basic auction settings (like combinatorial auctions, adwords auctions), revenue maximizing product pricing problems, and network mechanism design problems.
Organisations
People |
ORCID iD |
| Piotr Krysta (Principal Investigator) |
Publications
Briest P
(2009)
Internet and Network Economics
Briest P
(2012)
On stackelberg pricing with computationally bounded customers
in Networks
Christodoulou G
(2010)
A deterministic truthful PTAS for scheduling related machines.
Christodoulou G
(2013)
A Deterministic Truthful PTAS for Scheduling Related Machines
in SIAM Journal on Computing
Christodoulou G
(2013)
Contention Resolution under Selfishness
in Algorithmica
Fabrizio Grandoni, Piotr Krysta, Stefano Leonardi, Carmine Ventre
(2010)
Utilitarian Mechanism Design for Multi-Objective Optimization
in Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010
Fotakis D
(2011)
Algorithmic Game Theory
Grandoni F
(2014)
Utilitarian Mechanism Design for Multiobjective Optimization
in SIAM Journal on Computing
Krysta P
(2012)
Internet and Network Economics
Krysta P
(2015)
Combinatorial auctions with verification are tractable
in Theoretical Computer Science
| Description | This research project has significantly advanced our understanding of computational problems on the border of computer science and economics. This novel academic discipline has grown as the mathematical platform for problems motivated by practical applications arising in context of the Internet. As the project's main contributions: 1. We have developed new techniques for theoretical analysis of algorithmic models, and we defined new models, motivated by economic and network design applications, that use as their basis approximation algorithms and linear programming techniques. 2. We studied both pure optimisation problems, with complete knowledge of the data, and mechanism design problems, where part of the data is private property of selfish agents and needs to be elicited. In particular we have studied and advanced the following important classes of problems: (a) Combinatorial auctions (CAs), the paradigmatic problem in algorithmic mechanism design with many practical applications. We have designed and analysed for CAs a novel randomised truthful auction mechanism which has superior theoretical properties and is the best currently known such mechanism for online multidimensional bidders. Due to its simplicity this mechanism can be implemented and used in practice. This work has received the best paper award at the premier European conference in Theoretical Computer Science, ICALP 2012. Our second major contribution to CA is the introduction of verification to this mechanism design setting. With this approach we managed to give an efficient deterministic truthful mechanism for multidimensional bidders with best possible approximation guarantees. This work was published at the premier European algorithms conference ESA 2010. Our third major research paper deals with CA with small number of goods to sell. This work has received the best paper award of AAMAS 2013, the major and most influential conference on autonomous agents systems. (b) Keyword search advertisement auctions, used by search engines like Google. For this problem we have introduced and algorithmically analysed a novel model of externalities which is based on empirically observed behaviour of real advertisers. Our model is the first which captures all the externality effects observed in such real life auctions (publication at SAGT 2011). (c) Revenue maximising pricing, which is an especially challenging type of economic objective. We designed here online pricing mechanisms for a difficult version of such pricing problems with hard product supply constraints. Our mechanisms significantly improve on the previously known competitive ratios (publication at WINE 2012). (d) Network mechanism design problems. In this setting we introduce two new techniques that lead to efficient truthful mechanisms for multi-objective network design problems. Our new techniques use advanced optimisation paradigms (approximate Pareto curves, Langrangean relaxation, polyhedral combinatorics) and are mathematically sophisticated. This work was published at the most prestigious algorithms conference ACM-SIAM SODA 2010 and the top Computer Science journal SIAM Journal on Computing (SICOMP) 2014. (e) We also worked on additional closely related mechanism design topics: scheduling (SODA 2010 and SICOMP 2013 publications), collusion-resistant mechanisms with verification (ACM EC 2009), Stackelberg pricing (WINE 2009 and Networks 2012 publications). We would also like to mention that ACM EC is the top conference in computational economics and WINE and SAGT are the other two major conferences in this area. Our algorithmic models and algorithmic solutions will have significant theoretical impact (as already confirmed by two best paper awards and publications at the most prestigious conferences and journals). On the other hand they also will have practical impact in that the resulting algorithms can be implemented and used on a computer. Recent update: Our best paper award winning research from AAMAS 2013 has received a further recognition. We have been invited to present these results at Best Papers Session from Sister conferences at IJCAI 2015, which is the leading international conference in AI (this resulted in an IJCAI 2015 publication of an expository article on our results). In addition, the full journal version of this research at JAIR 2015. |
| Exploitation Route | We provided a number of novel theoretical methods of analysing properties of economic auction mechanisms which advence the state of the art in the area of algorithmic mechanism design. Many of these methods have already been used by other researchers. For instance, our overselling auction mechanism from ICALP 2012, has been used in context of auctions that are stochastically dominant truthful. Our techniques from AAMAS 2013 have been used to design new auctions for electric power allocation problems. Our approaches from SODA 2010 have been applied to obtaining trade-offs between social welfare and revenue in some auction settings. Another example is our work from ESA 2010 on verification in auctions, the direction that have been continued by many authors in context of different mechanism design settings. This research line has inspired new directions in mechanism design and has resulted in new findings published by the authors and by other researchers in AAMAS 2014, 2015, WINE 2015 and SIGMETRICS 2015. |
| Sectors | Financial Services, and Management Consultancy,Government, Democracy and Justice,Other |
| Description | Our research opened new research directions: one about combinatorial pricing problems, which have generated a flow of follow up work by other researchers; another new direction is that on verification in auctions, which proved an interesting alternative to payments in auction design, both from the theoretical and practical viewpoint. Many of our techniques to design and analyse economic auction protocols have been applied by other researchers in other related algorithmic mechanism design settings (these include our techniques from AAMAS 2013, ICALP 2012, ESA 2010, SODA 2010). On a possible non-academic side impact, we have introduced verification to the design of combinatorial auctions with multi-dimensional bidders. This proved very fruitful for achieving good approximation guarantees for such auctions. On the other hand this approach gives a promise of potential applications of such auctions in contexts of public government projects. |
| Sector | Financial Services, and Management Consultancy,Other |
| Impact Types | Economic,Policy & public services |