Three essays in the interface of optimization with mechanism design, nonexclusive competition, and prophet inequalities

Mekanizma Tasarımı. Para alış verişi olmaksızın birkaç adaydan birine tek bir mal tahsis etmek üzerine bir mekanizma tasarım problemini ele alıyoruz. Her aday mala sahip olmak ister ve bunu mekanizma tasarımcısı için değer yaratmak için kullanır. Bu değer, her adaya özel ve mahremdir. Mekanizma tasarımcısı bu değerleri bilmese de, bir ücret karşılığında onları teftiş edebilir. Dolayısıyla, malın tahsisi, adayların kendi beyan ettikleri değerlere ve gerçekleştirilen herhangi bir doğrulamanın sonuçlarına bağlıdır. Mekanizma tasarımcısının kazancı, tahsis değerinden teftiş maliyetleri çıkarılınca bulunan değere eşittir. Adayların değerleri bağımsız dağıtılan rasgele değişkenler olduğunda, tercih edilen aday mekanizmasının beklenen getiriyi enbüyüklediği bilinmektedir. Ancak bu sonuç, aday değerlerinin bilinen ve bağımsız olasılık dağılımlarına göre belirlendiğine dair gerçekçi olmayan varsayımlara dayanmaktadır. Biz ise aday değerlerinin bağlı olduğu olasılık dağılımının herkesçe bilinen bir belirsizlik kümesine ait olduğunu, ve mekanizma tasarımcısının en kötü durumda gerçekleşen beklenen getirisini enbüyüklemek istediğini varsayıyoruz. Üç tür belirsizlik kümesini ele alıyoruz: (i) bir dikdörtgen içindeki tüm dağılımları içeren belirsizlik kümeleri, (ii) bir dikdörtgen içinde olan, adayların beklenen değerlerini de sınırlayan belirsizlik kümeleri ve (iii) bir dikdörtgen içinde olan, adayların beklenen değerlerinin sınırlandığı ve bağımsız olduğu belirsizlik kümeleri. Bu belirsizlik kümelerinin her biri için, eniyi ve ayrıca Pareto-gürbüz eniyi olan bir tercih edilen aday mekanizması olduğunu gösteriyoruz. Her üç durumda da, Pareto-gürbüz eniyi mekanizmayı tanımlayan aday ve eşik değerleri teftiş maliyetlerinden bağımsız olarak seçilebilir. Münhasır Olmayan Rekabet. Zaman kısıtlaması olan bir serbest çalışan, birden fazla potansiyel müşteriden gelen tekliflerle karşı karşıya kalır. Serbest çalışan tarafından verilen hizmetin kalitesi yüksek veya düşük olabilir, ve bu bilgi sadece serbest çalışan tarafından bilinir. Serbest çalışanın maliyeti dışbükeydir ve çalışma süresi arttıkça kesinlikle artar. Bir saf strateji dengesinin ancak ve ancak yüksek tipte serbest çalışanın tercihleri ​​aşağıdaki iki farklı koşuldan birini karşılıyorsa var olduğunu gösteriyoruz: (i) yüksek tip serbest çalışan, ticaret yapılmayan noktada hizmetlerini beklenen kaliteye eşit bir fiyata sunmayı tercih etmiyor; (ii) yüksek tip serbest çalışan, herhangi bir uygun ticaret noktasında hizmetlerini beklenen kaliteye eşit bir fiyata sunmayı tercih ediyor. Eğer (i) tutarsa, o zaman dengede, yüksek tip serbest çalışan ticaret yapmazken, düşük tip ticaret yapmayabilir, verimli ticaret yapabilir veya tüm kapasitesini tüketebilir. Ayrıca, alıcılar işlem gören sözleşmelerinin her birinden sıfır kar elde eder. Eğer (ii) tutarsa, o zaman dengede, her iki serbest meslek türü de kapasitede ticaret yapar. Ayrıca, alıcılar yüksek tiple yapılan alış verişten kar ederken, düşük tiple olan alışverişten zarar ederler. Her alıcının beklenen kazancı ise sıfırdır. Herhangi bir dengede, toplam denge işlemlerinin alabileceği tek bir değer vardır. Kahin Eşitsizlikleri. Kahin eşitsizlikleri, durdurma problemlerinde elde edilen beklenen ödülü, karşılık gelen çevrimdışı problemin eniyi ödülünü kullanarak sınırlar. Bir çokyüzlüden strateji seçilmesi de dahil, geniş bir durdurma problemi sınıfı için kahin eşitsizliklerinin nasıl elde edileceğini gösteriyoruz. Doğrusal programlama araçlarını kullanan çözüm yöntemimiz, durdurma probleminin indirgenmiş temsiline dayanmaktadır. Literatürden üç farklı kahin eşitsizliği sonucunu yeniden elde ederek yaklaşımımızın yararlılığını gösteriyoruz. (i) Eşsiz Minkowski Simpleks toplamında eksi değerler olmayan polymatroid'ler için 1/2-kahin eşitsizliğini ispatlıyoruz. (ii) Evre sayısı n olduğunda, evrelerdeki ödüller birbirlerine bağımlı dağıtıldığında ve herhangi bir çokyüzlüden strateji seçme kısıtı olduğuda, 1/n-kahin eşitsizliğini ispatlıyoruz. (iii) Seçilebilen strateji kümesi K adet kısıtlama ile tanımlanabildiğinde, 1/K+1-kahin eşitsizliğini elde ediyoruz.