Arrow Research search

Author name cluster

Xiaohui Bei

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

37 papers
2 author rows

Possible papers

37

AAAI Conference 2025 Conference Paper

Optimal Auction Design for Mixed Bidders

  • Xiaohui Bei
  • Pinyan Lu
  • Zhiqi Wang
  • Tao Xiao
  • Xiang Yan

The predominant setting in classic auction theory considers bidders as utility maximizers (UMs), who aim to maximize quasi-linear utility functions. Recent autobidding strategies in online advertising have sparked interest in auction design with value maximizers (VMs), who aim to maximize the total value obtained. In this work, we investigate revenue-maximizing auction design for selling a single item to a mix of UMs and VMs. Crucially, we assume the UM/VM type is private information of a bidder. This shift to a multi-parameter domain complicates the design of incentive compatible mechanisms. Under this setting, we first characterize the optimal auction structure for auctions with a single bidder. We observe that the optimal auction moves gradually from a first-price auction to a Myerson auction as the probability of the bidder being a UM increases from 0 to 1. We also extend our study to multi-bidder setting and present an algorithm for deriving the optimal lookahead auction with multiple mixed types of bidders.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Welfare Loss in Connected Resource Allocation

  • Xiaohui Bei
  • Alexander Lam
  • Xinhang Lu
  • Warut Suksompong

We study the allocation of indivisible goods that form an undirected graph and investigate the worst-case welfare loss when requiring that each agent must receive a connected subgraph. Our focus is on both egalitarian and utilitarian welfare. Specifically, we introduce the concept of egalitarian (resp. , utilitarian) price of connectivity, which captures the worst-case ratio between the optimal egalitarian (resp. , utilitarian) welfare among all allocations and that among the connected allocations. We provide tight or asymptotically tight bounds on the price of connectivity for various large classes of graphs when there are two agents, and for paths, stars and cycles in the general case. Many of our results are supplemented with algorithms which find connected allocations with a welfare guarantee corresponding to the price of connectivity.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Approval-Based Voting with Mixed Goods

  • Xinhang Lu
  • Jannik Peters
  • Haris Aziz
  • Xiaohui Bei
  • Warut Suksompong

We consider a voting scenario in which the resource to be voted upon may consist of both indivisible and divisible goods. This generalizes both the well-studied model of multiwinner voting and the recently introduced model of cake sharing. Under approval votes, we propose two variants of the extended justified representation (EJR) notion from multiwinner voting, a stronger one called EJR for mixed goods (EJR-M) and a weaker one called EJR up to 1 (EJR-1). We extend three multiwinner voting rules to our setting—GreedyEJR, the method of equal shares (MES), and proportional approval voting (PAV)—and show that while all three generalizations satisfy EJR-1, only the first one provides EJR-M. In addition, we derive tight bounds on the proportionality degree implied by EJR-M and EJR-1, and investigate the proportionality degree of our proposed rules.

PDF Details DOI

UAI Conference 2022 Conference Paper

Proportional allocation of indivisible resources under ordinal and uncertain preferences

  • Zihao Li 0002
  • Xiaohui Bei
  • Zhenzhen Yan

We study a fair resource allocation problem with indivisible items. The agents’ preferences over items are assumed to be ordinal and have uncertainties. We adopt stochastic dominance proportionality as our fairness notion and study a sequence of problems related to finding allocations that are fair with a high probability. We provide complexity analysis for each problem and efficient algorithms for some problems. Finally, we propose several heuristic algorithms to find an allocation that is fair with the highest probability. We thoroughly evaluate the performance of the algorithms on both synthetic and real datasets.

Details

AAAI Conference 2022 Conference Paper

Real-Time Driver-Request Assignment in Ridesourcing

  • Hao Wang
  • Xiaohui Bei

