R4U - Meeting 2010-10-01

Table of Contents


  • Γενική συζήτηση
  • Περί της Θεωρίας Παιγνίων
  • Σχεδίαση Μηχανισμών και Πλειστηριασμοί
  • Competitive auctions - ανοικτά προβλήματα

Σκοπός της προσπάθειας

  • Να έρθουν κάποιοι φοιτητές/τριες σε επαφή με την πιο δημιουργική πλευρά του Πανεπιστημίου.
  • Στις πρώτες συναντήσεις που θα είμαστε περισσότεροι, θα μιλήσουμε γενικά για έρευνα και πανεπιστήμια
  • Κυρίως όμως να παιδευτούμε (με όλες τις έννοιες της λέξης)

Ας γνωριστούμε

Πριν φύγετε, συμπληρώστε στη φόρμα τις παρακάτω πληροφορίες.

  • Τα ενδιαφέροντά μου είναι …
  • Το υπόβαθρό μου είναι …
  • Νομίζω πως είμαι καλός σε …

Θεωρία Παιγνίων (Game Theory)

Τι χρειάζεται να ξέρω για υπόβαθρο;

  • Πολλά!
  • Τουλάχιστον όμως να διαβάσεις τις εξής πηγές
    1. Άρθρο του Χ. Παπαδημητρίου: Algorithms, games, and the internet
    2. Wikipedia on game theory
    3. Να "ξεφυλλίσεις" το βιβλίο "Algorithmic Game Theory" (διαθέσιμο online).

Σχετικές δημοσιεύσεις

  • J. Hartline and A. Karlin, Profit maximization in mechanism design (Chapter 13 of the book "Algorithmic Game Theory")
  • Andrew~V. Goldberg, Jason~D. Hartline, Anna~R. Karlin, Andrew Wright, and Michael Saks. Competitive auctions. In Games and Economic Behavior, pages 72–81, 2002.
  • Uriel Feige, Abraham Flaxman, Jason~D. Hartline, and Robert~D. Kleinberg. On the competitive ratio of the random sampling auction. In WINE, pages 878–886, 2005.
  • Jason~D. Hartline and Robert McGrew. From optimal limited to unlimited supply auctions. In ACM Conference on Electronic Commerce, pages 175–182, 2005.
  • E. Koutsoupias and G. Pierrakos. On the competitive ratio of online sampling auctions. To appear in WINE 2010.

Τι πρέπει να κάνω μέχρι την επόμενη συνάντηση;

  • Να διαβάσεις τα σχετικά με το υπόβαθρο
  • Να διαβάσεις προσεκτικά τις 5 σχετικές δημοσιεύσεις
  • Να σκεφτείς τα ανοικτά προβλήματα που αναφέρονται στη συνέχεια
  • Να λύσεις γραπτώς της "άσκηση" που ακολουθεί

Open problems

  1. Show that RSOP is 4-competitive (or improve the lower bound). We currently know that the competitive ratio of RSOP is between 4 and 4.68. The conjecture is that the lower bound is tight. A new technique seems to be needed for establishing the conjecture.
  2. Find the optimal competitive ratio. We currently have a lower bound of 2.42 and an upper bound of 3.25.
  3. Prove that BPSF is 4-competitive.
  4. Find another online algorithm which is easier to analyze and which has competitive ratio 4.

My guess is that the easiest problem is #4 while the hardest one is #2.


  • Consider the online algorithm which offers as price the average bid of the revealed buyers. Find its competitive ratio. This is a much easier problem compared to the 4 open problems. Solve it and hand in the solution at the next meeting.

Here is another way to state the problem without any jargon:

  • Let b1 ≥ … ≥ bn be positive real numbers (the bids)
  • Let bj1,…, bjn be a random permutation (the order in which the bids appear)
  • Let pk+1=(∑ki=1 bji)/k (the price offered to the (k+1)-st bidder)
  • If bjk ≥ pk then gk=pk; else gk=0 (the profit from the k-th bidder)
  • Let ρ=E[(∑nk=1 gk)/(maxi≥ 2 i bi)] (the expected ratio over F(2). The expectation is over all permutations.)
  • Find the minimum ρ over all sets of bids b1 ≥ … ≥ bn.


Author: Elias Koutsoupias

Date: 2010-10-03 17:01:01