Mingyu Guo

AAAI Conference 2026 Short Paper

Behavioral-Similarity and Clustering-Based Methods for Static Graph Estimation in Hybrid GNNs (Student Abstract)

• Ryusei Otani
• Keichi Namikoshi
• Yuko Sakurai
• Mingyu Guo
• Satoshi Oyama

In this study, we propose two methods to estimate static graphs from a single dynamic graph and integrate them into hybrid Graph Neural Networks (GNNs), which combine long-term static structure with transient dynamic interactions. Since static graphs are often unavailable and attributes may be difficult to use at scale or under privacy constraints, we introduce: (i) a “behavioral similarity” estimator based on normalized co-occurrence, which requires no attributes, and (ii) an attribute-aware K-means + k-NN estimator that is more efficient than cosine similarity. Experiments on multiple real-world datasets show that both methods consistently improve predictive accuracy and training efficiency, underscoring the importance of static graph choice in hybrid GNNs.

AAAI Conference 2026 Conference Paper

On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting

• Ratip Emin Berker
• Emanuel Tewolde
• Vincent Conitzer
• Mingyu Guo
• Marijn Heule
• Lirong Xia

Core stability is a natural and well-studied notion for group fairness in multi-winner voting, where the task is to select a committee from a pool of candidates. We study the setting where voters either approve or disapprove of each candidate; here, it remains a major open problem whether a core-stable committee always exists. In this work, we develop an approach based on mixed-integer linear programming for deciding whether and when core-stable committees are guaranteed to exist. In contrast to SAT-based approaches popular in computational social choice, our method can produce proofs for a specific number of candidates independent of the number of voters. In addition to these computational gains, our program lends itself to a novel duality-based reformulation of the core stability problem, from which we obtain new existence results in special cases. Further, we use our framework to reveal previously unknown relationships between core stability and other desirable properties, such as notions of priceability.

IJCAI Conference 2025 Conference Paper

Adaptive Wizard for Removing Cross-Tier Misconfigurations in Active Directory

• Huy Q. Ngo
• Mingyu Guo
• Hung X. Nguyen

Security vulnerabilities in Windows Active Directory (AD) systems are typically modeled using an attack graph and hardening AD systems involves an iterative workflow: security teams propose an edge to remove, and IT operations teams manually review these fixes before implementing the removal. As verification requires significant manual effort, we formulate an Adaptive Path Removal Problem to minimize the number of steps in this iterative removal process. In our model, a wizard proposes an attack path in each step and presents it as a set of multiple-choice options to the IT admin. The IT admin then selects one edge from the proposed set to remove. This process continues until the target t is disconnected from source s or the number of proposed paths reaches B. The model aims to optimize the human effort by minimizing the expected number of interactions between the IT admin and the security wizard. We first prove that the problem is #P-hard. We then propose a set of solutions including an exact algorithm, an approximate algorithm, and several scalable heuristics. Our best heuristic, called DPR, can operate effectively on larger-scale graphs compared to the exact algorithm and consistently outperforms the approximate algorithm across all graphs. We verify the effectiveness of our algorithms on several synthetic AD graphs and an AD attack graph collected from a real organization.

NeurIPS Conference 2025 Conference Paper

Can Dependencies Induced by LLM-Agent Workflows Be Trusted?

• Yu Yao
• Yiliao (Lia) Song
• Yian Xie
• Mengdan Fan
• Mingyu Guo
• Tongliang Liu

LLM-agent systems often decompose high-level objectives into subtask dependency graphs, assuming that each subtask’s output is reliable and conditionally independent of others given its parent responses. However, this assumption frequently breaks during execution, as ground-truth responses are inaccessible, leading to inter-agent misalignment—failures caused by inconsistencies and coordination breakdowns among agents. To address this, we propose SeqCV, a dynamic framework for reliable execution under violated conditional independence. SeqCV executes subtasks sequentially, each conditioned on all prior verified responses, and performs consistency checks immediately after agents generate short token sequences. At each checkpoint, a token sequence is accepted only if it represents shared knowledge consistently supported across diverse LLM models; otherwise, it is discarded, triggering recursive subtask decomposition for finer-grained reasoning. Despite its sequential nature, SeqCV avoids repeated corrections on the same misalignment and achieves higher effective throughput than parallel pipelines. Across multiple reasoning and coordination tasks, SeqCV improves accuracy by up to 30\% over existing LLM-agent systems. Code is available at https: //github. com/tmllab/2025 NeurIPS SeqCV.

