Dealing with Complexities in Auction and Matching Market Design

The week-long seminar began with participant introductions and featured a carefully balanced mix of:

• $\mathrm{■}$

  Survey talks, which provided foundational overviews and highlighted key developments in the field.

• $\mathrm{■}$

  Research presentations, focusing on current projects, algorithmic innovations, and real-world applications.

• $\mathrm{■}$

  Rump sessions to stimulate open discussion on challenges and open problems.

• $\mathrm{■}$

  Working group sessions for in-depth exploration of emerging research directions.

• $\mathrm{■}$

  A closing discussion including updates of working groups’ results, as well as a social excursion to foster informal interactions.

The seminar featured six in-depth survey talks, scheduled across the week, which framed the discussions and established key interdisciplinary touchpoints:

• $\mathrm{■}$

  Haris Aziz opened with a survey on fair allocation and matching, reviewing fundamental fairness concepts and recent advances in two-sided matching models.

• $\mathrm{■}$

  Thanh Nguyen gave a survey on relaxations in market design, highlighting how continuous relaxations and rounding can be used to tackle complex constraints in matching, exchange, and allocation markets.

• $\mathrm{■}$

  Axel Ockenfels presented a survey on behavioral market design, emphasizing the role of bounded rationality and empirical behavior in designing effective institutions, particularly in the face of global challenges.

• $\mathrm{■}$

  Bettina Klaus delivered a commemorative and forward-looking talk titled “Happy 50(+1)th birthday TTC!”, tracing the evolution of the Top Trading Cycles mechanism and its extensions to more complex and realistic preference domains.

• $\mathrm{■}$

  Margarida Carvalho concluded the seminar’s survey series with a talk on mathematical optimization for matchings, exploring mixed-integer programming formulations and their role in addressing many-to-one matching problems under constraints.

These survey talks spanned theoretical, algorithmic, and behavioral dimensions of market design and emphasized the importance of cross-disciplinary approaches to current market design problems.

Dagstuhl Seminar 25071 succeeded in fostering rich interdisciplinary exchange around the growing complexity of modern allocation problems. By emphasizing the connections between auctions and matching markets, and grounding theory in practical application domains, the seminar helped lay the groundwork for future collaboration and innovation in computational market design.

The diversity of topics and expertise reflected both the breadth of the field and the need for integrated approaches to market design challenges in an increasingly complex world.

The organisers thank all the Dagstuhl staff members for their professional support and the participants for enriching the seminar.

In this survey talk, I discuss some recent results and trends in the literature on fair allocation. I also discuss the connections with two sided matching.

We analyze the convergence of gradient-based learners to (Bayesian) Nash equilibrium in market games. While equilibrium can be verified ex-post, we discussed ex-ante conditions for convergence in games.

We study the relevance of the order of the objective criteria in the hierarchic optimisation in the Spanish kidney exchange programme. We conduct computer simulations on three real kidney exchange instances from Spain in 2019 and also on simulated datasets by using the ENCKEP kidney exchange simulator. We consider six optimisation criteria that are relevant in the Spanish policy: maximisation of (1) the number of transplants, (2) a composite quality-priority score, (3) the number of cycles, (4) the number of two-cycles and three-cycles with embedded two-cycles, (5) the number of back-arcs in the cycles, and (6) the minimisation of the number of ABO-incompatible transplants. In our simulations we compute all the alternative solutions that can be obtained by a hierarchical optimisation strategy using these criteria, and we analyse the trade-offs with regard to these objectives.

We study an optimal mechanism design problem for resource sharing between an incumbent noncommercial user and a commercial entrant. Motivated by applications such as wireless spectrum allocation and access to national resources, where noncommercial and commercial users compete for limited availability, the mechanism is subject to two key constraints. First, direct transfers cannot take place to compensate the incumbent for externalities caused by the activity of the commercial user. Instead, the incumbent reports a disutility for sharing to a regulator; the second constraint is that this disutility can only be verified via a costly inspection. The regulator optimizes total welfare by announcing a probability of shared resource assignment along with a probability of inspection. We show that in the optimal mechanism, both allocation and inspection decisions are binary: The regulator either fully allows or prohibits sharing, and inspections occur only for certain reported values when sharing is denied. We further reformulate the problem as a knapsack model to characterize threshold extremal points.

