Three essays in the interface of optimization with mechanism design, nonexclusive competition, and prophet inequalities
Mekanizma tasarımı, münhasır olmayan rekabet ve kahin eşitsizlikleri ile eniyileme arayüzünde üç deneme
- Tez No: 761729
- Danışmanlar: PROF. DR. MUSTAFA ÇELEBİ PINAR, YRD. DOÇ. DR. NUH AYGÜN DALKIRAN
- Tez Türü: Doktora
- Konular: Ekonomi, Endüstri ve Endüstri Mühendisliği, Economics, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 130
Özet
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.
Özet (Çeviri)
Mechanism Design. We consider the mechanism design problem of a principal allocating a single good to one of several agents without monetary transfers. Each agent desires the good and uses it to create value for the principal. We designate this value as the agent's private type. Even though the principal does not know the agents' types, she can verify them at a cost. The allocation of the good thus depends on the agents' self-declared types and the results of any verification performed, and the principal's payoff matches her allocation value minus the verification costs. It is known that when the agents' types are independent, a favored-agent mechanism maximizes her expected payoff. However, this result relies on the unrealistic assumptions that the agents' types follow known independent probability distributions. We assume that the agents' types are governed by an ambiguous joint probability distribution belonging to a commonly known ambiguity set and that the principal maximizes her worst-case expected payoff. We consider three types of ambiguity sets: (i) support-only ambiguity sets, which contain all distributions supported on a rectangle, (ii) Markov ambiguity sets, characterized through first-order moment bounds, and (iii) Markov with independence ambiguity sets. For each of these ambiguity sets, we show that a favored-agent mechanism, which we characterize implicitly, is optimal and also Pareto-robustly optimal. The optimal choices of the favored agent and the threshold do not depend on the verification costs in all three cases. Nonexclusive Competition. A freelancer with a time constraint faces offers from multiple identical parties. The quality of the service provided by the freelancer can be high or low and is only known by the freelancer. The freelancer's time cost is strictly increasing and convex. We show that a pure-strategy equilibrium exists if and only if the preferences of the high-type freelancer satisfy one of the following two distinct conditions: (i) the high-type freelancer does {not} prefer providing his services for a price equal to the expected quality at the no-trade point; (ii) the high-type freelancer prefers providing his services for a price equal to the expected quality at any feasible trade point. If (i) holds, then in equilibrium, the high-type freelancer does not trade, whereas the low-type may not trade, trade efficiently, or exhaust all of his capacity. Moreover, the buyers make zero profit from each of their traded contracts. If (ii) holds, then both types of the freelancer trade at the capacity in equilibrium. Furthermore, the buyers make zero expected profit with cross-subsidization. In any equilibrium, the aggregate equilibrium trades are unique. Prophet Inequalities. Prophet inequalities bound the expected reward obtained in a class of stopping problems by the optimal reward of the corresponding offline problem. We show how to obtain prophet inequalities for a large class of stopping problems associated with selecting a point in a polyhedron. Our approach utilizes linear programming tools and is based on a reduced form representation of the stopping problem. We illustrate the usefulness of our approach by re-establishing three different prophet inequality results from the literature. (i) For polymatroids with nonnegative coefficients in their unique Minkowski sum of simplices, we prove the 1/2-prophet inequality. (ii) We prove the 1/n-prophet inequality when there are n stages, the stages have dependently distributed rewards, and we are restricted to choosing a strategy from an arbitrary polyhedron. (iii) When the feasible set of strategies can be described via K different constraints, we obtain the 1/K+1-prophet inequality.
Benzer Tezler
- Essays on education inequality of women in Turkey
Türkiye'de kadınların eğitim eşitsizlikleri üzerine makaleler
SERDAR POLAT
Doktora
İngilizce
2021
DemografiHacettepe ÜniversitesiDemografi Ana Bilim Dalı
PROF. DR. AHMET SİNAN TÜRKYILMAZ
- La solution proposee par revonsuo concernant le probleme difficile de la conscience
Bilincin zor problemi hakkında revonsuo tarafından önerilen çözüm
HATİCE GÜLAY EROL
Yüksek Lisans
Fransızca
2023
FelsefeGalatasaray ÜniversitesiFelsefe Ana Bilim Dalı
DOÇ. DR. SELAMİ ATAKAN ALTINÖRS
- Ekolojik ekonomi üzerine üç makale: AB ülkelerinde ekonomik büyüme, çevresel regülasyonlar ve teknolojik inovasyon
Three essays in ecological economics: Economic growth, environmental regulations and technological innovation in EU countries
ELİF KOÇAK
- The influence of ethnicity on consumer-brand interaction andengagement in a social media context
Başlık çevirisi yok
SİDDİK BOZKURT
- Bir iletişim arayüzü olarak kent: İz bırakma ve haritalama
The city as a communication interface: Tracing and mapping
HANDE SERMET TOPÖNDER
Yüksek Lisans
Türkçe
2015
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. DR. İPEK VEDİA YÜREKLİ İNCEOĞLU