Online on-demand ridesourcing service has played a huge role in transforming urban transportation. A central function in most on-demand ridesourcing platforms is to dynamically assign drivers to rider requests that could balance the request waiting times and the driver pick-up distances. To deal with the online nature of this problem, existing literature either divides the time horizon into short windows and applies a static offline assignment algorithm within each window or assumes a fully online setting that makes decisions for each request immediately upon its arrival. In this paper, we propose a more realistic model for the driver-request assignment that bridges the above two settings together. Our model allows the requests to wait after their arrival but assumes that they may leave at any time following a quitting function. Under this model, we design an efficient algorithm for assigning available drivers to requests in real-time. Our algorithm is able to incorporate future estimated driver arrivals into consideration and make strategic waiting and matching decisions that could balance the waiting time and pick-up distance of the assignment. We prove that our algorithm is optimal ex-ante in the single-request setting, and demonstrate its effectiveness in the general multirequest setting through experiments on both synthetic and real-world datasets.

PDF Details

AAAI Conference 2022 Conference Paper

The Secretary Problem with Competing Employers on Random Edge Arrivals

  • Xiaohui Bei
  • Shengyu Zhang

The classic secretary problem concerns the problem of an employer facing a random sequence of candidates and making online hiring decisions to try to hire the best candidate. In this paper, we study a game-theoretic generalization of the secretary problem where a set of employers compete with each other to hire the best candidate. Different from previous secretary market models, our model assumes that the sequence of candidates arriving at each employer is uniformly random but independent from other sequences. We consider two versions of this secretary game where employers can have adaptive or non-adaptive strategies, and provide characterizations of the best response and Nash equilibrium of each game.

PDF Details

AAAI Conference 2022 Conference Paper

Truthful Cake Sharing

  • Xiaohui Bei
  • Xinhang Lu
  • Warut Suksompong

The classic cake cutting problem concerns the fair allocation of a heterogeneous resource among interested agents. In this paper, we study a public goods variant of the problem, where instead of competing with one another for the cake, the agents all share the same subset of the cake which must be chosen subject to a length constraint. We focus on the design of truthful and fair mechanisms in the presence of strategic agents who have piecewise uniform utilities over the cake. On the one hand, we show that the leximin solution is truthful and moreover maximizes an egalitarian welfare measure among all truthful and position oblivious mechanisms. On the other hand, we demonstrate that the maximum Nash welfare solution is truthful for two agents but not in general. Our results assume that mechanisms can block each agent from accessing parts that the agent does not claim to desire; we provide an impossibility result when blocking is not allowed.

PDF Details

JAAMAS Journal 2021 Journal Article

Candidate selections with proportional fairness constraints

  • Xiaohui Bei
  • Shengxin Liu
  • Hongao Wang

Abstract Selecting a subset of candidates with various attributes under fairness constraints has been attracting considerable attention from the AI community, with applications ranging from school admissions to committee selections. The fairness constraints are usually captured by absolute upper bounds and/or lower bounds on the number of selected candidates in specific attributes. In many scenarios, however, the total number of selected candidates is not predetermined. It is, therefore, more natural to express these fairness constraints in terms of proportions of the final selection size. In this paper, we study the proportional candidate selection problem, where the goal is to select a subset of candidates with maximum cardinality while meeting certain proportional fairness constraints. We first analyze the computational complexity of the problem and show strong inapproximability results. Next, we investigate the algorithmic aspects of the problem in two directions. First, by treating the proportional fairness constraints as soft constraints, we devise two polynomial-time algorithms that could return (near) optimal solutions with bounded violations on each fairness constraint. Second, we design an exact algorithm with a fast running time in practice. Simulations based on both synthetic and publicly available data confirm the effectiveness and efficiency of our proposed algorithms.

Details DOI

AAAI Conference 2021 Conference Paper

Dividing a Graphical Cake

  • Xiaohui Bei
  • Warut Suksompong

We consider the classical cake-cutting problem where we wish to fairly divide a heterogeneous resource, often modeled as a cake, among interested agents. Work on the subject typically assumes that the cake is represented by an interval. In this paper, we introduce a generalized setting where the cake can be in the form of the set of edges of an undirected graph, allowing us to model the division of road networks. Unlike in the canonical setting, common fairness criteria such as proportionality cannot always be satisfied in our setting if each agent must receive a connected subgraph. We determine the optimal approximation of proportionality that can be obtained for any number of agents with arbitrary valuations, and exhibit a tight guarantee for each graph in the case of two agents. In addition, when more than one connected piece per agent is allowed, we establish the best egalitarian welfare guarantee for each total number of connected pieces. We also study a number of variants and extensions, including when approximate equitability is considered, or when the item to be divided is undesirable (also known as chore division).