AAAI Conference 2024 Conference Paper

Limited Query Graph Connectivity Test

• Mingyu Guo
• Jialiang Li
• Aneta Neumann
• Frank Neumann
• Hung Nguyen

We propose a combinatorial optimisation model called Limited Query Graph Connectivity Test. We consider a graph whose edges have two possible states (On/Off). The edges' states are hidden initially. We could query an edge to reveal its state. Given a source s and a destination t, we aim to test s−t connectivity by identifying either a path (consisting of only On edges) or a cut (consisting of only Off edges). We are limited to B queries, after which we stop regardless of whether graph connectivity is established. We aim to design a query policy that minimizes the expected number of queries. Our model is mainly motivated by a cyber security use case where we need to establish whether attack paths exist in a given network, between a source (i.e., a compromised user node) and a destination (i.e., a high-privilege admin node). Edge query is resolved by manual effort from the IT admin, which is the motivation behind query minimization. Our model is highly related to Stochastic Boolean Function Evaluation (SBFE). There are two existing exact algorithms for SBFE that are prohibitively expensive. We propose a signifcantly more scalable exact algorithm. While previous exact algorithms only scale for trivial graphs (i.e., past works experimented on at most 20 edges), we empirically demonstrate that our algorithm is scalable for a wide range of much larger practical graphs (i.e., graphs representing Windows domain networks with tens of thousands of edges). We also propose three heuristics. Our best-performing heuristic is via limiting the planning horizon of the exact algorithm. The other two are via reinforcement learning (RL) and Monte Carlo tree search (MCTS). We also derive an algorithm for computing the performance lower bound. Experimentally, we show that all our heuristics are near optimal. The heuristic building on the exact algorithm outperforms all other heuristics, surpassing RL, MCTS and eight existing heuristics ported from SBFE and related literature.

JAAMAS Journal 2024 Journal Article

Mechanism design for public projects via three machine learning based approaches

• Mingyu Guo
• Diksha Goel
• Muhammad Ali Babar

Abstract We study mechanism design for nonexcludable and excludable binary public project problems. Our aim is to maximize the expected number of consumers and the expected agents’ welfare. We first show that for the nonexcludable public project model, there is no need for machine learning based mechanism design. We identify a sufficient condition on the prior distribution for the existing conservative equal costs mechanism to be the optimal strategy-proof and individually rational mechanism. For general distributions, we propose a dynamic program that solves for the optimal mechanism. For the excludable public project model, we identify a similar sufficient condition for the existing serial cost sharing mechanism to be optimal for 2 and 3 agents. We derive a numerical upper bound and use it to show that for several common distributions, the serial cost sharing mechanism is close to optimality. The serial cost sharing mechanism is not optimal in general. We propose three machine learning based approaches for designing better performing mechanisms. We focus on the family of largest unanimous mechanisms, which characterizes all strategy-proof and individually rational mechanisms for the excludable public project model. A largest unanimous mechanism describes an iterative mechanism, which is defined by an exponential number of mechanism parameters. Our first approach describes the largest unanimous mechanism family using a neural network and training is carried out by minimizing a cost function that combines the mechanism design objective and the constraint violation penalty. We interpret the largest unanimous mechanisms as price-oriented rationing-free (PORF) mechanisms, which enables us to move the mechanisms’ iterative decision making off the neural network, to a separate simulation process, therefore avoiding the vanishing gradient problem. We also feed the prior distribution’s analytical form into the cost function to achieve high-quality gradients for efficient training. Our second approach treats the mechanism design task as a Markov Decision Process with an exponential number of states. During the Markov decision process, the non-consumers are gradually removed from the system. We train multiple neural networks, each for a different number of remaining agents, to learn the optimal value function on the states. Training is carried out by supervised learning toward a set of manually prepared base cases and the Bellman equation. Our third approach is based on reinforcement learning for a Partially Observable Markov Decision Process. Each RL episode randomly draws a type profile, which is hidden from the RL agent (mechanism designer). The RL agent only observes which cost share offers have been accepted under the largest unanimous mechanism under discussion. We use a continuous action space reinforcement learning approach to adjust the offer policy (i. e. , adjust mechanism parameters). Lastly, our first two approaches use “supervision to manual mechanisms” as a systematic way for network initialization, which is potentially valuable for machine learning based mechanism design in general.