In this talk, we will begin by reviewing key aspects of effectively solving mixed-integer programming (MIP) formulations in practice. We will then explore optimization problems in many-to-one matchings, gradually progressing from computationally tractable cases to NP-hard ones. Along the way, we will examine MIP models, emphasizing the interplay between modeling techniques and solution strategies. Finally, we will conclude with open questions on the role of mathematical optimization in matching markets.

We study the problem of distributing subsidies in a market that includes both marginal individuals in need of assistance and infra-marginal individuals who would purchase the subsidized product without additional incentives. We propose the use of a wait time auction, where individuals bid the amount of time they are willing to wait in exchange for a specified subsidy amount. This design enables more direct targeting of marginal individuals, thereby enhancing the overall effectiveness of the subsidy program. Furthermore, screening is costless in equilibrium as no wait times are imposed, and practical robustness against deviations from equilibrium behavior can be ensured by implementing a maximum allowable bid.

The congested assignment problem is concerned with assigning agents to posts where agents care about both the posts and their congestion levels. Here, agents are averse to congestion, consistently preferring lower over higher congestion for the same resource. Such scenarios are prevalent across many domains, including traffic management and school choice, where fair resource allocation is crucial. Congested assignment can be considered as a restricted variant of the Group Activity Selection problem, introduced by Darmann et al. Additionally, it is related to many-to-one matching in matching under preferences.

In this talk, I will explore one ex-ante fairness concept, top-fairness, and two ex-post fairness concepts, envy-freeness and competitiveness. The top-fairness and competitiveness concepts were recently introduced by Bogomolnaia and Moulin. While a top-fair or envy-free assignment always exists and can be found easily, competitive assignments do not always exist. The talk will cover the following key points:

1. 1.

   An efficient method to determine the existence of competitive or maximally competitive assignments for a given congestion profile.

2. 2.

   Two optimization variants of congested assignments and their computational complexity: a) Finding a top-fair assignment that is envy-free b) Finding a top-fair assignment that is maximally competitive. Both variants are NP-hard, unfortunately.

3. 3.

   Parameterized algorithms for these NP-hard problems.

We study Abdulkadiroğlu and Sönmez’s (1999) house allocation problems with existing tenants. In particular, we focus on three welfare lower bounds conditions for agents, with respect to tenants’ endowments, solidarity for newcomers, and fairness for all agents. Based on these three welfare lower bounds conditions, together with three other well studied properties, namely pair efficiency, strategy-proofness and weak neutrality, we characterize a class of mechanisms proposed by Sönmez and Ünver (2005): the You Request My House-I Get Your Turn mechanism with Newcomer Priorities (YTP), which is a hybrid between the top trading cycles mechanism and a serial dictatorship mechanism of newcomers. Our result constitutes the first characterization, in the absence of invariance properties, e.g., non-bossiness and consistency.

Kidney Exchange Programs (KEPs) facilitate the exchange of kidneys, and larger pools of recipient-donor pairs tend to yield proportionally more transplants, leading to the proposal of international KEPs (IKEPs). However, practical limitations must be considered in IKEPs to ensure that countries remain willing to participate. Thus, we study IKEPs with country-specific parameters, restricting the selected transplants to be feasible for the countries to conduct, e.g., imposing an upper limit on the number of consecutive exchanges within a country’s borders. We provide a complexity dichotomy of finding allocations for different country-specific parameters and study the potential for countries to misreport their parameters to increase their allocation. As manipulation can harm the total number of transplants, we propose an individually rational (IR) and incentive compatible (IC) mechanism. We first give a theoretical approximation ratio for our mechanism in terms of the number of transplants and then use simulations to show that the cost of IC and IR in practice is between $18\%$ and $34\%$ of the maximum number of transplants.