PDF Details

ICML Conference 2021 Conference Paper

Learning Optimal Auctions with Correlated Valuations from Samples

  • Chunxue Yang
  • Xiaohui Bei

In single-item auction design, it is well known due to Cremer and McLean that when bidders’ valuations are drawn from a correlated prior distribution, the auctioneer can extract full social surplus as revenue. However, in most real-world applications, the prior is usually unknown and can only be learned from historical data. In this work, we investigate the robustness of the optimal auction with correlated valuations via sample complexity analysis. We prove upper and lower bounds on the number of samples from the unknown prior required to learn a (1-epsilon)-approximately optimal auction. Our results reinforce the common belief that optimal correlated auctions are sensitive to the distribution parameters and hard to learn unless the prior distribution is well-behaved.

Details

NeurIPS Conference 2021 Conference Paper

Least Square Calibration for Peer Reviews

  • Sijun Tan
  • Jibang Wu
  • Xiaohui Bei
  • Haifeng Xu

Peer review systems such as conference paper review often suffer from the issue of miscalibration. Previous works on peer review calibration usually only use the ordinal information or assume simplistic reviewer scoring functions such as linear functions. In practice, applications like academic conferences often rely on manual methods, such as open discussions, to mitigate miscalibration. It remains an important question to develop algorithms that can handle different types of miscalibrations based on available prior knowledge. In this paper, we propose a flexible framework, namely \emph{least square calibration} (LSC), for selecting top candidates from peer ratings. Our framework provably performs perfect calibration from noiseless linear scoring functions under mild assumptions, yet also provides competitive calibration results when the scoring function is from broader classes beyond linear functions and with arbitrary noise. On our synthetic dataset, we empirically demonstrate that our algorithm consistently outperforms the baseline which select top papers based on the highest average ratings.

PDF Details

AAAI Conference 2021 Conference Paper

Maximin Fairness with Mixed Divisible and Indivisible Goods

  • Xiaohui Bei
  • Shengxin Liu
  • Xinhang Lu
  • Hongao Wang

We study fair resource allocation when the resources contain a mixture of divisible and indivisible goods, focusing on the well-studied fairness notion of maximin share fairness (MMS). With only indivisible goods, a full MMS allocation may not exist, but a constant multiplicative approximate allocation always does. We analyze how the MMS approximation guarantee would be affected when the resources to be allocated also contain divisible goods. In particular, we show that the worst-case MMS approximation guarantee with mixed goods is no worse than that with only indivisible goods. However, there exist problem instances to which adding some divisible resources would strictly decrease the MMS approximation ratios of the instances. On the algorithmic front, we propose a constructive algorithm that will always produce an α-MMS allocation for any number of agents, where α takes values between 1/2 and 1 and is a monotonically increasing function determined by how agents value the divisible goods relative to their MMS values.

PDF Details

JAAMAS Journal 2021 Journal Article

Maximin fairness with mixed divisible and indivisible goods

  • Xiaohui Bei
  • Shengxin Liu
  • Hongao Wang

Abstract We study fair resource allocation when the resources contain a mixture of divisible and indivisible goods, focusing on the well-studied fairness notion of maximin share fairness (MMS). With only indivisible goods, a full MMS allocation may not exist, but a constant multiplicative approximate allocation always does. We analyze how the MMS approximation guarantee would be affected when the resources to be allocated also contain divisible goods. In particular, we show that the worst-case MMS approximation guarantee with mixed goods is no worse than that with only indivisible goods. However, there exist problem instances to which adding some divisible resources would strictly decrease the MMS approximation ratios of the instances. On the algorithmic front, we propose a constructive algorithm that will always produce an \(\alpha\) -MMS allocation for any number of agents, where \(\alpha\) takes values between 1/2 and 1 and is a monotonically increasing function determined by how agents value the divisible goods relative to their MMS values.

