Stability in Markets withPower AsymmetrybyBaharak RastgariM.Sc., The University of British Columbia, 2004B.Sc., Sharif University of Technology, 2002A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)December 2013? Baharak Rastgari 2013AbstractTwo classes of widely studied markets are auctions, such as eBay, and two-sided matching markets, such as matching medical residents to hospitals. Inboth of these markets, it often happens that one side is in power and caninfluence the outcome of the market?e.g., the seller in an auction.In the first part of this thesis we study two-sided matching markets inwhich participants are initially endowed with partial preference orderings.Our goal is to identify a matching that is stable and optimal for the side ofthe market that is in power, w.r.t. the underlying true preferences of theagents. We first investigate the extent to which we can learn about thismatching given the partial information. We then provide a novel model inwhich the true preferences are learned through interviews. Our goal is toidentify a centralized interviewing policy that returns our matching of interestwhile minimizing the number of interviews. We introduce three minimizationcriteria, of which the most desirable one is not always achievable. We providean exponential-time algorithm for computing a policy that satisfies the othertwo criteria, and exhibit evidence that a more efficient computation maynot be possible in general. We then show how to design a computationallyefficient interview-minimizing policy for a setting in which agents on one sideof the market are initially endowed with identical partial preferences, andagents must interview before getting matched.In the second part, we study combinatorial auctions (CAs), where multiplegoods are for sale and buyers are allowed to place bids on bundles, i.e. sets ofgoods. In single-good auctions the auctioneer is at no risk of losing revenueif more bidders compete in the auction. In CAs however, an auctioneer mayfind it profitable to disqualify bidders in order to be matched to a smallerset of bidders. We investigate the extent to which this counterintuitivephenomenon can occur under CA mechanisms that offer bidders dominantstrategies. We show that a broad class of deterministic CAs exhibit non-monotonicity in revenue. However, revenue monotonic CAs exist in thebroader domain of randomized mechanisms.iiPrefaceThe candidate contributed to all major ideas and writing of the publishedand unpublished manuscripts that are the basis of this thesis. The candidatewas the lead author in all published and unpublished manuscripts and inno instance was a co-author a student. The candidate collaborated withthe candidates? supervisors and mentors in all aspects of research includingmodeling the problems and proving the main claims.The introductory chapter, Chapter 1, was written by the candidate, butused selected content from publications that she co-authored [50, 53, 54].Research from Part I of the thesis was conducted in collaboration withthe candidate?s supervisors, Dr Anne Condon and Dr. Kevin Leyton-Brown,and mentors.? Chapter 2 is a collaboration between the candidate, Anne Condon,Kevin Leyton-Brown, Nicole Immorlica from Northwestern University,and Robert Irving from University of Glasgow.? A version of Chapter 3 appeared in the proceedings of the fourteenthACM Conference in Electronic Commerce (EC?13) [50], as a result ofa collaboration between the candidate, Anne Condon, Kevin Leyton-Brown, and Nicole Immorlica.Research from Part II of the thesis was conducted in collaboration withthe candidate?s supervisors, Anne Condon and Kevin Leyton-Brown.? A version of Chapter 4 was published in the Journal of ArtificialIntelligence [54]. A preliminary version of the main result in thischapter was published in the proceedings of the twenty-second AAAIConference in Artificial Intelligence (AAAI?07) [51]. A three-pagesummary also was published in SIGecom Exchange, Special issue oncombinatorial auctions [52].? A version of Chapter 5 appeared in the proceedings of the twentiethannual ACM-SIAM Symposium on Discrete Algorithms (SODA?09)[53].iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi1 Introduction to the Dissertation . . . . . . . . . . . . . . . . . 11.1 Two-sided matching with partial information . . . . . . . . . 21.2 Revenue monotonicity in combinatorial auctions . . . . . . . . 5I Two-sided Matching with Partial Information 72 Employer-optimal Matchings in Two-Sided Matching Mar-kets with Partial Information . . . . . . . . . . . . . . . . . . . 82.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.1.1 Optimal stable matchings . . . . . . . . . . . . . . . . . 92.1.2 Pervasive employer-optimal matchings and super-stability112.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3 Polynomial time algorithms . . . . . . . . . . . . . . . . . . . . 132.3.1 An algorithm to find a super-stable matching in SMP 132.3.2 An algorithm to check for a pervasive employer-optimalmatching . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.4 Necessary and impossible matches . . . . . . . . . . . . . . . . 232.4.1 Hardness of identifying impossible matches . . . . . . 232.4.2 Hardness of identifying necessary matches . . . . . . . 25ivTable of Contents2.5 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Determining the Employer-Optimal Matching with Mini-mum Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2 Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.2.1 Minimizing the number of interviews . . . . . . . . . . 323.3 Finding optimal policies . . . . . . . . . . . . . . . . . . . . . . 353.4 Finding minimum optimality certificates . . . . . . . . . . . . 383.5 Identical equivalence class orderings on one side of the market 413.6 Strict total orders with perturbation . . . . . . . . . . . . . . . 493.7 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . 55II Revenue Monotonicity in Combinatorial Auctions 574 Revenue Monotonicity in Deterministic, Dominant-StrategyTruthful Combinatorial Auctions . . . . . . . . . . . . . . . . . 584.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.1.1 Bidders . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.1.2 Combinatorial auction mechanisms . . . . . . . . . . . 604.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.3 Impossibility of revenue monotonicity . . . . . . . . . . . . . . 674.3.1 An example with an inefficient mechanism . . . . . . . 674.3.2 Impossibility theorem . . . . . . . . . . . . . . . . . . . 684.4 Related impossibility results . . . . . . . . . . . . . . . . . . . . 724.4.1 False-name-proofness . . . . . . . . . . . . . . . . . . . . 724.4.2 Monotonicity in the set of goods . . . . . . . . . . . . . 734.4.3 Outcomes in the Core . . . . . . . . . . . . . . . . . . . 744.5 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . 795 Revenue Monotonicity in Dominant-Strategy Truthful, Ran-domized Combinatorial Auctions . . . . . . . . . . . . . . . . . 805.1 Randomized combinatorial auctions . . . . . . . . . . . . . . . 805.1.1 Dominant strategy truthfulness for RCAM?s . . . . . 815.1.2 Revenue monotonicity for RCAM?s . . . . . . . . . . . 815.1.3 Maximality for RCAMs . . . . . . . . . . . . . . . . . . 815.1.4 Participation for RCAM?s . . . . . . . . . . . . . . . . . 825.1.5 Consumer sovereignty for RCAM?s . . . . . . . . . . . 825.2 Stepwise randomized mechanisms . . . . . . . . . . . . . . . . 83vTable of Contents5.3 A revenue monotonic mechanism . . . . . . . . . . . . . . . . . 845.3.1 Feasibility program . . . . . . . . . . . . . . . . . . . . . 855.3.2 Quadratically constrained linear program . . . . . . . 875.4 A polynomial time algorithm . . . . . . . . . . . . . . . . . . . 935.5 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . 95Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96AppendicesA Two-sided Matching: Proofs . . . . . . . . . . . . . . . . . . . . 102A.1 Hardness result . . . . . . . . . . . . . . . . . . . . . . . . . . . 102A.2 Identical strict total orderings for the applicants with 1-perturbation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104B Combinatorial Auctions: Formal Definitions . . . . . . . . . 107B.1 Bidders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107B.2 Deterministic CA mechanisms . . . . . . . . . . . . . . . . . . 108B.2.1 Properties of deterministic CA mechanisms . . . . . . 109B.2.2 Maximality . . . . . . . . . . . . . . . . . . . . . . . . . 111B.2.3 Impossibility results for general deterministic CA mech-anisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113B.3 Randomized CA mechanisms . . . . . . . . . . . . . . . . . . . 115B.3.1 Properties of randomized CA mechanisms . . . . . . . 115B.3.2 Weak maximality . . . . . . . . . . . . . . . . . . . . . . 115viList of Figures2.1 A setting with 2 employers and 2 applicants. Applicants havefull knowledge of their preferences; employers don?t. . . . . . . 102.2 The four possible underlying preference profiles for the em-ployers in the setting of Figure 2.1. . . . . . . . . . . . . . . . . 103.1 A setting with 3 employers and 3 applicants. Applicants areendowed with identical equivalence classes. . . . . . . . . . . . 443.2 Agents? preferences under total order ?1 that refines the settingdepicted in Figure 3.1. . . . . . . . . . . . . . . . . . . . . . . . . 453.3 Agents? preferences under total order ?2 that refines the settingdepicted in Figure 3.1. . . . . . . . . . . . . . . . . . . . . . . . . 453.4 Four of the possible strict preference orderings that refine asetting with 2 employers and 2 applicants with empty initialinformation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483.5 A setting with 4 employers and 2 applicants. Employers havefull knowledge of their preferences as shown in the table onright. Applicants? partial preference ordering is as depictedon the left: they both prefer e1 to e3 and e4. . . . . . . . . . . 503.6 Agents? preferences under total order ?. . . . . . . . . . . . . . 503.7 Agents? preferences under total order ??. . . . . . . . . . . . . . 503.8 A setting with 3 employers and 2 applicants. Employershave full knowledge of their preferences. Applicants? partialpreference orderings are as depicted on the left: they all prefere1 to e3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513.9 The three possible total orders for the applicants in the settingdepicted in Figure 3.8. . . . . . . . . . . . . . . . . . . . . . . . . 51viiList of Figures4.1 A high-level illustration of Theorem 60: Given ?{g1},v1?,?{g1, g2},v2? and ?{g3},v3??vi?s as constructed in the proofof the theorem?(1) Bidders 1 and 3 win bundle {g1} andbundle {g2} respectively and each pay more than a predefinedconstant amount, (2) bidder 3 wins bundle {g2} and paysmore than the sum of the payments in part (1). . . . . . . . . 684.2 Illustration of dependencies between the constructed valuesin the proof of Theorem 60: For example, the edge from v?1to v3 shows that v3 depends on v?1 ; the lack of edges to v?1shows that v?1 can be set freely. . . . . . . . . . . . . . . . . . . 684.3 Sketch of the proof of Theorem 60: Part 1 . . . . . . . . . . . . 694.4 Sketch of the proof of Theorem 60: Part 2 . . . . . . . . . . . . 695.1 i?s probability of winning as a function of her bid amount, givenfixed bids by the other agents. . . . . . . . . . . . . . . . . . . . . 845.2 Nonlinear feasibility program F (b,G). Constants are v? ?s andci,si ?s. Variables are piN,a?s, wN,i?s, pN,i?s and ?. We adopt theconventions thatN indexes subsets of N, i and l index elementsof N , si indexes elements of {0, . . . , ?}, and v? indexes elementsof V (b)N,G. Observe that because this last set is (uncountably)infinite, the feasibility program involves an infinite number ofboth variables and constraints. . . . . . . . . . . . . . . . . . . . 865.3 Quadratically constrained linear program P (V (b)N,G,G). Vari-ables are piN,a?s, qa,i?s and ?. We adopt the conventionsthat N indexes subsets of N, i indexes elements of N , siindexes elements of {0, . . . , ?}, and /?v indexes elements of/V (b)N,G = {v ?v ? V(b)N,G,?i ? N,?si ? {0, . . . , ?} ? vi = ci,si}. . . . . 895.4 Graph GRN for our three-bidder, two-good example. Each node(a, b, c) denotes (c1,a, c2,b, c3,c).The label corresponding to a1,3 ondirected edges from level k to k + 1 is ? and on directed edges fromlevel k + 1 to k is ??, 0 ? k < 3? ? 1. . . . . . . . . . . . . . . . . . 91viiiAcknowledgementsFirst and foremost, I would like to express my gratitude to my supervisors,Anne Condon and Kevin Leyton-Brown, for their guidance and help.Anne has been my mentor since shortly after my arrival to UBC. Herencouragements and invaluable advice were crucial for my progress duringboth my masters and doctoral studies. Thank you Anne, for being such awonderful mentor, for making time for me no matter how busy your schedulewas, and for being there for me when I needed you the most. Thank you forgiving me the freedom and support to peruse different research directions andfor supporting me when I was thinking of changing gears from bioinformaticsto game theory in the middle of my Ph.D. program. Without your fullsupport, I may have not taken the bold action of diving into a whole newarea of research! Thank you for teaching me how to be a scientist and ateacher. It has been a wonderful experience to know you and work alongsidewith you.Kevin was the person who introduced me to the field of Game Theory.Moreover, it was his multiagent systems class that made me fall in lovewith the whole concept of game theory. Kevin?s guidance was indispensablethroughout my doctoral studies. He taught me how to strive for excellenceand pay attention to the details. Thank you Kevin for all those long meetingsand in-depth discussions, which helped me think more critically and mademe a better researcher. Thank you, for all your help, advice and support.I would like to thank my supervisory committee members, Michael Petersand Joel Friedman, for their support and insightful feedback. My thanksalso go to the members of my examining committee, David Poole and We Li,and my external examiner, Vincent Conitzer, for the time and effort theyput into reading my thesis and for insightful and valuable comments andfeedback. I also thank all the anonymous reviewers who have reviewed myconference and journal submissions and have provided such valuable andconstructive feedback?it tremendously affected the quality of my work.Special thanks to my collaborators, Nicole Immorlica and Robert Irving.Thank you for your continuous support, and for helpful discussions andsuggestions which have benefited my research greatly.ixAcknowledgementsI am indebted to my family, many friends and wonderful teachers andmentors I have had throughout my lifetime, for what I am today and whereI have got so far. A big thanks to you all. If I am to name every single oneof you, the list will go on for pages. Hence, I have to be content with namingthe closest and the most recently acquainted.I owe so much to my caring and supportive parents, Amenah and Yadollah.Your love and unwavering support have been my greatest assets. You havesupported me in all my decisions, even when I chose to deal with numbers andequations instead of viruses and diseases :) Thank you, my dear sister andbrother, Tahmineh and Siavash, for your love, friendship, and for bringinglaughter and happiness to my life even in the gloomiest times.I would like to thank my friends and colleagues in Beta lab and LCI, inparticular GT-DT group. Thank you for your help with research problemsand for our fun discussions?my time in UBC was made much more enjoyableby your existence! More specifically, I would like to thank Dan Tulplan, SanjaRogic, Mirela Andronescu, Rosalia Aguirre-Hernandez, Hosna Jabbari, ChrisThachuk, Monir Hajiaghayi, Shelly Zhao, Dave Tompkins, Frank Hutter,Albert Jiang, Dave Thompson, James Wright and Chris Thornton. Sincerethanks to Chris for introducing me to the realm of Python and helping meregain my coding skills after so many years of proving theorems with a penand a paper.Special thanks to my (current and former) Vancouver-ian friends, inparticular Sara and Reza, Sara and Roozbeh, Sarah, Yalda and Navid, Goli,Anousheh and Mehran, and Nima. You have been my second family in thepast 11 years. Thank you for all your help and support, encouragements,friendship and love, and for bringing sunshine to my cloudy and rainy daysin Vancouver :) You are truly amazing, and I love you all!Thanks to the staff at the UBC Computer Science Department, inparticular Joyce Poon, Holly Kwan, Kath Imhiran, Lara Hall, Hermie Lam,and Michele Ng. You are wonderful people and make such a great team. Myexpectations are now so high that I doubt I will ever find another departmentas friendly and well supported by admin and tech staff as ours.Finally, thank you Misha for your unwavering support, encouragement,and the happiness you give me. Despite being frustrated at times for mystudies taking so long, I am very grateful to the universe for not letting megraduate few years earlier, and hence providing me with a chance to meetyou. You are the best.xDedicationTo mom & dad,Tahmineh & Siavash,and to Misha.xiChapter 1Introduction to theDissertationMarkets have been in use for a long time as a means to allocate scarceresources and exchange goods, services, and expertise. We all participatein various types of markets on a regular basis. Examples include: buyinggroceries from a supermarket, buying or selling goods on eBay, purchasingplane tickets and booking trips, running experiments on shared machinesand processors, and looking for a new job.Stability is a property highly desired by market designers. Consider atwo-sided matching market, for example the labor market for medical internsin which medical school students are matched with hospitals. Let M denotethe reported matching for this market. Assume that there is a hospital anda medical student who are not matched in M and prefer each other to theirassigned partners. Hence, M is susceptible to deviation by this pair as theyfind it in their interest to leave M and get matched together. In short, M isnot a stable solution.It often happens that one side of the market has the power or rightto influence the outcome of the market, for example when that side is incharge of designing or running the market, or when an outside authoritydecides to favor this side and give it more power. Take the labor marketfor medical interns. Assume that the hospitals decide to seek a centralizedmarket mechanism for hiring students, as they indeed did in 1950 [57]. Wealready argued in favor of a stable outcome. A market may however havemore than one stable solution, in which case one of them is to be picked.It is likely that a mechanism designed by the request of the hospitals picksthe stable matching that is in favor of the hospitals. In fact the NationalIntern Matching Program (NIMP) algorithm?later renamed to the NationalResident Matching Program (NRMP) algorithm, that was introduced in1952, and was in use until 1997, picks the stable matching that is optimal forthe hospitals (see, e.g., Roth [58]). In 1997, following controversies over theNRMP algorithm being unfair to the students, a new version was proposedand is in use since then; it picks the stable matching that the students like11.1. Two-sided matching with partial informationthe best (see, e.g., Roth and Peranson [59]).In this thesis, we study stability in two types of markets which usuallyexhibit power asymmetry: two-sided matching markets, such as the labormarket for medical interns introduced above, and auctions, such as eBay andFCC spectrum auctions.In the first part of this thesis, we focus on two-sided matching markets inwhich the participants are initially endowed with partial information abouttheir true preference orderings. For example, a medical intern applyingto different residency positions realistically cannot know his or her truepreference ordering over all available positions. Instead, s/he may knowwhat positions are his or her top-tier choices, which are his or her second-tierchoices, and so on.In the second part of this thesis, we focus on combinatorial auctions.Auctions are widely used to allocate resources among self-interested agents.In most auctions, it is the sum of the payments made by the bidders tothe auctioneer, the revenue, that the seller cares about the most. Thus,it is crucial to the stability of an auction?s outcome that revenue does notdecrease when more bidders are added to the auction. Otherwise, the sellermay find it profitable to disqualify bidders in order to be matched to asmaller set of bidders. In single-good auctions, probably the most familiartype, there is one good for sale and multiple potential buyers (bidders). Incombinatorial auctions, multiple goods are sold simultaneously and biddersare allowed to place bids on bundles, rather than just on individual goods.These auctions are interesting in settings where bidders have non-additivevalues for goods; goods may be complements where the value of a bundleis greater than the sum of the values of its parts, or substitutes, where thevalue is smaller. For example, two flight tickets for the same destination onthe same date are substitutes whereas a flight and a hotel reservation for thesame destination are complements. Combinatorial auction design aims fora fair and efficient allocation of goods by enabling bidders to express theirpreferences on bundles.1.1 Two-sided matching with partial informationTwo-sided matching markets model many practical settings, such as corporatehiring, marriage, and university admission. In such markets, participantsare partitioned into two disjoint sets?schools and students in an admissionsetting, for example. Each participant on one side of the market wishes to bematched to a candidate from the other side of the market, and has preferences21.1. Two-sided matching with partial informationover potential matches. A matching is called stable if no pair of participantswould prefer to leave their assigned partners to pair with each other. Amatching is optimal for one side of the market if each participant on that sideprefers that matching to any other stable matching. In their seminal work,Gale and Shapley [19] proposed an efficient algorithm for identifying optimalstable matchings. A rich literature has developed since. See the booksby Knuth 1976, Gusfield and Irving 1989, Roth and Sotomayor 1992, andManlove 2013 for excellent introductions and surveys (English translation ofKnuth 1976 is available as Knuth 1997).Overall, the study of matching has made contributions in both descriptiveand prescriptive senses. Descriptively, computational models have enrichedour understanding of existing social systems; for example, Gale and Shapley?swork helps us to understand marriage markets. Prescriptively, algorithmictools proposed in the literature are practical enough to be used directlyin applications, and indeed have transformed several matching markets.Perhaps most famously, the aforementioned NRMP algorithm (see, e.g., Roth[58]) matches American medical students to internships at hospitals, using amethod quite similar to the Gale?Shapley algorithm.Much of the matching literature makes the key assumption that all marketparticipants know their full (and often strict) preference orderings. Thisassumption is often reasonable, as attested by the practical impact justdescribed. However, as markets grow large it quickly becomes impracticalfor participants to assess their precise preference rankings. Returning tothe NRMP, in practice students typically interview at only 10?15 hospitalsout of about a thousand. The NRMP considers residents to have rankedas unacceptable all hospitals at which they did not interview, allowing thealgorithm to proceed as though a full preference ordering had been declared.Prescribing the use of this system is clearly suboptimal: students who makethe wrong decisions about where to interview can remain unmatched or bematched badly. There are likewise drawbacks from a descriptive perspective:such models shed little light on how matching works when participants areunsure about their preferences.In the first part of this thesis we focus on two-sided matching marketsin which agents are endowed with known partially ordered preferences andunknown true preferences drawn from known distributions consistent withthe partial order. For example, these preferences might be structured asranked equivalence classes, with the property that candidates in higher-ranked equivalence classes are preferred to those in lower-ranked classes.Each participant?s true (but unknown) preferences are a strict ordering overcandidates, consistent with the known partial order, and drawn from a known31.1. Two-sided matching with partial informationdistribution. In Chapter 2, we study the extent to which we can learn aboutthe stable matching that is optimal for the side of the market that is in power,w.r.t the underlying true, albeit unknown, preferences of the agents. We showthat we can decide in polynomial time whether there exists a unique matchingthat is stable and optimal under all strict total orders that refine the partialpreference orderings. If such a matching exists, we show how to identify itin polynomial time. Otherwise, we show that it is co-NP-complete to decidewhether a given pair of agents are matched in the optimal stable matching ofall, or none of the, underlying strict total orders. In Chapter 3, we proposea novel model in which the true preferences are learned through interviews,which reveal the pairwise rankings among all interviewed agents. For a givenparticipant, the first interview is uninformative; each subsequent interviewreveals pairwise rankings among all previously interviewed candidates. Ourgoal is to design an adaptive, centralized interviewing policy which, given anypartial information state, either selects an interview to perform or terminateswith an optimal stable matching.As interviews are costly, we would like our policy to minimize the numberof interviews performed. We propose three criteria according to which theeffectiveness of a policy can be assessed. First, a (very weakly) dominantpolicy performs a minimal number of interviews for all underlying truepreference profiles consistent with the partial information. Second, a Paretooptimal policy may not be minimal for all underlying preference profiles,but is guaranteed not to be dominated by any other policy. Finally, anoptimal-in-expectation policy minimizes the expected number of interviewswith respect to the known distribution of strict preference orders. Note thatthe first two of these notions are prior free: i.e., such policies are independentof the preference distribution, and so are also applicable in more generalsettings where there is no common prior. Note also that, as dominant policiesare Pareto optimal and optimal in expectation, the ideal is to compute adominant policy. However, as we show, dominant policies may not exist.Pareto optimal and optimal-in-expectation policies are guaranteed toexist; we show how to leverage a Markov Decision Process (MDP) encodingof our problem to find such policies in time polynomial in the number ofpossible preference orderings, which is exponentially faster than a naivealgorithm, but still exponential in the size of the input. The key question weinvestigate next is whether we can do better. We introduce the notion ofan optimality certificate, which is a matching and a set of interviews whoseoutcomes can be used to prove that the matching is stable and optimal fora given side of the market. We show that in general, finding an optimalitycertificate involving the minimum number of interviews is NP-complete. This41.2. Revenue monotonicity in combinatorial auctionssuggests that optimal-in-expectation and/or Pareto optimal policies mightbe hard to compute.We next consider a restricted setting in which participants on one sideof the market start out with the same equivalence classes, and in whichpairs of agents must interview before they can match. We show that in thissetting, minimum optimality certificates?and hence optimal policies?canbe computed efficiently. Indeed, our policy is optimal in the strongest sense:it is dominant, meaning that it is also prior free, Pareto optimal, and optimalin expectation with respect to any prior distribution that has full support.Lastly, we present preliminary investigations into extending this result toother settings.1.2 Revenue monotonicity in combinatorialauctionsIn the second part of this thesis, we study auctions. In two-sided matchingmarkets, participants on both sides are interested in acquiring some resourceor service that the other side is able to provide, and monetary transfersare not permitted. In auctions, agents on one side of the market?thebidders?are interested in acquiring goods, and the agent on other side ofthe market?the seller?is willing to sell goods in exchange for a monetarytransfer. The outcome of an auction not only specifies which bidders arematched to the seller, but also determines the amount each bidder has topay. The revenue of an auction is the sum of the payments made to theauctioneer. From single-good auctions, we have the intuition that addingbidders means more competition, and hence more revenue for the auctioneer.In this thesis we ask whether this intuition extends to combinatorial auctions.We provide two main results, one concerning deterministic and the otherconcerning randomized mechanisms.As with other applications of mechanism design, the design of combina-torial auctions has tended to focus on the theoretical properties that a givendesign can guarantee. It is often desired for an auction mechanism to offerbidders the dominant strategy of truthfully revealing their private informationto the mechanism. (By the revelation principle, the assumption that biddersdeclare truthfully is without loss of generality; however, not all mechanismsoffer dominant strategies.) Another desirable property is efficiency. A mech-anism is said to be efficient if it always chooses an allocation that maximizesthe social welfare. The VCG mechanism [10, 21, 66] has gained substantialattention because it offers dominant strategies to the bidders and allocates51.2. Revenue monotonicity in combinatorial auctionsgoods efficiently when bidders follow their dominant strategies. However, incombinatorial auctions using VCG, a seller can sometimes increase revenueby dropping bidders [5]. An auction is revenue monotonic if the seller?srevenue is guaranteed to weakly increase as the number of bidders grows.Revenue monotonicity is important because without it, the auctioneer hasan incentive to disqualify bidders to increase revenue. Similarly, in suchauctions a bidder might find it profitable to place pseudonymous bids inorder to reduce the seller?s revenue. We investigate the extent to whichthe counterintuitive phenomenon of revenue non-monotonicity can occurunder combinatorial auction mechanisms that offer dominant strategies tothe bidders.Our main result, in Chapter 4, is that such failures of revenue monotonicitycan occur under any deterministic, dominant-strategy truthful combinatorialauction mechanism that allows bidders to express arbitrary known single-minded preferences, even when we exchange efficiency for a weaker notionof weak maximality. Roughly speaking, a mechanism is weakly maximal ifit chooses allocations that cannot be augmented to cause a losing bidderto win without hurting winning bidders. A known single-minded bidderis interested in a single bundle of goods that is known to the auctioneer;the only piece of information the auctioneer is not aware of is the amountthe bidder values his or her bundle of interest. In our second main result,presented in Chapter 5, we demonstrate that revenue monotonic, dominant-strategy truthful mechanisms for known single-minded bidders can be foundin the broader class of randomized mechanisms. We show how they can beconstructed, by representing each mechanism as a solution to a quadraticallyconstrained linear program (QCLP). We prove that the QCLP is alwaysfeasible (i.e., for all bidder valuations) and give its solution analytically.Furthermore, we give an algorithm for running such a mechanism in timepolynomial in the number of bidders and goods; this is interesting becauseconstructing an instance of such mechanisms from our QCLP formulation ina naive way can require exponential time.6Part ITwo-sided Matching withPartial Information7Chapter 2Employer-optimal Matchingsin Two-Sided MatchingMarkets with PartialInformationIn this chapter we study two-sided matching markets in which agents areendowed with known partially ordered preferences and unknown true pref-erences that are strict total orders. We consider the case where the agentson one side of the market, say the employers, have the power to influencethe outcome, and look for a matching that is stable in a stronger sense thatis established in the literature. Our goal is to find a matching that is bothstable?i.e., no pair of participants would prefer to leave their assigned part-ners to pair with each other?and is (weakly) preferred by all the employersto any other stable matching. We investigate the extent to which we canlearn about this particular matching for the underlying true, albeit known,preferences of the agents.2.1 ModelLet A = {a1, . . . , an} be a set of applicants and let E = {e1, . . . , em} be aset of employers. We use the term agents when making statements thatapply both to applicants and employers, and the term candidates to referto agents on the side of the market opposite to that of an agent beingconsidered. We assume that each employer can hire at most one applicant,and that each applicant can be hired by at most one employer, hence focusingon one-to-one matching markets. Agents start out only partially aware oftheir preferences. Formally, each agent is initially aware of a strict partialpreference ordering over (a subset of) the candidates. We denote by peiand paj the strict partial preference ordering of ei and aj , respectively.We let pE,A = (pe1 , . . . , pem , pa1 , . . . , pan) and call pE,A a partial preference82.1. Modelordering profile. For example, agents might start out by assigning candidatesto equivalence classes, and having a strict preference ordering over theseequivalence classes. This equivalence class ordering is a natural model forscenarios in which each agent knows that some candidates are her top-tiercandidates, that others are her second-tier candidates, and so on. Figure 2.1of Example 4 depicts such a setting, with each agent?s partial preferenceordering partitioning the candidates into strictly ranked equivalence classes.Agents? true preferences are strict total orders: each applicant a has astrict preference ordering ?a over E ? {?}, and each employer e has a strictpreference ordering ?e over A ? {?}. If an agent i prefers ? to candidatej, we say j is unacceptable to i; all other candidates are acceptable to i.1We let ?E,A = (?e1 ,?e2 , . . . ,?em ,?a1 ,?a2 , . . . ,?an). The preference orderings?E,A are drawn according to a distribution whose support is consistent withthe partial preference ordering profile. That is to say, for each agent i, totalorder ? is in the support of the distribution, and for every pair of candidatesj and k: (i) if i prefers j to k according to the partial preference orderingprofile then i strictly prefers j to k under ?; and (ii) candidate j appearsin i?s partial preference ordering if and only if j is acceptable to i under ?.Furthermore, most of our definitions and results do not assume knowledgeof the distributions, and are thus prior free; i.e., the definitions and resultsapply regardless of the preference distribution.2.1.1 Optimal stable matchingsIn this work, we are focusing on two-sided matching markets in which oneside of the market has the power to influence the outcome. We assume thatthe employers, e.g. the hospitals in the labor market for medical interns,are on the powerful side. The goal of our work is to construct a matchingthat is stable with respect to the underlying preferences, and optimal for theemployers. We now define these notions mathematically.Definition 1 (Matching). A matching ? ? A ? E ? A ? E ? {?} is anassignment of applicants to employers such that each applicant is assignedto at most one employer and vice versa. More formally, ?(aj) = ei if andonly if ?(ei) = aj, for all aj ? A either there exists ei ? E such that ?(aj) = eior ?(aj) = ? (the applicant is unmatched), and likewise for all ei ? E eitherthere exists aj ? A such that ?(ei) = aj or ?(ei) = ?.1We assume that agents have strict preferences over unacceptable candidates only tosimplify notation.92.1. Modele1 e2a1 a1a2 a2a1 a2e1 e2e2 e1Figure 2.1: A setting with2 employers and 2 appli-cants. Applicants have fullknowledge of their prefer-ences; employers don?t.e1 e2a1 a1a2 a2(a)e1 e2a1 a2a2 a1(b)e1 e2a2 a1a1 a2(c)e1 e2a2 a2a1 a1(d)Figure 2.2: The four possible underlying pref-erence profiles for the employers in the settingof Figure 2.1.Definition 2 (Blocking pair). A pair (aj , ei) is a blocking pair with respectto matching ? if aj and ei are not matched together in ? and they prefereach other to their assigned partners?i.e., ei?aj?(aj), and aj?ei?(ei).Definition 3 (Stable matching). A matching ? is stable if it has no blockingpair and if no agent is matched to an unacceptable partner.Example 4. Consider the setting with 2 employers and 2 applicants depictedin Figure 2.1. The column corresponding to each agent i gives that agent?sstrict partial preference ordering, which is in fact an equivalence class or-dering, with the most preferred equivalence class at the top. In this exampleapplicants have full knowledge of their preferences, while employers have noknowledge of their preferences. Table 2.2 gives all four possible strict prefer-ence orderings for the employers. In every case, matching ?1, ?1(e1) = a1and ?1(e2) = a2, is stable. Matching ?2, ?2(e1) = a2 and ?2(e2) = a1, is alsostable under (c). ?2 is not stable in the other cases: (e1, a1) blocks ?2 under(a) and (b), while (e2, a2) blocks ?2 under (d).An employer-optimal matching is the matching most preferred by allemployers, as compared to all other stable matchings. When agents havestrict preferences, as in our model, an employer-optimal matching alwaysexists and is unique [19].Definition 5 (Employer-optimal matching). A matching is employer-optimalif it is stable and weakly preferred by all employers to every other stablematching.Example 6. Continuing Example 4, ?1 is the employer-optimal matchingunder cases (a), (b), and (d), and ?2 is the employer-optimal matching undercase (c).In a similar vein, we can define the applicant-pessimal matching.102.1. ModelDefinition 7 (Applicant-pessimal matching). A matching ? is applicant-pessimal if it is stable and all applicants weakly prefer every other stablematching to ?.A matching is employer-optimal if and only if it is applicant-pessimal [22,33].2.1.2 Pervasive employer-optimal matchings andsuper-stabilityWe are interested in the following question. Given an input I = (E,A, pE,A),do all strict total orderings that refine I have the same employer-optimalmatching ??Definition 8 (Pervasive employer-optimal (PEO) matching). Given an inputI = (E,A, pE,A) and a matching ?, we say that ? is a pervasive employer-optimal (PEO) matching w.r.t. I if and only if ? is the employer-optimalmatching w.r.t. all strict total orders that refine I.We call I an employer-optimal unique instance of the stable matchingproblem with partial information if and only if I admits a PEO matching.Our notion of pervasive employer-optimal matchings is closely relatedto the extensively studied notion of super-stability (see, e.g., Irving [24],Manlove [41]). Recall that we have assumed that the agents? true preferenceorderings are strict total orders. There is a large body of literature in whichthe preference model is instead augmented to include indifference betweencandidates. When indifference is allowed in the preference lists, it is not clearhow one should define stability. Three versions of stability have been definedin the literature (see, e.g., Irving [24]) including super-stability. Looselyspeaking, super-stable matchings are those that are stable no matter howindifferences in the preferences are resolved. It is worth nothing that inthis literature (see, e.g., Manlove [41]) indifference is not considered to benecessarily a transitive relation. That is to say, it is possible that an agentx is indifferent between agents y and z and also indifferent between agentsz and q, but strictly prefers y to q. A partial preference ordering in whichindifference is transitive is an equivalence class ordering.Definition 9 (Super-stable). A matching ? is super-stable if no agent ismatched to an unacceptable partner and there is no pair (ei, aj) who arenot matched together and each of whom either strictly prefers the other tohis/her partner in ? or is indifferent between them.112.2. Related workSuper-stable matchings can also be defined in our partial informationsetting by interpreting incomparability as indifference. Therefore, we say thatan agent x is indifferent between agents y and z, y ? z, under a given partialpreference ordering profile pE,A if x finds y and z incomparable. Observethat a matching is super-stable w.r.t. I if and only if it is stable w.r.t. allstrict total orderings that can be derived from pE,A by resolving indifferences.Hence, if a matching ? is to be the employer-optimal matching for everyrefinement of I, then ? must be a super-stable matching for I.Employer-optimal super-stable matchings can be defined analogously toemployer-optimal matchings.Definition 10 (Employer-optimal super-stable matching). A matching isemployer-optimal super-stable if it is super-stable and it is weakly preferredby all employers to every other super-stable matching.Super-stable matchings are not always guaranteed to exist. However, ifit turns out that a super-stable matching exists, then it is known that anemployer-optimal super-stable matching exists [41, 64]. Hence if there isa pervasive employer-optimal matching, it must be the employer-optimalsuper-stable matching. This claim, however, does not hold in the otherdirection. That is, even if the employer-optimal super-stable matching of Iexists, it may not be a pervasive employer-optimal matching?in which caseI does not admit a pervasive employer-optimal matching.Example 11. Continuing Examples 4 and 6, ?1 is the one and only super-stable matching for the setting depicted in Figure 2.1, and hence is theemployer-optimal super-stable matching for this setting. The employer-optimal matching for the strict preference ordering in case (c), depictedin Figure 2.2, is ?2. Therefore, ?1 is not a pervasive employer-optimalmatching.2.2 Related workAs stated above, there is a vast body of literature in which agents areallowed to declare indifference between two or more candidates (see, e.g.,Abdulkadiroglu and So?nmez [1], Irving [24], Irving and Manlove [28], Manlove[40, 41], Pathak [47], Scott [63]). For example, consider a school choice domainin which high school students are matched to public schools. Schools havesome preferences over students based on geography and legacy considerations,but many students are equivalent according to these measures and hence itis reasonable to say that the school is indifferent between them.122.3. Polynomial time algorithmsThree versions of stability have been defined in the literature (see, e.g., Irv-ing [24]) when indifference is allowed: weak stability, strong stability, andsuper-stability. When preferences are strict, the notions of weak, strong andsuper stability coincide. The notion of stability that we defined earlier, inSection 2.1.1, which is consistent with common usage in the literature, isweak stability in a setting where indifference is allowed. Strongly stableand super stable matchings are not always guaranteed to exist. Polynomialtime algorithms have been proposed for finding such matchings if they existor for reporting that none exists in various two-sided matching markets[24, 29, 30, 40]).2.3 Polynomial time algorithmsIn this section we show that we can decide, in polynomial time, whether ornot I is an employer-optimal unique instance. In proving our main claims,we build on results from the literature where indifference is allowed. In thisliterature?see, e.g., Manlove [40], Manlove et al. [43], the stable matchingproblem with ties, with incomplete lists (i.e. the agents are allowed to declaresome candidates unacceptable), and with both ties and incomplete lists arereferred to by SMT, SMI, and SMTI, respectively. For notational consistency,from now on we denote by SMP the stable matching problem with partialinformation, and by SMEC the stable matching problem with equivalenceclass ordering.The remainder of this section is organized as follows. We provide analgorithm, SUPER-SMP, that finds a super-stable matching for a giveninstance I of SMP, if such a matching exists. We show that if I admitssuper-stable matchings then SUPER-SMP outputs the employer-optimalsuper-stable matching Z. We then show how we can check, in polynomialtime, whether or not Z is a pervasive employer-optimal matching for I.2.3.1 An algorithm to find a super-stable matching in SMPIn this section we present SUPER-SMP, an algorithm that given an instanceI = (E,A, pE,A) of SMP identifies a super-stable matching for I if such amatching exists. It is an extension of the algorithms SUPER and SUPER2by Irving [24] and Manlove [40] for finding super-stable matchings in SMTand SMTI, which in turn are extensions of the deferred acceptance algorithm,proposed by Gale and Shapley [19], that finds the employer-optimal matchingin SMI. (Gale and Shapley in fact studied only SM, but their algorithmcan be easily extended to SMI.) SUPER-SMP finds the employer-optimal132.3. Polynomial time algorithmssuper-stable matching, if the set of super-stable matchings for I is not empty,otherwise it reports that no super-stable matching exists.Algorithm 1 gives a formal description of SUPER-SMP. Informally, thealgorithm can be described as a sequence of proposals by employers tothe applicants. After receiving one or more proposals, each applicant a (i)tentatively accepts the proposal she likes the best and becomes ?engaged?to the corresponding employer, e, and (ii) rejects the rest of the proposalsand declares all the employers she likes less than e to be unacceptable. Anapplicant a may receive two or more proposals that she likes the best andhence becomes multiply engaged. In this case, a rejects all the proposals anddeclares unacceptable (1) all the employers she likes less than one or moreof her best proposals, as well as (2) those she cannot compare with at leastone of her best proposals. Note that, as we will prove later, if a is indifferentbetween two or more employers who make proposals to her, then she can notbe matched to any of them in a super-stable matching, nor to any employerthat is incomparable to any of her best proposals.An employer e proposes to an applicant a if (i) e and a are not alreadyengaged, (ii) they are acceptable to each other, and (iii) there is no applicanta? that finds e acceptable whom e strictly prefers to a.The algorithm halts when no more proposals can be made. Let ? bethe engagement relation at the time when the algorithm halts. If ? is aone-to-one relation?i.e., each employer is engaged to at most one applicantand vice versa, and there is no applicant who has received a proposal butis not engaged in ?, then ? is the employer-optimal super-stable matching.Otherwise, no super-stable matching exists.In what follows, we say that agent z is a successor to agent y in x?spreference ordering under pE,A if agent x strictly prefers y to z. We use y?xzto mean that x strictly prefers y to z or is indifferent between them.When we say delete the pair (e, a), we mean that e should be deletedfrom the preference ordering of a, and a should be deleted from the preferenceordering of e. For any agent x, we refer to x?s preference ordering at thetermination of SUPER-SMP as x?s reduced preference ordering.At any stage of the algorithm, we say that an applicant a is at the headof an employer e?s preference ordering if there is no other applicant in e?sremaining preference ordering whom e strictly prefers to a. Note that morethan one applicant can be at the head of e?s preference ordering.To prove the correctness of SUPER-SMP, we follow a similar approach tothat taken in Irving [24] and Manlove [40]. The following lemmas are usefulin proving the main claim of this section, that SUPER-SMP is sound andcomplete, and are also interesting in their own right. The proofs, except for142.3. Polynomial time algorithmsAlgorithm 1: SUPER-SMPInput: I = (E,A, pE,A)Output: Matching ?Initializeproposed(a)? false,?a ? A ;repeatMain loop while some employer e has an applicant at the head of his preference orderingto whom he is not engaged doforeach applicant a at the head of e?s preference ordering doe proposes, and becomes engaged, to a ;proposed(a) ? true ;foreach strict successor e? of e on a?s preference ordering doif e? is engaged to a thenbreak the engagement ;delete the pair (e?, a);foreach applicant a who is multiply engaged doforeach employer e that a likes less than, or cannot compare with, at leastone of her fiances dodelete the pair (e, a);break all engagements involving a ;until each employer is either engaged to all applicants at the head of his preferenceordering, or has an empty preference ordering ;let ? be a maximum matching in the engagement relation ;Last check if some applicant a is unmatched in ? and proposed(a) thenreturn ?no super-stable matching exists?;elsereturn ? ;that of Lemma 14 and Corollary 16, are quite similar to the proofs of similarclaims in Irving [24] and Manlove [40].We begin by showing that for a given instance of SMP, the set of agentsmay be partitioned into two sets, those matched in all super-stable matchings,and those matched in none.Lemma 12. For a given instance of SMP, let ? and ?? be two super-stablematchings. Then for any agent x in the instance, x is matched in ? if andonly if x is matched in ??.Proof. Let I denote the given instance of SMP. Let J be an arbitrary instanceof SMI obtained from I by arbitrarily resolving indifferences in I. Both ? and?? are (weakly) stable in J . The claim hence follows by the Rural HospitalTheorem (see, e.g., Gusfield and Irving [22] and Manlove [42]) which states152.3. Polynomial time algorithmsthat for a given instance of SMI, the same agents are matched in all stablematchings. ?We next show that none of the pairs deleted by SUPER-SMP can blocka matching that the algorithm outputs.Lemma 13. If the pair (e, a) is deleted during an execution of SUPER-SMP,then that pair cannot block any matching output by SUPER-SMP.Proof. The proof is quite similar to the proof of Lemma 4.2 in Manlove[40]. Let ? be a matching output by SUPER-SMP, and suppose that (e, a)is deleted during an execution of the algorithm. Note that a pair, such as(e, a), is deleted only when a receives a proposal by an employer she strictlyprefers to e or when a is multiply engaged and she finds e incomparablewith at least one of her fiances. Also, since a has received proposals, thealgorithm does not output a matching in which she is unmatched. (Noticethat the last if statement of the algorithm, Last check, returns ?no super-stable matching exists? if there is an unmatched applicant who has receivedproposals.) Hence a is either (i) matched to an employer she prefers to e inthe output of SUPER-SMP, or (ii) the algorithm reports that no super-stablematching exists. Notice that (e, a) can not block ? if case (i) holds. Alsonote that the algorithm reports that no super-stable matching exists, ratherthan outputting ?, if case (ii) holds, a contradiction. ?Next we show that SUPER-SMP is sound.Lemma 14. A matching output by SUPER-SMP is super-stable.Proof. Suppose, for a contradiction, that some execution of SUPER-SMPoutputs a matching ? that is blocked by some pair (e, a). Thus e and a areacceptable to each other. By Lemma 13, the pair (e, a) has not been deleted,hence each is on the reduced preference ordering of the other.Let G be the engagement relation at the termination of the algorithm.Let EG and AG denote the set of employers and applicants engaged in G,respectively. Note that each applicant has degree at most one in G, thereforeeach employer e ? EG is matched in ? (or ? is not maximum). Also, eachapplicant a ? AG is matched in ?, as otherwise the algorithm reports that nosuper-stable matching exists, a contradiction. Since all agents engaged in Gare matched it must be the case that ?EG? = ?AG?. Furthermore, since eachapplicant has degree at most one in G, it must also be the case that eachemployer has degree at most one in G. Thus G is a one-to-one relation.162.3. Polynomial time algorithmsSince a is on the reduced preference ordering of e, it follows that e?sreduced preference ordering is nonempty and hence e must be engaged in Gto say a?. By the previous paragraph, e must be matched to a? in ?. Since(e, a) blocks ?, it follows that a ? a?. If e strictly prefers a to a?, then thepair (e, a) has been deleted, since a? is at the head of the reduced preferenceordering of e, a contradiction. Thus e can not compare a and a?.If a is at the head of the reduced preference ordering of e, then e musthave proposed to a and hence must be engaged to her in G, as otherwise(e, a) must have been deleted, a contradiction. Since a is engaged to e, andonly him, in G and has a partner in ?, thus she must be matched in ? to e.Therefore (e, a) is in ? and can not block ?, a contradiction.Thus a is not at the head of the reduced preference ordering of e andtherefore there is an applicant whom e strictly prefers to a. Since I is anstrict partial order and there is no cycle in the preference relation, there mustbe an applicant at the head of e?s reduced preference ordering, say a?, whome strictly prefers to a. We have already established that e can not comparea and a?, therefore a? ? a?. Since a? is at the head of the reduced preferenceordering of e, therefore e must have proposed to a? and consequently beengaged to her in G, as otherwise (e, a?) must have been deleted and a?shall not be in e?s reduced preference ordering, a contradiction. Therefore eis engaged to at least two applicants, a and a?, contradicting the previouslyestablished fact that G is a one-to-one relation. ?We say that a pair (e, a) is a super-stable pair if e and a are matched ina super-stable matching. We next show that SUPER-SMP preserves all suchpairs.Lemma 15. No super-stable pair is ever deleted during an execution ofSUPER-SMP.Proof. The proof is almost identical to the proof of Lemma 4.4 in Manlove[40]. Suppose, for a contradiction, that (e, a) is the first super-stable pairdeleted during the execution of the algorithm for some given instance I ofSMP. Thus e and a are acceptable to each other. Let ? be a super-stablematching in which e and a are partners.Case 1. Suppose that (e, a) is deleted as a result of some other employer,say e?, becoming engaged to a. Then a strictly prefers e? to e. Also, there isno super-stable matching in which e? has a partner, say a?, whom he strictlyprefers to a; for then the super-stable pair (e?, a?) would have been deletedbefore (e, a) during the execution of the algorithm, a contradiction. So thesupposed super-stable matching ? is blocked by (e?, a), a contradiction.172.3. Polynomial time algorithmsCase 2. Suppose that (e, a) is deleted as a result of a being multiplyengaged. If e? is any employer who was engaged to a at that point, then e?cannot have a super-stable partner a? whom he strictly prefers to a; for thenthe super-stable pair (e?, a?) would have been deleted before (e, a) duringthe execution of the algorithm, a contradiction. So once again the supposedsuper-stable matching ? is blocked by the pair (e?, a), a contradiction. ?The next corollary then follows by Lemmas 15, 14, and 12.Corollary 16. The matching that SUPER-SMP outputs is the employer-optimal super-stable matching.Proof. By Lemma 14 SUPER-SMP outputs a super-stable matching. Let? be the super-stable matching output by SUPER-SMP. Assume, for acontradiction, that ? is not the employer-optimal super-stable matching Z.Thus there must be an employer, say e, who is matched in Z and strictlyprefers Z(e) to his match in ?. Thus, (e,Z(e)) must have been deletedduring the execution of SUPER-SMP for e to propose to ?(e). (Note that,by Lemma 12, since e is matched in Z he must also be matched in ?.)However, by Lemma 15, no super-stable pair is deleted during the executionof SUPER-SMP, a contradiction. ?We next prove that the check at the end of the SUPER-SMP correctlyidentifies cases where no super-stable matching exists.Lemma 17. If, during the execution of SUPER-SMP, some applicant re-ceives a proposal and is unmatched in the maximum matching ? , then nosuper-stable matching exists for the given instance.Proof. The proof is quite similar to the proof of Lemma 3.5 in Manlove [40].Let e be an employer who proposes to a during execution of the algorithmand let G be the engagement relation at the termination of the algorithm.Suppose, for a contradiction, that there is a super-stable matching ?? for thegiven instance. Suppose first that a is unmatched in ??. If e is unmatchedin ?? then (e, a) blocks ??, since e and a are mutually acceptable. Thus ehas a partner, say x, in ??. If e strictly prefers x to a, then in order for eto propose to a, the super-stable pair (e, x) would have been deleted by thealgorithm, a contradiction to Lemma 15. Thus either e is indifferent betweena and x, or e strictly prefers a to x. In either case (e, a) blocks ??.Therefore a has a partner, say e?, in ?? (possibly e = e?). Now e? is engagedto some applicant in G. For if not, then the reduced preference ordering ofe? is empty, so that e? has no stable partners by Lemma 15, a contradiction.182.3. Polynomial time algorithmsNote that each applicant has degree at most one in G, therefore each employere engaged in G is matched in ? (or ? is not maximum). Thus e? has a partner,say a?, in ?. As (e?, a) ? ? , then a ? a?. If e? strictly prefers a to a?, then thesuper-stable pair (e?, a) would have been deleted in order for e? to proposeto a?, a contradiction to Lemma 15. Thus e? is either indifferent between a?and e, or e? strictly prefers a? to a.We claim that, for each i ? 1, there is a sequence of distinct employerse1, . . . , ei, and a sequence of distinct applicants a0, . . . , ai, such that1. a0 = a.2. (ei, ai) ? ? and (ei, ai?1) ? ??.3. ei either strictly prefers ai to ai?1 or is indifferent between them.The proof is similar to that of Lemma 12 and proceeds by induction on i.The base case i = 1 clearly holds with e1 = e?, a0 = a and a1 = a?. Supposethat the claim holds for i = r, r ? 1. We show that the claim holds for i = r+1.Suppose that ar is unmatched in ??. Since (er, ar) ? ?, er and ar find eachother acceptable. By Condition 3 above, either er strictly prefers ar to ar+1,or is indifferent between them. Hence (er, ar) blocks ??, a contradiction.Thus ar has a partner, say er+1, in ??. Clearly er+1 ? ej for any j, 1 ? j ? r.Now er+1 is engaged in G, for if not, then the reduced preference orderingof er+1 would be empty, meaning that er+1 would have no stable partnersby Lemma 15, a contradiction. As shown above, ? matches every employerwho is engaged to at least one applicant in G, so that er+1 has a partner,say ar+1, in ?. Clearly ar+1 ? aj for any j, 1 ? j ? r, and ar+1 ? a0 as a0 = ais unmatched in ?. If er+1 strictly prefers ar to ar+1, then the super-stablepair (er+1, ar) would have been deleted in order for er+1 to propose to ar+1,a contradiction to Lemma 15. Thus er+1 either strictly prefers ar+1 to ar oris indifferent between them. This completes the induction step.We have a finite set of agents, whereas i can get infinitely large. Hencewe reach a contradiction. Thus no super-stable matching exists for the giveninstance. ?Lastly, we show that SUPER-SMP is sound and complete.Theorem 18. For a given instance of SMP, SUPER-SMP determines, inpolynomial time, whether or not a super-stable matching exists. If such amatching does exist, all possible executions of the algorithm find one in whichevery employer has as good a partner (and every applicant as bad a partner)as in any super-stable matching.192.3. Polynomial time algorithmsProof. The proof is quite similar to the proof of Theorem 4.6 in [40]. LetI be the given instance of the SMP. First, we argue that the main loop ofthe algorithm terminates. If at the end of some iteration of the main loopsome employer e has some applicant at the head of his preference orderingto whom he has not proposed, then e proposes to such applicants in the nextiteration. There are at most n ?m such proposals, hence the terminationcondition is guaranteed to be satisfied in polynomial time.Let ? be a maximum matching in the final engagement relation. If someapplicant who is unmatched in ? has received a proposal during executionof the algorithm, then I has no super-stable matching, by Lemma 17. Ifthere is no such applicant, then SUPER-SMP outputs the matching ?. ByLemma 14, ? is super-stable and by Corollary 16, ? is in fact the employer-optimal super-stable matching.At most n ?m proposals are made during the execution of SUPER-SMPand at most n?m pairs are deleted. Thus, with suitably chosen data structures,the algorithm has an O(n ?m) worst-case time bound. ?2.3.2 An algorithm to check for a pervasiveemployer-optimal matchingIn this section we show that given an instance I of SMP, which admitssuper-stable matchings, and Z, the employer-optimal super-stable matchingof I, we can decide in polynomial time whether Z is the employer-optimalmatching for every refinement of I.Recall that a matching is the employer-optimal matching if and only if itis the applicant-pessimal stable matching. Irving and Leather [26] showedthat a matching ? is applicant-pessimal if there is no rotation exposed in?. We are going to use this notion in the main proof of this section, so weprovide a brief definition of an exposed rotation here. For more details see,e.g., Irving [25], Irving and Leather [26], and Gusfield and Irving [22].Definition 19 (Exposed rotation). Let ? be a stable matching for an instanceI of SMI. For each applicant a, we define the next-best employer for a relativeto ?. Let ??(a) denote the the first employer e on a?s preference ordering,following ?(a), such that e prefers a to his match under ?, ?(e). If a is notmatched to ?(a) in ?e, the employer-optimal matching of I, then ??(a) mustexist, since ?e(a) qualifies. Otherwise, it is undefined. A rotation exposedin ? is a cyclic sequence of pairs (a0, e0), ..., (ar?1, er?1) such that ?(ai) = eiand ??(ai) = ei+1, for all i, i + 1 taken modulo r.202.3. Polynomial time algorithmsWe next construct a directed graph G(I) that facilitates the search forpotential rotations in Z. Create a vertex in G for each applicant in theinstance, and an edge (a,Z(e)) for each employer e ?M(a), where e is inM(a) if and only if1. Z(a)?ae; and2. a?eZ(e); and3. there is no employer e? such that Z(a)?ae?, e??ae and a?e?Z(e?).In other words, e ?M(a) if and only (1) e is a successor to Z(a) in a?spreference ordering and (2) e either strictly prefers a to Z(e) or is indifferentbetween them, and (3) there is no other employer e? whom a strictly ranksbetween Z(a) and e, such that e? strictly prefers a to Z(e?).Theorem 20. For a given instance I of SMP that admits a super-stablematching, the employer-optimal super-stable matching Z is pervasive if andonly if the graph G(I) is acyclic.Proof. We first show that if G(I) contains a cycle then there is an SMIinstance I ? that is a refinement of I for which Z is not the employer-optimalmatching. Suppose that (ai0 , ai1 , . . . , air?1) is a cycle in G(I), and let eij =Z(aij) for 0 ? j ? r ? 1. We break indifference in I to construct I? in thefollowing way. (Here and elsewhere, subscripts are taken modulo r.)? In the preference ordering of aij , place eij+1 ahead of any employerwith whom he is incomparable;? in the preference ordering of eij+1 place aij ahead of any applicant withwhom she is incomparable;? in the preference ordering of any other employer e, place Z(e) aheadof any applicant with whom she is incomparable;? break all other indifferences arbitrarily.Define the matching ? so that ?(aij) = eij+1 for 0 ? j ? r ? 1 and ?(a) = Z(a)for all other applicants a. It follows from the precedence given to aij inindifference-breaking eij+1 ?s preference ordering that, in I?, no employer isworse off in ? as compared to Z. We claim that ? is stable in I ?, and thus Zcannot be the employer-optimal matching for I ?.Suppose that (e, a) blocks ? in I ?. If ?(a) = Z(a), then (e, a) blocksZ in I ?, contradicting the super-stability of Z. So a = aij for some j. But212.3. Polynomial time algorithms?(aij) = eij+1 , so aij prefers e to eij+1 in I?, and e prefers aij to ?(e) in bothI and I ?, and hence also to Z(e) in I ?. If, in I ?, aij prefers e to eij , then(aij , e) blocks Z, contradicting the super-stability of Z. Otherwise, becauseof the precedence given to eij+1 in tie-breaking aij ?s preference ordering, aijmust prefer e to eij+1 in I, but this contradicts condition 3 used in definingM(a) for the construction of G(I).Now suppose that there is a refinement I ? of I for which Z is not theemployer-optimal matching, and hence not the applicant-pessimal match-ing. It follows that, with respect to Z in I ? there is an exposed rotation(ai0 , ei0), . . . , (air?1 , eir?1). We claim that, in the graph G(I), (ai0 , . . . , air?1)forms a cycle.According to the definition of a rotation, eij+1 is the first successor eof eij on aij ?s preference ordering in I? such that e prefers aij to Z(e) inI ?? and thus in I either strictly prefers aij to Z(e) or is indifferent betweenthem. It follows that eij+1 ? M(aij). Suppose that this were not the case.Then, in I, aij prefers eij+1 to eij = Z(aij) or is indifferent between them.But, in I ?, eij+1 prefers aij to aij+1 = Z(eij+1) and so, in I, eij+1 prefers aijto aij+1 = Z(eij+1) or is indifferent between them. It follows that the pair(aij , eij+1) blocks Z as a super-stable matching, a contradiction. Therefore,(aij , aij+1) is an edge of G(I). Hence the rotation yields a cycle in G(I). ?Theorem 21. Given an instance I of SMP, we can decide in polynomialtime whether I is an employer-optimal unique instance and, if it is, returnthe pervasive employer-optimal matching.Proof. To check whether a given instance I of SMP is an employer-optimalunique instance, we apply the following 2-step algorithm.1. Apply the SUPER-SMP algorithm, Algorithm1 in Section 2.3.1. If nosuper-stable matching exists, then there can be no pervasive employer-optimal matching, return ?none exists?. Otherwise the algorithm givesus the employer-optimal super-stable matching Z.2. Construct G(I), given I and Z, as described above. Check whetherG(I) is acyclic. If so, return Z, otherwise return ?none exists?.We first verify the correctness of the above algorithm. Note that, by Theo-rem 18, SUPER-SMP returns the employer-optimal super-stable matching ofI, Z, if I admits super-stable matchings. As discussed earlier in Section 2.3,I does not admit a pervasive employer-optimal matching if it does not admitsuper-stable matchings. Furthermore, by Theorem 20, Z is pervasive if andonly if G(I) is acyclic. It remains to show that the above two steps take222.4. Necessary and impossible matchespolynomial time. By Theorem 18, SUPER-SMP halts in O(n ?m) time. It isstraightforward to verify that the construction of the directed graph G(I)takes O(n ?m) time and so does testing whether G(I) contains a cycle. Hencethe overall algorithm has O(n ?m) time complexity. ?2.4 Necessary and impossible matchesIn the previous section, we showed that we can decide in polynomial timewhether a given instance I is employer-optimal unique. What if I doesnot admit a pervasive employer-optimal matching? Can we still identify ifthere exist identical ?components? among the matchings that are employer-optimal w.r.t. some refinement of I? In this section we tackle this questionby studying the following two closely related problems. First, we investigatewhether one can identify pairs that are not matched in the employer-optimalmatching for any of the strict total orders that refine I. Next, we studywhether one can identify pairs that are matched in the employer-optimalmatching for all of the strict total orders that refine I.Definition 22 (Impossible matches). Given I, a pair (e, a) is an impossiblematch if for all ? that refine I, e and a are not matched in the employer-optimal matching of ?.Definition 23 (Necessary matches). Given I, a pair (e, a) is a necessarymatch if for all ? that refine I, e and a are matched in the employer-optimalmatching of ?.Unfortunately, identifying impossible and/or necessary matches is hardeven if (i) the given instance of SMP is in terms of equivalence classes (thatis it is an instance of SMEC), (ii) all applicants have the same partial orders,and (iii) all agents consider all the agents on the other side of the market tobe acceptable.2.4.1 Hardness of identifying impossible matchesThe proof of our next claim, on the hardness of identifying impossible matches,uses the same construction as in the hardness proof given by Irving et al. [27]for a related problem (Theorem 5.1 in Irving et al. [27]). Since our proofsin this section and the next make use of some terms and settings defined orused in Irving et al. [27], we briefly define those here.A master list of employers consists of a single list containing all of theemployers, which may or may not contain ties. Each applicant?s preference232.4. Necessary and impossible matchesordering contains her acceptable partners ranked precisely according to themaster list. A master list of applicants? and resulting employers? preferencesare defined analogously. Extensions -2ML and -1ML denote problem variantsinvolving master lists on both sides and on one side of the market respectively.For example, SMTI-2ML represents the Stable Matching problem with Tiesand Incomplete Lists, with a Master List on both sides.Irving et al. [27] show that COMPLETE SMTI-2ML, the problemof deciding whether a given instance of SMTI-2ML admits a completestable matching, is NP-complete even if ties occur only in the master list ofapplicants. Note that because of this latter assumption, employers must allbe endowed with strict total orders which are [almost] identical except thatsome employers may have declared some applicants unacceptable. We provethat identifying impossible matches is hard by reducing from this problem.Theorem 24. For a given instance of SMEC, and a given (employer, appli-cant) pair (e, a), it is co-NP-complete to decide whether (e, a) is an impossiblematch, even if all applicants have the same equivalence classes and all agentsare acceptable to the agents on the other side of the market.Proof. To see that the problem is in co-NP, we describe a nondeterministicpolynomial-time algorithm to determine that (e, a) is not an impossiblematch. The algorithm simply guesses a strict total order ?, verifies that ? isconsistent with the given SMEC instance and, by using the Gale-Shapleyalgorithm, that e and a are matched in the employer-optimal matching of ?.To prove co-NP-hardness, we show that the complement of the problem isNP-hard by reducing from the variant of COMPLETE SMTI-2ML in whichties occur only in the master list of applicants, which is NP-complete byTheorem 3.1 in Irving et al. [27]. Let J be an instance of this problem, whereLe and La are the master lists of employers and applicants respectively. LetE = {e1, . . . , en} be the set of employers and A = {a1, . . . , an} be the set ofapplicants in J . Let Qei be the preference ordering of each employer ei underJ . (Note that Qei may include ties.) We construct an instance I of ourproblem. Let the set of employers in I be E ? {e0} and the set of applicantsbe A? {a0}. The partial preference ordering for each agent in I is as follows.? e0 ? ?? a0? ei ? Qi a0 ??? a0 ? Le e0? ai ? Le e0242.4. Necessary and impossible matchesIn a given partial preference ordering, the symbol ?? denotes all remainingagents on the opposite side of the market in arbitrary strict order. Clearly allapplicants have the same equivalence classes with e0 being the only memberof the lowest ranked equivalence class. We show that J admits a completeweakly stable matching if and only if (e0, a0) is not an impossible match inI.Suppose that ? is a complete (weakly) stable matching for J . Let?? = ? ? {(e0, a0)}. We prove that ?? is stable w.r.t. some total order ?that refines I. Then we show that (e0, a0) belongs to the employer-optimalmatching of ?, which proves that (e0, a0) is not an impossible match. Let? be a total order where each agent ranks his partner under ?? at the topof his/her corresponding class. To see that ?? is stable w.r.t. ?, note thatneither (e0, ai) nor (ei, a0) can block ??. It remains to show that (ei, aj),1 ? i, j ? n, can not block ??. To see this, note that for (ei, aj) to be ablocking pair (1) aj must be in Qei , since ??(ei) is, (2) ei must rank aj ina higher equivalence class than ??(ei), and (3) aj must rank ai in a higherequivalence class than ??(aj). However this means that under J both eiand aj strictly prefer each other to their partners under ?, thus they block?, a contradiction. Let ??e denote the employer-optimal matching of ?. Bydefinition, every employer must like his partner under ??e at least as well ashis partner under ??. Assume for a contradiction that (e0, a0) ? ??e. Since??e is a complete matching (which it must be as the preference orderingsare complete), then (ei, a0) ? ??e for some ei, 1 ? i ? n. However ei strictlyprefers ??(ei) to a0?his match under the employer-optimal matching, acontradiction.Conversely, assume that there exists a total order ? that refines I suchthat (e0, a0) belongs to ??s employer-optimal matching, ??. Clearly ?? isa complete matching for I and so is ? for J . It remains to show that ?is weakly stable under J . Note that ? matches every employer ei to anacceptable partner under J (and thus every applicant aj to an acceptablepartner as well). For if not, then ei strictly prefers a0 to ??(ei). Since a0strictly prefers ei to e0?who is her partner under ???then (ei, a0) blocks??, a contradiction. Clearly ? is (weakly) stable in J , as otherwise any pairthat blocks ? in J would also block ?? in I. ?2.4.2 Hardness of identifying necessary matchesIn this section we show that the problem of deciding whether a given pairis a necessary match is co-NP-complete. The next theorem will come inhandy in proving the aforementioned hardness result. Let ANY-STABLE252.4. Necessary and impossible matchesSMTI-1ML denote the problem of deciding, given an instance of SMTI-1MLand an applicant a, whether there is a stable matching in which a is matched.We show that this problem is NP-complete.Theorem 25. The ANY-STABLE SMTI-1ML problem is NP-complete.Proof. The structure of the proof is similar to that of Theorem 5.1 in Irvinget al. [27]. To see that the problem is in NP, we describe a nondeterministicpolynomial-time algorithm to determine that a given applicant a is matchedin a stable matching of a given instance of SMTI-1ML. The algorithm simplyguesses a matching ? and verifies its stability by examining all potentialblocking pairs and furthermore checking that each agent is matched to anacceptable partner. To show NP-hardness, we transform from COMPLETESMTI-2ML which is shown to be NP-complete (by Theorem 3.1 in Irvinget al. [27]). Let J be an instance of this problem where Le denotes themaster list of employers. Let E = {e1, . . . , en} be the set of employers andA = {a1, . . . , an} be the set of applicants in J . Let Qei denote the preferenceordering of ei and Qaj denote the preference ordering of aj under J . Weconstruct an instance J ? of our problem as follows. Let the set of employersin J ? be E ? {e0} and the set of applicants be A ? {a0}. The preferenceordering for each agent in J ? is as follows.? e0 ? ?? a0? ei ? Qei? a0 ? e0? ai ? Qai e0In a given partial preference ordering, the symbol ?? denotes all remainingagents on the opposite side of the market in arbitrary strict order. We obtaina master list L?e of employers in J? by appending e0 to Le. We show that Jhas a complete stable matching if and only if there is a stable matching forJ ? in which a0 is matched.Suppose that ? is a complete (weakly) stable matching for J . Let?? = ? ? {(e0, a0)}. We claim that ?? is a (weakly) stable matching in J ?. Tosee this, first note that (ei, a0) cannot block ??, as e0 is the only employeracceptable to a0. Furthermore, (ei, aj), 1 ? i, j ? n, cannot block ?? asotherwise the pair would also block ? under J . It remains to show that(e0, aj), 1 ? j ? n cannot block ??. To see this, note that all applicants in Aare matched in ?, and hence ??, and they all prefer their partners to e0.262.4. Necessary and impossible matchesConversely, assume that J ? has a stable matching ?? such that (e0, a0) ? ??.We prove that ? = ???{(e0, a0)} is a complete stable matching for J . Clearly? is stable under J , otherwise any pair that blocks ? would also block ??. Itremains to show that ? is a complete matching. Assume for a contradictionthat it is not. Then there exists an applicant aj , 1 ? j ? n, who is unmatchedunder both ? and ??. However, e0 is acceptable to all applicants, and soto aj , and prefers all applicants in A to a0. Therefore, (e0, aj) blocks ??,contradicting the assumption that ?? is stable. ?We are now ready to prove our main claim in this section, that identifyingnecessary matches is hard. To prove this claim, we reduce from ANY-STABLE SMTI-1ML that we just proved is NP-complete.Theorem 26. For a given instance of SMEC, and a given (employer, appli-cant) pair (e, a), it is co-NP-complete to decide whether (e, a) is a necessarymatch, even if all applicants have the same equivalence classes and all agentsare acceptable to the agents on the other side of the market.Proof. To see that the problem is in co-NP, we describe a nondeterministicpolynomial-time algorithm to determine that (e, a) is not a necessary match.The algorithm simply guesses a strict total order ?, verifies that ? is consistentwith the given SMEC instance and, by using the Gale-Shapley algorithm,that e and a are not matched in the employer-optimal matching of ?. Toprove co-NP-hardness, we show that the complement of the problem is NP-hard by reducing from ANY-STABLE SMTI-1ML that we just showed, inTheorem 25, is NP-complete. Let J be an instance of this problem whereLe denotes the master list of employers. Let E = {e1, . . . , en} be the set ofemployers and A = {a1, . . . , an} be the set of applicants in J . Let Qei denotethe preference ordering of ei and Qaj denote the preference ordering of ajunder J . Without loss of generality, we can assume that Qei does not containan applicant who finds ei unacceptable, and similarly, Qaj does not containan employer who finds aj unacceptable. Let a? ? A be any given applicantin this setting. We construct an instance I of our problem as follows. Letthe set of employers in I be E ? {e?} and the set of applicants be A. Thepreference ordering for each agent in J ? is as follows.? e? ? a?? ei ? Qei , ?ei ? E, ei ? e?? ai ? Le e?, ?ai ? A272.5. Chapter summaryWe obtain the identical equivalence classes for the applicants by appendinge? to the end of Le.Note that Qei does not contain applicants who find ei unacceptable (inaddition to not containing applicants whom ei finds unacceptable). Further-more, e? finds all applicants except a? unacceptable. Hence the preferenceordering of each applicant ai ? A, ai ? a?, under I essentially reduces to Qai ,and the preference ordering of a? reduces to Qa?e?.It is then straightforward to verify that e? and a? are matched in allstable matchings for I, and hence in the employer-optimal matching forall refinements of I, if and only if a? is unmatched in all stable matchingsfor J . Hence (e?, a?) is not a necessary match if and only if the answer toANY-STABLE SMTI-1ML given J and a? is yes. So the co-NP-hardness ofour problem follows from the NP-completeness of ANY-STABLE SMTI-1ML.?2.5 Chapter summaryWe investigated what we can learn or reason about regarding employer-optimal matchings in settings with partial information. We showed that givenan instance of a stable matching problem with partially ordered preferences,we can decide in polynomial time whether all total orders that refine theinstance have the same employer-optimal matching. We then showed thatdeciding whether a pair belongs to the employer-optimal matching of all(or none) of the refinements is co-NP-complete, even in some very specialcases. Thus, even though we might be able to identify such pairs efficientlysometimes?e.g., our first polynomial result shows that we can do so if everypossible pair appears in the employer-optimal matching of either all or noneof the refinements?this is unfortunately not always the case.28Chapter 3Determining theEmployer-Optimal Matchingwith Minimum CostIn this chapter, we extend our model of two-sided matching given partially-ordered preferences to say that participants can refine these preferencesthrough interviews. Each interview reveals the pairwise rankings among allpreviously interviewed candidates. Our goal is to design an adaptive andcentralized policy which, given any partial information state, either selectsthe next interview or terminates with a matching that is guaranteed tobe employer-optimal w.r.t. the true underlying strict preference orderings.As interviews are costly, we seek a policy that minimizes the number ofinterviews.3.1 Related workWe are aware of three threads of related work. The first augments the pref-erence model to include indifference between candidates, which we discussedin the previous chapter, Section 2.2. However, this literature (e.g., Pathak[47] and Abdulkadiroglu and So?nmez [1]) is not intended to fully address theproblem of incomplete preferences, and indeed it does not.A second thread of related work sets up the matching problem as aBayesian game, assuming that participants have strict preferences drawnaccording to a commonly known probability distribution over preferenceorderings, and that all participants know their own preferences once the drawhas taken place. Work in this vein typically seeks to design Bayes?Nashincentive compatible mechanisms or to describe the Bayes?Nash equilibriaof standard mechanisms (see, e.g., Roth and Sotomayor [60]). One recentpaper augments such Bayesian models with interviews, which are costly andchosen in a decentralized fashion [38]. The authors investigate equilibriuminterviewing behavior and observe that ?clustered interviews? yield high293.2. Policiessocial welfare. However, they do not insist that the final matching be stablewith respect to agents? true preferences.A third thread of work tries to derive properties of the market basedon the available partial information. In recent work, Echenique et al.[15]study settings in which agents? preferences are unobserved. They charac-terize matchings that are rationalizable?i.e., stable w.r.t. some underlying(unobserved) preference, as well as those that are rationalizable and optimalfor one side of the market. An assumption crucial to most of their resultsis that the agents on each side of the market have different (unobserved)preference orderings, and it is known how many agents in the market haveeach possible preference ordering. Their work differs from ours in severalways; notably, we allow for preferences to be partially observed, and look formatchings that are stable and optimal for a given side of the market w.r.t.all possible underlying preference orderings (as opposed to only one). In arecent working paper, Haeringer and Iehle [23] study matching markets inwhich the preferences of one side of the market are known, but the agents onthe other side of the market only know whom they find acceptable. Haeringerand Iehle provide a technique for identifying pairs that are not matched inany stable matching for any underlying preference ordering, and hence foridentifying unstable matchings.3.2 PoliciesWe have defined stability of a matching in terms of agents? true preferences(as distinct from Lee and Schwarz [38]); thus, it will generally not be possibleto find a stable matching based on agents? initial knowledge. To find andcertify a stable matching, employers and applicants must gather additionalinformation about each other through interviews. Each interview pairs asingle applicant a with a single employer e; we denote such an interview e?a.After interview e?a, both e and a are able to strictly order the acceptablecandidates interviewed so far.Informally, a policy describes how to conduct interviews: it starts withinput I = (E,A, pE,A)?where E is the set of employers, A is the set ofapplicants, and pE,A is the agents? partially-ordered preference profile, per-forms a sequence of interviews, and then outputs a matching. Interviewscan be selected based on the results of previous interviews and the wholeprocedure is centralized. More formally, a policy maps information states tosubsequent interviews or to a matching that is stable and employer-optimalfor the underlying preference profile. To reduce notation, from this point on303.2. Policieswe assume that the input I = (E,A, pE,A) is given and fixed.Definition 27 (Information State). The information state Ii of agent iafter interviews with ` ? 0 candidates is a list of these ` candidates, orderedaccording to the underlying true preference profile. When ` = 0, we let Ii = ?.The global information state after a sequence of interviews is I = ?i?E?A Ii.We say that information state I refines partial preference ordering profilepE,A, which we write as I ? pE,A, if I is consistent with pE,A: for all agentsi and all candidates j and k, i preferring j to k under pE,A implies i alsopreferring j to k under I. Given a fixed pE,A and information states I andI ? that refine pE,A, we say that I ? refines I when it contains strictly moreinformation: when for all agents i, all candidates who were interviewed inIi were also interviewed in I ?i , and for all candidates j and k who wereinterviewed in both Ii and I ?i , i preferring j to k under Ii implies i preferringj to k under I ?i . We say that a preference profile ? refines an informationstate I, and write ? ? I, if ? is consistent with both pE,A and I. We write? ? pE,A to denote that ? is consistent with pE,A.Definition 28 (Policy). A policy is a mapping from a global informationstate I ? pE,A either to an interview to perform or to a matching. A policy issound if it is guaranteed to return an employer-optimal matching, regardlessof the true preference order ? ? pE,A.Notice that a sound policy is allowed to return a matching in which apair of agents e and a are matched even without e having interviewed a. Inpractice, employers may face the requirement of interviewing an applicantbefore offering her a job. We capture this additional requirement throughthe notion of a diligent policy.Definition 29 (Diligent policy). A policy is diligent if it is sound and,furthermore, it maps from I to ? only if e ? Ia and a ? Ie for all (e, a) ? ?.Example 30. Continuing Example 6 from Section 2.1.1, a sound policyfollows: given an information state I, if e1 has not interviewed a1, schedulethe interview e1 ?a1; else if e1 has not interviewed a2, schedule the interviewe1 ?a2. Otherwise, if e1 prefers a2 to a1: if e2 has not interviewed a1 schedulethe interview e2 ?a1; else if e2 has not interviewed a2, schedule the interviewe2 ?a2. These interviews are sufficient to distinguish between the underlyingpreference orderings that give rise to different employer-optimal matchings;hence, for the remaining information states, the policy can simply outputa matching. If e1 prefers a1 to a2, the true underlying ordering is (a) or313.2. Policies(b), and so return ?1. If e1 prefers a2 to a1 and e2 prefers a2 to a1, thetrue underlying ordering is (d), and so again return ?1. Otherwise, the trueunderlying ordering is (c), and so return ?2.The above sound policy can be made into a diligent policy by the followingmodification: If e1 prefers a1 to a2, have e2 interview a2 first and then return?1.3.2.1 Minimizing the number of interviewsIt is not hard to identify a sound policy: e.g., simply instruct all employersto interview all applicants and then run the Gale?Shapley algorithm to findthe employer-optimal matching. However, this policy is likely to performunnecessary interviews. We are motivated by the intuition that in reality,interviews are very costly; thus, we seek sound policies that minimize theirnumber. However, there is a problem. Because policies select interviewschedules dynamically, the number of necessary interviews may dependnot only on the policy?s input, but also on the true underlying preferenceorderings. What does it mean, then, to say that a sound policy performs theminimal number of interviews given an input I?One straightforward answer is to say that we should minimize the expectednumber of interviews with respect to a prior distribution over preferenceorderings. Let ?(f,?, pE,A) denote the number of interviews that policy fperforms when the true underlying preference profile is ? ? pE,A.Definition 31 (Optimal in expectation). A policy f is optimal in expec-tation if it is sound and it minimizes the expected number of interviewsperformed, given a prior Pr. That is, for all sound policies g, ???pE,A Pr(?) ??(f,?, pE,A) ? ???pE,A Pr(?) ? ?(g,?, pE,A).This objective has a major drawback: optimal-in-expectation policies arenot robust with respect to changes in the setting, i.e., they are not prior-free.We would prefer a sound policy that performs no more interviews than anyother sound policy, regardless of the underlying preference profile.Definition 32 (Very weak domination). A policy f very weakly dominatesanother sound policy g if and only if f performs no more interviews thang for any underlying preference profile. That is, ?(f,?, pE,A) ? ?(g,?, pE,A)for all ? ? pE,A.This dominance notion is called ?very weak? because two algorithms canvery weakly dominate each other by always performing the same number ofinterviews for every ?.323.2. PoliciesDefinition 33 (Very weakly dominant policy). A policy f is very weaklydominant if it is sound and it very weakly dominates any other sound policyg.We would like to find a very weakly dominant policy. Unfortunately, suchpolicies do not always exist.Theorem 34. There exist inputs for which no very weakly dominant policyexists.Proof. Consider the setting given in Figure 2.1. To certify that ?1 is employer-optimal for (a) or (b), we only need e1 to interview a1 and a2, to distinguish(a) from (c). To certify that ?1 is employer-optimal for (b) or (d), we onlyneed e2 to interview both candidates, to distinguish (d) from (c). Thus anypolicy that instructs e1 to perform any interviews?e.g. the policy describedin Example 30?is dominated in case (d), and any policy that instructs e2 toperform any interviews is dominated in case (a). ?Motivated by this impossibility result, we consider the weaker, but stillprior-free, notion of Pareto optimality.Definition 35 (Pareto domination). A policy f Pareto dominates anotherpolicy g if and only if both policies are sound, f very weakly dominates gand, furthermore, ?? ? pE,A such that ?(f,?, pE,A) < ?(g,?, pE,A).Definition 36 (Pareto optimal policy). A policy f is Pareto optimal2 ifthere does not exist another policy g that Pareto dominates f .For example, the policy described in Example 30 is Pareto optimal. Becauseof the strict inequality, Pareto domination is an asymmetric relation. Thuswe can not have cycles in Pareto domination, and soProposition 37. A Pareto optimal policy always exists.Now we briefly survey relationships between our solution concepts. Veryweak dominance is the strongest guarantee we can hope for: if we can findsuch a policy, it will also be Pareto optimal and optimal in expectation.Furthermore, every optimal-in-expectation policy is guaranteed to be Paretooptimal when the prior distribution has full support.2Pareto optimality is an extension of the standard concept of optimality to multiobjectivesettings. In game theory, the notion is traditionally used to reason about settings in whichthere is ane objective function corresponding to each agent?s utility function. We applythe notion differently here: we do not have an objective function per agent, but ratheran objective function (counting the number of interviews performed) per strict preferenceprofile that refines the given partial information.333.2. PoliciesProposition 38. If a policy f is optimal in expectation and Pr has fullsupport, then f is Pareto optimal.Proof. Assume for contradiction that f is not Pareto optimal. Thus there ex-ists a policy g that Pareto dominates f . Therefore, ?(g,?, pE,A) ? ?(f,?, pE,A)for all ? ? pE,A and ?(g,?, pE,A) < ?(f,?, pE,A) for at least one ? ? pE,A.Since Pr has full support, Pr(?) > 0 for all ? ? pE,A. Therefore, ???pE,A Pr(?)??(f,?, pE,A) > ???pE,A Pr(?) ? ?(g,?, pE,A), which implies that f does notminimize the expected number of interviews performed, a contradiction. ?All of the definitions in this section are stated in terms of sound policies.All of this section?s definitions and results can be extended to diligent policiessimply by replacing every occurrence of ?sound? with ?diligent?. For example,f is a very weakly dominant, diligent policy if it is diligent and it very weaklydominates any other diligent policy g. Unfortunately, the nonexistence resultof Theorem 34 can be straightforwardly extended to very weakly dominant,diligent policies.3Theorem 39. There exist inputs for which no very weakly dominant, diligentpolicy exists.Proof. Consider the same setting that we analyzed in the proof of Theorem 34,given in Figure 2.1. Note that at least one employer has to interviewboth applicants, or we can not distinguish between the four possible cases.Furthermore, all matched agents should interview each other, hence theother employer must interview at least one applicant. Therefore, any diligentpolicy performs at least three interviews before returning a matching.To certify that ?1 = {(e1, a1), (e2, a2)} is employer-optimal for (a), weneed e1 to interview both candidates a1 and a2, to distinguish (a) from(c). Then, to have all matched agents intervie each other, we only need toadditionally have e2 to interview a2. To certify that ?1 is employer-optimalfor (d), we need e2 to interview both candidates, to distinguish (d) from(c). Then, to have all matched agents interview each other, we only needadditionally to have e1 interview a1. Thus any diligent policy that instructse1 to interview first is Pareto dominated in case (d) and any diligent policythat instructs e2 to interview first is Pareto dominated in case (a). ?3Indeed, in what follows we will often observe that results that hold for sound policiesalso hold for diligent policies. However, important differences between the two kinds ofpolicies emerge in Section 3.5.343.3. Finding optimal policies3.3 Finding optimal policiesTo compute an optimal-in-expectation (or Pareto optimal) policy, we couldperform a brute-force search, considering every policy in turn. Let S denotethe set of global information states. Note that a policy may choose to performany of the possible n ?m interviews in any given global information state.Hence the number of distinct policies is ?((n2)?S?)?w.l.o.g., we assume thatn ?m. Thus, brute-force search requires time exponential in the number ofinformation states. The number of global information states is maximizedin the case where agents initially rank all candidates in one big equivalenceclass. In this special case, the number of strict total orders that refine thepartial preference ordering profile would be equal to (n!)m ? (m!)n, hence?S? ? (n!)m ? (m!)n. Therefore, the size of S is ?((n!)2n) for this specialworst case. Hence, brute-force search would take time ?((n2)((n!)2n)). Inthis section we show how to do better.We begin by identifying information states in which a sound policy canterminate and return a matching; i.e., in which enough information has beengathered that a policy can be sure of the employer-optimal matching.Definition 40 (Optimality certificate). A triple (I, ?, pE,A) is an optimalitycertificate if ? is employer-optimal w.r.t. all ? ? I.In other words, an optimality certificate is an information state thatadmits a pervasive employer-optimal matching.Define the size of an optimality certificate (I, ?, pE,A) as the number ofinterviews performed in I. A minimal optimality certificate is an optimalitycertificate that cannot be made smaller by dropping an interview.Definition 41 (Minimal optimality certificate). A triple (I, ?, pE,A) is aminimal optimality certificate if ? is employer-optimal w.r.t. all ? ? I, andthere is no smaller optimality certificate (I ?, ?, pE,A) such that I ? I ?.Notice that a triple (I, ?, pE,A) could be an optimality certificate evenif a pair of agents, say e and a, are matched in ? but have not interviewedtogether according to I. To certify the outputs of diligent policies, we alsodefine diligent optimality certificates.Definition 42 (Diligent optimality certificate). A triple (I, ?, pE,A) is adiligent optimality certificate if ? is employer-optimal w.r.t. all ? ? I and,furthermore, e ? Ia and a ? Ie for all (e, a) ? ?.Paralleling our earlier definitions, a diligent minimal optimality certificateis a diligent optimality certificate of minimal size.353.3. Finding optimal policiesTheorem 43. An optimal-in-expectation policy can be computed in timepolynomial in ?S?.Proof. We leverage the planning paradigm of MDPs [see, e.g., Puterman[48]]. An MDP is a tuple (S,A,C, T, s0, F ), where S is a finite set of states;A is a finite set of actions; C is a cost function where C(s, i, s?) representsthe cost of taking action i in state s and transitioning to state s?; T is atransition function where T (s, i, s?) denotes the probability that action iin state s leads to state s?; s0 denotes the system?s initial state; and Fdenotes a set of terminal states. Intuitively, our MDP encoding will workas follows. We start at an empty global information state and take actionscorresponding to interviews, paying a cost of 1 for every interview performed.The effect of an action is to transition to a new information state that refinesthe previous state in the appropriate way, with new rankings being revealedaccording to conditional probabilities derived from the prior. We reach aterminal state when we have gathered enough information to stop conductinginterviews. Formally, let S denote the set of global information states, Adenote the set of all possible interviews, and C(I, e?a,I ?) = 1 for all e?a, Iand I ?. Let T (I, e?a,I ?) = Pr(I?)Pr(I) if I? refines I and has exactly one moreinterview than I, that interview being e?a, and T (I, e?a,I ?) = 0 otherwise,where Pr(I) = ???I Pr(?). Let s0 be the empty global information state:I where Ii = ? for all i. Finally, we will define F as the set of informationstates such that I ? F if all preference profiles that refine I have the sameemployer-optimal matching, and there is no I ?, I ? I ? for which the sameproperty holds.We compute F as follows. We will iteratively refine a mapping h frominformation states to matchings, which will store all information states thatwe know to be safe stopping points for a sound policy. (In fact, h storesminimal optimality certificates.) Initially, let h map every information stateto the null matching, in which no agent is matched. A sound policy canclearly stop when it reaches an information state I that admits a pervasiveemployer-optimal matching (see Definition 8). Thus, for all such informationstates I let h(I) = ?I , where ?I is the employer-optimal matching forany preference profile that refines I. Initialize Q to be the set of all suchinformation states, and initialize F to be the empty set. We repeat thefollowing until Q is empty. Select an arbitrary information state I from Qsuch that h(I) does not map to the null matching. Now, make a linear passover Q, asking whether there exists a second information state I ? such thath(I) = h(I ?) and there exists a pair (e, a) where removing e from Ia and I ?aand removing a from Ie and I ?e yields the same global information state I?.363.3. Finding optimal policiesIf so, remove both I and I ? from Q, add I? to Q and let h(I?) = h(I). Ifno such I ? exists, remove I from Q and add it to F . The computation of Ftakes polynomial time in the number of states since (i) initializing Q can bedone in polynomial time, by a linear pass over all information states I ? Sand checking whether I admits a pervasive employer-optimal matching?byTheorem 21 this test can be done in polynomial time, (ii) each pass over Qtakes time O(n ?m ? ?S?), and (iii) at least one information state is removedfrom Q in each pass.Our MDP is finite horizon because we always reach a terminal statewithin n ?m actions (i.e., performing all interviews). Therefore, a standardresult from the literature on MDPs applies: a policy that minimizes expectedcost can be computed in time linear in the number of states via the backwardinduction algorithm (see, e.g., Puterman and Patrick [49]). This policy issound by the construction of F , and hence is optimal in expectation. ?An optimal-in-expectation diligent policy can be computed in time poly-nomial in ?S?. The proof is almost identical to the one given for Theorem 43with the modifications that (1) h stores minimal diligent optimality certifi-cates, and (2) we remove I and I ? from Q and add I? if, in addition to theconstraints stated in the proof, the pair (e, a) does not belong to h(I) = ?I .Overall, our MDP formulation yields an exponential time algorithm foridentifying an optimal-in-expectation policy. To see this, let us compute anupper bound on the size of S for the special case we discussed at the beginningof this section, where agents rank all candidates in one big equivalence class.Each strict total order corresponds to at most (2n)m global information states,hence ?S? ? (n!)m ?(m!)n ?(2n)m. Therefore, the size of S is O(2n2?(n!)2n) forthis special worst case. While our algorithm provides us with an exponentialimprovement over brute-force search, we would prefer a polynomial-timeguarantee. (We do note, however, that one advantage of MDP formulations?in our domain and elsewhere?is that well-structured problem instancescan be solved tractably even when the problem is intractable in the worstcase.) Our MDP formulation made little use of the structure of the matchingproblem, so we have reason to hope that better worst-case performancemight be possible. One hurdle is that explicitly stating a policy requiresexponential space, and hence at least exponential time, as the number ofinformation states is exponential. However, one could hope to do bettersimply by executing an optimal policy that can be described in polynomialspace and executed in polynomial time. The rest of this paper asks whetherthere are provably better ways of executing optimal policies.373.4. Finding minimum optimality certificates3.4 Finding minimum optimality certificatesWe now turn to the computational problem of finding an optimality certificate(recall Definition 40) that certifies the employer-optimal matching for agiven preference profile in as few interviews as possible. (Contrast withDefinition 41, which only required the local property that an optimalitycertificate would not remain valid after dropping an interview.) Such anoptimality certificate would have to be identified by any very weakly dominantpolicy, and would likely be useful for optimal-in-expectation policies as well.Definition 44 (Minimum optimality certificate for ?). (I, ?, pE,A) is a(diligent) minimum optimality certificate for a preference profile ? if ? isemployer-optimal w.r.t. ?, ? ? I, and if there does not exist a smaller(diligent) optimality certificate (I ?, ?, pE,A) such that ? ? I ?.Theorem 45. A sound (or diligent) policy f is very weakly dominant (anddiligent) if and only if it computes a (diligent) minimum optimality certificatefor every preference profile ? ? pE,A.Proof. Exactly the same argument suffices for both sound and diligent policies.To prove the first direction, assume for contradiction that f is not very weaklydominant. Then there must exist a policy g and a preference profile ? suchthat ?(g,?, pE,A) < ?(f,?, pE,A). Let ? be ??s employer-optimal matching andI be the information state after performing interviews that g performs under?. For g to be sound, (I, ?, pE,A) must be an optimality certificate. Thus fdoes not compute a minimum optimality certificate for ?, a contradiction.To prove the second direction, assume for contradiction that a minimumoptimality certificate is not computed for some preference profile ?. Let(I, ?, pE,A) be a minimum optimality certificate for ?. Take the set ofinterviews corresponding to I, Z, and order them arbitrarily. Let the policyg be as follows: if no interview has taken place, schedule the first interviewin Z; else if the first interview has taken place, schedule the second interview,and so on until all interviews in Z have taken place; if all the interviews in Zhave taken place and the current global information state is I, return ?, elseperform all possible interviews and return the employer-optimal matching ofthe corresponding total order. Clearly g is sound and computes the minimumoptimality certificate for ?. Thus ?(g,?, pE,A) < ?(f,?, pE,A) and therefore gdominates f on ?, a contradiction. ?Unfortunately, the problem of computing a minimum optimality certificateis NP-complete.383.4. Finding minimum optimality certificatesDefinition 46 (Optimality Certificate (OC) decision problem). Given (E,A, pE,A), a preference profile ? that refines pE,A and a bound K, decidewhether there exists an optimality certificate (I, ?, pE,A) of size at most Kwhere ? is employer-optimal w.r.t. ?.Theorem 47. The optimality certificate decision problem is NP-complete,even if the partial preference ordering is an equivalence class ordering.Proof. It follows directly from Theorem 18 that the OC decision problemis in NP. It remains to show that this problem is NP-hard. The proof is byreduction from the feedback arc set (FAS) problem [32]. Let G = (V,D) bea directed graph with no self-loops or multiple arcs. The feedback arc setproblem is to decide whether there exists a set of arcs C of size ? K suchthat C contains at least one arc from every directed cycle in G; i.e., suchthat removing all arcs in C breaks all directed cycles of G. We construct aninstance of the optimality certificate (OC) problem from (G,K) as follows.For each vertex i in G, create employers ei and e?i and applicants ai anda?i. For each employer ei, create a single equivalence class of acceptablecandidates, containing applicant ai and every aj where (i, j) is an arc inD. For each employer e?i, create a single equivalence class of acceptablecandidates containing applicants ai and a?i. For each applicant ai, create twoequivalence classes of acceptable candidates. Let the top class contain ei ande?i, and let the second class contain any ej where (j, i) is an arc in D. Foreach applicant a?i, create a single equivalence class of acceptable candidatescontaining only e?i. Finally, let ? be any preference profile under which eachei most prefers the corresponding ai, each employer e?i most prefers a?i, eachapplicant ai ranks ei at top, and each applicant a?i most prefers e?i. Observethat matching ? where ?(ei) = ai and ?(e?i) = a?i is employer-optimal w.r.t.?. To complete the proof we show that G has a FAS of size at most K ifand only if there exists an optimality certificate of size at most K + 2n for ?.The proof has two parts:1. Let (I, ?, pE,A) be an optimality certificate of size K ?. Let S be a setof arcs such that (vi, vj) ?D iff ei ?aj ? I. We claim that S is of size atmost K ? ? 2n and removing all the arcs in S breaks all the cycles in G.2. Let S be a solution of size K to the feedback arc set problem. Let I bean information state consistent with ? under which each ei, 1 ? i ? n,has interviewed ai and all applicants aj such that (vi, vj) ? S, andfurthermore, each employer e?i, ?1 ? i ? n, has interviewed ai. We claimthat (I, ?, pE,A) is an optimality certificate of size K + 2n for ?.393.4. Finding minimum optimality certificatesProof of (1): by contradiction. First note that I must include eitherboth interviews ei ?ai and e?i ?ai, or both interviews e?i ?ai and e?i ?a?i, ?1 ? i ? n.Otherwise, a total ordering ? ? I exists under which ai and e?i rank each otherat the top and hence must be matched in the employer-optimal matching;this contradicts the fact that (I, ?, pE,A) is an optimality certificate. Thus,there are at most K ? ? 2n interviews in I that are of type (ei, aj), and sothe size of S is at most K ? ? 2n.Assume that removing S does not break all the cycles in G. Let C bean unbroken cycle. For each edge (vi, vj) in C it must be the case thatei ?aj /? I. Let ?? be a matching in which ??(ei) = ?(e?i) = a?i if ei is not inC, and ??(ei) = ?(ej) if (ei, ej) is in C. Let ?? be a strict ordering underwhich each employer e?i likes a?i the best, each employer ei not in C likes aithe best (as in ?), and each ei in C likes aj the best, where (ei, ej) is inC. Note ?? is consistent with I. Furthermore, employers not in C have thesame applicant on the top of their list as in ? (which should be consistentwith the outcome of the interviews in I), and for employers in C their truepreferences between their partners in ? and ?? haven?t been revealed yet(since no interview between such an employer and his match under ?? hastaken place). Note that ?? is the employer-optimal matching for ?? and so? is not the employer-optimal matching for ??. Thus (I, ?, pE,A) is not anoptimality certificate for ?, a contradiction.Proof of (2): By contradiction. First note that it is easy to see, fromthe construction of I, that ?I ? = K + 2n. Assume that (I, ?, pE,A) is notan optimality certificate for ?. Thus, there exists a preference ordering ??consistent with I for which ? is not the employer-optimal matching. Weknow that ? is a stable matching under any preference ordering consistentwith I (it is the applicant-optimal matching indeed). Thus, it should bethe case that there is some other stable matching ?? that the employerscollectively prefer to ? (some are indifferent and some prefer ??). Therefore,there has to be a set of employers ec1 , . . . , ecl such that ??(eci) = ?(eci+1) fori < l and ??(ecl) = ?(ec1). If not, then there exists an unmatched employerand unmatched applicant who both prefer to be matched together than stayunmatched, thus ?? is not stable. Note that eci must prefer his match in ??to his match in ?, aci , under ??. Thus eci has ?(eci+1) in his one and onlyequivalence class and therefore (vci , vci+1) ? D. Furthermore (vcl , vc1) ? D.Thus, ec1 , . . . , ecl form a cycle in G, a contradiction. ?We can analogously define the diligent optimality certificate (DOC)decision problem. A corresponding hardness claim also holds for DOC. Thisproof is quite similar to the proof just given; we omit it to save space.403.5. Identical equivalence class orderings on one side of the marketAn optimal-in-expectation or a Pareto optimal policy need not computeoptimality certificates for every input. Nevertheless, we consider the hardnessof computing optimality certificates to be discouraging evidence about thetractability of the problem of identifying such policies.3.5 Identical equivalence class orderings on oneside of the marketIn many two-sided matching markets, there is positive correlation betweenagents? preferences. One way of modeling this is to say that agents on atleast one side of the market may have common a priori information, thoughperhaps different underlying preferences. In this section we focus on sucha setting, and furthermore consider the special case of partial preferenceorderings that we introduced earlier in Section 2.1 (as ?equivalence classorderings?).Specifically, we now assume that each agent has an equivalence relationover (a subset of) the candidates and a strict ordering over the equivalenceclasses. We denote the equivalence classes of employer ei and applicant ajthat are ranked `th in this strict ranking by cei,` and caj ,`, respectively. Welet cE,A denote the equivalence class profile for all employers and applicants.We assume that the applicants are endowed with identical equivalence classorderings. Thus, formally we assume that cai,k = caj ,k for all pairs of appli-cants ai and aj and all k; we allow applicants to have different distributionsand different underlying preference orderings, i.e., ?ai ? ?aj . We do notrestrict employers? preferences in any way. Irving et al. [31] study a similarsetting in which the preference orderings of one or both sides of the marketare derived from a common ranking of all the candidates into strictly rankedequivalence classes. They refer to this common ranking as a master list.They assume that each agent?s preference ordering is then derived from thecommon ranking by eliminating his or her unacceptable partners, thus pre-serving the indifferences if they exist in the master list. They were motivatedin this work by how the applicants were ranked in the hospitals?residentsmatching market in England in 2005?2006. Their setting differs from ours inthe sense that we allow, and even require, the agents to break ties.We will obtain positive results in this restricted setting under the addi-tional restriction to diligent policies. (We demonstrate the necessity of thisrestriction at the end of the section.) Even with these restrictions, observethat a tabular representation of an optimal-in-expectation, diligent policyrequires exponential space, since there are an exponential number of infor-413.5. Identical equivalence class orderings on one side of the marketmation states. As discussed earlier, we get around this problem by supplyingan algorithm that executes such a policy rather than specifying it explicitly.Specifically, we present a polynomial-time algorithm that executes a veryweakly dominant, diligent policy, and hence both an optimal-in-expectationand a Pareto optimal, diligent policy.Our algorithm for identifying a very weakly dominant, diligent policyworks like Gale?Shapley except that it is interleaved with another procedurethat instructs agents to interview. It is described formally as Algorithm 2;an informal description follows. We say that employer e ranks applicanta in class ` if a is in the `th equivalence class of e. Similarly, we say thatthe applicants rank e in class ` if e is in the `th equivalence class of theapplicants. Algorithm 2 alternates between two main stages, an interviewstage and a tentative matching stage.? In the interview stage, the algorithm chooses an unmatched employere that satisfies two properties. First, e has achievable applicants thathe has not yet interviewed. An achievable applicant is one that isacceptable to e, and has not yet received better offers. Second, ifapplicants rank e in class `, then they rank any other employer e? thatsatisfies the first property in a class below or equal to `. Employer ethen interviews all achievable applicants that he has not yet interviewed,and that belong to his equivalence class that is highest-ranked amongthose containing his achievable applicants.? In the tentative matching stage, unmatched employers propose to theirmost preferred achievable, interviewed applicant, if such an applicantexists. Each applicant a tentatively accepts her best proposal, say e.When there is no unmatched employer with an achievable interviewedapplicant, the tentative matching stage ends.If there are still unmatched employers with achievable applicants thatthey have not yet interviewed, the algorithm returns to the interview stage.Otherwise, the algorithm halts and returns the final tentative matching. Thenext example shows how the algorithm works.Example 48. Consider the setting with 3 employers and 3 applicants de-picted in Figure 3.1. Notice that the applicants are endowed with identicalequivalence classes. Assume that the true strict preference ordering of theagents is ?1, depicted in Figure 3.2. Note that ?2 is almost identical to ?1,depicted in Figure 3.2, except that e2?s top choices are reversed.423.5. Identical equivalence class orderings on one side of the marketAlgorithm 2: Lazy Gale-ShapleyInput: E, A, cE,AOutput: Matching ?Initialize` = 1 ; // Current equivalence class number of applicants?(ei)? ?, ?(aj)? ?,?ei ? E,?aj ? A ;?ei ? ?,?ei ? E ; // ei?s set of achievable interviewed applicantsrepeatInterview Stageforeach ei ? E doif ?(ei) = ? thenPei ? The set of achievable applicants in the highest-rankedequivalence class of ei among those with his achievable applicants,whom he has not interviewed yet ;Eu,` ? the set of unmatched employers ed in equivalence class ` of theapplicants with nonempty Ped ;while Eu,` = ? do`? ` + 1 ;Eu,` ? the set of unmatched employers ed in equivalence class ` of theapplicants with nonempty Ped ;ei ? an arbitrary employer in Eu,` ;foreach aj ? Pei doei interviews aj ;?ei = Pei ;Pei ? ? ;Tentative repeatMatching Stage foreach ei ? E doif ?(ei) = ? and ?ei ? ? thenei offers a position to the achievable applicant it prefers the most;she is removed from ?ei ;Each applicant who has received one or more job offers tentatively acceptsthe offer from the employer she most prefers and rejects the rest; matching? is updated accordingly ;Each tentatively matched applicant aj is no longer achievable to thoseemployers that are in the equivalence classes ranked lower than the one?(aj) belongs to; she is removed from the lists of such employers; ?ei isupdated accordingly for all ei ? E ;until there is no unmatched employer ei with ?ei ? ?;until each employer is either tentatively matched or has no achievable applicants;return ? ;Running Algorithm 2 on this setting returns the employer-optimal match-ing ?1 = {(e1, a1), (e2, a3), (e3, a2)} after 3 runs of the main loop and 5interviews. Assume, for the sake of this example, that in the interview stage,433.5. Identical equivalence class orderings on one side of the markete1 e2 e3a1 a1 a1a2 a3a3 a2 a2a3pEa1 a2 a3e1 e1 e1e2 e2 e2e3 e3 e3pAFigure 3.1: A setting with 3 employers and 3 applicants. Applicants areendowed with identical equivalence classes.Algorithm 2 chooses the lowest indexed employer that satisfies the two requiredproperties. Then, the execution of Algorithm 2 on ?1 will be as follows.1. e1 is instructed to interview both a1 and a2. e1 proposes to his mostfavorite candidate a1 and is matched to her. a1 is no longer achievablefor e3 and so is removed from his list.2. e2 is instructed to interview both a1 and a3. e2 proposes to his mostpreferred candidate a3 and is matched to her. a3 is no longer achievablefor e3 and so is removed from his list.3. e3 is instructed to interview a2, the only applicant still achievable forhim. e3 proposes to a2 and is matched to her.If the true ordering was ?2, depicted in Figure 3.3, then running Algorithm 2would return the employer-optimal matching ?2 = {(e1, a2), (e2, a1), (e3, a3)}after 3 runs of the main loop and 5 interviews.1. e1 is instructed to interview both a1 and a2. e1 proposes to his mostpreferred candidate a1 and is matched to her. a1 is no longer achievablefor e3 and so is removed from his list.2. e2 is instructed to interview both a1 and a3. e2 proposes to his mostpreferred candidate, a1. a1 accepts e2?s proposal and rejects e1, whomshe likes less than e2. e2 is matched to a1 and a1 is removed from e1?slist. e1 proposes to a2 who is now at the top of his list, and is matchedto her. a2 is no longer achievable for e3 and so is removed from hislist.3. e3 is instructed to interview a3, the only applicant still achievable tohim. e3 proposes to a3 and is matched to her.443.5. Identical equivalence class orderings on one side of the markete1 e2 e3a1 a3 a1a2 a1 a2a3 a2 a3a1 a2 a3e2 e1 e1e1 e2 e2e3 e3 e3Figure 3.2: Agents? preferences un-der total order ?1 that refines thesetting depicted in Figure 3.1.e1 e2 e3a1 a1 a1a2 a3 a2a3 a2 a3a1 a2 a3e2 e1 e1e1 e2 e2e3 e3 e3Figure 3.3: Agents? preferences un-der total order ?2 that refines thesetting depicted in Figure 3.1.Our main claim in this section is that Algorithm 2 executes a very weaklydominant, diligent policy. Key to the proof is to show that, regardless ofthe underlying preference profile, Algorithm 2 always identifies a diligentminimum optimality certificate.Theorem 49. Algorithm 2 executes a very weakly dominant, diligent policyin time polynomial in the input size.Proof. The proof proceeds in four steps.Step 1: Algorithm 2 terminates in time polynomial in the input size.Note that Algorithm 2 halts once each employer is matched or has no moreachievable applicants to propose to or to interview. Hence, the algorithm isguaranteed to perform at least at least one interview in the interview stageof each iteration. Furthermore, in each invocation of the tentative matchingstage, at least one employer proposes to an applicant and is then eitherrejected by that applicant or tentatively matched. There are n ?m possibleinterviews and hence n ?m possible proposals. Thus the algorithm halts inpolynomial time.Step 2: Algorithm 2 executes a diligent policy. Recall that the employer-proposal variant of the Gale?Shapley algorithm yields the employer-optimalmatching. The algorithm is robust w.r.t. varying the order in which un-matched employers propose, as long as they always propose to their topchoice among achievable candidates. In Algorithm 2, no employer interviewsan applicant unless all the applicants he ranks in higher equivalence classesare unachievable, no employer proposes when he is tentatively matched, andunmatched employers always propose to their most-preferred achievable,interviewed applicant. The algorithm only halts when each employer is eithermatched or has no more achievable applicants to propose to or to interview.Thus Algorithm 2 returns the same matching as Gale?Shapley would havereturned for any preference profile that refines the global information state453.5. Identical equivalence class orderings on one side of the marketthat holds at the moment Algorithm 2 terminates. Because Gale?Shapley issound, Algorithm 2 is sound. Since no employer proposes to an applicant hehas not interviewed, Algorithm 2 is also diligent.Step 3: Algorithm 2 only ever instructs an employer in applicants? equiva-lence class ` to interview applicants, or to make offers, when all employers inapplicants? higher-ranked equivalence classes are matched to their employer-optimal matches or have been rejected by all applicants they find acceptable.By the interview stage, if e in applicants? equivalence class ` is chosen toperform interviews, all employers in higher-ranked equivalence classes musteither be tentatively matched or have no more achievable applicants. If noneof the matched employers makes a new offer, their tentative matches becomefinal, and so must be, by Step 2, their employer-optimal matches. If any ofthe matched employers makes a new offer, it can only be because he hasbeen rejected by his current tentative match. Let e? be the first employer inapplicants? equivalence class ` ? 1 or higher that gets rejected by his currentmatch in a round in which employers in applicants? equivalence class ranked` or lower are interviewing. Then e??s tentative match must have receivedan offer from a more-preferred employer, e??, in applicants? equivalence class` ? 1 or higher. This is only possible if e?? was rejected by his match in anearlier round, contradicting our definition of e?.Step 4: All interviews performed by Algorithm 2 on any given preferenceprofile ? ? cE,A are in the diligent minimum optimality certificate for ?,(I, ?, cE,A). We show this in two steps. For a given employer e thatapplicants rank in class `, let ? be the set of all applicants in equivalenceclasses of e that are above or equal to the equivalence class containing ?(e),unless those applicants are matched by ? to employers that applicants rankin a class above `. We first show that (I, ?, cE,A) includes all interviews in?. We then show that Algorithm 2 performs only interviews in ?.? (I, ?, cE,A) includes all interviews in ?. By our requirement thatmatched agents must interview each other, any diligent policy mustrequire e to interview ?(e). Furthermore, for each a, a ? ?(e), whois ranked by e in the same equivalence class as ?(e) or higher, andwho is not matched to an employer she ranks in a higher equivalenceclass than `, there exists a preference ordering ?? that is the same as ?except that e and a promote each other to the highest possible positionin their respective rankings. Under ??, (e, a) blocks ?; thus ? is notemployer-optimal under ??. However, unless e interviews a, preferenceprofile ?? refines I and thus (I, ?, cE,A) is not an optimality certificate.463.5. Identical equivalence class orderings on one side of the market? Algorithm 2 performs only interviews in ?. We need to show that edoes not interview applicant a if applicants rank ?(a) in a class above `(recall that ` is the applicants? class containing e), and also if e ranks ain a class below the class containing ?(e). By Step 3, any a who ranks?(a) in an equivalence class ranked higher than ` must be matchedto him when e is chosen and thus is not achievable to e and so is notinterviewed by e. If e ranks a in a class below ?(e), then e also doesnot interview a in the policy executed by Algorithm 2, because e doesnot interview applicants in an equivalence class unless he is rejectedby all applicants in higher ranked equivalence classes. Since ?(e) doesnot reject e, we can conclude that e does not interview a.Finally, the desired result follows by Theorem 45. ?Recall that to get a polynomial-time result, we not only restricted ourpartial information setting, but also turned to diligent policies rather thansound policies. We have already seen, in Theorem 39, that without anyrestriction on the given partial preference ordering, we can not guaranteethe existence of a very weakly dominant, diligent policy. The next theoremshows that even in our restricted setting, we can not guarantee the existenceof a sound policy that very weakly dominates every other sound policy.Theorem 50. There exist equivalence class orderings in which applicantsare endowed with identical equivalence classes, for which no very weaklydominant policy exists.Proof. Consider a setting with 2 employers and 2 applicants where all agentsinitially rank both candidates in the same equivalence class. Let I1, I2, I3,and I4 be four information states that can be reached after a sequence ofthree interviews with the properties that:? under I1, e1 and a1 prefer each other the most,? under I2, e2 and a2 prefer each other the most,? under I3, e2 and a1 prefer each other the most, and? under I4, e1 and a2 prefer each other the most.The reader can easily verify that these four information states are indeed allreachable after three interviews in the setting described. It is also easy toverify that ?1 = {(e1, a1), (e2, a2)} is the employer-optimal matching for anypreference ordering that refines I1 and/or I2, and ?2 = {(e1, a2), (e2, a1)} is473.5. Identical equivalence class orderings on one side of the markete1 e2 a1 a2a1 a1 e1 e1a2 a2 e2 e2?1e1 e2 a1 a2a2 a2 e2 e2a1 a1 e1 e1?2e1 e2 a1 a2a1 a1 e2 e2a2 a2 e1 e1?3e1 e2 a1 a2a2 a2 e1 e1a1 a1 e2 e2?4Figure 3.4: Four of the possible strict preference orderings that refine asetting with 2 employers and 2 applicants with empty initial information.the employer-optimal matching for any preference ordering that refines I3and/or I4.Let ?i ? Ii, 1 ? i ? 4, be the four strict preference orderings depictedin Figure 3.4. The minimum optimality certificate for ?1 is (I1, ?1, pE,A).To see this, note that to certify ?1 as the employer-optimal matching for?1, e1 needs to have interviewed both applicants, to distinguish between?1 and ?? ? I4, e1??a1e2 and a1??e2a2. In addition, e2 has to interview a1 inorder to distinguish between ?1 and ??? ? I3, where ? and ??? are the sameexcept that a1?s preferences are reversed. Similarly, we can prove that theminimum optimality certificate for ?2 is (I2, ?1, pE,A), for ?3 is (I3, ?2, pE,A),and for ?4 is (I4, ?2, pE,A). Notice that each of these minimum optimalitycertificates are reached by three interviews. Any policy that performs theinterview e1 ?a1 (respectively e2 ?a2, e1 ?a2, e2 ?a1) is Pareto dominated under?2 (respectively under ?1, ?3, ?4). Hence, no very weakly dominant policyexists. ?The reader may wonder whether we can obtain an analogous positiveresult if we restrict the setting such that employers, as opposed to applicants,are endowed with identical equivalence classes. (Observe that the restrictionis not symmetric because in both cases we are concerned with identifyingemployer-optimal matchings.) It turns out that we cannot; instead, this newrestricted setting leads us back to the nonexistence result of Theorem 39.Theorem 51. There exist equivalence class orderings in which employersare endowed with identical equivalence classes, for which no very weaklydominant, diligent policy exists.The proof follows immediately from the proof of Theorem 39. Lastly, weshow that our restriction to equivalence class orderings was also important483.6. Strict total orders with perturbationfor getting us around the nonexistence of very weakly dominant, diligentpolicies.Theorem 52. There exist inputs for which no very weakly dominant, diligentpolicy exists, even when applicants are endowed with identical, strict partialpreference orderings.Proof. Consider a setting with 4 employers and 2 applicants where theagents? partial preference orderings are as depicted in Figure 3.5. Thatis, the employers initially have full knowledge of their preferences and theapplicants? identical partial preference orderings reveal that they both prefere1 to e3 and e4. Let the agents? preferences under total orders ? and ?? beas depicted in Figures 3.6 and 3.7. Note that ? and ?? are the same exceptthat a2?s top two choices are interchanged.Matching ?, ?(e1) = a1 and ?(e2) = a2, is the employer-optimal matchingunder both ? and ??. The minimum diligent optimality certificate for ?, (I, ?),consists of the interviews Z = {e1 ?a1, e2 ?a2, e1 ?a2}, whereas the minimumdiligent optimality certificate for ??, (I ?, ?), consists of the interviews Z ? ={e1 ?a1, e2 ?a2, e3 ?a2, e4 ?a2}. Note that Z and Z ? only share the two interviewse1 ?a1 and e2 ?a2, and that both ? and ?? refine the information state resultingfrom these two interviews. (In fact, the interviews e1 ?a1 and e2 ?a2 belongto the minimum diligent optimality certificate of all strict total orders thatrefine the setting in Figure 3.5, even when one or both of these pairs end upbeing matched.) Thus, a policy that computes a minimum diligent optimalitycertificate for ? cannot compute one for ?? (and vice versa): a policy thatperforms e1 ?a2 is Pareto dominated under ??, and a policy that performse3 ?a2 and/or e4 ?a2 is Pareto dominated under ?. Therefore, no very weaklydominant, diligent policy exists for the given setting. ?3.6 Strict total orders with perturbationAre identical equivalence class orderings for the applicants necessary for theexistence of very weakly dominant (diligent) policies? Or are there othersettings with partial orders that admit such policies? Obviously a settingwith total orders (even when those orders are not identical for the applicantsand/or the employers) admits such a policy; we only need to run Gale?Shapley to determine the employer-optimal matching. If a diligent policyis required, we only have to instruct each employer to interview his matchunder the employer-optimal matching. However, this is quite a degeneratesetting, since the agents? have no uncertainty about their preferences. Our493.6. Strict total orders with perturbatione2 e4 e3 e1 Applicants? partial preferenceorderingse1 e2 e3 e4a1 a2 a2 a2a2 a1 a1 a1Employers? partial preferenceorderingsFigure 3.5: A setting with 4 employers and 2 applicants. Employers have fullknowledge of their preferences as shown in the table on right. Applicants?partial preference ordering is as depicted on the left: they both prefer e1 toe3 and e4.e1 e2 e3 e4a1 a2 a2 a2a2 a1 a1 a1a1 a2e1 e2e2 e1e3 e3e4 e4Figure 3.6: Agents? preferencesunder total order ?.e1 e2 e3 e4a1 a2 a2 a2a2 a1 a1 a1a1 a2e1 e1e2 e2e3 e3e4 e4Figure 3.7: Agents? preferencesunder total order ??.next example shows that there are other interesting settings for which a veryweakly dominant (diligent) policy exists.Example 53. Consider a setting with 3 employers and 2 applicants where theagents? strict partial preference orderings are as depicted in Figure 3.8. Thatis, the employers have full knowledge of their preferences and the applicants?identical partial preference orderings only reveal that they all prefer e1 toe3. Note that the applicants? partial preference orderings are not equivalenceclass orderings. Each applicant?s underlying total order can be one of thethree depicted in Figure 3.9. It is easy to verify the following.1. If a2?s total order is either x1 or x3, the employer-optimal matching is?1 = {(e1, a1), (e2, a2)}. The minimum optimality certificate consistsof the two interviews Z1 = {e2 ? a2, e3 ? a2}, and the minimum diligentoptimality certificate additionally contains e1 ? a1.2. Else, if a2?s total order is x2 and a1?s total order is either x1 orx2, the employer optimal-matching is ?2 = {(e1, a1), (e3, a2)}. Theminimum (diligent) optimality certificate consists of the four interviewsZ2 = {e1 ? a1, e2 ? a2, e3 ? a2, e2 ? a1}.503.6. Strict total orders with perturbatione2 e3 e1 a1, a2 e1 e2 e3a1 a2 a2a2 a1 a1Figure 3.8: A setting with 3 employers and2 applicants. Employers have full knowl-edge of their preferences. Applicants? par-tial preference orderings are as depictedon the left: they all prefer e1 to e3.x1 x2 x3e1 e1 e2e2 e3 e1e3 e2 e3Figure 3.9: The three possibletotal orders for the applicantsin the setting depicted in Fig-ure 3.8.3. Else, if a2?s total order is x2 and a1?s total order is x3, then theemployer-optimal matching is ?3 = {(e2, a1), (e1, a2)}. The minimumoptimality certificate consists of the four interviews Z3 = {e1 ? a1, e2 ?a2, e3 ? a2, e2 ? a1}, and the minimum diligent optimality certificateadditionally contains e1 ? a2.A very weakly dominant policy for this setting follows: given an informationstate I, if e2 has not interviewed a2, schedule that interview; else if e3has not interviewed a2, schedule that interview. Otherwise, if a2 prefers e2to e3 return ?1; else if e2 has not interviewed a1, schedule that interview.Otherwise, if a1 prefers e1 to e2 return ?2; else return ?3.A very weakly dominant, diligent policy follows: given an informationstate I, if e1 has not interviewed a1, schedule that interview; else if e2 hasnot interviewed a2, schedule that interview; else if e3 has not interviewed a2,schedule that interview. Otherwise, if a2 prefers e2 to e3 return ?1; else ife2 has not interviewed a1, schedule that interview. Otherwise, if a1 preferse1 to e2 return ?2; else if e1 has not interviewed a2, schedule that interview;else return ?3.We next show how to generalize the setting of Figure 3.8. Notice thatthe applicants? partially ordered preferences in this setting can be viewed asstrict preference orderings with some noise, under which each candidate in agiven applicant?s preference list may be moved one rank up or down.Definition 54 (Strict total orderings with 1-perturbation). A partial prefer-ence ordering pai for applicant ai is a strict total ordering with 1-perturbationif there is an ordering of the employers ei1 , . . . , eim , 1 ? ij ?m, such that paionly reveals that ai prefers each employer eij to every employer indexed ij+2513.6. Strict total orders with perturbationor higher. That is, (1) ?j, l, j + 1 < l ?m and ??ai ? pai, it is the case thateij?aieil, and (2) ?j <m, ??ai ? pai such that eij+1?aieij .It is easy to see that the applicants in the setting of Figure 3.8 have stricttotal orders with 1-perturbation. We next show that for a setting in whichthe employers have full knowledge of their preferences, and the applicantsare endowed with identical strict total orders with 1-perturbation, a veryweakly dominant policy exists.Theorem 55. Let I = (E,A, pE,A) be a setting with strict total orderingsfor the employers and identical strict total orderings with 1-perturbation forthe applicants. There exists a very weakly dominant (diligent) policy for Iand there exists an algorithm that executes such a policy in time polynomialin the input size.Proof. Without loss of generality assume that the ordering of the employersei1 , . . . , eim , mentioned in in Definition 54, is e1, e2, . . . , em. We presenta polynomial-time algorithm, Algorithm 3, that executes a very weaklydominant policy for I. To execute a very weakly dominant, diligent policywe only need to modify Algorithm 3 to additionally require every employerto interview his partner in the final match. Algorithm 3 alternates betweenthe following two steps until all employers are either matched or have nomore achievable applicants to propose to.1. Unmatched employer ei proposes to his most preferred achievableapplicant, aj , if and only if all el, l < i, are tentatively matched. If ajis tentatively matched to either ei?1 or ei+1, then ei interviews aj andso does aj ?s tentative partner if he has not done so already.2. Applicant aj tentatively accepts her best proposal and rejects the rest.To complete the proof, we need to show that Algorithm 3 (i) terminatesin time polynomial in the input size, (ii) is sound, i.e. returns the employer-optimal matching, and (iii) computes a minimum optimality certificate(I, ?, pE,A) for any preference profile ? such that ? ? pE,A. The proofs for (i)and (ii) are straightforward and similar to the proofs of Step 1 and Step 2 inthe proof of Theorem 49. To prove (iii) we show that the interviews Algorithm3 instructs are precisely those that belong to all optimality certificates for ?.The proof proceeds in several steps.We first define some terms that are going to be useful in the remainderof the proof. We say that an employer ei kicks out another employer ej if eiproposes to ej ?s current tentative match and, as a consequence, she accepts523.6. Strict total orders with perturbationhim and rejects ej . We say that ei1 , . . . , eil is a kick-out chain if (i) ei1 hasnot yet been kicked out, (ii) ei1 kicks out ei2 and as a result ei2 kicks out ei3and so on, and (iii) eil proposes to an unmatched applicant. In other words,a kick-out chain is a chain of consecutive kick outs that starts with a freshemployer?i.e., one who has not yet proposed to any applicant?employerproposing and kicking out another employer, and ends with an employerproposing to an unmatched applicant and hence getting matched to herwithout kicking out another employer.Step 1: An employer ei can not kick out e1, . . . , ei?2. Since pA is a stricttotal ordering with 1-perturbation, under all strict total orders and henceunder ? the applicants prefer e1, . . . , ei?2 to ei. Thus ei can not kick outeither of these employers.Step 2: A kick-out chain can only start by an employer ei kicking outei?1. In Algorithm 3 an employer ei only proposes if all el, l < i aretentatively matched. By Step 1, ei can not kick out either of the employerse1, . . . , ei?2. Furthermore, by the definition of a kick-out chain, ei has not yetbeen kicked out and hence has not proposed yet, so all el, l > i, are currentlyunmatched and hence can not be kicked out by ei. Thus the only employerthat can be kicked out by ei is ei?1, and this would happen if ei?1?s tentativepartner prefers ei to ei?1.Step 3: Every kick-out chain is in the following form for some z1, . . . , zy > 1and k ? 1 where i?k+?1?l?y zl ? i: ei, ei?1, . . . , ei?k, ei?k+z1 , . . . , ei?k+?1?l?y zl .In other words, we claim that every kick-out chain can be broken to twoparts: in the first part each employer ei kicks out ei?1, and in the secondpart each employer ei kicks out an employer ei+z for positive z > 1. Theproof proceeds as follows. (1) By Step 2 the only employer ei, the first inthe chain, can kick out is ei?1. (2) By Step 1, an employer ej can kick outeither ej?1 or ej+z for some z ? 1. (3) Employer ei?k, the first employerwho is kicking out a higher indexed employer, can not kick out ei?k+1, sinceei?k+1 has just kicked out ei?k and hence ei?k+1?s current tentative partnermust prefer ei?k+1 to ei?k. (4) We show that all the kick-outs from now on,after ei?k kicking out ei?k+z1 , z1 > 1, are in the form of employers ej kickingout ej+z, z > 1. Following Step 1, it is enough to show that from now onno employer ej can kick out ej?1 or ej+1. Assume for contradiction thatthis is not true and let ej be the first employer who kicks out either ej?1or ej+1. If ej kicks out ej+1, then she is getting matched to an applicantwho earlier preferred ej+1 to ej , and hence resulted in ej+1 kicking out ej , acontradiction. If ej kicks out ej?1 then, by (3), j ? 1 ? i? k. Therefore ej?1 is533.6. Strict total orders with perturbationcurrently matched to an applicant who prefers him to ej?2 and thus, by thegiven partial ordering and transitivity, prefers him to ej . Thus ej can notkick out ej?1, a contradiction. (5) By the construction of Algorithm 3 andthe definition of a kick-out chain, no employer ej , j > i, is matched when thekick-out chain starts. Thus none of these employers can be kicked out andhence i ? k +?1?l?y zl ? i.Step 4: All the interviews Algorithm 3 schedules are precisely those thatbelong to all optimality certificates for ?. Note that, by description, Al-gorithm 3 only schedules interviews when an employer ei has a chance ofkicking out either ei?1 or ei+1. Also note that, by Step 3, no kick-outs of theform of ei kicking out ei+1 are possible, hence the only interviews Algorithm3 schedules are those for which some ei has a chance of kicking out ei?1. Letei be such an employer and let a? be the applicant matched to ei?1 to whomei proposes to as well and, consequently, Algorithm 3 instructs ei to interviewa? and also instructs ei?1 to interview her if he has not done so already. Notethat a? is achievable for ei, so it must be the case that she has not receivedany proposals from employers indexed lower than i ? 1, as otherwise eithershe must have been matched to one of them?and not to ei?1? or it musthave been revealed already that she prefers ei?1 to ei?2 which means she isno longer achievable for ei, a contradiction. Therefore ei?1 has indeed notyet interviewed a? and hence both ei and ei?1 are instructed by Algorithm 3to interview a? at this stage. We have claimed that both of these interviewsbelong to all optimality certificates for ?. Assume for contradiction that thisis not the case, then there exists an optimality certificate (I, ?, pE,A) suchthat either or both of the interviews ei ?a? and ei?1 ?a? do not belong to I.Either a? prefers ei to ei?1 under ?, or the other way around. If a? prefersei to ei?1 then ei?1 and a? can not be matched in ?, the employer-optimalmatching of ?, since ei?1 and a? block ?. If a? prefers ei?1 to ei then ei?1and a? are matched in ?. To see this, note that Algorithm 3 returns theemployer-optimal matching ?, and that ei can not kick out ei?1 in this stageof Algorithm 3. However, following Step 3, ei?1 would not be kicked outfrom now on unless first being kicked out by ei. Hence, Algorithm 3 returnsa? as the match of ei?1 and the pair are matched in ?. Observe that unlessboth ei and ei?1 interview a?, it is not revealed how a? compares ei againstei?1. Thus, there exists a total ordering that refines I and under which(ei ? a?) ? ? and there exists a total ordering that refines I and under which(ei ? a?) /? ?, contradicting our assumption that (I, ?, pE,A) is an optimalitycertificate. ?543.7. Chapter summaryIn fact we can show that in the very weakly dominant policy executedby Algorithm 3, each employer interviews at most two applicants. The proofis involved but similar to that of Step 3 in the proof of Theorem 55. Weprovide it in Appendix A.2 for completeness.3.7 Chapter summaryWe have introduced a model of two-sided matching markets in which agentsbegin with partially ordered preference information, and can refine thesepreferences through interviews. We defined three optimization criteria tocapture the idea of minimizing the number of interviews required to find astable matching that is optimal for a given side of the market. We showedthat among these criteria, very weakly dominant policies do not always exist,and that in general settings it is NP-complete to find such a policy if it doesexist. In contrast, optimal-in-expectation and Pareto-optimal policies doalways exist; they can be found in exponential time via an MDP encoding.We can do better in the setting where one side of the market is endowedwith identical equivalence class orderings and in which pairs of agents mustinterview before they can match; here, we can leverage the notion of minimumoptimality certificates to execute a very weakly dominant, diligent policy inpolynomial time. Furthermore, we can extend this result to another settingin which applicants? partially ordered preferences are not equivalence classorderings.Our work raises many questions. A particularly important open problemis the hardness of finding optimal-in-expectation policies (or Pareto opti-mal policies) in general settings. One could also consider approximatingthese objectives. It would be interesting to identify settings under whichwe can bound the number of interviews our proposed algorithm performs(e.g., w.r.t. the number of equivalence classes and the number of agentsin each equivalence class). In this vein, it would be particularly useful tounderstand when we only need a linear number of interviews, as this mimicsthe setting in the NRMP where applicants can only list a constant number ofhospitals. Another interesting direction is to forgo the employer-optimalityof the matching, and look for approximately employer-optimal matchings, inexchange for fewer interviews. Conversely, it is also interesting to investigatewhether one can guarantee the employer-optimal matching by performingat most boundedly more than the minimum number of interviews requiredby an optimal policy. It is also important to investigate how and when ourresults could be extended to the many-to-one matching markets. This would553.7. Chapter summaryof course depend on the employers? preferences over groups of applicants, aswell as the differences in the number of applicants each employer intends tohire. For example, if employers have different numbers of spots available, itmay be beneficial to have employers with larger numbers of spots interviewfirst. Finally, it would be worthwhile to investigate the computational impactof committing to decentralized policies.56Part IIRevenue Monotonicity inCombinatorial Auctions57Chapter 4Revenue Monotonicity inDeterministic,Dominant-Strategy TruthfulCombinatorial AuctionsIn this chapter, we ask whether there exists a combinatorial auction mecha-nism that allows bidders to express arbitrary known single-minded preferencesand that is both dominant strategy truthful and revenue monotonic.If dominant strategy truthfulness and revenue monotonicity are theonly conditions we require, it is easy to answer the above question in theaffirmative. Specifically, we can offer all goods as one indivisible bundle usinga second-price sealed-bid auction. However, this mechanism is unappealing,because it is combinatorial only in a degenerate sense. If we want to requirethe mechanism to allocate the goods more sensibly than through a staticpre-bundling, we must ask for some further property. Very restrictively,we could require efficiency. In this work, we exchange efficiency for themuch more inclusive notion of weak maximality. While efficiency requiresthe mechanism to choose an allocation that maximizes social welfare, weakmaximality requires that the mechanism choose an allocation that cannot beaugmented to make some bidder better off, while making none worse off.Our main result roughly states that, when bidders are allowed to ex-press arbitrary known single-minded preferences, no deterministic, dominant-strategy combinatorial auction mechanism is revenue monotonic (we furtherassume weak maximality, consumer sovereignty and participation; see Sec-tion 4.1).The rest of the chapter is organized as follows. In Section 4.1 we defineterminology for discussing combinatorial auction mechanisms and theirproperties, followed by related work in Section 4.2. We present our mainimpossibility result in Section 4.3. As corollaries, in Section 4.4, we provesimilar impossibility results concerning the existence of mechanisms that yield584.1. Preliminariesweakly increasing revenue as the set of goods (rather than bidders) increases,that are false-name-proof (i.e., that offer truthful dominant strategies whenagents are able to submit multiple bids under different identities), and thatchoose outcomes guaranteed to belong to the core.4.1 PreliminariesIn this section, we define terminology for discussing combinatorial auctionmechanisms. To keep our presentation concise and convey intuition, weprovide informal and intuitive definitions and defer many technicalities to theappendix (Appendix B). For the same purpose, we restrict our attention tothe most restricted class of bidders to which our impossibility result applies,known single-minded bidders, which is also the class of bidders for whichour possibility result (Chapter 5) holds. Note that any impossibility resultbecomes stronger under a more restricted setting.4.1.1 BiddersWe use N and G to denote the set of bidders present in an auction and theset of goods available for sale, respectively. Auction mechanisms generallywork for any given set of bidders and goods. In this work we want to reasonabout changing the setting to include or exclude bidders or goods. Therefore,we define a universal set of possible bidders N to be {1,2, . . . , n}, and auniversal set of goods G. In any auction, N ?N and G ? G.A valuation function describes the values that a bidder holds for subsetsof the set of goods in G. Let vi denote bidder i?s valuation function.We make the fairly standard assumption of quasilinear utilities where abidder?s utility in an auction is defined to be her value for the set of goodsallocated to her minus the monetary payment that she has to make to theauctioneer.A valuation profile is an n-tuple v = (v1, . . . , vn), where, for every partic-ipating bidder i, vi is a valuation function. We adopt the convention thatvaluation profiles always have one entry for every potential bidder, regardlessof the number of bidders who participate in the auction. We use the symbol? in such tuples as a placeholder for each non-participating bidder (i.e., eachbidder i /? N). Let v?i denote (v1, . . . , vi?1,?, vi+1, . . . , vn). Note that if i /? N ,then v = v?i.If asked to reveal her valuation, a bidder may not tell the truth. De-note the declared valuation function of a (participating) bidder i as v?i.594.1. PreliminariesLet v? be the declared valuation profile. Use the same notation to de-scribe declared valuation profiles as valuation profiles (e.g., all declaredvaluation profiles are n-tuples), and furthermore write (vi, v??i) to denote(v?1, . . . , v?i?1, vi, v?i+1, . . . , v?n).The class of unknown single-minded bidders, or simply single-mindedbidders, was first introduced by Lehmann et al. [39]. Informally, a partici-pating bidder i is single-minded if there exists a particular bundle bi suchthat bidder i has a nonzero valuation only for bundles that contain bi, andvalues all these bundles equally.Definition 56 (Single-minded bidder). Bidder i is single-minded if hervaluation function is defined asvi(b?i) = {vi b?i ? bi0 otherwise,where vi > 0 and bi ? G.A single-minded bidder i?s valuation can be characterized by two pa-rameters: ?bi,vi?. Therefore, we use ?bi,vi? and vi interchangeably whena bidder is single-minded. We let ??bi, v?i? denote the declared valuation ofsingle-minded bidder i.The even more restricted model of known single-minded bidders wasfirst introduced by Mu?alem and Nisan [44]. A bidder i is known single-minded if she is single-minded and her bundle of interest bi is known tothe mechanism designer. The valuation of a known single-minded bidder ican be characterized by the single parameter vi, representing i?s valuationfor any weak superset of bundle bi. Thus in this case we use v to denotea valuation profile for a group of single-minded bidders, v?i to denote thedeclared valuation of a participating bidder i, and v? to denote a tupleconsisting of declared valuations for participating bidders and ? symbolsfor non-participating bidders. We let b = (b1, b2, . . . , bn) denote the set ofknown bundles of interest for the bidders. For a fixed N ? N, G ? G, andb ? (2G)n, we denote by V (b)N,G the set of all possible known single-mindedvaluation profiles.4.1.2 Combinatorial auction mechanismsA combinatorial auction mechanism is capable of selling multiple goodssimultaneously and allows bidders to place bids on bundles. In a knownsingle-minded setting, the mechanism already knows the bundle each bidder604.1. Preliminariesis interested in. Thus, the bidders only have to express their value for theirbundles of interest.A deterministic direct Combinatorial Auction (CA) mechanism (CAmechanism) M (ksm) defined for known single-minded bidders over N andG produces an allocation of goods a = (a1(v?), . . . , an(v?)) and a paymentvector p = (p1(v?), . . . , pn(v?)) for all G ? G, N ? N, and b ? (2G)n, givenbidders? declared valuation profile v? . Note that for allocations to be feasible,the following must hold: (i) ?i ai(v?) ? G, and (ii) ai(v?) ? aj(v?) = ? if i ? j.Furthermore, a CA mechanism does not allocate goods to, and does notrequire a payment from, a bidder who is not participating in the auction.That is, ai(v?) = ? and, pi(v?) = 0 if i /? N .We refer to (a, p) as the outcome of a CA mechanism. We refer to ai andpi as bidder i?s allocation and payment functions respectively. Note that theallocation and payment functions may depend not only on v? , but also onb. We denote by AN,G the set of all possible ways of allocating goods. Theseller may fail to allocate some or all of the goods. For any given allocationa ? AN,G, we denote by ai the set of goods that are allocated to bidder iunder a. Whenever v? can be understood from the context, we refer to ai(v?)and pi(v?) by ai and pi, respectively. If v?i(ai) > 0, i.e. if ai ? bi, we say thatbidder i ?wins?. A losing bidder is a bidder who does not win. We assumethat bidders have quasilinear utility functions; that is, bidder i?s utility forbundle ai is vi(ai) ? pi.Next, we give informal definitions for the various properties that wewould like to require of CA mechanisms. We provide references to formaldefinitions in Appendix B throughout the section.Dominant strategy truthfulnessIn mechanism design, it is especially desirable for a mechanism to give riseto dominant strategies, as then there is no need for bidders to reason abouteach others? behavior in order to maximize their utilities. A CA mechanismM is truthful if bidders declare their true valuations to the mechanismin equilibrium. M is dominant strategy (DS) truthful if it is a dominantstrategy for every bidder to reveal her true preferences (see Definition 90in Appendix B). Observe that the revelation principle tells us that anysocial choice function that can be implemented in dominant strategies canalso be implemented truthfully in dominant strategies. This means thatour conflation of dominant strategies with truth-telling is without loss ofgenerality.Considerable research has characterized the space of social choice func-614.1. Preliminariestions that can be implemented in dominant strategies. A classic result ofRoberts [55] showed that for bidders with unrestricted quasilinear valua-tions, affine maximizers are the only dominant-strategy-implementable socialchoice functions. Subsequent work has focused mainly on restricted classesof preferences [9, 11, 36, 56, 62].The VCG mechanism [10, 21, 66] has gained substantial attention inmechanism design literature because of its strong theoretical properties. Inparticular, it offers dominant strategies and achieves efficiency. Indeed, nosubstantially different (technically, no non-Groves) mechanism can guaranteethese properties for agents with general quasilinear valuations [20]. VCG iscomputationally intractable4, thus, there have been many attempts to designfeasible dominant strategy truthful mechanisms, even for restricted classes ofvaluations. Archer and Tardos [3], Andelman and Mansour [2] and Mu?alemand Nisan [44] studied the design of dominant strategy truthful mechanismsfor combinatorial settings with single-parameter agents: agents whose privateinformation can be encoded in a single real number. Babaioff et al. [6, 7]studied CA design in single-value domains under the further assumptionthat each agent has the same value for all desired outcomes. Yokoo et al.[68, 69, 70] studied the design of dominant strategy truthful mechanisms forsettings in which bidders may submit multiple bids using pseudonyms.Revenue MonotonicityThe revenue of an auction mechanism is the sum over all the paymentsmade by the bidders to the auctioneer. An auction mechanism is revenuemonotonic if and only if the auctioneer never collects more money when abidder is dropped (see Definition 93 in Appendix B).Ausubel and Milgrom [4] dubbed this property bidder monotonicity. Inorder to emphasize that we are concerned with monotonicity of revenue?ascompared to some other auction property?we prefer the term bidder revenuemonotonicity. This can be contrasted with e.g., good revenue monotonicity,the property that a seller?s revenue from an auction is guaranteed to weaklyincrease as the number of goods at the auction grows. We are primarilyinterested in the former property; thus, as a shorthand we abbreviate bidderrevenue monotonicity simply as revenue monotonicity.4Indeed, VCG has a host of other drawbacks too; see, e.g., Rothkopf [61].624.1. PreliminariesEfficiencyAs discussed earlier, one of the most commonly-desired properties for anauction mechanism is efficiency. A CA mechanism is efficient if its chosenallocation in equilibrium maximizes the social welfare (see Definition 92 inAppendix B).The VCG mechanism [10, 21, 66] has gained substantial attention becauseit offers dominant strategies to the bidders and allocates goods efficientlywhen bidders follow their dominant strategies. It is easy to see that evenVCG is not revenue monotonic. Following an example due to Ausubel andMilgrom [5], consider an auction with three bidders and two goods for sale.Suppose that bidder 2 values the bundle of both goods at $2 billion whereasbidder 1 and bidder 3 value the first and the second goods at $2 billionrespectively. The VCG mechanism picks the efficient allocation and chargeseach bidder his social cost. So, in this example, VCG awards the goodsto bidders 1 and 3?yielding the social welfare of $4 billion?for the priceof zero, yielding the seller zero revenue. However, in the absence of eitherbidder 1 or bidder 3, the auction would generate $2 billion in revenue.Weak MaximalityConsider the set protocol, a simple mechanism that offers all goods as oneindivisible bundle and uses the second price sealed-bid auction to determinethe winner and the payment. It is trivial to show that the set protocol isdominant-strategy truthful. This mechanism is also revenue monotonic sincedropping a bidder cannot cause the second-price bid to increase. However,the set protocol is a combinatorial auction only in a degenerate sense: itpre-bundles all goods and treats them as a single indivisible good. If we arenot happy with this solution, we need to require some further property thatrules out mechanisms like the set protocol.One popular option is efficiency (see Definition 92). As mentioned above,the only dominant-strategy truthful and efficient CA mechanisms are Grovesmechanisms [20]. We have already seen that VCG fails revenue monotonicity;therefore, efficiency may be too strong a condition to require.We propose instead requiring weak maximality. Intuitively, weak maxi-mality requires that the mechanism does not withhold any good, or give itaway to a bidder who does not value it, when it is sufficiently valued by alosing bidder. Weak maximality is a less standard property than those wehave discussed so far. Thus, we provide a more formal definition of it here.For the fully formal treatment, see Definition 94 in Appendix B.634.1. PreliminariesConsider a truthful CA mechanism M (ksm) defined for known single-minded bidders, with set of bidders N , set of goods G and set of (known)bundles b = (b1, . . . , bn). M (ksm) is weakly maximal with respect to bidder iif and only if there exists a set of nonnegative finite constants ?N,G,b,i,g,5?g ? G, such that M (ksm) always chooses an allocation a where either:1. vi(ai) > 0; or2. for all allocations a? with vi(a?i) > ?N,G,b,i,a?i , ?a?i? = 1, and a?j = aj ? a?i forall j ? i, it must be the case that for some j, vj(a?j) < vj(aj).Equivalently, we could write condition (1) as bi ? ai, and condition (2) asbj ? aj and bj /? a?j .When a mechanism is weakly maximal with respect to bidder i, then ifi?s valuation for a single good g is at least ?N,G,b,i,g and if g is not allocatedto any other bidder who gets additional value for it, then i is awarded g. Thequantities {?N,G,b,i,g ? g ? G} can be thought of as bidder- and item-specificreserve prices. Observe that the set protocol does not satisfy weak maximalitywith respect to any bidder, because the winning bidder may be given a goodg that she does not value, even when there exists another bidder i who valuesg and bids more than an arbitrary constant amount.Many interesting mechanisms are weakly maximal. (The definitions ofthe concepts that follow, along with the formal statement of the claims andthe proofs are given in Appendix B.2.2.) Efficient mechanisms, a broad classof affine-maximizing mechanisms, and mechanisms that are strongly Paretoefficient with respect to bidders? valuations are all weakly maximal. Indeed,we can show that all these mechanisms satisfy an even stronger condition,maximality. Note that requiring a weaker condition makes our impossibilityresult stronger.Our weak maximality property is related to the reasonableness conditionof Nisan and Ronen [46], which says that whenever an item is desired by asingle agent only, that agent must receive the item. If ?N,G,b,i,g?s are all set tozero, then weak maximality implies reasonableness. However, reasonablenessdoes not imply weak maximality. Consider the case where there are exactlytwo bidders who desire an item. Reasonableness still holds even if that itemis never allocated to either of the agents, regardless of their declarations;however, such an allocation rule would violate weak maximality.5The reader may be surprised that these constants depend on N , G and b as well as iand g. A full explanation requires the formal details developed in Appendix B. Intuitively,the constants are allowed to vary for different sets of participating bidders N ?N, availablegoods G ? G, and known bundles b ? (2G)n.644.1. PreliminariesParticipationIt is natural to require that no bidder be made to pay unless she wins.A CA mechanism M satisfies participation if and only if any bidder i forwhom vi(ai) = 0 makes a zero payment to the mechanism (see Definition 91in Appendix B). Unlike the property of individual rationality (IR), whichrequires roughly that no bidder has to make a payment more than her valuefor the bundle she gets, participation does not constrain the payments ofbidders who win. Participation is therefore a weaker condition than IR.Consumer sovereigntyA CA mechanism M satisfies consumer sovereignty if any bidder can win anybundle she desires by bidding at or above a finite amount that may dependon the declarations of the other bidders (see Definition 95 in Appendix B).Practical auctions usually satisfy consumer sovereignty; see Feigenbaum et al.[18], upon which we base our definition.It is useful at this point to contrast consumer sovereignty with weakmaximality. Consumer sovereignty implies that e.g. a bidder i surely winsthe good she desires, g, by bidding at or above some finite amount. Incontrast, weak maximality does not imply that i necessarily wins g if shevalues it at or above the bidder-specific reserve price.Criticality for known single-minded biddersConsider a mechanism defined for known single-minded bidders. We saythat the mechanism offers critical values to bidder i if two properties hold.First, bidder i wins whenever she bids more than some critical value thatdepends only on the other bidders? declarations, and loses whenever she bidsless. Second, bidder i?s payment is equal to this critical value if she wins,and is zero otherwise. A mechanism defined for known single-minded bidderssatisfies criticality if it offers critical values to all bidders.Definition 57 (Criticality). A CA mechanism M defined for known single-minded bidders satisfies criticality if and only if ?b = (b1, b2, . . . , bn) ? (2G)nand ?v??i, there exists a critical value cvb,i(v??i) ? R ? {?} where:? if v?i > cvb,i(v??i), i wins and pays cvb,i(v??i);? if v?i < cvb,i(v??i), i loses and pays 0.Whenever b is understood from the context, we drop it from the subscript,writing cvi(v??i). The following result can be straightforwardly obtained from654.2. Related worknecessary and sufficient conditions for dominant-strategy truthfulness (see,e.g., Mu?alem and Nisan [44] and Nisan [45]).Theorem 58 (Following Lehmann et al. [39] and Mu?alem and Nisan [44]).Any CA mechanism defined for known single-minded bidders that satisfiesdominant-strategy truthfulness and participation also satisfies criticality.The following corollary, which immediately follows from Theorem 58 andconsumer sovereignty, is used in the proof of our main theorem.Corollary 59. Any CA mechanism defined for known single-minded biddersthat satisfies dominant-strategy truthfulness, participation, and consumersovereignty offers finite critical values to all bidders.4.2 Related workAusubel and Milgrom [4] were the first to demonstrate that VCG is not rev-enue monotonic. Different approaches have been proposed for understandingthe extent of revenue non-monotonicity in various combinatorial auctionproblems. One approach has considered VCG?s performance under restrictedvaluation classes. Say that the combined valuation of bidders satisfies biddersubmodularity if and only if for any bidder i and any two sets of biddersS and S? with S ? S?, it is the case that V ?S?{i} ? V?S ? V?S??{i} ? V?S? , whereV ?S is the maximum social welfare achievable under S. Ausubel and Mil-grom [4] showed that if the combined valuation of bidders satisfies biddersubmodularity then VCG is guaranteed to be revenue monotonic. Biddersubmodularity is implied by the goods are substitutes condition (see, e.g.,Ausubel and Milgrom [4] for a definition). However, in many applicationdomains for which combinatorial auctions have been proposed, goods are notsubstitutes and bidders? valuations exhibit complementarity.Day and Milgrom [13] argued that, under the assumption that biddersfollow a so-called ?best-response truncation strategy,? auctions that alwaysselect an outcome that is in the core with respect to declared valuations(so-called core-selecting auctions) are revenue monotonic when they select acore outcome that minimizes the seller?s revenue. (A precursor to this resultalso appeared in Ausubel and Milgrom [4].) Lamy [35] however showed, bymeans of a simple example, that Day and Milgrom?s claim does not hold. Infact, Lamy showed that, when there are at least three goods for sale, there isno revenue-monotonic auction that selects a bidder-optimal core outcome. Ina recent work, Beck and Ott [8] provided necessary and sufficient conditionsunder which core-selecting auctions are revenue monotonic.664.3. Impossibility of revenue monotonicityFollowing our work, Todo et al. [65] provided a characterization forthe allocation rule of DS truthful CA mechanisms that guarantees revenuemonotonicity.4.3 Impossibility of revenue monotonicityIn this section we turn to our main claim, that no CA mechanism can berevenue monotonic if it satisfies our desired properties of dominant-strategytruthfulness, participation, consumer sovereignty and weak maximality withrespect to at least two bidders. We begin by giving an example of how anexisting inefficient mechanism fails revenue monotonicity, and then prove thegeneral result.4.3.1 An example with an inefficient mechanismEarlier we gave a well-known example showing that VCG does not satisfyrevenue monotonicity, even when bidders are single-minded. Now we show?we believe, for the first time?that another widely-studied mechanism alsofails revenue monotonicity, even though it does not have an efficient allocationrule. The existence of such an example is not surprising given our impossibilitytheorem; however, it offers intuition for what follows.Lehmann et al. [39] introduced an inefficient, dominant-strategy truthful,direct CA mechanism for single-minded bidders. Naming it after its authors,we call the mechanism LOS. Like VCG, LOS satisfies participation andconsumer sovereignty. LOS is also strongly Pareto efficient with respect tobidders? valuations (see Definition 99 in Appendix B), and so satisfies weakmaximality with respect to all bidders.Let ppgi = vi/?bi?, bidder i?s declared price per good. LOS ranks bids in alist L in decreasing order of ppg, and then greedily allocates bids startingfrom the top of L. Thus, each bidder i?s bid is granted if bi does not conflictwith any previously allocated bids. If i?s bid is allocated, she is made to pay?bi? ? vinext/?binext?, where inext is the first bidder following i in L whose bidwas denied but would have been allocated if i?s bid were not present. Bidderi pays zero if she does not win or if there is no bidder inext.Consider three bidders {1,2,3} and two goods {g1, g2}. Let the truevaluations of bidder 1, 2 and 3 be ?{g1},v1?, ?{g1, g2},v2? and ?{g2},v3?,respectively. Now consider the following conditions on the bidders? valuations:(1) v1 > v3 > v2/2; (2) v2 > 0. It is possible to assign values to the vi?s in away that satisfies both conditions: e.g., v1 = 5, v2 = 4 and v3 = 3.674.3. Impossibility of revenue monotonicityFigure 4.1: A high-level illustration of Theorem 60: Given ?{g1},v1?,?{g1, g2},v2? and ?{g3},v3??vi?s as constructed in the proof of the theorem?(1) Bidders 1 and 3 win bundle {g1} and bundle {g2} respectively and eachpay more than a predefined constant amount, (2) bidder 3 wins bundle {g2}and pays more than the sum of the payments in part (1).Figure 4.2: Illustration of dependencies between the constructed values inthe proof of Theorem 60: For example, the edge from v?1 to v3 shows thatv3 depends on v?1 ; the lack of edges to v?1 shows that v?1 can be set freely.We will demonstrate that the auctioneer?s revenue under LOS can beincreased by dropping a bidder whenever the bidders and their valuationsare as described above. From Condition 1, ppg1 > ppg3 > ppg2 and thereforebidders 1 and 3 win. Each pays zero, so the total revenue is zero. To see this,note that the next bidder in the list after bidder 1 whose bid conflicts withb1 is bidder 2. However, bidder 2 would not win even if bidder 1 were notpresent, since b2 also conflicts with b3. Therefore bidder 1 pays zero. Thesame is true for bidder 3, and thus she also pays zero. If bidder 1 is dropped,bidder 3 wins and must pay ppg2 = v2/2. Since v2 > 0 (Condition 2), thispayment is more than zero and so revenue monotonicity fails.4.3.2 Impossibility theoremWe are now ready to prove our main result.684.3. Impossibility of revenue monotonicityFigure 4.3: Sketch of the proof of Theorem 60: Part 1Figure 4.4: Sketch of the proof of Theorem 60: Part 2Theorem 60. Let ?G? ? 2 and ?N? ? 3. Let M (ksm) be a CA mechanismdefined for known single-minded bidders that offers dominant strategies tothe bidders and satisfies participation,6 consumer sovereignty, and weak6In the case of single-parameter domains?which includes known single-minded bidders?it is possible to satisfy participation for free. That is, the space of social choice functionsthat are implementable in dominant strategies is the same with or without adding aparticipation constraint. This is mainly because each bidder has to pay either of the twospecific amounts: one if she wins and one if she loses. If we ?normalize? the paymentfunction and unconditionally pay each bidder the losing amount?which could be negative?694.3. Impossibility of revenue monotonicitymaximality with respect to at least two bidders. Then M is not revenuemonotonic.Proof. Without loss of generality (by the revelation principle) assume thatM (ksm) is dominant-strategy truthful. We will further assume that biddersfollow their dominant strategies and bid truthfully. Since ?N? ? 3, there areat least three bidders; let us name the first three 1, 2, and 3. (For notationalsimplicity in what follows, we will write the proof as though ?N? = 3. Ifin fact ?N? > 3 our argument would not change, except that all valuationprofiles would include extra ? entries.) Assume without loss of generalitythat M (ksm) is weakly maximal with respect to bidders 1 and 3. Since ?G? ? 2,there are at least two goods; let us name the first two g1 and g2. Let thebundles valued by bidders 1, 2, and 3 be b1 = {g1}, b2 = {g1, g2} and b3 = {g2}respectively.The five properties in which we are interested (DS truthfulness, partici-pation, revenue monotonicity, weak maximality, and consumer sovereignty)are all universally quantified over N ?N and G ? G (see Definitions 90, 91,93, 94, and 95 in Appendix B). Thus, to prove the theorem, it is enoughto demonstrate that no mechanism satisfies all of these properties for somegiven N and G. Specifically, we consider N = {1,2,3} and G = {g1, g2}.We now show how to construct valuations for the three bidders. Firstpick an arbitrary positive constant k, and then define v?1 = ?{1,2,3},G,b,1,g1 + kand v?3 = ?{1,2,3},G,b,3,g2 + k. Next pick an arbitrary positive constant ?, andthen pick an arbitrary value for v2 that satisfiesv2 > cv2(?,?,v?1 + v?3 + ?).Finally, pick values for v1 and v3 that satisfyv1 > max{cv1(?,v2,v?3 ), cv1(?,v2,?),v?1 }, andv3 > max{cv3(v?1 ,v2,?), cv3(?,v2,?),v?3 }.By Corollary 59 the above critical values are all finite. Dependencies betweenv?1 , v?3 , v2, v1, and v3 are shown in Figure 4.2, illustrating the fact that it ispossible to pick values for these variables that satisfy all our constraints byfollowing the ordering given.then we achieve a dominant-strategy mechanism that satisfies participation. However,there are revenue implications to these unconditional payments that vary with the numberof bidders in the auction. Therefore, we nevertheless state the participation conditionexplicitly.704.3. Impossibility of revenue monotonicityThe rest of the proof is divided into two parts. In Part 1 we considerN = {1, 2, 3} and construct an expression for the auction?s revenue. In Part 2we consider N = {2, 3} and show that more revenue is obtained than in Part1. Sketches of the arguments in each of these parts are given in Figures 4.3and 4.4 respectively. Figure 4.1 gives a high-level illustration of the proof.Part 1: Since v1 > cv1(?,v2,v?3 ) (by construction), if bidder 3 were to bidv?3 then bidder 1 would win (by criticality). By construction, bidder 3 is theonly bidder whose bundle does not overlap with b1, and v?3 > ?{1,2,3},G,b,3,g2 ;thus, by weak maximality bidder 3 would also win and, by criticality,cv3(v1,v2,?) ? v?3 (see (1) in Figure 4.3). (4.1)Symmetrically, from v3 > cv3(v?1 ,v2,?) we can also conclude thatcv1(?,v2,v3) ? v?1 . (4.2)By construction, v1 > v?1 and v3 > v?3 . Then, using Inequalities (4.1)and (4.2) and by criticality, bidders 1 and 3 win (see (2) in Figure 4.3). Byparticipation, since bidder 2 loses she must pay zero. Therefore the revenueof the auction, by criticality, is R = cv1(?,v2,v3) + cv3(v1,v2,?) ? v?1 + v?3 .Part 2: If bidder 1 is not present, then only bidders 2 and 3 compete.Since v3 > cv3(?,v2,?), by criticality, bidder 3 wins and pays cv3(?,v2,?)(see (3) in Figure 4.4). Since b2 and b3 overlap, bidder 2 loses and byparticipation pays zero. The revenue of the auction is therefore R?1 =cv3(?,v2,?). By construction, v2 > cv2(?,?,v?1 + v?3 + ?). Thus if bidder 3were to bid v?1 +v?3 +? then bidder 2 would win (by criticality) and so bidder 3would lose. This tells us (again by criticality) that cv3(?,v2,?) ? v?1 + v?3 + ?(see (4) in Figure 4.4). Therefore, R?1 = cv3(?,v2,?) ? v?1 +v?3 +? > v?1 +v?3 ?R. Thus, M (ksm) is not revenue monotonic. ?One might have imagined that weak maximality would increase an auctionmechanism?s revenue by avoiding ?leaving money on the table,? augmentingallocations to award available goods to the bidders who value them. Instead,we have shown above that any dominant-strategy truthful combinatorialauction mechanism that satisfies weak maximality with respect to at least twobidders?along with some more standard conditions?can sometimes collectno more than a predefined constant amount of revenue despite competitionbetween bidders. That is, given the constructed valuations, the paymentsof bidders 1 and 3 are bounded from above by an amount that does notdepend on bidder 2?s losing bid; bidder 2 effectively fails to offer competitionto bidders 1 and 3, who also offer each other no competition as they bid714.4. Related impossibility resultson separate bundles. On the other hand, when bidder 1 is dropped thenbidders 2 and 3 do compete. Although bidder 3 still wins, she pays morethan before and more than the sum of the payments in the three-bidder case.The mechanism can thus achieve arbitrarily higher revenue in the two-biddercase than in the three-bidder case, since ? and k can be set to be arbitrarilylarge and arbitrarily small, respectively.We have mentioned that an impossibility result becomes stronger as theset of mechanisms it describes becomes more restricted, hence our focus onknown single-minded bidders. However, our claim is only really true if wecan state our impossibility theorem for mechanisms that are not restricted toknown single-minded bidders. It may seem intuitive that such a result wouldbe very close to, and somewhat straightforward to derive from, what wehave already shown. While this is indeed the case, the general statement ofour result requires considerable formal setup beyond what we have providedso far. We formally state our result for the general case and prove it inAppendix B.2.3 (Theorem 100). The extension of all theorems and corollariesin Section 4.4 to the same general case are also given in the same appendix.4.4 Related impossibility resultsOur main impossibility result straightforwardly implies several other impossi-bility results. Here we demonstrate that arguments of the same form suffice toshow that it is impossible to achieve false-name-proofness and monotonicityin the set of goods rather than the set of bidders, and to guarantee that anauction?s outcome belongs to the core.4.4.1 False-name-proofnessFalse-name (pseudonymous) bidding has been studied extensively (e.g., Yokoo[67] and Yokoo et al. [69, 70]). This work is concerned with auctions in whicha bidder may submit multiple bids using pseudonyms. An auction mechanismis said to be false-name-proof if truth-telling without using false-name bidsis a dominant strategy for each bidder. Yokoo et al. [69] proved that theredoes not exist any combinatorial auction mechanism that is false-name-proofand efficient. Observe that this is a somewhat narrow result, because?as discussed earlier?only Groves mechanisms are both dominant-strategytruthful and efficient [20].There is a connection between false-name-proofness and revenue mono-tonicity. From the seller?s perspective, false-name bidding is the same ashaving more bidders in the auction. If an auction is not revenue monotonic,724.4. Related impossibility resultsmore bidders can mean less revenue. Our results are therefore relevant toresearch on false-name bidding (Todo et al. [65] indeed recently investigatedthis connection). For technical reasons, we have to make minor changesto our formal model to capture false-name bidding (e.g., we have assumedthat mechanisms know bidders? identities.) We can then prove the followingcorollary which generalizes the result of Yokoo et al. [69] by replacing theirrequirement of efficiency with the much weaker criterion of weak maximality.Recall that all efficient mechanisms are weakly maximal with respect to allbidders, but there exist other mechanisms that are inefficient and still weaklymaximal.Corollary 61. Let ?G? ? 2 and ?N? ? 3. Let M (ksm) be a CA mechanismdefined for known single-minded bidders that offers dominant strategies tothe bidders, and that satisfies participation, consumer sovereignty, and weakmaximality with respect to at least two bidders. Then M (ksm) is not false-name-proof.Proof. Given the valuations constructed in the proof of Theorem 60, bidder3 gains by pseudonymously bidding also as bidder 1, and so truth telling isnot a dominant strategy for bidder 3. ?4.4.2 Monotonicity in the set of goodsHere we show that we can also obtain the same impossibility results as inTheorem 60 when we define revenue monotonicity over the set of goodsinstead of over the set of bidders. This result may be more intuitive thanour first result, as it relies on the fact that adding goods to an auction canreduce the level of competition between the bidders.An auction mechanism is good revenue monotonic if and only if theauctioneer never collects more money by dropping a good (see Definition 102in Appendix B.2.3).Corollary 62. Let ?G? ? 3 and ?N? ? 3. Let M (ksm) be a CA mechanismdefined for known single-minded bidders that offers dominant strategiesto the bidders and satisfies participation, consumer sovereignty, and weakmaximality with respect to at least two bidders. Then M (ksm) is not goodrevenue monotonic.Proof. The claim follows from the proof of Theorem 60 with some minormodifications: (i) add an extra good g3 to bidder 1?s bundle b1; (ii) insteadof dropping bidder 1 in Part 2, drop g3?then bidder 1?s valuation for allavailable bundles is 0. ?734.4. Related impossibility results4.4.3 Outcomes in the CoreCoalitional game theory focuses on groups of players and the utility they canachieve together. It is relatively standard (see, e.g., Ausubel and Milgrom [4];Day and Milgrom [13]) to describe efficient auction mechanisms as coalitionalgames. This theory can be useful for discussing what happens to an auction?srevenue when bidders are added or removed.Modeling Efficient Mechanisms as Coalitional GamesA transferable utility (TU) coalitional game is defined by a set of playersNp and a characteristic function w that maps each coalition of players Sto the coalition?s value, w(S). The grand coalition is the coalition of allplayers. An imputation is a payoff profile in which each player receives anonnegative payoff and the sum of the payoffs does not exceed the grandcoalition?s value.7 An efficient combinatorial auction naturally defines a TUcoalitional game. Define Np as the set of participating bidders, N , plus theseller whom we denote by 0. An efficient auction game is then defined asfollows.Definition 63 (Efficient auction game). For any coalition S ? Np, definethe coalition?s value asw(S) = {maxa?AS,G?i?S?{0} vi(ai) 0 ? S,0 0 /? S.Intuitively, in an efficient auction game, the value of a coalition consistingof any set of players S including the seller is the maximum social welfareachievable under S. When the seller does not belong to a coalition, thecoalition?s value is zero.In an auction, the mechanism picks a specific imputation by imposingthe chosen allocation and payments. We call this auction?s imputation. In anauction game, define the payoff of the seller under the auction?s imputationas the auction?s revenue, pi0 = R = ?i?N pi. Define bidder i?s payoff as herutility from the auction, pii = ui = vi ? pi. Observe that in an efficient auctiongame ?i?Np pii = w(Np).7In the literature, it is usually also required that imputations be efficient. Here,we slightly modified the common definition so that we can later extend it to inefficentmechanisms.744.4. Related impossibility resultsDefinition 64 (Core in TU coalitional game). An imputation pi is in thecore of a TU coalitional game if and only if no subset of players can achievehigher payoff:?S ? Np, ?j?Spij ? w(S).If an auction?s imputation is in the core, no coalition has an incentive todeviate from it. (Observe that all coalitions that do not involve the sellerhave zero value; thus, a deviating coalition would always involve the sellerand a subset of the bidders.) Note that we allow for the possibility thatthe grand coalition (in addition to smaller coalitions) would make such adeviation. We say that the outcome of an auction mechanism is in the core ifthe auction?s imputation is in the core. Recall that any efficient mechanismis maximal with respect to all bidders. Our impossibility result then impliesthe following corollary.Corollary 65. Let ?G? ? 2 and ?N? ? 3. Let M (ksm) be a CA mechanismdefined for known single-minded bidders that offers dominant strategies to thebidders, and that satisfies participation, consumer sovereignty, and efficiency.Then, there exists a valuation profile for which the auction?s imputation doesnot belong to the core.This result follows as a special case of Corollary 68, so we omit the proof.Modeling Inefficient Mechanisms as Coalitional GamesThe literature on modeling auctions as coalitional games focuses on efficientmechanisms. This makes sense under the assumption that any deviatingcoalition can achieve a social welfare maximizing outcome. Recall that inan auction game, the payoff of the seller is the auction?s revenue and thepayoff of each bidder is her utility. If one attempts to describe an inefficientauction mechanism as a TU game following Definition 63, the outcome ofthe auction is not guaranteed to be in the core. This is because the sum ofthe payoffs may not add up to the grand coalition?s value. In other words,if the auction mechanism chooses an inefficient outcome then the grandcoalition has an incentive to deviate to an efficient outcome. However, if aseller elects to use an inefficient mechanism, it is inconsistent to then imagineall bidders and the seller jointly deviating to an efficient allocation. Theuse of an inefficient mechanism can nevertheless make sense, e.g., becauseregulatory or computational constraints may limit the set of outcomes thatcan be achieved. Therefore, here we aim to model inefficient mechanisms as754.4. Related impossibility resultscoalitional games. Specifically, we discuss three alternate coalitional gamemodels of the auction game, none of which obviously dominates the others.In the first alternative, which makes minimal changes to Definition 63,we assume that players can reach the efficient allocation for all but the grandcoalition. (That is, we assume that the coalition?s value for all coalitionsexcept the grand coalition is as stated in Definition 63.)In what follows, let vS denote the valuation profile of the bidders in S.That is, vS is the restriction of v to the bidders in S and is derived from vby replacing the valuation of any bidder i /? S by ?.Definition 66 (Inefficient auction game (first alternative)). For any coalitionS ? Np, define the coalition?s value asw(S) =??????????i?S?{0} vi(ai(vS)) S = Np,maxa?AS,G?i?S?{0} vi(ai) 0 ? S and S ? Np,0 0 /? S.In the second alternative, we assume that players have to obey themechanism?s allocation choice under all coalitions, rather than only underthe grand coalition.Definition 67 (Inefficient auction game (second alternative)). For anycoalition S ? Np, define the coalition?s value asw(S) = { ?i?S?{0}vi(ai(vS)) 0 ? S,0 0 /? S.The second alternative may seem more plausible than the first one. Wedo not need to choose between them, however, as both lead to the followingimpossibility result.Corollary 68. Let ?G? ? 2 and ?N? ? 3. Let M (ksm) be a CA mechanismdefined for known single-minded bidders that offers dominant strategiesto the bidders and satisfies participation, consumer sovereignty, and weakmaximality with respect to at least two bidders. Define the auction game asin Definition 66 or Definition 67. Then, there exists a valuation profile forwhich the auction?s imputation does not belong to the core.Proof. The proof can be derived from the proof of Theorem 60 by slightmodifications. First, construct valuations as in the proof of Theorem 60,but now choose v2 to satisfy the constraint v2 > max(cv2(?,?,v?1 + v?3 +?), cv2(?,?,?),v?1 + v?3 ). Then, notice that in the auction game defined764.4. Related impossibility resultsas in either of Definitions 66 or 67, the auctioneer must award bidder 2her desired bundle when she is the only present bidder, as by constructionv2 > cv2(?,?,?). Therefore, w({2,0}) = v2. Furthermore, the coalition ofthe seller and bidder 2 has an incentive to deviate from the grand coalitionsince w({2,0}) = v2 > v?1 + v?3 ? R. In other words, the seller can sell thebundle to bidder 2 for the price of p?2, v?1 + v?3 < p?2 < v2, making both himselfand bidder 2 better off. ?In the coalitional game formulations that we have considered so far,the mechanism only dictates its choice of allocation to some or all of thecoalitions?specifically, to the grand coalition in Definition 66 and to allcoalitions in Definition 67. We may want to assume that the mechanismimposes not only its choice of allocation, but also its choice of payments,thus, disallowing side payments between bidders. This motivates our thirdcoalitional game model, which describes an inefficient auction game as acoalitional game with nontransferable utility (NTU).Formally, a NTU coalitional game is defined by a set of players Np anda characteristic function w that maps each coalition of players S to a setof real-valued vectors describing different sets of payoffs achievable by themembers.Definition 69 (Core in an NTU coalitional game). A payoff vector pi ? w(Np)is in the core of a NTU coalitional game if and only if ?S ? Np, ??x ? w(S)such that ?i ? S,pii ? xi and ?j ? S,pij < xj.Definition 70 (Inefficient auction game (third alternative)). Let the char-acteristic function w map each coalition S ? Np to a single real-valued vectorin which each player?s payoff is exactly her utility under the mechanism?schosen allocation and taking into account her payment to the mechanism,when the set of participating bidders is S ? {0}.For known single-minded bidders, all mechanisms that involve only a sin-gle bidder i, that satisfy participation, and that offer dominant strategies canbe understood as offering i her desired bundle at a fixed price, cvi(?, . . . ,?).The following result can be understood as showing that any mechanismsatisfying our conditions either already sets cvi(?, . . . ,?) in such a way thatboth the seller and i can gain when all other bidders are excluded from themechanism, or can be modified to do so. Intuitively, our counterexamplecannot be used to show that a given (unmodified) mechanism always suffersfrom this problem because, while i is always better off when the other biddersare dropped, the seller could be worse off if cvi(?, . . . ,?) is set too low.774.4. Related impossibility resultsCorollary 71. Let ?G? ? 2 and ?N? ? 3. Let M (ksm) be a CA mechanismdefined for known single-minded bidders that offers dominant strategiesto the bidders and satisfies participation, consumer sovereignty, and weakmaximality with respect to at least two bidders. Then there exists a CAmechanism M ? that allows bidders to express the same preferences as inM (ksm) and that1. has the same allocation and payment functions as M (ksm), except thatit may have a different cvi(?, . . . ,?) for some (single) i ?N;2. satisfies participation, consumer sovereignty, and weak maximality withrespect to at least two bidders; and3. chooses an outcome that is not guaranteed to belong to the core.Proof. The result follows from the proof of Theorem 60 by slight modification.Consider the three-bidder two-good setting in the proof of Theorem 60. Toemphasize that M (ksm) may already choose outcomes that do not belong tothe core, our proof considers two cases.Case 1: cv2(?,?,?) > ?{1,2,3},G,b,1,g1 + ?{1,2,3},G,b,3,g3 . Pick an arbitrarypositive k < 12(cv2(?,?,?)??{1,2,3},G,b,1,g1 ??{1,2,3},G,b,3,g3). Construct valu-ations as in the proof of Theorem 60, given the chosen k, but now choose v2to satisfy the constraint v2 > max(cv2(?,?,v?1 +v?3 +?), cv2(?,?,?),v?1 +v?3 ).By Corollary 59, M (ksm)?s revenue when only bidder 2 participates isR2 = cv2(?,?,?) > v?1 + v?3 ? R. The utility of bidder 2 in this case?i.e.,when only bidder 2 participates?is u2 = v2?cv2(?,?,?) > 0, which is strictlygreater than bidder 2?s utility when all three bidders participate. Thus, theoutcome chosen by M (ksm) does not belong to the core; let M ? =M (ksm).Case 2: cv2(?,?,?) ? ?{1,2,3},G,b,1,g1 +?{1,2,3},G,b,3,g3 . Construct M? to bethe same as M (ksm), except choose cv2(?,?,?) such that cv2(?,?,?) >?{1,2,3},G,b,1,g1 + ?{1,2,3},G,b,3,g3 . Observe that this change preserves domi-nant strategies (this property is unaffected by the specific value taken bycv2(?,?,?)), participation (bidder 2 pays nothing if she loses), consumersovereignty (cv2(?,?,?) is finite), and weak maximality with respect tobidders 1 and 3 (nothing changes for these bidders). Then, the proof followsfrom the argument in Case 1. ?Earlier, when we modeled inefficient auctions as TU games, we assumedthat bidder 2 and the seller could divide gains between them, meaning thatthe pair were always better off forming a coalition. Under the NTU model,that division must be described explicitly through the auction?s payment784.5. Chapter summaryrule. The proof of Corollary 71 shows that such a division can always beaccomplished by an appropriate choice of cvi(?, . . . ,?).4.5 Chapter summaryIn this chapter, we investigated whether there exists any deterministic,dominant-strategy truthful CA mechanism that satisfies participation, con-sumer sovereignty and weak maximality with respect to at least two biddersand that is revenue monotonic. We showed that no such mechanism ex-ists, whenever bidders are allowed to express arbitrary known single-mindedpreferences; as corollaries, we were able to show similar results concerningmechanisms that yield weakly decreasing revenue when goods are droppedand false-name-proof mechanisms. We also investigated the relationshipbetween a mechanism being revenue monotonic and the mechanism yieldingan outcome that belongs to the core. More specifically, we showed thatfor any mechanism that satisfies our desired properties, the outcome of themechanism is not guaranteed to belong to the core.79Chapter 5Revenue Monotonicity inDominant-Strategy Truthful,Randomized CombinatorialAuctionsIn the previous chapter, we proved that no revenue monotonic mechanism ex-ists in a very broad class of deterministic, DS truthful combinatorial auctionmechanisms. There are many cases ([14, 16, 17, 37]) in which randomizedmechanisms are able to achieve desirable properties that cannot be obtainedby deterministic mechanisms. In this chapter, we show that it is possibleto circumvent our impossibility result, at least for known single-mindedbidders, by moving to the realm of randomized mechanisms, which enablesus to relax consumer sovereignty, and proposing a class of combinatorial auc-tion mechanisms that we call ?stepwise? randomized combinatorial auctionmechanisms.The rest of the chapter is organized as follows. In Section 5.1 we de-fine randomized CA mechanisms, followed by our definition of stepwiserandomized CA mechanisms in Section 5.2. We then show how to con-struct revenue-monotonic stepwise randomized mechanisms in Section 5.3,though this construction can sometimes require exponential time. Finally,in Section 5.4 we give a polynomial-time algorithm for constructing ourmechanism.5.1 Randomized combinatorial auctionsA randomized direct Combinatorial Auction (CA) mechanism (RCAM) de-fined for known single-minded bidders over N and G produces a distributionover pairs (a, p) where a and p are defined exactly as in deterministic CAmechanisms (Section 4.1.2).In the previous chapter we defined several properties that we would like805.1. Randomized combinatorial auctionsto require of CA mechanisms. Moving to the randomized case will requirereinterpretations of these properties, particularly of consumer sovereignty.5.1.1 Dominant strategy truthfulness for RCAM?sA randomized CA mechanism M is dominant strategy (DS) truthful inexpectation if and only if truth-telling is a dominant strategy for all biddersin the game induced by expectation.Let pia(v?) denote the probability that allocation a ? AG will be chosengiven declared values v? . Let pi(v?) denote the expected payment of i. Letwi(v?) denote the probability that bidder i wins?that is, i is allocated abundle that includes bi. Note that the pia(v?)?s fully define wi(v?)?s. Formally,wi(v?) = ??a?AG,ai?bipia(v?). (5.1)The following theorem characterizes the class of DS truthful randomizedmechanisms defined over known single-minded bidders (indeed, for any singleparameter domain). For ease of notation the theorem, and also Corollary 73,are stated for mechanisms in which the bidders who bid 0 lose and pay 0.Theorem 72 (see, e.g. Nisan [45]). A randomized mechanism defined overknown single-minded bidders is DS truthful in expectation, and satisfiesparticipation, if and only if for all N ?N, G ? G, b = (b1, b2, . . . , bn) ? (2G)nand for every bidder i ? N and every fixed v??i we have that1. the function wi(v?i, v??i) is monotonically non decreasing in v?i.2. pi(v?i, v??i) = v?i ?wi(v?i, v??i) ? ?t=v?it=0 wi(t, v??i)dt.5.1.2 Revenue monotonicity for RCAM?sA randomized CA mechanism is revenue monotonic if and only if dropping abidder never increases the mechanism?s expected revenue (see Definition 108in Appendix B.3).5.1.3 Maximality for RCAMsWe chose to use weak maximality for deterministic mechanisms because itstrengthens the impossibility result we provide in Chapter 4. For randomizedmechanisms, however, we will prove a positive result, namely the existence ofrevenue monotonic randomized mechanisms with several desired properties.To make our positive result as strong as possible, we use a more generalnotion of maximality. Informally, a mechanism is maximal with respect815.1. Randomized combinatorial auctionsto a bidder i if, whenever i values any subset of goods s sufficiently, themechanism does not withhold that bundle or give the goods in the bundleaway to bidders who do not value them.Let M (ksm) be a truthful randomized CA mechanism defined for knownsingle-minded bidders, with set of bidders N , set of goods G and set of(known) bundles b = (b1, . . . , bn). M (ksm) is maximal with respect to bidder iif and only if there exists a set of nonnegative finite constants {?N,G,i,s ? s ? G}such that the following holds. For any allocation a that is chosen by M (ksm)with probability above zero, either:1. vi(ai) > 0; or2. for any allocation a? with vi(a?i) > ?N,G,i,a?i and a?j = aj ? a?i for all j ? i,it must be the case that for some j, vj(a?j) < vj(aj).5.1.4 Participation for RCAM?sA randomized CA mechanism satisfies participation if and only if any bid-der i for whom wi(v) = 0 makes zero payment to the mechanism. (seeDefinition 109 in Appendix B.3).Corollary 73 (immediate from Theorem 72). A DS truthful mechanismsatisfies participation if and only if it is characterized by a set of feasibleallocation distributions pia(v?)?s that induce monotonic winning probabilityfunctions wi(v?) ?s and pi?s are defined as in Theorem 72.5.1.5 Consumer sovereignty for RCAM?sIt is somewhat harder to decide how to extend our consumer sovereigntydefinition to randomized mechanisms for known single-minded bidders. Wefirst consider two possible extensions to the definition for deterministicmechanisms, which can be seen as opposite extremes. First, we could defineconsumer sovereignty (I) as requiring that, fixing bids of the others, anybidder is able to win any desired bundle with probability one if she bids highenough. Unfortunately, in this case we recover the impossibility result fordeterministic CA mechanisms (Chapter 4).Theorem 74 (informal). Let ?G? ? 2 and ?N? ? 3. Let M (ksm) be a random-ized CA mechanism defined for known single-minded bidders that offers dom-inant strategies to bidders and satisfies participation, consumer sovereignty(I), and weak maximality with respect to at least two bidders. Then M (ksm)is not revenue monotonic.825.2. Stepwise randomized mechanismsOn the other hand, we could define consumer sovereignty (II) as requiringthat any bidder be able to win any desired bundle with some probabilityabove zero if she bids high enough. This leads to a different problem. Considera mechanism M (ksm) with ?N,G,i,s = 0 that chooses a maximal allocationuniformly at random, and charges nothing. Note that each bidder wins herdesired bundle in at least one maximal allocation. Therefore, it is easy toverify that M (ksm) is strategyproof and satisfies participation, consumersovereignty, and maximality with respect to all bidders. It also is revenuemonotonic since it never collects any money.The above arguments suggest that we ought to seek an intermediatedefinition for consumer sovereignty. We thus present the following definition,which roughly requires that, given the valuations of the other bidders, abidder who starts bidding at 0 and then raises her bid can increase herprobability of winning by at least ? at least ? times.Definition 75 ((?-step, ?) Consumer Sovereignty). A randomized CA mech-anism defined for known single-minded bidders satisfies (?-step, ?) consumersovereignty, ? ? 0 and ? > 0, iff for any fixed tuple of bundles b = (b1, . . . , bn)and for some constants 0 = ci,0 < ci,1 < . . . < ci,? < ci,?+1 = ?, ?i ? N, thefollowing holds. For all N ? N, G ? G, bidder i ? N , v??i ? (V (b)N,G)?i, andj < ?, we have that: the winning probabilities, wi?s, are monotonic andfurthermore either wi(ci,si+1, v??i) ? wi(ci,si , v??i) + ? or wi(ci,si+1, v??i) = 1.It is easy to see that if a mechanism satisfies (?-step, ?) consumersovereignty for some ? = k, it then also satisfies (?-step, ?) consumersovereignty for any ? for which 0 ? ? ? k. Observe that the constantsci,si are independent of all bidders? declared valuations; in a sense, they canbe seen as ?bidder-specific, leveled reserve prices.? Thus, while we do notassume that the mechanism designer knows anything about the valuationdistribution(s), if such information is available, it can be useful for settingthese constants.5.2 Stepwise randomized mechanismsRecall that a randomized CA mechanism produces a distribution over al-locations and payments. Here, we propose a simple and useful class ofrandomized CA mechanisms, that we later show includes those that are bothDS truthful and revenue monotonic.Definition 76 (Stepwise Randomized Mechanism). A randomized CA mech-anism defined for known single-minded bidders is stepwise if for some k > 0835.3. A revenue monotonic mechanismpiv?ic4 c5c0 c1 c2 c3 c610Figure 5.1: i?s probability of winning as a function of her bid amount, given fixedbids by the other agents.and some constants 0 = ci,0 < ci,1 < . . . < ci,k < ci,k+1 = ?, ?i ? N, the fol-lowing holds. For all fixed tuples of bundles b = (b1, . . . , bn), for all N ? N,G ? G, bidder i ? N and valuation profiles v??i ? (V (b)N,G)?i, and for allci,si ? v?i < ci,si+1, it is the case that w`(v?i, v??i) = w`(ci,si , v??i), for all ` ? N .We call the mechanism a ?-step randomized mechanism if it satisfies theabove for k = ?.A ?-step randomized mechanism can be interpreted as a mechanism thatfor each bidder i, cares only about specific declared values, ci,0, ci,1, . . . , ci,?and treats any declared value of i between ci,si and ci,si+1 the same as ci,si .In fact, one can easily verify that wi(v?) = wi(c1,s1 , . . . , cn,sn), for all v? whereci,si ? v?i < ci,si+1 for all participating bidders i. If a ?-step randomizedmechanism additionally has the following monotonicity property that either(1) wi(ci,si , v??i) + ? ? wi(ci,si+1, v??i), or (2) wi(ci,si+1, v??i) = 1, then themechanism satisfies (?-step, ?) consumer sovereignty.Figure 5.1 shows a sample wi for a 6-step stepwise randomized mechanism,given fixed bids by the other bidders. Observe that by Theorem 72, if themechanism is to satisfy DS truthfulness and participation, our choice of wimust imply a specific choice of pi. Here, if the bidder declares v?i, she mustpay an amount equal to the area of the shaded region.5.3 A revenue monotonic mechanismIn this section, we construct a ?-step randomized mechanism, which we dubM? , that is DS truthful and revenue monotonic and satisfies participation,maximality and (?-step, ?) consumer sovereignty, for any given ? and for845.3. A revenue monotonic mechanismsome ? > 0. We construct M? such that when a bidder i increases her bidone step, her probability of winning increases by ? unless she wins in allmaximal allocations, in which case her probability of winning is equal to 1.We first give a nonlinear feasibility program F and show that its solutionscorrespond to mechanisms that satisfy all our desired properties. We thenconstruct a quadratically constrained linear program (QCLP) P , and provethat all of its solutions that satisfy one additional constraint also solve F .Finally, we constructively prove that such solutions of P always exist.Given V (b)N,G, for all N ?N let MN be the set of all maximal allocationswith respect to maximality parameters set to zero?that is, ?N,G,i,s = 0,?i ?N,s ? G. Let MN be a set of maximal allocations?that is MN ?MN?suchthat each bidder is either allocated her desired bundle or nothing and suchthat each bidder wins in at least one allocation a ?MN . Let 0? denote thetuple of declared valuations in which all participating bidders bid 0.Lemma 77. For all V (b)N,G, all N? ? N ?N, and all bidders i ? N ?, if i belongsto all allocations a ?MN then i belongs to all allocations a? ?MN ?.Proof. Since i belongs to all a ?MN , then it must be the case that bi does notoverlap with any other bidder?s desired bundle; that is bi?bj = ?,?j ? N, j ? i.Therefore, since N ? ? N , it is also true that bi ? bj = ?,?j ? N ?, j ? i. Thus,i has to belong to all maximal allocations under N ? and therefore to allallocations a? ?MN ? . ?5.3.1 Feasibility programObserve that a mechanism is a mapping from declared valuations to alloca-tion probabilities pia?s and payments pi?s. Here we express such a mappingas a solution to a set of feasibility programs (albeit ones with some nonlinearconstraints, and an uncountably infinite number of both variables and con-straints). Recall that any CA mechanism defined for known single-mindedbidders is able to condition its behavior on G,N , and b (see Section 4.1.2).Because the mechanism is free to behave differently for every G (availableset of goods) and b (set of known bundles of interest for the bidders), wewrite a separate feasibility program for each possible joint assignment tothese variables. Our feasibility program, denoted F and given in Figure 5.2,is thus parameterized by b and G. Note that we assume that the mecha-nism knows the bundles of both participating and non-participating bidders.This assumption will make no difference in what follows, but dramaticallysimplifies notation.855.3.Arevenuemonotonicmechanism0 ? piN,a(v?) ? 1 ?N, v? ,a ?AG (F.a1)?a?AGpiN,a(v?) = 1 ?N, v? (F.a2)wN,i(v?) = ?a?AG,ai?bipiN,a(v?) ?N, i, v? (F.w)wN,l(v?i, v??i) = wN,l(ci,si , v??i) ?N, i, l, si, v? ?ci,si ? v?i < ci,si+1 (F.step)wN,i(v?) ? wN,i(v? ?) ?N, i, v? , v? ??v?i ? v? ?i and v??i = v? ??i (F.mon)pN,i(v?i, v??i) = v?i ?wN,i(v?i, v??i) ? ?t=v?it=0wN,i(t, v??i)dt ?N, i, v? (F.sp)piN,a(v?) = 0 ?N, v? ,a ?MN (F.max)?ipN,i(v?) ??i?lpN?{l},i(v??l) ?N, l, v? (F.rm)wN,i(ci,si+1, v??i) ? wN,i(ci,si , v??i) + ? or wN,i(ci,si+1, v??i) = 1 ?N, i, si, v??i ? (V(b)N,G)?i(F.cs)? > 0 (F.?)Figure 5.2: Nonlinear feasibility program F (b,G). Constants are v? ?s and ci,si ?s. Variables are piN,a?s, wN,i?s, pN,i?sand ?. We adopt the conventions that N indexes subsets of N, i and l index elements of N , si indexes elementsof {0, . . . , ?}, and v? indexes elements of V (b)N,G. Observe that because this last set is (uncountably) infinite, thefeasibility program involves an infinite number of both variables and constraints.865.3. A revenue monotonic mechanismLemma 78. Any solution to F (V (b)N,G,G) for all V(b)N,G and G ? G, correspondsto a ?-step randomized mechanism that satisfies DS truthfulness, participation,maximality, (?-step, ?) consumer sovereignty, and revenue monotonicity.Proof. We must ensure that a solution to the F (V (b)N,G,G)?s induces a validmechanism. First, it is necessary to ensure that piN,a?s correspond to probabil-ities. This is achieved by Constraints (F.a1) and (F.a2). Second, Constraint(F.w) ensures that these allocation probabilities fully define winning proba-bilities, as required by Equation (5.1). Third, Constraint (F.step) ensuresthat our mechanism is stepwise randomized.Now we must show that the mechanism satisfies our five desired properties.First, Constraints (F.mon) and (F.sp) together entail both DS truthfulnessand participation (by Theorem 72). Second, Constraint (F.max) entailsmaximality. Third, Constraint (F.rm) entails revenue monotonicity. Finally,Constraints (F.mon), (F.cs) and (F.?) together ensure that the mechanismsatisfies (?-step, ?) consumer sovereignty for a given ? and some ? > 0. ?5.3.2 Quadratically constrained linear programConsider quadratically constrained linear program (QCLP) P (V (b)N,G,G) inFigure 5.3. We will prove that if P (V (b)N,G,G) can be solved for all V(b)N,G andG ? G with ? > 0 then we can construct solutions for the F (V (b)N,G,G)?s andconstruct our desired mechanism, M? . Recall that F is parameterized byan infinite size valuation space, V (b)N,G, and thus has an infinite number ofvariables and constraints. The main idea in this section is that we can movefrom an infinite-sized F to a finite-sized QCLP P by working with a finitesized valuation space, /V (b)N,G. Specifically, for each bidder i we only needto consider the finite set of possible declared values ci,0, . . . , ci,s? . Formally,/V (b)N,G = {v ?v ? V(b)N,G,?i ? N,?si ? {0, . . . , ?} ? vi = ci,si}. To show that anysolution of P corresponds to a solution of F we provide a mapping from/V (b)N,G to V(b)N,G.To provide intuition for our proof, we state P (V (b)N,G,G) for a simpleexample and show how we can find a solution to it that sets ? > 0. Considerthe bidder-bundle setting described in the introduction, which we used todemonstrate that VCG is not revenue monotonic. That is, let G = {g1, g2}and N = {1,2,3}; bidders 1, 2 and 3 are known single-minded, where thebundles valued by bidders 1, 2, and 3 are b1 = {g1}, b2 = {g1, g2} and b3 = {g2}respectively. Let S3,2 denote this three-bidder, two-good setting. We statethe constraints and explain the solution for the case when all bidders are875.3. A revenue monotonic mechanismpresent and all goods are for sale. That is, let G = G and N =N. One caneasily follow the same approach for other choices of G and N , many of whichare trivial.It is easy to verify that there is exactly one choice for MN : we have toeither award bidder 2 her desired bundle, or award bidders 1 and 3 eachtheir desired bundle. Therefore MN = {(?,{g1, g2},?), ({g1},?,{g2})}. Leta2 = (?,{g1, g2},?) and a1,3 = ({g1},?,{g2}). Thus, for all /?v ? /V(b)N,G: (i)piN,a( /?v) = 0, for all a ? AG such that a ? a2,a1,3 constitute (P.pi1), (ii)0 ? piN,a( /?v) ? 1 if a = a2 or a = a1,3 constitute (P.pi2), and (iii) piN,a2( /?v) =1 ? piN,a1,3( /?v) constitute (P.pi3).As each bidder i belongs to exactly one allocation a ?MN , Constraints(P.q1)?(P.q5) can be expressed as qN,a,i = 0, for all a ? a2,a1,3 and all i ? N ,and qN,a1,3,1 = qN,a1,3,3 = 1, qN,a2,2 = 1, qN,a1,3,2 = ?1, and qN,a2,1 = qN,a2,3 = ?1.Intuitively, qN,a,i ?? denotes the change to piN,a when bidder i increases herbid by one step. We constrain the qN,a,i?s in (P.pi4) such that when i increasesher bid by one step?from ci,si to ci,si+1 , the probability that a ?MN will bechosen weakly increases if i belongs to ai, and weakly decreases otherwise.One can illustrate constraints in (P.pi4) by the following graph represen-tation. Let GRN be a graph of (? + 1)?N ? nodes, each corresponding to adifferent potential declared valuation profile of bidders in /V (b)N,G. Let therebe a directed edge between each pair of nodes that differ in only one of thebidders? declarations, and in which this difference is an increase of exactly onestep (i.e., from ci,si to ci,si+1). In other words, we can move from one nodeto another by increasing one bidder?s bid by one step. If an edge indicatesan increase in bidder i?s declared value, we say the edge is of type ei. Now,assign ?MN ? labels to each edge, one for each allocation in MN . Allocationa?s label on an edge of type ei denotes the change to piN,a by moving alongan edge of type ei (which increases bidder i?s bid amount by one step) andis equal to qN,a,i ? ?. Define the cost of a path as the absolute value of thesum of the labels of the edges in the path.Lemma 79. In each GRN and for all allocations a ?MN , all paths betweenany two given nodes s and t have the same cost: ?piN,a(t) ? piN,a(s)?.Proof. For all i ? N , the number of edges of type ei is the same in all pathsbetween s and t. Since all edges of type ei have the same label correspondingto allocation a, the sum of a?s associated labels along any path between sand t is equal to piN,a(t) ? piN,a(s). ?885.3.Arevenuemonotonicmechanismmaximize ? subject to:piN,a( /?v) = 0 ?N, /?v ,a ?AG ?MN (P.pi1)0 ? piN,a( /?v) ? 1 ?N, /?v ,a ?MN (P.pi2)?a?MNpiN,a( /?v) = 1 ?N, /?v (P.pi3)piN,a( /?v) = piN,a(0?) +?i(qN,a,i ? ? ? si) ?N, /?v ,a ?MN ? /?v i = ci,si (P.pi4)qN,a,i = 0 ?N, i,a ?MN ??a? ?MN ,a?i = bi (P.q1)0 ? qN,a,i ? 1 ?N, i,a ?MN ?ai = bi (P.q2)? 1 ? qN,a,i ? 0 ?N, i,a ?MN ?ai = ? (P.q3)?a?MN ?ai=biqN,a,i = 1 ?N, i??a? ?MN and a?i = ? (P.q4)?a?MN ?ai=?qN,a,i = ?1 ?N, i??a? ?MN and a?i = ? (P.q5)Figure 5.3: Quadratically constrained linear program P (V (b)N,G,G). Variables are piN,a?s, qa,i?s and ?. We adopt theconventions that N indexes subsets of N, i indexes elements of N , si indexes elements of {0, . . . , ?}, and /?v indexeselements of /V (b)N,G = {v ?v ? V(b)N,G,?i ? N,?si ? {0, . . . , ?} ? vi = ci,si}.895.3. A revenue monotonic mechanismFigure 5.4 represents GRN for S3,2. On each edge, the label correspondingto a1,3?which denotes the change in piN,a1,3 due to moving along the edge?is equal to qN,a1,3,i ? ? for some i ? N and is exactly the negative of thelabel corresponding to a2. The the cost of the longest path (e.g., between(c1,0, c2,? , c3,0) and (c1,? , c2,0, c3,?)) is 3??.Now let us move to the proof of our general result.Lemma 80. Any solution to P (V (b)N,G,G) with ? > 0 corresponds to a solutionto F (V (b)N,G,G).Proof. Let a solution to P (V (b)N,G,G) for which ? > 0 be given. Thus we havepiN,a( /?v) for all /?v ? /V(b)N,G. To give a solution to F (V(b)N,G,G), we have tomap the piN,a( /?v)?s to the allocation probabilities, winning probabilities andpayments in F (V (b)N,G,G). For all v? ? V(b)N,G, letpiN,a(v?) = piN,a( /?v) (5.2)where /?v i = ci,si for some si ? {0, . . . , ?} such that ci,si ? v?i < ci,si+1. Also, forall v? ? V (b)N,G and all i ? N letwN,i(v?) = ?a?AG,ai?bipiN,a(v?),and (5.3)pN,i(v?) = ?1?s?i?si ?ci,si?v?i<ci,si+1ci,s?i[wN,i(ci,s?i , /?v?i)?wN,i(ci,s?i?1, /?v?i)]. (5.4)We show that the above piN,a?s, wN,i?s, pN,i?s and ? indeed constitute asolution to F (V (b)N,G,G).Note that (5.3) is in fact (F.w). Also note that ? > 0 induces (F.?). It iseasy to see that five of the constraints in F are directly induced by (5.2), (5.3)and a set of constraints in P . Precisely, (i) (F.a1) is induced by (5.2), (P.pi1)and (P.pi2); (ii) (F.a2) is induced by (5.2) (P.pi1) and (P.pi3); (iii) (F.max) isinduced by (5.2) and (P.pi1)?this simply follows the fact that any a ?MNis certainly not in MN ; (iv) (F.w) is induced by (5.3); and (v) (F.step) isinduced by (5.2) and (5.3).(F.mon) is induced by (P.pi1), (P.pi3), (P.pi4), (P.q1)?(P.q4), (5.2) and(5.3). To see this, note that we can write wN,i(v?) = ?a?AG,ai?bi piN,a(c1,s1 , . . . ,cn,sn)= ?a?M,ai=bi(piN,a(0?) +?`?N(qN,a,` ? ? ? s`)). The first equality follows905.3. A revenue monotonic mechanism(0, ?, 0)(1, ?, 0) (0, ?-1, 0) (0, ?, 1)(1, ?-1, 0) (1, ?, 1) (0, ?-1, 1)(0, ?-2, 0) (0, ?, 2)(2, ?, 0)(?, 0, ?)(?-1, 0, ?) (?, 1, ?) (?, 0, ?-1)(?-1, 1, ?)(?-1, 0, ?-1) (?, 1, ?-1)(?, 2, ?) (?, 0, ?-2)(?-2, 0, ?) 3?3?-13?-2012 Figure 5.4: Graph GRN for our three-bidder, two-good example. Each node (a, b, c)denotes (c1,a, c2,b, c3,c).The label corresponding to a1,3 on directed edges from levelk to k + 1 is ? and on directed edges from level k + 1 to k is ??, 0 ? k < 3? ? 1.from (5.2) and (5.3) and the second equality follows from (P.pi1) and (P.pi4).Now, if (1) ai = bi,?a ?MN , then, wN,i(v?) = ?a?M,ai=bi piN,a(0?) = 1. The firstequality holds by (P.q1) and the second equality holds by (P.pi3). Otherwise,let v? ? = (v? ?i , v??i). Then wN,i(v? ?)?wN,i(v?) = ?a?MN ,ai=bi(qN,a,i ?? ?(s?i?si)) =? ? (s?i ? si). The first equality holds by (P.pi4) and the second equality holdsby (P.q4). Now, if v?i ? v? ?i then si ? s?i and thus (2) wN,i(v?) ? wN,i(v? ?). Thus,by (1) and (2), we have (F.mon).(F.cs) is induced by the same set of constraints as (F.mon); that is, by(P.pi1), (P.pi3), (P.pi4), (P.q1)?(P.q4), (5.2) and (5.3). Following the sameargument as above, if ai = bi,?a ?MN , then, wN,i(v?) = ?a?M,ai=bi piN,a(0?) =1. Otherwise, wN,i(ci,si+1, v??i) ?wN,i(ci,si , v??i) = ?. Thus we get (F.cs).(F.sp) is induced by (F.step) and (5.4). This is because by (F.step), theintegral part of (F.sp) is over a discrete domain and thus we can write (F.sp)as (5.4).915.3. A revenue monotonic mechanism(F.rm) is induced by (5.4) and the rest of the constraints in F . As statedabove, if bidder i belongs to all a ? MN , then ?v? , wN,i(v?) = 1 and thuspN,i(v?) = 0. Otherwise, pN,i(v?) = ?1?s?i?si?ci,si?v?i<ci,si+1 ci,s?i ? ?. By Lemma 77,it is clear that dropping bidder j ? i either does not change the payment ofbidder i or sets it to zero (if dropping j entails a case in which i belongs toall the allocation in the support of the mechanism). Thus (F.rm) followsimmediately. ?Constraints in P (V (b)N,G,G) are all linear or quadratic, and so our problemof identifying mechanism M? can be reduced to solving a set of quadraticallyconstrained linear programs where the objective function in each is to maxi-mize ?, and then checking each for ? > 0. However, we can do even better.The next result demonstrates that this QCLP is always feasible; later, wewill show how to analytically construct a solution with ? > 0.Lemma 81. Let P (V (b)N,G,G) be given. For any given piN,a(0?) > 0,?N ?N,a ?MN , such that ?a?MN piN,a(0?) = 1, and any given qN,a,i, ?N ? N, i ?N,a ?MN , such that (P.q1)?(P.q5) are satisfied, there exists a solution to(P.pi1)?(P.pi4) that sets ? > 0.Proof. Let piN,a( /?v) = 0, ?a ?AG ?MN . Thus we have (P.pi1). We can write(P.pi2) and (P.pi4) as0 ? piN,a(0?) +?i(qN,a,i ? ? ? si) ? 1. (5.5)Let ta denote ?i?N(qN,a,i ? si). If ta = 0 then let piN,a = piN,a(0?); bythe assumption of the lemma, (5.5) holds. Otherwise, we can rewrite eachequation (5.5) in which ta < 0 as ? ??piN,a(0?)ta , and ta > 0 as ? ?1?piN,a(0?)ta . Now,we have many constraints of the form ? ? k for different positive k?s. Denotethe smallest k by k? and set ? = k?. Thus (5.5) holds and furthermore, sinceall piN,a(0?)?s and all k?s are greater than zero, k? = ? is greater than zero.Note that if ta = 0 in all constraints (5.5), any ? > 0 would work.It remains to show that (P.pi3) holds. We can write ?a?MG pia( /?v) =?a?MN (piN,a(0?)+ ?i(qa,i ? ? ? si)) = ?a?MN piN,a(0?)+ ??a?MN ?i(qN,a,i ? si) =1+??i?a?MN (qN,a,i ?si) = 1+??i si ?(?a?MN ,ai=? qN,a,i+?a?MN ,ai=bi qN,a,i) =1 + 0 = 1. The first equality holds by (P.pi4), the third equality holds bythe lemma?s assumption. and the fifth equality holds by (P.q1), (P.q4) and(P.q5). ?Theorem 82. For any given ? ? 0, there exists a ?-step randomized mecha-nism that is DS truthful and revenue monotonic and satisfies participation,maximality and (?-step, ?) consumer sovereignty, for some ? > 0.925.4. A polynomial time algorithmProof. It is easy to verify that regardless of V (b)N,G and G we can alwaysgenerate piN,a(0?)?s such that ?a?MN piN,a(0?) = 1. For example, we can setpiN,a(0?) = 1?MN ? . In fact, there are infinitely many such assignments ofpiN,a(0?)?s. Similarly, there exist infinitely many random assignments of theqN,a,i?s that satisfy (P.q1)?(P.q5). Now note that except for ?, P (V(b)N,G,G)?shave no other variable in common. Thus, if we set ? to be the minimumof ??s in the solutions to P (V (b)N,G,G)?s, the rest of the proof directly followsfrom Lemma 80 and Lemma 81. ?In the example, it is clear that 3?? ? 1 and thus ? ? 13? . Since we havecomplete freedom in choosing piN,a(0)?s, we can set them appropriately?thatis to set piN,a1,3(0?) = 1/3 and piN,a2(0?) = 2/3?so that ? =13? is feasible. Aswe said earlier, we described the solution of S3,2 for N =N and G = G. Tofully define the mechanism we simply have to find ? for all choices for N andG and keep the smallest ??which indeed is ? = 13? .Our QCLP formulation characterizes a class of randomized mechanismsthat satisfy our desired properties. However, a mechanism designer may alsohope to optimize some additional objective function such as social welfare orrevenue. In our construction above, we have full or partial freedom to set?, MN , piN,a, and qN,a,i. Here, we briefly discuss tuning ?; we leave furtherinvestigations of optimization for future work.Fixing MN ?s, piN,a?s and qN,a,i?s, we obtain a DS truthful mechanism,which yields the same social welfare no matter how we set ?. This is becausethe social welfare depends only on the allocation and bidders? true valuations.Since fixed sets of MN ?s and piN,a?s always produce the same distributionover the allocation space, the social welfare is always the same in expectationregardless of ?. On the other hand, ? does affect payments; indeed, themaximum ? maximizes revenue. Furthermore, the bigger ? is, the stronger isthe consumer sovereignty guarantee offered to bidders. Thus maximizing ?offers (different) benefits both to the auctioneer and to bidders.5.4 A polynomial time algorithmAt first glance, it may seem that constructing M? requires time exponential inthe number of potential bidders N and goods G, since P has an exponentialnumber of variables and constraints. As the example S3,2 in Section 5.3shows, some settings are ?easy to solve? because of their special bidder-bundlestructure that let us circumvent the exponential nature of the problem. It935.4. A polynomial time algorithmturns out that, even in the general case, we can always construct MN for allV (b)N,G, G, and N ?N in polynomial time in ?N ? and ?G?.Theorem 83. For any given V (b)N,G, G and N , in time polynomial in ?N ? and?G? we can find a set of maximal allocations MN , where ?N,G,i,s = 0, suchthat each bidder i ? N belongs to at least one allocation in MN and for alla ?MN and all i ? N , ai = bi or ai = ?.Proof. Set MN = ?. Randomly order all the bidders in N and mark them as?unawarded?. Then run the following greedy algorithm. (1) Set G? = G. Startfrom the top of the list and award each ?unawarded? bidder i her desiredbundle bi if available, and remove bi from G?, until there are either no moregoods or no more bidders. Mark all the bidders that have awarded theirdesired bundle as ?awarded?. (2) Start from the top of the list and awardeach ?awarded? bidder i her desired bundle bi if available, and remove bifrom G?, until there are either no more goods or no more bidders. (3) Addthe current allocation to MN . If there is any bidder marked as ?unawarded?then go to step 1. Otherwise, stop.Steps 1-3 take O(?N ??G? log(?G?)) time and we have to run them at most?N ? times, since in each run at least one bidder is marked as ?awarded?. Thus,the algorithm take time O(?N ?2?G? log(?G?)) to run. We add one allocationto MN at the end of each run; thus MN is of size O(?N ?). ?Unfortunately, finding a desirable solution among the set of feasiblesolutions?e.g. a solution that maximizes ??can be complicated and de-pendent on the architecture of the given bidder-bundle setting, our choiceof MN ?s and the other parameters. However, we can construct a feasiblesolution in polynomial time giving a (loose) lower bound on the maximum ?that satisfies our constraints.Theorem 84. For any given V (b)N,G,G and N , we can construct a ?-steprandomized mechanism M? in time polynomial in ?N ? and ?G? such that M?is DS truthful and revenue monotonic and satisfies participation, maximalityand (?-step, ?) consumer sovereignty where ? = 1n2? .Proof. Construct MN as in the proof of Theorem 83. If ?MN ? = 1, then thesolution is trivial. (All participating bidders win with probability equal toone.) Otherwise, if ?MN ? ? 2, let qN,a,i = 1?MN,i? , ?a ?MN , i ? N , where MN,iis the set of allocations a ?MN that i belongs to. Therefore, 1n ? qN,a,i ? 1.Let piN,a = 1?MN ? . Therefore,1n ? piN,a ?12 . Consider the combinationof constraints (P.pi2) and (P.pi4) in the form we presented in the proof945.5. Chapter summaryof Lemma 81. That is ? ? ?piN,a(0?)ta if ta < 0, and ? ?1?piN,a(0?)ta if ta > 0,where ta = ?i?N(qN,a,i ? si). By our choice of piN,a?s and qN,a,i?s in above,?piN,a(0?)ta ?1n2? and1?piN,a(0?)ta ?12n? . Thus, max(?) ? min{1n2? ,12n? } =1n2? . ?5.5 Chapter summaryIn this chapter we showed that the impossibility result of Chapter 4 canbe circumvented by stepwise randomized mechanisms. That is, there existrandomized CA mechanisms, for known single-minded bidders, that are bothDS truthful and revenue monotonic and furthermore satisfy participation,maximality, and a reasonably relaxed version of consumer sovereignty. Itwould be interesting to investigate whether our mechanisms can be extendedto unknown single-minded bidders and other variations in the auction setting.Another interesting future direction would be to explore connections tothe core and to false-name bidding, and to identify stepwise randomizedmechanisms that maximize objective functions of interest. Finally, one couldaim to maximize ?; we conjecture that ? cannot be bounded from below bya constant.95Bibliography[1] Abdulkadiroglu, A., So?nmez, T., 2003. School choice: A mechanismdesign approach. American Economic Review 93 (3), 729?747.[2] Andelman, N., Mansour, Y., 2006. A sufficient condition for truthfulnesswith single parameter agents. In: Proceedings of the ACM Conferenceon Electronic Commerce (EC). Ann Arbor, Michigan, USA, pp. 8?17.[3] Archer, A., Tardos, E., 2001. Truthful mechanisms for one-parameteragents. In: Proceedings of the Annual IEEE Symposium on Foundationsof Computer Science (FOCS). pp. 482?491.[4] Ausubel, L. M., Milgrom, P., 2002. Ascending auctions with packagebidding. Frontiers of Theoretical Economics 1 (1).[5] Ausubel, L. M., Milgrom, P., 2006. The lovely but lonely Vickrey auction.In: [12], Ch. 1, pp. 17?40.[6] Babaioff, M., Lavi, R., Pavlov, E., 2005. Mechanism design for single-value domains. In: Proceedings of the AAAI Conference on ArtificialIntelligence. pp. 241?247.[7] Babaioff, M., Lavi, R., Pavlov, E., 2006. Single-value combinatorialauctions and implementation in undominated strategies. In: Proceedingsof the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).pp. 1054?1063.[8] Beck, M., Ott, M., 2011. Revenue monotoicity in core-selecting packageauctions, stanford university.[9] Bikhchandani, S., Chatterji, S., Lavi, R., Mu?alem, A., Nisan, N., Sen, A.,2006. Weak monotonicity characterizes deterministic dominant-strategyimplementation. Econometrica 74 (4), 1109?1132.[10] Clarke, E. H., 1971. Multipart pricing of public goods. Public Choice11 (1), 17?33.96Bibliography[11] Constantin, F., Parkes, D. C., 2005. Preference-based characterizationsof truthfulness and the limited expressiveness of order-based domains.Proceeding of the Workshop on Preference HandlingPosition Paper.[12] Cramton, P., Shoham, Y., Steinberg, R. (Eds.), 2006. CombinatorialAuctions. MIT Press.[13] Day, R., Milgrom, P., 2008. Core-selecting package auctions. Interna-tional Journal of Game Theory 36 (3?4), 393?407.[14] Dobzinski, S., Nisan, N., Schapira, M., 2006. Truthful randomizedmechanisms for combinatorial auctions. In: STOC. pp. 644?652.[15] Echenique, F., Lee, S., Shum, M., Yenmez, M. B., 2013. The revealedpreference theory of stable and extremal stable matchings. Econometrica81 (1), 153?171.[16] Feige, U., 2006. On maximizing welfare when utility functions aresubadditive. In: STOC. pp. 41?50.[17] Feige, U., Vondrak, J., 2006. Approximation algorithms for allocationproblems: Improving the factor of 1 ? 1/. In: FOCS. pp. 667?676.[18] Feigenbaum, J., Krishnamurthy, A., Sami, R., Shenkar, S., 2003. Hard-ness results for multicast cost sharing. Theoretical Computer Science304 (1?3), 215?236.[19] Gale, D., Shapley, L., 1962. College admission and the stability ofmarriage. The American Mathematical Monthly 69 (1), 9?15.[20] Green, J., Laffont, J.-J., 1977. Characterization of satisfactory mecha-nisms for the revelation of preferences for public goods. Econometrica45 (2), 427?438.[21] Groves, T., 1973. Incentives in teams. Econometrica 41 (4), 617?631.[22] Gusfield, D., Irving, R. W., 1989. The stable marriage problem: structureand algorithms. MIT Press, Cambridge, MA, USA.[23] Haeringer, G., Iehle, V., 2012. Two-sided matching with one-sidedinformation. working paper.[24] Irving, R. W., 1994. Stable marriage and indifference. Discrete AppliedMathematics 48 (3), 261?272.97Bibliography[25] Irving, R. W., 2008. Stable matching problems with exchange restrictions.Journal of Combinatorial Optimization 16, 344?360.[26] Irving, R. W., Leather, P., 1986. The complexity of counting stablemarriages. SIAM Journal of Computation 15, 655?667.[27] Irving, R. W., Manlove, D., Scott, S., 2008. The stable marriage problemwith master preference lists. Discrete Applied Mathematics 156 (15),2959?2977.[28] Irving, R. W., Manlove, D. F., 2002. The stable roommates problemwith ties. Journal of Algorithms 43 (1), 85?105.[29] Irving, R. W., Manlove, D. F., Scott, S., 2000. The hospitals/residentsproblem with ties. In: SWAT. pp. 259?271.[30] Irving, R. W., Manlove, D. F., Scott, S., 2003. Strong stability in thehospitals/residents problem. In: Alt, H., Habib, M. (Eds.), STACS. Vol.2607 of Lecture Notes in Computer Science. Springer-Verlag GmbH, pp.439?450.[31] Irving, R. W., Manlove, D. F., Scott, S., 2008. The stable marriageproblem with master preference lists. Discrete Applied Mathematics156 (15), 2959?2977.[32] Karp, R. M., 1972. Reducibility among combinatorial problems. In:Complexity of Computer Computations. pp. 85?103.[33] Knuth, D., 1976. Mariages Stables. Montre?al: Les Presses de l?Universite?de Montre?al.[34] Knuth, D., 1997. Stable marriage and its relation to other combinatorialproblems: an introduction to the mathematical analysis of algorithms.CRM proceedings & lecture notes. American Mathematical Society.[35] Lamy, L., 2010. Core-selecting package auctions: A comment on revenuemonotonicity. International Journal of Game Theory 39 (3), 503?510.[36] Lavi, R., Mu?alem, A., Nisan, N., 2003. Towards a characterization oftruthful combinatorial auctions. In: Proceedings of the Annual IEEESymposium on Foundations of Computer Science (FOCS). pp. 574?583.[37] Lavi, R., Swamy, C., 2007. Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity. EC ?07, 252?261.98Bibliography[38] Lee, R., Schwarz, M., 2009. Interviewing in two-sided matching markets.NBER Working Paper No. 14922.[39] Lehmann, D., O?Callaghan, L. I., Shoham, Y., 2002. Truth revelationin approximately efficient combinatorial auctions. Journal of the ACM49 (5), 1?26.[40] Manlove, D., 1999. Stable marriage with ties and unacceptable part-ners. Tech. Rep. TR-1999-29, University of Glasgow, Department ofComputing Science.[41] Manlove, D. F., 2002. The structure of stable marriage with indifference.Discrete Applied Mathematics 122 (13), 167 ? 181.[42] Manlove, D. F., 2013. Algorithmics of matching under preferences. WorldScientific.[43] Manlove, D. F., Irving, R. W., Iwama, K., Miyazaki, S., Morita, Y.,2002. Hard variants of stable marriage. Theoretical Computer Science276 (1-2), 261 ? 279.[44] Mu?alem, A., Nisan, N., 2002. Truthful approximation mechanisms forrestricted combinatorial auctions: Extended abstract. In: Proceedingsof the AAAI Conference on Artificial Intelligence. pp. 379?384.[45] Nisan, N., 2007. Introduction to mechanism design. In: Nisan, N.,Roughgarden, T., Tardos, E., Vazirani, V. V. (Eds.), Algorithmic GameTheory. Cambridge University Press, Cambridge, UK, Ch. 9.[46] Nisan, N., Ronen, A., 2000. Computationally feasible VCG mechanisms.In: Proceedings of the ACM Conference on Electronic Commerce (EC).pp. 242?252.[47] Pathak, P., 2006. Lotteries in student assignment. Unpublished mimeo,Harvard University.[48] Puterman, M., 1994. Markov Decision Processes: Discrete StochasticDynamic Programming. John Wiley and Sons, New York.[49] Puterman, M., Patrick, J., 2010. Encyclopedia of Machine Learning. Ch.Dynamic programming.[50] Rastegari, B., Condon, A., Immorlica, N., Leyton-Brown, K., 2013.Two-sided matching with partial information. In: Proceedings of theACM Conference on Electronic Commerce (EC). ACM, pp. 733?750.99Bibliography[51] Rastegari, B., Condon, A., Leyton-Brown, K., 2007. Revenue monotonic-ity in combinatorial auctions. In: Proceedings of the AAAI Conferenceon Artificial Intelligence. pp. 122?127.[52] Rastegari, B., Condon, A., Leyton-Brown, K., 2007. Revenue mono-tonicity in combinatorial auctions. SIGecom Exchanges, Special issueon combinatorial auctions 7 (1), 1?3.[53] Rastegari, B., Condon, A., Leyton-Brown, K., 2009. Stepwise random-ized combinatorial auctions achieve revenue monotonicity. In: Proceed-ings of the Annual ACM-SIAM Symposium on Discrete Algorithms(SODA). pp. 738?747.[54] Rastegari, B., Condon, A., Leyton-Brown, K., February 2011. Revenuemonotonicity in deterministic, dominant-strategy combinatorial auctions.Artificial Intelligence 175 (2), 441?456.[55] Roberts, K., 1979. The characterization of implementable choice rules.In: Laffont, J.-J. (Ed.), Aggregation and Revelation of Preferences.North Holland Publishing Company, pp. 321?348.[56] Rochet, J.-C., 1987. A necessary and sufficient condition for rationaliz-ability in a quasi-linear context. Journal of Mathematical Economics16 (2), 191?200.[57] Roth, A., 1984. The evolution of the labor market for medical internsand residents: a case study in game theory. Journal of Political Economy92, 991?1016.[58] Roth, A., 1996. The national residency matching program as a labormarket. Journal of the American Medical Association 275 (13), 1054?1056.[59] Roth, A., Peranson, E., 1999. The redesign of the matching marketfor american physicians: Some engineering aspects of economic design.American Economic Review 89 (4), 748?780.[60] Roth, A., Sotomayor, M., 1992. Two-Sided Matching: A Study inGame-Theoretic Modeling and Analysis. Cambridge University Press.[61] Rothkopf, M. H., 2007. Thirteen reasons why the Vickrey-Clarke-Grovesprocess is not practical. Operations Research 55 (2), 191?197.100[62] Saks, M., Yu, L., 2005. Weak monotonicity suffices for truthfulness onconvex domains. In: Proceedings of the ACM Conference on ElectronicCommerce (EC). pp. 286?293.[63] Scott, S., January 2005. A study of stable marriage problems with ties.Ph.D. thesis, Department of Computing Science, University of Glasgow.[64] Spieker, B., 1995. The set of super-stable marriages forms a distributivelattice. Discrete Applied Mathematics 58 (1), 79?84.[65] Todo, T., Iwasaki, A., Yokoo, M., 2009. Characterization of strategy-proof, revenue monotone combinatorial auction mechanisms and con-nection with false-name-proofness. In: Proceedings of the InternationalWorkshop on Internet and Network Economics (WINE). pp. 561?568.[66] Vickrey, W., 1961. Counterspeculations, auctions, and competitive sealedtenders. Journal of Finance 16 (1), 8?37.[67] Yokoo, M., 2006. Pseudonymous bidding in combinatorial auctions. In:[12], Ch. 7, pp. 161?187.[68] Yokoo, M., Matsutani, T., Iwasaki, A., 2006. False-name-proof com-binatorial auction protocol: Groves mechanism with submodular ap-proximation. In: Proceedings of the International Joint Conference onAutonomous Agents and Multiagent Systems (AAMAS). pp. 1135?1142.[69] Yokoo, M., Sakurai, Y., Matsubara, S., 2001. Robust combinatorialauction protocol against false-name bids. Artificial Intelligence 130 (2),167?181.[70] Yokoo, M., Sakurai, Y., Matsubara, S., 2004. The effect of false-namebids in combinatorial auctions: New fraud in internet auctions. Gamesand Economic Behavior 46 (1), 174?188.101Appendix ATwo-sided Matching: ProofsA.1 Hardness resultIn this section we prove that the claim of Theorem 47 holds even if weexchange optimality certificate with diligent optimality certificate.Definition 85 (Diligent Optimality Certificate (DOC) decision problem).Given (E,A, pE,A), a preference profile ? that refines pE,A and a bound K,decide whether there exists a diligent optimality certificate (I, ?, pE,A) of sizeat most K where ? is employer-optimal w.r.t. ?.Theorem 86. The diligent optimality certificate decision problem is NP-complete, even if the partial preference ordering is an equivalence classordering.Proof. It follows almost directly from Theorem 18 that the DOC decisionproblem is in NP. (We only need to also check that all pairs matched in ?have interviewed under I.) It remains to show that this problem is NP-hard.The proof is by reduction from the feedback arc set (FAS) problem, or itsalternative formulation maximum acyclic subgraph problem, which are bothNP-complete problems [32]. Let G = (V,D) be a directed graph (with noself-loops or multiple arcs). The feedback arc set problem is to decide whetherthere exists a set of arcs A of size ?K such that A contains at least one arcfrom every directed cycle in G; i.e. removing arcs in A breaks all directedcycles of G.Let G = (V,D) be any given directed graph where V = {v1, . . . , vn}. Wefirst construct an instance of the optimality certificate problem from (G,K).? Let E = {e1, . . . , en} and A = {a1, . . . , an} be the set of employers andapplicants respectively, where n = ?V ?, the number of vertices in G.That is, there is a one-to-one correspondence between the vertices andthe sets of employers and applicants.? Let the equivalence classes be such that102A.1. Hardness result? each employer ei has exactly one equivalence class containing aiand any applicant aj where (vi, vj) ?D.? each applicant has exactly two equivalence classes. The topequivalence class of aj contains only ej . The bottom equivalenceclass of aj contains any employer ei where (vi, vj) ?D.? Let ? be any strict ordering refining the equivalence classes underwhich each employer ei ranks ai at top. Thus ?, ?(ei) = ai, is theemployer-optimal matching of ?.We claim that G has a FAS of size K if and only if there exists a diligentoptimality certificate (I, ?, pE,A) of size K + ??? where ? is the employer-optimal matching of ?. The proof has two parts:1. Let (I, ?, pE,A) be a diligent optimality certificate of size K ?. Let S bea set of arcs such that (vi, vj) ? D iff ei ?aj ? I. We claim that S is ofsize K ? ? ??? and removing all the arcs in S breaks all the cycles in G.2. Let S be a solution of size K to the feedback arc set problem. Let I bean information state consistent with ? under which each ei, 1 ? i ? n,has interviewed ai and all applicants aj such that (vi, vj) ? S. We claimthat (I, ?, pE,A) is a diligent optimality certificate of size K + ??? for ?.Proof of (1): by contradiction. First note that, since every pair matchedin ? must have interviewed together under I, there are exactly K ? ? ???interviews in I that are of type (ei, aj). So ?S? = K ? ? ???. Assume thatremoving S does not break all the cycles in G. Let C be an unbroken cycle.For each edge (vi, vj) in C it must be the case that ei ?aj /? I. Let ?? be amatching in which ??(ei) = ?(ei) = ai if ei is not in C, and ??(ei) = ?(ej) if(ei, ej) is in C. Let ?? be a strict ordering under which each employer ei notin C likes ai the best (as in ?), and each ei in C likes aj the best, where(ei, ej) is in C. Note ?? is consistent with I. Furthermore, employers notin C have the same applicant on the top of their list as in ? (which shouldbe consistent with the outcome of the interviews in I), and for employersin C their true preferences between their partners in ? and ?? haven?t beenrevealed yet (since no interview between such an employer and his matchunder ?? has taken place). Note that ?? is the employer-optimal matching for?? and so ? is not the employer-optimal matching for ??. Thus (I, ?, pE,A)is not a diligent optimality certificate for ?, a contradiction.Proof of (2): By contradiction. First note that it is easy to see, fromthe construction of I, that ?I ? = K + ???. Assume that (I, ?, pE,A) is not a103A.2. Identical strict total orderings for the applicants with 1-perturbationdiligent optimality certificate for ?. Thus, there exists a preference ordering?? consistent with I for which ? is not the employer-optimal matching. Weknow that ? is a stable matching under any preference ordering consistentwith I (it is the applicant-optimal matching indeed). Thus, it should bethe case that there is some other stable matching ?? that the employerscollectively prefer to ? (some are indifferent and some prefer ??). Therefore,there has to be a set of employers ec1 , . . . , ecl such that ??(eci) = ?(eci+1) fori < l and ??(ecl) = ?(ec1). If not, then there exists an unmatched employerand unmatched applicant who both prefer to be matched together than stayunmatched, thus ?? is not stable. Note that eci must prefer his match in ??to his match in ?, aci , under ??. Thus eci has ?(eci+1) in his one and onlyequivalence class and therefore (vci , vci+1) ? D. Furthermore (vcl , vc1) ? D.Thus, ec1 , . . . , ecl form a cycle in G,a contradiction. ?A.2 Identical strict total orderings for theapplicants with 1-perturbationTheorem 87. In the setting described by Theorem 55, the very weaklydominant policy for I identified by Algorithm 3 requires each employer tointerview at most two applicants, and the employer at the top of the applicants?strict total ordering to interview at most one applicant.Proof. The proof proceeds by induction on the number of interviews. It isobvious that if the algorithm instructs no interviews then the claim holds.Assume that the claim holds for the number of interviews less than k. Weshow that it holds for the number of interviews equal k.As shown in Step 3 of the proof of Theorem 55, the only interviewsAlgorithm 3 schedules are those when an employer ei has a chance of kickingout ei?1. Let ei be the first employer whose proposal results in Algorithm3 scheduling interviews. Again, by Step 3 of the proof of Theorem 55,Algorithm 3 instructs both ei and ei?1 to interview ei?1?s partner at the time,a?.First consider the case where ei does not kick out ei?1. In this case a?must prefer ei?1 to ei. By Step 2, no kick-out chain can involve e1 . . . ei?1when ei?1 can not kick out ei. Thus, e1 . . . ei?1 will not perform any interviewfrom now on and are indeed matched to their employer-optimal partnersalready. Furthermore, e1 . . . ei?2 have performed no interview and ei?1andei have performed exactly one interview each. Note that the rest of theemployers, ei+1, . . . , em, have not even proposed yet. Thus from now on104A.2. Identical strict total orderings for the applicants with 1-perturbationAlgorithm 3 is essentially running on a setting I ? with ei, . . . , em and thoseapplicants of I who are not matched to e1, . . . ei?1. It is easy to see thatI ? is a setting with strict total orders for the employers and identical stricttotal orderings with 1-perturbation for the applicants. It is also obviousthat Algorithm 3 schedules k ? 2 interviews on I ?, thus by induction everyemployer interviews at most two applicants and ei interviews at most oneapplicant. Recall that ei has performed one interview earlier when makinghis first proposal, so in total ei performs at most two applicants.Now consider the case where ei kicks out ei?1 out and a kick-out chain isinitiated. Either ei is the last employer in this chain or not.Consider the case in which ei is not the last employer in the chain. Wefirst show that he will not be kicked out again later. To see this, note thatunder this kick-out chain ei kicks out ei?1 and is matched to his at-the-timepartner, say a?. Thus a? prefers ei to ei?1 and hence by the setting andtransitivity must prefer ei to ei+1 as well. Therefore ei+1 can not kick outei. Hence e1 . . . ei will not perform any interviews from now on and areindeed matched to their employer-optimal partners already. Furthermore,following the format of a kick-out chain, each employer in this kick-out chainhas performed at most two interviews, the least indexed employer in thechain has performed at most one interview , and all other employers haveperformed no interviews. Thus each of the employers e1 . . . ei have performedat most two interviews and will perform no more, and e1 has performed atmost one interview. From now on Algorithm 3 is essentially running on asetting I ? with ei+1, . . . , em and those applicants of I who are not matchedto e1, . . . ei. It is easy to see that I ? is a setting with strict total orders forthe employers and identical strict total orderings with 1-perturbation forthe applicants. It is also obvious that Algorithm 3 instructs less than kinterviews on I ?, thus by induction every employer ei+1, . . . , em performs atmost two interviews.Now, consider the case in which ei is the last employer in the chain.Thus, he is kicked out and gets matched to an unmatched applicant. Notethat, by Step 2 in the proof of Theorem 55, ei must have been kicked outby ei?z for some z > 1. Thus ei?1 is not kicked out in the second part ofthe chain, and only in the first part. Thus ei?1 is matched to the applicantei?2 was matched to, say a?, at the time ei?1 kicked out ei?2. Thus a?prefers ei?1 to ei?2 and hence by the setting and transitivity must prefer ei?1to ei as well. Therefore ei can never again kick out ei?1, hence neither ofthe employers e1, . . . , ei?1 are kicked out in the rest of the algorithm andtheir current partners are their employer-optimal partners. Furthermore,following the format of a kick-out chain, each employer in this kick-out chain105A.2. Identical strict total orderings for the applicants with 1-perturbationhas performed at most two interviews, ei and the least indexed employerin the chain has performed at most one interview, and all other employershave performed no interviews. Thus each of the employers e1 . . . ei?1 haveperformed at most two interviews and will perform no more, and e1 and eihas performed at most one interview. From now on Algorithm 3 is essentiallyrunning on a setting I ? with employers ei, . . . , em and those applicants ofI who are not matched to e1, . . . ei?1. It is easy to see that I ? is a settingwith strict total orders for the employers and identical strict total orderingswith 1-perturbation for the applicants. I ? clearly induces less than k kick-outchains and thus, by induction hypothesis, ei, . . . , em are kicked out at mosttwice and ei is kicked out at most once. Recall that ei has performed oneinterview earlier when making his first proposal, so in total ei performs atmost two applicants. ?106Appendix BCombinatorial Auctions:Formal DefinitionsIn this chapter we formally define the concepts introduced in Chapters 4 and5.B.1 BiddersLet valuation function vG,i for bidder i ?N map 2G to the nonnegative reals.For every G ? G let valuation function vG,i be the restriction of vG,i to 2G.Whenever G is understood, we drop it from the subscript.Let V denote the universal set of all possible valuation profiles. Let VN,Gdenote a set of valuation profiles for the set of participating bidders N andthe set of goods for sale G. Let VN,G denote the set of all valuation profilesgiven a set of participating bidders N and a set of goods for sale G; that is,the set of all valuation profiles vG for which vi = ? if and only if i /? N .In a particular auction, bidders? valuation functions may be drawn fromsome restricted set. Let VN,G ? VN,G denote a subspace of the universal setof valuation profiles for the set of participating bidders N and the set ofgoods for sale G. Let VN,G,i denote the set {vi?(v1, . . . , vi, . . . , vn) ? VN,G}.Let VN,G denote the universal set of valuation profile subspaces, that isVN,G = {VN,G ? N ?N,G ? G, VN,G ? VN,G}. Let V denote a set of valuationprofile subspaces with at least one member corresponding any N ? N andG ? G. That is, V ? VN,G and ?VN,G ? V,?N ? N,G ? G. Note that therecould be more than one subspace corresponding to a fixed N and a fixed Gin V.Consider the case of known single-minded bidders. Let N ? N andG ? G be fixed. Let b = (b1, b2, . . . , bn) ? (2G)n. If i is a participatingbidder, let V (b)N,G,i be the set of all possible single-minded valuation functions,taken over all possible choices of vi, and otherwise let V (b)N,G,i = ?. LetV (b)N,G = V(b)N,G,1?. . .?V(b)N,G,n. Then, V(b)N,G is simply the space of valuation profilesin which participating bidders are all single-minded and each participating107B.2. Deterministic CA mechanismsbidder i values bundle bi. Let V(ksm) denote the set of valuation profilesubspaces for known single-minded bidders, V(ksm) = {V (b)N,G ? N ? N,G ?G, b ? (2G)n}.B.2 Deterministic CA mechanismsWe first formally define a combinatorial auction mechanism. Observe thatour definition requires a mechanism to define allocations and payments forall possible sets of bidders, all possible sets of goods, and all correspondingvaluation profiles belonging to a given, possibly restricted set. Also, notethe implicit assumption that the auction setting?i.e., N , G and VN,G?iscommon knowledge among all bidders and the auctioneer.Definition 88 (CA Mechanism). Let the set of valuation profile subspacesV be given. A deterministic direct Combinatorial Auction (CA) mechanismM (CA mechanism) maps each VN,G ? V, N ?N and G ? G, to a pair (a, p)where? a, the allocation scheme, maps each v? ? VN,G to an allocation tuplea = (a1(v?), . . . , an(v?)) of goods, where ?iai(v?) ? G, ai(v?)? aj(v?) = ? ifi ? j, and ai(v?) = ? if v?i = ?.? p, the payment scheme, maps each v? ? VN,G to a payment tuple p =(p1(v?), . . . , pn(v?)), where pi(v?) is the payment from bidder i to theauctioneer such that pi(v?) = 0 if v?i = ?.We say that CA mechanism M is defined for V. A CA mechanism isdefined for known single-minded bidders if its set of valuation profile subspacesis V(ksm). From the definition it follows that the allocation and paymentfunctions depend on the set V (b)N,G ? V(ksm) from which bidders? valuationprofiles are drawn. Informally, b is known, since the allocation and paymentsdepend on b. Observe that our definition requires that the mechanism bedefined for all possible known single-minded valuations, not just for the setof bundles that a given set of bidders might value.A set of valuation subspaces V subsumes another set of valuation sub-spaces V ? if and only if for all V ?N,G ? V?, there exists VN,G ? V such thatV ?N,G ? VN,G. For example, the set of valuation subspaces for single-mindedbidders subsumes the set of valuation subspaces for known single-mindedbidders.We can say that the class of mechanisms defined for V is a subset ofthe class of mechanisms defined for known single-minded bidders when V108B.2. Deterministic CA mechanismssubsumes known single-minded valuations. The preceding claim is in fact truein a general sense, that is even if we replace known single-minded valuationswith any V ?. The following lemma states it formally. On some level thisresult is obvious; however, we were not able to find any formal discussion ofit in the literature and so present it here for completeness.Lemma 89. If V subsumes V ?, then every social choice function that canbe implemented by a mechanism defined for V can also be implemented by amechanism defined for V ?.Proof. Without loss of generality ((by the revelation principle)), we canrestrict ourselves to truthful mechanisms. The allocation function in atruthful mechanism is precisely the social choice function. Let M (V) be atruthful mechanism defined for V. Modify M (V) such that given declaredvaluation profile v? ? V ?N,G, V?N,G ? V?, runs the same allocation and paymentfunctions as M (V) would run on v? ? VN,G, VN,G ? V, where V ?N,G ? VN,G. AsV subsumes V ?, such a VN,G exists. Let M (V?) be this new mechanism thatis defined for V ?. M (V?) is clearly truthful, since is M (V). ?Informally speaking, for each mechanism M defined for V, there is acorresponding mechanism M ? defined for V ?. We will use the above claim inSection 4.3 to state our result for general CA mechanisms.B.2.1 Properties of deterministic CA mechanismsHere, we formally define properties that we may require of a CA mechanism.Definition 90 (Dominant-strategy truthfulness). A CA mechanism M isdominant strategy truthful (or DS truthful) if and only if for all fixed setsof participating bidders, it is a best response for each participating bidderto declare her true valuation regardless of the declarations of the otherparticipating bidders. That is, for all N ? N,G ? G, VN,G ? V, v? ? VN,G,vi ? VN,G,i, and for every bidder i we have thatvi(ai(vi, v??i)) ? pi(vi, v??i) ? vi(ai(v?)) ? pi(v?).Definition 91 (Participation). A truthful CA mechanism M satisfies partic-ipation if and only if for all N ?N,G ? G, VN,G ? V, and v ? VN,G, pi(v) = 0for all bidder i for whom vi(ai) = 0 (i.e., who does not win).109B.2. Deterministic CA mechanismsDefinition 92 (Efficiency). A CA mechanism M is efficient if its chosenallocation in equilibrium, a?, maximizes the social welfare; that is, for allN ?N,G ? G, VN,G ? V, and v ? VN,G,a? ? arg maxa?AN,G?i?Nvi(ai).Definition 93 (Revenue monotonicity). A truthful CA mechanism M isbidder revenue monotonic (or revenue monotonic) if and only if for allN ?N,G ? G, VN,G ? V, v ? VN,G and for all bidders j,?i?Npi(v) ? ?i?N?{j}pi(v?j).Definition 94 (Weak Maximality). A truthful CA mechanism M is weaklymaximal with respect to bidder i if and only if for all N ? N where i ? N ,for all G ? G, and for all VN,G ? V, there exists a set of nonnegative finiteconstants {?N,G,VN,G,i,g ? g ? G} such that the following holds. For allv ? VN,G, M always chooses an allocation a where either:1. vi(ai) > 0; or2. for all allocations a? with vi(a?i) > ?N,G,VN,G,i,a?i , ?a?i? = 1, and a?j = aj ?a?ifor all j ? i, it must be the case that for some j, vj(a?j) < vj(aj).Note that ? is subscripted by N , G and VN,G. This is because a CAmechanism may set different bidder-specific reserve prices for different set-tings, i.e. for different sets of participating bidders N , available goods G, anddifferent valuation profiles subspaces VN,G. Also note that in the informaldefinition of weak maximality that we provided in Section 4.1.2, VN,G in thesubscript of ? was replaced by b, bidders? bundles of interest. This change isinnocuous as, in the case of known single-minded bidders, all the knowledgethat a mechanism extracts from VN,G can be learned from b.In what follows let (VN,G)?i denote the set {v?i?v ? VN,G}.Definition 95 (Consumer sovereignty). A CA mechanism M satisfies con-sumer sove/-reignty if and only if for all N ?N, G ? G, and VN,G ? V, ?i ? Nand ?v??i ? (VN,G)?i, for all s ? G that i may value above zero according toVN,G, there exists some finite amount ksi (v??i) ? R, ksi (v??i) > 0, such that ican win s by reporting that she values s at amount at least ksi (v??i).110B.2. Deterministic CA mechanismsB.2.2 MaximalityWe use a weakened version of maximality in our work as it is sufficient forour purpose and, being a weaker constraint, makes our impossibility resultstronger. Maximality, on the other hand, is useful when one is trying toprove a possibility result (see, e.g., Chapter 5).Definition 96 (Maximality). A truthful CA mechanism M is maximalwith respect to bidder i if and only if for all N ? N where i ? N , for allG ? G, and for all VN,G ? V, there exists a set of nonnegative finite constants{?N,G,VN,G,i,s ? s ? G} such that the following holds. For all v ? VN,G, Malways chooses an allocation a where either:1. vi(ai) > 0; or2. for all allocations a? with vi(a?i) > ?N,G,VN,G,i,a?i , and a?j = aj ? a?i for allj ? i, it must be the case that for some j, vj(a?j) < vj(aj).Observe that the definition of weak maximality is simply derived fromthe definition of maximality by restricting a?i to be of size 1. Intuitively,maximality ensures that the mechanism does not withhold any subset ofgoods, or give the goods away to the bidders who do not value them, when theyare sufficiently valued by a losing bidder. The quantities {?N,G,VN,G,i,s ? s ?G} can be thought of as bidder- and bundle-specific reserve prices.8Many interesting mechanisms are maximal. First, it is straightforward toshow that efficiency implies maximality. Second, we show here that a broadclass of affine maximizing mechanisms are maximal.Affine maximizers generalize the idea behind the VCG mechanism?sallocation rule (which aims to maximize the social welfare) by allowingthe mechanism to restrict the set of possible allocations, to assign differentnonnegative weights ?i to different players, and to assign different additiveweights ?a to different allocations.Definition 97 (Affine maximizer). A CA mechanism is an affine maximizerif for some A?N,G ?AN,G, nonnegative {?i}i?N and {?a}a?A?N,G, for all N ?N,G ? G, VN,G ? V, v ? VN,G, its chosen allocation in equilibrium, a? satisfies8Note that in the definition of maximality there exist distinct ? variables for eachdifferent subset of goods s ? G; in contrast, in the definition of weak maximality, thereexist distinct ??s only for each single good g ? G. Thus, we can understand the ??sas representing bundle-specific reserve prices in maximal mechanisms, and item-specificreserve prices in weakly maximal mechanisms.111B.2. Deterministic CA mechanismsthe following:a? ? arg maxa?A?N,G(?i?ivi(ai) + ?a) .We call {?i}i?N and {?a}a?A?N,G the allocation parameters of affine maxi-mizer M .Theorem 98. Let M be an affine maximizing truthful CA mechanism withfinite allocation parameters {?i}i?N and {?a}a?AN,G. Suppose that for somei ?N, ?i > 0. Then M is maximal with respect to bidder i.Proof. Let ?N,G,VN,G,i,s =maxa{?a}?i , ?N ? N where i ? N , ?G ? G and?s ? G. We prove that M is maximal with respect to bidder i. Assume forcontradiction that M is not maximal with respect to i. Then, for some v,M ?s allocation scheme maps v to an allocation a that satisfies the followingproperties: (i) vi(ai) = 0, and (ii) ?s ? G, ?a? ? AN,G: a?i = s and ?j ? i,a?j = aj ? s such that vi(a?i) > ?N,G,VN,G,i,s and vj(a?j) ? vj(aj).From construction and (i) and (ii) we have that?k?N?kvk(a?k) + ?a? > ?k?N?{i}?kvk(a?k) +maxa{?a} + ?a? ? ?k?N?kvk(ak) + ?a.Since M is affine maximizing it would not choose allocation a, giving us ourcontradiction. ?Finally, all mechanisms that are strongly Pareto efficient with respect tobidders? valuations are also maximal.Definition 99 (Strong Pareto efficiency with respect to bidders? valuations).A mechanism is strongly Pareto efficient with respect to bidders? valuationsif it chooses allocations that would be strongly Pareto efficient if monetarytransfers were disallowed.Note that these allocations are a superset of those that are strongly Paretoefficient when transfers are permitted. Thus, a broader class of mechanismsachieves strong Pareto efficiency with respect to bidders? valuations thanachieve strong Pareto efficiency.In case of single-minded bidders, strong Pareto efficiency with respect tobidder?s valuations is equivalent to maximality with respect to all bidderswhen all bidder- and bundle-specific reserve prices, ??s, are set to zero.In general, however, maximality is a weaker condition than strong Paretoefficiency. To see this, consider an example with a single bidder, 1, and two112B.2. Deterministic CA mechanismsgoods {g1, g2}. Assume that bidder 1 values each good individually, and also(e.g., by free disposal) values a bundle of both goods. A mechanism thatawards either of the goods, but not both, to bidder 1 is maximal but does notsatisfy strong Pareto efficiency. Alternatively, if bidder 1 were single-mindedand interested in {g1, g2}, then any mechanism would be weakly maximalwith respect to bidder 1, whereas a mechanism that is maximal with respectto bidder 1 has to award both goods to her as long as she values them abovethe bidder- and bundle-specific reserve price.B.2.3 Impossibility results for general deterministic CAmechanismsTheorem 100. Let ?G? ? 2 and ?N? ? 3. Let M be a CA mechanism whoseset of valuation subspaces V subsumes known single-minded bidders, thatoffers dominant strategies to the bidders and satisfies participation, consumersovereignty, and weak maximality with respect to at least two bidders. ThenM is not revenue monotonic.Proof. The proof directly follows from Lemma 89 and Theorem 60. FollowingLemma 89, if there is a mechanism M defined for V?i.e., M ?s set of valuationsubspaces is V?that offers dominant strategies to the bidders and satisfiesparticipation, consumer sovereignty, weak maximality with respect to at leasttwo bidders and revenue monotonicity, then there exists a mechanism M (ksm)defined for known single-minded bidders that has all the above properties.By Theorem 60, such a mechanism M (ksm) does not exist, and thus nor doessuch a mechanism M . ?The following corollaries are the extension of those in Section 4.4 to thegeneral case. We omit the proofs as they are very similar to the proofs givenin Section 4.4 except that they have to also appeal to Lemma 89, making anargument similar to the one in the proof of Theorem 100.Corollary 101. Let ?G? ? 2 and ?N? ? 3. Let M be a CA mechanism whoseset of of valuation subspaces subsumes known single-minded bidders, thatoffers dominant strategies to the bidders, and that satisfies participation,consumer sovereignty, and weak maximality with respect to at least twobidders. Then M is not false-name-proof.Let pGi (v) denote bidder i?s payment to a DS truthful CA mechanismwhen all bidders? valuations are v, and where the set of goods at auction isG. Then we can give the following definition.113B.2. Deterministic CA mechanismsDefinition 102 (Good revenue monotonicity). A truthful CA mechanismM is good revenue monotonic if and only if for all N ?N,G ? G, VN,G ? V,v ? VN,G and for all goods g ? G,?i?NpGi (v) ? ?i?NpG?{g}i (v).Corollary 103. Let ?G? ? 3 and ?N? ? 3. Let M be a CA mechanism whoseset of of valuation subspaces subsumes known single-minded bidders, thatoffers dominant strategies to the bidders and satisfies participation, consumersovereignty, and weak maximality with respect to at least two bidders. ThenM is not good revenue monotonic.Corollary 104. Let ?G? ? 2 and ?N? ? 3. Let M be a CA mechanism whoseset of of valuation subspaces subsumes known single-minded bidders, thatoffers dominant strategies to the bidders, and that satisfies participation,consumer sovereignty, and efficiency. Then, there exists a valuation profilefor which the auction?s imputation does not belong to the core.Corollary 105. Let ?G? ? 2 and ?N? ? 3. Let M be a CA mechanism whoseset of valuation subspaces V subsumes known single-minded bidders, thatoffers dominant strategies to the bidders and satisfies participation, consumersovereignty, and weak maximality with respect to at least two bidders. Definethe auction game as in Definition 66 or Definition 67. Then, there exists avaluation profile for which the auction?s imputation does not belong to thecore.Corollary 106. Let ?G? ? 2 and ?N? ? 3. Let M be a CA mechanism whoseset of valuation subspaces V subsumes known single-minded bidders, thatoffers dominant strategies to the bidders and satisfies participation, consumersovereignty, and weak maximality with respect to at least two bidders. Thenthere exists a CA mechanism M ? that allows bidders to express the samepreferences as in M and that1. has the same allocation and payment functions as M , except that itmay have a different cvi(?, . . . ,?) for some (single) i ?N;2. satisfies participation, consumer sovereignty, and weak maximality withrespect to at least two bidders; and3. chooses an outcome that is not guaranteed to belong to the core.114B.3. Randomized CA mechanismsB.3 Randomized CA mechanismsDefinition 107 (Randomized CA Mechanism (RCAM)). Let V be given.A randomized direct Combinatorial Auction mechanism M (RCAM) mapseach VN,G ? V, N ?N and G ? G, to a distribution over pairs (a, p) where aand p are defined exactly as in Definition 88.B.3.1 Properties of randomized CA mechanismsDefinition 108 (Revenue Monotonicity for RCAM?s). A truthful randomizedCA mechanism is revenue monotonic if dropping a bidder never increasesthe mechanism?s expected revenue.Definition 109 (Participation for RCAM?s). A truthful randomized CAmechanism satisfies participation iff for all N ? N,G ? G, VN,G ? V, andv ? VN,G , pi(v) = 0 for any bidder i for whom wi(v) = 0.B.3.2 Weak maximalityDefinition 110 (Maximality for RCAM?s). A truthful randomized CA mech-anism M is maximal with respect to bidder i iff ?N ? N, ?G ? G, andVN,G ? V, there exists a set of nonnegative finite constants {?N,G,i,s ? s ? G}such that the following holds. For all v ? VN,G, for any allocation a that hasa positive support under M?that is, a is chosen by M with probability abovezero?either:1. vi(ai) > 0; or2. for any allocation a? with vi(a?i) > ?N,G,i,a?i and a?j = aj ? a?i for all j ? i,it must be the case that for some j, vj(a?j) < vj(aj).An allocation a is maximal if it satisfies either (1) or (2) for all bidders i.A randomized CA mechanism M satisfies maximality if any allocation withpositive support under M is maximal.115
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Stability in markets with power asymmetry
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Stability in markets with power asymmetry Rastegari, Baharak 2013
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Stability in markets with power asymmetry |
Creator |
Rastegari, Baharak |
Publisher | University of British Columbia |
Date Issued | 2013 |
Description | Two classes of widely studied markets are auctions, such as eBay, and two-sided matching markets, such as matching medical residents to hospitals. In both of these markets, it often happens that one side is in power and can influence the outcome of the market---e.g., the seller in an auction. In the fist part of this thesis we study two-sided matching markets in which participants are initially endowed with partial preference orderings. Our goal is to identify a matching that is stable and optimal for the side of the market that is in power, w.r.t. the underlying true preferences of the agents. We first investigate the extent to which we can learn about this matching given the partial information. We then provide a novel model in which the true preferences are learned through interviews. Our goal is to identify a centralized interviewing policy that returns our matching of interest while minimizing the number of interviews. We introduce three minimization criteria, of which the most desirable one is not always achievable. We provide an exponential-time algorithm for computing a policy that satisfies the other two criteria, and exhibit evidence that a more efficient computation may not be possible in general. We then show how to design a computationally efficient interview-minimizing policy for a setting in which agents on one side of the market are initially endowed with identical partial preferences, and agents must interview before getting matched. In the second part, we study combinatorial auctions (CAs), where multiple goods are for sale and buyers are allowed to place bids on bundles, i.e. sets of goods. In single-good auctions the auctioneer is at no risk of losing revenue if more bidders compete in the auction. In CAs however, an auctioneer may fi nd it pro table to disqualify bidders in order to be matched to a smaller set of bidders. We investigate the extent to which this counterintuitive phenomenon can occur under CA mechanisms that o er bidders dominant strategies. We show that a broad class of deterministic CAs exhibit non-monotonicity in revenue. However, revenue monotonic CAs exist in the broader domain of randomized mechanisms. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2014-01-02 |
Provider | Vancouver : University of British Columbia Library |
Rights | CC0 1.0 Universal |
DOI | 10.14288/1.0072135 |
URI | http://hdl.handle.net/2429/45695 |
Degree |
Doctor of Philosophy - PhD |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2014-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/publicdomain/zero/1.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2014_spring_rastegari_baharak.pdf [ 1.13MB ]
- Metadata
- JSON: 24-1.0072135.json
- JSON-LD: 24-1.0072135-ld.json
- RDF/XML (Pretty): 24-1.0072135-rdf.xml
- RDF/JSON: 24-1.0072135-rdf.json
- Turtle: 24-1.0072135-turtle.txt
- N-Triples: 24-1.0072135-rdf-ntriples.txt
- Original Record: 24-1.0072135-source.json
- Full Text
- 24-1.0072135-fulltext.txt
- Citation
- 24-1.0072135.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0072135/manifest