AAAI Conference 2024 Conference Paper

Worst-Case VCG Redistribution Mechanism Design Based on the Lottery Ticket Hypothesis

• Mingyu Guo

We study worst-case VCG redistribution mechanism design for the public project problem. The mechanism design task comes down to designing a payment function that maximizes the worst-case allocative efficiency ratio. We use a multilayer perceptron (MLP) with ReLU activation to model the payment function and use mixed integer programming (MIP) to solve for the worst-case type profiles that maximally violate the mechanism design constraints. We collect these worst-case type profiles and use them as training samples to train toward better worst-case mechanisms. In practice, we require a tiny neural network structure for the above approach to scale. The Lottery Ticket Hypothesis states that a large network is likely to contain a "winning ticket" -- a much smaller subnetwork that "won the initialization lottery", which makes its training particularly effective. Motivated by this hypothesis, we train a large network and prune it into a tiny subnetwork. We run MIP-based worst-case training on the drawn subnetwork and evaluate the resulting mechanism's worst-case performance. If the subnetwork does not achieve good worst-case performance, then we record the type profiles that cause the current draw to be bad. To draw again, we restore the large network to its initial weights and prune using recorded type profiles from earlier draws, therefore avoiding drawing the same ticket twice. We expect to eventually encounter a tiny subnetwork that leads to effective training for our worst-case mechanism design task. Lastly, a by-product of multiple ticket draws is an ensemble of mechanisms with different worst cases, which improves the worst-case performance further. Using our approach, we find previously unknown optimal mechanisms for up to 5 agents. Our results confirm the tightness of existing theoretical upper bounds. For up to 20 agents, we derive significantly improved worst-case mechanisms, surpassing a long list of existing manual results.

IJCAI Conference 2023 Conference Paper

Diverse Approximations for Monotone Submodular Maximization Problems with a Matroid Constraint

• Anh Viet Do
• Mingyu Guo
• Aneta Neumann
• Frank Neumann

Finding diverse solutions to optimization problems has been of practical interest for several decades, and recently enjoyed increasing attention in research. While submodular optimization has been rigorously studied in many fields, its diverse solutions extension has not. In this study, we consider the most basic variants of submodular optimization, and propose two simple greedy algorithms, which are known to be effective at maximizing monotone submodular functions. These are equipped with parameters that control the trade-off between objective and diversity. Our theoretical contribution shows their approximation guarantees in both objective value and diversity, as functions of their respective parameters. Our experimental investigation with maximum vertex coverage instances demonstrates their empirical differences in terms of objective-diversity trade-offs.

AAMAS Conference 2023 Conference Paper

Near Optimal Strategies for Honeypots Placement in Dynamic and Large Active Directory Networks

• Huy Q. Ngo
• Mingyu Guo
• Hung Nguyen

Active Directory (AD) is the default security management system for Windows domain networks and is the target of many recent cyber attacks. We study a Stackelberg game between an attacker and a defender on large Active Directory (AD) attack graphs, where the defender employs a set of honeypots to stop the attacker from reaching high value targets. Contrary to existing works that focus on small and static attack graphs, AD graphs typically contain hundreds of thousands of nodes/edges and constantly change over time. We show that the optimal honeypot placement problem is NP-hard even for static graphs and develop a tree decomposition method to derive an optimal deployment strategy and a mixedinteger programming (MIP) formulation to scale to large graphs. We observed that the optimal blocking plan for static graphs performs poorly for dynamic graphs. To handle dynamic graphs, we re-design the mixed-integer programming formulation by combining m MIP (dyMIP(m)) instances. We prove a performance lower-bound on the optimal blocking strategy for dynamic graphs and show that our dyMIP(m) algorithm produces near optimal results.

AAAI Conference 2023 Conference Paper

Scalable Edge Blocking Algorithms for Defending Active Directory Style Attack Graphs

• Mingyu Guo
• Max Ward
• Aneta Neumann
• Frank Neumann
• Hung Nguyen

