Source author record

Ali Kakhbod

Ali Kakhbod appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

12works
6topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2016arXiv

Resource allocation with costly participation

We propose a new all-pay auction format in which risk-loving bidders pay a constant fee each time they bid for an object whose monetary value is common knowledge among the bidders, and bidding fees are the only source of benefit for the seller. We show that for the proposed model there exists a {unique} Symmetric Subgame Perfect Equilibrium (SSPE). The characterized SSPE is stationary when re-entry in the auction is allowed, and it is Markov perfect when re-entry is forbidden. Furthermore, we fully characterize the expected revenue of the seller. Generally, with or without re-entry, it is more beneficial for the seller to choose $v$ (value of the object), $s$ (sale price), and $c$ (bidding fee) such that $\frac{v-s}{c}$ becomes sufficiently large. In particular, when re-entry is permitted: the expected revenue of the seller is \emph{independent} of the number of bidders, decreasing in the sale price, increasing in the value of the object, and decreasing in the bidding fee; Moreover, the seller's revenue is equal to the value of the object when players are risk neutral, and it is strictly greater than the value of the object when bidders are risk-loving. We further show that allowing re-entry can be important in practice. Because, if the seller were to run such an auction without allowing re-entry, the auction would last a long time, and for almost all of its duration have only two remaining players. Thus, the seller's revenue relies on those two players being willing to participate, without any breaks, in an auction that might last for thousands of rounds

preprint2012arXiv

Games on Social Networks: On a Problem Posed by Goyal

Within the context of games on networks S. Goyal (Goya (2007), pg. 39) posed the following problem. Under any arbitrary but fixed topology, does there exist at least one pure Nash equilibrium that exhibits a positive relation between the cardinality of a player's set of neighbors and its utility payoff? In this paper we present a class of topologies/games in which pure Nash equilibria with the above property do not exist.

preprint2012arXiv

Market Mechanisms with Non-Price-Taking Agents

The paper develops a decentralized resource allocation mechanism for allocating divisible goods with capacity constraints to non-price-taking agents with general concave utilities. The proposed mechanism is always budget balanced, individually rational, and it converges to an optimal solution of the corresponding centralized problem. Such a mechanism is very useful in a network with general topology and no auctioneer where the competitive agents/users want different type of services.

preprint2012arXiv

On Describing the Routing Capacity Regions of Networks

The routing capacity region of networks with multiple unicast sessions can be characterized using Farkas' lemma as an infinite set of linear inequalities. In this paper this result is sharpened by exploiting properties of the solution satisfied by each rate-tuple on the boundary of the capacity region, and a finite description of the routing capacity region which depends on network parameters is offered. For the special case of undirected ring networks additional results on the complexity of the description are provided.

preprint2012arXiv

On the Construction of Prefix-Free and Fix-Free Codes with Specified Codeword Compositions

We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a given code for a special class of codes called distinct codes. We consider the construction of optimal fix-free codes which minimizes the average codeword cost for general letter costs with uniform distribution of the codewords and present an approximation algorithm to find a near optimal fix-free code with a given constant cost.

preprint2012arXiv

Power Allocation and Spectrum Sharing in Multi-User, Multi-Channel Systems with Strategic Users

We consider the decentralized power allocation and spectrum sharing problem in multi-user, multi-channel systems with strategic users. We present a mechanism/game form that has the following desirable features. (1) It is individually rational. (2) It is budget balanced at every Nash equilibrium of the game induced by the game form as well as off equilibrium. (3) The allocation corresponding to every Nash equilibrium (NE) of the game induced by the mechanism is a Lindahl allocation, that is a weakly Pareto optimal allocation. Our proposed game form/mechanism achieves all the above desirable properties without any assumption about, concavity, differentiability, monotonicity, or quasi-linearity of the users' utility functions.

preprint2012arXiv

Tight Bounds on the Redundancy of Huffman Codes

In this paper we study the redundancy of Huffman codes. In particular, we consider sources for which the probability of one of the source symbols is known. We prove a conjecture of Ye and Yeung regarding the upper bound on the redundancy of such Huffman codes, which yields in a tight upper bound. We also derive a tight lower bound for the redundancy under the same assumption. We further apply the method introduced in this paper to other related problems. It is shown that several other previously known bounds with different constraints follow immediately from our results.

preprint2011arXiv

Finding an Integral vector in an Unknown Polyhedral Cone

We present an algorithm to find an integral vector in the polyhedral cone $Γ=\{X | \textbf{A}X \leq \textbf{0}\}$, without assuming the explicit knowledge of $\textbf{A}$. About the polyhedral cone, $Γ$, it is only given that, (i) the elements of \textbf{A} are in $\{-d,-d+1,\...,0,\...,d-1,d\}$, $d \in \mathbb{N}$, and, (ii) $Y=[y(1),y(2),\...,y(n)]$ is a non-zero integral solution to $Γ$. The proposed algorithm finds a non-zero integral vector in $Γ$ such that its maximum element is less than ${(2d)^{2^{n-1}-1}}/{2^{n-1}}$.

preprint2011arXiv

Revenue Maximization in Spectrum Auctions for Dynamic Spectrum Access

We investigate revenue maximization problems in auctions for dynamic spectrum access. We consider the frequency division and spread spectrum methods of dynamic spectrum sharing. In the frequency division method, a primary spectrum user allocates portions of spectrum to different secondary users. In the spread spectrum method, the primary user allocates transmission powers to each secondary user. In both cases, we assume that a secondary user's utility function is linear in the rate it can achieve by using the available spectrum/power. Assuming strategic users, we present incentive compatible, individually rational and revenue-maximizing mechanisms for the two scenarios.

preprint2007arXiv

Tight Bounds on the Average Length, Entropy, and Redundancy of Anti-Uniform Huffman Codes

In this paper we consider the class of anti-uniform Huffman codes and derive tight lower and upper bounds on the average length, entropy, and redundancy of such codes in terms of the alphabet size of the source. The Fibonacci distributions are introduced which play a fundamental role in AUH codes. It is shown that such distributions maximize the average length and the entropy of the code for a given alphabet size. Another previously known bound on the entropy for given average length follows immediately from our results.