The EU Energy Platform was established in April 2022. As part of the EU Energy Platform the EU also set up a demand aggregation and joint purchasing mechanism (DA/JPM), called AggregateEU. The AggregateEU is a non-binding mechanism that aims to match the supply and demand of natural gas in the context of multiple delivery points (mostly LNG terminals). The non-binding nature of the platform raises several potential problems (like the phenomenon of overbidding and its implications). Still, the synthesis of a non-binding alternative is also non-trivial. We aim to create an auction framework in which participants, either buyers or sellers of a homogeneous good are characterized by limited access and different access costs to each delivery point, while also considering the principle of fairness, i.e. equal access to cheap sources for buyer participants.

In this talk I will give an overview of some recent projects, focusing on the remaining open questions. The topics include NTU games for kidney exchange, core of many-to-many matching markets, student and resident allocation and a new notion called $k$-stability.

We use valid inequalities (cuts) of the binary integer program for winner determination in a combinatorial auction (CA) as “artificial items” that can be interpreted intuitively and priced to generate Artificial Walrasian Equilibria. While the lack of an integer programming gap is sufficient to guarantee a Walrasian equilibrium, we show that it does not guarantee a “price-match equilibrium” (PME), a refinement that we introduce, in which prices are justified by an iso-revenue outcome for any hypothetical removal of a single bidder. We prove the existence of PME for any CA and characterize their economic properties and computation. We implement minimally artificial PME rules and compare them with other prominent CA payment rules in the literature.

One cannot make truly fair decisions using integer linear programs unless one controls the selection probabilities of the (possibly many) optimal solutions. For this purpose, we propose a unified framework when binary decision variables represent agents with dichotomous preferences, who only care about whether they are selected in the final solution. We develop several general-purpose algorithms to fairly select optimal solutions, for example, by maximizing the Nash product or the minimum selection probability, or by using a random ordering of the agents as a selection criterion (Random Serial Dictatorship). We also discuss in detail how to extend the proposed methods when agents have cardinal preferences. Lastly, we evaluate the proposed methods on the specific application of kidney exchange. We find that while the methods maximizing the Nash product or the minimum selection probability outperform the other methods on the evaluated welfare criteria, methods such as Random Serial Dictatorship perform reasonably well in computation times that are similar to those of finding a single optimal solution.

In the Stable Roommates problem, the aim is, given a set of agents and their non-bipartite ordinal preferences over each other are given, to compute a matching of the agents such that no two agents prefer each other to their assigned partners (or are unmatched). In this talk, we will review concepts related to this problem, outline new theoretical and empirical perspectives on how to deal with instances that do not admit such matchings, and pose a range of algorithmic, structural, and complexity-theoretic questions.

We discuss two open problems in matching. First, in terms of a farsightedness, is a maximal matching indeed maximal? Second, under which conditions can we guarantee the existence of stable matchings, when preferences are generated through the satisfaction of objective criteria? Here we draw a connection to bargaining theory.

It is a classic result that the set of one-to-one stable matchings form a distributive lattice. We generalize this to many-to-many matchings with substitutable, IRC and increasing choice functions, and show that the lattice of the solutions is distributive. We know one-to-one stable matchings have rotations, we try to look at how to find something similar in many-to-many matchings.

We consider the housing market model with identical objects where each agent is indifferent among identical objects.  The Top Trading Cycles (TTC) mechanism with uniform tie-breaking satisfies individual rationality, Pareto optimality, and strategy-proofness. We introduce a new consistency notion for housing market with identical objects model. We show that when there are two types of objects TTC mechanism with uniform tie-breaking is consistent. However, when there are at least three types of objects TTC mechanism with uniform tie-breaking violates consistency. Our conjecture is that there is no rule satisfying individual rationality, Pareto optimality, strategy-proofness, and consistency for housing market with identical objects.

I present a survey talk commemorating more that 50 years of Gale’s famous top trading cycles (TTC) algorithm. The classical housing market model and the TTC algorithm were introduced by Shapley and Scarf (1974) in their seminal paper “Cores and Indivisibilities,” Journal of Mathematical Economics 1. The TTC agorithm / rule satisfies many desirable properties relating to weak / strong core stability, efficiency, and incentives, and, remarkably, is characterized by various combinations of these properties. I review some of the most important papers in the field and include some recent results on variations of the Shapley Scarf housing market model (multiple object (re)allocation, limited externalities, weak preference domains).