Active Directory (AD) is the default security management system for Windows domain networks. An AD environment naturally describes an attack graph where nodes represent computers/accounts/security groups, and edges represent existing accesses/known exploits that allow the attacker to gain access from one node to another. Motivated by practical AD use cases, we study a Stackelberg game between one attacker and one defender. There are multiple entry nodes for the attacker to choose from and there is a single target (Domain Admin). Every edge has a failure rate. The attacker chooses the attack path with the maximum success rate. The defender can block a limited number of edges (i.e., revoke accesses) from a set of blockable edges, limited by budget. The defender's aim is to minimize the attacker's success rate. We exploit the tree-likeness of practical AD graphs to design scalable algorithms. We propose two novel methods that combine theoretical fixed parameter analysis and practical optimisation techniques. For graphs with small tree widths, we propose a tree decomposition based dynamic program. We then propose a general method for converting tree decomposition based dynamic programs to reinforcement learning environments, which leads to an anytime algorithm that scales better, but loses the optimality guarantee. For graphs with small numbers of non-splitting paths (a parameter we invent specifically for AD graphs), we propose a kernelization technique that significantly downsizes the model, which is then solved via mixed-integer programming. Experimentally, our algorithms scale to handle synthetic AD graphs with tens of thousands of nodes.

AAAI Conference 2022 Conference Paper

Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs

• Mingyu Guo
• Jialiang Li
• Aneta Neumann
• Frank Neumann
• Hung Nguyen

Active Directory is the default security management system for Windows domain networks. We study the shortest path edge interdiction problem for defending Active Directory style attack graphs. The problem is formulated as a Stackelberg game between one defender and one attacker. The attack graph contains one destination node and multiple entry nodes. The attacker’s entry node is chosen by nature. The defender chooses to block a set of edges limited by his budget. The attacker then picks the shortest unblocked attack path. The defender aims to maximize the expected shortest path length for the attacker, where the expectation is taken over entry nodes. We observe that practical Active Directory attack graphs have small maximum attack path lengths and are structurally close to trees. We first show that even if the maximum attack path length is a constant, the problem is still W[1]-hard with respect to the defender’s budget. Having a small maximum attack path length and a small budget is not enough to design fixed-parameter algorithms. If we further assume that the number of entry nodes is small, then we derive a fixedparameter tractable algorithm. We then propose two other fixed-parameter algorithms by exploiting the tree-like features. One is based on tree decomposition and requires a small tree width. The other assumes a small number of splitting nodes (nodes with multiple outgoing edges). Finally, the last algorithm is converted into a graph convolutional neural network based heuristic, which scales to larger graphs with more splitting nodes.

JAAMAS Journal 2021 Journal Article

An asymptotically optimal VCG redistribution mechanism for the public project problem

• Mingyu Guo

Abstract We study the classic public project problem, where the agents decide whether or not to build a non-excludable public project. We focus on efficient, strategy-proof, and weakly budget-balanced mechanisms (VCG redistribution mechanisms). Our aim is to maximize the worst-case efficiency ratio—the worst-case ratio between the achieved total utility and the first-best maximum total utility. Previous studies have identified an optimal mechanism for 3 agents. Unfortunately, no optimal mechanisms have been identified for more than 3 agents. We propose an automated mechanism design approach that is capable of handling worst-case objectives. With its help, we identify a different optimal mechanism for 3 agents. For more agents, we identify mechanisms with better worst-case efficiency ratios than previous results. Using a dimension reduction technique, we extend the newly identified optimal mechanism for 3 agents to n agents. The resulting mechanism’s worst-case efficiency ratio equals \(\frac{n+1}{2n}\). In comparison, the best previously known worst-case efficiency ratio equals 0. 102 asymptotically. We then derive an asymptotically optimal mechanism under a minor technical assumption: we assume the agents’ valuations are rational numbers with bounded denominators. Previous studies conjectured that the optimal asymptotic worst-case efficiency ratio equals 1. We confirm this conjecture.

JAAMAS Journal 2021 Journal Article

Gini index based initial coin offering mechanism

• Mingyu Guo
• Zhenghui Wang
• Yuko Sakurai

Abstract As a fundraising method, Initial Coin Offering (ICO) has raised billions of dollars for thousands of startups. Existing ICO mechanisms place more emphasis on the short-term benefits of maximal fundraising while ignoring the problem of unbalanced token allocation, which negatively impacts subsequent fundraising and has bad effects on introducing new investors and resources. We propose a new ICO mechanism which uses the concept of Gini index for the very first time as a mechanism design constraint to control allocation inequality. Our mechanism has an elegant and straightforward structure, which makes it explainable. It allows the agents to modify their bids as a price discovery process, while limiting the bids of whales. Under natural technical assumptions, we show that under our mechanism most agents have simple dominant strategies and the equilibrium revenue approaches the optimal revenue asymptotically in the number of agents. We verify our mechanism using real ICO dataset we collected, and confirm that our mechanism performs well in terms of both allocation fairness and revenue.

