PaperlayerView exact revision on arXiv

Source-linked AI summary

A Weakly Group Strategy-Proof and Pareto-Stable Matching Mechanism with Two-Sided Indifferences under Gross Substitutes

Yasushi Kawase, Ryosuke Sato

arXiv:2610.30807v1cs.GTecon.TH

TL;DR

Tie-breaking in deferred acceptance can produce weakly stable matchings that are Pareto dominated under the original preferences. This paper constructs a deterministic generalized deferred acceptance mechanism for GS-representable firm preferences. It selects Pareto-stable matchings, is worker weakly group strategy-proof, and runs in strongly polynomial time given value oracles.

  • Problem

    With indifferences on both sides, tie-breaking before deferred acceptance can yield a weakly stable matching that is Pareto dominated under the original preferences.

    Source: §1 · p. 1

  • Method

    The paper uses generalized deferred acceptance over preference tiers and relates its outcome to a seller-optimal equilibrium matching in a tiered auxiliary market.

    Source: Generalized Deferred Acceptance · p. 7

  • Results

    For GS-representable firm preferences, the mechanism is worker weakly group strategy-proof, selects a Pareto-stable matching, and runs in strongly polynomial time given value oracles.

    Source: Generalized Deferred Acceptance · p. 7

  • Takeaways & Limitations

    The guarantees cover nonresponsive firm preferences over worker sets, including preferences based on hiring constraints, diversity policies, and position-dependent values.

    Source: §1.1 · p. 2

    The procedure requires GS-representability of firms’ full preferences over worker sets; GS-induced choice correspondences alone do not suffice.

    Source: §7 · p. 21

Abstract

from arXiv · show

We study finite many-to-one matching markets with indifferences on both sides and publicly known firm preferences over sets of workers. A standard approach breaks ties uniformly at random and runs deferred acceptance, which is strategy-proof for workers but may select a weakly stable matching that is Pareto dominated under the agents' original preferences. For the broad class of markets in which each firm's preferences admit a gross substitutes (GS) representation, we construct a deterministic generalized deferred acceptance mechanism that is weakly stable, Pareto efficient with respect to both sides, worker weakly group strategy-proof, and implementable in strongly polynomial time given value oracles for the GS representations. This domain includes nonresponsive firm preferences, such as additive scores under matroid constraints and assignment values. Our analysis bridges ordinal matching with indifferences and competitive equilibria under imperfectly transferable utility. Although the mechanism uses only ordinal comparisons, it returns a seller-optimal equilibrium matching of a tiered auxiliary market, and the equilibrium structure of this market yields the stability, efficiency, and incentive guarantees.

1 Introduction

With indifferences on both sides, breaking ties before deferred acceptance can sacrifice Pareto efficiency, while later stable improvements can sacrifice strategy-proofness. The paper gives a deterministic mechanism for gross-substitutes firm preferences that is worker weakly group strategy-proof and selects Pareto-stable matchings.

1 Introduction

  • Tie-breaking before deferred acceptance can return a weakly stable matching that is Pareto dominated under the original preferences.Stable improvement cycles may address this inefficiency, but a mechanism based on them need not be strategy-proof.Source: §1 · pp. 1–2

1.1 Our results

  • For GS-representable firm preferences, the mechanism is worker weakly group strategy-proof and selects a matching that is weakly stable and Pareto efficient for workers and firms.The domain includes nonresponsive preferences, such as those arising from hiring constraints, diversity policies, and position-dependent values.Source: §1.1 · p. 2
  • The procedure moves unmatched workers down preference tiers and uses serial dictatorship over feasible matchings, while matched workers may change firms within their current tiers.It uses ordinal comparisons and runs in strongly polynomial time with value oracles for the GS representations.Source: §1.1 · p. 2
  • A tiered auxiliary market with workers as sellers and firms as GS buyers connects the mechanism to seller-optimal equilibrium matchings and establishes its guarantees.The analysis also shows resistance to coalitions of several firms; equilibrium assigned-tier profiles form a distributive lattice, whose greatest element the mechanism attains.Source: §1.1 · pp. 2–3