We study the role of correlation in matching, where multiple decision-makers simultaneously face selection problems from the same pool of candidates. We propose a model in which decision-makers have varying information on candidates from different sociodemographic groups when evaluating and ranking them, thus leading to varying correlations among candidates’ priority scores. Such differential correlation arises, for example, when the cost of information acquisition, decision-maker preferences, or the prevalence of selection criteria vary across sociodemographic groups. We show that a lower correlation for one of the groups worsens the outcome for all groups, thus leading to efficiency loss. Moreover, students from a given group are worse of as their own correlation level increases. This implies that it is advantageous to belong to a low-correlation group. Finally, we extend the extent tie-breaking literature to multiple priority classes and intermediate levels of correlation. Overall, our results point to a previously overlooked systemic source of group inequalities in school, university, and job admissions.

In many applications, participants care about an exogenous ranking that potentially distorts the preferences they submit in a centralized match. For example, a ranking influenced by a schools yield percentage might lead to a school rejecting students who the school expects to reject them. In the doctor-hospital match, the rank-to-fill metric (what spot on your preference list where you matched to) leads some hospitals to pressure students to rank it first. Can we design rankings which capture the relative quality of the agents being match but which do not distort the agent’s preference reports?

This talk presents a survey of a new approach to market design for complex environments. The approach first relaxes the discreteness of market design problems into a continuous market equilibrium solution and then rounds it to a nearby solution. I illustrate this method in four different settings: stable matching with complementarities, competitive equilibrium in allocations beyond substitutes and with budget constraints, combinatorial assignment and exchange without monetary transfer, and social choice.

Addressing pressing economic and social challenges – such as pandemics and other health crises, climate change, and energy scarcity – requires changes in behavior. In this talk, I will use case studies, primarily from my own research, to illustrate how human behavior and bounded rationality influences the design of institutions aimed at aligning incentives and actions with overarching goals. I will argue that economic design research and behavioral science are often complementary, rather than substitutes, in promoting effective behavioral change.

In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition (servers) are given, and the vertices on the other side (clients) arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching.

We propose a solution concept in which each agent $i$ does not necessarily optimize but selects one of their top $k_i$ actions. Our concept accounts for heterogeneous agents’ bounded rationality. We show that there exist satisficing equilibria in which all but one agent best-respond and the remaining agent plays at least a second-best action in asymptotically almost all games. Additionally, we define a class of approximate potential games in which satisficing equilibria are guaranteed to exist. Turning to foundations, we characterize satisficing equilibrium via decision theoretic axioms and we show that a simple dynamic converges to satisficing equilibria in almost all large games. Finally, we apply the satisficing lens to two classic games from the literature.

This talk presents a continuous-time game of strategic experimentation with two-armed bandits in which payoffs on the risky arm are generated by a compound Poisson process. The distribution of payoff increments depends on an unkown state of the world, whereas the arrival rate of such increments does not. As a consequence, players learn exclusively from the size of the lump-sum payoffs they obtain. Under perfect monitoring, the piecewise constancy of beliefs allows for an analysis of stationary Markov equilibria with essentially discrete-time techniques. In turn, these Markov equilibria constitute perfect Bayesian equilibria when players observe all payoffs, but not each other’s actions. Strongly symmetric equilibria cannot improve on the symmetric Markovian one. Whether asymmetric equilibria can achieve higher payoffs than Markovian equilibria is the focus of ongoing work.

We consider a strategic M/M/1 queueing model under a first-come first-served regime, where customers are split into two classes and class $A$ has priority over class $B$. Customers can decide whether to join the queue or balk, and, in case they have joined the queue, whether and when to renege. We study the equilibrium strategies and compare the equilibrium outcome and the social optimum in the two cases where the social optimum is or is not constrained by priority.