AAMAS Conference 2021 Conference Paper

Mechanism Design for Public Projects via Neural Networks

• Guanhua Wang
• Runqi Guo
• Yuko Sakurai
• Muhammad Ali Babar
• Mingyu Guo

We study mechanism design for nonexcludable and excludable binary public project problems. We aim to maximize the expected number of consumers and the expected agents’ welfare. For the nonexcludable public project model, we identify a sufficient condition on the prior distribution for the conservative equal costs mechanism to be the optimal strategy-proof and individually rational mechanism. For general distributions, we propose a dynamic program that solves for the optimal mechanism. For the excludable public project model, we identify a similar sufficient condition for the serial cost sharing mechanism to be optimal for 2 and 3 agents. We derive a numerical upper bound. Experiments show that for several common distributions, the serial cost sharing mechanism is close to optimality. The serial cost sharing mechanism is not optimal in general. We design better performing mechanisms via neural networks. Our approach involves several technical innovations that can be applied to mechanism design in general. We interpret the mechanisms as price-oriented rationing-free (PORF) mechanisms, which enables us to move the mechanism’s complex (e. g. , iterative) decision making off the neural network, to a separate simulation process. We feed the prior distribution’s analytical form into the cost function to provide high-quality gradients for efficient training. We use supervision to manual mechanisms as a systematic way for initialization. Our approach of “supervision and then gradient descent” is effective for improving manual mechanisms’ performances. It is also effective for fixing constraint violations for heuristic-based mechanisms that are infeasible.

JAAMAS Journal 2021 Journal Article

Revenue maximizing markets for zero-day exploits

• Mingyu Guo
• Guanhua Wang
• Muhammad Ali Babar

Abstract Markets for zero-day exploits (software vulnerabilities unknown to the software vendor) have a long history and a growing popularity. We study these markets from a revenue-maximizing mechanism design perspective. We first propose a theoretical model for zero-day exploits markets. In our model, one exploit is being sold to multiple buyers. There are two kinds of buyers, which we call the defenders and the offenders. The defenders are buyers who buy vulnerabilities in order to fix them ( e. g. , software vendors). The offenders, on the other hand, are buyers who intend to utilize the exploits ( e. g. , national security agencies and police). We study the problem of selling one zero-day exploit to multiple defenders and offenders. Our model has a few unique features that make it different from single-item auctions. First, an exploit is a piece of information, so one exploit can be sold to multiple buyers. Second, buyers have externalities. If any defender wins, then the exploit becomes worthless to the offenders. Third, if the auctioneer discloses the details of the exploit to the buyers before the auction, then they may leave with the information without paying. On the other hand, if the auctioneer does not disclose enough details, then the buyers cannot determine how valuable the exploit is. Considering the above, our proposed mechanism discloses the details of the exploit to all offenders at the beginning of the auction. The defenders will receive the information slightly delayed. The offenders bid to prolong the delay and the defenders bid to shorten the delay. We derive the optimal mechanism for single-parameter valuations. For general valuations, we propose three numerical solution techniques. One is based on iterative linear programming and the other two are based on neural networks and evolutionary computation.

IJCAI Conference 2019 Conference Paper

An Asymptotically Optimal VCG Redistribution Mechanism for the Public Project Problem

• Mingyu Guo

We study the classic public project problem, where a group of agents need to decide whether or not to build a non-excludable public project. We focus on efficient, strategy-proof, and weakly budget-balanced mechanisms (VCG redistribution mechanisms). Our aim is to maximize the worst-case efficiency ratio --- the worst-case ratio between the achieved total utility and the first-best maximum total utility. Previous studies have identified the optimal mechanism for 3 agents. It was also conjectured that the worst-case efficiency ratio approaches 1 asymptotically as the number of agents approaches infinity. Unfortunately, no optimal mechanisms have been identified for cases with more than 3 agents. We propose an asymptotically optimal mechanism, which achieves a worst-case efficiency ratio of 1, under a minor technical assumption: we assume the agents' valuations are rational numbers with bounded denominators. We also show that if the agents' valuations are drawn from identical and independent distributions, our mechanism's efficiency ratio equals 1 with probability approaching 1 asymptotically. Our results significantly improve on previous results. The best previously known asymptotic worst-case efficiency ratio is 0. 102. For non-asymptotic cases, our mechanisms also achieve better ratios than all previous results.