1.2 Related work

  • The framework extends prior tiered-slope and indifference-handling approaches to GS firm preferences, including nonresponsive preferences over worker sets.Earlier approaches discussed here derive firm preferences from individual-worker rankings or study efficiency within weakly stable matchings.Source: §1.2 · p. 3

2 Model

The model is a finite many-to-one ordinal market with worker reports and public firm preferences over worker sets. Firm preferences are assumed to have gross-substitutes representations, a condition that accommodates several forms of nonresponsive preferences.

2.1 Ordinal matching market

  • Workers and firms have weak orders that may contain ties; workers report preferences, while firms’ preferences over sets of workers are public.A matching assigns each worker to at most one firm, and firms may employ several workers.Source: §2.1 · p. 4
  • A matching is weakly stable when it is individually rational and has no blocking coalition, and Pareto-stable when it is also Pareto efficient for workers and firms.Worker weak group strategy-proofness rules out a coalition of workers all strictly benefiting from alternative reports.Source: §2.1 · p. 4

2.2 Gross substitutes firm preferences

  • Firm preferences must be represented by a gross-substitutes set function, whose demand retains unchanged-price items when prices rise and which satisfies an exchange axiom.The effective domain and demand families of GS functions are generalized matroids; integer-valued GS representations can represent the firm’s weak order over worker sets.Source: §2.2 · p. 5

2.3 Examples of GS-representable preferences

  • GS-representable preferences include additive scores under matroid constraints, laminar concave values, and assignment values for position-dependent contributions.Assignment values can also model reserved positions for worker types, including overlapping eligibility, with each worker filling at most one position.Source: §2.3 · pp. 5–6

3 Generalized Deferred Acceptance

Generalized deferred acceptance advances workers through acceptable preference tiers while selecting among feasible matchings by firm and worker index orders. Under GS-representable firm preferences, it returns a Pareto-stable matching and is worker weakly group strategy-proof.

3 Generalized Deferred Acceptance

  • The procedure fixes firm and worker index orders before reports and lets unmatched workers advance to their next acceptable tier while matched workers may change firms within their current tiers.Firms, then workers, successively retain their best remaining feasible matchings; the final matching is selected by a lexicographic rule.Source: §3 · p. 6

Generalized Deferred Acceptance

  • Each round advances at least one unmatched worker, so the procedure stops after at most |I| · |J| rounds.The set of advancing workers does not depend on which matching is selected among the retained candidates.Source: Generalized Deferred Acceptance · p. 7
  • With strict worker preferences and unique firm choices, the procedure coincides with worker-proposing deferred acceptance; in one-to-one markets with indifferences, it coincides with the algorithm of Igarashi et al. [24].Source: Generalized Deferred Acceptance · p. 7
  • For GS-representable firm preferences, the procedure is worker weakly group strategy-proof, selects a Pareto-stable matching, and runs in strongly polynomial time given value oracles.It returns a seller-optimal equilibrium matching of a tiered auxiliary market without computing transfers or payoffs.Source: Generalized Deferred Acceptance · p. 7

4 Equilibria of the Auxiliary Market

The section represents the matching problem as an auxiliary market with workers as sellers and firms as gross-substitutes buyers. Seller-optimal equilibria provide the basis for the section’s Pareto-stability and worker-incentive guarantees.

4.1 Markets with transfers

  • The transfer-market framework yields an existing seller-optimal equilibrium, and every deterministic seller-optimal mechanism is seller weakly group strategy-proof [40].Sellers supply at most one trade, while buyers may take several; buyers report public quasilinear utilities and sellers report utility functions.Source: §4.1 · pp. 8–9