We study the strong core of housing markets when agents’ preferences over houses are expressed as partial orders. We provide a structural characterization of the strong core, and propose an efficient and weakly group-strategyproof algorithm that finds an allocation in the strong core or decides that it is empty, even in the presence of forced and forbidden arcs. Additionally, we show that certain results known for the strong core in the case when agents’ preferences are weak orders can be extended to the setting with partial order preferences; among others, we show that the strong core in such housing markets satisfies the property of respecting improvements.

This paper studies service assignment at the United States Naval Academy (USNA). Service assignment is the process which assigns each member of USNA’s senior class to one of several communities, each representing a career path within the Navy. This matching problem is unique to the literature in that it features hard minimums, community individual rationality constraints, and the requirement that every midshipman be assigned to a community. A stable assignment is generally impossible under these requirements: we characterize a natural relaxation that we call minimal unfairness. We then introduce the individual-rationality adjusted deferred acceptance algorithm (IRDA) and show that it always selects a minimally unfair assignment which respects the Navy’s requirements. This mechanism relies on the construction of caps based on the primitives, namely the minimums, maximums, and individual rationality constraints. These caps thus determine when a community must reject a midshipman, as well as which midshipman should be rejected. Unlike standard deferred acceptance in which the rejecting community simply rejects its least favorite proposal(s) above its ceiling, IRDA identifies a rejectable set of midshipmen, and forces the rejection of a midshipman in that set. We also discuss two alternative mechanisms, generalized serial dictatorship (GSD) and eligibility type capped deferred acceptance (ECDA), and contrast their properties with IRDA.

Last-mile delivery refers to the final leg in the distribution process, typically involving the transportation of goods from a depot or store to the customer’s house. Traditionally, this role was fulfilled by professional delivery fleets. However, the exponential growth of e-commerce globally has introduced significant logistical challenges, requesting for innovative delivery models. One such model is based on the concept of crowdsourcing, where individuals – commonly referred to as occasional drivers (ODs) – who have no professional affiliation with the retailers, sign up to deliver goods to customers for a compensation. That is the case of e.g. Amazon Flex.

Several research challenges can be considered. To name a few:

1. 1.

   How should parcels be assigned for delivery – should they be handled by the professional fleet or an OD? And among ODs, which driver is the best candidate for a specific delivery?

2. 2.

   Beyond economic efficiency, how can we ensure ODs remain engaged and satisfied with the program

3. 3.

   What is the optimal payment structure for an OD to ensure fairness while maintaining cost efficiency for the retailer?

The purpose of this talk is to provide a brief introduction to the problem and discuss with the audience potential areas of research aligned with the main topics of the seminar.

In kidney exchange programmes (KEP) patients may swap their incompatible donors leading to cycles of kidney transplants. Recently, countries try to merge their national patient-donor pools leading to international KEPs (IKEPs). As shown in the literature, long-term stability of an IKEP can be achieved through a credit-based system. In each round, every country is prescribed a “fair” initial allocation of kidney transplants. The initial allocation, which we obtain by using solution concepts from cooperative game theory, is adjusted by incorporating credits from the previous round, yielding the target allocation. The goal is to find, in each round, an optimal solution that closely approximates this target allocation. There is a known polynomial-time algorithm for finding an optimal solution that lexicographically minimizes the country deviations from the target allocation if only $2$-cycles (matchings) are permitted. In practice, kidney swaps along longer cycles may be performed. However, the problem of computing optimal solutions for maximum cycle length $\mathrm{\ell }$ is $NP$-hard for every $\mathrm{\ell }\ge 3$. By contrast, the problem is polynomial time solvable once we allow unbounded cycle length. However, in contrast to the case where $\mathrm{\ell }=2$, we show that for $\mathrm{\ell }=\mathrm{\infty }$, lexicographical minimization is only polynomial-time solvable under additional conditions (assuming $P\ne NP$). Nevertheless, the fact that the optimal solutions themselves can be computed in polynomial time if $\mathrm{\ell }=\mathrm{\infty }$ still enables us to perform a large scale experimental study for showing how stability and total social welfare are affected when we set $\mathrm{\ell }=\mathrm{\infty }$ instead of $\mathrm{\ell }=2$.