AIJ Journal 2014 Journal Article

Better redistribution with inefficient allocation in multi-unit auctions

• Mingyu Guo
• Vincent Conitzer

AAAI Conference 2014 Conference Paper

Increasing VCG Revenue by Decreasing the Quality of Items

• Mingyu Guo
• Argyrios Deligkas
• Rahul Savani

The VCG mechanism is the standard method to incentivize bidders in combinatorial auctions to bid truthfully. Under the VCG mechanism, the auctioneer can sometimes increase revenue by “burning” items. We study this phenomenon in a setting where items are described by a number of attributes. The value of an attribute corresponds to a quality level, and bidders’ valuations are non-decreasing in the quality levels. In addition to burning items, we allow the auctioneer to present some of the attributes as lower quality than they actually are. We consider the following two revenue maximization problems under VCG: finding an optimal way to mark down items by reducing their quality levels, and finding an optimal set of items to burn. We study the effect of the following parameters on the computational complexity of these two problems: the number of attributes, the number of quality levels per attribute, and the complexity of the bidders’ valuation functions. Bidders have unit demand, so VCG’s outcome can be computed in polynomial time, and the valuation functions we consider are step functions that are non-decreasing with the quality levels. We prove that both problems are NP-hard even in the following three simple settings: a) four attributes, arbitrarily many quality levels per attribute, and single-step valuation functions, b) arbitrarily many attributes, two quality levels per attribute, and single-step valuation functions, and c) one attribute, arbitrarily many quality-levels, and multi-step valuation functions. For the case where items have only one attribute, and every bidder has a single-step valuation (zero below some quality threshold), we show that both problems can be solved in polynomial-time using a dynamic programming approach. For this case, we also quantify how much better marking down is than item burning, and we compare the revenue of both approaches with computational experiments.

IJCAI Conference 2013 Conference Paper

Revenue Maximization via Hiding Item Attributes

• Mingyu Guo
• Argyrios Deligkas

We study probabilistic single-item second-price auctions where the item is characterized by a set of attributes. The auctioneer knows the actual instantiation of all the attributes, but he may choose to reveal only a subset of these attributes to the bidders. Our model is an abstraction of the following Ad auction scenario. The website (auctioneer) knows the demographic information of its impressions, and this information is in terms of a list of attributes (e. g. , age, gender, country of location). The website may hide certain attributes from its advertisers (bidders) in order to create thicker market, which may lead to higher revenue. We study how to hide attributes in an optimal way. We show that it is NP-hard to compute the optimal attribute hiding scheme. We then derive a polynomial-time solvable upper bound on the optimal revenue. Finally, we propose two heuristicbased attribute hiding schemes. Experiments show that revenue achieved by these schemes is close to the upper bound.

AAMAS Conference 2012 Conference Paper

Worst-Case Optimal Redistribution of VCG Payments in Heterogeneous-Item Auctions with Unit Demand

• Mingyu Guo

Many important problems in multiagent systems involve the allocation of multiple resources among the agents. For resource allocation problems, the well-known VCG mechanism satisfies a list of desired properties, including efficiency, strategy-proofness, individual rationality, and the non-deficit property. However, VCG is generally not budget-balanced. Under VCG, agents pay the VCG payments, which reduces social welfare. To offset the loss of social welfare due to the VCG payments, VCG redistribution mechanisms were introduced. These mechanisms aim to redistribute as much VCG payments back to the agents as possible, while maintaining the aforementioned desired properties of the VCG mechanism. We continue the search for worst-case optimal VCG redistribution mechanisms -- mechanisms that maximize the fraction of total VCG payment redistributed in the worst case. Previously, a worst-case optimal VCG redistribution mechanism (denoted by WCO) was characterized for multi-unit auctions with nonincreasing marginal values. Later, WCO was generalized to settings involving heterogeneous items, resulting in the HETERO mechanism. This \emph{conjectured} that HETERO is feasible and worst-case optimal for heterogeneous-item auctions with unit demand. In this paper, we propose a more natural way to generalize the WCO mechanism. We prove that our generalized mechanism, though represented differently, actually coincides with HETERO. Based on this new representation of HETERO, we prove that HETERO is indeed feasible and worst-case optimal in heterogeneous-item auctions with unit demand. Finally, we conjecture that HETERO remains feasible and worst-case optimal in the even more general setting of combinatorial auctions with gross substitutes.