4.2 A tiered auxiliary market

  • The auxiliary market makes workers unit-supply sellers and firms gross-substitutes buyers, with fixed weights ranking firms and worker-index weights breaking remaining ties.Worker utilities scale transfers by λ^-rank, so a better-ranked firm yields the same payoff for a smaller payment; baseline outside payoffs are set by β0_i = ω_iλ^r_i(∅).Source: §4.2 · pp. 9–10
  • Every baseline equilibrium matching is Pareto-stable under the original preferences, and every deterministic mechanism selecting a seller-optimal equilibrium matching is worker WGSP.The result holds for any fixed positive integer firm weights α_j used in the construction.Source: §4.2 · pp. 9–10

4.3 Equilibrium payoff bounds

  • At a seller-optimal baseline equilibrium, a matched worker’s payoff lies in [λr, λr+1), identifying the rank of her assigned firm.Seller-optimal payoffs satisfy the lower bound needed for this tier interpretation; all baseline equilibria also have the stated upper bound.Source: §4.3 · pp. 10–12

4.4 Proof of Theorem 4.2

  • The proof derives weak stability from firms’ equilibrium demand and rules out Pareto improvements by combining firm-value gains with workers’ rank and payoff bounds.A strict improvement for either a firm or a worker makes a corresponding term positive, contradicting the equilibrium demand inequality; worker WGSP follows from seller-optimality in the auxiliary market.Source: §4.2 · p. 10, §4.4 · p. 13

5 An Equilibrium Characterization of Generalized Deferred Acceptance

Generalized deferred acceptance can be characterized through equilibria of auxiliary markets whose worker outside payoffs change as workers advance through tiers. This characterization connects the matchings retained during the procedure to welfare maximization and, at termination, to seller-optimal equilibrium in the baseline market.

5 An Equilibrium Characterization of Generalized Deferred Acceptance

  • The auxiliary market keeps trades and buyer valuations fixed while later rounds lower the outside payoffs of unmatched workers as they advance through tiers.This descending change parallels a descending auction until a buyer accepts.Source: §5 · p. 14

5.1 Welfare maximization within current tiers

  • Within current tiers, maximizing the welfare objective retains exactly the matchings selected by the firms’ and workers’ ordered choices.The objective first maximizes firm values in index order, then reproduces workers’ choices in index order.Source: §5.1 · pp. 14–15

5.2 Equilibrium matchings in each round

  • After each round, the matchings retained by generalized deferred acceptance are exactly the equilibrium matchings of that round’s auxiliary market.The auxiliary market uses outside payoffs determined by the current tier profile; its seller-optimal payoff vector is monotone in those outside payoffs.Source: §5.2 · p. 16

5.3 Seller optimality at termination

  • At termination, the retained matchings are exactly the seller-optimal equilibrium matchings of the baseline market, so generalized deferred acceptance selects a Pareto-stable matching and is worker weakly group strategy-proof.The procedure fixes its representations, weights, and constants before workers report and runs in strongly polynomial time given value oracles.Source: §5.3 · p. 17

6 Further Properties of Generalized Deferred Acceptance

The equilibrium characterization yields further properties of generalized deferred acceptance: resistance to specified multi-firm deviations, a lattice structure for equilibrium assigned tiers, and a worker-undominance guarantee within a defined mechanism class.

6.1 Coalitional stability

  • No coalition of firms can weakly improve all its firms’ outcomes, strictly improve one, and satisfy the stated worker-improvement conditions through a deviation.This extends beyond weak stability, which rules out deviations by a single firm together with workers.Source: §6.1 · p. 18

6.2 Lattice structure of assigned-tier profiles

  • The rank vectors of baseline equilibrium matchings form a distributive lattice under coordinatewise maximum and minimum, and generalized deferred acceptance attains its greatest element.The comparison concerns workers’ assigned tiers across equilibrium matchings.Source: §6.2 · p. 19