We are interested in the question of why gradient-based no-regret learning converges to the Bayes-Nash equilibrium in Bayesian market games such as auctions, contests, and oligopoly pricing. For this, we first focus on the all-pay auction. The complete-information all-pay auction only has a mixed Nash equilibrium. In contrast, with continuous types and actions, there is a unique pure Bayes-Nash equilibrium (PBNE). After discretizing the type and action space of this continuous game, we usually observe convergence to a PBNE. However, existence and convergence depend on the discretization of the type and action space. We aim to explain the reasons why the complete-information all-pay auction has no PBNE, but the discretized version of the game does. These questions should shed light on the more general reasons why we see convergence to a PBNE in a wide variety of Bayesian games.

In a financial network the banks (or companies) have initial assets and liabilities towards each other. Financial clearing means that all the banks have to pay their obligations immediately. If a bank has more dept than its assets and credits then it will go bankrupt, and can only pay part of its liabilities to its creditors using a pre-defined payment rule, potentially causing a cascading effect of bankruptcy in the network involving banks that looked healthy initially. The so-called systemic risk in a network can be even higher if certain bankruptcy costs occur when a bank defaults, generating amplified losses in the economy.

Portfolio compression is an act in financial markets where the financial obligations are cleared in a cycle after the mutual agreement of the agents involved. The coordination of the portfolio compression can be done by private agencies, e.g., TriOptima for banks, or by governmental agencies, as in Romania for companies. When the agents give their approval in advance to a central coordinator for portfolio compression, then the coordinator can choose a portfolio compression over one or multiple cycles. The goal of the coordinator can be to reduce as much dept as possible, or to reduce the systemic risk. In our working group, we discussed the possibility of using a mixed integer linear programming approach with bi-level optimisation to finding a portfolio compression for a given financial network and payment rules to maximise these objectives.

In supply chain management, the expression last mile describes the logistical challenges corresponding to the final phase of transportation, in which items are delivered to their terminal destinations. Last-mile delivery (LMD) is the most expensive and most polluting part of the supply chain. Considering the totality of simultaneous LMDs, efficiency is not ideal. Multiple vehicles take part in the process, partially loaded. It is however not trivial, how the coordination of LMD operations may be increased, without monopolizing the sector.

The concept of cooperation in the delivery process is not novel. Literature sources emphasize the importance of central planning (or collaborative planning), which reduce the the overall cost and so the sum of distance and increase the efficiency at the same time. However, in these works the collaboration platform is operated by delivery companies and focuses mainly on profit sharing mechanism, or in other word the players in the game are the the delivery companies and the single delivery tasks are not considered as active members of the market.

As a particular approach, auctions may be efficiently used to increase the coordination in transportation management, more specifically in the efficient procurement of transportation services. The first optimization-based auction for a transportation service allocation, which allowed package (or combined) bids dates to 1992. The items to be auctioned were service rights for lanes, i.e., single transportation paths between cities, and the service rights have been allocated for years.

For Shapley-Scarf housing markets with weak preferences the TTC rule with fixed tie-breaking is not Pareto efficient. Ehlers (2014): “Top trading with fixed tie-breaking in markets with indivisible goods,” Journal of Economic Theory, shows that Gale’s top trading cycles algorithm with fixed tie-breaking is characterized by weak efficiency, individual rationality, strategyproofness, non-bossiness, and consistency.

For Shapley-Scarf housing markets with strict preferences, the TTC rule is the only rule satisfying Pareto efficiency, individual rationality, and strategy-proofness. A natural question then is: Are there generalizations of TTC that are satisfying the Ma properties? The answer is yes, as illustrated by the following references: Jaramillo and Manjunath (2012); Alcalde-Unzu and Molis (2013); Aziz and de Keijzer (2012); Plaxton (2013); Saban and Sethuraman (2013); Xiong, Wang, and He (2022). Since there are several extensions of TTC to the weak preference domain, can we refine the class by imposing more properties?

