Aarhus University Seal / Aarhus Universitets segl

Pricing mechanisms for resource allocation

Applications are invited for a PhD fellowship/scholarship at Graduate School of Natural Sciences, Aarhus University, Denmark, within the Computer Science programme. The position is available from 1 February 2021 or later.

Pricing mechanisms for resource allocation

Research area and project description:

The project falls within the area of Algorithmic Game Theory, a very active research trend at the interface of Computer Science (in particular, theoretical computer science) and Economics (microeconomics and game theory). It is motivated by modern cloud systems, where computation, communication, and storage resources are allocated to users who pay for the corresponding services. The main objective is to study pricing schemes that lead either to the best use of the resources by the users or to high revenue for the cloud system. The concrete questions that will be studied originate from the following classical single-item auction from microeconomics. There is an indivisible item for sale and a set of potential buyers, each with a private valuation for the item. The celebrated second-price auction is optimal with respect to the social welfare, in the sense that the agent who values the item the most gets it. Revenue maximization is possible when agents draw their private values from independent probability distributions. Statistical information about these distributions is known to the seller, who can use it and run the ideal auction to sell the item (and maximize her expected revenue). Such revenue-maximizing auctions were first presented in Myerson's seminal paper.

Even though welfare- and revenue-maximizing auctions are success stories, the corresponding auctions are relatively complex and usually far from the ones used in practice. Different formats such as sequential posted pricing result to simple pricing algorithms (or mechanisms), which are not very far from optimality in terms of social welfare or revenue. And, even though all these mechanisms have been successful when allocating an indivisible item, several resources in a cloud system are divisible. Then, the valuations a user has for fractions of the item is not necessarily linear. So, the divisibility of resources makes the problem of designing an approximately optimal mechanism much more difficult. To make things even more challenging, the project will consider resource allocation problems with multiple divisible resources. The expected outcomes include new mechanisms that approximate optimal social welfare and revenue within small constants and corresponding lower bounds and impossibility results. It is expected that the research will also consider other performance objectives. These include the recently introduced liquid welfare and objectives that measure fairness in the resulting resource allocation.

Qualifications and specific competences:

Applicants to the PhD position must have a relevant MSc degree (e.g., Computer Science, Mathematics, or Economics) and mathematical maturity. Previous involvement with topics such as design and analysis of algorithms and computational complexity is a plus.

Place of employment and place of work:
The place of work will be the Department of Computer Science at Aarhus University, Aabogade 34, 8200 Aarhus N, Denmark.

Applicants seeking further information are invited to contact:

Professor Ioannis Caragiannis, e-mail: iannis@cs.au.dk, web: iannis.dk

Application procedures

Before you apply

Information and attachments:

Please be aware that you must have all relevant appendices, attachments, addresses for referees, etc. ready when you apply, as the entire application must be uploaded to the system in one go.

Documentation of language skills:

The English language requirement at the graduate school is comparable to an “English B level” in the Danish upper secondary school (“gymnasium”).

English language qualifications comparable to an “English B level” are documented by one of the following tests:

  • TOEFL test (internet-based), minimum score: 83. The graduate school does not accept the paper-based test, nor the TOEFL ITP test. Remember to ask the test center to send your test results to Aarhus University in order to enable verification of your test results. Aarhus University’s TOEFL code is 8935.
    Currently, the TOEFL iBT Special Home Edition test (available in selected areas) will also be accepted.
  • IELTS (academic) test, minimum average score: 6.5 points
  • Cambridge English Language Assessment:
    Cambridge Certificate of Proficiency (CPE)
    Cambridge English: Certificate of Advanced English with grade A,B or C (CAE)
    Cambridge English: First Certificate with grade A (FCE)

When to take the test and how to upload the documentation:
The test result must not be more than two years old at the time of application.

The English language test should be taken before applying for admission and uploaded under “language skills documentation” in the online application form.

It is possible to apply for admission before you have taken the test. In this case documentation stating that you have signed up for a test (please state expected submission date) must be uploaded. If the test result is not part of the original application the test result is to be sent to gsns@psys.au.dk no later than one month after the application deadline.

The following applicants are exempted from documenting their English qualifications/taking a test:

  • Applicants with citizenship from the following countries: Australia, Canada, Ireland, New Zealand, the United Kingdom, the United States, or one of the Nordic countries (Denmark, Finland, Iceland, Norway or Sweden).
  • Applicants with a Bachelor’s or Master’s programme completed in Australia, Canada, Ireland, New Zealand, the United Kingdom, or the United States. In this case, please upload your Bachelor’s or Master’s diploma under the section ”Language skills documentation”.
  • Applicants with a Bachelor’s or Master’s programme completed at a Danish university for which the requirement was English B level at the time of admission. In this case, please upload your Bachelor’s or Master’s diploma under the section ”Language skills documentation”.

The programme committee may request further information or invite the applicant to attend an interview.

How to apply:

1)      Find the application form:
Go to https://phd.nat.au.dk/for-applicants/apply-here/ - Note, the online application system opens on 1 September 2020.
Choose November 2020 Call with deadline 1 November 2020 at noon (11.59 AM CEST).
You will be directed to the call, and must choose the programme “Computer Science”.

2)      Fill in the following information:

  • Personal information
  • Academic background
  • Admission
  • Financing (if any)
  • Study: In the dropdown menu you must choose the project: “Pricing mechanisms for resource allocation”
  • Source (how you found out about the call)

Next to some of the information fields you will find a number. Click on the number to get further directions on how to fill in the information field/what information is needed.

3)      Application attachments:
Please be aware that you cannot submit the application if one or several of these documents have not been uploaded.

If you wish to upload more than one document under each section, you must scan/merge all documents into one large PDF file and upload this. Please note that we reserve the right to remove scientific papers, large reports, theses and the like. Instead you can indicate a URL where the information is available.

All information in the application must be in English or Danish, preferably English. A certified English translation is required for documents written in languages other than English or one of the Scandinavian languages (i.e. Norwegian, Swedish or Danish) languages.

As a minimum all applications must include (pdf-files only, max. 20 MB, no zip):

  • One reference (template for references)
  • Curriculum vitae,
  • Motivation (max. 1 page)
  • Transcripts, grade point averages (weighted and unweighted), and diploma(s) for both Bachelor’s and Master’s degree. If the original documents are not in English or one of the Scandinavian languages (i.e. Norwegian, Swedish or Danish) then copies of the original documents as well as a certified English translation must be attached.
  • Project description (½-3 pages). For technical reasons, you must upload a project description. When - as here - you apply for a specific project, please simply copy the project description above (possibly, by pumping it up with your thoughts about it), and upload it as a PDF in the application. If you wish to, you can indicate an URL where further information can be found. Please note that we reserve the right to remove scientific papers, large reports, theses and the like.
  • Documentation of language skills if required.

After submission of the application, you will receive a confirmation e-mail with an application ID, you should use for reference if needed.

The graduate school reserves the right to verify the authenticity of your educational diploma and transcripts:

  • Request additional information to verify an application.
  • Reject the application if it is proven, or if the University has reasonable belief, that the information provided is false or if the applicant refuses to provide the requested information, whether or not an offer has already been made. 
  • For further information on applying, assessment procedures, etc. please see the GSNS Application Guide.

Please note:

  • The programme committee may request further information or invite the applicant to attend an interview.
  • The project will only be initiated if final funding (from the graduate school/the faculty) is secured.

All interested candidates are encouraged to apply, regardless of their personal background.

19572 / i43