Details DOI

AAAI Conference 2021 Conference Paper

The Price of Connectivity in Fair Division

  • Xiaohui Bei
  • Ayumi Igarashi
  • Xinhang Lu
  • Warut Suksompong

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on the well-studied fairness notion of maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.

PDF Details

AAAI Conference 2020 Conference Paper

Fair Division of Mixed Divisible and Indivisible Goods

  • Xiaohui Bei
  • Zihao Li
  • Jinyan Liu
  • Shengxin Liu
  • Xinhang Lu

We study the problem of fair division when the resources contain both divisible and indivisible goods. Classic fairness notions such as envy-freeness (EF) and envy-freeness up to one good (EF1) cannot be directly applied to the mixed goods setting. In this work, we propose a new fairness notion envyfreeness for mixed goods (EFM), which is a direct generalization of both EF and EF1 to the mixed goods setting. We prove that an EFM allocation always exists for any number of agents. We also propose efficient algorithms to compute an EFM allocation for two agents and for n agents with piecewise linear valuations over the divisible goods. Finally, we relax the envy-free requirement, instead asking for -envyfreeness for mixed goods ( -EFM), and present an algorithm that finds an -EFM allocation in time polynomial in the number of agents, the number of indivisible goods, and 1/.

PDF Details

NeurIPS Conference 2019 Conference Paper

Balancing Efficiency and Fairness in On-Demand Ridesourcing

  • Nixie Lesmana
  • Xuan Zhang
  • Xiaohui Bei

We investigate the problem of assigning trip requests to available vehicles in on-demand ridesourcing. Much of the literature has focused on maximizing the total value of served requests, achieving efficiency on the passengers’ side. However, such solutions may result in some drivers being assigned to insufficient or undesired trips, therefore losing fairness from the drivers’ perspective. In this paper, we focus on both the system efficiency and the fairness among drivers and quantitatively analyze the trade-offs between these two objectives. In particular, we give an explicit answer to the question of whether there always exists an assignment that achieves any target efficiency and fairness. We also propose a simple reassignment algorithm that can achieve any selected trade-off. Finally, we demonstrate the effectiveness of the algorithms through extensive experiments on real-world datasets.

PDF Details

SODA Conference 2019 Conference Paper

Correlation-Robust Analysis of Single Item Auction

  • Xiaohui Bei
  • Nikolai Gravin
  • Pinyan Lu
  • Zhihao Gavin Tang

We investigate the problem of revenue maximization in single-item auction within the new correlation-robust framework proposed by Carroll [2017] and further developed by Gravin and Lu [2018]. In this framework the auctioneer is assumed to have only partial information about marginal distributions, but does not know the dependency structure of the joint distribution. The auctioneer's revenue is evaluated in the worst-case over the uncertainty of possible joint distribution. For the problem of optimal auction design in the correlation robust-framework we observe that in most cases the optimal auction does not admit a simple form like the celebrated Myerson's auction for independent valuations. We analyze and compare performances of several DSIC mechanisms used in practice. Our main set of results concern the sequential posted-price mechanism (SPM). We show that SPM achieves a constant (4. 78) approximation to the optimal correlation-robust mechanism. We also show that in the symmetric (anonymous) case when all bidders have the same marginal distribution, (i) SPM has almost matching worst-correlation revenue as any second price auction with common reserve price, and (ii) when the number of bidders is large, SPM converges to optimum. In addition, we extend some results on approximation and computational tractability for lookahead auctions to the correlation-robust framework.

Details

UAI Conference 2019 Conference Paper

Dynamic Trip-Vehicle Dispatch with Scheduled and On-Demand Requests

  • Taoan Huang
  • Bohui Fang
  • Xiaohui Bei
  • Fei Fang 0001

