Source-linked AI summary
From the Social Choice Problem to a Collusion-Proof Tendering Mechanism for Dynamic Stochastic Projects
Endre Csóka
TL;DR
The paper addresses how efficient implementation can remain robust to strategic behavior and collusion in static and dynamic multi-agent settings. It connects TU-GUM’s sequential bilateral settlement rule to broader project-management mechanisms combining GUE with first-price tendering. The resulting framework preserves budget balance and utility guarantees while extending to dynamic settings, subject to scope limitations in richer tendering environments.
Problem
Efficient implementation mechanisms must reconcile truthful incentives, budget balance, robustness to other agents’ behavior, and cooperation failures in dynamic projects.
Method
The paper connects TU-GUM’s GUE-based sequential bilateral externalities with a general project-management mechanism combining GUE and contingent first-price tendering.
Results
TU-GUM preserves budget balance and GUE utility guarantees, extends to dynamic settings, and is a special case of the broader project-management mechanism.
Takeaways & Limitations
The framework provides a transferable-utility route to efficient implementation that protects guaranteed utilities and supports coordinated execution in dynamic settings.
Takeaways & Limitations
In the full project-management model, general formal guarantees for first-price tendering’s allocative efficiency and expected revenue under moderate competition remain difficult to establish.
Abstract
from arXiv · showhide
The VCG family and the AGV mechanism are two classical approaches to efficient implementation in the static social choice problem. In 2024, Csóka et al. showed that AGV has critical weaknesses. In contrast, the transferable-utility Guaranteed Utility Mechanism (TU-GUM) retains all the standard desirable properties of AGV while adding further ones, including collusion-proofness, because it implements efficiency in Guaranteed Utility Equilibrium. TU-GUM also applies to a more general dynamic setting with multiple extensions. Moreover, TU-GUM is a special case of an even more general and robust mechanism that combines contingent first-price tendering with the coordinated execution of dynamic stochastic multi-agent projects through a surprisingly simple rule. This paper summarizes and connects existing results from a different perspective, with some minor new observations.
1 The static social choice problem: VCG, AGV, and TU-GUM
The section contrasts VCG, AGV, and TU-GUM as mechanisms for efficient implementation, focusing on incentive properties, budget balance, and robustness in static and dynamic settings. TU-GUM uses sequential bilateral externalities to obtain Guaranteed Utility Equilibrium implementation while preserving budget balance.
- VCG implements the efficient policy in dominant strategies but cannot generally combine truthful implementation with exact budget balance.
- AGV is budget-balanced and makes truthful reporting a Bayesian Nash equilibrium through expected externality transfers.
- Truthful reporting under TU-GUM provides a Guaranteed Utility Equilibrium guarantee, and symmetrizing over processing orders preserves budget balance and the same guarantees.
- TU-GUM processes reports sequentially and settles each bilateral externality directly between the reporting and affected agents.
- In dynamic settings, GUE implementation extends beyond static mechanisms, whereas dynamic VCG implementation can fail robustness to iterated elimination of weakly dominated strategies.
- For two agents, AGV and its dynamic extension BTM are also GUE implementations, and every two-agent dynamic externality-payment mechanism has this property.
2 A three-agent social choice example
The three-agent example computes VCG, AGV, and TU-GUM transfers for a fixed efficient policy. It shows how TU-GUM preserves budget balance and guarantees truthful agents expected utility against arbitrary behavior by others, unlike AGV’s collusion vulnerability.
- Efficient policy: The efficient policy selects x = 1 when at least two reports equal 10 and has ex-ante expected total payoff M = 9.
- TU-GUM transfers: When a report changes another agent’s anticipated payoff, TU-GUM compensates the affected agent through a direct bilateral payment.
- TU-GUM transfers: Fixed-order TU-GUM transfers sum to zero for every displayed report profile, although the fixed processing order makes individual transfers asymmetric.
- Utility guarantees: Truthful reporting guarantees each agent ex-ante expected utility 3 against every strategy profile of the other agents.
- Utility guarantees: Both AGV and TU-GUM give a truthful agent ex-ante expected utility 3, but only TU-GUM guarantees that level against arbitrary behavior by others.
- Collusion-proofness: Under AGV, a coalition can increase its aggregate utility through joint misreporting, whereas TU-GUM prevents such gains when outsiders remain truthful.
3 Generalizations of TU-GUM
The sequential-externality construction extends TU-GUM beyond static social choice to dynamic games, private actions, and contractible interdependencies. These extensions retain exact GUE implementation in transferable-utility settings under fixed participating sets and initial types.
- Dynamic games: In dynamic games, sequential bilateral externalities include effects on other agents’ anticipated utilities in future periods as well as the current period.
- Private actions: The framework accommodates efficient policies recommending private actions in addition to public decisions by enlarging continuation-value and sequential-externality calculations.
- Working-process interdependencies: The construction also covers contractible interdependencies between agents’ working processes.
- All three extensions yield exact GUE implementations in transferable-utility settings when the participating set and initial type profile are fixed in the mechanism specification.
- Further directions: Transfer-free and non-fixed-initial-type variants provide further extensions, including mechanisms with vanishing per-period error and auction stages for contingent offers.
4 The Project Management Model and Mechanism
The Project Management Model addresses team selection and coordinated execution when agents privately know dynamic stochastic work processes. Its prior-free mechanism combines contingent contract offers with a maximin choice rule, using guaranteed utility to support truthful cooperation.
- The Project Management Mechanism is prior-free and combines guaranteed-utility logic with first-price tendering for team selection.
- Each candidate privately observes a type specifying a stochastic dynamic working process, including private actions, chance events, probabilities, and contractible results.
- The principal selects a team and accepts contract offers that specify transfers for every communication history and result vector.
- The mechanism evaluates accepted agents in a worst-case game where they may choose arbitrary communication strategies, results, and coordination.
- The principal chooses a strategy maximizing her minimum utility, making offers comparable while assigning each agent the risks from his own uncertainty.The maximin rule secures a guaranteed utility level for the principal.
- Truthful offers guarantee each agent a specified utility against every strategy profile, allowing the principal to direct efficient team cooperation under the idealized assumptions.This is the GUE-type logic underlying the Project Management Mechanism.
5 Specializations and the full Project Management Model
The model’s specializations connect dynamic multi-agent execution to first-price tendering, combinatorial auctions, and TU-GUM. These reductions clarify both the mechanism’s collusion properties and its limits under competition and informational assumptions.
- The model distinguishes dynamic versus static interaction, multi-agent versus single-agent execution, robustness, and the presence or absence of an auction.
- Single-contractor tendering: With a commonly known principal type, truthful offers can be indexed by one parameter, and the quasilinear sell-the-firm representation makes the contractor residual claimant of project surplus.Conditional on selection, the contractor’s private decisions maximize expected project surplus.
- Single-contractor tendering: In the quasilinear benchmark, the single-contractor tender reduces exactly to a first-price auction, or equivalently a procurement auction after reversing signs.First-price tendering is an exact reduction of the induced game, not a general efficiency result.
- Full Project Management Model: The full mechanism specializes to a first-price combinatorial auction, while TU-GUM’s exact reduction requires quasilinearity and independence of newly realized private chance events.
- Combinatorial tendering: Against fixed outside bids, a coalition cannot gain from separate combinatorial bids beyond what it could obtain by entering openly as one consortium.This aggregation property does not prevent consortium formation; it removes the extra benefit of concealed coordination.
- Full Project Management Model: The static benchmark lacks useful general guarantees for allocative efficiency and expected revenue, while the first-price mechanism’s competitive performance is supported mainly by intuition under moderate competition.
- Full Project Management Model: Under perfect competition, and when agents know one another’s initial types while the principal does not, the Project Management Mechanism has exact efficiency results.More generally, competitive losses are expected to resemble those of first-price combinatorial auctions rather than additional execution-cooperation losses.
A.1 A three-agent counterexample
The three-agent example shows that exhaustive IEWDS under AGV can leave only an inefficient strategy profile, independently of deletion order. At the low-type profile, the surviving reports induce the big investment despite a zero-payoff alternative.
- The example has two agents with independent equiprobable low and high types, a third single-type agent, and decisions of none, small investment, or big investment.
- Efficiency does not identify a unique decision policy because multiple decisions tie at some type profiles.At (L, L), both N and S are efficient; at (L, H), all three decisions are efficient.
- AGV incentive terms make reporting H costly relative to L by 15 transfer units for agent 1 and 4 for agent 2.
- The IEWDS implications force the relevant reporting and mixing probabilities toward the always-H strategies.
- Deletion order does not matter: the unique survivor is for agents 1 and 2 to always report H, so the mechanism always selects B.
- At (L, L), selecting B is inefficient because its total payoff is −5, whereas N and S each yield total payoff 0.
- Thus exhaustive IEWDS under AGV eliminates every efficient strategy profile.
A.2 Unique-decision protection: scope and limits
With a unique efficient decision at every type profile, truthful reporting survives every iterated elimination of weakly dominated strategies in AGV, even with randomized reports. This protection does not resolve equilibrium-selection concerns, and dynamic AGV can fail even under generic uniqueness.
- Protection: Truthful reporting survives every iterated elimination of weakly dominated strategies in AGV when the efficient decision is unique at every type profile.The result continues to hold when randomized reports are allowed.
- Protection: Any report that changes the decision against truthful opponents is strictly worse, while unchanged reports are payoff-equivalent to truth everywhere.Full support ensures that a changed decision occurs with positive probability and lowers total welfare.
- Protection: The truthful efficient profile therefore survives every elimination order because truthful opponent reports remain available when any first deletion is considered.The contradiction argument applies to every IEWDS sequence.
- Limits: Unique efficient decisions do not by themselves resolve equilibrium selection, since arbitrarily small perturbations can preserve proximity to the counterexample while weakening the dominance argument.Thus truthful play need not become intuitively compelling merely because the efficient decision is unique.
- Limits: Dynamic AGV is more fragile: a generic environment with at least three agents and a unique efficient policy can have exhaustive IEWDS eliminate all efficient strategy profiles.This establishes failure even beyond the non-generic multiplicity concern.
A.3 A counterexample for every deterministic efficient policy
The paper constructs a three-agent finite environment showing that every deterministic efficient policy can fail under exhaustive IEWDS. Both policies generated by the sole efficient tie eliminate all efficient strategy profiles, independently of elimination order.
- Construction: A three-agent finite independent-private-values environment has two public decisions and exactly two deterministic efficient policies, both vulnerable to exhaustive IEWDS.The policies differ only in how they resolve the single efficient tie at (β, ℓ).
- Failure: Under either deterministic policy, every exhaustive IEWDS sequence eliminates all efficient strategy profiles, even when randomized reports enter dominance comparisons.The conclusion is independent of the elimination order.
- χY: For policy χY, successive dominance restrictions force pα ≥ 1/3, then q ≥ 1/2, then pα ≥ 2/3, and finally q = 1 before eliminating the remaining efficient reports.The sequence ends with α strictly dominating the payoff-equivalent report class n for true type γ.
- χZ: For policy χZ, dominance first removes g for true type α and h for true type ℓ, then forces g to dominate m for types β and γ and h to be removed for true type h.The surviving strategies satisfy bθ1(β) = bθ1(γ) = γ and bθ2(ℓ) = bθ2(h) = ℓ.
- Failure: At the true profile (α, h), every surviving strategy profile induces z even though y is uniquely efficient there.Thus the surviving profile is inefficient at a type profile without an efficient tie.
- Scope: The deterministic-policy construction does not establish failure for randomized tie-breaking, motivating a conjecture covering every efficient decision policy.The stronger claim remains stated as a conjecture rather than a proposition.
B VCG mechanisms and GU-VCG
The VCG family permits arbitrary Groves payment terms, including prior-free and reference-distribution-based choices. GU-VCG is introduced as a prior-dependent choice whose expected transfer is centered at zero for every fixed report profile.
- VCG family: Arbitrary Groves terms generate many payment rules within the VCG family, including the algebraically natural prior-free choice hi ≡ 0 and the Clarke pivot rule.These choices differ in how they specify the redistribution terms while preserving the Groves form.
- Pivot interpretation: A neutral report yielding zero payoff for every decision makes the chosen decision maximize other agents’ reported welfare and gives the pivot transfer equal to zero.The neutral report provides an operational interpretation of the pivot payment under this condition.
- Reference distributions: A reference distribution ν can select a VCG member ex ante, and the resulting mechanism remains dominant-strategy truthful even when ν differs from the true distribution or types are dependent.Prior dependence in selecting the rule does not remove dominant-strategy implementation.
- Prior-dependent rules: The paper considers prior-dependent choices based on a product reference distribution, including the conditionally centered VCG rule and GU-VCG.These rules replace the original prior with a reference distribution ν in the relevant construction.
- Prior-dependent rules: For every fixed report profile of the other agents, the conditionally centered rule has expected transfer zero over the reference distribution νi.This centering property is stated for the first prior-dependent choice.
B.1 The GU-VCG mechanism
GU-VCG preserves dominant-strategy truthfulness and individual utility guarantees, but its GUE property requires correct calibration and restricted information sharing. Unlike TU-GUM, it is not budget-balanced, so unrestricted reporting can support profitable collective deviations.
- Mechanism properties: GU-VCG remains a Groves mechanism because its adjustment depends only on other agents’ reports, preserving dominant-strategy truthfulness for any reference distribution.The mechanism is not budget-balanced.
- Restricted GUE property: Correct calibration and independence of other agents’ reports from an agent’s type are required for GU-VCG to be a GUE implementation.Under these conditions, truthful reporting maximizes total expected utility and induces the efficient decision policy.
- Restricted GUE property: The reporting restriction permits ex-ante coordination and common randomization but excludes conditioning reports on another agent’s realized type.This informational boundary is what allows guaranteed utilities to constrain every admissible strategy profile.
- Related construction: For two agents, GU-VCG coincides up to agent-specific additive constants with Zik’s externality-free construction.This correspondence is stated for the two-agent case.
- Comparison with TU-GUM: GU-VCG and TU-GUM provide the same individual utility guarantees in the standard private-type game, but only TU-GUM combines them with budget balance.GU-VCG is therefore less robust as a GUE mechanism.
B.2 The three-agent example
The three-agent example makes GU-VCG’s guarantees and limitations concrete. It matches TU-GUM’s individual guarantees under the informational restriction, but nonzero transfer sums permit a coalition with shared types to improve aggregate utility.
- VCG family: The symmetric VCG family is parameterized by three constants a, b, c, with transfer patterns determined by whether other reports are equal or mixed.The mixed-report case changes the second transfer from b to b + 4.
- Mechanism comparison: GU-VCG and symmetrized TU-GUM have identical utility rows under the informational restriction, while GU-VCG transfer sums are 9, −5, 1, and 3 across Table 7’s columns.The identical rows reflect common individual utility guarantees, not budget balance.
- Coalitional deviation: If the grand coalition shares realized types, it can coordinate reports that preserve the decision while changing transfers from zero expected value to positive transfers for every agent.The deviation reports −6 when at most one type is 10 and 10 otherwise.
- Coalitional deviation: The resulting deviation shows that GU-VCG’s GUE property, and its implied collusion-proofness, holds only when agents cannot condition reports on another agent’s realized type.Truthful reporting gives expected total utility 9, equal to the sum of the three guarantees.
C The three-agent social choice example in the Project Management Mechanism
The Project Management Mechanism embeds the three-agent example and reproduces fixed-order TU-GUM through sequential scalar announcements. Truthful offers guarantee the agents’ utilities, forcing the principal’s maximin utility to zero while implementing the efficient outcome.
- Embedding the example: The construction reproduces fixed-order TU-GUM for order 1, 2, 3, rather than the symmetrized payment rule.It embeds the three-agent social choice example in the Project Management Mechanism.
- Embedding the example: Each agent’s type is represented by an equiprobable private chance event, with contractible result spaces encoding the social choice component.The principal’s payoff is zero, while the social choice component is precisely the decision x.
- Truthful contract offer: The truthful contract offer reduces the principal’s relevant choices to a one-parameter family of scalar announcements, without characterizing every admissible protocol pointwise.The reduction follows from discarding options that are never worth choosing for the principal.
- Truthful contract offer: Immediately before requesting an agent’s report, the principal announces a scalar a, after which the report and selected outcome determine the agent’s transfer.The scalar announcement, report, and subsequent selection rule are contractible components of the protocol.
- Reproducing TU-GUM: Assigning a scalar to each earlier-report history and fixing it before the next report reproduces the fixed-order TU-GUM transfer vector at every report profile.The example verifies this by matching transfers for agent 2 and then checking the remaining rows.
- Maximin conclusion: Truthful strategies guarantee each agent expected utility at least 3 against any principal and other-agent strategies, so their combined utility is at least 9.Because transfers cancel and expected total payoff cannot exceed 9, the principal cannot guarantee more than 0.
- Maximin conclusion: The scalar strategy gives the principal utility 0 at every report profile and is therefore maximin, while truthful reporting generates the efficient TU-GUM outcome.The sequential scalar construction does not represent the symmetrized rule because early transfers may depend on later reports.