R4U - Meeting 2010-10-01

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

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

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

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

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

• Πολλά!
• Τουλάχιστον όμως να διαβάσεις τις εξής πηγές
  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 σχετικές δημοσιεύσεις
• Να σκεφτείς τα ανοικτά προβλήματα που αναφέρονται στη συνέχεια
• Να λύσεις γραπτώς της "άσκηση" που ακολουθεί

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 b₁ ≥ … ≥ b_n be positive real numbers (the bids)
• Let b_j1,…, b_jn be a random permutation (the order in which the bids appear)
• Let p_k+1=(∑^k_i=1 b_ji)/k (the price offered to the (k+1)-st bidder)
• If b_jk ≥ p_k then g_k=p_k; else g_k=0 (the profit from the k-th bidder)
• Let ρ=E[(∑ⁿ_k=1 g_k)/(max_{i≥ 2} i b_i)] (the expected ratio over F⁽²⁾. The expectation is over all permutations.)
• Find the minimum ρ over all sets of bids b₁ ≥ … ≥ b_n.

• By the way, most senior researchers are university professors. So, what do professors do?
• On a lighter note: Consider this when you attempt to cheat next time.