Our working group (Bettina, Haris, Mehmet, Naomi, Tamas, Thayer, Yang) first studied the Xiong, Wang, and He (2022) algorithm. We conjecture that it satisfies strong core stability (proof to be worked out) and plan to analyze the other properties for it (and for the other mechanisms). We also brainstormed on the general structure behind all proposed algorithms and their link to the underlying properties. We’ll continue with these ideas and hopefully will obtain some neat results.

School authorities increasingly turn to lotteries as a means of addressing school segregation. In Europe, a growing number of cities have adopted lottery-based admissions, replacing traditional priority-based systems.

Our working group (Federico, Margarida, Gian, Jiehua, Gergely, Tom, Frederik, Claus-Jochen, Zsuzsanna, Thilo, Katarzyna, Nadja) examined the case of Amsterdam, which introduced the Deferred Acceptance (DA) mechanism with multiple tie-breaking and no priorities in 2015. We analysed the city’s responses to the challenges that emerged from this approach and identify three key areas for improvement: (1) Efficiency: In response to legal disputes from parents seeking to swap school places, Amsterdam transitioned to a single tie-breaking system. (2) Inequality: To address concerns about unequal access, the city introduced a guarantee of placement at a top-$k$ school from students’ ranked preferences. (3) Reciprocity: Amsterdam added a priority rule for students ranking a school first, effectively introducing an Immediate Acceptance (IA) step before the DA process. While these modifications, implemented in 2016 and 2018, aimed to improve outcomes, they rendered the mechanism obviously manipulable.

We analysed an adaptive mechanism combining a maximum $b$-matching with the rank minimizing (RM) mechanism. This combination balances efficiency, equality, and reciprocity while muting strategic incentives. We will continue this analysis and discuss it with researchers and policy makers in Amsterdam.

Consider an undirected graph $G=(V,E)$ and a set of agents $𝒩$.Each agent $i\in 𝒩$ has a valuation function over the graph’s edges $w_i:E\to ℝ$. Our problem is to find a spanning subgraph $H=(V,F)$ of $G$ such that $|F|$ is minimal and for each agent $i\in 𝒩$, the graph $H$ contains a minimal spanning tree of $G$ with respect to $w_i$.

We started with the case where $|𝒩|=2$, and provided two polynomial-time algorithms for the problem. The first algorithm relies on the known fact that the edge sets of minimum spanning trees for some valuation function $w_i$ form a matroid, and uses a weighted matroid-intersection algorithm to compute in polynomial time a largest edge set that is contained in a $w_i$-minimum spanning tree for both $i=1,2$. Such an edge set can then be extended to a solution of minimum size in a straightforward manner. The second algorithm is combinatorial and relies only on elementary techniques and a few structural observations without building on matroid theory.

The initial steps and focus areas of a project aimed at integrating generative AI into auction bidding systems. After exploring multiple potential use cases, the team chose to prioritize building a bidding interface for a combinatorial auction, deferring broader mechanism design-related applications to future work. The team explored applications such as TV advertising slot auctions and school choice mechanisms, and reviewed existing bidding language models including combinatorial assignments with budget constraints. The plan is to begin with simple sealed bid scenarios using value queries, avoiding more complex iterative approaches initially.

Preliminary testing with various versions of Claude and GPT models revealed limitations and strengths. While the models show potential in templating and general language understanding, they struggle with advanced quantitative reasoning. GPT-4’s reasoning model was marginally better but still insufficient for more nuanced tasks. The team observed a bias toward online advertising tasks – likely due to the models’ training data – further highlighting the need for customization to suit a specific bidding application (actually to include advertising, as the model biases towards contemporary mechanisms like adsense).

To address these challenges, the team recognized a need for customization, likely both in the LLM and in the code around it. More specifically, this likely includes integrating domain-specific information via Retrieval-Augmented Generation (RAG), building a custom value calculator (potentially with LLM support), and creating agentic systems that combine LLMs with tool-use capabilities. Fine-tuning the LLM is a potential step, though we are hoping to avoid having to do this.

The initial work at the conference was promising, but also made clear that there is quite a bit of follow on work necessary to get a usable system. We also briefly discussed how such a system might be evaluated as a path to a publishable paper.