Showing posts with label matching. Show all posts
Showing posts with label matching. Show all posts

Thursday, January 18, 2024

It's a dominant strategy for deferred acceptance proposers to state true preferences in the marriage problem: simple proof

This post is not entirely self-contained, it is in some sense a continuation of and addition to my talk last year at the Simons Institute, which you can see at this link: 

Simple Proofs of Important Results in Market Design-- (video of my talk at Berkeley's Simons Institute)

In that talk (based on work I'm doing with Mike Ostrovsky) I defined the marriage model of Gale and Shapley, gave necessary definitions,  and following the style of their original article, I showed simple, verbal proofs of a number of results, including the constant employment ("lone wolf") theorem:

Constant employment theorem: In a "marriage market"(M,W, P) with strict preferences, the set of people who are single is the same for all stable matchings.

Now based on that theorem, here's a simple proof of the dominant strategy theorem, inspired by a  very short proof (with attributions to Alex Teytelboym and Ravi Jagadeesan) in Nick Arnosti's recent blog post A Short Proof of the Truthfulness of DA by Nick Arnosti 2023/10/01 

Here's the theorem to be proved:

Dominant Strategy Theorem (Dubins and Freedman, Roth): In the M-optimal stable mechanism for the marriage problem (e.g. when the man-proposing deferred acceptance algorithm is used, which produces the most favorable stable matching for every man) it is a dominant strategy for each man i to state a preference list corresponding to his true preferences ≻.


Notation: for any preference ≻′ of player i, an outcome is ≻′-stable if it is stable when i reports ≻′ and everyone else's preferences remain constant.

Proof (following Arnosti)

Suppose that the theorem is false. That is, suppose there exist preferences for all other agents such that when i reports ≻, the resulting ≻-stable matching μ gives μ(i)=w, and when i reports ≻′ ≠ ≻, the resulting ≻′-stable matching μ′ gives μ′(i)=w′≻w. (Note that the final comparison is ≻, i.e. take ≻ to be i's true preference list.)

Consider the market in which i lists w′ as the only acceptable woman (and everyone else's preferences remain fixed). We'll see that this will lead to a contradiction with the constant employment theorem, by implying that there must exist a {w'}-stable matching in which i matches to w′, and another {w'}-stable matching in which i is unmatched. 

1. The matching μ′ assigns i to w′. Because it is ≻′-stable, it must also be {w′}-stable: the only difference between ≻′ and {w'} is that we have removed women from i’s list, which clearly does not create any new blocking pairs.

Note: this step uses only the definition of stability.

2. Let ≻′′ be the deviation in which i truncates ≻ below w′ (i leaves everyone below w′ off of his list), and let μ′′ be the resulting matching.

a. The matching μ′′ leaves i unassigned.  This follows from the fact that, if it matched i, then μ″ would be ≻-stable, since ≻ differs from ≻'' only in that it restores the truncated elements of i's preference, which would be below i's match and hence not introduce any new blocking pairs (since it wouldn't change i's match). But  μ″ can't be ≻-stable,  because w is i’s best ≻-stable partner by assumption, and is worse than all women listed in ≻′′.*

Note: this step uses the definition of stability and fact that μ is optimal for i.

b. Because μ′′  (which leaves i unassigned) is ≻′′-stable, it is also {w′}-stable: the only difference between ≻′′ and {w′} is that we have removed women from i’s list, which does not create any new blocking pairs).

Note: this step uses only the definition of stability.

To recap: μ′ and μ′′ must both be {w′}-stable, but i is matched to w′ by μ′ and unmatched by μ′′ (a contradiction).

This completes the proof.

*Note that the reason μ′′ isn't ≻-stable is that it leaves i unassigned, and so creates new blocking pairs involving i with respect to his true full preferences.


Monday, January 15, 2024

Matching and market design in the latest GEB (stack overflow...)

 The current (January 2024) issue of Games and Economic Behavior presents an increasingly common dilemma (faced by scholars in burgeoning fields, and maybe by aging scholars...). Papers I should read are being written much faster than I can read them.

Here are 9 papers in that issue that are pretty clearly about matching and market design (which leaves out some papers on auctions and one on unraveling of the timing of markets) :

  1. Obvious manipulations of tops-only voting rules

    Pages 12-24
    View PDF
  2. Rejection-proof mechanisms for multi-agent kidney exchange

    Pages 25-50
    View PDF

Thursday, January 4, 2024

Topics in Market Design: Econ 287/365: Winter quarter, Itai Ashlagi

Itai Ashlagi will be teaching Econ 287 this quarter, on topics in market design.  It's highly recommended.

He writes that the syllabus below is very tentative, and will depend in part on how many of the enrolled students took Econ 285 (Ostrovsky and Roth) in the Fall (back in 2023:-)

Topics in Market Design 2024, Itai Ashlagi

Market design is a field that links the rules of the of the marketplace to understand frictions, externalities and more generally economic outcomes. The course will provide theoretical foundations on assignment and matching mechanisms as well as mechanism design. There will be emphasis on theories at the intersection of economics, CS and operations as well as applications that arise in labor markets, organ allocation, platforms.

The class will further expose students to timely market design challenges and will we will host a few guest lectures. The class offers an opportunity to begin a research project. Students will reading critique papers, present papers and write a final paper.

Lectures: Monday 10:30am-1:20pm Shriram 052

Course requirements: (i) reading and writing critiques about papers, (ii), presenting papers in class, and (iii) a term paper.

Instructor: Itai Ashlagi. iashlagi@stanford.edu

Some potential papers for presenting:

Equity and Efficiency in Dynamic Matching: Extreme Waitlist Policies, Nikzad and Strack.

Eliminating Waste in Cadaveric Organ Allocation, Shi and Yin

Pick-an-object mechanisms, Bo and Hakimov

Monopoly without a monopolist, Huberman, Leshno and Moallemi

The College Portfolio Problem, Ali and Shorrer

Equal Pay for Similar Work, Passaro, Kojima, and Pakzad-Hurson

Auctions with Withdrawal Rights: A Foundation for Uniform Price, Haberman and Jagadessan.

Optimal matchmaking strategy in two-sided marketplaces, Shi

Practical algorithms and experimentally validated incentives for equilibrium-based fair division (ACEEI),

Budish, Gao, Othman, Rubinstein

Congestion pricing, carpooling, and commuter welfare, Ostrovsky and Schwarz

Artificial intelligence and auction design, Banchio and Skrzypacz

Selling to a no-regret buyer, Braverman et al.

Dynamic matching in overloaded waiting lists, Leshno

The regulation of queue size by levying tolls, Naor

Optimal search for the best alternative, Weitzman

Whether or not to open Pandora’s box, Doval

Descending price optimally coordinates search, Kleinberg, Waggoner, Weyl

Market Failure in Kidney Exchange? Nikhil Agarwal, Itai Ashlagi, Eduardo Azevedo, Clayton Featherstone and Omer Karaduman

Choice Screen Auctions, Michael Ostrovsky

Incentive Compatibility of Large Centralized Matching Markets, Lee

Tentative schedule:

Week 1: Two-sided matching, stability and large markets.

Week 2: One-sided matching, duality, optimization and constraints.

Week 3: Multi-item auctions, auction design, revenue equivalence, optimal auctions, interdependent

valuations.

Week 4: Congestion, dynamic matching.

Week 5: Waitlists, search and learning.

Week 6: Foundations of mechanism design.

Week 7: Robustness in implementation

Weeks 8-10: Projects

We will host several guest lectures. Presentations of papers will take place throughout the course.

Background references

1. List of (mostly applied) papers are given in a separate document.

2. Books

Roth, Alvin E.and Marilda A. Oliveira Sotomayor, Two-sided matching: A study in game-theoretic modeling and analysis. No. 18. Cambridge University Press, 1992.

Vijay Krishna, Auction Theory, 2010.

Tilman Borgers, An Introduction to Mechanism Design by Tilman Borgers.

Milgrom, Paul, Putting Auction Theory to Work, 2004.

3. Papers

(a) Introduction

Roth, Alvin E. The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics. Econometrica, 70(4), 2002. 1341-1378.

Klemperer, Paul, What Really Matters in Auction Design?, Journal of Economic Perspectives, 16(1): 169-189, 2002.

Weitzman, Martin, Is the Price System or Rationing More Effective in Getting a Commodity to Those Who Need it Most?, The Bell Journal of Economics, 8, 517-524, 1977.

(b) Stable matching and assignment

Gale, David and Lloyd Shapley, College Admissions and the Stability of Marriage, American Mathematical Monthly, 69: 9-15,1962.

Roth and Sotomayor, Chapters 2-5.

Hylland, Aanund, and Richard Zeckhauser. The efficient allocation of individuals to positions, The Journal of Political Economy, 293-314,1979.

Roth, Alvin E., The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory. Journal of Political Economy, 92: 991-1016, 1984.

Kojimam, Fuhito and Parag A. Pathak. Incentives and stability in large two-sided matching markets. American Economic Review, 99:608-627, 2009

Abdulkadiroglu, Atila and Tayfun Sonmez. School choice: A mechanism design approach. American Economic Review, 93:729-747, 2003.

Abdulkadiroglu, Atila , Parag A. Pathak, and Alvin E. Roth. The New York City high school match. American Economic Review, 95:364-367, 2005.

Ashlagi, Itai, Yash Kanoria, and Jacob D. Leshno. Unbalanced random matching markets: The stark effect of competition, Journal of Political Economy,

Ashlagi, Itai and Peng Shi. Optimal allocation without money: An engineering approach. Management Science, 2015.

Peng Shi and Nick Arnosti. Design of Lotteries and Waitlists for Affordable Housing Allocation, Management Science, 2019.

Peng Shi, Assortment Planning in School Choice, 2019.

Ashlagi, Itai, and Afshin Nikzad. What matters in tie-breaking rules? how competition guides design, 2015.

(c) Auctions and revenue equivalence

Myerson, Roger Auction Design, Mathematics of Operations Research, 1981.

Milgrom, Paul. Putting Auction Theory to Work. Chapter 2-3.

W. Vickrey, Counterspeculation, auctions, and competitive sealed tenders, The Journal of Finance, 16(1) 8–37, 1961.

R. Myerson, Optimal auction design, Mathematics of Operations research, 1981.

J. Bulow and J. Roberts, The simple economics of optimal auctions, Journal of Political Economy, 1989.

J. Bulow and P. Klemperer, Auctions vs negotiations, American Economic Review, 1996.

P.R. McAfee and J. McMillan, Auctions and bidding, Journal of Economic Literature 1987.

P. Milgrom and R. Weber, A theory of auctions and competitive bidding, Econometrica, 1982.

Roth, A. E. and A. Ockenfels, Late-Minute Bidding and the Rules for Ending Second-Price Auctions: Evidence from eBay and Amazon.” American Economic Review, 92(4): 1093-1103, 2002.

(d) Mechanism design

Vickrey, William (1961): Counterspeculation, Auctions and Competitive Sealed Tenders. Journal of Finance, 16(1): 8-37.

Ausubel, Larry and Paul Milgrom, The Lovely but Lonely Vickrey Auction. in Cramton et. al Combinatorial Auctions, 2005.

J.C. Rochet, A necessary and sufficient condition for rationalizability in a quasi-linear context”, 1987.

K. Roberts, The characterization of implementable choice rules”, 1979.

F. Gul and E. Stacchetti, Walrasian equilibrium with gross substitutes, Journal of Economic Theory, 1999.

I. Ashlagi, M. Braverman, A,. Hassidim and D. Monderer, Monotonicity and implementability, Econometrica, 2011.

(e) Dynamic mechanism design and dynamic pricing

G. Gallego and G. Van Ryzin, Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management science, 40(8), 999-1020, 1994.

S. Board and A. Skrzypacz, Revenue management with forward-looking buyers, Unpublished manuscript, Stanford University,2010.

A. Gershkov, B. Moldovanu, P. Strack, Revenue Maximizing Mechanisms with Strategic Customers and Unknown, Markovian Demand

D. Bergemann and J. Valimaki, The dynamic pivot mechanism, Econometrica, 2010.

A. Gershkov and B. Moldovanu, Dynamic Revenue Maximization with Heterogeneous Objects: A Mechanism Design Approach, 168-198, 2009.

F. Gul, H. Sonnenschein, R. Wilson, Foundations of dynamic monopoly and the Coase conjecture, J. of Economic Theory, 1986.

D. Besanko and W. L. Whinston, Optimal price skimming by a monopolist facing rational consumers, Management Science, 1990.

(f) Dynamic matching

Itai Ashlagi and Alvin E. Roth. New challenges in multihospital kidney exchange. American Economic Review, 102:354-359, 2012

Nikhil Agarwal, Itai Ashlagi, Eduardo Azevedo, Clayton Featherston and Omer Karaduman. Market Failure in Kidney Exchange, 2018.

Anderson, R., Ashlagi, I., Gamarnik, D. and Kanoria, Efficient Dynamic Barter Exchange, Operations Research, 2015.

Mohammad Akbarpour, Shengwu Li, and Shayan Oveis Gharan. Dynamic matching market design. JPE, 2019.

Baccara, Mariagiovanna, SangMok Lee, and Leeat Yariv, Optimal dynamic matching, 2015.

Jacob Leshno, Dynamic Matching in Overloaded Waiting Lists, 2017.


Sunday, November 19, 2023

Scott Kominers on the history of matching, at Tsinghua, tomorrow

 CMSA/Tsinghua Math-Science Literature Lecture: Scott Kominers


"Beginning in Spring 2020, the CMSA began hosting a lecture series on literature in the mathematical sciences, with a focus on significant developments in mathematics that have influenced the discipline, and the lifetime accomplishments of significant scholars."

Monday, October 30, 2023

Simple Proofs of Important Results in Market Design-- (video of my talk at Berkeley's Simons Institute)

Here's a video of the talk I gave on Friday at the Simons Institute, on simple proofs of important theorems about matching, that have had impact on practical market design.

Thursday, October 26, 2023

Online and Matching-Based Market Design, Simons Institute, Berkeley. Oct. 26 – , Oct. 27,

 To celebrate the book of the same name, the Simons Institute is hosting a conference today and tomorrow on

Online and Matching-Based Market Design, Simons Institute, Berkeley.  Calvin Lab Auditorium, Thursday, Oct. 26 – Friday, Oct. 27, 2023


"All talks can also be viewed live on our YouTube channel, and recordings of each talk will also be available following each presentation unless otherwise noted. YouTube Live Stream: https://www.youtube.com/user/SimonsInstitute/live."

Thursday, Oct 26:

###
Update: the links in the final program now also include videos of most of the talks.