AAAI Conference 2011 Conference Paper

VCG Redistribution with Gross Substitutes

• Mingyu Guo

For the problem of allocating resources among multiple strategic agents, the well-known Vickrey-Clarke-Groves (VCG) mechanism is efficient, strategy-proof, and it never incurs a deficit. However, in general, under the VCG mechanism, payments flow out of the system of agents, which reduces the agents’ utilities. VCG redistribution mechanisms aim to return as much of the VCG payments as possible back to the agents, without affecting the desirable properties of the VCG mechanism. Most previous research on VCG redistribution mechanisms has focused on settings with homogeneous items and/or settings with unit-demand agents. In this paper, we study VCG redistribution mechanisms in the more general setting of combinatorial auctions. We show that when the gross substitutes condition holds, we are able to design mechanisms that guarantee to redistribute a large fraction of the VCG payments.

AAAI Conference 2010 Conference Paper

Computationally Feasible Automated Mechanism Design: General Approach and Case Studies

• Mingyu Guo
• Vincent Conitzer

AAMAS Conference 2010 Conference Paper

False-Name-Proofness with Bid Withdrawal

• Mingyu Guo
• Vincent Conitzer

We study a more powerful variant of false-name manipulation in Internet auctions: an agent can submit multiple false-name bids, butthen, once the allocation and payments have been decided, withdraw some of her false-name identities (have some of her false-name identities refuse to pay). While these withdrawn identitieswill not obtain the items they won, their initial presence may havebeen beneficial to the agent's other identities. We define a mechanism to be false-name-proof with withdrawal (FNPW) if the aforementioned manipulation is never beneficial. FNPW is a strongercondition than false-name-proofness (FNP). We discuss the relation between FNP and FNPW in general combinatorial auction settings. We also propose the maximum marginalvalue item pricing (MMVIP) mechanism, which we prove is FNPW. (The full version contains a number of other results. )

AIJ Journal 2010 Journal Article

Optimal-in-expectation redistribution mechanisms

• Mingyu Guo
• Vincent Conitzer

AAMAS Conference 2010 Conference Paper

Strategy-proof Allocation of Multiple Items between Two Agents without Payments or Priors

• Mingyu Guo
• Vincent Conitzer

We investigate the problem of allocating items (private goods) amongcompeting agents in a setting that is both prior-free and payment-free. Specifically, we focus on allocating multiple heterogeneousitems between two agents with additive valuation functions. Ourobjective is to design strategy-proof mechanisms that are competitive against the most efficient (first-best) allocation. We introduce the family of linear increasing-price (LIP) mechanisms. TheLIP mechanisms are strategy-proof, prior-free, and payment-free, and they are exactly the increasing-price mechanisms satisfying astrong responsiveness property. We show how to solve for competitive mechanisms within the LIP family. For the case of two items, we find a LIP mechanism whose competitive ratio is near optimal(the achieved competitive ratio is $0. 828$, while any strategy-proofmechanism is at most $0. 841$-competitive). As the number of itemsgoes to infinity, we prove a negative result that any increasing-pricemechanism (linear or nonlinear) has a maximal competitive ratio of$0. 5$. Our results imply that in some cases, it is possible to designgood allocation mechanisms without payments and without priors.

AAMAS Conference 2010 Conference Paper

Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms

• Atsushi Iwasaki
• Vincent Conitzer
• Yoshifusa Omori
• Yuko Sakurai
• Taiki Todo
• Mingyu Guo
• Makoto Yokoo