Transportation service providers that dispatch drivers and vehicles to riders start to support both on-demand ride requests posted in real time and rides scheduled in advance, leading to new challenges which, to the best of our knowledge, have not been addressed by existing works. To fill the gap, we design novel trip-vehicle dispatch algorithms to handle both types of requests while taking into account an estimated request distribution of on-demand requests. At the core of the algorithms is the newly proposed Constrained Spatio-Temporal value function (CST-function), which is polynomial-time computable and represents the expected value a vehicle could gain with the constraint that it needs to arrive at a specific location at a given time. Built upon CST-function, we design a randomized best-fit algorithm for scheduled requests and an online planning algorithm for on-demand requests given the scheduled requests as constraints. We evaluate the algorithms through extensive experiments on a real-world dataset of an online ride-hailing platform.

Details

AAMAS Conference 2019 Conference Paper

Optimal Trip-Vehicle Dispatch with Multi-Type Requests

  • Taoan Huang
  • Bohui Fang
  • Hoon Oh
  • Xiaohui Bei
  • Fei Fang

In recent years, traditional transportation platforms which mainly provide real-time ride-hailing services have started to accept rides scheduled in advance. The presence of both ride requests posted in real time and scheduled rides leads to new challenges to the service providers in deciding which requests to accept and how to dispatch the vehicles in a dynamic and optimal way, which, to the best of our knowledge, have not been addressed by existing works. To fill the gap, we provide the following contributions: (i) a novel two-stage decision-making model where in the first stage, the system decides whether to accept requests scheduled in advance in an online fashion, and in the second stage, dispatches vehicles to on-demand ride requests in real time given the accepted scheduled requests as constraints; (ii) novel algorithms for both stages that take an estimated distribution of on-demand ride requests into account to handle both on-demand and scheduled requests.

PDF

IJCAI Conference 2019 Conference Paper

The Price of Fairness for Indivisible Goods

  • Xiaohui Bei
  • Xinhang Lu
  • Pasin Manurangsi
  • Warut Suksompong

We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and equitability. However, these notions cannot always be satisfied for indivisible goods, leading to certain instances being ignored in the analysis. In this paper, we focus instead on notions with guaranteed existence, including envy-freeness up to one good (EF1), balancedness, maximum Nash welfare (MNW), and leximin. We mostly provide tight or asymptotically tight bounds on the worst-case efficiency loss for allocations satisfying these notions.

PDF Details

AAAI Conference 2018 Conference Paper

Algorithms for Trip-Vehicle Assignment in Ride-Sharing

  • Xiaohui Bei
  • Shengyu Zhang

We investigate the ride-sharing assignment problem from an algorithmic resource allocation point of view. Given a number of requests with source and destination locations, and a number of available car locations, the task is to assign cars to requests with two requests sharing one car. We formulate this as a combinatorial optimization problem, and show that it is NP-hard. We then design an approximation algorithm which guarantees to output a solution with at most 2. 5 times the optimal cost. Experiments are conducted showing that our algorithm actually has a much better approximation ratio (around 1. 2) on synthetically generated data.

PDF Details

AAMAS Conference 2018 Conference Paper

Efficient Auctions with Identity-Dependent Negative Externalities

  • Chaoli Zhang
  • Xiang Wang
  • Fan Wu
  • Xiaohui Bei

We investigate a class of single-item multi-supply auctions (including digital goods auctions with unlimited supply) with bidders who have identity-based negative externalities. In such an auction, each bidder has a set of competitors. Her private valuation from winning an item decreases with the number of her winning competitors. Negative externalities are prevalent in many applications, in which the auctioned goods play a role in future interactions among the auction’s participants, such as patent licensing and sponsored search auctions. However, the development of auctions with such externalities is stymied by the computational difficulty of the underlying welfare maximization allocation problem; even without consideration of truthfulness, the problem of social welfare maximization with general competition relations is NP-hard and even hard to approximate within a constant factor (unless P=NP). In this work, we design polynomial time and strategy-proof mechanisms under different restrictions on the underlying competition graph structure. Our results can be summarized as follows. (1) When each bidder has only one competitor, we propose a truthful and welfare maximizing mechanism. (2) We design a truthful and (1 + ϵ)-approximation mechanism when the underlying competition graph is planar. (3) We give two truthful mechanisms when bidders have arbitrary competition relations, with welfare approximation ratio (n/ logn) and ⌈(d + 1)/3⌉, respectively, where d is the maximum degree of the “undirected” competition graph.

