Efficient Algorithms for Mechanism Design Without Monetary Transfer
Lead Research Organisation:
University of Glasgow
Department Name: School of Computing Science
Abstract
Abstracts are not currently available in GtR for all funded research. This is normally because the abstract was not required at the time of proposal submission, but may be because it included sensitive information such as personal details.
People |
ORCID iD |
| David Manlove (Principal Investigator) |
Publications
Arulselvan A
(2015)
Algorithms and Computation
Arulselvan A
(2016)
Matchings with Lower Quotas: Algorithms and Complexity
in Algorithmica
Askalidis G
(2013)
Algorithms and Data Structures
Aziz H
(2020)
Stable Matching with Uncertain Linear Preferences.
in Algorithmica
Aziz H
(2022)
Stable matching with uncertain pairwise preferences
in Theoretical Computer Science
Biró P
(2014)
Editorial: Special Issue on Matching under Preferences
in Algorithms
Biró P
(2014)
Experimental Algorithms
Bogomolnaia A
(2015)
Size versus fairness in the assignment problem
in Games and Economic Behavior
Cechlárová K
(2018)
Pareto optimal matchings of students to courses in the presence of prerequisites
in Discrete Optimization
| Description | We have designed mechanisms without monetary transfer for the problem of allocating resources to agents who submit preferences over these resources. An example is allocating students to dormitories, also known as the house allocation problem. Our starting point is one of the most widely studied mechanisms for the house allocation problem in economics literature -- the serial dictator. We generalise this mechanism allowing agents' preferences to include ties. Our mechanism is the first known that provides provable guarantees on the quality of the computed allocation (weight of the computed matching). This opened a completely new research direction, that of approximate truthful mechanisms, for matching problems under preferences (ACM EC 2014). This research direction has been continued by economists and a related paper has been published by Bogomolnaia and Moulin in Games and Economic Behavior (2015). Our truthful mechanism provides an approximation with constant guarantee on its performance, assuming that each agent gives each object the same weight. We were also able to prove a strong non-constant lower bound on the performance of such truthful mechanisms if each agent is allowed to give different weights to each object (AAMAS 2016). This shows that our constant bound on mechanism's performance cannot be improved under this more general scenario. Moreover, the existing theoretical economics literature implies that even our constant approximation guarantee cannot be further improved within a broad class of truthful non-bossy mechanisms. Our recent results include a strong generalisation of these results from matching under preferences to many-to-many settings (SAGT 2015 and Theory of Computing Systems 2016) and to such matching problems where in addition we allow for matroid or knapsack constraints. In this latter setting we are able to strongly generalise our previous results from ACM EC 2014 to the setting where each object has its own matroid constraint. A feasible solution allows for any object to be assigned to many agents so long as they form an independent set of the respective matroid. The agents still have preferences with ties over the set of objects and weights. We were able to prove the same approximation guarantees in this very general setting as ones from our AC EC 2014 paper, however, by generalising our previous mechanisms and by using a completely different analysis. We have obtained similar results assuming that objects have knapsack-type constraints. These results were published in ICALP 2016. Continuing on the theme of matching under preferences, we have also investigated problems that come directly from practical applications, such as the allocation of students to projects under capacity constraints on projects and lecturers (IWOCA 2014); in a follow-up paper we also considered the case where projects may have lower quotas indicating that they require a certain number of students to be viable (ISAAC 2015 and Algorithmica 2017). Another example involves the allocation of trainee teachers to schools in Slovakia, where specific constraints must be satisfied (CEJOR 2015 and Theoretical Computer Science 2016). We also considered the problem of assigning students to elective courses in the presence of pre-requisite and co-requisite constraints (COMSOC 2016). In a series of papers we have developed integer programming models to solve NP-hard optimisation problems that again feature in real-world applications, such as the assignment of junior doctors to hospitals where preferences can include ties (OR 2013) or where couples can submit joint preferences (OR 2013, SEA 2014, Constraints 2016). We used a similar technique to solve the kidney exchange problem subject to (hierarchical) optimality criteria that are specific to the UK setting (ACM EC 2016, ACM JEA 2014). Finally we have considered different models of preferences, where (i) agents may have to be acquainted to one another in order to disrupt a given matching (WADS 2013); (ii) agents may be unaware of their full preferences but can obtain information about them through a process of carrying out interviews (AAMAS 2016); (iii) certain partnerships may be forced or forbidden by a matching administrator (SAGT 2015 and Discrete Optimization 2016); and (iv) the lengths of preference lists are bounded (SAGT 2016). Our second research strand concerns strong theoretical results for approximate truthful mechanisms for combinatorial auctions without monetary transfers. These mechanisms use a notion of verification, which can be an attractive alternative to monetary payments in real-world auction systems. Combinatorial auctions collectively form one of the paradigmatic problems in algorithmic mechanism design. In the setting of combinatorial auctions without money but with verification, we characterise the class of all truthful mechanisms and give a host of upper and lower bounds on the approximation guarantees obtained by either deterministic or randomized truthful mechanisms. Our results provide an almost complete picture of truthfully approximating combinatorial auctions in this general setting with multi-dimensional bidders. These results are published in AAMAS 2014 and in Algorithmica 2017. We continued the study of verification in context of greedy mechanisms for combinatorial auctions. Greedy algorithms are known to provide near optimal approximation guarantees for combinatorial auctions with multidimensional bidders, ignoring truthfulness issues. We provide a deeper understanding of greedy mechanism design and investigate under which general assumptions we can have efficient and truthful greedy mechanisms for combinatorial auctions. Towards this goal, we use the framework of priority algorithms, and weak and strong verification, and provide a complete characterisation of the power of weak verification showing that it is sufficient and necessary for any greedy fixed priority algorithm to become truthful with the use of money or not, depending on the ordering of the bids. Moreover, we show that strong verification is sufficient and necessary for the well-known greedy algorithm of Lehmann, Lehmann and Nisan, which is 2-approximate for submodular combinatorial auctions, to become truthful with money in finite bidding domains. Our work, published in AAMAS 2015, is the first that studies the complexity of computing payments in mechanisms. A parallel class of allocation problem deal with divisible resources, i.e., resources which can be divided into fractions and these fractions are allocated to agents (for instance oil or coal). We use here a weaker than truthfulness solution concept for mechanisms, namely that of Nash equilibria, and use a tool for analysing quality of Nash equilibria, called the Price of Anarchy (PoA). PoA shows how much worse the social welfare is under any Nash equilibrium compared to the social welfare of the best optimal solution. We study the efficiency of the proportional allocation mechanism, which is widely used in economics to allocate divisible resources. Each agent submits a bid for each divisible resource and receives a fraction proportional to her bids. We quantify the inefficiency of Nash equilibria by studying the PoA of the induced game under complete and incomplete information. We provide a set of bounds on PoA assuming that agents' valuations are concave, subadditive, and for settings with budget constraints and polyhedral constraints, and under Bayesian Nash equilibria and coarse-correlated equilibria. These results, published in SAGT 2015, show that the proportional allocation mechanism can successfully be deployed in these settings as it has small PoA. In a related research direction we have applied algorithmic mechanism design to the important problem of pollution control (published in AAMAS 2016 and COCOON 2016). In this work we introduce a novel network model of the pollution control problem. Our model comprises a graph whose nodes represent the agents (sources of pollution), and edges between agents represent the effect of spread of pollution. The government as the regulator is responsible for maximising the social welfare while setting bounds on the levels of emitted pollution both locally and globally. Our model is inspired by the existing literature in environmental economics. We study the social welfare maximisation problem in this model. Our main results include computational hardness results for the problem, approximation algorithms and truthful approximate mechanisms when networks are general bounded degree graphs, planar graphs (modelling air pollution) and trees (modelling water pollution in rivers). Our mechanisms on planar networks are obtained by a novel decomposition technique of planar graphs to deal with constraints on vertices, and this technique can be of independent interest. Additional results: Makespan minimisation in scheduling is the second, together with combinatorial auctions, paradigmatic optimisation problem studied in algorithmic mechanism design. It has a status of an unsolved problem in general. We design randomised truthful mechanisms for this problem for a restriction of the general multi-dimensional domain (i.e., unrelated machines). In a sense, our model is the simplest (difficult) multi-dimensional setting, where each machine holds privately only a single bit of information. Some of the impossibility results for deterministic mechanisms carry over to this setting as well. We prove a separation between truthful-in-expectation and universally truthful mechanisms for makespan minimisation: we first show how to design an optimal truthful-in-expectation mechanism, and then prove lower bounds on the approximation guarantee of universally truthful mechanisms. Our results are published in Theory of Computing Systems (2015). Our SAGT 2015 paper studies the design of novel auctions that maximise the chance (probability) of raising a given revenue target. We provide a number of computational hardness results for various settings concerning such auctions. We then characterise an optimal revenue target auctions for the case of two buyers with independent valuations, which leads to such optimal auction mechanism. In settings with many buyers we design simple auctions (posted price and monopoly price auctions) that approximate their success probability with an arbitrarily good precision. In our IJCAI 2015 paper we study the algorithmic mechanism design problem within one of the most successful electronic commerce applications paradigms -- that of Google's sponsored search auctions. We design envy-free sponsored search auctions, where bidders are budget-constrained; this is an assumption that is very important in e-commerce practice. Our primary goal is to design auctions that maximise the social welfare of the bidders and revenue of the auctioneer, which are the two classical objectives in auction theory. For this purpose, we characterise envy-freeness with budgets by proving several elementary properties including consistency, monotonicity and transitivity. Based on this characterisation, we come up with an envy-free auction that is both social-optimal and bidder optimal for a wide class of bidder types. More generally, for all bidder types, we provide two polynomial time approximation schemes (PTASs) for maximising social welfare or revenue, where the notion of envy-freeness has been slightly relaxed. Finally, in cases where randomisation is allowed in designing auctions, we devise similar PTASs for social welfare or revenue-maximisation problems. The Price of Anarchy (PoA) in congestion games has attracted a lot of research over the last decade. This has resulted in a thorough understanding of this concept. In contrast the Price of Stability, which is an equally interesting concept, is much less understood. In our ICALP 2013 paper (with full version published in ACM TEAC 2015), we consider congestion games with polynomial cost functions with nonnegative coefficients and maximum degree d. We give matching bounds for the Price of Stability in such games, i.e., our technique provides the exact value for any degree d. For linear congestion games, tight bounds were previously known. Those bounds hold even for the more restricted case of dominant equilibria, which may not exist. We give a separation result showing that already for congestion games with quadratic cost functions this is not possible; that is, the Price of Anarchy for the subclass of games that admit a dominant strategy equilibrium is strictly smaller than the Price of Stability for the general class. In a series of papers we investigate the query complexity of computing equilibria in strategic games. This approach has a very timely rationale, because in large scale applications, the players usually do not have full knowledge about their opponents' play or about the full game itself. Instead, they can query only certain subset of strategy profiles and their payoffs. In such settings, we study: (i) computational query complexity of learning exact and approximate Nash equilibria in games (Journal of Machine Learning Research 2015); (ii) query complexity of computing approximate equilibria for various classes of games (ACM EC 2014), and for anonymous games (WINE 2015). |
| Exploitation Route | This is described in more detail under "narrative impact". |
| Sectors | Healthcare |
| Description | Algorithms arising from this project are being used by NHS Blood and Transplant as part of the UK Living Kidney Sharing Scheme (UKLKSS). These algorithms allow optimal sets of kidney exchanges to be identified, where in a kidney exchange, a patient with a willing but incompatible donor can swap their donor with that of another patient who is in a similar position in order to obtain a compatible kidney. Furthermore, the algorithms can find chains triggered by altruistic donors, which also involve incompatible patient-donor pairs, with the final donor donating to a patient on the deceased donor waiting list. These algorithms, which are executed as part of each quarterly matching run of the UKLKSS, have had to evolve to cope with changing requirements and increased pool sizes. As of February 2020, 940 transplants identified by the algorithms have proceeded to surgery. It is estimated that our research has led to an increase in the number of kidney transplants carried out in the UK by 292 up to the end of 2019. Compared to dialysis, every additional kidney transplant that this research has enabled saves the NHS approximately £241k over 10 years, which equates to total estimated savings of £70M. Two relevant papers from the project concerned with this research are http://dx.doi.org/10.1145/2940716.2940759 and http://dx.doi.org/10.1145/2670129. Also, optimal matching algorithms that have been developed during the course of this project are being used to allocate students to courses and projects, and also markers to projects, within various university departments. During the lifetime of this project our algorithms have been used for allocating students to elective courses within the School of Medicine, University of Glasgow, taking into account students' ranked preferences over courses and course capacities. The algorithms have also been used to allocate students to projects within the School of Computing Science, University of Glasgow, the School of Mathematics and Statistics, University of Glasgow, the School of Informatics, University of Edinburgh, the School of Engineering, University of Aberdeen, the School of Medicine, University of Leeds, the Schools of Biosciences and Physical Sciences, University of Kent and the School of Engineering, University of San Diego. Finally, the algorithms have further been used to allocate readers (second-markers) to projects at the School of Computing Science, University of Glasgow. By automating these complex allocation processes, the algorithms will have saved many hours of academic and administrative staff time, resulting in implicit financial savings for the institutions concerned. A relevant paper from the project in connection with this research is http://dx.doi.org/10.1007/978-3-319-19315-1_19. |
| First Year Of Impact | 2013 |
| Sector | Education,Healthcare |
| Impact Types | Societal,Economic,Policy & public services |
| Description | ENCKEP: European Network for Collaboration on Kidney Exchange Programmes (COST Action CA15210) |
| Amount | € 720,000 (EUR) |
| Funding ID | CA15210 |
| Organisation | European Commission |
| Sector | Public |
| Country | European Union (EU) |
| Start | 09/2016 |
| End | 03/2021 |
| Description | Impact Acceleration Account |
| Amount | £29,640 (GBP) |
| Funding ID | EP/K503903/1 |
| Organisation | Engineering and Physical Sciences Research Council (EPSRC) |
| Sector | Public |
| Country | United Kingdom |
| Start | 01/2015 |
| End | 09/2015 |
| Description | Institutional Sponsorship Fund |
| Amount | £17,765 (GBP) |
| Funding ID | EP/N508792/1 |
| Organisation | Engineering and Physical Sciences Research Council (EPSRC) |
| Sector | Public |
| Country | United Kingdom |
| Start | 10/2015 |
| End | 03/2016 |
| Description | Standard grant (responsive mode) |
| Amount | £801,639 (GBP) |
| Funding ID | EP/P028306/1 |
| Organisation | Engineering and Physical Sciences Research Council (EPSRC) |
| Sector | Public |
| Country | United Kingdom |
| Start | 11/2017 |
| End | 10/2020 |
| Title | "Almost stable" matchings in the Hospitals / Residents problem with Couples |
| Description | Collection of randomly-generated instances of the Hospitals / Residents problem with Couples |
| Type Of Material | Database/Collection of data |
| Provided To Others? | No |
| Impact | Data used in the experimental evaluation section of this paper: http://dx.doi.org/10.1007/s10601-016-9249-7 |
| URL | http://researchdata.gla.ac.uk/303/ |
| Title | An Integer Programming Model for the Hospitals/Residents Problem with Couples |
| Description | Collection of randomly-generated instances of the Hospitals / Residents problem with Couples |
| Type Of Material | Database/Collection of data |
| Provided To Others? | No |
| Impact | Data used in the experimental evaluation section of this paper: http://dx.doi.org/10.1007/978-3-319-07001-8_40 |
| URL | http://researchdata.gla.ac.uk/255/ |
| Title | An Integer Programming approach to the Hospitals / Residents problem with Ties |
| Description | Collection of randomly-generated instances of the Hospitals / Residents problem with Ties |
| Type Of Material | Database/Collection of data |
| Provided To Others? | No |
| Impact | Data used in experimental evaluation section of this paper: http://dx.doi.org/10.1007/978-3-319-07001-8_36 |
| URL | http://researchdata.gla.ac.uk/244/ |
| Title | Profile-based optimal matchings in the Student-Project Allocation problem |
| Description | Collection of randomly-generated student-project allocation instances |
| Type Of Material | Database/Collection of data |
| Provided To Others? | No |
| Impact | Data used in the experimental section of this paper: http://dx.doi.org/10.1007/978-3-319-19315-1_19 |
| URL | http://researchdata.gla.ac.uk/253 |
| Title | The Hospitals / Residents problem with Couples: Complexity and Integer Programming models |
| Description | Collection of randomly-generated instances of the Hospitals / Residents problem with Couples |
| Type Of Material | Database/Collection of data |
| Provided To Others? | No |
| Impact | Data used in the experimental evaluation section of this paper: http://dx.doi.org/10.1007/978-3-319-07959-2_2 |
| URL | http://researchdata.gla.ac.uk/254/ |
| Description | ENCKEP: European Network for Collaboration on Kidney Exchange Programmes (COST Action CA15210) |
| Organisation | Erasmus University Rotterdam |
| Department | Institute of Health Policy & Management (iBMG) |
| Country | Netherlands |
| Sector | Academic/University |
| PI Contribution | Drafting the proposal for the COST Action. Vice-Chair to April 2018 and Chair from May 2018. |
| Collaborator Contribution | Drafting the proposal for the COST Action. Vice-Chair to April 2018 and Chair from May 2018. |
| Impact | Memorandum of Understanding published at https://e-services.cost.eu/files/domain_files/CA/Action_CA15210/mou/CA15210-e.pdf Publications listed at https://www.enckep-cost.eu/category/resources/publications Outputs / impacts listed in the final achievement report: https://e-services.cost.eu/files/domain_files/CA/Action_CA15210/final_achievement_report/final_achievement_report-CA15210.pdf |
| Start Year | 2016 |
| Description | ENCKEP: European Network for Collaboration on Kidney Exchange Programmes (COST Action CA15210) |
| Organisation | INESC TEC |
| Country | Portugal |
| Sector | Private |
| PI Contribution | Drafting the proposal for the COST Action. Vice-Chair to April 2018 and Chair from May 2018. |
| Collaborator Contribution | Drafting the proposal for the COST Action. Vice-Chair to April 2018 and Chair from May 2018. |
| Impact | Memorandum of Understanding published at https://e-services.cost.eu/files/domain_files/CA/Action_CA15210/mou/CA15210-e.pdf Publications listed at https://www.enckep-cost.eu/category/resources/publications Outputs / impacts listed in the final achievement report: https://e-services.cost.eu/files/domain_files/CA/Action_CA15210/final_achievement_report/final_achievement_report-CA15210.pdf |
| Start Year | 2016 |
| Title | Kidney exchange web applications |
| Description | These websites find optimal solutions to kidney exchange problems. See: http://kidney.optimalmatching.com http://toolkit.optimalmatching.com http://www.dcs.gla.ac.uk/~jamest/weighted-toolkit/#/input |
| Type Of Technology | Webtool/Application |
| Year Produced | 2015 |
| Impact | Algorithms that feature in these web applications are used by NHS Blood and Transplant for quarterly matching runs of the National Living Donor Kidney Sharing Schemes. More information about these algorithms can be found under "Narrative Impact". |
| URL | http://kidney.optimalmatching.com |
| Description | BBC4 documentary: "The Secret Rules of Modern Living: Algorithms" |
| Form Of Engagement Activity | A broadcast e.g. TV/radio/film/podcast (other than news/press) |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Media (as a channel to the public) |
| Results and Impact | I appeared in the BBC4 documentary "The Secret Rules of Modern Living: Algorithms", presented by Marcus du Sautoy, first shown on 24 September 2015. The documentary describes how algorithms can be used in a range of real-life applications. It discusses kidney exchange from approx. 27:10 onwards. I am interviewed, along with Rachel Johnson, Head of Organ Donation and Transplantation Studies at NHS Blood and Transplant, and patients and donors who have participated in the matching scheme. Along with Dr Patrick Prosser at the School of Computing Science, University of Glasgow, we also contributed a lot of material to the Producer and Director when they were at the planning / research stage of the documentary, to enable them to determine which algorithms might be good choices to feature in the programme, and who they should interview. |
| Year(s) Of Engagement Activity | 2015 |
| URL | http://www.bbc.co.uk/programmes/p030s6b3 |