This paper analyzes the worst-case efficiency ratio of false-name-proofcombinatorial auction mechanisms. False-name-proofness generalizesstrategy-proofness, by assuming that a bidder can submit multiple bidsunder fictitious identifiers. Even the well-known Vickrey-Clarke-Grovesmechanism is not false-name-proof. It has previously been shown thatthere is no false-name-proof mechanism that always achieves a Paretoefficient allocation. Hence, if false-name bids are possible, we need to sacrifice efficiency to some extent. This leaves the natural question of how much surplusmust be sacrificed. To answer this question, this paper focuses on worst-case analysis. Specifically, we consider thefraction of the Pareto-efficient surplus that we obtain, and try tomaximize this fraction in the worst case, under the constraint offalse-name-proofness. As far as we are aware, this is the first attempt to examine theworst-case efficiency of false-name-proof mechanisms. We show that the worst-case efficiency ratio of any false-name-proofmechanism that satisfies some apparently minor assumptions is atmost $2/(m+1)$ for auctions with $m$ different goods. We also observe that the worst-case efficiency ratioof existing false-name-proof mechanisms is generally $1/m$ or 0. Finally, we propose a novel mechanism, called the adaptive reserve price mechanism, which is false-name-proof when all bidders are single-minded, and its worst-case efficiency ratio is $2/(m+1)$, i. e. , optimal.

AAMAS Conference 2009 Conference Paper

Combinatorial Prediction Markets for Event Hierarchies

• Mingyu Guo
• David M. Pennock

We study combinatorial prediction markets where agents bet on the sum of values at any tree node in a hierarchy of events, for example the sum of page views among all the children within a web subdomain. We propose three expressive betting languages that seem natural, and analyze the complexity of pricing using Hanson’s logarithmic market scoring rule (LMSR) market maker. Sum of arbitrary subset (SAS) allows agents to bet on the weighted sum of an arbitrary subset of values. Sum with varying weights (SVW) allows agents to set their own weights in their bets but restricts them to only bet on subsets that correspond to tree nodes in a fixed hierarchy. We show that LMSR pricing is NP-hard for both SAS and SVW. Sum with predefined weights (SPW) also restricts bets to nodes in a hierarchy, but using predefined weights. We derive a polynomial time pricing algorithm for SPW. We discuss the algorithm’s generalization to other betting contexts, including betting on maximum/minimum and betting on the product of binary values. Finally, we describe a prototype we built to predict web site page views and discuss the implementation issues that arose.

AAMAS Conference 2008 Conference Paper

Optimal-in-Expectation Redistribution Mechanisms

• Mingyu Guo
• Vincent Conitzer

Many important problems in multiagent systems involve the allocation of multiple resources to multiple agents. If agents are selfinterested, they will lie about their valuations for the resources if they perceive this to be in their interest. The well-known VCG mechanism allocates the items efficiently, is incentive compatible (agents have no incentive to lie), and never runs a deficit. Nevertheless, the agents may have to make large payments to a party outside the system of agents, leading to decreased utility for the agents. Recent work has investigated the possibility of redistributing some of the payments back to the agents, without violating the other desirable properties of the VCG mechanism. We study multi-unit auctions with unit demand, for which previously a mechanism has been found that maximizes the worst-case redistribution percentage. In contrast, we assume that a prior distribution over the agents’ valuations is available, and try to maximize the expected total redistribution. We analytically solve for a mechanism that is optimal among linear redistribution mechanisms. The optimal linear mechanism is asymptotically optimal. We also propose discretization redistribution mechanisms. We show how to automatically solve for the optimal discretization redistribution mechanism for a given discretization step size, and show that the resulting mechanisms converge to optimality as the step size goes to zero. We also present experimental results showing that for auctions with many bidders, the optimal linear redistribution mechanism redistributes almost everything, whereas for auctions with few bidders, we can solve for the optimal discretization redistribution mechanism with a very small step size.

AAMAS Conference 2008 Conference Paper

Undominated VCG Redistribution Mechanisms

• Mingyu Guo
• Vincent Conitzer

Many important problems in multiagent systems can be seen as resource allocation problems. For such problems, the well-known Vickrey-Clarke-Groves (VCG) mechanism is efficient, incentive compatible, individually rational, and does not incur a deficit. However, the VCG mechanism is not (strongly) budget balanced: generally, the agents’ payments will sum to more than 0. Very recently, several mechanisms have been proposed that redistribute a significant percentage of the VCG payments back to the agents while maintaining the other properties. This increases the agents’ utilities. One redistribution mechanism dominates another if it always redistributes at least as much to each agent (and sometimes more). In this paper, we provide a characterization of undominated redistribution mechanisms. We also propose several techniques that take a dominated redistribution mechanism as input, and produce as output another redistribution mechanism that dominates the original. One technique immediately produces an undominated redistribution mechanism that is not necessarily anonymous. Another technique preserves anonymity, and repeated application results in an undominated redistribution mechanism in the limit. We show experimentally that these techniques improve the known redistribution mechanisms.