PDF

IJCAI Conference 2018 Conference Paper

Truthful Fair Division without Free Disposal

  • Xiaohui Bei
  • Guangda Huzhang
  • Warut Suksompong

We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results in this setting have been established in previous works, they rely crucially on the free disposal assumption, meaning that the mechanism is allowed to throw away part of the resource at no cost. In the present work, we remove this assumption and focus on mechanisms that always allocate the entire resource. We exhibit a truthful envy-free mechanism for cake cutting and chore division for two agents with piecewise uniform valuations, and we complement our result by showing that such a mechanism does not exist when certain additional assumptions are made. Moreover, we give truthful mechanisms for multiple agents with restricted classes of valuations.

PDF Details

IJCAI Conference 2017 Conference Paper

Cake Cutting: Envy and Truth

  • Xiaohui Bei
  • Ning Chen
  • Guangda Huzhang
  • Biaoshuai Tao
  • Jiajun Wu

We study envy-free cake cutting with strategic agents, where each agent may manipulate his private information in order to receive a better allocation. We focus on piecewise constant utility functions and consider two scenarios: the general setting without any restriction on the allocations and the restricted setting where each agent has to receive a connected piece. We show that no deterministic truthful envy-free mechanism exists in the connected piece scenario, and the same impossibility result for the general setting with some additional mild assumptions on the allocations. Finally, we study a large market model where the economy is replicated and demonstrate that truth-telling converges to a Nash equilibrium.

PDF Details

IJCAI Conference 2017 Conference Paper

Networked Fairness in Cake Cutting

  • Xiaohui Bei
  • Youming Qiao
  • Shengyu Zhang

We introduce a graphical framework for fair division in cake cutting, where comparisons between agents are limited by an underlying network structure. We generalize the classical fairness notions of envy-freeness and proportionality in this graphical setting. An allocation is called envy-free on a graph if no agent envies any of her neighbor's share, and is called proportional on a graph if every agent values her own share no less than the average among her neighbors, with respect to her own measure. These generalizations enable new research directions in developing simple and efficient algorithms that can produce fair allocations under specific graph structures. On the algorithmic frontier, we first propose a moving-knife algorithm that outputs an envy-free allocation on trees. The algorithm is significantly simpler than the discrete and bounded envy-free algorithm introduced in [Aziz and Mackenzie, 2016] for compete graphs. Next, we give a discrete and bounded algorithm for computing a proportional allocation on transitive closure of trees, a class of graphs by taking a rooted tree and connecting all its ancestor-descendant pairs.

PDF Details

IJCAI Conference 2017 Conference Paper

Online Roommate Allocation Problem

  • Guangda Huzhang
  • Xin Huang
  • Shengyu Zhang
  • Xiaohui Bei

We study the online allocation problem under a roommate market model introduced in [Chan et al. , 2016]. Consider a fixed supply of n rooms and a list of 2n applicants arriving sequentially in an online fashion. The problem is to assign a room to each person upon her arrival, such that after the algorithm terminates, each room is shared by exactly two people. We focus on two objectives: (1) maximizing the social welfare, which is defined as the sum of valuations that applicants have for their rooms, plus the happiness value between each pair of roommates; (2) the allocation should satisfy certain stability conditions, such that no group of people would be willing to switch roommates or rooms. We first show a polynomial-time online algorithm that achieves constant competitive ratio for social welfare maximization. We then extend it to the case where each room is assigned to c > 2 people, and achieve a competitive ratio of Ω(1/c^2). Finally, we show both positive and negative results in satisfying different stability conditions in this online setting.

PDF Details

AAAI Conference 2016 Conference Paper

Learning Market Parameters Using Aggregate Demand Queries

  • Xiaohui Bei
  • Wei Chen
  • Jugal Garg
  • Martin Hoefer
  • Xiaoming Sun