6.3 Worker-Pareto undominance

  • No deterministic worker strategy-proof mechanism satisfying tierwise firm priority can uniformly give every worker an assignment weakly preferred to generalized deferred acceptance’s while strictly improving anyone.Generalized deferred acceptance need not be worker-optimal among all weakly stable matchings.Source: §6.3 · pp. 19–20

7 Concluding Remarks

The concluding remarks extend the guarantees to specified alternatives for firms’ choice stage and identify boundaries of the approach. They leave open whether conditions on choice correspondences alone suffice when workers may be indifferent.

7 Concluding Remarks

  • Pareto stability and worker weak group strategy-proofness also hold when firms maximize a positive-integer weighted sum of their gross substitutes representations fixed before reports, retaining all maximizers.The same ordered worker choices and final selection are used.Source: §7 · p. 21
  • With responsiveness-based firm preferences and suitable slot weights, the extension reproduces the round-robin choice of Igarashi et al. [24] under the stated capacity conditions.The example assumes all workers find all firms acceptable and specifies capacities using n = km + r.Source: §7 · p. 21
  • Gross substitutes representability cannot be replaced by requiring only that firms’ choice correspondences be induced by gross substitutes functions.An appendix example returns an unstable matching even though a Pareto-stable one exists.Source: §7 · p. 21
  • It remains open whether path independence and the law of aggregate demand suffice for a mechanism guaranteeing weak stability, Pareto efficiency, and worker weak group strategy-proofness when workers may be indifferent.The proposed extension evaluates firm welfare using revealed-preference preorders generated by choice correspondences.Source: §7 · p. 21

A Failure under GS-Induced Choice Correspondences

The example shows that generalized deferred acceptance can fail weak stability even when firm choice correspondences have GS representations. Yet a Pareto-stable matching exists, and GS-representability of choices does not imply GS-representability of firms’ full preferences.

A Failure under GS-Induced Choice Correspondences

  • Generalized deferred acceptance can fail weak stability even when every firm’s choice correspondence is induced by a GS function.The example distinguishes GS-representability of choice correspondences from GS-representability of full firm preferences.Source: A Failure under GS-Induced Choice… · p. 24
  • The procedure’s third-round matching is blocked by firm B and workers bcd because B prefers bcd to cd and worker b prefers B.At termination, B’s bundle is cd; the blocking bundle bcd has higher utility for B.Source: A Failure under GS-Induced Choice… · p. 25
  • Firm B’s choice correspondence has a GS representation although its full weak order has none, so unchanged choices can conceal comparisons relevant to stability.Changing bundle comparisons without changing the choice correspondence can lead the procedure to return an unstable matching.Source: A Failure under GS-Induced Choice… · pp. 24–25
  • A different matching is Pareto-stable: B receives its unique best bundle acd, and preserving B’s best bundle and A’s welfare fixes all assignments.That matching is individually rational and admits no block.Source: A Failure under GS-Induced Choice… · p. 25

B Strongly Polynomial Implementation

For each tier profile, the round’s matching is the unique maximizer of an objective over feasible matchings. Valuated matroid intersection computes it, yielding a strongly polynomial implementation with GS value oracles.

B Strongly Polynomial Implementation

  • For every tier profile, Ψ(F) is the unique maximizer over M(F), with the objective retaining the eligible matchings and selecting by worker-index assignment order.The objective first retains the designated matching set, then minimizes the assignment vector lexicographically.Source: B Strongly Polynomial Implementation · p. 25
  • The maximization is a valuated matroid intersection on |EF| + n elements, formed using a valuated matroid and a partition matroid.The partition-matroid bases correspond to feasible matchings with dummy elements for unmatched workers.Source: B Strongly Polynomial Implementation · pp. 25–26
  • O(n^4m^3) value queries suffice across at most nm rounds, and the procedure runs in strongly polynomial time given value oracles for GS representations.Each round uses O(n^3m^2) value queries.Source: B Strongly Polynomial Implementation · pp. 25–26
Loading 2610.30807v1…