We study efficient algorithms for a natural learning problem in markets. There is one seller with m divisible goods and n buyers with unknown individual utility functions and budgets of money. The seller can repeatedly announce prices and observe aggregate demand bundles requested by the buyers. The goal of the seller is to learn the utility functions and budgets of the buyers. Our scenario falls into the classic domain of “revealed preference” analysis. Problems with revealed preference have recently started to attract increased interest in computer science due to their fundamental nature in understanding customer behavior in electronic markets. The goal of revealed preference analysis is to observe rational agent behavior, to explain it using a suitable model for the utility functions, and to predict future agent behavior. Our results are the first polynomial-time algorithms to learn utility and budget parameters via revealed preference queries in classic Fisher markets with multiple buyers. Our analysis concentrates on linear, CES, and Leontief markets, which are the most prominent classes studied in the literature. Some of our results extend to general Arrow-Debreu exchange markets.

PDF Details

STOC Conference 2013 Conference Paper

On the complexity of trial and error

  • Xiaohui Bei
  • Ning Chen 0005
  • Shengyu Zhang 0002

Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems in which inputs are unknown . More specifically, we consider constraint satisfaction problems ⋀ i C i , where the constraints C i are hidden, and the goal is to find a solution satisfying all constraints. We can adaptively propose a candidate solution (i.e., trial ), and there is a verification oracle that either confirms that it is a valid solution, or returns the index i of a violated constraint (i.e., error ), with the exact content of C i still hidden. We studied the time and trial complexities of a number of natural CSPs, summarized as follows. On one hand, despite the seemingly very little information provided by the oracle, efficient algorithms do exist for Nash, Core, Stable Matching, and SAT problems, whose unknown-input versions are shown to be as hard as the corresponding known-input versions up to a factor of polynomial. The techniques employed vary considerably, including, e.g., order theory and the ellipsoid method with a strong separation oracle. On the other hand, there are problems whose complexities are substantially increased in the unknown-input model. In particular, no time-efficient algorithms exist for Graph Isomorphism and Group Isomorphism (unless PH collapses or P = NP). The proofs use quite nonstandard reductions, in which an efficient simulator is carefully designed to simulate a desirable but computationally unaffordable oracle. Our model investigates the value of input information, and our results demonstrate that the lack of input information can introduce various levels of extra difficulty. The model accommodates a wide range of combinatorial and algebraic structures, and exhibits intimate connections with (and hopefully can also serve as a useful supplement to) certain existing learning and complexity theories.

Details

AAAI Conference 2012 Conference Paper

Optimal Proportional Cake Cutting with Connected Pieces

  • Xiaohui Bei
  • Ning Chen
  • Xia Hua
  • Biaoshuai Tao
  • Endong Yang

We consider the classic cake cutting problem where one allocates a divisible cake to n participating agents. Among all valid divisions, fairness and efficiency (a. k. a. social welfare) are the most critical criteria to satisfy and optimize, respectively. We study computational complexity of computing an efficiency optimal division given the conditions that the allocation satisfies proportional fairness and assigns each agent a connected piece. For linear valuation functions, we give a polynomial time approximation scheme to compute an efficiency optimal allocation. On the other hand, we show that the problem is NP-hard to approximate within a factor of Ω 1 √ n for general piecewise constant functions, and is NP-hard to compute for normalized functions.

PDF Details

SODA Conference 2011 Conference Paper

Bayesian Incentive Compatibility via Fractional Assignments

  • Xiaohui Bei
  • Zhiyi Huang 0002

Very recently, Hartline and Lucier [14] studied single-parameter mechanism design problems in the Bayesian setting. They proposed a black-box reduction that converted Bayesian approximation algorithms into Bayesian-Incentive-Compatible (BIC) mechanisms while preserving social welfare. It remains a major open question if one can find similar reduction in the more important multi-parameter setting. In this paper, we give positive answer to this question when the prior distribution has finite and small support. We propose a black-box reduction for designing BIC multi-parameter mechanisms. The reduction converts any algorithm into an ε-BIC mechanism with only marginal loss in social welfare. As a result, for combinatorial auctions with sub-additive agents we get an ε-BIC mechanism that achieves constant approximation.

Details